AlphaZero [2018] - история о плодотворной дружбе поиска и глубокого обучения

Обобщая, есть 2 поколения подходов в настольных играх:

1) Поиск по всем вариантам с оптимизациями
Шахматные алгоритмы, начиная с появления компьютеров, как минимум до Deep Blue [1997], работали на основе таких подходов. В глубине души они по эффективности похожи на полный перебор, но засчёт хитростей (вроде дебютной книги и эвристических оценок позиций в листьях дерева поиска) алгоритмам удаётся как-то работать.

2) Направленный поиск с помощью обучаемой функции полезности
Именно в этом и состояла революция AlphaGo (и её потомка AlphaZero). Оказалось, что обучаемая функция полезности действия в данной позиции позволяет перебирать радикально меньше вариантов ходов из каждой позиции. Она позволяет строить дерево поиска на больше ходов вперёд, потому что мы грамотно выбираем ходы при переборе.
Что интересно, обучается данная функция довольно просто - достаточно генерировать данные, садя алгоритм играть против себя же и своих прошлых итераций, и учить её предсказывать результат игры. В результате система легко обходит человека в шахматы и го.

Слабые точки AlphaZero понятны - требует много данных, обучается отдельно под одну игру. Но все революции за раз не совершить!

@knowledge_accumulator