Как настроить дерево поиска Minimax для работы с игрой без терминов?

Question

Я должен сделать проект, в котором нам нужно реализовать настольную игру Mancala, а затем реализовать AI для нее.

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

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

Теперь я понимаю нормальное минимаксное дерево и то, как каждый уровень чередуется между минимальным узлом и максимальным узлом. С деревом, которое мне нужно сейчас, я бы сказал: min > max > max > min > max если 2-й игрок получил два хода?

Нам также нужно иметь возможность указать заданную глубину сгиба минимаксного дерева. Нам также нужно выполнить альфа-бета-обрезку, но это будет позже, как только у меня появится дерево.

Answer 1

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

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

Так что общий подход

Стандартный минимакс выглядит так:

function minimax(node, depth, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        bestValue := -∞
        for each child of node
            val := minimax(child, depth - 1, FALSE)
            bestValue := max(bestValue, val)
        return bestValue
    else
        bestValue := +∞
        for each child of node
            val := minimax(child, depth - 1, TRUE)
            bestValue := min(bestValue, val)
        return bestValue

Где вы инициализируете минимаксный вызов с max / min, а затем он постоянно меняется. В вашем случае вам нужно добавить только один крошечный чек.

function minimax(node, depth, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        bestValue := -∞
        for each child of node
            # here is a small change
            if freeTurn(child):
               isMax := TRUE
            else:
               isMax := FALSE
            val := minimax(child, depth - 1, isMax)
            bestValue := max(bestValue, val)
        return bestValue
    else
        bestValue := +∞
        for each child of node
            # here is a small change
            if freeTurn(child):
               isMax := FALSE
            else:
               isMax := TRUE
            val := minimax(child, depth - 1, isMax)
            bestValue := min(bestValue, val)
        return bestValue

Где твоя функция freeTurn возвращает вас, есть ли у вас свободный ход после вашего текущего хода. Обратите внимание, что для этого алгоритма нет разницы, можете ли вы сделать только 2 хода подряд или 5 ходов подряд.

Что касается Манкала

Существует множество вариаций манкалы, но фактор ветвления игры довольно мал (в том, что я знаю, <= 6). Теперь предположим, что у вас есть три хода A, B, C, D и двигаться C позволяет играть еще раз. С позиции C ты можешь делать ходы C1, C2, Таким образом, вы можете объединить их (C + C1, C + C2) и относитесь к ним как к одному движению (следует вести небольшую бухгалтерию, чтобы помнить, что на самом деле это два хода). Итак, сейчас вы заканчиваете вашими минимальными итерациями, когда у вас есть не 4, а 5 ходов: A, B, C + C1, C + C2, D, На самом деле нет ничего плохого в том, чтобы использовать этот подход для игр с большим коэффициентом ветвления.

Answer 2

Если у стороны может быть несколько ходов в повороте, то должен быть какой-то способ обнаружить это. При обнаружении генератор ходов для противника генерирует список, который содержит только нулевой ход, то есть ход, который ничего не делает. Оппонент будет вынужден сыграть этот ход (ничего не делать), и тогда первый игрок сможет рассчитать свой следующий ход.