Сложнее шахмат

Мир интеллектуальных игр очень богат. Почти все знакомы с шахматами и шашками, многие слышали про го и бридж, но про рэндзю, сянцы, сёги знают уже немногие. Между тем и в малоизвестных играх нередко можно найти не меньше красоты и глубины, в том числе и вычислительной. В этой статье мы вкратце расскажем об играх рэндзю и гомоку, их появлении, истории, развитии, а также о подходах к решению этих игр и противостоянии между человеком и машиной, научившейся играть в рэндзю.

Нить жемчуга

Базовые правила обеих игр очень просты и знакомы многим со времен школы: двое ставят по очереди камни, один (начинающий) — черные, второй — белые, на большую доску, при этом, чтобы выиграть, необходимо поставить непрерывный ряд из пяти своих камней по вертикали, горизонтали или диагонали. Под именем «крестики-нолики на бесконечном поле» в эту игру массово играют школьники и студенты, примерно в это же играли и китайцы четыре тысячи лет назад — принято считать, что игра зародилась в долинах рек Хуанхэ и Янцзы в начале второго тысячелетия до нашей эры, практически одновременно с игрой го. Тогда еще никто не видел в ней ни философского смысла, ни глубины, она служила просто для отдыха. Через пару тысяч лет, в начале нашей эры, игра попала в Японию, где получила и инвентарь — тот же, что и для игры го — камни и доску размером 19x19, и развитие, и даже имя — «гомокунарабэ» (пять штук в ряд). Примерно с пятнадцатого века появляются мэйдзины — чемпионы по игре в рэндзю.

Шло время, и первый большой шаг к аналитическому изучению игры был сделан с появлением книгопечатания — в XVI веке итальянские миссионеры завезли книгопечатание в Японию, а в XVII веке уже начали появляться частные типографии. Любителям интеллектуальных игр пришлось подождать, когда после выпуска духовных текстов и историй правителей издатели займутся, наконец, вопросами досуга. В середине XIX века в Европе появились серьезные исследования по теории шахмат,а в Японии — книги по теории го, рэндзю (тогда еще, мы помним, гомокунарабэ), сёги.

С точки зрения теории, шахматам повезло, так как преимущество первого хода в этой игре не очень велико, аналитикам есть где развернуться. А вот в гомокунарабэ процент выигрышей первого номера был чрезвычайно высоким. Проблему пришлось решать сложным путем: в игру в начале ХХ века была добавлена асимметрия в правилах, начинающему в расплату за право первого хода было запрещено делать ходы, при которых образовывались некоторые виды вилок (сначала две тройки, затем и две четверки), а также запрещалось завершать ряды из более чем пяти своих камней. Эти запрещенные ходы принято называть фолами. Немногим ранее, на рубеже веков, поэт в статье об игре назвал ее словом renju (連珠), что в переводе значит «нить жемчуга». С тех пор игру с асимметричными правилами принято ассоциировать с названием «рэндзю», а игру просто до пяти в ряд — с названием «гомоку».

Раскол и чемпионаты

Но уже в 1960-х годах и эта версия игры была исчерпывающе проанализирована в книге японского топ-игрока Сигэру Сагары. Впрочем, к моменту издания книги в Японии, где тогда играли лучшие рэндзисты мира, придумали способ полностью уравнять игру, лишив начинающего игрока перевеса простым, но изящным трюком. Вкратце его можно описать так: при постановке первых нескольких камней один игрок принимает большее участие в формировании позиции (например, ставит первые три камня, 2 черных и 1 белый), а второй игрок получает возможность выбрать цвет камней, которыми он хочет играть. Таким образом, первый игрок вынужден предлагать для выбора нечто максимально равное, иначе он проиграет. Так, если поставить оба черных камня в центр, а белый в угол, то черные легко выиграют. А если поставить черные камни по углам, а белый камень в центр, то тогда победят белые. Между этими двумя полюсами лежит широкий спектр самых разных по оценке позиций. Рэндзю с этими правилами — их называют дебютными регламентами — стало, конечно, куда менее интересным для математиков и кибернетиков, поскольку один из игроков теперь заинтересован не в выигрыше, а в создании максимально близкого к равенству положения. Зато в спортивности и состязательности игра выиграла.

К сожалению, появление фолов и ряд других изменений, произошедших в начале ХХ века (в частности, уменьшение размера доски до современного, 15х15 линий), внесли раскол в сообщество игроков. Этому немало способствовали конкретные игроки и их встречи за доской, даже объединительные. Так, уже в семидесятые годы мэйдзин «старой» версии шестидесятилетний Ёсидзава и «новой версии» молодой Накамура решили сыграть матч по правилам обеих федераций. Начали по «новым» правилам, современным, и Ёсидзава, проиграв первые пару партий из-за отсутствия привычки к фолам, сумел все же переломить ход матча и обыграл Накамуру на его же поле. Вторую часть матча решили не играть, Ёсидзава неодобрительно покачал головой, мол, эх, молодежь-молодежь, и объединение в тот раз не состоялось.

Кризис в среде рэндзистов усугубило поражение Японской империи во Второй мировой войне. Но в восьмидесятые годы игра, наконец, перестала быть эндемиком. Была образована международная федерация, начали проводиться турниры, в том числе чемпионаты мира. Поначалу безоговорочно лидировавших основателей со временем подвинули игроки из других стран — Эстонии, России, Китая.

Рэндзю в теории игр

В ХХ веке в теории игр нашлось место и играм «k в ряд на доске m на n». Этот класс игр даже получил собственное название: m,n,k-игры. С точки зрения классификации они являются детерминированными играми (как и го, но не как нарды), с полной информацией (как и шахматы, но не как бридж), с внезапной смертью (как и шахматы, но не как го), дивергентными (как и го, но не как шахматы). Эти термины означают следующее: в игре полностью исключена случайность; вся информация о положении в игре и всех возможных ходах игроков в каждый момент доступна каждому играющему; игра может окончиться при достижении одним из игроков определенной позиции (мат в шахматах, пятерка в гомоку и рэндзю); число имеющихся на доске «фигур» и, главное, количество возможных позиций растет от дебюта к эндшпилю.

Поскольку правилами разрешено пропускать ход, очевидно, что в гомоку у начинающего при оптимальной игре в кармане как минимум ничья, но этот подход не срабатывает с рэндзю из-за фолов. Многие из m,n,k-игр тривиальны, так, при k=1 начинающий всегда выигрывает, при k=2 лучшим исходом для начинающего является ничья, а при m=n=k=3 мы имеем обычные детские крестики-нолики с давно доказанной ничьей при оптимальной игре. Дело значительно затрудняется с увеличением размера доски, ведь сложность перебора вариантов возрастает экспоненциально с ростом площади.

В восьмидесятые годы на m,n,k-игры в очередной раз обратили пристальное внимание математики, так как на изучение и моделирование сложных игр из этого класса стало хватать вычислительных мощностей, и в 1993 году Виктором Аллисом, автором книги «Поиск решений в играх и сфере искусственного интеллекта», и программой Victoria было слабо решено гомоку, а в 2001 году венграми Яношем Вагнером и Иштваном Вирагом — рэндзю без дебютных регламентов, т.е. без специальной процедуры для первых ходов.

В теории игр считается, что игра решена сильно, если для каждой позиции известен ее исход при оптимальной игре, и слабо, если известен исход для начальной позиции, то есть построено полное дерево, позволяющее тому, кто должен выиграть, довести дело до успеха при любой игре оппонента, либо обоим игрокам гарантировать ничью, если решением является ничейный исход. Понятно, что о сильном решении го и рэндзю речь идти не может: число нулей в количестве возможных позиций в рэндзю превышает количество нулей в количестве, например, возможных шахматных позиций в два-три раза. Без специальных алгоритмов, отсекающих неперспективные варианты, рэндзю радикально, несравнимо сложнее шахмат — как и го, которое из-за большей доски еще сложнее.

Кремниевые игроки

Из-за нетривиальной дебютной процедуры научить компьютер играть в рэндзю не так-то просто (к тому же во второй половине ХХ века правила в дебютной части дополнительно усложнились). Тем не менее, в конце восьмидесятых и начале девяностых годов появились и соответствующие программы, и даже соревнования среди программ, пусть их уровень тогда оставался низким. Так, в 2000 году программа MEIJIN-2000, разработанная Олегом Степановым, приняла участие в турнире Moscow Open и финишировала

, показав игру уровня среднего или даже крепкого любителя. В 2000 году появилось соревнование для бесплатных движков, играющих в гомоку, —

. Поначалу качество игры оставляло желать лучшего, а лидеры определялись в непростой борьбе, пока в 2011 году пьедестал не заняла программа Yixin (автор Kai Sun), вплоть до нынешнего дня его никому не уступившая. Уровень ее игры можно считать довольно неплохим. Что касается рэндзю, то на gomocup.org эта игра впервые появилась в 2016 году и победу в ней тоже уверенно одержала программа Yixin.

По-настоящему серьезных матчей между людьми и программами в рэндзю и гомоку никогда не проводилось. Максимум — чешские игроки дважды под пиво играли командный матч против лучших программ из очередного розыгрыша gomocup.org, сыграв вничью в 2006-м и проиграв матч в 2011 году. Причина этого проста — до недавних пор топ-игроки были уверены в своем превосходстве. Принято считать, что сильный игрок в гомоку или рэндзю переиграет любую программу. Но так ли это?

Вскоре после последнего чемпионата gomocup.org, прошедшего в мае, на волне нашумевшего

AlphaGo и Ли Седоля, был согласован и проведен матч между лучшим AI в рэндзю, уже упомянутым выше Yixin, и белковым игроком. Человек победил со счетом 5:3, то есть с довольно шатким перевесом. Вероятно, если корпорация Google поставит себе такую же цель, как и с го, ждать победы кремниевого игрока останется недолго.