Алгоритм сортировки, созданный ИИ, работает в 3 раза быстрее всех придуманных математиками за столетие

На протяжении столетия ученые оптимизируют способы сортировки данных, чтобы сэкономить время при выдаче результатов поиска. Компания DeepMind значительно повысила скорость сортировки, применив технологию, лежащую в основе AlphaZero — системы искусственного интеллекта для игры в настольные игры: шахматы, го и сёги — к игре по созданию алгоритмов сортировки. Система «играющая» в сортировку получила название AlphaDev.

Эта система нашла более быстрые алгоритмы, которые уже стали частью двух стандартных библиотек программирования на C++. Теперь они будут использоваться триллионы раз в день всеми устройствами по всему миру.

Исследователи применили AlphaDev к задаче сортировки чисел. Они начали с малого, — с алгоритмов, которые сортировали только 3, 4 или 5 чисел, но они важны, поскольку используются алгоритмами, которые сортируют более длинные списки. AlphaDev работал на уровне инструкций ассемблера. Сегодня на ассемблере пишут редко. Это - язык, генерируемый компиляторами из программ высокого уровня, например, C++. Писать на нем довольно утомительно, но у него есть замечательное свойство — очень простой набор команд. Он даже менее разнообразен, чем ходы в шахматной партии.

AlphaDev работает аналогично своему предшественнику AlphaZero, который ищет оптимальные ходы в настольных играх. Но AlphaDev ищет не ходы; вместо этого он выбирает ассемблерные инструкции для добавления в процедуру сортировки (инженеры DeepMind называют этот процесс AssemblyGame).

В каждой точке принятия решения AlphaZero рассматривает возможные ходы, возможные ходы после каждого из этих ходов и так далее по ветвям, вычисляя, какие ходы с наибольшей вероятностью приведут к выигрышу. Рассмотрение всех возможных ветвей может занять больше времени, чем возраст Вселенной, поэтому для сокращения поиска используется что-то вроде «интуиции». На каждом шаге компьютерная программа передает состояние игры в нейронные сети, которые и решают какой ход является наиболее перспективным. Во время обучения нейросеть постоянно обновляет свои параметры, основываясь на результатах игры.

AlphaDev может выполнить одно из четырех типов действий (это своего рода ходы в игре на ускорение): задание значения ячейки, сравнение значений ячеек, перемещение значений между ячейками, переход к другой части программы. После каждого действия AlphaDev пытается отсортировать входные списки (например, наборы чисел) и получает вознаграждение за то, сколько элементов в списках он отсортировал правильно. AlphaDev играет до тех пор, пока не отсортирует все списки идеально или не достигнет предела длины программы, после чего начинает новую программу с нуля.

Нейронные сети оценивают и награждают программы не только за правильность сортировки, но и за скорость. Команда Даниэля Манковица, руководителя разработки, обучила систему оценивать скорость на основе либо общего количества инструкций, либо времени обработки. В зависимости от используемого процессора и количества сортируемых значений, время работы лучших алгоритмов AlphaDev меньше от 4% до 71%, чем у программ сортировки, разработанных человеком. Но когда алгоритмы вызывались несколько раз для сортировки списков из четверти миллиона значений, суммарная экономия времени составляла всего 1-2%. Это связано с тем, что весь остальной код, используемый в таком случае, не был оптимизирован ИИ.

Команда DeepMind применила AlphaDev к алгоритмам, не связанным с сортировкой. Ее версия алгоритма, используемого для конвертирования данных из одного формата в другой (это тоже классическая задача программирования), заняла на 67% меньше времени, чем стандартная версия. А алгоритм хэширования, используемый для хранения и поиска данных, занял на 30% меньше времени, чем стандартный.

Чтобы понять, как именно AlphaDev добилась такого успеха, команда более подробно рассмотрела алгоритмы, созданные ИИ. Для сортировки они нашли две новые тактики, которые назвали AlphaDev swap move и AlphaDev copy move. Манковиц сравнивает их с «ходом 37», удивительным ходом, который AlphaGo, предшественник AlphaZero, сделал против чемпиона по игре в го Ли Седоля в 2016 году во время выставочного матча в Сеуле.

«Я не вижу, чтобы там была какая-то особая научная новизна», — говорит Майкл Литтман, ученый из Университета Брауна. - «Но инженерный эффект разработки просто феноменальный». Он подчеркнул, что исследователи из DeepMind умеют замечательно приспосабливать свои методы к новым задачам. В прошлом году DeepMind модифицировала AlphaZero для создания AlphaTensor. Это — алгоритм, который сильно ускорил перемножение матриц. Это тоже важнейшая задача программирования.

В будущем команда DeepMind намерена применить алгоритмы в стиле AlphaZero к еще большему числу задач, в том числе к проектированию аппаратного обеспечения, говорит Манковиц: «Мы действительно хотим решать весь стек». То есть, с помощью «игры» исследователи намерена оптимизировать все программы — от аппаратного обеспечения до стандартных библиотек. Если это удастся, все программы, работающие на всех устройствах в мире, радикально ускорятся.