Правила го просты и естественны. Возможно, по математической элегантности правил го занимает первое место среди всех игр. Тем удивительнее, что компьютеры, с их «генетической предрасположенностью» к решению математических задач, пытаясь «штурмовать» го, оказываются в положении беспомощного новичка или, в лучшем случае, старательного, но неумелого ученика. При этом в главной «европейской» игре — шахматах — лучшие программы уже несколько лет обыгрывают чемпионов мира! В чем особенность го, почему она неприступна для изощренных игровых алгоритмов?
Лес за деревьями
Вначале подумаем над тем, как машина вообще играет в игры — шахматы, шашки, реверси... Под машиной здесь и далее будем подразумевать программу на универсальном «железе», специальное аппаратное решение или их комбинацию.
Пусть в партии встретилась определенная позиция, и очередь хода за машиной. Основная процедура в середине игры — построение модельного дерева (когда не используется заготовленная библиотека дебютов или эндшпилей, которую уже загрузили в машину). Генерируются все возможные ходы «за себя», машина по очереди совершает их на виртуальной внутренней доске, и в каждой новой получившейся позиции снова повторяет ту же самую процедуру (подобный алгоритм называют рекурсией). Финальное условие рекурсии — достижение конечной позиции в игре (в шахматах это мат или теоретическая ничья).
Размеры получающегося «дерева» во всех распространенных играх не позволяют довести его рекурсивное построение до конечных позиций. Поэтому вводятся правила прекращения поиска — либо по достижении определенной глубины (числа полуходов от начальной позиции), либо на основании каких-либо дополнительных критериев эвристического характера. В таких модельно-заключительных позициях машина оценивает положение дел, присваивая узлам дерева перебора некоторые числовые значения. Затем, выбирая оптимальное решение (минимаксная процедура), машина «поднимает» эти значения от модельно-заключительных позиций к корню дерева — той позиции, в которой машина ищет ход. Выбирается ход, который дает наибольшую модельную оценку за себя (она же — наименьшая за противника).
Вопрос о том, как оценивать модельно заключительные позиции, — нетривиален. В шахматах есть хорошая эвристика — выигрыш материала обычно способствует победе в партии; поэтому в модельную оценку с большим весом входит соотношение сил на доске — количество фигур и пешек. Учитываются и позиционные факторы: контроль полей, пешечная структура, безопасность короля… Применять модельную статическую оценку в произвольной позиции небезопасно. Нужно обязательно сперва проанализировать возможные форсированные варианты (ФВ) — серии взятий за обе стороны, шахи и уходы из-под шахов, — то есть добиться относительно «спокойной» позиции.
Подобная структура алгоритма: построение модельного дерева, ФВ, статическая оценка и минимакс — уже стала классической. В шахматах перебор на четыре-пять полуходов с ФВ на современных машинах дает силу программы в районе крепкого первого разряда. А увеличение глубины перебора до 10–12 полуходов вплотную приближает машину к уровню лучших игроков-людей. Примерно так же обстоит дело в реверси и различных вариантах шашек.
Го — антишахматы?
Однако описанный выше подход оказался совершенно непродуктивным в отношении го. Главные отличия го от шахмат, приводящие к трудности программирования, таковы:
– Размеры дерева перебора. В шахматах типичная позиция миттельшпиля допускает 35–40 возможных ходов, в го их число в начале партии — свыше 300. Если Deep Blue (1997) в поединке с Каспаровым полностью просчитывала позицию на 12 полуходов, то в го компьютер сравнимой мощности осилил бы только 3–4 полухода.
– Неопределенность статической оценки. В го крайне трудно определить, является ли позиция модельно-заключительной и можно ли в ней применять статическую оценку. Зачастую результат тактической операции зависит от положения одного-единственного камня, который может находиться на другой стороне доски. Если в шахматах «форсированный вариант» можно определить как некий сходящийся процесс, приводящий к относительно стабильной позиции, то в го, которое являет собой пространство непрерывной борьбы, такое невозможно: слишком много «горячих точек» существует и продолжает оставаться практически до конца партии.
– Ко-борьба. Правило ко часто приводит к резкому изменению характера борьбы, последствия которой трудно оценить даже опытному игроку. Фактически надо каждый раз соизмерять последствия от «неответа» на ко-угрозу (как свою, так и противника) с ценой проигрыша ко-борьбы. Человеку приходится опираться на свой опыт и интуицию, в то время как для компьютера эти понятия трудно формализуемы.
– Отсутствие «точной» дебютной теории. Начальная стадия партии в го — фусеки — подчиняется определенным законам развития камней. Но для нее характерно гораздо большее разнообразие ходов, чем в шахматах. Новинки могут встречаться не на 20-м ходу, а уже на третьем или четвертом, и грамотная игра в дебюте невозможна без осмысления стратегических перспектив конструкций, возникающих на доске.
– Отсутствие «точной» теории эндшпиля. Окончание партии в го — есэ — самая «математическая» часть партии; в ней почти каждому ходу можно дать оценку с точки зрения количества приносимых ходом очков. Тем не менее и эта стадия оказывается компьютеру не по зубам — во многом из-зако-борьбы, неожиданно возникающей в вариантах тактики, а также вследствие трудностей, связанных с численной оценкой понятия инициативы. В отличие от шахмат, в го к концу игры доска не освобождается от фигур, а тесно заполняется камнями — что делает невозможным создание глобальных баз данных для окончаний.
Первые шаги по гобану
После знакомства с перечисленными трудностями кажется странным уже не то, что компьютеры не играют в го в силу профессиональных данов, а то, что они вообще способны хоть что-то понимать в этой игре! Тем не менее лучшие современные программы — Many Faces of Go, Go4++, Go Professional — играют в силу 12–15-го кю. Такого уровня игры человек достигает обычно за несколько месяцев активной игровой практики, имея в качестве партнера более опытного игрока.
Первая программа, сыгравшая на большой доске партию от начала до конца, была написана в 1968 году А. Зобристом (США). В 1984 году появились первые коммерческие го-программы — Acornsoft Go, Microgo 1 и Nemesis.
С 1987 года действует самое известное предложение в области компьютерного го. За победу компьютерной программы над чемпионом тайваньских любителей фонд Ing Foundation обещает 40 миллионов тайваньских долларов. Однако ни одна из современных программ претендовать на этот приз в ближайшие годы, увы, не в состоянии…
В 1997 году японская ассоциация го выдала специальный почетный диплом программе Handtalk, оценив ее третьим кю. Очевидно, эта оценка крайне завышена: в корейских рейтинг-листах та же Handtalk получает оценку не выше 15–17 кю.
По рейтингу Igs.nuri.net — самого популярного интернетовского го-сервера — программа Go4++ играет на уровне 14–16 кю.
Лабиринты го-программирования
Сегодняшние ссылки посвящены внутреннему устройству программ, играющих в го. Возможно, они подвигнут вас на более глубокое исследование алгоритмов. Не исключено, что среди читателей этой статьи окажутся будущие создатели электронного игрока-профессионала.
Игра го: хитросплетение камней — дальнейший рассказ о правилах и основных моментах игры. Жизнь и смерть. Стадии партии. Ссылки на популярные играющие программы.
Игра го: непреодолимый барьер для компьютеров? — о «взаимоотношениях» компьютеров и Го. Почему в шахматах компьютеры преуспели, а в Го — до сих пор нет? Ссылки на сайты по теории компьютерного Го и разработке программ.
Игра го: тактика на службе стратегии — продолжение введения в элементарную тактику Го: лестница, гэта, защёлка. Разбор примерной партии на доске 13х13.
http://www.