Verification with Perft

Perft is a well known reliable way to know if your move generator is correct. It counts the total number of leaf nodes reachable from a given position at a given depth. The counts are well-known for standard positions and have been verified by dozens of independent engines over decades.

The implementation is a simple recursive function: at depth 0, return 1. Otherwise generate all legal moves, make each on a copy, recurse, and accumulate.

long long perft(Board& board, int depth){
    if (depth == 0) return 1;
    MoveGen gen(board);
    auto moves = gen.generateMoves();
    long long total = 0;
    for (const Move& m : moves){
        Board next = board;
        next.makeMove(m);
        total += perft(next, depth - 1);
    }
    return total;
}

The standard starting position results are (taken from the chess programming wiki):

Depth	Nodes
1	20
2	400
3	8,902
4	197,281
5	4,865,609
6	119,060,324

When a count is wrong, the standard debugging technique is "divide perft": print the count for each root move separately, compare against a known-good engine like Stockfish (which supports the perft command), and narrow down which move is generating the wrong number of nodes.