Игра гомоку (крестики-нолики, 5 в ряд)
Читая публикации на Хабре нашел пару статей об алгоритмах игры гомоку: эту и эту. В первой статье разобраны различные варианты решения задачи, но нет реализации в виде игры, во второй — игра есть, но компьютер «играет» слабовато. Я решил сделать свой вариант игры гомоку с блэкджеком достаточно сильной игрой компьютера. Публикация о том, что в итоге получилось. Для тех, кто любит сразу в бой — сама игра.
Для начала хочу определиться с основными моментами. Во-первых, существует множество разновидностей игры гомоку, я остановился на таком варианте: игровое поле 15×15, крестики ходят первыми, выигрывает тот, кто первый построит 5 в ряд. Во-вторых, игровой алгоритм расчета хода компьютером для простоты буду называть AI.Теория AI
shebeko в своей статье рассмотрел различные алгоритмы AI. Понятно, что при простом переборе всех вариантов ходов при углублении на несколько ходов количество требуемых расчетов зашкаливает. Поэтому надо реализовать какой-нибудь алгоритм по-умнее перебора в лоб.
Читая его статью я задумался над фразой: «Гомоку — это расходящаяся игра с полной информацией и внезапной смертью». Как пример другой игры с внезапной смертью приводятся шахматы. В моем понимании между шахматами и гомоку есть огромная разница: один ход в шахматах может кардинально изменить расклад сил. В шахматах фигуры могут ходить далеко и влиять на множество клеток. Ферзь или ладья потенциально могут атаковать любую клетку поля за 1 ход, т.е. за 1 ход можно поставить так, что любая конкретная клетка будет атакована (если свободны линии хода и атаки). В гомоку такого эффекта нет, одна фигура («камень» — крестик или нолик) может оказывать влияние только на 5 соседних с ней клеток в каждую сторону. Это первая предпосылка к моему алгоритму AI.
Второе важное допущение — в гомоку есть «эндшпили» — шаблоны которые ведут к победе. Помните риторический вопрос Тарантино: «Как долго человек считает до 600?» Аналогично, чтобы построить победную линию из 5 фигур, сначала надо построить линию из 4 (в общем случае: из 5 с 1 пропущенной с краю (линия из 4) или в середине), по другому — никак. Продолжая рассуждения получаем что для 4 необходима тройка, для тройки — двойка.
Я предположил, что такие шаблоны ходов есть нечто аналогичное расчету ходов в глубину, т.к. ходы локальны (имеют относительно малый радиус влияния в отличии от шахмат, например). Значит, можно просто перебрать все возможные варианты шаблонов для каждого потенциального хода. Это вторая половина алгоритма AI.
Осталось определить потенциальные ходы — те клетки поля в которые можно поставить фигуру. В общем случае, потенциальные ходы — это все пустые (не занятые) клетки доски. Учитывая что ходы — локальны, то все клетки нам не нужны, можно рассмотреть только ближайшие к уже стоящим на доске фигурам. Это первая половина алгоритма AI.
Алгоритм AI
1. Определение потенциальных ходов
Т.к. влияние фигур локально, то нет смысла определять потенциальные ходы каждый раз заново. Можно их просто накапливать.
— Особая ситуация: если в начале игры компьютер ходит первым — ход осуществляется в предустановленную клетку — центр доски (массив потенциальных ходов состоит из 1 клетки).
— В дальнейшем, после хода пользователя или AI, в массив потенциальных ходов добавляются поля отстоящие на 2 клетки от ячейки хода (соседние и соседние с соседними), а ячейка в которую совершен ход удаляется из этого массива.2. Расчет значения важности каждой клетки потенциальных ходов
Для каждой клетки из массива потенциальных ходов:
1) собираются 4 линии из 9 клеток в середине которых сама выбранная клетка (2 диагональных, вертикальная, горизонтальная)
2) каждая линия сравнивается со всеми имеющимися шаблонами. При вхождении клетки в шаблон ее значимость увеличивается на вес этого шаблона. Если в клетке есть возможность поставить «вилку», то ее вес будет в 2 раза больше (он будет просуммирован от весов шаблонов двух линий).3. Выбор клетки с максимальным значением важности
Расчет весов осуществятся отдельно для атаки (опираясь на фигуры AI) и защиты (сравнение линий из фигур соперника с теми же шаблонами), далее они суммируются. И клетка с максимальным весом — это лучший ход с точки зрения AI.Возможные улучшения AI
Первое улучшение — это добавление шаблонов, которые я пропустил :)
Второе — реализация алгоритма просчета хотя бы на пару ходов вперед с целью выявления потенциальных «вилок» и серии победных ходов в будущем. Это, кстати, основной способ как мне удается обыграть AI — создание серии ходов в которых AI вынужден закрывать 4, чтобы не проиграть (у него по сути нет альтернативы хода) и в результате этой серии ходов создается вилка из двух предфинальных линий (например, из двух четверок), так что зарыть их за один ход не возможно.Реализация игры
Игра написана на чистом JavaScript (без фреймворков типа jQuery). Графический интерфейс игры реализован на Canvas.Результат
Сама игра, исходный код на гитхабе (MIT).
Спасибо за внимание. Надеюсь, вам было также приятно читать и играть, как мне — реализовывать :)
P.S. Небольшая просьба, если будете легко выигрывать — прикрепите, пожалуйста, скриншот игры и ходы (из логов консоли) для анализа и улучшения алгоритма.
