5

如果满足条件,同一玩家移动,您如何处理游戏?

我尝试过这样的事情,但我认为这不太对:

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 α
4

3 回答 3

11

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

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

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

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

于 2012-01-07T23:43:29.463 回答
2

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

希望这可以帮助!

于 2012-01-07T21:28:37.057 回答
0

当条件满足时,不要减少深度。

于 2012-03-25T14:35:38.687 回答