Devlog 0x2 - Magic Bitboards

Devlog 0x2. Today, I implemented magic bitboards for sliding pieces in Zig.

Magic Bitboards

Magic bitboards are a fascinating and highly efficient technique used in chess engines to calculate sliding piece (rooks, bishops, queens) move possibilities. They rely on a combination of precomputed magic numbers and bitwise operations to map board occupancy to valid move masks via a lookup table. The key to their performance lies in the “magic number,” which, when multiplied by the occupancy bitboard and shifted, produces a unique index into the move table for almost every possible occupancy.

The main steps to implement magic bitboards are:

1. Generate magic numbers
2. Create move masks for sliding pieces
3. Precompute and store the attack tables

Generating Magic Numbers

The process of finding a magic number involves generating random numbers and checking if they satisfy the unique-index property for all relevant occupancies. My implementation uses a combination of XORSHIFT32 and a method inspired by Tord Romstad's article on finding magics:

pub fn getRandomNumberU32() u32 {
    var number: u32 = bitboard.state;

    number ^= number << 13;
    number ^= number >> 17;
    number ^= number << 5;

    bitboard.state = number;

    return number;
}

pub fn getRandomNumberU64() u64 {
    const n1: u64 = @as(u64, getRandomNumberU32()) & 0xFFFF;
    const n2: u64 = @as(u64, getRandomNumberU32()) & 0xFFFF;
    const n3: u64 = @as(u64, getRandomNumberU32()) & 0xFFFF;
    const n4: u64 = @as(u64, getRandomNumberU32()) & 0xFFFF;

    return n1 | (n2 << 16) | (n3 << 32) | (n4 << 48);
}

pub fn generateMagicNumber() u64 {
    return getRandomNumberU64() & getRandomNumberU64() & getRandomNumberU64();
}

Attack Masks

Attack masks define the potential moves for sliding pieces on an empty board, excluding edge squares. Here is my implementation for rook attack masks:

pub fn maskRookAttacks(square: u6) u64 {

    const targetRank: i8 = square / 8;
    const targetFile: i8 = square % 8;

    var rank: i8 = targetRank + 1;

    while (rank <= 6) {
        const result: u6 = @intCast(rank * 8 + targetFile);
        attacks |= @as(u64, 1) << result;
        rank += 1;
    }

    rank = targetRank - 1;

    while (rank >= 1) {
        const result: u6 = @intCast(rank * 8 + targetFile);
        attacks |= @as(u64, 1) << result;
        rank -= 1;
    }

    var file: i8 = targetFile + 1;

    while (file <= 6) {
        const result: u6 = @intCast(targetRank * 8 + file);
        attacks |= @as(u64, 1) << result;
        file += 1;
    }

    file = targetFile - 1;

    while (file >= 1) {
        const result: u6 = @intCast(targetRank * 8 + file);
        attacks |= @as(u64, 1) << result;
        file -= 1;
    }

    return attacks;
}

Precomputed Attack Tables

With magic bitboards now implemented for rooks and bishops, my next step was to generate precomputed attack tables for these pieces. This is accomplished with a simple function to generate these attack tables and print them.

fn initMagicNumbers() void {
    std.debug.print("bishop:\n", .{});
    for (0..64) |square| {
        const result: u64 = findMagicNumber(@intCast(square), bitboard.bishopRelevantBits[square], true);
        std.debug.print("0x{x},\n", .{result});
    }
    std.debug.print("rook:\n", .{});
    for (0..64) |square| {
        const result: u64 = findMagicNumber(@intCast(square), bitboard.rookRelevantBits[square], true);
        std.debug.print(" 0x{x},\n", .{result});
    }
}

Next, I simply redirected the output from stderr to a file which I then copied and hard-coded into the program.

zig build
./kirin-chess 2&>kirin.out

Challenges

The primary challenge in generating magic numbers was ensuring that the generated numbers would produce unique indicies for all occupancies. This was achieved through iterative testing and adjustments to the random number generation, Additionally, memory usage optimization for attack tables required careful design.

Thanks for reading, see you tomorrow!