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. 将一个玩家所做的移动序列表示为交替移动的移动序列,其他玩家可以做任何事情.也就是说,只要满足条件,就会向游戏状态添加一条信息,这样其他玩家可以进行的唯一移动就不会改变状态.这种方法在数学上是正确的,当我使用它时,它在实践中运作得很好.要记住的唯一复杂性是,如果你使用迭代加深,你将评估一个玩家连续多次移动的游戏树.在设计与转置表和其他哈希一起使用的存储启发式时,您可能还需要小心

我知道没有任何文献能够讨论你的特定问题.当我想出上面的解决方案2时,我感到很聪明,但我怀疑很多其他人发明了同样的技巧.

我应该说,让极小极大家庭正确行动是非常困难的.在高级语言中设计游戏搜索AI时的一个技巧是在更简单的游戏(缩小的板尺寸,使用井字游戏等)上测试您的搜索算法以确保正确性.如果游戏很小,你就可以了.通过手动玩游戏确保其结果有意义.通过确保他们给出与天真的negamax相同的答案来测试像negascout这样的高级算法 .尝试将代码与游戏特定行为(评估函数,板表示,搜索和存储启发式等)保持在远离执行树搜索的代码的位置也是一个好主意.