0

我已经为 Checkers 实现了 alpha-beta 修剪，并认为我已经让它工作了，但发现计算机不会连续进行多次跳转（当它必须时）。例如：

人工智能会：

O _ _ _ _      _ _ _ _ _

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

_ _ _ _ _      _ _ O _ _

人工智能应该这样做：

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

4

1 回答 1

2

您的极小极大算法需要“生成”新动作的事实 （当您需要吃第二块时）。

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

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

该解决方案将使算法更加健壮，并允许您轻松地进行将来的修改。

于 2012-11-28T17:09:37.100 回答