我在跳棋游戏中实现了Alpha-beta剪枝算法，并以为它已经正常工作，但发现计算机在需要时并未进行连续的多次跳跃。例如：

AI 执行的操作：

O _ _ _ _      _ _ _ _ __ X _ X _  ->  _ _ _ X _  (因为只执行了一次移动而错过了跳跃)_ _ _ _ _      _ _ O _ _

AI 应该 执行的操作：

O _ _ _ _      _ _ _ _ O_ X _ X _  ->  _ _ _ _ _  (意识到当前回合未结束，继续进行)_ _ _ _ _      _ _ _ _ _

我尝试通过检查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可迭代对象中的一个元素），使其包含移动的元组（或列表），并在极小极大算法阶段避免使用TurnResule.NotDone。

采用这种方法 – moves列表将预先扩展，以包含移动(吃棋子，吃棋子)，除了单个移动之外。

这种解决方案将使算法更加健壮，并允许你轻松进行未来的修改。