[Из песочницы] Выигрышная стратегия Гомоку – 35 ходов
При игре по стандартным правилам Гомоку для выигрыша черным требуется не более 35 ходов. В статье Вашему вниманию представлена полная выигрышная стратегия и соответствующий алгоритм игры.
Демонстрация полного решения — здесь — можно поиграть и найти самые длинные варианты. Программа всегда выигрывает и затрачивает на это не более 35 ходов. Исходные тексты приложения, само решение и примеры партий в конце статьи.
Не буду подробно останавливаться на правилах и тактике игры. Тема подробно обсуждалась на habr здесь, а также алгоритмы решений здесь и здесь.
Небольшое отступление
До эпохи смартфонов крестики/нолики «пять в ряд» (Гомоку, Рендзю) были одним из самых популярных убийц времени на уроках в школе. Считать комбинации было интереснее развития народного хозяйства северной Африки или классификации цветков клевера.
Осенью 1985 года девчонок из нашего 10«б» забрали с урока математики. Нас же, оставшихся шестерых ребят, с большой вероятностью ждало неформальное общение с учителем математики на отвлеченные темы. Учитель вошел в класс молча, раздал всем листочки в клеточку и начал писать на доске фамилии присутствующих. Мы приуныли, намечалась самостоятельная работа или блиц-опрос. Но список на доске превратился в турнирную таблицу и нам были объявлены правила чемпионата. Каждый с каждым серию из пяти партий. Приз победителю — пятерка в журнал. По результатам турнира мне повезло выиграть, но игра на этом не завершилась. Учитель пообещал поставить пятерки всем ребятам, если победитель выиграет у него подряд все пять партий серии. Право первого хода отдается победителю. Вопреки утверждению нашего учителя о том, что на таком условии при правильной игре можно выиграть и 10, и 100, и вообще любое количество партий подряд, победа для меня представлялась невероятным везением.
Спустя 9 лет в 1994 году о наличии доказательства этой гипотезы заявил доктор Льюис Виктор Аллис в статье Go-Moku and Threat-Space Search. Автор не публиковал полученную им выигрышную стратегию, позволяющую проверить доказательство. Однако в опубликованной им же в 1996 году книге Searching for Solutions in Games and Artificial Intelligenceбыло приведено общее описание алгоритмов. В заключении отдельно упоминается процедура проверки полноты выигрышной стратегии, которая опирается на корректность реализации алгоритма поиска «последовательности угроз» и анализе вариантов контригры соперника.
Приведенные в статье и книге примеры решений при «правильных ходах» соперников, являющиеся часть выигрышной стратегии, демонстрируют слабость используемых алгоритма.
Для примера на рисунке решение программы для стандартных правил Гомоку. Если в ответ на 10-й ход белых g9 черные отвечают j10 и затем j8, то партия завершается в 29 ходов вместо 45. Далее программа дважды «не заметила» комбинации «последовательности угроз» черных в 17 ходов после 16-го и после 26-го хода белых. И в завершении, если белые сделают 36й ход f12 вместо j12, то они продержатся как минимум до 49 го хода. Справедливости ради надо сказать, что в этом примере все ходы черных не оставляют белым ни одного шанса завершить партию в свою пользу.
На просторах интернета нашел несколько упоминаний об аналогичных работах поиска выигрышной стратегии. Не решенным остается вопрос оптимальности найденных решений. Какое минимальное количество ходов требуется черным для выигрыша?
Итак, имея немного свободного времени, современные вычислительные ресурсы и отдавая дань детским увлечениям через 33 года после памятного школьного чемпионата, поставил задачу поиска оптимальной стратегии выигрыша черными в Гомоку.
Оцифровываем позицию на доске
Запись партии довольно примитивна. На поле всего 225 клеток. Соответственно каждая клетка кодируется 1 байтом. Для записи партии из 35-и ходов требуется всего 35 байт. Но такая запись плохо пригодна для оценки позиции в силу двух причин: одинаковая позиция может получаться в разной последовательности ходов и не учитываются симметричные позиции.
Достижение цели игры — построение пяти камней в ряд — может быть осуществлено по одному из четырех направлений: по вертикали, по горизонтали и по двум диагоналям. Таким образом любую позицию мы можем представить в виде набора линий. Горизонтальные и вертикальные линии длиной по 15 клеток и диагональные линии длиной от 1 до 15 клеток. Каждый ход изменяет значение сразу 4-х линий по разным направлениям.
Задача оценки позиции — определить все значимые фигуры для каждой линии. Для простоты каждую клетку линии описываем 2-мя битами. Первый бит заполнен, когда установлен белый камень, второй бит — черный камень. Каждая линия содержит не более 15 клеток и кодируется в 32-х разрядное целое число. Таким образом поиск фигур на линии сводится к сравнению числового значения линии через скользящее окно с битовым шаблоном фигуры.
В приведенном на рисунке примере позиция описывается 26-ю линиями. Соответственно кодируется 104 байтами, в то время как обычная запись партии требует всего 17 байт.
Нетрудно догадаться, что все симметрии — повороты и зеркальные отображения — получаются простым изменением номера (перетасовкой) и направления линий. Для идентификации позиции и быстрого поиска в коллекциях на этом принципе реализована 32-х разрядная хэш-функция, дающая разные значения только для несимметричных позиций.
Использование симметрий существенно сокращает число рассматриваемых позиций. Например, количество вариантов второго хода сокращается с 224 до 35.
При поиске решений и комбинаций (об этом речь пойдет ниже) рассчитанные позиции составляют вершины многослойного графа. Вершины группируются в слои по числу заполненных клеток. Ходы составляют ребра графа, соединяющих вершины соседних слоев. Когда при поиске неудачные ходы отбрасываются — ребра удаляются и часть вершин теряет связность с основной ветвью. Поэтому после этапов расчета выполняется сборка мусора (или перестроение графа от вершины).
В процессе разработки были рассмотрены несколько алгоритмов кодирования, но описанный выше показал наибольшую скорость оценки позиции.
Оцениваем позицию
Важным фактором для оценки позиции является то, насколько значимые фигуры построили соперники.
Пятерка — если такая фигура найдена на доске, игра закончена. Для стандартных правил Гомоку выигрыш не дают никакие шестерки, семерки и т.д. Поэтому пятерка, как, впрочем, и все другие фигуры, требует отсутствия своих камней на соседних клетках в линии.
Открытая четверка — длина 6 клеток, средние четыре заняты камнями одного цвета, крайние обязательно пустые. Ну и как для пятерки свои камни отсутствуют на соседних клетках. Очень сильная фигура, означает выигрыш даже на чужом ходе.
Четверка — длина 5 клеток, одна (любая) из пяти клеток свободная. Дает выигрыш на своем ходу. Создает угрозу и вынуждает соперника сделать ход в свободную клетку, если у него нет своей четверки. Дает 5 баллов в рейтинг позиции при защите.
Открытая тройка — длина 6 или 7 клеток, крайние клетки обязательно свободны. Для 6 клеток три из четырех средних заняты камнями одного цвета, одна свободная. Для 7 клеток — три средних заняты камнями одного цвета. Фигура на своем ходе становится открытой четверкой, если у соперника нет четверки или открытой тройки. На чужом ходе создает угрозу и вынуждает соперника закрывать тройку или ставить в ответ свою четверку. 6-и клеточная тройка имеет 1 повышающий ход и 3 закрывающих. 7-и клеточная тройка имеет 2 повышающих хода и только 2 закрывающих. Дает от 2-х до 4-х баллов в рейтинг позиции.
Тройка, или закрытая тройка — длина 5 клеток, любые три из которых заняты камнями одного цвета. Тройка на своем ходе может быть превращена в четверку и используется при атаке и защите, создавая угрозу больше, чем открытая тройка соперника. Дает 1 балл в рейтинг позиции.
Отрытая (перспективная) двойка — длиной от 6 до 7 клеток. При атаке преобразуется в открытую тройку. Дает 1 или 2 балла в рейтинг позиции.
Вилка — одновременно две и более угроз, которые не могут быть закрыты одним ходом. Различаются вилки 3×3 (две открытых тройки), 3×4 (открытая тройка и четверка) и 4×4 (две открытых четверки. Вилки дают выигрыш, если у соперника нет большей угрозы — четверка или открытая тройка для вилки 3×3, или соперник не может последовательно закрыть вилку, создавая большие угрозы — последовательность четверок для вилки 3×3.
Комбинация — непрерывная последовательность угроз и защит от более значимых угроз соперника, приводящая к положительному результату для игрока. Комбинации бывают на атакующие (или выигрышные) и защитные.
Атакующая или выигрышная комбинация является успешной, если на любые защитные или атакующие ходы соперника были найдены ответные ходы, приводящие к выигрышу. Атакующая комбинация завершается установкой вилки, которую соперник не может закрыть.
Защитная комбинация, наоборот, успешна, когда у соперник перестает создавать угрозы, или превышен лимит ходов для расчета. Защитная комбинация состоит из ходов защиты или создания большей угрозы для соперника.
При оценке позиции выполняется поиск выигрышной комбинации. В случае успеха мы выиграли. В противном случае если нет угроз от соперника — состояние нейтральное. При наличии угроз от соперника, выполняем поиск защитной комбинации. В случае успеха состояние нейтрально, при неудаче — мы проиграли.
Так как количество вариантов атакующих и вынужденных ответных ходов довольно ограничено, то поиск комбинаций допустимо выполнять на достаточно большую глубину. При начальном построении оптимальной стратегии разрешенная глубина поиска комбинаций устанавливалась более 25 ходов. При пересчете решения для реализации алгоритма оценки позиций на javascript допустимая глубина поиска была снижена до 17 ходов.
При расчете оптимальной стратегии глубина поиска выигрышной комбинации сверху дополнительно ограничивалась целевым максимальным количеством ходов.
Ищем решение
Итак, мы оценили заданную позицию как нейтральную и выбираем какой будет следующий ход. Наше поведение в этом случае зависит от того, мы атакующая или защищающаяся сторона. Для атакующей стороны полным решением будет последовательность ходов, в котором для любого ответного хода соперника позиция оценивается как выигрышная (найдена выигрышная комбинация) или в решение содержит следующий собственный ход. Стоит заметить, что для расчета оптимальной стратегии атакующей стороной всегда являются черные, защищающейся — белые.
Атакующей стороне необходимо найти только один ход, приводящей к наиболее быстрой победе. В условиях недостатка ресурсов, атакующая сторона искусственно ограничивает количество вариантов для перебора, исследую в первую очередь ходы, приводящие к позиции с наибольшим рейтинговым баллом. После того, как найдены какие-либо решения, в направлении наиболее длинного из них атакующая сторона расширяет набор вариантов, исследуя менее рейтинговые позиции с целью добиться сокращения длины решения.
Защищающейся стороне достаточно найти один единственный ход, который не приводит к победе соперника в заданный лимит ходов. Для перебора могут быть использованы все свободные клетки.
Чтобы уменьшать перебираемое число ходов защиты используем алгоритм «пропуска хода». Пропускаем защитный ход и ищет выигрышную атакующую комбинацию. В случае успеха возможные ходы защиты могут быть ограничены ходами, влияющими успех найденной комбинации. В среднем на каждом шаге это позволяет уменьшить область поиска в 4–6 раз. Необходимо учитывать, что среди проигнорированных ходов могут оказаться более длинные ветви решения. Поэтому для поиска оптимальных решений алгоритм «пропуска хода» применяем только при первичном поиске.
Рассчитываем стратегию
Все компоненты готовы, мы ставим первый черный камень в центр поля, запускаем поиск решения и… На этом через несколько часов ресурсы моего ноутбука заканчиваются и приходится признать поражение «в сражении, но не в битве».
По правде сказать, у меня под рукой были вычислительные мощности с полутора сотней ядер Xeon и терабайтом свободной оперативной памяти. Но, помятую, что в середине девяностых у Аллиса было всего 10 SUN SPARCstation 2 на каждой по 128 Мб оперативной памяти, почувствовал угрызение совести за неспортивное поведение и принял решение ограничить объем оперативной памяти на java-машину до 1Гб и выделил под задачу всего 1 поток процессора. Это хоть как-то могло компенсировать мои GHz по сравнению с его MHz. Плюс дал себе обещание в конце работы перевести алгоритмы на javascript под браузер.
Итак, поиск стратегий нужно было начинать с решения дебютных этюдов. Подробное описание дебютов для игры Рендзю на русском языке можно найти в известных книгах Сагара «От дебюта к миттельшпилю» и Михаила Кожина «Зов камней» здесь. Книгам уже по 20 лет, но с тех пор подобной литературы издавалось мало. Более свежий сборник Дмитрия Епифанова «Тигр в клетке» 2015 года, к сожалению, не доступен в электронном виде.
Поиск оптимальных решений дебюта выполнялся по следующему алгоритму. На первом шаге выполнялся предварительный расчет без ограничения длины партии. Затем для наиболее длинных решений выполнялась оптимизация: замена найденных комбинаций на более короткие решения для финальных шагов и поиск более коротких ветвей решений для всех промежуточных ходов. Оптимизация выполнялась до достижения целевого лимита для всех ветвей решения. Затем целевой лимит уменьшался и выполнялась попытка провести оптимизацию до нового значения.
С приведенным на рисунке 3-м вертикальным дебютом проблем не возникло. Получился полный комплект решений. Наиболее сложные позиции после 4-го хода i8 и j10 в результате решались за 31 ход. Тогда был установлен целевой лимит в 35 ходов на партию.
Из диагональных для решения традиционно выбрал 7-й дебют. Наиболее сложная позиция возникает после 4-го хода g9. Решения допустимой длины были найдены для 6-х ходов g8 и g7.
А вот для этого варианта 6-го ходом на j9 мне никак не удавалось найти решения короче 33 ходов. Это была почти катастрофа. От отчаянья перепробовал решения для альтернативного 5-го хода, а также все другие виды диагональных дебютов. Дебюты решались до конца, но ничего короче 39 ходов на партию найти не получалось.
Вернувшись к исходному 7-му диагональному дебюту, переделал алгоритм формирования предложений для атакующих ходов. В результате ходы, приводящие к позициям с рейтинговым баллом из третьей десятки, неожиданно стали давать результат и снижать длину пути решения. Вариативность расчета при таком количестве становилась довольно большой. При глубине решения в 12 ходов находилось более 2 млн. позиций (без учета позиций при поиске комбинаций). Продолжение упиралось в выделенный на задачу 1Гб оперативной памяти. Таким образом, чтобы проверить решение до финальной вилки в некоторых случаях приходилось отдельно решать позиции от 18-го хода.
После того, как 7-й диагональный дебют был решен в заданный 35 ходов, можно было праздновать победу — борьба за центр выиграна. Впереди предстоял еще большой объем рутинной вычислительной работы, расчетов «неоптимальных» ходов белых для полноты стратегии. От общего объема оптимальной стратегии ответ на такие ходы в результате составил 80%. По счастью они автоматически решались полностью на предварительном расчете после 2-го хода, и весь этот объем был добавлен в оптимальную стратегию за пару дней.
Итак, решения для всех 2-х ходов найдено. Ставим первый черный камень в центр поля, запускаем поиск решения и даже не успеваем ощутить важность момента — начальная позиция решена за 35 ходов. Граф оптимальной выигрышной стратегии построен.
Проверяем себя
Следующий этап — проверка решения. Полностью выключаем интеллект у защищающейся стороны. После каждого хода черных белые ходят на любую свободную клетку доски. Полученная после хода белых позиция должна быть либо найдена графе решений, либо оценена как выигрышная за количество ходов, не превышающих наиболее длинную ветвь в исходной позиции. При оценке каждой позиции проверяем найденную выигрышную комбинацию по всем допустимых ходам белых до построения черными финальной фигуры — пять в ряд.
Проверка выполнялась несколько раз до полного завершения. Финальный безошибочный прогон в однопоточном режиме занял 14 часов. По ходу проверки были найдены и исправлены ошибки, возникшие в результате различий глубины поиска комбинаций, допущений пропуска хода, дублирования симметричных позиций.
Ответить на вопрос — действительно ли решение в 35 ходов является самым оптимальным. По моим исследованием для ряда наиболее длинных ветвей вертикального дебюта удается найти более оптимальные решения длиной в 33 хода. Но для диагонального после 6-го хода на j9 на поиск решения в 33 хода было потрачено много времени, вариативность для черных расширялась до 50 ходов на каждом шаге и безрезультатно. Строго доказать отсутствие решения в 33 хода не удается, тем не выделенное на проект время подошло к концу и было принято решение остановился на целевом лимите в 35 ходов.
Конвертируем из java в javascript
Публикация решения задачи требует наглядности. Чтобы использовать решение непосредственно в браузере потребовалось:
- Уменьшить глубину поиска комбинаций при оценке позиций до 17 ходов. Это привело к увеличению в 2–3 раза количества предрассчитанных ходов оптимальной стратегии.
- Преобразовать бинарный формат графа решений в JSON последовательности ходов. Такой формат более удобен в javascript и нагляден.
- Конвертировать классы java в модули javascript, кроме процедур поиска решений. Здесь же в web-интерфейсе заменить вызовы rest-сервисов локальными функциями.
Список классов приложения:
- Board — управления партией на доске, визуальный интерфейс
- Vertex — вершина графа решений, наследуется от позиции
- Edge — ребро графа решений, ход связывающий позиции
- Layout — позиция, содержит коллекцию линий
- Line — линия по заданному направлений, содержит коллекцию фигур
- Figure — фигура, определяет тип и начало фигуры на линии
- Pattern — шаблоны фигур для сравнения при поиске
Полное решение в формате JSON можно загрузить из файла gomoku.json.
Исходные тексты в репозитории на GitHub.
Для наглядности ниже приведу примеры наиболее длинных партий, полученные в демонстрации по клавише Next.
Диагональный дебют:
Вертикальный дебют:
