Skip to content

Instantly share code, notes, and snippets.

@Osrepnay

Osrepnay/magics.rs

Created September 14, 2022 02:02
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Osrepnay/1e5c50faf05c6fbe236c090fe8be1eaa to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Osrepnay/1e5c50faf05c6fbe236c090fe8be1eaa to your computer and use it in GitHub Desktop.
Download ZIP
chess magic generator in rust
Raw
magics.rs
use rand_core::RngCore;
use rand_core::SeedableRng;
use rand_xoshiro::Xoshiro256StarStar;
use std::time::{Duration, SystemTime, UNIX_EPOCH};
static BISHOP_BITS: [u32; 64] = [
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,
];
#[rustfmt::skip]
static ROOK_BITS: [u32; 64] = [
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
];
// pops lowest set bit
macro_rules! pop_lowest {
( $n:ident ) => {{
let lowest = $n.trailing_zeros();
$n &= !(1 << lowest);
lowest
}};
}
// bishop-rook agnostic
fn classic(sq: usize, blockers: u64, rays: &[[u64; 4]; 64]) -> u64 {
let mut squares = 0;
for i in 0..4 {
squares |= rays[sq][i];
let masked_blockers = rays[sq][i] & blockers;
if masked_blockers != 0 {
let blocker_ray_start = match i {
0 => masked_blockers.trailing_zeros(), // bit scan forward
1 => 63 - masked_blockers.leading_zeros(), // bit scan not forward
2 => 63 - masked_blockers.leading_zeros(),
3 => masked_blockers.trailing_zeros(),
_ => panic!("direction doesn't exist"),
} as usize;
squares &= !rays[blocker_ray_start][i];
}
}
squares
}
fn map_bits_mask(mut mask: u64, num_set: u32, bits: u64) -> u64 {
let mut mapped = 0;
for i in 0..num_set {
let popped = pop_lowest!(mask);
if bits & (1 << i) != 0 {
mapped |= 1 << popped;
}
}
mapped
}
fn magic_good(magic: u64, correct_moves: &[u64; 1 << 12], mask: u64, bits: u32) -> bool {
let mut moves = [0; 1 << 12]; // 0 move isn't possible
let mask_num_set = mask.count_ones();
for set_bits in 0..(1 << bits) {
let blockers = map_bits_mask(mask, mask_num_set, set_bits as u64);
let magic_idx = (blockers.wrapping_mul(magic) >> (64 - bits)) as usize;
if moves[magic_idx] == 0 {
moves[magic_idx] = correct_moves[set_bits];
} else if moves[magic_idx] != correct_moves[set_bits] {
return false;
}
}
true
}
fn _print_bitboard(mut board: u64) {
for _ in 0..8 {
eprintln!(
"{}",
format!("{:0>8b}", board >> 56)
.chars()
.rev()
.collect::<String>()
);
board <<= 8;
}
eprintln!("");
}
fn main() {
let since_the_epoch = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap_or(Duration::ZERO)
.as_millis() as u64;
let mut rand = Xoshiro256StarStar::seed_from_u64(since_the_epoch);
let top = 0xFF00000000000000;
let bottom = 0x00000000000000FF;
let left = 0x0101010101010101;
let right = 0x8080808080808080;
let edges = top | bottom | left | right;
let mut bishop_rays = [[0; 4]; 64];
let mut bishop_masks: [u64; 64] = [0; 64];
for i in (0 as isize)..64 {
// these cannot be reordered (rook ones can't either) because of classic movegen
// assumptions
// up-right
let mut j = i + 9;
while j < 64 && j % 8 != 0 {
bishop_rays[i as usize][0] |= 1 << j;
j += 9;
}
// down-left
let mut j = i - 9;
while j >= 0 && j % 8 != 7 {
bishop_rays[i as usize][1] |= 1 << j;
j -= 9;
}
// down-right
let mut j = i - 7;
while j >= 0 && j % 8 != 0 {
bishop_rays[i as usize][2] |= 1 << j;
j -= 7;
}
// up-left
let mut j = i + 7;
while j < 64 && j % 8 != 7 {
bishop_rays[i as usize][3] |= 1 << j;
j += 7;
}
bishop_masks[i as usize] = bishop_rays[i as usize][0]
| bishop_rays[i as usize][1]
| bishop_rays[i as usize][2]
| bishop_rays[i as usize][3];
bishop_masks[i as usize] &= !edges;
_print_bitboard(bishop_rays[i as usize][0]);
}
let mut rook_rays = [[0; 4]; 64];
let mut rook_masks: [u64; 64] = [0; 64];
for i in (0 as isize)..64 {
// up
for j in ((i + 8)..=63).step_by(8) {
rook_rays[i as usize][0] |= 1 << j;
}
rook_masks[i as usize] |= rook_rays[i as usize][0] & !top;
// down
for j in ((i % 8)..=(i - 8)).step_by(8) {
rook_rays[i as usize][1] |= 1 << j;
}
rook_masks[i as usize] |= rook_rays[i as usize][1] & !bottom;
// left
for j in (8 * (i / 8))..=(i - 1) {
rook_rays[i as usize][2] |= 1 << j;
}
rook_masks[i as usize] |= rook_rays[i as usize][2] & !left;
// right
for j in (i + 1)..=(8 * (i / 8 + 1) - 1) {
rook_rays[i as usize][3] |= 1 << j;
}
rook_masks[i as usize] |= rook_rays[i as usize][3] & !right;
}
eprintln!("done initializing");
println!("bishop moves");
for sq in 0..64 {
let mut correct_moves = [0; 1 << 12];
let mask_num_set = bishop_masks[sq].count_ones();
for i in 0..(1 << BISHOP_BITS[sq]) {
correct_moves[i] = classic(
sq,
map_bits_mask(bishop_masks[sq], mask_num_set, i as u64),
&bishop_rays,
);
}
let mut maybe_magic = rand.next_u64() & rand.next_u64() & rand.next_u64();
while !magic_good(
maybe_magic,
&correct_moves,
bishop_masks[sq],
BISHOP_BITS[sq],
) {
maybe_magic = rand.next_u64() & rand.next_u64() & rand.next_u64();
}
println!("0x{:0>16X},", maybe_magic);
}
println!("rook moves");
for sq in 0..64 {
let mut correct_moves = [0; 1 << 12];
let mask_num_set = rook_masks[sq].count_ones();
for i in 0..(1 << ROOK_BITS[sq]) {
correct_moves[i] = classic(
sq,
map_bits_mask(rook_masks[sq], mask_num_set, i as u64),
&rook_rays,
);
}
let mut maybe_magic = rand.next_u64() & rand.next_u64() & rand.next_u64();
while !magic_good(maybe_magic, &correct_moves, rook_masks[sq], ROOK_BITS[sq]) {
maybe_magic = rand.next_u64() & rand.next_u64() & rand.next_u64();
}
println!("0x{:0>16X},", maybe_magic);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment