Negamax - 玩家移动两次

问题描述：

如何处理游戏？如果满足条件，同一个玩家移动？Negamax - 玩家移动两次

我想是这样的，但我不认为这是完全正确的：

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 α

如果你能解释更多关于所有变量的信息，我们可以帮忙... – 2012-01-07 21:00:24

@Dhaivat Pandya代码摘录取自wiki http://en.wikipedia.org/wiki/Negamax – 2012-01-07 21:04:08

啊。所以，这不是游戏开发，现在呢？ – 2012-01-07 21:06:00

答

不要尝试改变这个minimax算法本身，而是修改游戏表示以适应。基本上有两种解决方案：

表示一个玩家作为一个动作所做的动作序列。这在游戏很简单但是不会总是这样的情况下很有用。我写了一个AI引擎，用于生成这棵树的游戏（描述为游戏规则中的一个“移动”），PSPACE很难（对于真实游戏有很大的n），这意味着它在计算上不可行。另一方面，如果以这种方式对其进行建模对于特定游戏来说很容易，请这样做
表示一个玩家在一系列移动中交替移动时所做的移动顺序，其中另一个玩家执行任何操作。也就是说，只要符合条件，就可以在游戏状态中添加一条信息，这样其他玩家可以进行的唯一移动不会改变状态。这种方法在数学上是正确的，而且当我使用它的时候在实践中工作得很好。唯一需要记住的复杂性是，如果您使用iterative deepening，您将评估一个玩家连续多次移动的游戏树。您可能还需要小心在设计存储启发式与transposition table和其他哈希

我不知道有文献认为铁饼您的特定问题的使用。当我想到上面的解决方案2时，我感到很聪明，但我怀疑许多其他人发明了相同的技巧。

我应该说，获得极大极限家庭的权利是非常困难的。在高级语言中设计游戏搜索AI时，一个窍门是在更简单的游戏上测试搜索算法（缩小棋盘大小，使用井字棋等）以确保正确性。如果游戏很小，你可以a。通过手动和b来确保其结果是有意义的。像negascout一样测试高级算法，确保他们给出与天真negamax相同的答案。将代码与特定于游戏的行为（评估函数，棋盘表示，搜索和存储启发式等）保持在远离执行树搜索的代码之间也是一个好主意。

答

在negamax，你正在探索一个树形结构，其中每个节点具有对应于由玩家做出的举动孩子。如果在某些情况下玩家可以移动两次，那么您可能会想将该玩家的“移动”视为该玩家制作的两个移动顺序。更一般地说，您应该将当前游戏状态的孩子视为当前玩家轮到后可以获得游戏的所有可能状态。这包括所有可以通过一次移动到达的游戏状态，以及如果玩家能够在一个回合中进行两次移动，则以两次移动可达到的所有游戏状态。因此，您应该保持negamax的基本逻辑不变，但更新代码以生成后继状态来处理单个玩家可以移动两次的情况。

希望这会有所帮助！

我还不够清楚，如果遇到一些条件，玩家可以多次移动。所以，如果我要实现你的解决方案，我将处理一个新的树结构，只是为了找到节点的后继者。 – 2012-01-07 21:37:53

@ JohnRetallack-是的，那是对的。我认为关键的想法是认识到一个“移动”不只是一个游戏，而是一个玩家完成一个玩家不能参与其中的完整序列。或者，您可以将一名球员的一系列动作视为一系列交替动作，其中另一名球员*进行“禁止”动作。 – templatetypedef 2012-01-08 01:54:41

@templatetypedef：OP的代码有什么问题？我看起来很好。 – TonyK 2012-01-11 18:05:43

答

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

Negamax - 玩家移动两次

相关推荐