На рис. 31 показана схема поиска. Взгляните сначала на рис. 31A. Черным кружком на нем обозначена текущая позиция на доске, то есть конфигурация камней на доске на момент текущего хода. Допустим, программа играет в го черными и наступает очередь черных ходить. Для простоты допустим, что у черных есть три возможных хода, показанные тремя стрелками. Какой ход выбрать черным?
Если бы у черных было достаточно времени, они могли бы осуществить “полный поиск” по дереву игры: просчитать все возможные последовательности ходов и выбрать ход, который с наибольшей вероятностью приведет их к победе. Но в го такой обстоятельный поиск невыполним: как я уже упоминала, даже всего времени с момента рождения Вселенной недостаточно, чтобы провести полный поиск по дереву игры в го. Применяя метод Монте-Карло, черные просматривают лишь малую часть возможных последовательностей после каждого хода, подсчитывают количество побед и поражений, к которым ведут эти гипотетические последовательности, и на основе полученных результатов присваивают оценку каждому доступному ходу. Вдохновленная рулеткой случайность нужна, чтобы оценить возможные ходы.
В частности, чтобы выбрать ход из текущей позиции, черные “представляют” (то есть испытывают) несколько возможных сценариев развития игры, как показано на рис. 31B – D. В каждом испытании черные начинают с текущей позиции, случайно выбирают один из доступных ходов, затем (с новой позиции) случайно выбирают ход противника (белых) и так далее, пока моделируемая партия не закончится победой или поражением черных. Такое испытание, начинающееся с конкретной позиции на доске, называется разверткой с этой позиции.
На рисунке видно, что в трех развертках черные один раз победили и два раза проиграли. Теперь черные могут оценить все доступные ходы с текущей позиции на доске (рис. 31E). Ход 1 (левая стрелка) фигурировал в двух развертках, одна из которых закончилась победой, поэтому он получает оценку 1 из 2. Ход 3 (правая стрелка) фигурировал в одной развертке, которая закончилась поражением, поэтому он получает оценку 0 из 1. Ход 2 (центральная стрелка) вообще не проверялся, поэтому он получает оценку 0. Кроме того, программа ведет такую же статистику для всех промежуточных ходов в развертках. Когда очередной раунд поиска по дереву методом Монте-Карло заканчивается, программа использует скорректированные оценки, чтобы решить, какой из доступных ходов кажется наиболее перспективным (здесь – ход 1). Затем программа совершает этот ход в игре.
Я сказала, что в развертке программа выбирает ходы для себя и противника случайным образом, но на самом деле она делает вероятностный выбор, ориентируясь на оценки, которые эти ходы получали в предыдущих раундах поиска по дереву методом Монте-Карло. Когда каждая развертка заканчивается победой или поражением, алгоритм корректирует все оценки сделанных в этой партии ходов, чтобы отразить результат.
Сначала программа выбирает ходы из конкретной позиции на доске случайно (выполняя операцию, эквивалентную вращению рулетки), но в процессе моделирования других разверток, получая дополнительную статистику, все больше склоняется к выбору тех ходов, которые чаще всего приводили к победным разверткам.
Таким образом, алгоритму поиска по дереву методом Монте-Карло не приходится гадать, какой ход с наибольшей вероятностью приведет к победе, ориентируясь лишь на текущую позицию: он использует развертки для сбора информации о том, как часто конкретный ход действительно приводит к победе или поражению. Чем больше разверток строит алгоритм, тем надежнее статистика. Как и раньше, программе необходимо найти баланс между использованием (выбором ходов, получивших самую высокую оценку при развертке) и исследованием (периодическим выбором ходов с низкой оценкой, для которых у программы еще мало статистических данных). На рис. 31 я показала три развертки, но в AlphaGo поиск по дереву методом Монте-Карло строил около двух тысяч разверток при каждом ходе.
Поиск по дереву методом Монте-Карло изобрели не специалисты по компьютерным наукам из DeepMind. Его предложили применить к деревьям игр в 2006 году, и это позволило значительно расширить способности программ для игры в го. Но этим программам оставалось не под силу победить людей. Одна из проблем заключалась в том, что накопление достаточной статистики из разверток занимает немало времени – особенно в го, где существует огромное количество допустимых ходов. Специалисты DeepMind поняли, что могут усовершенствовать систему, дополнив поиск по дереву методом Монте-Карло глубокой сверточной нейронной сетью. AlphaGo сообщает текущую позицию на доске обученной глубокой СНС, которая берет ее в качестве входного сигнала и присваивает расчетные значения ценности всем допустимым из этой позиции ходам. Затем поиск по дереву методом Монте-Карло использует эти значения ценности в качестве отправной точки: вместо того чтобы сначала выбирать ходы случайным образом, он рассматривает выходные сигналы сверточной сети в качестве индикатора предпочтительности начальных ходов. Представьте, что вы AlphaGo и смотрите на доску: прежде чем вы запустите процесс построения разверток из текущей позиции по методу Монте-Карло, сверточная сеть шепнет вам на ухо, какие допустимые из этой позиции ходы, вероятно, окажутся лучшими.
Результаты поиска по дереву методом Монте-Карло, в свою очередь, используются для обучения нейронной сети. Представьте, что вы AlphaGo и уже осуществили поиск. Его результатами стали новые вероятности, присвоенные всем вашим допустимым ходам на основе того, как часто эти ходы приводили к победам или поражениям в построенных развертках. Далее новые вероятности используются для корректировки выходного сигнала сверточной сети с помощью метода обратного распространения ошибки. Затем вы с противником выбираете ходы, после чего позиция на доске меняется – и процесс продолжается. По сути, СНС учится распознавать паттерны, прямо как мастера го. В конце концов сеть начинает играть роль “интуиции” программы, которая подкрепляется поиском по дереву методом Монте-Карло.
Как и ее предшественница, шашечная программа Сэмюэла, AlphaGo учится, играя сама с собой и проводя огромное количество партий (около пяти миллионов). Во время обучения веса сверточной нейронной сети корректируются после каждого хода на основе различий между выходными ценностями сети и уточненными ценностями после проведения поиска по дереву методом Монте-Карло. Затем, когда AlphaGo играет с человеком вроде Ли Седоля, обученная СНС на каждом ходе присваивает ценности, которые становятся отправными точками для поиска.
Создав AlphaGo, специалисты DeepMind продемонстрировали, что один из давних больших вызовов ИИ покорился хитроумной комбинации обучения с подкреплением, сверточных нейронных сетей и поиска по дереву методом Монте-Карло (а также мощной современной вычислительной техники). В результате AlphaGo заняла заслуженное место в пантеоне ИИ. Но что дальше? Научится ли эта действенная комбинация методов генерализации за пределами игрового мира? Об этом я расскажу в следующей главе.
Глава 10
Не ограничиваясь играми
За последнее десятилетие обучение с подкреплением превратилось из относительно малоизвестного ответвления ИИ в одно из самых перспективных (и активно финансируемых) направлений развития отрасли. Возрождение обучения с подкреплением – особенно в глазах общественности – произошло во многом благодаря проектам DeepMind, которые я описала в предыдущей главе. Достижения DeepMind в играх Atari и го действительно феноменальны и заслуживают признания.
