beta修剪同一玩家的连续移动

我已经为跳棋实施了alpha-beta修剪，并认为我已经可以工作了，但是发现计算机并未连续进行多次跳跃（当它需要时）。 例如：

AI会：

O _ _ _ _      _ _ _ _ _

_ X _ X _  ->  _ _ _ X _  (misses a jump because it only does a single move)

_ _ _ _ _      _ _ O _ _

AI应该这样做：

O _ _ _ _      _ _ _ _ O
_ X _ X _  ->  _ _ _ _ _  (sees that it's current turn is not finished, continues)
_ _ _ _ _      _ _ _ _ _

我试图通过检查MovePiece的返回值来解决这个问题，该返回值返回是否玩家已经完成他的转身，由移动是否是跳转以及是否还有跳转来决定。 根据返回值，它将再次运行MaxValue / MinValue（取决于它在第一次看到还有哪些进一步移动时所处的位置），或者继续在树中并切换播放器。

相关代码（在C＃中）如下所示（retVal是包含Value，Depth和Move的类型）：

foreach(var m in moves)
{
    var resultingBoard = board.Clone();

    var moveResult = resultingBoard.MovePiece(m.TypeOfMove,
                                resultingBoard.GetPieceAtPosition(m.OriginalPieceLocation.X,
                                                                  m.OriginalPieceLocation.Y),
                                m.FinalPieceLocation.X, m.FinalPieceLocation.Y);

    var newDepth = currentDepth;

    if(moveResult == TurnResult.NotDone)
    {
        retVal = MaxValue(resultingBoard, ref alphaValue, ref betaValue, color, ref newDepth, ref maxDepth);
    }
    else if(moveResult == TurnResult.Finished)
    {
        newDepth++; 
        retVal = MinValue(resultingBoard, ref alphaValue, ref betaValue, color == PieceColor.Black ? PieceColor.Red : PieceColor.Black, ref newDepth, ref maxDepth);
    }
}

...

然而，这会导致一些...有趣的结果（第一步除了最小的李子之外什么也不做），尽管我认为这将是正确的改变。

让MaxValue / MinValue再次调用自己的新举措是正确的做法吗？

---

事实上，你的极小极大算法需要“产生”新的移动气味 （当你需要吃第二块）。

我会尝试重新设计它 - 您可以扩展move （迭代moves的元素），使其包含元组（或列表）移动 ，并避免Minimax算法阶段中的TurnResule.NotDone 。

采用这种方法 - 列表moves将被预先扩展，除了一次移动之外(eat piece,eat piece)还包含移动(eat piece,eat piece) 。

---

该解决方案将使算法更加稳健，并且可以让您轻松进行未来的修改。

链接地址: http://www.djcxy.com/p/56401.html

上一篇: beta pruning consecutive moves for same player

下一篇: Using minimax search for card games with imperfect information