how do I debug my move generation/make unmake functions?

[am5083]

I've hit a roadblock in debugging my move generator where my `perft` output is incorrect, but when I manually step through the moves to see if I can find where the problem is, my `perft` outputs the correct number of nodes per stockfish.

For example:

FEN: 2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1
DEPTH 0: 13
D1C2: 48
D1D2: 48
D1E2: 48
D1C1: 39
D1E1: 39
E8A8: 43
E8B8: 84
E8C8: 352
E8D8: 343
E8F8: 338
E8G8: 348
E8H8: 349
E8E7: 76
DEPTH 1: 2155

But then when I do something like make(...E8H8...), the output becomes:

A7B7: 160
A7A6: 157
A7B6: 181
E7E8n: 111
E7E8b: 147
E7E8r: 197
E7E8q: 272
DEPTH 1: 1225

which is what it should be, per stockfish:

go perft 3
e7e8q: 272
e7e8r: 197
e7e8b: 147
e7e8n: 111
a7a6: 157
a7b6: 181
a7b7: 160

Nodes searched: 1225

This is the second position I've hit this problem with and I don't know what to do or where to begin trying to solve it, any help is appreciated.

[am5083]

This is the source, if it helps

[Ras]

FEN: 2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1
DEPTH 0: 13

That's already wrong because it counts Kb8 and Kd8 which are pseudo-legal, but actually illegal. There are 11 legal moves with White to move, and perft only counts legal moves and nodes following legal moves.

[Ajedrecista]

Hello:

I can not give you a solution since I am not a programmer, but I want to point out a possible mess with FEN strings. In your second position, I think that you make ...E8C8... instead of ...E8H8..., and the white king is on a7 instead of a8 of your first FEN. I mean, your second position should be:

[d]2r5/K3P3/8/8/8/8/8/3k4 w - - 0 1

And your first position should be with the white king on a7 (instead of on c8 in your first FEN), the black rook on e8 (instead of on f8 in your first FEN) and black to move (instead white to move in your first FEN), given the list of possible moves of perft(1):

[d]4r3/K3P3/8/8/8/8/8/3k4 b - - 0 1

And from this position, perft(4) = 10313 and starting with ..., Rc8: perft(3) = 1225 using divide function of perft().

Regards from Spain.

Ajedrecista.

[am5083]

FEN: 2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1
DEPTH 0: 13

That's already wrong because it counts Kb8 and Kd8 which are pseudo-legal, but actually illegal. There are 11 legal moves with White to move, and perft only counts legal moves and nodes following legal moves.

I should clarify that the FEN in perft output is not the position perft is generating moves for, that's just the initial position before I manually started 'making' moves

[am5083]

This is a better demonstration of the issue:

FEN: 5r2/1K2P3/8/8/8/8/8/3k4 b - - 1 1

Code: Select all

DEPTH 0: 19
D1C2: 214
D1D2: 362
D1E2: 307
D1C1: 351
D1E1: 236
F8A8: 344
F8B8: 71
F8C8: 336
F8D8: 357
F8E8: 324
F8G8: 363
F8H8: 364
F8F7: 129
F8F6: 330
F8F5: 426
F8F4: 429
F8F3: 428
F8F2: 434
F8F1: 334
DEPTH 3: 6139

stockfish:

Code: Select all

position fen 5r2/1K2P3/8/8/8/8/8/3k4 b - - 1 1
go perft 3
f8f1: 176
f8f2: 224
f8f3: 224
f8f4: 224
f8f5: 224
f8f6: 167
f8f7: 120
f8a8: 122
f8b8: 81
f8c8: 122
f8d8: 164
f8e8: 65
f8g8: 151
f8h8: 151
d1c1: 175
d1e1: 151
d1c2: 214
d1d2: 208
d1e2: 186

Then make(...F8F1...) (new FEN: 8/1K2P3/8/8/8/8/8/3k1r2 w - - 2 2)

Code: Select all

DEPTH 0: 12
B7A8: 15
B7B8: 15
B7C8: 15
B7A7: 15
B7C7: 15
B7A6: 15
B7B6: 15
B7C6: 15
E7E8n: 15
E7E8b: 15
E7E8r: 13
E7E8q: 13
DEPTH 2: 176

which matches up with the stockfish output for f8f1

[Ras]

I should clarify that the FEN in perft output is not the position perft is generating moves for, that's just the initial position before I manually started 'making' moves

The point stays the same: why is it 13 and not 11? Your move generator is called genLegalMoves, so it should generate only legal moves. But then there shouldn't be a 13 in the initial position.

[am5083]

I should clarify that the FEN in perft output is not the position perft is generating moves for, that's just the initial position before I manually started 'making' moves

The point stays the same: why is it 13 and not 11? Your move generator is called genLegalMoves, so it should generate only legal moves. But then there shouldn't be a 13 in the initial position.

The correct FEN is [fen]4r3/K3P3/8/8/8/8/8/3k4 b - - 3 2[/fen] which has 13 legal moves

[algerbrex]

I encountered this sort of bug myself when I was first writing my move generator. I wish I could remember better what exactly caused them, but I can't remember the specific fixes. Generally, I found there was an issue with undoing the move in the majority of cases where an issue like this was caused. But also, sometimes the best solution is just to go through your code with a fine-toothed comb and make sure each part is doing exactly what you want it to do to.

Here are some general guidelines to consider. First, do you have too few or too many nodes? If too few, I would start with the move generator and look there to make sure you're generating all of the pseduo-legal/legal moves you should be. If too many, I would check all my code related to move legality first, like computing pinned pieces, checkers, attackers, etc. Also, keep in mind the edge cases that can occur from en-passant or casting. Make sure you're not allowing en-passant-ing into check, or not allowing casting if the rook is captured as well.

For your specific case, I'd start by checking my promotion code, and then checking my code that deals with determining move legality. I'll try to look over your code myself when I get the chance to see if I notice anything.

[am5083]

I encountered this sort of bug myself when I was first writing my move generator. I wish I could remember better what exactly caused them, but I can't remember the specific fixes. Generally, I found there was an issue with undoing the move in the majority of cases where an issue like this was caused. But also, sometimes the best solution is just to go through your code with a fine-toothed comb and make sure each part is doing exactly what you want it to do to.

Here are some general guidelines to consider. First, do you have too few or too many nodes? If too few, I would start with the move generator and look there to make sure you're generating all of the pseduo-legal/legal moves you should be. If too many, I would check all my code related to move legality first, like computing pinned pieces, checkers, attackers, etc. Also, keep in mind the edge cases that can occur from en-passant or casting. Make sure you're not allowing en-passant-ing into check, or not allowing casting if the rook is captured as well.

For your specific case, I'd start by checking my promotion code, and then checking my code that deals with determining move legality. I'll try to look over your code myself when I get the chance to see if I notice anything.

I think the issue is in the unmake function, but either I'm blind or it's a really sneaky bug. I scrapped my old one because it was buggy, but there isn't anything I can see that's wrong with it. I don't think the issue is in legal move generation because making the moves manually and then running perft(n-1) gives the right number of nodes.

One thing I did notice, though, is that this issue (seemingly?) only comes up when the board is mostly empty, so it could have something to do with promotion, but I can't see anything wrong with it. I'll probably spend some time in GDB and see if I can find where it's failing.

Code: Select all

        case P_KNIGHT:
        case P_BISHOP:
        case P_ROOK:
        case P_QUEEN: {
            int pTo = (getCapture(move) - P_KNIGHT) + ((6 * board->turn) + n_wKnight);
            board->color[board->turn] ^= frmMsk ^ toMsk;
            board->pieceBB[fromPc]    ^= frmMsk;
            board->pieceBB[pTo]       ^= toMsk;

            board->board[fromPos] = 0;
            board->board[toPos]   = pTo;
            board->lastCapt = toPc;
        } break;
        case CP_KNIGHT:
        case CP_BISHOP:
        case CP_ROOK:
        case CP_QUEEN: {
            int pTo = (getCapture(move) - CP_KNIGHT) + ((6 * board->turn) + n_wKnight);
            board->color[board->turn] ^= frmMsk ^ toMsk;
            board->pieceBB[fromPc]    ^= frmMsk;
            board->pieceBB[pTo]       ^= toMsk;

            board->color[1^board->turn] ^= toMsk;
            board->pieceBB[toPc] ^= toMsk;

            if (toPc == n_wRook) {
               board->castleStatus &= castleMod[toPos];
            }
            else if (toPc == n_bRook) {
               board->castleStatus &= castleMod[toPos];
            }

            board->board[fromPos] = 0;
            board->board[toPos]   = pTo;
            board->lastCapt = toPc;
        } break;