В 2007 году в мире
компьютерного Го произошел реальный прорыв - на малых досках программы достигли силы данов.
Хотя последние 10 лет прогресса в силе игры практически не было - что на большой (19x19), что на малой (9x9) досках программы играли примерно на уровне 10 кю. Классические "шахматные" алгоритмы (альфа-бета перебор на фиксированную глубину + ФВ + статическая оценка позиции) в
Го не работали - прежде всего из-за невозможности понять, когда же кусок позиции стабилизировался, чтобы ее можно было статически оценивать... а главное - как оценивать?..
Революция произошла с появлением алгоритма UCT.
По сути своей,
UCT - это алгоритм из семейства Монте-Карло. Для каждого возможного по правилам хода делается большое количество (порядка десятков или сотен тысяч) симуляций - фактически, пробных партий, состоящих из случайных ходов за обе стороны. Итог этих партий (окончательный счет очков по китайской системе) усредняется, и выбирается ход с наибольшим матожиданием.
И все! - никаких специальных знаний теории Го программе не требуется. В реальном алгоритме используется еще некоторая динамическая подстройка симуляций - более многообещающие узлы дерева посещаются чаще, но для анализа все равно используются только уже накопленные распределения вероятностей.
Алгоритмы семейства UCT активно исследуются уже несколько лет, но только недавно появились их эффективные реализации.
Лучшие из UCT-программ действительно играют на маленькой доске в силу дана, например,
программа MoGo. Родом она из Франции, автор успешно защитил по ней диссертацию и сразу прекратил дальнейшую разработку. Однако исходный код
программы для игры в Го был передан группе студентов, которые намерены продолжить исследования.
Интересная особенность Го-алгоритмов, основанных на Монте-Карло - в выигранной позиции они начинают делать сверх-надежные ходы, тем не менее не упускающие победу. Программа не делает различий между выигрышем в 30 камней и в половину камня - в результате обычно именно 0,5-1,5 камня и выигрывает. Именно так всегда предпочитали делать в партиях с любителями японские профессионалы, у них это считалось показателем стиля!
Есть у MoGo и слабости - она плохо понимает живые формы накадэ в углу.
Играть с
MoGo надо надежно, не пытаясь соревноваться с ней в тенуки. Если обоснованно отвечать ее на угрозы - через несколько ходов в ваших руках оказывается сэнте.
На большой доске программа играет не так сильно, хотя по результатам бота на KGS держится на уровне 2-3 кю.
По информации от автора, Linux-версия играет сильнее - так как лучше использует многопоточность.