DeepMind обновила библиотеку C++ своими уникальными алгоритмами сортировки данных

DeepMind - британская компания, которая занимается исследованиями и разработками в области искусственного интеллекта (ИИ), известна тем, что создала систему ИИ AlphaZero, которая может обучаться играть в настольные игры, такие как шахматы, го и сёги, без человеческого наставления. AlphaZero использует метод обучения с подкреплением, при котором система ИИ учится на своем опыте, получая награду или наказание за свои действия.

Теперь DeepMind применила этот метод к другой задаче - созданию алгоритмов сортировки данных. Сортировка - это важная и распространенная задача компьютерной науки, которая лежит в основе многих приложений, от баз данных до поисковых систем. Эффективность сортировки влияет на производительность и качество вычислений. Несмотря на десятилетия исследований в области разработки и оптимизации алгоритмов сортировки, дальнейшие улучшения оказались труднодостижимыми как для человеческих экспертов, так и для вычислительных методов. Теперь искусственный интеллект смог преодолеть этот барьер и открыть новые алгоритмы.

В статье, опубликованной в журнале Nature , группа ученых из компании DeepMind представила новую систему ИИ, названную AlphaDev. Эксперты поставили перед ИИ задачу поиска лучшего алгоритма сортировки в виде однопользовательской игры, в которой ИИ должен генерировать последовательности команд на языке ассемблера для сортировки массивов различной длины и типов данных. Целью игры является минимизация времени выполнения алгоритма на реальном процессоре.

Для решения этой задачи ИИ использовал метод обучения с подкреплением, который позволяет обучаться на основе своего опыта и получаемой награды. ИИ не имел никаких знаний о существующих алгоритмах сортировки или общих принципах программирования. Он начинал со случайных команд и постепенно улучшал свои алгоритмы, получая обратную связь от процессора о времени выполнения. ИИ также использовал технику генерации и испытания кандидатов (Generation and Testing of Candidates, GTC ), которая позволяет эффективно искать и оценивать пространство корректных и быстрых программ.

Благодаря этим методам AlphaDev создал алгоритмы сортировки данных, которые работают до трех раз быстрее, чем алгоритмы, созданные человеком. Эти алгоритмы были переведены из языка ассемблера в язык C++ и включены в официальную библиотеку языка C++, которая используется в рамках популярного набора компиляторов LLVM. Это первый раз, когда алгоритм, созданный с помощью ИИ, был включен в эту библиотеку.