Демонстрация полного решения – здесь – можно поиграть и найти самые длинные варианты. Программа всегда выигрывает и затрачивает на это не более 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 балла в рейтинг позиции.
Вилка – одновременно две и более угроз, которые не могут быть закрыты одним ходом. Различаются вилки 3x3 (две открытых тройки), 3x4 (открытая тройка и четверка) и 4x4 (две открытых четверки. Вилки дают выигрыш, если у соперника нет большей угрозы – четверка или открытая тройка для вилки 3x3, или соперник не может последовательно закрыть вилку, создавая большие угрозы – последовательность четверок для вилки 3x3.
Комбинация – непрерывная последовательность угроз и защит от более значимых угроз соперника, приводящая к положительному результату для игрока. Комбинации бывают на атакующие (или выигрышные) и защитные.
Атакующая или выигрышная комбинация является успешной, если на любые защитные или атакующие ходы соперника были найдены ответные ходы, приводящие к выигрышу. Атакующая комбинация завершается установкой вилки, которую соперник не может закрыть.
Защитная комбинация, наоборот, успешна, когда у соперник перестает создавать угрозы, или превышен лимит ходов для расчета. Защитная комбинация состоит из ходов защиты или создания большей угрозы для соперника.
При оценке позиции выполняется поиск выигрышной комбинации. В случае успеха мы выиграли. В противном случае если нет угроз от соперника – состояние нейтральное. При наличии угроз от соперника, выполняем поиск защитной комбинации. В случае успеха состояние нейтрально, при неудаче – мы проиграли.
Так как количество вариантов атакующих и вынужденных ответных ходов довольно ограничено, то поиск комбинаций допустимо выполнять на достаточно большую глубину. При начальном построении оптимальной стратегии разрешенная глубина поиска комбинаций устанавливалась более 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.
Диагональный дебют:
Вертикальный дебют:
Комментарии (25)
GlukKazan
22.01.2019 13:28+1На счёт Рендзю и её фолов не думали?
MaximRud Автор
22.01.2019 17:28Думал, возможно вернусь к теме, если будет свободное время.
В 2001 году такую работу без учета регламентных правил проделали венгры Янус Вагнер и Истван Вираг. Прочитать можно здесь. Как ни странно оценка позиции и поиск комбинаций в Рендзю на компьютере выполняется быстрее, чем в Гомоку из-за меньшего числа допустимых вилок со стороны черных.
FatalER
22.01.2019 17:12Победил игру, но она мне почему то не засчитала победу, внезапно.
MaximRud Автор
22.01.2019 17:14С отключенным Auto move и если делать ходы за черных такое возможно. Или были нарушены правила, например, шесть в ряд. Не исключаю также ошибок в демонстрационной javascript версии. Поэтому, если получиться в автоматическом режиме, пришлите, скриншот, пожалуйста.
FatalER
23.01.2019 08:23+1Да. Там и правда было 6 в ряд. Но насколько я знаю правила у белых может быть 6 и более в ряд, а у черных только 5, при чем они не могут делать вилки 3х3, 4х4. Иначе баланс игры ломается, т.к. у черных преимущество первого хода.
OwenE
23.01.2019 10:08Даже и эти правила (это уже рэндзю, не гомоку) не обеспечивают равенства, начинающий все равно выигрывает, но несколько сложнее.
В современном рэндзю, да и гомоку, для уравнивания шансов используются дебютные регламенты — специальные процедуры совершения первых пяти ходов, в числе прочего содержащие момент (-ы), когда один из игроков выбирает цвет, которым будет играть. То есть пирог: один режет пополам, другой выбирает себе половину.
MaximRud Автор
23.01.2019 10:30По стандартным правилам Гомоку построение длинного ряда не запрещено, в отличии от Рендзю, но победой не считается ни за белых, ни за черных. См., например, здесь wikipedia. Длинный ряд разрешен в так называемом «свободном» Гомоку на бесконечном поле. В некоторых разновидностях Гомоку для черных были запрещены вилки 3x3. Запрет вилок 4x4 есть только в Рендзю. Впрочем, эти ограничения не дают преимущества, а только создают сложности для играющего человека, но не для компьютера. Выше есть ссылка на подобную работу по Рендзю.
OwenE
23.01.2019 12:17+1Во-первых, игра все же называется рэндзю, а не «Рендзю». Можно, опять же, проверить в Вики.
Во-вторых, запреты (или, как их принято называть, фолы) изрядное преимущество белым дают, но этой прибавки недостаточно, чтобы скомпенсировать преимущество первого хода, поэтому для уравнивания шансов, как я уже написал, используют другой инструмент, дебютный регламент. Причем как в рэндзю, так и в гомоку. И, кстати, это преимущество должно выражаться и в том, что оптимальная игра должна приводить черных к победе в рэндзю без дебютного регламента за большее число ходов, чем в гомоку. Я где-то видел оценку не то в 45, не то в 49 ходов. Кажется, не у Иштвана Вирага.
Далее, про разновидности. Сейчас и по гомоку, и по рэндзю регулярно проходят серьезные соревнования (от фестивальных турниров до чемпионатов мира), рэндзю вообще есть во Всероссийском реестре видов спорта, так что говоря о разновидностях, надо понимать, что и в рэндзю, и в гомоку есть общепринятый набор правил и малораспространенные разновидности. Говоря про спортивное гомоку, мы подразумеваем, что длинный ряд — это просто ход, не выигрывает и не проигрывает; а когда мы говорим про рэндзю, мы имеем в виду, что длинный ряд, поставленный любой из сторон, приводит к победе белых.
Но самое интересное — это про отсутствие сложностей для компьютера. Тут такое дело, что в гомоку машина (в частности, программа Yixin, она бесплатная) играет уже на голову лучше человека, а в рэндзю тот же Исинь пока не может громить топ-игроков, как показывают матчи. Это странно, если тезис про отсутствие сложностей верен. Мне кажется, он имеет место только для вашей узкой задачи — доказательство выигрыша черных при игре без дебютного регламента.MaximRud Автор
23.01.2019 21:37Не встречал оценок длительности оптимальных игр для Рэндзю. Если найдете, пришлите, пожалуйста. Диагональные дебюты в Гомоку рассчитал все, некоторые даже с альтернативными ходами. Решаются быстрее 45 ходов.
В отношении уверенности — поиск комбинаций, как правило, дает сразу несколько альтернатив для окончаний в зависимости от порядка применения угроз. При глубине поиска более 15 ходов практически всегда встречаются альтернативы с вилкой 4x3. По моему опыту такие вилки находятся быстрее, если при альтернативном выборе идем по пути открытых троек, а не четверок.
В отношении Yixin, думаю, объясняется тем, что ее автор Кай Сун по национальности китаец. Смотрел интервью, в котором он рассказывает о своем вкладе в развитие именно Гомоку. Попробуйте китайцу сказать, что ушу это каратэ, или ханьфу это кимоно, или гомоку это рэндзю. :)OwenE
23.01.2019 22:24Не очень понятно, что такое «все диагональные дебюты в гомоку». В гомоку (гомоку swap2, в которое все соревнования) нет ограничений на расположение камней, первый не обязательно в центр, второй не обязательно рядом и т.д. Если вы имеете в виду все дебюты рэндзю, то есть вопросы. Вы доказали выигрыш (в стандартное гомоку) в первом диагональном дебюте, это H8 I9 J10? В 13д, это H8 I9 F6? И там, и там, насколько мне известно, чистый выигрыш черных не доказан (и во втором, честно говоря, сомнителен — я бы скорее выигрыш белых доказывал).
Если вы имеете в виду более широкий спектр дебютов (так называемое «свободное рэндзю» или «ЦЗК»), то что вы скажете про дебют H8 I9 K5?
Вообще, было бы интересно увидеть полный список закрытых трехходовок, мало ли, вдруг вы уже внесли вклад в формирующуюся дебютную теорию гомоку =)
Про то, что объясняется национальностью автора, мысль не понял, вы не могли бы ее развернуть? Китайцы не так уж и давно на топ-уровне играют в рэндзю и в гомоку, тут хранителями традиций являются японцы. Которые, впрочем, гомоку в общем и целом пренебрегают — и я хорошо их понимаю.MaximRud Автор
24.01.2019 00:25Нет-нет :) Под словом «все» имел ввиду те дебюты, которые дают черным преимущество. Кроме 7-Д считал 3-Д, 6-Д, 9-Д и 11-Д. Короче все, без отрыва 3-го хода от черного камня. Здесь оговорюсь, считал ходы и наиболее длинные продолжения, рекомендованные в сборниках. Для меня было важно было определить, что нет решения более короткого, чем в 7-Д.
В отношении спорного национального происхождения игры. Оба слова Гомоку и Рэндзю японские. Исконно это была одна и та же игра и в Японии, и в Китае. Современные дебютные правила и фолы в Рэндзю придуманы только в XX веке японцами. Распространение в мире они получили где-то в конце 80-х. Поэтому, например, в детские годы, называя игру Рэндзю, играл по правилам близким к Гомоку без фолов. Все что касается традиций Рэндзю — сильное преувеличение. На самом деле игра по современным правилам Рэндзю очень молода.
Можно говорить об излишней сложности правил и неоправданных ограничениях в игре. Кай Сун, в частности, считает что для выравнивания шансов игроков в Гомоку достаточно использовать правило swap после первого хода черных.OwenE
24.01.2019 02:19+1Помню, некоторое время назад я заинтересовался вопросом, каков минимальный размер доски, где черные все еще гарантированно выигрывают, и нашел, что на доске 13х13 выигрыш еще есть, а на 11х11 уже, видимо, нет. К чему я это? К тому, что на доске 13х13 выигрывает именно 9д, а не 7д, так что ваш поиск целесообразен. Но за черных очень сильны еще и некоторые коневые дебюты, в первую очередь 4д. Для вашей задачи, вероятно, 4д даст ту же оценку, там, полагаю, будут просто общие варианты с 7д, в 2д выигрыши будут длиннее (но зато и путей к победе больше, а сами пути проше и естественнее), но вот 8д какой-нибудь или 12д могут оказаться и быстрее, проверьте.
С происхождением игры споров нет, возникла в Китае несколько тысяч лет назад, попала в Японию, которой обязана своим развитием. Фолы появились на рубеже 19-20 веков, уже в конце 19 века в матчах сильнейших считался неприличным выигрыш вилкой 3-3, дебютные регламенты в рэндзю появились в 20 веке, а дебютный регламент гомоку, swap2, уже в 21 веке (хотя его аналог для рэндзю предлагался эстонцами и в конце 20-го).
То, что вы играли в гомоку, называя это рэндзю, это заслуга вполне конкретного человека, В. Сапронова, написавшего цикл статей в «Науке и жизни» и предложившего фактически свой набор правил — рэндзю с центральным запрещенным квадратом.
Что касается возраста игры, то тут вы радикально неправы. Последние изменения правил пинг-понга датируются 2018 годом, в 21 веке пару раз меняли параметры мячика — и что, все, новая игра? Конечно же, нет.
Наконец, о выравнивании шансов. Да, так можно, но есть одна простая проблема: остается буквально два-три разумных дебюта (с точностью до поворотов и отражений). Это то, через что проходил дебютный регламент ЦЗК, когда по нему стали всерьез играть заочно: пришлось расширять список запрещенных дебютов, так как стали закрываться заквадратные дебюты, то там, то сям находили выигрыш черных. Тут будет та же фигня: из-за крайней скудности выбора первого хода довольно быстро дебютная теория разовьется так, что будет гарантировать знающему человеку непоражение (и значительный перевес в случае схода оппонента с диаграмм). Поэтому этот регламент не приживется, а соревнования проводятся по регламенту swap2.
MaximRud Автор
22.01.2019 19:07Спасибо! Действительно ошибка была в конвертации бинарного графа решений в JSON формат. Перепутал местами аргументы при сложении симметрий позиций. Двойная трансформация симметрий в решениях возникает редко, не удалось сразу обнаружить. Теперь все в порядке. Перед игрой потребуется очистить кэш браузера (Ctrl+Shift+Del).
OwenE
23.01.2019 12:56+2Не, я положительно не могу остановиться с комментариями, этот пост выглядит лучшим хабрапостом про крестики-нолики so far =)
Сначала еще немножко придирок.
Про книжки.
Книжка Кожина и Носовского (да, там два автора, и вклад второго, Александра Носовского, часто недооценивают — а он, похоже, является основным автором) называется не «Зов камней», а «Звон камней», вот.
А «Тигр в клетке» хоть и недоступен в электронном виде, но вполне приобретаем в бумажном, особенно легко это провернуть, если вы находитесь в Москве или в Санкт-Петербурге.
Но «Тигр» решает уже другие задачи. У Сагары в целом подход «найти результативную атаку черных в каждом дебюте» — это то, что близко вам; а «Звон» и «Тигр» дают представление о возможностях обоих цветов по конкретным дебютным регламентам («Звон камней» для регламента RIF, «Тигр в клетке» — для Ямагути), а именно указание спектра играбельных позиций (т.е. позиций, где нет доказываемого выигрыша одного из цветов и подразумевается отсутствие доказуемого выигрыша), а также основные диаграммы про то, как реализовывать перевес там, где эта реализация существует и доказана.
И теперь про интересное.
Во-первых, gomocup.
Смотрите, сейчас есть довольно большое число разного рода движков для игры в игры семейства пять-в-ряд. Среди движков проводится ежегодное состязание, так называемый gomocup. Понятно, что то, что вы написали, к самостоятельной игре из равных позиций пока что неспособно (и уже давным-давно есть движок, расставляющий выигрыш черных в гомоку без дебютного регламента, называется Terminator); но, может быть, вам будет интересно написать что-то, что будет способно?
Во-вторых, решалка.
Программ, которые призваны решать задачи в играх пять-в-ряд, т.е. находить и доказывать выигрыш там, где он есть, тоже некоторое количество имеется (упомянутый уже Yixin, есть еще RenjuSolver из сильных решалок). Может быть, у вас получится наваять программу, которая делает это лучше существующих? Пока киборг из человека и компьютера значительно сильнее чистого компьютера (и железо не решает исход этого противостояния), существует заочная игра, в первую очередь рэндзю. И заочникам такого рода инструменты очень нужны.
В общем, можно от прикольного проекта, позволившего вам вспомнить молодость, перейти к чему-то, что будет полезно людям. Что скажете?MaximRud Автор
23.01.2019 20:45Спасибо за уточнения.
По gomocup условия читал, смотрел код Yixin. Здесь действительно разные задачи. Для турнира важным ограничениям является время расчета, решение может быть приближенным, например, найден ход ведущий к наиболее рейтинговой позиции.
Моя программа, имею ввиду Java-версию, предназначена для нахождения полного решения позиции за заданное количество ходов. Ограничение по времени здесь не так важно. Здесь используется послойное решение — см. метод Vertex.compute (на Java). В программе есть альтернативный метод решения, основанный на алгоритме pn2-поиска, — см. метод Apex.compute (в интерфейсе можно заменить вызываемый метод). Этот алгоритм позволяет сократить число оцениваемых позиций, соответственно время поиска, для нахождения решения без ограничения числа ходов. Однако, для нахождения оптимальных решений он менее пригоден, так как склонен рассчитывать в первую очередь маловариантные позиции, которые редко приводят к быстрой победе. По моему опыту ход со скрытой угрозой позволяет победить быстрее, чем прямая атака.
Опубликованных полных решений (дерева ходов) не нашел. В своей задаче занимался не столько проверкой доказательства, сколько поиском оптимального решения. Важный результат — 35 ходов.
Про Terminator — хорошая программа, но довольно старая. По моей информации там не было ни полного решения, ни оптимального. Обсуждение этой темы см. здесь и пример выигрыша за белых здесь.OwenE
23.01.2019 22:30Ну, основная мысль в том, что задача, которую решили вы, занятная, но тупиковая. А можно было бы дать программе будущее — либо в формате находилки выигрышей, либо в формате игрового движка. Собственно, вопрос к вам: интересно ли вам развивать детище?
Терминатор — да, видимо, просто дебютная библиотека слабовата, потому решение неполное. Мне казалось, он был лучше.
molnij
23.01.2019 13:06В разделе описания позиций не увидел ограничений на шестерки (т.е. вида х0хххх0х для открытой четверки). Не берусь судить, насколько это реально что-то меняет в реальной игре, но с точки зрения строгости вопрос вызывает
MaximRud Автор
23.01.2019 21:00Это очень важно. Однако в описании фигур, в частности для открытой четверки, написано, что свои камни должны отсутствовать на соседних клетках. Возможно Вы были не совсем внимательны.
В реальной игре это меняет правила. Если не проверять наличие своих камней на соседних клетках, то построение длинного ряда считаем выигрышем.
В коде при поиске фигур по шаблонам это обязательно проверяется:
// Поиск выбранных фигур в строке Line.prototype.findFigures = function (figures, type) { ... // По черным камням if ((probe & 2) > 0) { ... // Нет черного каменя слева && (offset > 0 ? (stroke >> ((offset - 1) << 1)) & 2 : 0) === 0 // Нет черного камня справа && ((stroke >> ((offset + pattern.length) << 1)) & 2) === 0 ... } // По белым камням if ((probe & 1) > 0) { ... // Нет белого каменя слева && (offset > 0 ? (stroke >> ((offset - 1) << 1)) & 1 : 0) === 0 // Нет белого камня справа && ((stroke >> ((offset + pattern.length) << 1)) & 1) === 0 ... }
OwenE
24.01.2019 11:26> Но для диагонального после 6-го хода на j9 на поиск решения в 33 хода было потрачено много времени
Если это единственная шестиходовка, в которую упирается ваше решение, то давайте попробуем улучшить. Насколько мне известно, 9-i6 выигрывает заметно проще, чем 9-i8, как минимум в рэндзю. Проще не значит быстрее, а рэндзю и гомоку — разные игры, но, имхо, должен помочь и вам. Вы смотрели этот 9 ход? Нужны ли вам 11 ходы на какие-то наиболее упорные защиты?
MaximRud Автор
24.01.2019 22:11Да. Там проблема только с одним 10-м ходом на k8 — он дает самые длинны продолжения.
OwenE
25.01.2019 00:35Нет, у меня не получается выиграть там быстрее, чем к 35 ходу — только в 37 ходов придумал. Там несколько форсажей есть, можно по-разному выигрывать, но все атаки длиннее, чем хочется. Даже не ожидал, насколько это на самом деле жесткое условие — пятерка 35 ходом…
amarao
Без нейронных сетей? Внезапно, поздравляю.
MaximRud Автор
Спасибо. Нейронные сети обычно используются для аппроксимации решения. Например, AlphaGo использует метод Монте-Карло чтобы избежать полного перебора. В этой задаче требовалось найти полное решение.
dim2r
Для нейронок потребовалось много вычислительных ресурсов.
Я как-то писал нейронку, которая играет в крестики-нолики. В 3х3 учится за несколько минут против алгоритма. Но как только добавляешь размерность 5х5, то время становится очень большим из-за степенных и факториальных зависимостей. Даже ждать не стал, когда она найдет очевидную и выигрышную стратегию.