Devlog 0xC - Continued Movegen Debugging Part 2
Today, I worked on debugging movegen further. Significant progress was made, correctly removing moves that put the king in check before we add them to the move list and therefore reducing the number of invalid nodes being created by ~300.
Perft & Movegen Debugging Continued
To begin, I'm using the Perft Results page from the Chess Programming Wiki. This page contains a variety of known chess positions and their expected move generation output.
Recall that previously, we were testing the Kiwi Pete test position by Peter McKenzie. After successfully getting 48 nodes for depth 1, we moved onto depth two where we are now expecting 2039 nodes. When running Kirin in it's current state, here's what we're actually getting:
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
Upon further digging, I've been able to see that the number of capture moves being generated is incorrect. For the position kiwiPete, we expect to see 351 capture moves but we only are generating 350.
Let's dig even deeper. Having the number of captures is great, but if we take it a step further we can have the perft testing print the number of moves of each type. Here's the code:
fn perftCountInternal(self: *Perft, depth: u32, targetDepth: u32) u64 {
if (depth == 0) return 1;
var nodes: u64 = 0;
var moves = movegen.MoveList.init();
var stats = PerftResult{};
self.generateAllMoves(&moves);
for (moves.getMoves()) |move| {
const saved_board = self.board.*;
var is_legal: u1 = 1;
self.board.makeMove(move, self.attackTable) catch {
self.board.* = saved_board;
is_legal = 0;
};
if (is_legal == 1) {
// Collect stats when we're one move away from target depth
if (depth == targetDepth - 1) {
var reply_moves = movegen.MoveList.init();
self.generateAllMoves(&reply_moves);
for (reply_moves.getMoves()) |reply| {
switch (reply.moveType) {
.capture => stats.captures += 1,
.castle => stats.castles += 1,
.promotion, .promotionCapture => stats.promotions += 1,
.enpassant => stats.en_passants += 1,
else => {},
}
}
const fromCoords = move.from.toCoordinates() catch continue;
const toCoords = move.to.toCoordinates() catch continue;
std.debug.print("Move {c}{c}-{c}{c} ({s} {s}) generated {d} replies\n", .{
fromCoords[0], fromCoords[1],
toCoords[0], toCoords[1],
@tagName(move.piece), @tagName(move.moveType),
reply_moves.count,
});
}
const subnodes = self.perftCountInternal(depth - 1, targetDepth);
nodes += subnodes;
}
self.board.* = saved_board;
}
if (depth == targetDepth - 1) {
std.debug.print("\nTotal for depth {d}:\n", .{targetDepth});
std.debug.print("Captures: {d}\n", .{stats.captures});
std.debug.print("En passants: {d}\n", .{stats.en_passants});
std.debug.print("Castles: {d}\n", .{stats.castles});
std.debug.print("Promotions: {d}\n", .{stats.promotions});
std.debug.print("Checks: {d}\n", .{stats.checks});
std.debug.print("Total nodes: {d}\n", .{nodes});
}
return nodes;
}
pub fn perftCount(self: *Perft, depth: u32) u64 {
return self.perftCountInternal(depth, depth + 1);
}
And here's the debug output:
Total for depth 2:
Captures: 350
En passants: 1
Castles: 90
Promotions: 0
Checks: 0
Total nodes: 2038
Perft(2) found 2038 nodes in 2ms
Now we can see that the issue is actually the number of castles being generated. We're currently one short. This is a strange bug, and means that we're being too restrictive on what castling moves can be generated. But the number of captures is also off by 1, and because a castling move can never be a capture, this suggests we have something deeper that's causing issues. If we correct the number of captures, we'd have the correct number of moves generated but the wrong number of castling moves, and if we add the missing castling move as well then we will be at 2040 nodes, one over the desired result. As the man I learned chess programming from often says, "something has gone horribly wrong".
Each day we make a bunch of progress toward a functional move generator. Once we pass perft testing, the plan is to begin working on evaluation of positions and use the results of the evaluation to make moves. But for now, more debugging. Thanks for reading, and I'll see you tomorrow :)