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

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

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

image

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

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

image

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

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 линии. Несмотря на то, что это кажется небольшим изменением, на самом деле результат игры может существенно измениться и нолики смогут свести игру в ничью, а может, и выиграть. Так, что тут есть что исследовать.

Комментарии (16)


  1. ilynxy
    26.10.2017 21:23

    en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets
    Parallel bit deposit and extract — то что надо?
    Могу попробовать помочь с оптимизацией под x86.


  1. DistortNeo
    27.10.2017 01:49

    У меня есть следующие соображения:

    Проверять все 192 автоморфизма не нужно. Достаточно после каждого хода преобразовывать поле к каноничному виду — выбирать автоморфизм, который бы имел, например, минимальный индекс.

    Вычисление и перебор всех 192 значений — задача действительно вычислительно сложная. Но эту задачу можно значительно упростить, если изменить порядок нумерации бит в кубе: сначала идут 8 вершин куба (XA), затем 8 вершин центральной части 2х2х2 (XB), затем остальные 48 ячеек (XC). То есть конфигурация поля кодируется как [XA8 XB8 XC48] [OA8 OB8 OC48] [F]. Пока рассматривается только отражение и перестановка координат.

    При автоморфизмах (перестановка координат, отражение) биты остаются в вершинах куба, отсюда следует, что перестановка бит будет осуществляться в пределах XA8, XB8 и XC48, не влияя друг на друга. Причём таблицы преобразования для XA8 и XB8 будут одинаковы. Аналогично можно и XC48 перегруппировать, если есть желание.

    Ну а дальше дело техники. Если нам нужно найти минимальный автоморфизм, то делаем так: создаём таблицу, которая для каждого префикса XA8 выдаёт список автоморфизмов, имеющих префикс, совпадающий с префиксом каноничного автоморфизма. Список будет совсем небольшой. Далее делаем перебор для XB8, выбирая минимальный префикс. Если остаётся более 1 варианта, то делаем перебор по XC48. Случаи XA8 = 0 и XA8 = 255 рассматриваются отдельно.

    Таким образом, вместо вычисления 192 автоморфизмов, на каждом шаге их будет около десятка, что должно сильно ускорить вычисления.

    Условных переходов будет мало. Во-первых, условные переходы для XA8 = 0 и XA8 = 255 будут прекрасно обрабратываться предсказателем переходов. Во-вторых, список возможных автоморфизмом можно сделать фиксированного размера, просто дополнив его повторящимися автоморфизмами.


    1. andy_p Автор
      27.10.2017 12:26

      Хмм...


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


      1. Sayonji
        27.10.2017 13:31

        Предлагается выделить какое-то одно состояние из изоморфных, скажем минимальное если интерпретировать как число, и сразу приводить к нему, и уже его сохранять в кеш и соответственно проверять только его.


        1. andy_p Автор
          27.10.2017 15:53

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


      1. DistortNeo
        27.10.2017 15:35

        Канонический вид — автоморфизм с наименьшим индексом.
        И я предлагаю способ относительно быстрого его нахождения.


        1. andy_p Автор
          27.10.2017 16:04
          -1

          А что такое автоморфизм с наименьшим индексом ?


        1. andy_p Автор
          27.10.2017 16:30

          Если следовать предложенной методике, то необходимо иметь таблицу на 256 входов для XA8, затем таблицу на 256 входов для каждой из предыдущих таблиц для XB8, а затем таблицу на 2 в степени 48 входов для каждой предыдущей таблицы. То есть в итоге иметь таблицу размером 2 в степени 64 .


          1. DistortNeo
            27.10.2017 18:25

            Нет. Таблица для XA8 нужна, только чтобы сузить количество проверяемых автоморфизмов с 192 до примерно 8. Ну а для вычисления самих автоморфизмов достаточно использовать таблицы, как описано у автора.


  1. mayorovp
    27.10.2017 14:01

    Каким таким хитрым образом обходы в ширину и в глубину могут применяться для решения игр на графе?


    Однако, у кубика есть еще два внутренних автоморфизма. Один переставляет координаты полей в первой и второй паре в каждой линии,
    а второй оставляет первое и последнее поле на месте, а переставляет только координаты для второго и третьего поля.

    Не понял что это за хитрые автоморфизмы. Не могли бы вы пояснить их картинкой?


    1. andy_p Автор
      27.10.2017 15:58

      Вот описание из википедии:


      The group of automorphisms of the game contains 192 automorphisms. It is made up of combinations of the usual rotations and reflections that reorient or reflect the cube, plus two that scramble the order of cells on each line. If a line comprises cells A, B, C and D in that order, one of these exchanges inner cells for outer ones (such as B, A, D, C) for all lines of the cube, and the other exchanges cells of either the inner or the outer cells ( A, C, B, D or equivalently D, B, C, A) for all lines of the cube.


    1. andy_p Автор
      27.10.2017 16:04

      Под поиском в ширину я понимаю следующее:
      производятся итерации со все возрастающей глубиной — сначала 4, потом 6, потом 8 и т.д.
      На каждой такой итерации производится исследование всего дерева соответствующей глубины.


      1. mayorovp
        27.10.2017 16:21

        Как выглядит дерево на глубине 4 и как его можно "исследовать" раньше чем на глубине 6?


        1. andy_p Автор
          27.10.2017 16:26

          Просто ограничивать глубину просмотра — делать не более 4 ходов.


  1. noxius
    28.10.2017 09:20

    Решения, это линии, все возможные линии (76), с соответствующими координатами, запоминаем в массиве, они то и есть цель… любой ноль, либо соответственно крестик, перекрывает все соответствующие решения, и эти линии исключаются из последующих ходов… естественно приоритет, клетки с максимальным количеством вариантов (центр 2х2), то есть клетки имеющие координаты в максимально большем количестве линий…


    1. andy_p Автор
      28.10.2017 09:21

      Я так и делаю для увеличения производительноссти.