Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?
Реми Кулэм (слева) с компьютерной программой Crazy Stone против гроссмейстера Норимото ЙодыВ 1994 году компьютер обыграл чемпиона мира по шашкам, в 1997 году — по шахматам. Сегодня компьютеры превосходят людей абсолютно во всех играх с полной информацией, кроме одной — го.
У классической игры с 2500-летней историей очень простые правила, но компьютерные программы даже близко не могут подобраться к победе над лучшими гроссмейстерами, пишет Wired.Древнюю игру можно считать «восточной версией шахмат». Как и шахматы, это игра с полной информацией, то есть в любой момент игры все игроки имеют полную информацию о состоянии игры и воздействуют на игру дискретными действиями. Здесь успех не зависит от удачи или скорости реакции.
Несмотря на рост вычислительной мощи компьютеров — чемпион мира по шахматам сегодня, вероятно, проиграет даже вашему домашнему ПК — алгоритмы игры в го на экспертном уровне остаются нерешённой и одной из самых интересных задач ИИ. Проблема ещё и в том, что очень немногие способны подняться до девятого дана в игре. Для этого нужно несколько лет обучаться в Японии или Корее. Там талантливых детей забирают из дома для обучения в академии го примерно с 9 лет.
Продвинутые любители почти всегда застревают на определённом уровне игры и не могут улучшить результат: «Требуется некий ментальный прыжок, чтобы снять эту блокировку, и в разработке программ та же проблема, — объясняет Дэвид Фотлэнд (David Fotland), главный разработчик процессора PA-RISC в компании Hewlett Packard в 70-е годы. Он тестировал программу го на процессоре своей разработки. — Вопрос в том, как оценивать всю доску, а не отдельные фрагменты».
Игра давно пользовалась популярностью не только на востоке, но и на западе, особенно среди математиков и физиков. Например, Эйнштейн частенько играл в го, также как знаменитые математики Джон Нэш и Алан Тьюринг.
Компьютерные программы для го разрабатывают уже 45 лет, этой проблеме уделяли почти столько же внимания, сколько и шахматным программам. Первую написал гений теории игр Альфред Зобрист в 1968 году. Она могла обыграть абсолютного новичка, который только что познакомился с правилами (запись первой игры человек-компьютер). Начало казалось оптимистичным. В следующие четыре десятилетия было потрачено огромное количество времени и интеллектуальных усилий, но даже с учётом прогресса в вычислительной мощности программы так и не смогли одолеть даже продвинутого любителя.
Причину можно понять, если сравнить го с шахматами. В начале шахматной партии у белых есть 20 возможных ходов, а у чёрных — 20 возможных вариантов ответа. После первого хода на доске может быть 400 различных позиций. А теперь сравните цифры в го: на доске 19×19 у чёрных есть 361 возможных начальных ходов, а у белых 360 вариантов ответа. Это означает 129 960 возможных комбинаций только после первого раунда.
Так называемый «фактор ветвления» — среднее количество ходов, доступных в каждом раунде — в шахматах составляет 35, в го — 250. Игры с сильным ветвлением затрудняют работу стандартных алгоритмов, использующих правило минимакса для создания дерева возможных комбинаций. Даже с учётом анализа не всех, а только перспективных ветвлений для более глубокого анализа. То, что работает в шашках и шахматах, не работает в го. Выбор перспективных ветвлений в дереве возможных комбинаций го — часто совершенно таинственный процесс. Даже игроки не понимают, как они это делают: «Просто смотришь на доску и знаешь», говорят они.
Опять же, в шахматах почти всегда можно понять, кто выигрывает, хотя бы по числу фигур. В го ситуацию могут толковать только эксперты.
Среднее количество ходов в игре: в шахматах — около 40, в го — 200. Учитывая фактор ветвления и эту статистику, становится понятным бессилие компьютеров.
Талантливый французский программист Реми Кулэм (Rémi Coulom) добился первого успеха с программой Crazy Stone в 2006 году, когда догадался совместить минимакс и метод Монте-Карло. Новый алгоритм расчёта дерева ветвлений он назвал Monte Carlo Tree Search или MCTS. Француз выиграл чемпионат среди компьютерных программ UEC Cup в 2007 и 2008 годах, но это так и не принесло ему известности, и Реми забросил разработку. Но в 2010 году он получил предложение от японского игрового разработчика Unbalance — и в 2011 году вышла первая коммерческая версия Crazy Stone. В 2013 году Реми победно вернулся на чемпионат.
Однако, в 2014 году случилась неудача. В финальном противостоянии против программы Zen зрители поняли, что творится нечто странное уже после третьего хода. Программа Zen, после стандартной постановки двух камней по углам вдруг поставила третий камень около центра. Так никто не играл, это было явно «нечеловеческое» решение. Вскоре уровень победных ожиданий у Crazy Stone вырос до неприлично высоких значений, более 60%. Судя по всему, программа считала безопасной группу камней в правом верхнем углу, хотя она не была безопасной. Поскольку успешная стратегия напрямую зависит от правильной оценки доски, зрители начали шептаться о возможном поражении Crazy Stone. Так оно и вышло: на 186 ходу Crazy Stone признала поражение, а Zen стал новым чемпионом UEC Cup.
Впрочем, у Кулэма осталась возможность реванша. Как финалист, он получил право играть против настоящего гроссмейстера-человека с форой в четыре камня. В этом году на турнир приехал Норимото Йода. Японский гроссмейстер сел за стол в традиционном зелёном кимоно. Реми Кулэм — в очках без оправы и синем свитере, в которых был и на прошлом чемпионате.
Комментаторы-профессионалы, которые сопровождали онлайн-трансляцию партии, сошлись во мнении, что Crazy Stone играет неплохо и даже имеет преимущество. Йода был исключительно раздражён и выглядел сурово, а Кулэм суетился, посматривая то на ноутбук, то на игровую доску, то на хронометр — куда угодно, только не на Йоду.
Обидное поражение Crazy Stone потерпела в самой концовке. Выигрывая 11 камней, любой человек сделал бы несколько очевидных защитных ходов, чтобы не дать противнику отыграться и сохранить преимущество. Но Crazy Stone была запрограммирована только на победу. Поэтому её алгоритм состоял в том, чтобы в ситуации выигрыша делать бессмысленные ходы в собственной зоне, ожидая, когда соперник признает поражение. Но здесь такой фокус не прошёл — и Йода сумел отыграться. Во втором матче против Zen он уже выглядел получше и выиграл у программы четыре камня.
Реми Кулэм всё равно был счастлив — и пообещал к следующему чемпионату доработать алгоритм действий в концовке.
Судя по всему, скоро компьютер выиграет в последнюю игру с полной информацией, которая пока остаётся за человеком. По оценке Кулэма, программа выиграет без форы в течение 10 лет. Эксперты, знающие силу лучших игроков, не так уверены. Дело в том, что на высших уровнях игра выходит на качественно иной уровень, ходы перестают быть предсказуемыми. В то же время качество игры программ до сих пор полагается на вычислительную мощь, сколько на качество кода: например, те же Crazy Stone и Zen на 64-ядерных стандартных серверах легко побеждали 2048-ядерные кластеры противников. То есть программы могут снова уткнуться в стену.
Но даже если компьютеры и выиграют в го, нельзя говорить о «падении последнего интеллектуального бастиона», где доминирует человек, как это писали газеты после победы Dep Blue в шахматах. Программы для го — это просто узкоспециализированные инструменты для решения конкретных задач. Они весьма далеки от человеческого разума и не пытаются эмулировать работу мозга. «Для меня это просто развлечение, — говорит Кулэм, — не более того».
