Хабрахабр

[Из песочницы] Выигрышная стратегия Гомоку – 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. Приведенные в статье и книге примеры решений при «правильных ходах» соперников, являющиеся часть выигрышной стратегии, демонстрируют слабость используемых алгоритма.

Для примера на рисунке решение программы для стандартных правил Гомоку. И в завершении, если белые сделают 36й ход f12 вместо j12, то они продержатся как минимум до 49го хода. Далее программа дважды «не заметила» комбинации «последовательности угроз» черных в 17 ходов после 16-го и после 26-го хода белых. Справедливости ради надо сказать, что в этом примере все ходы черных не оставляют белым ни одного шанса завершить партию в свою пользу.

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

Итак, имея немного свободного времени, современные вычислительные ресурсы и отдавая дань детским увлечениям через 33 года после памятного школьного чемпионата, поставил задачу поиска оптимальной стратегии выигрыша черными в Гомоку.

Оцифровываем позицию на доске

Запись партии довольно примитивна. На поле всего 225 клеток. Соответственно каждая клетка кодируется 1 байтом. Для записи партии из 35-и ходов требуется всего 35 байт. Но такая запись плохо пригодна для оценки позиции в силу двух причин: одинаковая позиция может получаться в разной последовательности ходов и не учитываются симметричные позиции.

Таким образом любую позицию мы можем представить в виде набора линий. Достижение цели игры – построение пяти камней в ряд – может быть осуществлено по одному из четырех направлений: по вертикали, по горизонтали и по двум диагоналям. Каждый ход изменяет значение сразу 4-х линий по разным направлениям. Горизонтальные и вертикальные линии длиной по 15 клеток и диагональные линии длиной от 1 до 15 клеток.

Для простоты каждую клетку линии описываем 2-мя битами. Задача оценки позиции – определить все значимые фигуры для каждой линии. Каждая линия содержит не более 15 клеток и кодируется в 32-х разрядное целое число. Первый бит заполнен, когда установлен белый камень, второй бит – черный камень. Таким образом поиск фигур на линии сводится к сравнению числового значения линии через скользящее окно с битовым шаблоном фигуры.

Соответственно кодируется 104 байтами, в то время как обычная запись партии требует всего 17 байт.
Нетрудно догадаться, что все симметрии – повороты и зеркальные отображения – получаются простым изменением номера (перетасовкой) и направления линий. В приведенном на рисунке примере позиция описывается 26-ю линиями. Для идентификации позиции и быстрого поиска в коллекциях на этом принципе реализована 32-х разрядная хэш-функция, дающая разные значения только для несимметричных позиций.

Например, количество вариантов второго хода сокращается с 224 до 35. Использование симметрий существенно сокращает число рассматриваемых позиций.

Вершины группируются в слои по числу заполненных клеток. При поиске решений и комбинаций (об этом речь пойдет ниже) рассчитанные позиции составляют вершины многослойного графа. Когда при поиске неудачные ходы отбрасываются – ребра удаляются и часть вершин теряет связность с основной ветвью. Ходы составляют ребра графа, соединяющих вершины соседних слоев. Поэтому после этапов расчета выполняется сборка мусора (или перестроение графа от вершины).

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

Оцениваем позицию

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

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

Ну и как для пятерки свои камни отсутствуют на соседних клетках. Открытая четверка – длина 6 клеток, средние четыре заняты камнями одного цвета, крайние обязательно пустые. Очень сильная фигура, означает выигрыш даже на чужом ходе.

Дает выигрыш на своем ходу. Четверка – длина 5 клеток, одна (любая) из пяти клеток свободная. Дает 5 баллов в рейтинг позиции при защите. Создает угрозу и вынуждает соперника сделать ход в свободную клетку, если у него нет своей четверки.

Для 6 клеток три из четырех средних заняты камнями одного цвета, одна свободная. Открытая тройка – длина 6 или 7 клеток, крайние клетки обязательно свободны. Фигура на своем ходе становится открытой четверкой, если у соперника нет четверки или открытой тройки. Для 7 клеток – три средних заняты камнями одного цвета. 6-и клеточная тройка имеет 1 повышающий ход и 3 закрывающих. На чужом ходе создает угрозу и вынуждает соперника закрывать тройку или ставить в ответ свою четверку. Дает от 2-х до 4-х баллов в рейтинг позиции. 7-и клеточная тройка имеет 2 повышающих хода и только 2 закрывающих.

Тройка на своем ходе может быть превращена в четверку и используется при атаке и защите, создавая угрозу больше, чем открытая тройка соперника. Тройка, или закрытая тройка – длина 5 клеток, любые три из которых заняты камнями одного цвета. Дает 1 балл в рейтинг позиции.

При атаке преобразуется в открытую тройку. Отрытая (перспективная) двойка – длиной от 6 до 7 клеток. Дает 1 или 2 балла в рейтинг позиции.

Различаются вилки 3x3 (две открытых тройки), 3x4 (открытая тройка и четверка) и 4x4 (две открытых четверки. Вилка – одновременно две и более угроз, которые не могут быть закрыты одним ходом. Вилки дают выигрыш, если у соперника нет большей угрозы – четверка или открытая тройка для вилки 3x3, или соперник не может последовательно закрыть вилку, создавая большие угрозы – последовательность четверок для вилки 3x3.

Комбинации бывают на атакующие (или выигрышные) и защитные. Комбинация – непрерывная последовательность угроз и защит от более значимых угроз соперника, приводящая к положительному результату для игрока.

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

Защитная комбинация состоит из ходов защиты или создания большей угрозы для соперника. Защитная комбинация, наоборот, успешна, когда у соперник перестает создавать угрозы, или превышен лимит ходов для расчета.

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

При начальном построении оптимальной стратегии разрешенная глубина поиска комбинаций устанавливалась более 25 ходов. Так как количество вариантов атакующих и вынужденных ответных ходов довольно ограничено, то поиск комбинаций допустимо выполнять на достаточно большую глубину. При пересчете решения для реализации алгоритма оценки позиций на javascript допустимая глубина поиска была снижена до 17 ходов.
При расчете оптимальной стратегии глубина поиска выигрышной комбинации сверху дополнительно ограничивалась целевым максимальным количеством ходов.

Ищем решение

Итак, мы оценили заданную позицию как нейтральную и выбираем какой будет следующий ход. Наше поведение в этом случае зависит от того, мы атакующая или защищающаяся сторона. Для атакующей стороны полным решением будет последовательность ходов, в котором для любого ответного хода соперника позиция оценивается как выигрышная (найдена выигрышная комбинация) или в решение содержит следующий собственный ход. Стоит заметить, что для расчета оптимальной стратегии атакующей стороной всегда являются черные, защищающейся – белые.

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

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

Рассчитываем стратегию

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

Но, помятую, что в середине девяностых у Аллиса было всего 10 SUN SPARCstation 2 на каждой по 128 Мб оперативной памяти, почувствовал угрызение совести за неспортивное поведение и принял решение ограничить объем оперативной памяти на java-машину до 1Гб и выделил под задачу всего 1 поток процессора. По правде сказать, у меня под рукой были вычислительные мощности с полутора сотней ядер Xeon и терабайтом свободной оперативной памяти. Плюс дал себе обещание в конце работы перевести алгоритмы на javascript под браузер. Это хоть как-то могло компенсировать мои GHz по сравнению с его MHz.

Подробное описание дебютов для игры Рендзю на русском языке можно найти в известных книгах Сагара «От дебюта к миттельшпилю» и Михаила Кожина «Зов камней» здесь. Итак, поиск стратегий нужно было начинать с решения дебютных этюдов. Более свежий сборник Дмитрия Епифанова «Тигр в клетке» 2015 года, к сожалению, не доступен в электронном виде. Книгам уже по 20 лет, но с тех пор подобной литературы издавалось мало.

На первом шаге выполнялся предварительный расчет без ограничения длины партии. Поиск оптимальных решений дебюта выполнялся по следующему алгоритму. Оптимизация выполнялась до достижения целевого лимита для всех ветвей решения. Затем для наиболее длинных решений выполнялась оптимизация: замена найденных комбинаций на более короткие решения для финальных шагов и поиск более коротких ветвей решений для всех промежуточных ходов. Затем целевой лимит уменьшался и выполнялась попытка провести оптимизацию до нового значения.

Получился полный комплект решений. С приведенным на рисунке 3-м вертикальным дебютом проблем не возникло. Тогда был установлен целевой лимит в 35 ходов на партию. Наиболее сложные позиции после 4-го хода i8 и j10 в результате решались за 31 ход.

Наиболее сложная позиция возникает после 4-го хода g9. Из диагональных для решения традиционно выбрал 7-й дебют. Решения допустимой длины были найдены для 6-х ходов g8 и g7.

Это была почти катастрофа. А вот для этого варианта 6-го ходом на j9 мне никак не удавалось найти решения короче 33 ходов. Дебюты решались до конца, но ничего короче 39 ходов на партию найти не получалось. От отчаянья перепробовал решения для альтернативного 5-го хода, а также все другие виды диагональных дебютов.

В результате ходы, приводящие к позициям с рейтинговым баллом из третьей десятки, неожиданно стали давать результат и снижать длину пути решения. Вернувшись к исходному 7-му диагональному дебюту, переделал алгоритм формирования предложений для атакующих ходов. При глубине решения в 12 ходов находилось более 2 млн. Вариативность расчета при таком количестве становилась довольно большой. Продолжение упиралось в выделенный на задачу 1Гб оперативной памяти. позиций (без учета позиций при поиске комбинаций). Таким образом, чтобы проверить решение до финальной вилки в некоторых случаях приходилось отдельно решать позиции от 18-го хода.

Впереди предстоял еще большой объем рутинной вычислительной работы, расчетов «неоптимальных» ходов белых для полноты стратегии. После того, как 7-й диагональный дебют был решен в заданный 35 ходов, можно было праздновать победу – борьба за центр выиграна. По счастью они автоматически решались полностью на предварительном расчете после 2-го хода, и весь этот объем был добавлен в оптимальную стратегию за пару дней. От общего объема оптимальной стратегии ответ на такие ходы в результате составил 80%.

Ставим первый черный камень в центр поля, запускаем поиск решения и даже не успеваем ощутить важность момента – начальная позиция решена за 35 ходов. Итак, решения для всех 2-х ходов найдено. Граф оптимальной выигрышной стратегии построен.

Проверяем себя

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

Финальный безошибочный прогон в однопоточном режиме занял 14 часов. Проверка выполнялась несколько раз до полного завершения. По ходу проверки были найдены и исправлены ошибки, возникшие в результате различий глубины поиска комбинаций, допущений пропуска хода, дублирования симметричных позиций.

По моим исследованием для ряда наиболее длинных ветвей вертикального дебюта удается найти более оптимальные решения длиной в 33 хода. Ответить на вопрос – действительно ли решение в 35 ходов является самым оптимальным. Строго доказать отсутствие решения в 33 хода не удается, тем не выделенное на проект время подошло к концу и было принято решение остановился на целевом лимите в 35 ходов. Но для диагонального после 6-го хода на j9 на поиск решения в 33 хода было потрачено много времени, вариативность для черных расширялась до 50 ходов на каждом шаге и безрезультатно.

Конвертируем из java в javascript

Публикация решения задачи требует наглядности. Чтобы использовать решение непосредственно в браузере потребовалось:

  • Уменьшить глубину поиска комбинаций при оценке позиций до 17 ходов. Это привело к увеличению в 2-3 раза количества предрассчитанных ходов оптимальной стратегии.
  • Преобразовать бинарный формат графа решений в JSON последовательности ходов. Такой формат более удобен в javascript и нагляден.
  • Конвертировать классы java в модули javascript, кроме процедур поиска решений. Здесь же в web-интерфейсе заменить вызовы rest-сервисов локальными функциями.

Список классов приложения:

  • Board – управления партией на доске, визуальный интерфейс
  • Vertex – вершина графа решений, наследуется от позиции
  • Edge – ребро графа решений, ход связывающий позиции
  • Layout – позиция, содержит коллекцию линий
  • Line – линия по заданному направлений, содержит коллекцию фигур
  • Figure – фигура, определяет тип и начало фигуры на линии
  • Pattern – шаблоны фигур для сравнения при поиске

Полное решение в формате JSON можно загрузить из файла gomoku.json.

Исходные тексты в репозитории на GitHub.

Для наглядности ниже приведу примеры наиболее длинных партий, полученные в демонстрации по клавише Next.

Диагональный дебют:

Вертикальный дебют:

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть