Debugging perft

[Dan]

Hi everyone, I've been working on making my engine have a correct perft, and perft(1) = 20, perft(2) = 400, perft(3) = 8902, but I can't make it through perft(4) without seg.faulting. I split up the perft as per a divide command, and this is the result I get thus far:

Code: Select all

From: b1 (1) To: a3 (16) Flag F.Normal 8886
From: b1 (1) To: c3 (18) Flag F.Normal 9756
From: g1 (6) To: f3 (21) Flag F.Normal 9749
From: g1 (6) To: h3 (23) Flag F.Normal 8881
From: a2 (8) To: a3 (16) Flag F.Normal 8458
From: a2 (8) To: a4 (24) Flag F.Normal 9330
From: b2 (9) To: b3 (17) Flag F.Normal 9346
From: b2 (9) To: b4 (25) Flag F.Normal 9333
Segmentation fault


The lattermost column is the perft count for that particular move, and when examining the numbers most of them are off by (count+1) with respect to qperft. In this case, all are off except 1.g1h3. The seg. fault also doesn't necessarily occur at the same iteration through the data, so I guess I'm reaching unmapped territory.

What would be the most common error that I could have made?

[Ron Murawski]

What would be the most common error that I could have made?

An uninitialized local variable or writing beyond the bounds of an array are very common errors. Run your code through a debugger and set up break points. Keep at it and you will soon zero in on your bug(s).

[crystalclear]

Problems that go away as you zoom in on them
I think I've had some perft problems in the past that went away as I tried to home in on the problem.

I think it was due to a problem in undoing a move so you had to back-up in order to reproduce the problem.
When you got in close, the software was no longer backing up far enough to reproduce the problem.
If you suspect a problem in doing or undoing a move, you can check that you have matching lines on code in the doing and undoing.
Sort them into some sort of order and verify that undo does the same basic steps in reverse order.

Problems that cause an incorrect perft count
Yep, I've had these too. I had tests to see if a move left me in check and if it does, it isn't a legal move.
To speed things up, I verified simply that the moving piece wasn't pinned. That was wrong, it might be pinned, move and stayed pinned.
Then I decided to verify if the direction it moved was the same as the direction of the piece to the king.
The count being too high or too low is an indication of what might be wrong.
If there is a crash, you might simply get an incorrect count at a lower depth.
I downloaded a copy of another chess engine SHARPER that does perft, to verify my own perft counts.
Then I edit somthing into SHARPER.INI, e.g.

Code: Select all

setboard 2k5/7R/8/3N1K2/P3N3/P7/P7/8 b - - 4 11
divide 1
divide 2
divide 3
quit


Problems that cause a crash
I found that this sort of thing happens when the move generator generates a completely invalid move.
Let's say that a move leaves the king in check. Then another move comes along and captures the king: removes it from the board.
And then another move generation tries to verify if there is a check, and there isn't even a king anywhere.
SPLAT! Things like that happen, depending of course on the structure of the program, how checks are stored and where they are tested.

I proposed on here once to have a fairly good perft test set.
I believed that specific tests can be useful. A contrary opinion was that that there is no substitute for search depth.
I still believe that certain areas of move generation are problematic and that themed tests can help expose where a problem lies.
Castling rights
Not moving into check.
Not revealing a check by moving a pinned piece.
En passant.
Promotion
Pawn colour,
Etc.

I now have a collection of EPD files that I can use to test a new version of my software,
mate tests, best move test, tablebase tests, graph history interaction tests, perft tests, Zobrist hash code tests, etc.
The perft tests are organised by number of nodes.

Code: Select all

 Volume in drive C has no label.
 Volume Serial Number is E021-C1C0

 Directory of C:\Users\me\epd\bin\Debug\tests\perft

24/04/2012  17:20    <DIR>          .
24/04/2012  17:20    <DIR>          ..
21/04/2012  21:22             1,880 perft.epd
21/04/2012  21:12               261 perft_100k.epd
05/12/2011  12:49                93 perft_100mega.epd
14/12/2011  15:44               307 perft_10mega.epd
05/12/2011  12:47                94 perft_giga.epd
14/12/2011  15:52               247 perft_mega.epd


Here's the small file (perft.epd), warts and all.

Code: Select all

4B3/2p1kppr/3p4/2p2b1p/1pP1qPnP/1PN3P1/3K4/B3Q1R1 w - - Perft 759;
4k3/8/8/8/8/8/8/r3K3 w - - c0 "king in check"; Perft 37147;
K3k3/8/8/8/8/4pb2/4P3/8 w - - c0 "Pawn capture only evasion"; Perft 94990;
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - c0 "StartPos"; Perft 8902;
rnbqkbnr/ppp1pppp/8/3P4/8/8/PP1PPPPP/RNBQKBNR b KQkq - c0 "King Movement"; Perft 28;
rnbqkbnr/1ppppppp/8/p7/8/N7/PPPPPPPP/R1BQKBNR w KQkq a6 c0 "pawn on a5 should not pin d2 like a bishop would"; Perft 20;
r2Nk2r/pPp3P1/8/bP4B1/1p5b/6P1/PpP3p1/R3K2R b KQkq - c0 "pawns cannot promote into occupied squares"; Perft 966;
7Q/4k1r1/7P/p7/P7/5p2/4K3/8 w - - c0 "King moves in all 8 directions"; c1 "including capture"; Perft 25884;
8/5rRP/p3kp2/8/8/P7/7P/5K2 w - - c0 "Rook and pawn close to promotion"; Perft 6592;
8/5rRP/p3kp2/8/8/P7/7P/5K2 w - - c0 "Rook and pawn close to promotion"; Perft 101117;
8/5rRP/p3kp2/8/8/P7/6KP/8 b - - Perft 97688;
5rR1/7P/p3kp2/8/8/P7/6KP/8 b - - Perft 16;
5rR1/7P/p3kp2/8/8/P7/6KP/8 b - - Perft 344;
8/6R1/3N4/6k1/1p6/1PP2p2/5P1K/8 b - - Perft 10352;
8/8/3N4/8/1p3k2/1PP2p2/5PRK/8 b - - Perft 54;
R2b4/1pP2rk1/pK5p/1N2p2P/1P2P3/P7/8/8 w - - Perft 18; c0 "queening a pinned pawn with capture is possible when capturing the pinning piece";
r4rk1/6p1/4p2p/pB1bPp1P/P4KP1/1PR5/2R5/8 w - f6 Perft 32; c0 "exf6/ep";
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - - Perft 16;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - a3 Perft 17;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - b6 Perft 18;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - c3 Perft 18;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - d6 Perft 18;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - e3 Perft 18;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - f6 Perft 18;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - g3 Perft 18;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - h6 Perft 17;
8/p2R4/5k2/n1b1r3/2p1pPP1/2P4P/r1P3K1/4NR2 b - f3 c0 "does ep capture reveal a check?"; Perft 30;


If it were really for public distribution, I should tidy it up.
The last few tests are en passant tests.
I don't remember really, but I had planned to have test for castling rights, tests for pawn promotion, test for en passant etc, and with little overlap in some of the tests, so that the failing test would indicate where to look.

Perseverance!

[crystalclear]

It seems I had a problem with my own move generator. The problem manifested itself as inability to read a move from a game in a PGN file.
So I just added a test case in my file and edited the list above.
Sometimes, capturing en passant would reveal a check on your own king and so the move isn't allowed. For that to happen there needs to be an enemy slider lined up behind the pawn that moved two squares, on the opposite side to your king. In this case, there is a slider lined up just like that, but the en passant is still okay because the capturing pawn then blocks the check.

I had considered this, coded for it, and even correctly implemented it. But I'd tested it for white performing en passant and somehow didn't get round to putting the same code in there for black. Most people wouldn't need to, but my chess program has seven piece types rather than the more usual 6. Every piece that moves differently is a different piece type for me, and so white knights and black knights are the same piece type, but white pawns and black pawns, moving in opposite directions are different.

8/p2R4/5k2/n1b1r3/2p1pPP1/2P4P/r1P3K1/4NR2 b - f3 c0 "does ep capture reveal a check?"; Perft 30;