chess/square/
moves.rs

1use crate::{Piece, Player, Role, board::Bitboard};
2
3use super::{Direction, Square};
4
5use Player::*;
6use Role::*;
7
8include!("slider-sights.rs");
9
10/// Square Move API.
11impl Square {
12    pub const fn attacks(self, piece: Piece, occupied: Bitboard) -> Bitboard {
13        match piece.role {
14            Pawn => self.pawn_attack_moves(piece.player),
15            Knight => self.knight_moves(),
16            Bishop => self.bishop_sight(occupied),
17            Rook => self.rook_sight(occupied),
18            Queen => self.queen_sight(occupied),
19            King => self.king_moves(),
20        }
21    }
22
23    pub const fn king_moves(self) -> Bitboard {
24        const KING_ATTACKS: [Direction; 8] = {
25            use Direction::*;
26            [North, NorthEast, East, SouthEast, South, SouthWest, West, NorthWest]
27        };
28
29        self.checked_add_vector_const(&KING_ATTACKS)
30    }
31
32    pub const fn knight_moves(self) -> Bitboard {
33        const KNIGHT_MOVES: [Direction; 8] = {
34            use Direction::*;
35            [
36                KnightNorthEast,
37                KnightEastNorth,
38                KnightEastSouth,
39                KnightSouthEast,
40                KnightSouthWest,
41                KnightWestSouth,
42                KnightWestNorth,
43                KnightNorthWest,
44            ]
45        };
46
47        self.checked_add_vector_const(&KNIGHT_MOVES)
48    }
49
50    pub const fn pawn_attack_moves(self, player: Player) -> Bitboard {
51        const WHITE_PAWN_ATTACKS: [Direction; 2] = {
52            use Direction::*;
53            [NorthWest, NorthEast]
54        };
55        const BLACK_PAWN_ATTACKS: [Direction; 2] = {
56            use Direction::*;
57            [SouthWest, SouthEast]
58        };
59
60        match player {
61            White => self.checked_add_vector_const(&WHITE_PAWN_ATTACKS),
62            Black => self.checked_add_vector_const(&BLACK_PAWN_ATTACKS),
63        }
64    }
65
66    pub const fn bishop_sight(self, occupied: Bitboard) -> Bitboard {
67        SLIDER_SIGHTS.bishop_sight(self, occupied)
68    }
69
70    pub const fn rook_sight(self, occupied: Bitboard) -> Bitboard {
71        SLIDER_SIGHTS.rook_sight(self, occupied)
72    }
73
74    pub const fn queen_sight(self, occupied: Bitboard) -> Bitboard {
75        self.bishop_sight(occupied).union(self.rook_sight(occupied))
76    }
77}
78
79mod bishop {
80    use super::*;
81
82    pub const DIRECTIONS: [Direction; 4] = {
83        use Direction::*;
84        [NorthEast, SouthEast, SouthWest, NorthWest]
85    };
86
87    pub const fn projector(square: Square) -> &'static Projector<9> {
88        &BISHOP_PROJECTOR[square as usize]
89    }
90
91    pub const fn blockers(square: Square) -> Bitboard {
92        const BLOCKERS: SliderBlockers = SliderBlockers::new(&DIRECTIONS);
93
94        BLOCKERS.get(square)
95    }
96}
97
98mod rook {
99    use super::*;
100
101    pub const DIRECTIONS: [Direction; 4] = {
102        use Direction::*;
103        [North, East, South, West]
104    };
105
106    pub const fn projector(square: Square) -> &'static Projector<12> {
107        &ROOK_PROJECTOR[square as usize]
108    }
109
110    pub const fn blockers(square: Square) -> Bitboard {
111        const BLOCKERS: SliderBlockers = SliderBlockers::new(&DIRECTIONS);
112
113        BLOCKERS.get(square)
114    }
115}
116
117struct Projector<const B: u32> {
118    pub factor: u64,
119    pub offset: usize,
120}
121
122impl<const B: u32> Projector<B> {
123    const fn new(factor: u64, offset: usize) -> Self {
124        Self { factor, offset }
125    }
126
127    // Compress the "occupied squares" bitboard down to 88772 entries
128    const fn index(&self, bitboard: Bitboard) -> usize {
129        (self.factor.wrapping_mul(bitboard.0) >> (64 - B)) as usize + self.offset
130    }
131}
132
133pub struct SliderSights([Bitboard; 88772]);
134
135impl SliderSights {
136    pub const fn volker_annuss() -> Self {
137        let mut this = Self([Bitboard::EMPTY; 88772]);
138        let mut index = 0;
139        while index < 64 {
140            let square = Square::ALL[index];
141            this.project_bishop_sights(square);
142            this.project_rook_sights(square);
143            index += 1;
144        }
145        this
146    }
147
148    pub const fn into_array(self) -> [Bitboard; 88772] {
149        self.0
150    }
151
152    // All the squares a bishop in square "sees", assuming the given occupied squares.
153    // Includes the first occupied squarie blocking further sight
154    pub const fn bishop_sight(&self, square: Square, occupied: Bitboard) -> Bitboard {
155        let blockers = bishop::blockers(square);
156        let index = bishop::projector(square).index(occupied.intersection(blockers));
157        self.0[index]
158    }
159
160    pub const fn rook_sight(&self, square: Square, occupied: Bitboard) -> Bitboard {
161        let blockers = rook::blockers(square);
162        let index = rook::projector(square).index(occupied.intersection(blockers));
163        self.0[index]
164    }
165
166    const fn project_bishop_sights(&mut self, square: Square) {
167        self.project_slider_sights(
168            square,
169            &bishop::DIRECTIONS,
170            bishop::blockers(square),
171            bishop::projector(square),
172        );
173    }
174
175    const fn project_rook_sights(&mut self, square: Square) {
176        self.project_slider_sights(
177            square,
178            &rook::DIRECTIONS,
179            rook::blockers(square),
180            rook::projector(square),
181        );
182    }
183
184    const fn get(&self, index: usize) -> Bitboard {
185        self.0[index]
186    }
187
188    const fn set(&mut self, index: usize, attack: Bitboard) {
189        self.0[index] = attack;
190    }
191
192    const fn project_slider_sights<const B: u32>(
193        &mut self,
194        square: Square,
195        directions: &[Direction],
196        blockers: Bitboard,
197        projector: &Projector<B>,
198    ) {
199        let mut occupied = Bitboard::EMPTY;
200        loop {
201            let index = projector.index(occupied);
202            let sight = Self::sight(square, occupied, directions);
203            // sanity check: we are not overwriting an existing attack
204            // due to hash / magic index failing by clashing.
205            assert!(self.get(index).is_empty() || self.get(index).eq(sight));
206            self.set(index, sight);
207            occupied = blockers.next_subset(occupied);
208            if occupied.is_empty() {
209                break;
210            }
211        }
212    }
213
214    // This is NOT computed directly for every "slider" attack from a given square.
215    // Instead, it's used to precompute the slider attack table.
216    const fn sight(square: Square, occupied: Bitboard, directions: &[Direction]) -> Bitboard {
217        let mut sight = Bitboard::EMPTY;
218        let mut i = 0;
219        while i < directions.len() {
220            let direction = directions[i];
221            let mut square = square;
222            while let Some(target) = square.checked_add(direction) {
223                sight.append(Bitboard::from_square(target));
224                // hit an occupied square
225                if occupied.contains(target) {
226                    break;
227                }
228                square = target;
229            }
230            i += 1;
231        }
232        sight
233    }
234}
235
236#[allow(dead_code)]
237struct SliderBlockers([Bitboard; 64]);
238
239#[allow(dead_code)]
240impl SliderBlockers {
241    const fn new(directions: &[Direction]) -> Self {
242        let mut blockers = [Bitboard::EMPTY; 64];
243        let mut index = 0;
244        while index < 64 {
245            blockers[index] = Self::ray_blockers(Square::ALL[index], directions);
246            index += 1;
247        }
248        Self(blockers)
249    }
250
251    const fn get(&self, square: Square) -> Bitboard {
252        self.0[square as usize]
253    }
254
255    const fn ray_blockers(square: Square, directions: &[Direction]) -> Bitboard {
256        let mut blockers = Bitboard::EMPTY;
257        let mut i = 0;
258        while i < directions.len() {
259            let direction = directions[i];
260            let mut target = square.checked_add(direction);
261            while let Some(square) = target {
262                target = square.checked_add(direction);
263                if target.is_some() {
264                    blockers.append(Bitboard::from_square(square));
265                }
266            }
267            i += 1;
268        }
269        blockers
270    }
271}
272
273// Fixed shift white magics found by Volker Annuss.
274// From: http://www.talkchess.com/forum/viewtopic.php?p=727500&t=64790
275
276#[rustfmt::skip]
277const BISHOP_PROJECTOR: [Projector<9>; 64] = [
278    Projector::new(0x007f_bfbf_bfbf_bfff, 5378),
279    Projector::new(0x0000_a060_4010_07fc, 4093),
280    Projector::new(0x0001_0040_0802_0000, 4314),
281    Projector::new(0x0000_8060_0400_0000, 6587),
282    Projector::new(0x0000_1004_0000_0000, 6491),
283    Projector::new(0x0000_21c1_00b2_0000, 6330),
284    Projector::new(0x0000_0400_4100_8000, 5609),
285    Projector::new(0x0000_0fb0_203f_ff80, 22236),
286    Projector::new(0x0000_0401_0040_1004, 6106),
287    Projector::new(0x0000_0200_8020_0802, 5625),
288    Projector::new(0x0000_0040_1020_2000, 16785),
289    Projector::new(0x0000_0080_6004_0000, 16817),
290    Projector::new(0x0000_0044_0200_0000, 6842),
291    Projector::new(0x0000_0008_0100_8000, 7003),
292    Projector::new(0x0000_07ef_e0bf_ff80, 4197),
293    Projector::new(0x0000_0008_2082_0020, 7356),
294    Projector::new(0x0000_4000_8080_8080, 4602),
295    Projector::new(0x0002_1f01_0040_0808, 4538),
296    Projector::new(0x0001_8000_c06f_3fff, 29531),
297    Projector::new(0x0000_2582_0080_1000, 45393),
298    Projector::new(0x0000_2400_8084_0000, 12420),
299    Projector::new(0x0000_1800_0c03_fff8, 15763),
300    Projector::new(0x0000_0a58_4020_8020, 5050),
301    Projector::new(0x0000_0200_0820_8020, 4346),
302    Projector::new(0x0000_8040_0081_0100, 6074),
303    Projector::new(0x0001_0119_0080_2008, 7866),
304    Projector::new(0x0000_8040_0081_0100, 32139),
305    Projector::new(0x0001_0040_3c04_03ff, 57673),
306    Projector::new(0x0007_8402_a880_2000, 55365),
307    Projector::new(0x0000_1010_0080_4400, 15818),
308    Projector::new(0x0000_0808_0010_4100, 5562),
309    Projector::new(0x0000_4004_c008_2008, 6390),
310    Projector::new(0x0001_0101_2000_8020, 7930),
311    Projector::new(0x0000_8080_9a00_4010, 13329),
312    Projector::new(0x0007_fefe_0881_0010, 7170),
313    Projector::new(0x0003_ff0f_833f_c080, 27267),
314    Projector::new(0x007f_e080_1900_3042, 53787),
315    Projector::new(0x003f_ffef_ea00_3000, 5097),
316    Projector::new(0x0000_1010_1000_2080, 6643),
317    Projector::new(0x0000_8020_0508_0804, 6138),
318    Projector::new(0x0000_8080_80a8_0040, 7418),
319    Projector::new(0x0000_1041_0020_0040, 7898),
320    Projector::new(0x0003_ffdf_7f83_3fc0, 42012),
321    Projector::new(0x0000_0088_4045_0020, 57350),
322    Projector::new(0x0000_7ffc_8018_0030, 22813),
323    Projector::new(0x007f_ffdd_8014_0028, 56693),
324    Projector::new(0x0002_0080_200a_0004, 5818),
325    Projector::new(0x0000_1010_1010_0020, 7098),
326    Projector::new(0x0007_ffdf_c180_5000, 4451),
327    Projector::new(0x0003_ffef_e0c0_2200, 4709),
328    Projector::new(0x0000_0008_2080_6000, 4794),
329    Projector::new(0x0000_0000_0840_3000, 13364),
330    Projector::new(0x0000_0001_0020_2000, 4570),
331    Projector::new(0x0000_0040_4080_2000, 4282),
332    Projector::new(0x0004_0100_4010_0400, 14964),
333    Projector::new(0x0000_6020_6018_03f4, 4026),
334    Projector::new(0x0003_ffdf_dfc2_8048, 4826),
335    Projector::new(0x0000_0008_2082_0020, 7354),
336    Projector::new(0x0000_0000_0820_8060, 4848),
337    Projector::new(0x0000_0000_0080_8020, 15946),
338    Projector::new(0x0000_0000_0100_2020, 14932),
339    Projector::new(0x0000_0004_0100_2008, 16588),
340    Projector::new(0x0000_0040_4040_4040, 6905),
341    Projector::new(0x007f_ff9f_df7f_f813, 16076),
342];
343
344#[rustfmt::skip]
345const ROOK_PROJECTOR: [Projector<12>; 64] = [
346    Projector::new(0x0028_0077_ffeb_fffe, 26304),
347    Projector::new(0x2004_0102_0109_7fff, 35520),
348    Projector::new(0x0010_0200_1005_3fff, 38592),
349    Projector::new(0x0040_0400_0800_4002, 8026),
350    Projector::new(0x7fd0_0441_ffff_d003, 22196),
351    Projector::new(0x4020_0088_87df_fffe, 80870),
352    Projector::new(0x0040_0088_8847_ffff, 76747),
353    Projector::new(0x0068_00fb_ff75_fffd, 30400),
354    Projector::new(0x0000_2801_0113_ffff, 11115),
355    Projector::new(0x0020_0402_01fc_ffff, 18205),
356    Projector::new(0x007f_e800_42ff_ffe8, 53577),
357    Projector::new(0x0000_1800_217f_ffe8, 62724),
358    Projector::new(0x0000_1800_073f_ffe8, 34282),
359    Projector::new(0x0000_1800_e05f_ffe8, 29196),
360    Projector::new(0x0000_1800_602f_ffe8, 23806),
361    Projector::new(0x0000_3000_2fff_ffa0, 49481),
362    Projector::new(0x0030_0018_010b_ffff, 2410),
363    Projector::new(0x0003_000c_0085_fffb, 36498),
364    Projector::new(0x0004_0008_0201_0008, 24478),
365    Projector::new(0x0004_0020_2002_0004, 10074),
366    Projector::new(0x0001_0020_0200_2001, 79315),
367    Projector::new(0x0001_0010_0080_1040, 51779),
368    Projector::new(0x0000_0040_4000_8001, 13586),
369    Projector::new(0x0000_0068_00cd_fff4, 19323),
370    Projector::new(0x0040_2000_1008_0010, 70612),
371    Projector::new(0x0000_0800_1004_0010, 83652),
372    Projector::new(0x0004_0100_0802_0008, 63110),
373    Projector::new(0x0000_0400_2020_0200, 34496),
374    Projector::new(0x0002_0080_1010_0100, 84966),
375    Projector::new(0x0000_0080_2001_0020, 54341),
376    Projector::new(0x0000_0080_2020_0040, 60421),
377    Projector::new(0x0000_8200_2000_4020, 86402),
378    Projector::new(0x00ff_fd18_0030_0030, 50245),
379    Projector::new(0x007f_ff7f_bfd4_0020, 76622),
380    Projector::new(0x003f_ffbd_0018_0018, 84676),
381    Projector::new(0x001f_ffde_8018_0018, 78757),
382    Projector::new(0x000f_ffe0_bfe8_0018, 37346),
383    Projector::new(0x0001_0000_8020_2001, 370),
384    Projector::new(0x0003_fffb_ff98_0180, 42182),
385    Projector::new(0x0001_fffd_ff90_00e0, 45385),
386    Projector::new(0x00ff_fefe_ebff_d800, 61659),
387    Projector::new(0x007f_fff7_ffc0_1400, 12790),
388    Projector::new(0x003f_ffbf_e4ff_e800, 16762),
389    Projector::new(0x001f_fff0_1fc0_3000, 0),
390    Projector::new(0x000f_ffe7_f8bf_e800, 38380),
391    Projector::new(0x0007_ffdf_df3f_f808, 11098),
392    Projector::new(0x0003_fff8_5fff_a804, 21803),
393    Projector::new(0x0001_fffd_75ff_a802, 39189),
394    Projector::new(0x00ff_ffd7_ffeb_ffd8, 58628),
395    Projector::new(0x007f_ff75_ff7f_bfd8, 44116),
396    Projector::new(0x003f_ff86_3fbf_7fd8, 78357),
397    Projector::new(0x001f_ffbf_dfd7_ffd8, 44481),
398    Projector::new(0x000f_fff8_1028_0028, 64134),
399    Projector::new(0x0007_ffd7_f7fe_ffd8, 41759),
400    Projector::new(0x0003_fffc_0c48_0048, 1394),
401    Projector::new(0x0001_ffff_afd7_ffd8, 40910),
402    Projector::new(0x00ff_ffe4_ffdf_a3ba, 66516),
403    Projector::new(0x007f_ffef_7ff3_d3da, 3897),
404    Projector::new(0x003f_ffbf_dfef_f7fa, 3930),
405    Projector::new(0x001f_ffef_f7fb_fc22, 72934),
406    Projector::new(0x0000_0204_0800_1001, 72662),
407    Projector::new(0x0007_fffe_ffff_77fd, 56325),
408    Projector::new(0x0003_ffff_bf7d_feec, 66501),
409    Projector::new(0x0001_ffff_9dff_a333, 14826),
410];
chess/square/moves.rs

chess/square/
moves.rs
