Perft test results - Can't find Bug?

Question

I apologize right now for my bad english, I'm italian.

I'm writing a full implementation of a chess game in C#, Player vs Player and Player vs Computer, and now I'm having some difficult implementing a NegaMax algorithm. for who is interested, here is my github repository: https://github.com/crybot/ChessEngine_NOGUI/tree/master/Chess%20Engine%20-%20NOGUI

I have tried to make this project as OO as possible, so, if you think my design is incorrect, please tell me :)

here is my problem:

I implemented a very simple evaluation function that work symmetrically for all players:

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;
}

And here is my NegaMax function, wich accept a Game parameter (that includes board, players, ecc.ecc.), the playerColor provided by an enum, and the depth-search;

I first scan for all the possible moves of the EnginePlayer and then I get their score from the NegaMax function, but something is not working...

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;
}

I think this is all... I hope you will find what I'm doing wrong :) thanks.

Edit: I implemented a Perft that has showed the non-correctnes of the move generator. It helped a lot finding some relatively easy to find bugs, but at last some results are still wrong. Here are the results:

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

and here are the correct results: https://chessprogramming.wikispaces.com/Perft+Results

As you can see, at Depth 4, I get correct nodes analyzed, but incorrect Captures and checks values (while mates are correct).

Thanks to those results I tried to isolate the bug by dividing the nodes analyzed per move at depth 4, getting those results:

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

and the compared with those results, obtained from 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

but even here the values are correct... So I tried a depth 5 perft getting those results:

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

and then compared to Sharper's results:

 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

So I realized that the problem is caused by the moves generated by the double-pushes of the pawns... but I can't really found the bug... has anyone had the same problem? or something similar, or just an hint to find that bug...

thanks to all :)

Answer 1

You should first ensure move generation is consistent, have a look here on how to. This is referred as perft tests. Another strange thing is I can't see in your algo the 'mate' threated: you should return a very bad value when there is no moves at all and the king is under capture ( otherwise is a stand ). Then you should put some strategy to sort the moves in order to benefit from the negamax algorithm, and then some 'horizon' strategy ( that is, what happen if there is still captures when depth== 0 ? ). If you have problem with move generation, try challenging your engine with some more interesting position, have a look here for example, or if you want something harder this is the file that I use for testing my engine. It consist of many lines containing positions in FEN format, followed by depth-move count in the following format:

D1 50; D2 279

thats mean ( for example ) 50 moves at depth1, 279 moves at depth 2

The position I proposed comes frome my old research on goggle, about challenging position. You need being able to support FEN notation, if you are not yet I strongly reccomend to implement, since it is a "de facto" standard for communicating positions in chess engine ( and not only ) world.

Answer 2

Have you figured it out? I got the same problem. By saying the same I mean I got 1610 captures for perft(4) for the initial position.

And, this guy seemed to have the same problem too.

I examined the code(and replaced some complicated codes with naive alternatives) very carefully, but could not find anything wrong. After all, the total moves count are correct, aren't they?

Then I realize that:　1610 = 1576 + 34. This is just one example, I examined the rest perft results, and was sure it was the problem.

The capture counts in those 'standard' perft result tables count captures only the leaf nodes with depth equals to 0, including en passant captures.