阿尔法-贝塔修剪同一玩家的连续移动

Question

我已经为Checkers实现了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 to do的类型)：

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再次自我调用是正确的做法吗？

Answer 1

事实上，你的最小最大算法需要"生成"新的动作，这闻起来很香(当你需要吃第二块时)。

我会尝试重新设计它-你可以这样做扩展move(可迭代moves中的一个元素)，使其包含移动的元组(或列表)，并在最小最大算法阶段避免使用TurnResule.NotDone。

通过这种方法，列表moves将预先扩展为除了单个移动之外还包含移动(eat piece,eat piece)。

---

此解决方案将使算法更加稳健，并允许您在未来轻松修改。