09.03.2016 11:08
Beif 17 9800 Источник
image
Читая публикации на Хабре нашел пару статей об алгоритмах игры гомоку: эту и эту. В первой статье разобраны различные варианты решения задачи, но нет реализации в виде игры, во второй — игра есть, но компьютер «играет» слабовато. Я решил сделать свой вариант игры гомоку с блэкджеком достаточно сильной игрой компьютера. Публикация о том, что в итоге получилось. Для тех, кто любит сразу в бой — сама игра.

Для начала хочу определиться с основными моментами. Во-первых, существует множество разновидностей игры гомоку, я остановился на таком варианте: игровое поле 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. Небольшая просьба, если будете легко выигрывать — прикрепите, пожалуйста, скриншот игры и ходы (из логов консоли) для анализа и улучшения алгоритма.

Update 1

1. На 10% увеличил значимость весов для атаки. Теперь атака для AI предпочтительнее защиты при прочих равных. Например, если 4ка у AI и у пользователя, то AI предпочтет выиграть.

2. Изменил значения весов по шаблонам. При более четкой балансировки весов можно добиться лучшей игры AI.
Значения весов у шаблонов сейчас такие:
99999 — xxxxx — пять в ряд (финальная выигрышная линия)
7000 — _xxxx_ — открытая четверка
4000 — _xxxx — полузакрытая четверка (две таких четверки предпочтительнее одной открытой, возможно «интереснее игра» будет)
2000 — _x_xxx, _xx_xx, _xxx_x — полузакрытая четверка с брешью (2 таких четверки равны одной открытой четверке и «предпочтительнее» открытой тройки; но если только 1 такая четверка, то открытая тройка предпочтительнее)
3000 — _xxx_ — открытая тройка
1500 — _xxx — полузакрытая тройка
800 — _xx_x, _x_xx — полузакрытая тройка с брешью
200 — _xx_ открытая двойка
Также небольшие веса (от 1 до 20-30) есть вокруг всех ходов, для создания «небольшой случайности хода».

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


  1. OlegUV
    09.03.2016 15:19
    #8799045

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


  1. stasmus
    09.03.2016 16:04
    #8799137

    раз
    New Game! X — user, O — AI AppModel.js:94:13
    1: 7, 7 AppModel.js:168:9
    2: 8, 6 AppModel.js:168:9
    3: 7, 6 AppModel.js:168:9
    4: 7, 5 AppModel.js:168:9
    5: 9, 7 AppModel.js:168:9
    6: 8, 7 AppModel.js:168:9
    7: 8, 8 AppModel.js:168:9
    8: 7, 9 AppModel.js:168:9
    9: 9, 9 AppModel.js:168:9
    10: 6, 6 AppModel.js:168:9
    11: 9, 8 AppModel.js:168:9
    12: 9, 6 AppModel.js:168:9
    13: 10, 8 AppModel.js:168:9
    14: 7, 8 AppModel.js:168:9
    15: 10, 5 AppModel.js:168:9
    16: 10, 6 AppModel.js:168:9
    17: 11, 7 AppModel.js:168:9
    18: 12, 6 AppModel.js:168:9
    19: 11, 6 AppModel.js:168:9
    20: 11, 8 AppModel.js:168:9
    21: 10, 7 AppModel.js:168:9
    22: 8, 9 AppModel.js:168:9
    23: 12, 7 AppModel.js:168:9
    24: 13, 7 AppModel.js:168:9
    25: 13, 8 AppModel.js:168:9
    26: 9, 4 AppModel.js:168:9
    27: 14, 9 AppModel.js:168:9


    1. Joshua
      09.03.2016 16:29
      #8799195

      Игра за Х доказана — форсированная победа.
      Играйте за 0.

      38 ходов
      1: 7, 7
      AppModel.js:168 2: 8, 6
      AppModel.js:168 3: 7, 6
      AppModel.js:168 4: 7, 5
      AppModel.js:168 5: 9, 7
      AppModel.js:168 6: 6, 7
      AppModel.js:168 7: 8, 7
      AppModel.js:168 8: 6, 6
      AppModel.js:168 9: 6, 5
      AppModel.js:168 10: 9, 8
      AppModel.js:168 11: 5, 7
      AppModel.js:168 12: 10, 7
      AppModel.js:168 13: 8, 9
      AppModel.js:168 14: 6, 8
      AppModel.js:168 15: 8, 8
      AppModel.js:168 16: 10, 6
      AppModel.js:168 17: 6, 10
      AppModel.js:168 18: 7, 9
      AppModel.js:168 19: 8, 10
      AppModel.js:168 20: 8, 11
      AppModel.js:168 21: 7, 10
      AppModel.js:168 22: 9, 10
      AppModel.js:168 23: 10, 9
      AppModel.js:168 24: 9, 6
      AppModel.js:168 25: 11, 6
      AppModel.js:168 26: 8, 4
      AppModel.js:168 27: 8, 5
      AppModel.js:168 28: 9, 3
      AppModel.js:168 29: 10, 2
      AppModel.js:168 30: 10, 4
      AppModel.js:168 31: 10, 5
      AppModel.js:168 32: 9, 4
      AppModel.js:168 33: 7, 4
      AppModel.js:168 34: 9, 5
      AppModel.js:168 35: 9, 2
      AppModel.js:168 36: 7, 3
      AppModel.js:168 37: 11, 7
      AppModel.js:168 38: 6, 2


      1. stasmus
        09.03.2016 16:35
        #8799209

        победа за 0
        New Game! X — AI, O — user AppModel.js:92:13
        1: 7, 7 AppModel.js:168:9
        2: 7, 6 AppModel.js:168:9
        3: 6, 6 AppModel.js:168:9
        4: 8, 8 AppModel.js:168:9
        5: 5, 5 AppModel.js:168:9
        6: 8, 7 AppModel.js:168:9
        7: 6, 5 AppModel.js:168:9
        8: 8, 9 AppModel.js:168:9
        9: 8, 6 AppModel.js:168:9
        10: 6, 8 AppModel.js:168:9
        11: 7, 8 AppModel.js:168:9
        12: 7, 9 AppModel.js:168:9
        13: 8, 10 AppModel.js:168:9
        14: 6, 9 AppModel.js:168:9
        15: 9, 9 AppModel.js:168:9
        16: 6, 10 AppModel.js:168:9
        17: 9, 7 AppModel.js:168:9
        18: 6, 11 AppModel.js:168:9
        19: 6, 12 AppModel.js:168:9
        20: 6, 7 AppModel.js:168:9


    1. Joshua
      09.03.2016 16:35
      #8799211

      Вот еще пример за 0. Тут AI игнорирует свою победу в 3 хода, вместо этого защищается и проигрывает.

      36 ходов
      1: 7, 7
      AppModel.js:168 2: 8, 6
      AppModel.js:168 3: 7, 6
      AppModel.js:168 4: 7, 8
      AppModel.js:168 5: 7, 5
      AppModel.js:168 6: 5, 6
      AppModel.js:168 7: 6, 7
      AppModel.js:168 8: 8, 7
      AppModel.js:168 9: 8, 5
      AppModel.js:168 10: 5, 8
      AppModel.js:168 11: 5, 7
      AppModel.js:168 12: 8, 8
      AppModel.js:168 13: 6, 8
      AppModel.js:168 14: 6, 9
      AppModel.js:168 15: 9, 6
      AppModel.js:168 16: 8, 9
      AppModel.js:168 17: 8, 10
      AppModel.js:168 18: 7, 9
      AppModel.js:168 19: 5, 9
      AppModel.js:168 20: 6, 10
      AppModel.js:168 21: 9, 7
      AppModel.js:168 22: 7, 10
      AppModel.js:168 23: 4, 7
      AppModel.js:168 24: 3, 7
      AppModel.js:168 25: 9, 8
      AppModel.js:168 26: 9, 9
      AppModel.js:168 27: 10, 9
      AppModel.js:168 28: 5, 11
      AppModel.js:168 29: 4, 12
      AppModel.js:168 30: 8, 11
      AppModel.js:168 31: 9, 12
      AppModel.js:168 32: 7, 11
      AppModel.js:168 33: 7, 12
      AppModel.js:168 34: 6, 11
      AppModel.js:168 35: 4, 11
      AppModel.js:168 36: 9, 11


      1. sozercanie_kosmosa
        10.03.2016 10:59
        #8800161

        в 25
        New Game! X — user, O — AI
        AppModel.js:164 1: 6, 7
        AppModel.js:164 2: 7, 7
        AppModel.js:164 3: 7, 6
        AppModel.js:164 4: 8, 5
        AppModel.js:164 5: 5, 8
        AppModel.js:164 6: 4, 9
        AppModel.js:164 7: 4, 7
        AppModel.js:164 8: 6, 9
        AppModel.js:164 9: 5, 6
        AppModel.js:164 10: 5, 9
        AppModel.js:164 11: 7, 9
        AppModel.js:164 12: 6, 8
        AppModel.js:164 13: 8, 6
        AppModel.js:164 14: 6, 6
        AppModel.js:164 15: 8, 8
        AppModel.js:164 16: 6, 10
        AppModel.js:164 17: 6, 5
        AppModel.js:164 18: 7, 4
        AppModel.js:164 19: 8, 7
        AppModel.js:164 20: 9, 8
        AppModel.js:164 21: 8, 9
        AppModel.js:164 22: 8, 10
        AppModel.js:164 23: 7, 8
        AppModel.js:164 24: 9, 10
        AppModel.js:164 25: 4, 5


  1. stasmus
    09.03.2016 16:38
    #8799213

    еще за 0
    New Game! X — AI, O — user AppModel.js:92:13
    1: 7, 7 AppModel.js:168:9
    2: 6, 7 AppModel.js:168:9
    3: 7, 6 AppModel.js:168:9
    4: 7, 8 AppModel.js:168:9
    5: 5, 6 AppModel.js:168:9
    6: 6, 6 AppModel.js:168:9
    7: 6, 8 AppModel.js:168:9
    8: 8, 6 AppModel.js:168:9
    9: 6, 5 AppModel.js:168:9
    10: 7, 5 AppModel.js:168:9
    11: 5, 7 AppModel.js:168:9
    12: 9, 7 AppModel.js:168:9
    13: 6, 4 AppModel.js:168:9
    14: 8, 7 AppModel.js:168:9
    15: 8, 8 AppModel.js:168:9
    16: 9, 6 AppModel.js:168:9
    17: 6, 9 AppModel.js:168:9
    18: 10, 5 AppModel.js:168:9
    19: 11, 4 AppModel.js:168:9
    20: 10, 8 AppModel.js:168:9
    21: 11, 9 AppModel.js:168:9
    22: 10, 7 AppModel.js:168:9
    23: 10, 6 AppModel.js:168:9
    24: 8, 5 AppModel.js:168:9
    25: 7, 4 AppModel.js:168:9
    26: 9, 5 AppModel.js:168:9
    27: 11, 5 AppModel.js:168:9
    28: 9, 4 AppModel.js:168:9
    29: 9, 3 AppModel.js:168:9
    30: 9, 8 AppModel.js:168:9


  1. quakin
    09.03.2016 17:24
    #8799281
    +1

    38, выиграл за 0
    X — AI, O — user
    1: 7, 7
    2: 6, 7
    3: 7, 6
    4: 7, 8
    5: 5, 6
    6: 6, 6
    7: 6, 8
    8: 8, 6
    9: 7, 5
    10: 7, 3
    11: 6, 5
    12: 4, 7
    13: 8, 7
    14: 5, 4
    15: 5, 5
    16: 4, 5
    17: 4, 6
    18: 6, 3
    19: 3, 6
    20: 7, 2
    21: 8, 1
    22: 7, 4
    23: 8, 5
    24: 9, 5
    25: 5, 7
    26: 3, 5
    27: 8, 4
    28: 7, 1
    29: 7, 0
    30: 8, 3
    31: 9, 3
    32: 5, 3
    33: 4, 3
    34: 6, 1
    35: 6, 2
    36: 9, 4
    37: 10, 5
    38: 5, 0


    1. Beif
      09.03.2016 20:54
      #8799645

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


  1. 9mm
    09.03.2016 17:31
    #8799291
    -6

    Хорошую вещь «гомоку» не назовут.


  1. Greendq
    09.03.2016 17:37
    #8799299
    +1

    Я реализовывал когда-то "5 в ряд" для Киндла (который читалка) (и "6 в ряд" на её основе потом). За основу был взят классический вариант реплизации min-max из примеров для Борландовской реализации Паскаля.
    QA Амазона выкатили единственную претензию — "игра слишком сложна и не прощает ошибок. Добавьте уровни сложности". Пришлось вводить "случайные" ошибки — т.е. ИИ тупо делал ошибки в зависимости от уровня сложности.


    1. Beif
      09.03.2016 20:56
      #8799651

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


  1. Joshua
    09.03.2016 17:48
    #8799317

    Тут явная проблема. AI не увидел угрозы в полуоткрытой 4-ке.

    22 хода
    New Game! X — AI, O — user
    AppModel.js:168 1: 7, 7
    AppModel.js:168 2: 8, 6
    AppModel.js:168 3: 7, 6
    AppModel.js:168 4: 9, 5
    AppModel.js:168 5: 7, 5
    AppModel.js:168 6: 7, 8
    AppModel.js:168 7: 7, 4
    AppModel.js:168 8: 7, 3
    AppModel.js:168 9: 8, 4
    AppModel.js:168 10: 10, 4
    AppModel.js:168 11: 6, 6
    AppModel.js:168 12: 9, 3
    AppModel.js:168 13: 9, 4
    AppModel.js:168 14: 8, 2
    AppModel.js:168 15: 11, 5
    AppModel.js:168 16: 6, 4
    AppModel.js:168 17: 5, 5
    AppModel.js:168 18: 4, 4
    AppModel.js:168 19: 8, 5
    AppModel.js:168 20: 11, 3
    AppModel.js:168 21: 10, 3
    AppModel.js:168 22: 12, 2


  1. MAXHO
    09.03.2016 19:19
    #8799475
    +2

    проблема даже не в том что выигрываю,
    Проблема что компьютер играет "скушно".

    Кстати, это интересная игровая проблема — как написать ИИ играющий "интересно". Т.е. ходы которого не просто набор оптимальных на глубину поиска, а "атакующие" или "защищающиеся" или "коварные". Именно субъективность делает игру интересной.


  1. spuf
    09.03.2016 20:19
    #8799573
    +1

    Мой (достаточно простой) вариант: http://spuf.github.io/xo-game/game.html


  1. chibiryaev
    09.03.2016 20:35
    #8799613

    Предлагаю помериться у кого будет самый короткий выигрыш

    17 ходов
    New Game! X — user, O — AI
    AppModel.js:168 1: 7, 7
    AppModel.js:168 2: 8, 7
    AppModel.js:168 3: 7, 4
    AppModel.js:168 4: 7, 6
    AppModel.js:168 5: 6, 5
    AppModel.js:168 6: 5, 6
    AppModel.js:168 7: 6, 4
    AppModel.js:168 8: 6, 6
    AppModel.js:168 9: 8, 6
    AppModel.js:168 10: 7, 5
    AppModel.js:168 11: 8, 4
    AppModel.js:168 12: 5, 4
    AppModel.js:168 13: 10, 4
    AppModel.js:168 14: 9, 4
    AppModel.js:168 15: 9, 5
    AppModel.js:168 16: 6, 8
    AppModel.js:168 17: 11, 3


  1. bromozel
    13.03.2016 18:03
    #8804127

    Добрый день
    Я немножко умею играть в эту игру. Программа, увы, пока не особо сильная :)
    Если вообще эта тема интересна, то есть даже чемпионат мира среди программ по гомоку:
    http://gomocup.org
    Там можно узнать о программах, которые играют сильно (непрофессионала обыграют). Если будут вопросы — пишите!