2

私はイタリア人なので、英語が下手で申し訳ありません。

私は C# でチェス ゲームの完全な実装、Player vs Player、Player vs Computer を書いていますが、今は NegaMax アルゴリズムの実装に苦労しています。興味のある方は、こちらが私の github リポジトリです: https://github.com/crybot/ChessEngine_NOGUI/tree/master/Chess%20Engine%20-%20NOGUI

私はこのプロジェクトを可能な限り OO にしようと試みたので、私の設計が間違っていると思われる場合は教えてください :)

ここに私の問題があります:

すべてのプレイヤーに対して対称的に機能する非常に単純な評価関数を実装しました。

public static float Evaluate(PieceColor playerColor, Game game)
{
    float score = 0;

    score += 1 * (game.board.GetNumberOfPieces(PieceType.Pawn, playerColor)
    - game.board.GetNumberOfPieces(PieceType.Pawn, playerColor.GetOpposite()));

    score += 3 * (game.board.GetNumberOfPieces(PieceType.Bishop, playerColor)
    - game.board.GetNumberOfPieces(PieceType.Bishop, playerColor.GetOpposite()));

    score += 3 * (game.board.GetNumberOfPieces(PieceType.Knight, playerColor)
    - game.board.GetNumberOfPieces(PieceType.Knight, playerColor.GetOpposite()));

    score += 5 * (game.board.GetNumberOfPieces(PieceType.Rook, playerColor)
    - game.board.GetNumberOfPieces(PieceType.Rook, playerColor.GetOpposite()));

    score += 9 * (game.board.GetNumberOfPieces(PieceType.Queen, playerColor)
    - game.board.GetNumberOfPieces(PieceType.Queen, playerColor.GetOpposite()));

    score += 0.1f * (game.GetPlayer(playerColor).GetMoves(game).Count);

    return score;
}

そして、ここに私の NegaMax 関数があります。この関数は、Game パラメーター (ボード、プレーヤー、ecc.ecc を含む)、enum によって提供される playerColor、および深度検索を受け入れます。

まず、EnginePlayer のすべての可能な動きをスキャンしてから、NegaMax 関数からスコアを取得しますが、何かが機能していません...

private float NegaMax(Game game, PieceColor playerColor, int depth)
{
    if (depth == 0) 
    return EvaluateMove(playerColor, game);

    float max = float.MinValue;
    float score;

    foreach (Move move in game.GetPlayer(playerColor.GetOpposite()).GetMoves(game))
    {
        game.board.SimulateMove(move);
        score = Math.Max(max, -NegaMax(game, playerColor.GetOpposite(), depth - 1));

        game.board.CancelMove(move);

        if (score > max)
          max = score;
    }

    return max;
}


public Move ThinkMove(Game game, PieceColor playerColor, int depth)
{

    Move bestMove = new NullMove();
    float bestScore = float.MinValue;
    float temp = 0;

    foreach (Move move in GetMoves(game))
    {
        game.board.SimulateMove(move);
        temp = NegaMax(game, playerColor, depth);
        game.board.CancelMove(move);

        if (temp > bestScore)
        {
            if (Judge.IsLegal(move, game))
            {
                 bestMove = move;
                 bestScore = temp;
            }
        }
    }

    if (bestMove is NullMove)
    throw new NotImplementedException();
    return bestMove;
}

これですべてだと思います...私が間違っていることを見つけていただければ幸いです:)ありがとう。

編集: ムーブ ジェネレーターの不正解を示す Perft を実装しました。比較的見つけやすいバグを見つけるのに大いに役立ちましたが、最終的にいくつかの結果はまだ間違っています。結果は次のとおりです。

Perft Depth: 1
Nodes: 20  Captures: 0  Checks: 0  Castles: 0  Mates: 0  EnPassant: 0

Perft Depth: 2
Nodes: 400  Captures: 0  Checks: 0  Castles: 0  Mates: 0  EnPassant: 0

Perft Depth: 3
Nodes: 8902  Captures: 34  Checks: 12  Castles: 0  Mates: 0  EnPassant: 0

Perft Depth: 4
Nodes: 197281  Captures: 1610  Checks: 473  Castles: 0  Mates: 8  EnPassant: 0

正しい結果は次のとおりです: https://chessprogramming.wikispaces.com/Perft+Results

ご覧のように、深さ 4 では正しいノードが分析されますが、キャプチャとチェックの値は正しくありません (メイトは正しいのに)。

これらの結果のおかげで、深さ 4 で移動ごとに分析されたノードを分割することでバグを分離しようとしました。これらの結果が得られました。

Move    Nodes
a2a3    8457
a2a4    9329
b2b3    9345
b2b4    9332
c2c3    9272
c2c4    9744
d2d3    11959
d2d4    12435
e2e3    13134
e2e4    13160
f2f3    8457
f2f4    8929
g2g3    9345
g2g4    9328
h2h3    8457
h2h4    9329
b1a3    8885
b1c3    9755
g1f3    9748
g1h3    8881
Total Nodes: 197281

そして、Sharper から取得したこれらの結果と比較します。

 Sharper v0.17 by Albert Bertilsson
 divide 4
 b1c3 9755
 b1a3 8885
 g1h3 8881
 g1f3 9748
 a2a3 8457
 a2a4 9329
 b2b3 9345
 b2b4 9332
 c2c3 9272
 c2c4 9744
 d2d3 11959
 d2d4 12435
 e2e3 13134
 e2e4 13160
 f2f3 8457
 f2f4 8929
 g2g3 9345
 g2g4 9328
 h2h3 8457
 h2h4 9329
 Nodes: 197281
 Moves: 20

しかし、ここでも値は正しいです...だから私はそれらの結果を得るための深さ5のperftを試しました:

Move    Nodes
a2a3    181046
a2a4    217813
b2b3    215255
b2b4    216110
c2c3    222861
c2c4    240044
d2d3    328511
d2d4    361753
e2e3    402988
e2e4    405348
f2f3    178891
f2f4    198437
g2g3    217210
g2g4    214017
h2h3    181044
h2h4    218810
b1a3    198572
b1c3    234656
g1f3    233491
g1h3    198502
Total Nodes: 4865359

次に、Sharper の結果と比較します。

 Sharper v0.17 by Albert Bertilsson
 divide 5
 b1c3 234656
 b1a3 198572
 g1h3 198502
 g1f3 233491
 a2a3 181046
 a2a4 217832
 b2b3 215255
 b2b4 216145
 c2c3 222861
 c2c4 240082
 d2d3 328511
 d2d4 361790
 e2e3 402988
 e2e4 405385
 f2f3 178889
 f2f4 198473
 g2g3 217210
 g2g4 214048
 h2h3 181044
 h2h4 218829
 Nodes: 4865609
 Moves: 20

それで、ポーンのダブルプッシュによって生成された動きが問題の原因であることに気付きました...しかし、実際にはバグを見つけることができません... 誰か同じ問題がありましたか? または同様のもの、またはそのバグを見つけるための単なるヒント...

ありがとうございます ：）

4

2 に答える 2

1

最初に移動の生成が一貫していることを確認する必要があります。方法については、こちらを参照してください。これはパーフト テストと呼ばれます。もう1つの奇妙なことは、あなたのアルゴで「仲間」が脅かされているのを見ることができないことです.まったく動きがなく、キングが捕獲されている場合(そうでなければスタンドです)、非常に悪い値を返す必要があります. 次に、negamax アルゴリズムの恩恵を受けるために移動を並べ替えるための戦略を立ててから、「地平線」戦略 (つまり、depth== 0 のときにキャプチャがまだある場合はどうなるか?) を設定する必要があります。ムーブの生成に問題がある場合は、エンジンにもっと興味深い位置で挑戦してみてください。たとえば、ここを見てください。または、より難しいものが必要な場合は、これが私のエンジンのテストに使用するファイルです。. これは、FEN 形式の位置を含む多くの行で構成され、その後に次の形式の深度移動カウントが続きます。

D1 50; D2 279

つまり、(たとえば) 深さ 1 で 50 回、深さ 2 で 279 回移動します。

私が提案した位置は、挑戦的な位置についてのゴーグルに関する私の古い研究から来ています。FEN 表記をサポートできる必要があります。まだ実装していない場合は、実装することを強くお勧めします。これは、チェス エンジン (および だけでなく) の世界で位置を伝達するための「事実上の」標準であるためです。

于 2012-07-06T15:44:04.870 に答える