Семь главных игр в истории человечества. Шашки, шахматы, го, нарды, скрабл, покер, бридж

Но играющая компьютерная программа, которая воспринимала бы игру го с какой-то ясностью, никак не удавалась разработчикам. В 1997 году, вскоре после того, как программа Deep Blue обыграла Гарри Каспарова, газета New York Times процитировала одного астрофизика и игрока в го из Института перспективных исследований, который сказал: «В игре го компьютер возьмет верх над человеком лет через 100, а может быть, еще позже».

В решении проблемы го, дерево которой было по большей части недоступно для цифровых муравьев, почти не было прогресса, пока бывший профессор информатики Лилльского университета (Франция), Реми Кулом, не добился прорыва. Опираясь на свой опыт в компьютерных шахматах, он создал программу Crazy Stone, дебютировавшую в 2005 году. Это была одна из первых программ, в которых успешно использовался алгоритм поиска по дереву методом Монте-Карло (этот термин придумал Кулом). Эффект казался чудесным.

В общих чертах метод Монте-Карло, получивший свое название в честь знаменитого казино в Монако, предполагает использование результатов случайных событий для решения детерминированных, то есть имеющих фиксированный истинный ответ задач. Современная версия этой концепции была разработана при осуществлении Манхэттенского проекта. Данный метод часто полезен при громоздких вычислениях. Допустим, вы хотите вычислить значение числа π. Один из способов заключается в точном измерении окружности и диаметра идеального круга, если вам удастся найти такой, и подсчитать отношение этих величин. Другой, более занятный метод – рассыпать коробок спичек по дощатому полу. Каждая спичка соответствует диаметру воображаемого круга. Вероятность того, что один из этих кругов пересечет любую линию стыка досок пола, является величиной, содержащей π[27]. Чем больше спичек вы набросаете и чем больше проведете экспериментов, тем точнее будет вычисленное значение π. Так из случайности рождается изящество.

Поиск по дереву методом Монте-Карло, или MCTS (Monte Carlo tree search), задействует случайность для создания эффективного упрощения. В большинстве шахматных программ алгоритм перебирает многочисленные возможные позиции и оценивает качество каждого потенциального хода – главным образом путем подсчета стоимости фигур на каждой стороне доски[28]. В го подсчет стоимости фигур практически не имеет смысла. У обоих игроков приблизительно равное количество фишек на доске, причем все они одинаковые. Это все равно что пытаться сравнивать две картины Ротко по количеству мазков. Более того, игра разворачивается на всей доске. Мелкие стычки могут перерастать в полномасштабные сражения, и какой-нибудь камень в углу доски может оказывать влияние на камень в другом углу, отделенном от первого сотней ходов. В своей статье 2007 года Фэн-Сюн Сюй, ученый, работавший над Deep Blue, описал это следующим образом: «В типичной партии [го] у нас на доске запросто может одновременно возникать более 10 подобных проблем, и состояние одной группы может оказывать воздействие на ее соседей, как бывает, когда один ковбой направляет револьвер на другого и затем осознает, что на него самого нацелено ружье стрелка на крыше».

Другими словами, шахматная программа начинает с основания ствола дерева и лихорадочно оценивает сучья и ветки, пока не найдет перспективный путь в кроне. В го, где «дерево» до неприличия замысловато, MCTS пропускает нудное восхождение и просто сканирует случайную ветвь дерева. Алгоритм многократно проигрывает партию до конца, используя случайные ходы, и фиксирует результаты. Некоторые из этих рандомных ходов ведут к победам. Понятно, что такие ходы являются удачными, и программа присваивает им больший вес, когда рандомно воспроизводит игру в следующий раз. Многократно проделав это, MCTS генерирует карту удачных и неудачных ходов, хотя партия ни разу не разыгрывается традиционным образом. В самом деле, го – настолько сложная игра, что компьютеру легче играть в нее наугад, чем использовать традиционный подход поиска и оценки. Это так же удивительно и прекрасно, как найти значение π с помощью рассыпанных спичек.

Вооруженные до зубов интеллектуальными ресурсами и «железом» DeepMind и AlphaGo довели метод MCTS до сверхчеловеческого уровня. Они взяли алгоритмы глубокого обучения вроде тех, которые используются для распознавания лиц, и запрограммировали их на распознание сильных ходов в го. И в результате – быстрее, чем кто-либо мог ожидать, – программы го перешли от плохой игры к фантастической.

Мюллер посвятил свою карьеру изучению го. Его факультет выделил на решение этой проблемы уйму времени. А команда DeepMind за исключением пары заумных статей даже не намекала на то, что именно разрабатывается. И вдруг проблема го оказалась решенной. Стало ли это неожиданностью?

«О да, – сказал Мюллер, торжественно кивая. – О да».