Google DeepMind сообщила, что благодаря использующей обучение с подкреплением системе ИИ AlphaDev, удалось разработать усовершенствованные алгоритмы сортировки. В компании отмечают, что в отличие от общепринятых подходов, разработка велась с нуля при помощи игры, основанной на ассемблерных кодах.
Делая ход, AlhpaDev оценивала сгенерированный ей алгоритм и информацию в процессоре, а затем выбирала очередную инструкцию, которую добавляла при новом ходе. В DeepMind отмечают, что игра получилась невероятно сложной за счет огромного количества возможных комбинаций, число которых аналогично количеству частиц во вселенной или количеству возможных комбинаций ходов шахматах (10^120). При этом всего один неверный ход мог привести к порче всего алгоритма.
В конечном итоге AlphaDev обнаружила новые алгоритмы сортировки, которые были интегрированы в библиотеку сортировки LLVM libc ++ и позволили на 70% ускорить сортировку коротких последовательностей и примерно на 1,7% - последовательностей, превышающих 250 000 элементов.
Материал, посвященный этой работе, опубликован в журнале Nature.
