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. 将单个玩家的移动序列表示为一个移动。当游戏很简单时，这是有效的，但并不总是有效。我为一个游戏写了一个AI引擎，其中生成这棵树(在游戏规则中被描述为一个“移动”)是PSPACE困难的(并且对于真正的游戏有一个非常大的n)，这意味着它在计算上是不可行的。另一方面，如果以这种方式建模对于您的特定游戏很容易，那么使用
2. 将一个玩家进行的移动序列表示为交替移动的序列，其中另一个玩家可以执行任何操作。也就是说，每当满足您的条件时，您都会向游戏状态添加一条信息，以便其他玩家可以进行的唯一移动不会改变状态。这种方法在数学上是正确的，当我使用它时，它在实践中工作得很好。唯一要记住的复杂性是，如果你使用iterative deepening，你将会评估一个玩家连续移动多次的博弈树。在设计与

的transposition table和其他哈希一起使用的存储试探法时，您可能还需要小心

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

我应该说，获得正确的minimax家族是出乎意料的困难。在高级语言中设计游戏搜索人工智能时的一个技巧是在更简单的游戏上测试您的搜索算法(减少棋盘大小，使用tic-tac-toe等)以确保正确性。如果游戏很小，你可以a。通过手工玩游戏来确保它的结果是有意义的，b。测试高级算法，如negascout，确保它们给出的答案与朴素的negamax相同。尝试将具有游戏特定行为(评估函数、棋盘表示、搜索和存储启发式等)的代码与执行树搜索的代码保持在一起也是一个好主意。

Answer 2

在negamax中，您正在探索一个树结构，其中每个节点都有对应于玩家所做动作的子节点。如果在某些情况下，一个玩家可以移动两次，您可能希望将该玩家的“移动”看作是该玩家进行的两步移动序列。更广泛地说，您应该将当前游戏状态的子代视为当前玩家在轮到他们之后可以进入的所有可能状态。这包括通过一步棋可以到达的所有游戏状态，加上如果玩家能够在一轮中进行两步棋的话在两步棋中可以到达的所有游戏状态。因此，您应该保持negamax的基本逻辑不变，但更新您的代码以生成后续状态，以处理单个玩家可以移动两次的情况。

希望这能有所帮助！

Answer 3

当满足条件时，不要减小深度。