Devlog 0xD - Pseudo Legal Move Generation with Immediate Legality Testing

Today, I modified my approach to move generation to be more inline with engines like Stockfish and Crafty. This new approach is called Pseudo Legal Move Generation with Immediate Legality Testing. This approach first generates pseudo-legal moves and then tests them for legality by checking to see if the king is left in check.

Why the switch?

My new approach to move generation, which is known as "pseudo-legal move generation with immediate legality testing", is a big upgrade from the way I was previously occupying the move list. Previously, my approach was to generate all possible moves into a move list, and then check this move list for legality. My new implementation uses two helper functions, isMoveLegal and addLegalMove, which run during move generation for a given piece. This means that invalid moves aren't stored in the move list should be significantly faster than what I was doing previously.

New Implementation

These are the helper functions that do what makeMove was doing inline previously:

pub fn isMoveLegal(board: *bitboard.Board, move: Move, attackTable: *const atk.Attac    kTable) bool {
    // Save the current board state
    const savedBoard = board.*;
    var isLegal = false;

    // Attempt to make the move
    board.makeMove(move) catch {
        // Restore board and return false if move is invalid
        board.* = savedBoard;
        return false;
    };

    // Find our king
    const kingBB = if (savedBoard.sideToMove == .white)
        board.bitboard[@intFromEnum(bitboard.Piece.K)]
    else
        board.bitboard[@intFromEnum(bitboard.Piece.k)];
    const kingSquare = @as(u6, @intCast(utils.getLSBindex(kingBB)));

    // Check if the king is not attacked after the move
    isLegal = !atk.isSquareAttacked(kingSquare, savedBoard.sideToMove, board, attack    Table);

    // Restore the board
    board.* = savedBoard;

    return isLegal;
}

// Modified move generation callback wrapper
pub fn addLegalMove(
    context: anytype,
    board: *bitboard.Board,
    attackTable: *const atk.AttackTable,
    move: Move,
    callback: fn (@TypeOf(context), Move) void,
) void {
    if (isMoveLegal(board, move, attackTable)) {
        callback(context, move);
    }
}

Essentially, if the move we made puts our king in check, we restore the board state to before the move was made.

And here's how the generateAttacks functions have been updated. For brevity, we'll just look at move generation for the knights, but they all function in a similar way.

pub fn generateKnightMoves(
    board: *bitboard.Board,
    attackTable: *const atk.AttackTable,
    context: anytype,
    callback: fn (@TypeOf(context), Move) void,
) void {
    const side = board.sideToMove;
    const opponentPieces = board.occupancy[@intFromEnum(side.opposite())];

    // Get knights bitboard for current side
    const knightsBB = if (side == .white)
        board.bitboard[@intFromEnum(bitboard.Piece.N)]
    else
        board.bitboard[@intFromEnum(bitboard.Piece.n)];

    var bbCopy = knightsBB;
    while (bbCopy != 0) {
        const from = utils.getLSBindex(bbCopy);
        if (from < 0) break;
        const fromSquare = @as(u6, @intCast(from));

        // Get all possible moves for this knight
        const moves = attackTable.knight[fromSquare];

        // Split into captures and quiet moves
        const captures = moves & opponentPieces;
        const quietMoves = moves & ~board.occupancy[2]; // All empty squares

        // Process captures
        var capturesBB = captures;
        while (capturesBB != 0) {
            const to = utils.getLSBindex(capturesBB);
            if (to < 0) break;
            const toSquare = @as(u6, @intCast(to));
            addLegalMove(context, board, attackTable, .{
                .from = @as(bitboard.Square, @enumFromInt(fromSquare)),
                .to = @as(bitboard.Square, @enumFromInt(toSquare)),
                .piece = if (side == .white) .N else .n,
                .moveType = .capture,
            }, callback);

            capturesBB &= capturesBB - 1;
        }

        // Process quiet moves
        var quietBB = quietMoves;
        while (quietBB != 0) {
            const to = utils.getLSBindex(quietBB);
            if (to < 0) break;
            const toSquare = @as(u6, @intCast(to));
            addLegalMove(context, board, attackTable, .{
                .from = @as(bitboard.Square, @enumFromInt(fromSquare)),
                .to = @as(bitboard.Square, @enumFromInt(toSquare)),
                .piece = if (side == .white) .N else .n,
                .moveType = .quiet,
            }, callback);
            quietBB &= quietBB - 1;
        }

        bbCopy &= bbCopy - 1;
    }
}

Using this method, we eliminate redundancy in the codebase and likely increase runtime performance significantly. Unfortunately, we aren't able to properly test performance as a metric because our Perft Test results are still inaccurate.

Hopefully today I will have some time to debug perft testing and I will update you with my findings! :)