algorithm - Negamax - 玩家移动两次

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

不要尝试为此更改 minimax 算法本身，而是修改游戏表示以适应。基本上有两种解决方案:

1. 将单个玩家的一系列 Action 表示为一个 Action 。这在游戏简单时有效，但并非总是如此。我为一个游戏编写了一个 AI 引擎，其中生成这棵树(在游戏规则中被描述为一个“移动”)是 PSPACE 困难的(并且对于真实游戏有一个非常大的 n)意味着它在计算上不可行。另一方面，如果以这种方式建模对于您的特定游戏来说很容易，那就那样做
2. 将一个玩家的移动序列表示为交替移动的一系列移动，其中另一个玩家做任何事情。也就是说，只要满足您的条件，您就会向游戏状态添加一条信息，这样其他玩家可以做出的唯一移动不会改变状态。这种方法在数学上是正确的，当我使用它时，它在实践中效果很好。唯一要记住的复杂性是，如果您使用 iterative deepening您将评估一个玩家连续多次移动的游戏树。在设计与 transposition table 一起使用的存储启发式时，您可能还需要小心。和其他哈希值

据我所知，没有文献讨论过您的特定问题。当我想到上面的解决方案 2 时，我觉得自己很聪明，但我怀疑很多其他人也发明了同样的把戏。

我应该说，正确处理 minimax 系列非常困难。用高级语言设计游戏搜索 AI 时的一个技巧是在更简单的游戏(减少棋盘大小、使用井字游戏等)上测试您的搜索算法以确保正确性。如果游戏足够小，你可以。通过手动和 b 玩游戏来确保其结果有意义。测试高级算法，如 negascout通过确保他们给出与 naive negamax 相同的答案。尝试让具有游戏特定行为(评估函数、棋盘表示、搜索和存储启发式等)的代码远离执行树搜索的代码也是一个好主意。