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

Вступление

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

Я реализовал этот ИИ для игры в Connect Four, но он подходит для многих разных игр. Я все же рекомендую что-то вроде Connect Four для начинающих, потому что игровая механика проста.

Возьмем, к примеру, шахматы: Minimax может играть в шахматы, но у вас есть несколько отдельных фигур, которые делают разные ходы, а также захват, рокировка, шах, мат и т. Д. В то время как с Connect Four все, что вы можете сделать, это бросить фигуру в столбик. Это означает, что каждый ход настолько прост, что его можно представить как одно целое число (индекс столбца, в который нужно поместить фигуру), а доска представляет собой просто 2D-массив.

Что-то вроде крестиков-ноликов также было бы хорошим выбором, но даже в этом случае вы должны рассматривать как столбцы, так и строки.

Теперь давайте поговорим о том, как на самом деле будет работать этот ИИ: алгоритм минимакса.

Как работает Minimax

В теории игр Minimax - это рекурсивный алгоритм, который максимизирует возможности для себя, минимизируя возможности для своего противника. Таким образом, название говорит само за себя.

Допустим, противник ходит первым. Minimax будет следить за состоянием игрового поля после того, как будет сделан ход, а затем рассмотрит все возможные ходы, которые он может сделать. И для каждого итогового состояния игры он затем будет рассматривать все возможные ходы, которые может сделать оппонент, и так далее ...

Это будет происходить либо до тех пор, пока не будет найдено конечное состояние игры (игра выиграна или доска заполнена), либо пока не будет достигнута определенная глубина. Глубина ограничена, иначе дерево всех возможных состояний игры будет быстро расти и будет очень медленно вычисляться.

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

Затем алгоритм выбирает ход, который в конечном итоге приведет к состоянию доски с наивысшим баллом для ИИ и наименьшим баллом для противника. И это тот ход, который он сделает.

Реализация

Настраивать

Чтобы написать алгоритм Minimax, вам потребуются некоторые переменные и функции, реализация которых будет зависеть от вашей настольной игры:

npc => In my case, just a character that represents the AI's piece
opponent => Another character to represent the opponent's piece
isTerminalNode() => To determine if a board is terminal (boolean)
isWinningMove()  => To determine if a move wins the game (boolean)
getValidMoves()  => To get all possible valid moves (array)
score()          => To calculate a board state's score (integer)
tempBoard()      => To make a copy of the game board (2D array)
makeMove()       => Make a hypothetical move on the board (void)

Поскольку моя игра - Connect Four, мой метод isTerminalNode () вызывает серию вспомогательных методов, которые выполняют следующее:

  1. Проверьте, нет ли четверки в ряду (по диагонали, вертикали или горизонтали).
  2. Убедитесь, что доска заполнена и больше нельзя делать ходов.

Вам нужен getValidMoves (), потому что столбец может заполниться, и поэтому Minimax не должен пытаться перемещаться в этом столбце.

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

Current player gets 4 in a row                              => 100
Current player gets 3 in a row with an empty adjacent space => 5
Current player gets 2 in a row with 2 empty adjacent spaces => 2
Opponent has 3 in a row with an empty adjacent space        => -500

Это гарантирует, что ваш ИИ будет размещать свои части рядом друг с другом, а также не позволит противнику получить 4 штуки подряд.

Алгоритм

Я написал свой код на Java, но я собираюсь перевести его в своего рода псевдокод в стиле Java / Python, чтобы эта статья не зависела от языка.

  • В первой части найдите все допустимые ходы, которые можно сделать, и проверьте, находится ли доска в конечном состоянии.
  • Мы будем уменьшать глубину каждый раз, поэтому, когда глубина равна 0 или доска является терминальной, проверьте, выиграна ли игра для NPC (неигрового персонажа) или оппонента.
  • Если да, верните соответственно очень высокий или низкий балл. Если нет, верните счет для этой доски.
minimax(board, depth, maximisingPlayer)
    int[] validCols = getValidMoves(board)
    boolean isTerminalNode = isTerminalNode(board)
    if (depth == 0 || isTerminalNode)
        if (isTerminalNode)
            if (isWinningMove(board, npc))
                return null, 1000000000
            else if (isWinningMove(board, opponent))
                return null, -2000000000
            else
                return null, 0
        else
            return null, score(board, npc)

Обратите внимание, что функция возвращает две вещи: счет и ход.

  • Создайте две переменные: ход (случайный ход в списке допустимых ходов) и значение (счет).
  • Теперь проверьте, принадлежит ли текущий ход нашему ИИ (игроку, которого мы хотим максимизировать) или оппоненту (игроку, которого мы хотим минимизировать). Это передается в функцию в качестве аргумента - проверьте подпись в блоке кода выше.
  • Если сейчас ход максимизирующего игрока, установите для value что-нибудь очень низкое, например отрицательную бесконечность.
  • Затем выполните итерацию по массиву допустимых ходов и для каждого из них сделайте ход (на копии доски, чтобы не менять состояние исходной доски - я определил функцию для неглубокого копирования моей доски), сделайте рекурсивный вызов minimax (), передавая новое игровое поле, глубина минус один и ложь (потому что теперь мы хотим сделать ход для минимизирующего игрока). [1] в конце вызова указывает, что мы хотим вернуть вторую вещь, а именно счет.
  • Присвойте новые значения значению и переместите его, если результат, возвращаемый функцией minimax (), больше отрицательной бесконечности.
    int move = validCols[(Math.random() * validCols.length)]
    double value
    if (maximisingPlayer)
        value = NEGATIVE_INFINITY;
        for (int validCol : validCols)
            char[][] tempBoard = tempBoard(board)
            makeMove(validCol, tempBoard, npc, ROWS)
            int newScore = minimax(tempBoard, depth - 1, false)[1]
            if (newScore > value)
                value = newScore
                move = validCol

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

    else
        value = POSITIVE_INFINITY
        for (int validCol : validCols)
            char[][] tempBoard = tempBoard(board)
            makeMove(validCol, tempBoard, opponent, ROWS)
            int newScore = minimax(tempBoard, depth - 1, true)[1]
            if (newScore < value)
                value = newScore
                move = validCol
    return move, value

Возвращенный ход - это то, чего вы в конечном итоге добиваетесь. И это так просто.

Оптимизация

Чем глубже ваш ИИ сможет заглянуть в дерево возможных досок, тем сложнее оно будет. Однако, как я упоминал ранее, это требует больших вычислительных затрат.

Вы, конечно, можете оптимизировать алгоритм Minimax с помощью метода, называемого альфа-бета-обрезкой, о котором я расскажу в другой статье, а когда он выйдет, я дам ссылку здесь.

Заключение

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

Я отправил игру одному из моих друзей, который считает себя очень сильным игроком в Connect Four, и именно он назвал ИИ «непобедимым».

Это должно дать вам все необходимое для реализации собственного искусственного интеллекта для настольных игр. Если вы создаете что-то классное, оставьте отзыв.

А пока удачного кодирования!

Ресурсы

Кейт Галли Соедините четыре Minimax AI https://www.youtube.com/watch?v=MMLtza3CZFM

Великолепно минимаксный алгоритм https://brilliant.org/wiki/minimax/

FreeCodeCamp Минимаксный алгоритм https://www.freecodecamp.org/news/playing-strategy-games-with-minimax-4ecb83b39b4b/