tanton/helper/
magic.rs

1use std::mem;
2use std::ptr;
3
4use core::masks::*;
5use SQ;
6
7use core::bit_twiddles::popcount64;
8use core::{file_bb, rank_bb};
9use tools::prng::PRNG;
10
11/// Size of the magic rook table.
12const ROOK_M_SIZE: usize = 102_400;
13static mut ROOK_MAGICS: [SMagic; 64] = [SMagic::init(); 64];
14static mut ROOK_TABLE: [u64; ROOK_M_SIZE] = [0; ROOK_M_SIZE];
15
16/// Size of the magic bishop table.
17const BISHOP_M_SIZE: usize = 5248;
18static mut BISHOP_MAGICS: [SMagic; 64] = [SMagic::init(); 64];
19static mut BISHOP_TABLE: [u64; BISHOP_M_SIZE] = [0; BISHOP_M_SIZE];
20
21const B_DELTAS: [i8; 4] = [7, 9, -9, -7];
22const R_DELTAS: [i8; 4] = [8, 1, -8, -1];
23
24const SEEDS: [[u64; 8]; 2] = [
25    [8977, 44_560, 54_343, 38_998, 5731, 95_205, 104_912, 17_020],
26    [728, 10_316, 55_013, 32_803, 12_281, 15_100, 16_645, 255],
27];
28
29#[cold]
30pub fn init_magics() {
31    unsafe {
32        gen_magic_board(
33            BISHOP_M_SIZE,
34            &B_DELTAS,
35            BISHOP_MAGICS.as_mut_ptr(),
36            BISHOP_TABLE.as_mut_ptr(),
37        );
38        gen_magic_board(
39            ROOK_M_SIZE,
40            &R_DELTAS,
41            ROOK_MAGICS.as_mut_ptr(),
42            ROOK_TABLE.as_mut_ptr(),
43        );
44    }
45}
46
47#[inline]
48pub fn bishop_attacks(mut occupied: u64, square: u8) -> u64 {
49    let magic_entry: &SMagic = unsafe { BISHOP_MAGICS.get_unchecked(square as usize) };
50    occupied &= magic_entry.mask;
51    occupied = occupied.wrapping_mul(magic_entry.magic);
52    occupied = occupied.wrapping_shr(magic_entry.shift);
53    unsafe { *(magic_entry.ptr as *const u64).add(occupied as usize) }
54}
55
56#[inline]
57pub fn rook_attacks(mut occupied: u64, square: u8) -> u64 {
58    let magic_entry: &SMagic = unsafe { ROOK_MAGICS.get_unchecked(square as usize) };
59    occupied &= magic_entry.mask;
60    occupied = occupied.wrapping_mul(magic_entry.magic);
61    occupied = occupied.wrapping_shr(magic_entry.shift);
62    unsafe { *(magic_entry.ptr as *const u64).add(occupied as usize) }
63}
64
65/// Structure inside a `MagicTable` for a specific hash. For a certain square,
66/// contains a mask,  magic number, number to shift by, and a pointer into the array slice
67/// where the position is held.
68#[derive(Copy, Clone)]
69struct SMagic {
70    ptr: usize,
71    mask: u64,
72    magic: u64,
73    shift: u32,
74}
75
76impl SMagic {
77    pub const fn init() -> Self {
78        SMagic {
79            ptr: 0,
80            mask: 0,
81            magic: 0,
82            shift: 0,
83        }
84    }
85}
86
87/// Temporary struct used to create an actual `SMagic` Object.
88struct PreSMagic {
89    start: usize,
90    len: usize,
91    mask: u64,
92    magic: u64,
93    shift: u32,
94}
95
96impl PreSMagic {
97    pub fn init() -> PreSMagic {
98        PreSMagic {
99            start: 0,
100            len: 0,
101            mask: 0,
102            magic: 0,
103            shift: 0,
104        }
105    }
106
107    // creates an array of PreSMagic
108    pub unsafe fn init64() -> [PreSMagic; 64] {
109        let arr: [PreSMagic; 64] = mem::MaybeUninit::uninit().assume_init();
110        arr
111    }
112
113    // Helper method to compute the next index
114    pub fn next_idx(&self) -> usize {
115        self.start + self.len
116    }
117}
118
119/// Creates the `MagicTable` struct. The table size is relative to the piece for computation,
120/// and the deltas are the directions on the board the piece can go.
121#[cold]
122unsafe fn gen_magic_board(
123    table_size: usize,
124    deltas: &[i8; 4],
125    static_magics: *mut SMagic,
126    attacks: *mut u64,
127) {
128    // Creates PreSMagic to hold raw numbers. Technically jsut adds room to stack
129    let mut pre_sq_table: [PreSMagic; 64] = PreSMagic::init64();
130
131    // Initializes each PreSMagic
132    for table in pre_sq_table.iter_mut() {
133        *table = PreSMagic::init();
134    }
135
136    // Occupancy tracks occupancy permutations. MAX permutations = subset of 12 bits = 2^12
137    // Reference is similar, tracks the sliding moves from a given occupancy
138    // Age tracks the best index for a current permutation
139    let mut occupancy: [u64; 4096] = [0; 4096];
140    let mut reference: [u64; 4096] = [0; 4096];
141    let mut age: [i32; 4096] = [0; 4096];
142
143    // Size tracks the size of permutations of the current block
144    let mut size: usize;
145
146    // b is used for generating the permutations through ripple - carry
147    let mut b: u64;
148
149    // current and i is a placeholder for actually generating correct magic numbers
150    let mut current: i32 = 0;
151    let mut i: usize;
152
153    // set the first PreSMagic start = 0. Just in case.
154    pre_sq_table[0].start = 0;
155
156    // Loop through each square! s is a SQ
157    for s in 0..64 as u8 {
158        // Magic number for later
159        let mut magic: u64;
160
161        // edges is the bitboard represenation of the edges s is not on.
162        // e.g. sq A1 is on FileA and Rank1, so edges = bitboard of FileH and Rank8
163        // mask = occupancy mask of square s
164        let edges: u64 = ((RANK_1 | RANK_8) & !rank_bb(s)) | ((FILE_A | FILE_H) & !file_bb(s));
165        let mask: u64 = sliding_attack(deltas, s, 0) & !edges;
166
167        // Shift = number of bits in 64 - bits in mask = log2(size)
168        let shift: u32 = (64 - popcount64(mask)) as u32;
169        b = 0;
170        size = 0;
171
172        // Ripple carry to determine occupancy, reference, and size
173        'bit: loop {
174            occupancy[size] = b;
175            reference[size] = sliding_attack(deltas, s, b);
176            size += 1;
177            b = ((b).wrapping_sub(mask)) as u64 & mask;
178            if b == 0 {
179                break 'bit;
180            }
181        }
182
183        // Set current PreSMagic length to be of size
184        pre_sq_table[s as usize].len = size;
185
186        // If there is a next square, set the start of it.
187        if s < 63 {
188            pre_sq_table[s as usize + 1].start = pre_sq_table[s as usize].next_idx();
189        }
190        // Create our Random Number Generator with a seed
191        let mut rng = PRNG::init(SEEDS[1][SQ(s).rank() as usize]);
192
193        // Loop until we have found our magics!
194        'outer: loop {
195            // Create a magic with our desired number of bits in the first 8 places
196            'first_in: loop {
197                magic = rng.sparse_rand();
198                if popcount64((magic.wrapping_mul(mask)).wrapping_shr(56)) >= 6 {
199                    break 'first_in;
200                }
201            }
202            current += 1;
203            i = 0;
204
205            // Filling the attacks Vector up to size digits
206            while i < size {
207                // Magic part! The index is = ((occupancy[s] & mask) * magic >> shift)
208                let index: usize = ((occupancy[i as usize] & mask).wrapping_mul(magic) as u64)
209                    .wrapping_shr(shift) as usize;
210
211                // Checking to see if we have visited this index already with a lower current number
212                if age[index] < current {
213                    // If we have visited with lower current, we replace it with this current number,
214                    // as this current is higher and has gone through more passes
215                    age[index] = current;
216                    *attacks.offset((pre_sq_table[s as usize].start + index) as isize) =
217                        reference[i];
218                } else if *attacks.offset((pre_sq_table[s as usize].start + index) as isize)
219                    != reference[i]
220                {
221                    // If a magic maps to the same index but different result, either magic is bad or we are done
222                    break;
223                }
224                i += 1;
225            }
226            // If we have filled it up to size or greater, we are done
227            if i >= size {
228                break 'outer;
229            }
230        }
231        // Set the remaining variables for the PreSMagic Struct
232        pre_sq_table[s as usize].magic = magic;
233        pre_sq_table[s as usize].mask = mask;
234        pre_sq_table[s as usize].shift = shift;
235    }
236
237    // size = running total of total size
238    let mut size = 0;
239    for i in 0..64 {
240        // begin ptr points to the beginning of the current slice in the vector
241        let beginptr = attacks.offset(size as isize);
242
243        // points to the static entry
244        let staticptr: *mut SMagic = static_magics.offset(i as isize);
245        let table_i: SMagic = SMagic {
246            ptr: mem::transmute::<*const u64, usize>(beginptr),
247            mask: pre_sq_table[i].mask,
248            magic: pre_sq_table[i].magic,
249            shift: pre_sq_table[i].shift,
250        };
251
252        ptr::copy::<SMagic>(&table_i, staticptr, 1);
253
254        // Create the pointer to the slice with begin_ptr / length
255        size += pre_sq_table[i].len;
256    }
257    // Sanity check
258    assert_eq!(size, table_size);
259}
260
261/// Returns a bitboards of sliding attacks given an array of 4 deltas/
262/// Does not include the original position/
263/// Includes occupied bits if it runs into them, but stops before going further.
264fn sliding_attack(deltas: &[i8; 4], sq: u8, occupied: u64) -> u64 {
265    assert!(sq < 64);
266    let mut attack: u64 = 0;
267    let square: i16 = sq as i16;
268    for delta in deltas.iter().take(4 as usize) {
269        let mut s: u8 = ((square as i16) + (*delta as i16)) as u8;
270        'inner: while s < 64 && SQ(s as u8).distance(SQ(((s as i16) - (*delta as i16)) as u8)) == 1
271        {
272            attack |= (1 as u64).wrapping_shl(s as u32);
273            if occupied & (1 as u64).wrapping_shl(s as u32) != 0 {
274                break 'inner;
275            }
276            s = ((s as i16) + (*delta as i16)) as u8;
277        }
278    }
279    attack
280}
tanton/helper/magic.rs

tanton/helper/
magic.rs
