Негамакс - игрок двигается дважды

Question

Как вы относитесь к играм, в которых, если выполняется условие, перемещается один и тот же игрок?

Я пробовал что-то подобное, но не думаю, что это правильно:

function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            if (condition is met) // the same player moves
               val := negamax(child, depth-1, α, β, color)
            else
               val := -negamax(child, depth-1, -β, -α, -color)
            if val≥β
                return val
            if val≥α
                α:=val
        return α

Answer 1

Не пытайтесь изменить сам минимаксный алгоритм для этого, вместо этого измените представление игры, чтобы приспособиться.Есть в основном два решения:

1. Представляет последовательность ходов, сделанных одним игроком, как один ход.Это работает, когда игра проста, но не всегда.Я написал движок ИИ для игры, в которой генерация этого дерева (описанного в правилах игры как один «ход») является трудной для PSPACE (и имела очень большое n для реальных игр), означая, что она неосуществима в вычислительном отношении.С другой стороны, если моделирование этого способа легко для вашей конкретной игры, сделайте это таким образом
2. Представьте последовательности ходов, сделанных одним игроком, как последовательности ходов, чередующихся ходов, где другой игрок делаетДелать что-нибудь.Таким образом, вы добавляете часть информации в состояние игры всякий раз, когда выполняется ваше условие, так что единственный ход, который может сделать другой игрок, не меняет состояние.Этот метод математически правильный, и когда я использовал его, он работал довольно хорошо на практике.Единственная сложность, которую следует иметь в виду, заключается в том, что если вы используете итеративное углубление , вы будете недооценивать деревья игр, в которых один игрок перемещается много раз подряд.Вам также может понадобиться быть осторожным при разработке эвристики хранения для использования с таблицей транспонирования и другими хэшами

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

Я должен сказать, что правильно подобрать минимаксную семью на удивление сложно.При разработке ИИ для поиска игр на языках высокого уровня хитрость заключается в том, чтобы проверить свои алгоритмы поиска в более простых играх (уменьшенный размер доски, использовать крестики-нолики и т. Д.), Чтобы убедиться в их корректности.Если игра маленькая, вы можете:убедитесь, что его результаты имеют смысл, сыграв в игру вручную и б.протестируйте продвинутые алгоритмы, такие как negascout , убедившись, что они дают тот же ответ, что и наивный negamax.Также хорошей идеей является попытаться сохранить код с поведением, специфичным для игры (функции оценки, представления на доске, эвристики поиска и хранения и т. Д.), От кода, который выполняет поиск по дереву.

Answer 2

В negamax вы изучаете древовидную структуру, в которой у каждого узла есть дочерние элементы, соответствующие ходам, сделанным игроком. Если в каком-то случае игрок может двинуться дважды, вы, вероятно, захотите думать о «ходе» для этого игрока как о последовательности двух ходов, которую делает игрок. В более общем смысле, вы должны думать о детях текущего игрового состояния как о всех возможных состояниях, в которые текущий игрок может войти в игру после своего хода. Это включает в себя все игровые состояния, достижимые за один ход, плюс все игровые состояния, достижимые за два хода, если игрок может сделать два хода за один ход. Поэтому вы должны оставить базовую логику Negamax неизменной, но обновите свой код, чтобы генерировать состояния преемника для обработки случая, когда один игрок может двинуться дважды.

Надеюсь, это поможет!

Answer 3

При выполнении условия не уменьшать глубину.