algorithm - 同一玩家的 Alpha-beta 修剪连续 Action

Question

我已经为西洋跳棋实现了 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 用新的 Action 再次调用自己是正确的做法吗？

Answer 1

您的 minimax 算法需要“生成”新 Action 的事实 smells (当你需要吃第二 block 时)。

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

使用这种方法 - 列表 moves将预先扩展以包含移动 (eat piece,eat piece)除了单一的移动。

---

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