voroskoi/pistike - Change TDHJSFFSJZBEZFMDHPLRSVB6CIVJ7AWGGNIC3WUCADQLQSIQKXDAC

Add magic number generator

Created by voroskoi on January 2, 2023

TDHJSFFSJZBEZFMDHPLRSVB6CIVJ7AWGGNIC3WUCADQLQSIQKXDAC

Dependencies

In channels

main

Change contents

Insertion in src/attacks.zig at line 275 [3.204]

[3.7465]

}
fn setOccupancy(index: usize, bits_in_mask: Chess.BoardType, attack_mask: Chess.BoardType) Chess.BoardType {
    var occupancy: Chess.BitBoard = .{};
    var attack: Chess.BitBoard = .{ .board = attack_mask };
    var count: u6 = 0;
    while (count < bits_in_mask) : (count += 1) {
        const square = @ctz(attack.board);
        attack.pop(@intToEnum(Chess.Square, square));
        if (index & @as(Chess.BoardType, 1) << count != 0) {
            occupancy.set(@intToEnum(Chess.Square, square));
        }
    }
    return occupancy.board;
}
test "occupancy bits" {
    const attack_mask = genSteps(.a1, .rook, .white);
    var occupancy: Chess.BitBoard = .{};
    occupancy.board = setOccupancy(4095, @popCount(attack_mask), attack_mask);
    var expected: Chess.BitBoard = .{};
    expected.setSlice(&[_]Chess.Square{ .a2, .a3, .a4, .a5, .a6, .a7, .b1, .c1, .d1, .e1, .f1, .g1 });
    try std.testing.expectEqual(expected, occupancy);
}
fn genRelevantOccupancy(piece: Chess.Pieces) [@typeInfo(Chess.Square).Enum.fields.len]u4 {
    var ret: [64]u4 = [_]u4{0} ** 64;
    for (std.enums.values(Chess.Square)) |square| {
        const count = @popCount(genSteps(square, piece, .white));
        ret[@enumToInt(square)] = @intCast(u4, count);
    }
    return ret;
}
test "genRelevantOccupancy" {
    { // bishop
        const bishop = genRelevantOccupancy(.bishop);
        // zig fmt: off
        const expected = [64]u4{
            6, 5, 5, 5, 5, 5, 5, 6,
            5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 7, 7, 7, 7, 5, 5,
            5, 5, 7, 9, 9, 7, 5, 5,
            5, 5, 7, 9, 9, 7, 5, 5,
            5, 5, 7, 7, 7, 7, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 5,
            6, 5, 5, 5, 5, 5, 5, 6,
        };
        // zig fmt: on
        try std.testing.expectEqualSlices(u4, &expected, &bishop);
    }
    { // rook
        const rook = genRelevantOccupancy(.rook);
        // zig fmt: off
        const expected = [64]u4{
            12, 11, 11, 11, 11, 11, 11, 12,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            12, 11, 11, 11, 11, 11, 11, 12,
        };
        // zig fmt: on
        try std.testing.expectEqualSlices(u4, &expected, &rook);
    }

Insertion in src/attacks.zig at line 358 [3.204]

[3.7467]


fn findMagicNumber(square: Chess.Square, relevant: u4, piece: Chess.Pieces) Chess.BoardType {
    // TODO: piece+square defines the relevant bits
    // TODO: this is for rooks, bishop needs less
    var occupancies: [4096]Chess.BoardType = undefined;
    var attacks: [4096]Chess.BoardType = undefined;
    var used: [4096]Chess.BoardType = undefined;
    // attack mask for a current piece
    const attack_mask = genSteps(square, piece, .white);
    const occupancy_idx = @as(Chess.BoardType, 1) << relevant;
    var bb = Chess.BitBoard{};
    var idx: usize = 0;
    while (idx < occupancy_idx) : (idx += 1) {
        occupancies[idx] = setOccupancy(idx, relevant, attack_mask);
        bb.board = occupancies[idx]; // FIXME UGLY
        attacks[idx] = bb.riderBlocker(square, piece);
    }
    // test the generated number
    var loop: usize = 0;
    while (loop < 100_000_000) : (loop += 1) {
        const magic = randLowZero();
        // skip inappropriate numbers FIXME: ugly
        var tmp1: Chess.BoardType = undefined;
        _ = @mulWithOverflow(Chess.BoardType, attack_mask, magic, &tmp1);
        if (@popCount(tmp1 & 0xFF00000000000000) < 6) continue;
        used = [_]Chess.BoardType{0} ** 4096;
        var index: usize = 0;
        var fail: bool = false;
        while (!fail and index < occupancy_idx) : (index += 1) {
            var tmp2: Chess.BoardType = undefined; // FIXME: ugly
            _ = @mulWithOverflow(Chess.BoardType, occupancies[index], magic, &tmp2);
            var magic_index: usize = @intCast(usize, tmp2 >> @intCast(u6, @as(u7, 64) - relevant));
            if (used[magic_index] == 0) {
                // magic index works
                used[magic_index] = attacks[index];
            } else if (used[magic_index] != attacks[index]) {
                // magic index does not work
                fail = true;
            }
        }
        if (!fail) {
            return magic;
        }
    }
    unreachable;
}
fn randLowZero() u64 {
    return rand() & rand() & rand();
}
var random_state: u32 = 1804289383;
fn rand32() u32 {
    var number = random_state;
    // XOR shift algorithm
    number ^= number << 13;
    number ^= number >> 17;
    number ^= number << 5;
    // update random number state
    random_state = number;
    // return random number
    return number;
}
fn rand() u64 {
    const r1 = @intCast(u64, rand32()) & 0xFFFF;
    const r2 = @intCast(u64, rand32()) & 0xFFFF;
    const r3 = @intCast(u64, rand32()) & 0xFFFF;
    const r4 = @intCast(u64, rand32()) & 0xFFFF;
    return r1 | (r2 << 16) | (r3 << 32) | (r4 << 48);
}
test "MagicNumbers" {
    var bishop_magic: [64]Chess.BoardType = undefined;
    var rook_magic: [64]Chess.BoardType = undefined;
    for (std.enums.values(Chess.Square)) |square, idx| {
        bishop_magic[idx] = findMagicNumber(
            square,
            genRelevantOccupancy(.bishop)[square.int()],
            .bishop,
        );
        rook_magic[idx] = findMagicNumber(
            square,
            genRelevantOccupancy(.rook)[square.int()],
            .rook,
        );
    }
    // std.debug.print("{any}\n{any}\n", .{ bishop_magic, rook_magic });
}

Replacement in src/Chess.zig at line 149 [3.7502]

B:BD[4.685] → [4.685:737]

            while (step < SIZE - 1) : (step += 1) {

[4.685]

[4.737]

            while (step < SIZE) : (step += 1) {

Insertion in src/Chess.zig at line 163 [3.7502]

[4.1191]

                // stop when we hit a blocker

Deletion in src/Chess.zig at line 252 [3.7502]

∅:D[4.1949] → [3.12112:12120]

B:BD[3.12112] → [3.12112:12120]

B:BD[3.12120] → [5.142:998]

B:BD[5.998] → [2.209:1071]

    }
}
fn setOccupancy(index: usize, attack_mask: BoardType) BoardType {
    var occupancy: BitBoard = .{};
    var attack: BitBoard = .{ .board = attack_mask };
    var count: u6 = 0;
    while (count < @popCount(attack_mask)) : (count += 1) {
        const square = @ctz(attack.board);
        attack.pop(@intToEnum(Square, square));
        if (index & @as(BoardType, 1) << count != 0) {
            occupancy.set(@intToEnum(Square, square));
        }
    }
    return occupancy.board;
}
test "occupancy bits" {
    const attack_mask = Attacks.genSteps(.a1, .rook, .white);
    var occupancy: BitBoard = .{};
    occupancy.board = setOccupancy(4095, attack_mask);
    var expected: BitBoard = .{};
    expected.setSlice(&[_]Square{ .a2, .a3, .a4, .a5, .a6, .a7, .b1, .c1, .d1, .e1, .f1, .g1 });
    try std.testing.expectEqual(expected, occupancy);
}
fn genRelevantOccupancy(piece: Pieces) [@typeInfo(Square).Enum.fields.len]BoardType {
    var ret: [64]BoardType = [_]BoardType{0} ** 64;
    for (std.enums.values(Square)) |square| {
        ret[@enumToInt(square)] = @popCount(Attacks.genSteps(square, piece, .white));
    }
    return ret;
}
test "genRelevantOccupancy" {
    { // bishop
        const bishop = genRelevantOccupancy(.bishop);
        // zig fmt: off
        const expected = [64]BoardType{
            6, 5, 5, 5, 5, 5, 5, 6,
            5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 7, 7, 7, 7, 5, 5,
            5, 5, 7, 9, 9, 7, 5, 5,
            5, 5, 7, 9, 9, 7, 5, 5,
            5, 5, 7, 7, 7, 7, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 5,
            6, 5, 5, 5, 5, 5, 5, 6,
        };
        // zig fmt: on
        try std.testing.expectEqualSlices(BoardType, &expected, &bishop);

Replacement in src/Chess.zig at line 255 [3.7502]

B:BD[2.1092] → [2.1092:1142]

        const rook = genRelevantOccupancy(.rook);

[2.1092]

[2.1142]

        bb.board = 0;
        bb.setSlice(&[_]Square{.b8});
        const got = bb.riderBlocker(.h8, .rook);

Replacement in src/Chess.zig at line 260 [3.7502]

B:BD[2.1143] → [2.1143:1593]

        // zig fmt: off
        const expected = [64]BoardType{
            12, 11, 11, 11, 11, 11, 11, 12,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            11, 10, 10, 10, 10, 10, 10, 11,
            12, 11, 11, 11, 11, 11, 11, 12,
        };
        // zig fmt: on

[2.1143]

[2.1593]

        bb.board = 0;
        bb.setSlice(&[_]Square{ .b8, .c8, .d8, .e8, .f8, .g8, .h7, .h6, .h5, .h4, .h3, .h2, .h1 });

Replacement in src/Chess.zig at line 263 [3.7502]

B:BD[2.1594] → [2.1594:1666]

        try std.testing.expectEqualSlices(BoardType, &expected, &rook);

[2.1594]

[2.1666]

        try std.testing.expectEqual(bb.board, got);