Devlog 0xA - Perft Testing
Devlog 0xA. Implementing perft testing and trying to debug the results.
Performance Testing
I introduced a small timing utility to measure elapsed time in milliseconds (getTimeMs, Timer struct). This will help track how different areas of code perform, allowing more fine-grained optimization later on. The Timer struct can be started with Timer.start() and then provides:
- elapsed(): Returns the elapsed time since the timer started.
- elapsedAndReset(): Returns the elapsed time and then resets the timer’s start time to now.
Using this, I can measure the performance of various functions, such as generating moves or running perft calculations at different depths. This is especially valuable when diagnosing slowdowns in the move generator or in the validation logic for moves.
Move Generation Accuracy Testing
In addition to performance, I’m now printing detailed breakdowns of move generation to ensure correctness. This includes:
-
debugMoveGeneration()
- Generates all legal moves for the current board state.
- Prints out each move grouped by piece type.
- Displays the from-square, to-square, and the move type (quiet, capture, promotion, etc.).
-
Perft (Performance Test) Implementation
- perftCount(): Recursively counts all possible moves down to a given depth.
- perftDivide(): Provides a more detailed breakdown at the root level. It prints out each move with the number of resulting nodes, plus flags like (capture), (promotion), (castle), etc.
- perftCountDetailed(): Tracks advanced stats (captures, en passant, castles, promotions, checks).
By comparing these perft results against known correct perft values for test positions, I can confirm that the move generation is accurate. Any discrepancies in the node counts at various depths will highlight bugs in the movegen logic. Ensuring that each move is generated correctly (and that illegal moves are not included) is the cornerstone of a robust chess engine.
Debugging
The perft testing revealed that there are atleast a few bugs within my move generation. To be expected as it is a complete refactor with tons of new (to me) data structures and unique-to-Zig features like comptime generics. Here's the result of the kiwiPete FEN discussed earlier in the devlog series: Move d5-d6 (P quiet) generated 41 replies Move d5-e6 (P capture) generated 46 replies Move a2-a3 (P quiet) generated 44 replies Move a2-a4 (P doublePush) generated 44 replies Move b2-b3 (P quiet) generated 42 replies Move g2-g3 (P quiet) generated 42 replies Move g2-g4 (P doublePush) generated 42 replies Move g2-h3 (P capture) generated 43 replies Move e5-d7 (N capture) generated 45 replies Move e5-f7 (N capture) generated 45 replies Move e5-g6 (N capture) generated 43 replies Move e5-c6 (N quiet) generated 42 replies Move e5-c4 (N quiet) generated 42 replies Move e5-g4 (N quiet) generated 44 replies Move e5-d3 (N quiet) generated 43 replies Move c3-b5 (N quiet) generated 39 replies Move c3-a4 (N quiet) generated 42 replies Move c3-b1 (N quiet) generated 42 replies Move c3-d1 (N quiet) generated 42 replies Move d2-h6 (B quiet) generated 41 replies Move d2-g5 (B quiet) generated 42 replies Move d2-f4 (B quiet) generated 43 replies Move d2-e3 (B quiet) generated 43 replies Move d2-c1 (B quiet) generated 43 replies Move e2-a6 (B capture) generated 36 replies Move e2-b5 (B quiet) generated 40 replies Move e2-c4 (B quiet) generated 41 replies Move e2-d3 (B quiet) generated 42 replies Move e2-d1 (B quiet) generated 44 replies Move e2-f1 (B quiet) generated 44 replies Move a1-b1 (R quiet) generated 43 replies Move a1-c1 (R quiet) generated 43 replies Move a1-d1 (R quiet) generated 43 replies Move h1-f1 (R quiet) generated 43 replies Move h1-g1 (R quiet) generated 43 replies Move f3-f6 (Q capture) generated 39 replies Move f3-h3 (Q capture) generated 43 replies Move f3-f5 (Q quiet) generated 45 replies Move f3-h5 (Q quiet) generated 43 replies Move f3-f4 (Q quiet) generated 43 replies Move f3-g4 (Q quiet) generated 43 replies Move f3-d3 (Q quiet) generated 42 replies Move f3-e3 (Q quiet) generated 43 replies Move f3-g3 (Q quiet) generated 43 replies Move e1-d1 (K quiet) generated 43 replies Move e1-f1 (K quiet) generated 43 replies Move e1-g1 (K castle) generated 43 replies Move e1-c1 (K castle) generated 43 replies Perft(2) found 2038 nodes in 3ms
White pawn bitboard: 100000010000000000001110011100000000
Pawn at square 8 has attack mask: 101000000000000000
After masking with opponent pieces: 0
Pawn at square 9 has attack mask: 1000000000000000000
After masking with opponent pieces: 0
Pawn at square 10 has attack mask: 10100000000000000000
After masking with opponent pieces: 0
Pawn at square 13 has attack mask: 10100000000000000000000
After masking with opponent pieces: 0
Pawn at square 14 has attack mask: 1000000000000000000000
After masking with opponent pieces: 0
Pawn at square 15 has attack mask: 1010000000000000000000000
After masking with opponent pieces: 0
Pawn at square 28 has attack mask: 10100000000000000000000000000000000000
After masking with opponent pieces: 0
Pawn at square 35 has attack mask: 101000000000000000000000000000000000000000000
After masking with opponent pieces: 100000000000000000000000000000000000000000000
Debug Move Generation for position:
8 r . . . k . . r
7 p . p p q p b .
6 b n . . p n p .
5 . . . P N . . .
4 . p . . P . . .
3 . . N . . Q . p
2 P P P B B P P P
1 R . . . K . . R
a b c d e f g h
Side: white
En passant: no
Castling: KQkq
Total moves generated: 47
Moves by piece type:
Pawn: a2-a3 (quiet)
Pawn: a2-a4 (double push)
Pawn: b2-b3 (quiet)
Pawn: g2-g3 (quiet)
Pawn: g2-g4 (double push)
Pawn: d5-d6 (quiet)
Pawn: d5-e6 (capture)
Knight: c3-b1 (quiet)
Knight: c3-d1 (quiet)
Knight: c3-a4 (quiet)
Knight: c3-b5 (quiet)
Knight: e5-g6 (capture)
Knight: e5-d7 (capture)
Knight: e5-f7 (capture)
Knight: e5-d3 (quiet)
Knight: e5-c4 (quiet)
Knight: e5-g4 (quiet)
Knight: e5-c6 (quiet)
Bishop: d2-c1 (quiet)
Bishop: d2-e3 (quiet)
Bishop: d2-f4 (quiet)
Bishop: d2-g5 (quiet)
Bishop: d2-h6 (quiet)
Bishop: e2-a6 (capture)
Bishop: e2-d1 (quiet)
Bishop: e2-f1 (quiet)
Bishop: e2-d3 (quiet)
Bishop: e2-c4 (quiet)
Bishop: e2-b5 (quiet)
Rook: a1-b1 (quiet)
Rook: a1-c1 (quiet)
Rook: a1-d1 (quiet)
Rook: h1-f1 (quiet)
Rook: h1-g1 (quiet)
Queen: f3-h3 (capture)
Queen: f3-f6 (capture)
Queen: f3-d3 (quiet)
Queen: f3-e3 (quiet)
Queen: f3-g3 (quiet)
Queen: f3-f4 (quiet)
Queen: f3-g4 (quiet)
Queen: f3-f5 (quiet)
Queen: f3-h5 (quiet)
King: e1-d1 (quiet)
King: e1-f1 (quiet)
King: e1-g1 (castle)
King: e1-c1 (castle)
White pawn bitboard: 100000010000000000001110011100000000
Pawn at square 8 has attack mask: 101000000000000000
After masking with opponent pieces: 0
Pawn at square 9 has attack mask: 1000000000000000000
After masking with opponent pieces: 0
Pawn at square 10 has attack mask: 10100000000000000000
After masking with opponent pieces: 0
Pawn at square 13 has attack mask: 10100000000000000000000
After masking with opponent pieces: 0
Pawn at square 14 has attack mask: 1000000000000000000000
After masking with opponent pieces: 0
Pawn at square 15 has attack mask: 1010000000000000000000000
After masking with opponent pieces: 0
Pawn at square 28 has attack mask: 10100000000000000000000000000000000000
After masking with opponent pieces: 0
Pawn at square 35 has attack mask: 101000000000000000000000000000000000000000000
After masking with opponent pieces: 100000000000000000000000000000000000000000000
Perft(1) found 47 nodes in 1ms
From these results, we can see rather easily one of the issues that's occurring: The pawn on g2 doesn't take h3. Here's my theory:
I think the current perft issue lies in how I'm generating attack masks. In my C implementation, I intentionally don't include the board edges in the attack mask so that we don't get wrapping captures (h2 takes a3) but I don't know that I'm accounting for that when making the attack masks. I think we will need to bitwise & the result with a board that only contains the edge squares, and this should fix the problem.
Development from this point forward is likely to slow down greatly, as I have the most experience and understanding of move generation, but ideas like hashing transposition tables and implementing Alpha-Beta pruning are fairly new to me so they will take more investigation in order to implement.
Attributions
Special thanks to the following people for helping me along this journey:
Thanks a bunch for reading, and I'll see you tomorrow :)