Все знают игру крестики-нолики 3x3. При правильной игре при первом ходе крестиков результатом является ничья. Можно вручную составить дерево ходов, где на любой ход ноликов, существует ход крестиков, который ведет к наилучшему результату (для крестиков), то есть к ничьей или выигрышу. Это дерево ходов исчерпывает все варианты, поэтому говорят, что игра «решена». Существует трехмерная разновидность крестиков-ноликов 4x4x4 для которой ответ на вопрос, кто победит при первом ходе крестиков, не очевиден. Более того, возникает вопрос, можно ли построить такое минимальное дерево, которое будет решать эту задачу.

Ответ на этот вопрос под катом.

Напомню, что из себя представляет игра крестики-нолики 4x4x4 (её еще называют Qubic).
Это куб, состоящий из 64 полей, в котором для выигрыша необходимо поставить 4 подряд идущих крестика или нолика, причем они могут идти по любой линии, включая главные диагонали. Всего существует 76 таких линий — 48 горизонталей и вертикалей, 24 диагонали и 4 главные диагонали. Учитывая это, можно заметить, что не все поля одинаковы: существуют 8 угловых и 8 центральных полей, которые контролируют 7 линий и 48 остальных полей, которые контролируют по 4 линии. Поэтому, имеет смысл стараться занимать позиции, которые контролируют больше линий.


Какова же сложность построения дерева решений для этой игры? Грубо можно оценить как 2 в степени 64 вариантов, что достаточно много. Конечно, не все эти варианты реализуются в игре и многие ветви дерева отсекаются достаточно быстро, но и в этом случае построение такого дерева путем простого перебора не представляется возможным. Как же можно уменьшить перебор для того, чтобы решить эту задачу? Можно заметить, что после нескольких ходов крестиков и ноликов может возникнуть ситуация, при которой возможно создать угрозу противнику, поставив три крестика или нолика по одной линии. При такой угрозе противник вынужден делать свой следующий ход на оставшееся пустое место в данной линии, иначе он проиграет на следующем ходе. Таких ходов с угрозой можно делать несколько подряд, если в наличии имеется достаточное количество линий, на которых находятся только два крестика или, соответственно, нолика. Если такая цепочка ходов приводит к ситуации, в которой существует две линии с тремя крестиками или ноликами, то соответствующий игрок проигрывает. Это называется форсированным выигрышем.

Пронумеруем все поля числами от 0 до 63 начиная с верхней грани и идя горизонтальными линиями слева направо.



Проиллюстрируем это на примере одной игры:

0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48

Здесь крестики делают первый ход в левый дальний угол на верхней грани (0), затем нолики отвечают в правый дальний угол на той же грани (3). Крестики ходят в левый ближний угол на нижней грани (60), нолики отвечают в поле на второй сверху грани и т.д. После хода ноликов в 63, крестики начинают последовательность форсированных ходов: 4 — шах. Нолики вынуждены отвечать в 8, крестик 5 шах, нолики отвечают в 10 и т.д. до тех пор, пока у крестиков не образуются две линии с тремя крестиками. Нолики проиграли.

Для решения этой игры необходимо найти такие последовательности для всех возможных ходов ноликов. Для оптимального решения, такие последовательности должны быть минимальными.

Исторический экскурс

Первым, кто решил эту игру был Паташник (Patashnik) в начале 80-х годов. Он вручную подбирал начальные комбинации, а затем искал выигрышный ход с помощью компьютера. Он показал, что если крестики ходят в угол, то они всегда выигрывают при правильной игре. Следующий шаг сделал Виктор Аллис (Victor Allis). В своей диссертации в середине 90-х годов он показал, что решение может быть получено полностью на компьютере. Однако, он проверял не все варианты, которыми крестики могут прийти к выигрышу, а только десять первых, наиболее перспективных. Поэтому его решение не было оптимальным и он оставил эту задачу другим исследователям.

Решением этой задачи оптимальным образом, то есть нахождением минимального дерева решил заняться я. Очевидно, что для этого необходимо использовать поиск в ширину, в отличие от поиска в глубину у Аллиса. В первую очередь, был реализован поиск форсированного выигрыша для произвольной ситуации. Оказалось, однако, что он получился довольно медленный, поскольку поиск в глубину для форсированного выигрыша для длинных комбинаций довольно затратный. Выход был найден путем добавления хранилища уже просчитанных вариантов в std::unordered_set. Стоит сказать, что игровое поле было закодировано в виде двух 64 битных переменных, одной для крестиков, одной для ноликов, где 1 означает наличие крестика или нолика в соответствующем поле. Такое кэширование дало значительное ускорение. Однако, основная проблема заключалась в поиске в ширину для нефорсированных ходов. При обычном поиске без оптимизации расчет не заканчивался за разумное время.

Пришлось опять обратиться к кэшированию. К просчитанному игровому полю был добавлен еще один байт с результатом расчета поддерева для этого варианта расстановки крестиков и ноликов. При этом кодировка игрового поля стала занимать 17 байтов. Таким образом, при поиске в ширину и постепенном увеличении глубины дерева можно было отбрасывать уже просчитанные поддеревья. С помощью этого мне удалось рассчитать минимальные деревья
для первого хода крестика в угол (клетка 0) и ответов ноликов во все поля, которые контролируют по четыре линии.

Трудности возникли, если нолики первым ответным ходом занимали поле, которое контролировало семь линий. В этом случае объем памяти, занимаемой кэшем стал превышать 32 гигабайта ОЗУ, и мой Linux уходил в своп. Необходимо было искать другое решение.

Тут я обратился к тому факту, что игровое поле имеет множество автоморфизмов, то есть если найти решение для одной комбинации крестиков и ноликов, то и комбинации, соответствующие различным поворотам и отражениям также будут иметь решение. Тут надо заметить, что благодаря этим автоморфизмам первый ход крестиков имеет всего два варианта — один в поле 0 (контролирующее 7 линий) и один в поле 1 (контролирующее 4 линии). Поэтому в моем случае первый ход крестики делают всегда в поле 0. Но это справедливо только для пустого поля.

Вернемся, однако, к автоморфизмам для произвольного игрового поля. Как их все найти?
Я использовал следующий способ: поскольку у кубика размерность три, то можно переставлять координаты (таких перестановок будет 6) и делать отражения (их будет 8). Стало быть, всего пространственных автоморфизмов будет 48. Однако, у кубика есть еще два внутренних автоморфизма. Один переставляет координаты полей в первой и второй паре в каждой линии,
а второй оставляет первое и последнее поле на месте, а переставляет только координаты для второго и третьего поля. Эти два автоморфизма можно также применить одновременно. Таким образом, для каждого из 48 пространственных автоморфизмов существуют четыре
(включая тривиальный) внутренних автоморфизмов. Иного для всего кубика существуют 192 автоморфизма. Это дает надежду на существенное сокращение количества хранимых уже просчитанных полей.

Однако, тут возникает другая проблема: если проверять все 192 автоморфизма, то необходимо быстро преобразовывать игровое поле путем перестановки бит. Если это преобразование не сделать быстрым, то все время будет уходить на него, выигрыша в производительности не будет и вся затея с автоморфизмами вылетит в трубу. Поэтому я занялся поиском в интернете быстрого способа переставлять биты. Сказать честно, я не нашел ничего подходящего. Единственный приемлемый быстрый способ переставить биты — это заранее составить таблицу и выбирать в ней уже готовое решение имея в качестве индекса текущее игровое поле. Для меня такой способ не подходил, поскольку необходимо было иметь массив из 2 в степени 64 шестидесятибитных слов.

Я уже совсем хотел оставить эту идею, однако, мне в голову пришла мысль о том, что не обязательно иметь одну большую таблицу, а можно иметь несколько маленьких. В принципе, можно было выбрать разное количество таких таблиц, но я остановился на 8 таблицах по 256 слов (для каждого автоморфизма). Таким образом, для перестановки бит я беру один байт из 64 битного поля и, в заранее просчитанной таблице, выбираю шаблон, где биты уже стоят на своих местах (если они, конечно, не нулевые в исходном поле). Затем беру следующий байт из 64 битного поля и в следующей заранее просчитанной таблице выбираю другой шаблон и делаю логическое «или» с первым. И так 8 раз. Поскольку эти операции не содержат условных переходов, они должны производиться достаточно быстро не нарушая конвейера в процессоре.

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

Заключение и последующие разработки

После создания вышеописанной программы стало возможно за несколько дней найти почти оптимальное дерево для игры крестики-нолики 4x4x4. Почему «почти оптимальное»? Потому, что не учитывается суммарная длина форсированных ходов и может так случиться, что существует дерево для нефорсированных ходов одинаковой глубины, но с меньшей общей глубиной форсированных ходов. Но я думаю, что это не очень большой недостаток.

Таким образом, игра крестики-нолики 4x4x4 полностью просчитана, крестики всегда выигрывают и эту тему можно закрывать? Не совсем. Дело в том, что поскольку крестики ходят первыми, они имеют преимущество. Что, если попробовать это преимущество как-либо скомпенсировать? Я предлагаю следующую идею — запретить крестикам первым ходом ставить крестик в поле, которое контролирует 7 линий, ограничивая их только полями, контролирующими только 4 линии. Несмотря на то, что это кажется небольшим изменением, на самом деле результат игры может существенно измениться и нолики смогут свести игру в ничью, а может, и выиграть. Так, что тут есть что исследовать.