Hi,
I have a simple zig file for generating chess moves. I have pasted it below, but it is not that interesting.
const std = @import("std");
pub fn main() !void {
const attacks = Attacks{};
_ = attacks;
}
const chess = struct {
const Piece = enum { P, N, B, R, Q, K, p, n, b, r, q, k, none };
pub const Color = enum(u1) { white, black };
const Square = enum(u6) {
// zig fmt: off
a8, b8, c8, d8, e8, f8, g8, h8,
a7, b7, c7, d7, e7, f7, g7, h7,
a6, b6, c6, d6, e6, f6, g6, h6,
a5, b5, c5, d5, e5, f5, g5, h5,
a4, b4, c4, d4, e4, f4, g4, h4,
a3, b3, c3, d3, e3, f3, g3, h3,
a2, b2, c2, d2, e2, f2, g2, h2,
a1, b1, c1, d1, e1, f1, g1, h1,
// zig fmt: on
};
};
const Attacks = struct {
// leaper pieces
pawn_attacks: [2][64]u64 = genPawnAttacks(),
king_attacks: [64]u64 = genKingAttacks(),
knight_attacks: [64]u64 = genKnightAttacks(),
bishop_masks: [64]u64 = genBishopMasks(),
rook_masks: [64]u64 = genRookMasks(),
bishop_attacks: [64][512]u64 = genBishopAttacks(),
rook_attacks: [64][4096]u64 = genRookAttacks(),
// rider pieces
const bishop_magic: [64]u64 = .{
0x0002020202020200, 0x0002020202020000, 0x0004010202000000, 0x0004040080000000,
0x0001104000000000, 0x0000821040000000, 0x0000410410400000, 0x0000104104104000,
0x0000040404040400, 0x0000020202020200, 0x0000040102020000, 0x0000040400800000,
0x0000011040000000, 0x0000008210400000, 0x0000004104104000, 0x0000002082082000,
0x0004000808080800, 0x0002000404040400, 0x0001000202020200, 0x0000800802004000,
0x0000800400A00000, 0x0000200100884000, 0x0000400082082000, 0x0000200041041000,
0x0002080010101000, 0x0001040008080800, 0x0000208004010400, 0x0000404004010200,
0x0000840000802000, 0x0000404002011000, 0x0000808001041000, 0x0000404000820800,
0x0001041000202000, 0x0000820800101000, 0x0000104400080800, 0x0000020080080080,
0x0000404040040100, 0x0000808100020100, 0x0001010100020800, 0x0000808080010400,
0x0000820820004000, 0x0000410410002000, 0x0000082088001000, 0x0000002011000800,
0x0000080100400400, 0x0001010101000200, 0x0002020202000400, 0x0001010101000200,
0x0000410410400000, 0x0000208208200000, 0x0000002084100000, 0x0000000020880000,
0x0000001002020000, 0x0000040408020000, 0x0004040404040000, 0x0002020202020000,
0x0000104104104000, 0x0000002082082000, 0x0000000020841000, 0x0000000000208800,
0x0000000010020200, 0x0000000404080200, 0x0000040404040400, 0x0002020202020200,
};
const rook_magic: [64]u64 = .{
0x0080001020400080, 0x0040001000200040, 0x0080081000200080, 0x0080040800100080,
0x0080020400080080, 0x0080010200040080, 0x0080008001000200, 0x0080002040800100,
0x0000800020400080, 0x0000400020005000, 0x0000801000200080, 0x0000800800100080,
0x0000800400080080, 0x0000800200040080, 0x0000800100020080, 0x0000800040800100,
0x0000208000400080, 0x0000404000201000, 0x0000808010002000, 0x0000808008001000,
0x0000808004000800, 0x0000808002000400, 0x0000010100020004, 0x0000020000408104,
0x0000208080004000, 0x0000200040005000, 0x0000100080200080, 0x0000080080100080,
0x0000040080080080, 0x0000020080040080, 0x0000010080800200, 0x0000800080004100,
0x0000204000800080, 0x0000200040401000, 0x0000100080802000, 0x0000080080801000,
0x0000040080800800, 0x0000020080800400, 0x0000020001010004, 0x0000800040800100,
0x0000204000808000, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080,
0x0000040008008080, 0x0000020004008080, 0x0000010002008080, 0x0000004081020004,
0x0000204000800080, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080,
0x0000040008008080, 0x0000020004008080, 0x0000800100020080, 0x0000800041000080,
0x00FFFCDDFCED714A, 0x007FFCDDFCED714A, 0x003FFFCDFFD88096, 0x0000040810002101,
0x0001000204080011, 0x0001000204000801, 0x0001000082000401, 0x0001FFFAABFAD1A2,
};
const bishop_relevant_bits = genRelevantOccupancy(.B);
const rook_relevant_bits = genRelevantOccupancy(.R);
fn genBishopAttacks() [64][512]u64 {
var ret: [64][512]u64 = undefined;
for (std.enums.values(chess.Square)) |square| {
const square_int = @enumToInt(square);
const attack_mask = genSteps(square, .B);
// init relevant occupancy bit count
const relevant_bits = @popCount(attack_mask);
const occupancy_idx = @as(u64, 1) << @intCast(u6, relevant_bits);
var idx: usize = 0;
while (idx < occupancy_idx) : (idx += 1) {
const occupancy = setOccupancy(idx, relevant_bits, attack_mask);
const res = @mulWithOverflow(occupancy, bishop_magic[square_int])[0];
const magic_index = res >>
@intCast(u6, @as(u7, 64) - bishop_relevant_bits[square_int]);
ret[square_int][magic_index] =
attackWithBlocker(occupancy, square, .B);
}
}
return ret;
}
fn genRookAttacks() [64][4096]u64 {
var ret: [64][4096]u64 = undefined;
for (std.enums.values(chess.Square)) |square| {
const square_int = @enumToInt(square);
const attack_mask = genSteps(square, .R);
// init relevant occupancy bit count
const relevant_bits = @popCount(attack_mask);
const occupancy_idx = @as(u64, 1) << @intCast(u6, relevant_bits);
var idx: usize = 0;
while (idx < occupancy_idx) : (idx += 1) {
const occupancy = setOccupancy(idx, relevant_bits, attack_mask);
const res = @mulWithOverflow(occupancy, rook_magic[@enumToInt(square)])[0];
const magic_index = res >>
@intCast(u6, @as(u7, 64) - rook_relevant_bits[square_int]);
ret[square_int][magic_index] =
attackWithBlocker(occupancy, square, .R);
}
}
return ret;
}
pub fn getBishopAttacks(self: *const @This(), square: u6, occupancy: u64) u64 {
var mut_occupancy = occupancy;
mut_occupancy &= self.bishop_masks[square];
mut_occupancy = @mulWithOverflow(mut_occupancy, bishop_magic[square])[0];
mut_occupancy >>= @intCast(u6, @as(u7, 64) - bishop_relevant_bits[square]);
return self.bishop_attacks[square][mut_occupancy];
}
pub fn getRookAttacks(self: *const @This(), square: u6, occupancy: u64) u64 {
var mut_occupancy = occupancy;
mut_occupancy &= self.rook_masks[square];
mut_occupancy = @mulWithOverflow(mut_occupancy, rook_magic[square])[0];
mut_occupancy >>= @intCast(u6, @as(u7, 64) - rook_relevant_bits[square]);
return self.rook_attacks[square][mut_occupancy];
}
pub fn getQueenAttacks(self: *const @This(), square: u6, occupancy: u64) u64 {
return getBishopAttacks(self, square, occupancy) |
getRookAttacks(self, square, occupancy);
}
pub fn rookXray(self: *const @This(), square: u6, occupancy: u64) u64 {
const attacks = self.getRookAttacks(square, occupancy);
return attacks ^ self.getRookAttacks(square, occupancy ^ (attacks & occupancy));
}
pub fn bishopXray(self: *const @This(), square: u6, occupancy: u64) u64 {
const attacks = self.getBishopAttacks(square, occupancy);
return attacks ^ self.getBishopAttacks(square, occupancy ^ (attacks & occupancy));
}
};
fn genPawnAttacks() [@typeInfo(chess.Color).Enum.fields.len][@typeInfo(chess.Square).Enum.fields.len]u64 {
var ret: [2][64]u64 = [_][64]u64{[_]u64{0} ** 64} ** 2;
for (std.enums.values(chess.Square)) |square| {
ret[@enumToInt(chess.Color.white)][@enumToInt(square)] = genSteps(square, .P);
ret[@enumToInt(chess.Color.black)][@enumToInt(square)] = genSteps(square, .p);
}
return ret;
}
fn genKnightAttacks() [@typeInfo(chess.Square).Enum.fields.len]u64 {
var ret: [64]u64 = [_]u64{0} ** 64;
for (std.enums.values(chess.Square)) |square| {
ret[@enumToInt(square)] = genSteps(square, .N);
}
return ret;
}
fn genKingAttacks() [@typeInfo(chess.Square).Enum.fields.len]u64 {
var ret: [64]u64 = [_]u64{0} ** 64;
for (std.enums.values(chess.Square)) |square| {
ret[@enumToInt(square)] = genSteps(square, .K);
}
return ret;
}
fn genBishopMasks() [@typeInfo(chess.Square).Enum.fields.len]u64 {
var ret: [64]u64 = [_]u64{0} ** 64;
for (std.enums.values(chess.Square)) |square| {
ret[@enumToInt(square)] = genSteps(square, .B);
}
return ret;
}
fn genRookMasks() [@typeInfo(chess.Square).Enum.fields.len]u64 {
var ret: [64]u64 = [_]u64{0} ** 64;
for (std.enums.values(chess.Square)) |square| {
ret[@enumToInt(square)] = genSteps(square, .R);
}
return ret;
}
fn genSteps(square: chess.Square, piece: chess.Piece) u64 {
const rank = @intCast(isize, @enumToInt(square) / 8);
const file = @intCast(isize, @enumToInt(square) % 8);
const rider = switch (piece) {
.P, .p => false,
.N, .n => false,
.B, .b => true,
.R, .r => true,
.K, .k => false,
.Q, .q, .none => @panic("unexpected piece"),
};
// TODO: I repeat some moves here to make zig happy, but ugly.
const moves = switch (piece) {
.P => [_][2]i3{ .{ -1, -1 }, .{ -1, 1 }, .{ -1, -1 }, .{ -1, 1 }, .{ -1, -1 }, .{ -1, 1 }, .{ -1, -1 }, .{ -1, 1 } },
.p => [_][2]i3{ .{ 1, -1 }, .{ 1, 1 }, .{ 1, -1 }, .{ 1, 1 }, .{ 1, -1 }, .{ 1, 1 }, .{ 1, -1 }, .{ 1, 1 } },
.N, .n => [_][2]i3{ .{ -2, -1 }, .{ -2, 1 }, .{ 2, -1 }, .{ 2, 1 }, .{ -1, -2 }, .{ 1, 2 }, .{ -1, 2 }, .{ 1, -2 } },
.B, .b => [_][2]i3{ .{ -1, -1 }, .{ -1, 1 }, .{ 1, -1 }, .{ 1, 1 }, .{ -1, -1 }, .{ -1, 1 }, .{ 1, -1 }, .{ 1, 1 } },
.K, .k => [_][2]i3{ .{ -1, -1 }, .{ -1, 1 }, .{ 1, -1 }, .{ 1, 1 }, .{ -1, 0 }, .{ 0, 1 }, .{ 1, 0 }, .{ 0, -1 } },
.R, .r => [_][2]i3{ .{ -1, 0 }, .{ 1, 0 }, .{ 0, -1 }, .{ 0, 1 }, .{ -1, 0 }, .{ 1, 0 }, .{ 0, -1 }, .{ 0, 1 } },
.Q, .q, .none => @panic("unexpected piece"),
};
var attacks: u64 = 0;
@setEvalBranchQuota(10_000);
var step: i5 = 1;
while (step < 8 - 1) : (step += 1) {
for (moves) |m| {
const dr = rank + m[0] * step;
const df = file + m[1] * step;
switch (rider) {
true => {
if (m[0] > 0 and dr > 6) continue;
if (m[0] < 0 and dr < 1) continue;
if (m[1] > 0 and df > 6) continue;
if (m[1] < 0 and df < 1) continue;
},
false => {
if (dr < 0 or dr > 7) continue;
if (df < 0 or df > 7) continue;
},
}
const s = @intCast(u6, dr * 8 + df);
attacks |= @as(u64, 1) << s;
}
if (!rider) break;
}
return attacks;
}
fn attackWithBlocker(blocks: u64, square: chess.Square, piece: chess.Piece) u64 {
const rank = @intCast(isize, @enumToInt(square) / 8);
const file = @intCast(isize, @enumToInt(square) % 8);
const moves = switch (piece) {
.B, .b => [_][2]i3{
.{ -1, -1 },
.{ -1, 1 },
.{ 1, -1 },
.{ 1, 1 },
},
.R, .r => [_][2]i3{
.{ -1, 0 },
.{ 1, 0 },
.{ 0, -1 },
.{ 0, 1 },
},
else => @panic("unexpected piece"),
};
var attacks: u64 = 0;
@setEvalBranchQuota(10_000_000);
for (moves) |m| {
var step: i5 = 1;
while (step < 8) : (step += 1) {
const dr = rank + m[0] * step;
const df = file + m[1] * step;
if (m[0] > 0 and dr > 7) break;
if (m[0] < 0 and dr < 0) break;
if (m[1] > 0 and df > 7) break;
if (m[1] < 0 and df < 0) break;
const s = @intCast(u6, dr * 8 + df);
const mask = @as(u64, 1) << s;
attacks |= mask;
// stop when we hit a blocker
if (mask & blocks != 0) break;
}
}
return attacks;
}
fn setOccupancy(index: usize, bits_in_mask: u64, attack_mask: u64) u64 {
var occupancy: u64 = 0;
var attack = attack_mask;
var count: u6 = 0;
while (count < bits_in_mask) : (count += 1) {
const square = @intCast(u6, @ctz(attack));
// pop square bit
attack ^= @as(u64, 1) << square;
if (index & @as(u64, 1) << count != 0) {
occupancy |= @as(u64, 1) << square;
}
}
return occupancy;
}
fn genRelevantOccupancy(piece: chess.Piece) [@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));
ret[@enumToInt(square)] = @intCast(u4, count);
}
return ret;
}
When I try to compile it on my rpi4 it takes 140 seconds. If I apply the following patch it drops down to 4 seconds.
--- main-comptime.zig
+++ main.zig
@@ -1,7 +1,7 @@
const std = @import("std");
pub fn main() !void {
- const attacks = Attacks{};
+ const attacks = Attacks.init();
_ = attacks;
}
@@ -29,9 +29,10 @@
knight_attacks: [64]u64 = genKnightAttacks(),
bishop_masks: [64]u64 = genBishopMasks(),
rook_masks: [64]u64 = genRookMasks(),
- bishop_attacks: [64][512]u64 = genBishopAttacks(),
- rook_attacks: [64][4096]u64 = genRookAttacks(),
+ var bishop_attacks: [64][512]u64 = undefined;
+ var rook_attacks: [64][4096]u64 = undefined;
+
// rider pieces
const bishop_magic: [64]u64 = .{
0x0002020202020200, 0x0002020202020000, 0x0004010202000000, 0x0004040080000000,
@@ -74,6 +75,13 @@
const bishop_relevant_bits = genRelevantOccupancy(.B);
const rook_relevant_bits = genRelevantOccupancy(.R);
+ pub fn init() @This() {
+ var attacks: @This() = .{};
+ bishop_attacks = genBishopAttacks();
+ rook_attacks = genRookAttacks();
+ return attacks;
+ }
+
fn genBishopAttacks() [64][512]u64 {
var ret: [64][512]u64 = undefined;
@@ -135,7 +143,7 @@
mut_occupancy = @mulWithOverflow(mut_occupancy, bishop_magic[square])[0];
mut_occupancy >>= @intCast(u6, @as(u7, 64) - bishop_relevant_bits[square]);
- return self.bishop_attacks[square][mut_occupancy];
+ return bishop_attacks[square][mut_occupancy];
}
pub fn getRookAttacks(self: *const @This(), square: u6, occupancy: u64) u64 {
@@ -145,7 +153,7 @@
mut_occupancy = @mulWithOverflow(mut_occupancy, rook_magic[square])[0];
mut_occupancy >>= @intCast(u6, @as(u7, 64) - rook_relevant_bits[square]);
- return self.rook_attacks[square][mut_occupancy];
+ return rook_attacks[square][mut_occupancy];
}
pub fn getQueenAttacks(self: *const @This(), square: u6, occupancy: u64) u64 {
As You can see I just move the bishop and rook move precalculations from comptime to runtime. Can You tell me if this difference is expected? Can I do something about it besides the patch?
Is it possible with the new build system to create some kind of module from it and just link it?
Thanks,