Идиот или гений? Как работает и на что способен искусственный интеллект

Если бы у черных было достаточно времени, они могли бы осуществить “полный поиск” по дереву игры: просчитать все возможные последовательности ходов и выбрать ход, который с наибольшей вероятностью приведет их к победе. Но в го такой обстоятельный поиск невыполним: как я уже упоминала, даже всего времени с момента рождения Вселенной недостаточно, чтобы провести полный поиск по дереву игры в го. Применяя метод Монте-Карло, черные просматривают лишь малую часть возможных последовательностей после каждого хода, подсчитывают количество побед и поражений, к которым ведут эти гипотетические последовательности, и на основе полученных результатов присваивают оценку каждому доступному ходу. Вдохновленная рулеткой случайность нужна, чтобы оценить возможные ходы.

В частности, чтобы выбрать ход из текущей позиции, черные “представляют” (то есть испытывают) несколько возможных сценариев развития игры, как показано на рис. 31B – D. В каждом испытании черные начинают с текущей позиции, случайно выбирают один из доступных ходов, затем (с новой позиции) случайно выбирают ход противника (белых) и так далее, пока моделируемая партия не закончится победой или поражением черных. Такое испытание, начинающееся с конкретной позиции на доске, называется разверткой с этой позиции.

На рисунке видно, что в трех развертках черные один раз победили и два раза проиграли. Теперь черные могут оценить все доступные ходы с текущей позиции на доске (рис. 31E). Ход 1 (левая стрелка) фигурировал в двух развертках, одна из которых закончилась победой, поэтому он получает оценку 1 из 2. Ход 3 (правая стрелка) фигурировал в одной развертке, которая закончилась поражением, поэтому он получает оценку 0 из 1. Ход 2 (центральная стрелка) вообще не проверялся, поэтому он получает оценку 0. Кроме того, программа ведет такую же статистику для всех промежуточных ходов в развертках. Когда очередной раунд поиска по дереву методом Монте-Карло заканчивается, программа использует скорректированные оценки, чтобы решить, какой из доступных ходов кажется наиболее перспективным (здесь – ход 1). Затем программа совершает этот ход в игре.

Я сказала, что в развертке программа выбирает ходы для себя и противника случайным образом, но на самом деле она делает вероятностный выбор, ориентируясь на оценки, которые эти ходы получали в предыдущих раундах поиска по дереву методом Монте-Карло. Когда каждая развертка заканчивается победой или поражением, алгоритм корректирует все оценки сделанных в этой партии ходов, чтобы отразить результат.

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

Таким образом, алгоритму поиска по дереву методом Монте-Карло не приходится гадать, какой ход с наибольшей вероятностью приведет к победе, ориентируясь лишь на текущую позицию: он использует развертки для сбора информации о том, как часто конкретный ход действительно приводит к победе или поражению. Чем больше разверток строит алгоритм, тем надежнее статистика. Как и раньше, программе необходимо найти баланс между использованием (выбором ходов, получивших самую высокую оценку при развертке) и исследованием (периодическим выбором ходов с низкой оценкой, для которых у программы еще мало статистических данных). На рис. 31 я показала три развертки, но в AlphaGo поиск по дереву методом Монте-Карло строил около двух тысяч разверток при каждом ходе.

Поиск по дереву методом Монте-Карло изобрели не специалисты по компьютерным наукам из DeepMind. Его предложили применить к деревьям игр в 2006 году, и это позволило значительно расширить способности программ для игры в го. Но этим программам оставалось не под силу победить людей. Одна из проблем заключалась в том, что накопление достаточной статистики из разверток занимает немало времени – особенно в го, где существует огромное количество допустимых ходов. Специалисты DeepMind поняли, что могут усовершенствовать систему, дополнив поиск по дереву методом Монте-Карло глубокой сверточной нейронной сетью. AlphaGo сообщает текущую позицию на доске обученной глубокой СНС, которая берет ее в качестве входного сигнала и присваивает расчетные значения ценности всем допустимым из этой позиции ходам. Затем поиск по дереву методом Монте-Карло использует эти значения ценности в качестве отправной точки: вместо того чтобы сначала выбирать ходы случайным образом, он рассматривает выходные сигналы сверточной сети в качестве индикатора предпочтительности начальных ходов. Представьте, что вы AlphaGo и смотрите на доску: прежде чем вы запустите процесс построения разверток из текущей позиции по методу Монте-Карло, сверточная сеть шепнет вам на ухо, какие допустимые из этой позиции ходы, вероятно, окажутся лучшими.