0

私は Checkers に alpha-beta pruning を実装し、動作していると思っていましたが、コンピューターが複数のジャンプを連続して実行しないことがわかりました (必要な場合)。例えば：

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 を再度呼び出すのは正しいことですか?

4

1 に答える 1

2

ミニマックスアルゴリズムが新しい動きを「生成」する必要があるという事実は、 匂いがします（2番目のピースを食べる必要がある場合）。

私はそれを再設計しようとします- （iterableの要素）を拡張してmove、移動のタプル（またはリスト）を含むようにし、ミニマックスアルゴリズムの段階で回避することができます。movesTurnResule.NotDone

このアプローチでは、リストmovesは事前に拡張さ(eat piece,eat piece)れ、単一の移動に加えて移動も含まれます。

このソリューションにより、アルゴリズムがはるかに堅牢になり、将来の変更が容易になります。

于 2012-11-28T17:09:37.100 に答える