blunders_engine/
bitboard.rs

1//! A general purpose way to efficiently encode data,
2//! where each bit index of a 64-bit unsigned integer represents a chessboard square.
3//!
4//! Data Order:
5//! * Little-Endian Rank-File mapping (LSR)
6//! * A1 = least significant bit = 0b0 = 0
7//! * B1 = 0b1 = 1
8//! * C1 = 0b10 = 2
9//! * A2 = 0b1000 = 8
10//! * H8 = most significant bit = 0x8000000000000000
11//!
12//! Compass Rose Bit Shifting:
13//! ```text
14//! NoWe       North       NoEa
15//!      +7     +8      +9
16//! West -1      0      +1 East
17//!      -9     -8      -7
18//! SoWe       South       SoEa
19//! ```
20//!
21//! Examples of data that may be represented with Bitboards:
22//! * W/B King position
23//! * W/B Queen positions
24//! * W/B Rook positions
25//! * W/B Bishop positions
26//! * W/B Knight positions
27//! * W/B Pawn positions
28//! * Pawn Attack Pattern per square
29//! * Knight Attack Pattern per square
30//! * King Attack Pattern per square
31//! * Sliding Attack Pattern per square
32//! * Pass Pawns
33
34use std::convert::TryFrom;
35use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, Not};
36
37use crate::coretypes::{File, Rank, Square, Square::*, SquareIndexable};
38
39/// Alias for inner type of Bitboard. Useful for const evaluation.
40pub type BitboardKind = u64;
41
42/// Bitboard is a wrapper around a u64 integer, where each bit represents some or none
43/// on its corresponding chess board square. It is used to encode a set of some arbitrary
44/// homogenous data for an entire chess board.
45#[derive(Debug, Copy, Clone, Eq, PartialEq)]
46#[repr(transparent)]
47pub struct Bitboard(pub(crate) BitboardKind);
48
49// Generate a bitboard made from bit-or-ing the bit-shifted representation of
50// each identifier passed.
51// Macro needed because `from` trait not const.
52// example: bb_from_shifts!(A1, A2) ->
53//          Bitboard(0u64 | (1u64 << A1 as u8) | (1u64 << A2 as u8))
54macro_rules! bb_from_shifts {
55    ($($shiftable:ident),+) => {
56        Bitboard(0u64 $( | (1u64 << $shiftable as u8))*)
57    };
58}
59
60/// Bitboard Constants
61impl Bitboard {
62    pub const EMPTY: Bitboard = Self(0x0);
63    pub const BLACK_SQUARES: Bitboard = Self(0xAA55AA55AA55AA55);
64    pub const WHITE_SQUARES: Bitboard = Self(!Self::BLACK_SQUARES.0);
65    // Ranks
66    pub const RANK_1: Bitboard = bb_from_shifts!(A1, B1, C1, D1, E1, F1, G1, H1);
67    pub const RANK_2: Bitboard = bb_from_shifts!(A2, B2, C2, D2, E2, F2, G2, H2);
68    pub const RANK_3: Bitboard = bb_from_shifts!(A3, B3, C3, D3, E3, F3, G3, H3);
69    pub const RANK_4: Bitboard = bb_from_shifts!(A4, B4, C4, D4, E4, F4, G4, H4);
70    pub const RANK_5: Bitboard = bb_from_shifts!(A5, B5, C5, D5, E5, F5, G5, H5);
71    pub const RANK_6: Bitboard = bb_from_shifts!(A6, B6, C6, D6, E6, F6, G6, H6);
72    pub const RANK_7: Bitboard = bb_from_shifts!(A7, B7, C7, D7, E7, F7, G7, H7);
73    pub const RANK_8: Bitboard = bb_from_shifts!(A8, B8, C8, D8, E8, F8, G8, H8);
74    // Files
75    pub const FILE_A: Bitboard = bb_from_shifts!(A1, A2, A3, A4, A5, A6, A7, A8);
76    pub const FILE_B: Bitboard = bb_from_shifts!(B1, B2, B3, B4, B5, B6, B7, B8);
77    pub const FILE_C: Bitboard = bb_from_shifts!(C1, C2, C3, C4, C5, C6, C7, C8);
78    pub const FILE_D: Bitboard = bb_from_shifts!(D1, D2, D3, D4, D5, D6, D7, D8);
79    pub const FILE_E: Bitboard = bb_from_shifts!(E1, E2, E3, E4, E5, E6, E7, E8);
80    pub const FILE_F: Bitboard = bb_from_shifts!(F1, F2, F3, F4, F5, F6, F7, F8);
81    pub const FILE_G: Bitboard = bb_from_shifts!(G1, G2, G3, G4, G5, G6, G7, G8);
82    pub const FILE_H: Bitboard = bb_from_shifts!(H1, H2, H3, H4, H5, H6, H7, H8);
83
84    pub const NOT_FILE_A: Bitboard = Self(!Self::FILE_A.0);
85    pub const NOT_FILE_H: Bitboard = Self(!Self::FILE_H.0);
86    // Squares between king and kingside rook. Useful for checking castling.
87    pub const KINGSIDE_BETWEEN: Bitboard = bb_from_shifts!(F1, G1, F8, G8);
88    pub const QUEENSIDE_BETWEEN: Bitboard = bb_from_shifts!(B1, C1, D1, B8, C8, D8);
89    // Squares that king passes through during castling.
90    pub const KINGSIDE_PASS: Bitboard = bb_from_shifts!(E1, F1, G1, E8, F8, G8);
91    pub const QUEENSIDE_PASS: Bitboard = bb_from_shifts!(C1, D1, E1, C8, D8, E8);
92}
93
94impl Bitboard {
95    /// Get copy of internal u64 representation of this Bitboard.
96    #[inline(always)]
97    pub const fn bits(&self) -> u64 {
98        self.0
99    }
100
101    /// Returns true if there are no squares in self, false otherwise.
102    #[inline(always)]
103    pub const fn is_empty(&self) -> bool {
104        self.0 == 0
105    }
106
107    /// Returns number of squares present.
108    /// Equivalent to number of bits in binary representation that are '1'.
109    /// When compiled for targets with BMI1 popcnt instruction, should resolve to a single instruction.
110    #[inline(always)]
111    pub const fn count_squares(&self) -> u32 {
112        self.0.count_ones()
113    }
114
115    /// Returns true if index is populated.
116    #[inline(always)]
117    pub fn has_square<I: SquareIndexable>(&self, idx: I) -> bool {
118        self.0 & idx.shift() != 0
119    }
120    /// Sets bit index to 1.
121    #[inline(always)]
122    pub fn set_square<I: SquareIndexable>(&mut self, idx: I) {
123        self.0 |= idx.shift();
124    }
125    /// Sets bit index to 0.
126    #[inline(always)]
127    pub fn clear_square<I: SquareIndexable>(&mut self, idx: I) {
128        self.0 &= !idx.shift();
129    }
130    /// Toggles bit index. 0 -> 1, 1 -> 0.
131    #[inline(always)]
132    pub fn toggle_square<I: SquareIndexable>(&mut self, idx: I) {
133        self.0 ^= idx.shift();
134    }
135
136    /// Clears squares including and above target square.
137    /// TODO:
138    /// There is a BMI2 instruction BZHI to zero high hits starting at position,
139    /// however the instruction is not used with &mut self, only self.
140    /// Figure out how to get get compiler to use BZHI.
141    #[inline(always)]
142    pub fn clear_square_and_above<I: SquareIndexable>(&mut self, idx: I) {
143        self.0 &= idx.shift() - 1;
144    }
145
146    /// Clears squares including and below target square.
147    /// TODO:
148    /// Find a BMI instruction, if applicable. Maybe BLSMSK.
149    pub fn clear_square_and_below<I: SquareIndexable>(&mut self, idx: I) {
150        self.0 &= !(idx.shift() ^ (idx.shift() - 1));
151    }
152
153    /// Clears the lowest square from self. If there are no squares, does nothing.
154    /// When compiled for targets that support BMI1 BLSR (reset lowest set bit),
155    /// should resolve to a single instruction and a move.
156    #[inline(always)]
157    pub fn clear_lowest_square(&mut self) {
158        // self.0 &= self.0 - 1 is same as below, but wrapping_sub doesn't panic for 0.
159        self.0 &= self.0.wrapping_sub(1);
160    }
161
162    /// Returns the lowest square that exists in bitboard, or None if bitboard has no squares.
163    #[inline(always)]
164    pub fn get_lowest_square(&self) -> Option<Square> {
165        Square::try_from(self.0.trailing_zeros() as u8).ok()
166    }
167
168    /// Remove all squares in other from self.
169    #[inline(always)]
170    pub fn remove(&mut self, other: &Bitboard) {
171        *self &= !other
172    }
173
174    /// Returns true if other is a subset of self.
175    /// If all squares of other are in self, then other is a subset of self.
176    #[inline(always)]
177    pub const fn contains(&self, other: &Bitboard) -> bool {
178        self.0 & other.0 == other.0
179    }
180
181    /// Returns true if self has any squares that are in other.
182    /// In other words, if there is any overlap, return true.
183    #[inline(always)]
184    pub const fn has_any(&self, other: &Bitboard) -> bool {
185        self.0 & other.0 != Self::EMPTY.0
186    }
187
188    /// Returns new Bitboard with all squares shifted 1 square north (ex: D4 -> D5).
189    #[inline(always)]
190    pub const fn to_north(&self) -> Self {
191        Self(self.0 << 8)
192    }
193    /// Returns new Bitboard with all squares shifted 1 square south (ex: D4 -> D3).
194    #[inline(always)]
195    pub const fn to_south(&self) -> Self {
196        Self(self.0 >> 8)
197    }
198    /// Returns new Bitboard with all squares shifted 1 square east (ex: D4 -> E4).
199    /// To prevent wrapping of bit to other rank, bits are removed on FILE_A.
200    #[inline(always)]
201    pub const fn to_east(&self) -> Self {
202        Self((self.0 << 1) & Self::NOT_FILE_A.0)
203    }
204    /// Returns new Bitboard with all squares shifted 1 square west (ex: D4 -> C4).
205    /// To prevent wrapping of bit to other rank, bits are removed on FILE_H.
206    #[inline(always)]
207    pub const fn to_west(&self) -> Self {
208        Self((self.0 >> 1) & Self::NOT_FILE_H.0)
209    }
210
211    /// Returns new Bitboard with all squares shifted 1 square north east (ex: D4 -> E5).
212    /// To prevent wrapping of bit to other rank, bits are removed on FILE_A.
213    #[inline(always)]
214    pub const fn to_north_east(&self) -> Self {
215        Self((self.0 << 9) & Self::NOT_FILE_A.0)
216    }
217    /// Returns new Bitboard with all squares shifted 1 square north west (ex: D4 -> C5).
218    /// To prevent wrapping of bit to other rank, bits are removed on FILE_H.
219    #[inline(always)]
220    pub const fn to_north_west(&self) -> Self {
221        Self((self.0 << 7) & Self::NOT_FILE_H.0)
222    }
223    /// Returns new Bitboard with all squares shifted 1 square south east (ex: D4 -> E3).
224    /// To prevent wrapping of bit to other rank, bits are removed on FILE_A.
225    #[inline(always)]
226    pub const fn to_south_east(&self) -> Self {
227        Self((self.0 >> 7) & Self::NOT_FILE_A.0)
228    }
229    /// Returns new Bitboard with all squares shifted 1 square south west (ex: D4 -> C3).
230    /// To prevent wrapping of bit to other rank, bits are removed on FILE_H.
231    #[inline(always)]
232    pub const fn to_south_west(&self) -> Self {
233        Self((self.0 >> 9) & Self::NOT_FILE_H.0)
234    }
235
236    /// Returns a vector of all the Squares represented in the Bitboard.
237    /// # Examples
238    /// ```rust
239    /// # use blunders_engine::bitboard::Bitboard;
240    /// # use blunders_engine::coretypes::Square;
241    /// let squares = vec![Square::A1, Square::D7];
242    /// let mut board = Bitboard::EMPTY;
243    /// squares.iter().for_each(|square| board.set_square(*square));
244    /// assert_eq!(board.squares(), squares);
245    /// ```
246    /// # Algorithm
247    /// For each '1' bit in Bitboard:
248    /// * Count trailing zeros. This is equal to the Square index, and is of 0-63.
249    /// * Get shift index by shifting by square index.
250    /// * Use shift index to remove bit from Bitboard.
251    /// * Convert square index to a Square and add to list.
252    pub fn squares(&self) -> Vec<Square> {
253        let mut bits = self.clone();
254        let num_ones = self.count_squares() as usize;
255        let mut vec = Vec::with_capacity(num_ones);
256
257        for _ in 0..num_ones {
258            let square_value = bits.0.trailing_zeros() as u8;
259            bits.clear_lowest_square();
260            let square = Square::try_from(square_value);
261            debug_assert!(square_value < 64u8 && square.is_ok());
262            vec.push(square.unwrap());
263        }
264        vec
265    }
266}
267
268impl Not for Bitboard {
269    type Output = Self;
270    fn not(self) -> Self::Output {
271        Self(!self.0)
272    }
273}
274
275impl Not for &Bitboard {
276    type Output = Bitboard;
277    fn not(self) -> Self::Output {
278        Bitboard(!self.0)
279    }
280}
281
282impl BitOr for Bitboard {
283    type Output = Self;
284    fn bitor(self, rhs: Self) -> Self::Output {
285        Self(self.0 | rhs.0)
286    }
287}
288
289impl BitOr<&Bitboard> for Bitboard {
290    type Output = Self;
291    fn bitor(self, rhs: &Bitboard) -> Self::Output {
292        Self(self.0 | rhs.0)
293    }
294}
295
296impl BitOr<Bitboard> for &Bitboard {
297    type Output = Bitboard;
298    fn bitor(self, rhs: Bitboard) -> Self::Output {
299        Bitboard(self.0 | rhs.0)
300    }
301}
302
303impl BitOrAssign for Bitboard {
304    fn bitor_assign(&mut self, rhs: Self) {
305        self.0 |= rhs.0
306    }
307}
308
309impl BitOrAssign<&Bitboard> for Bitboard {
310    fn bitor_assign(&mut self, rhs: &Bitboard) {
311        self.0 |= rhs.0
312    }
313}
314
315impl BitAnd for Bitboard {
316    type Output = Self;
317    fn bitand(self, rhs: Self) -> Self::Output {
318        Self(self.0 & rhs.0)
319    }
320}
321
322impl BitAnd<Bitboard> for &Bitboard {
323    type Output = Bitboard;
324    fn bitand(self, rhs: Bitboard) -> Self::Output {
325        Bitboard(self.0 & rhs.0)
326    }
327}
328
329impl BitAndAssign for Bitboard {
330    fn bitand_assign(&mut self, rhs: Self) {
331        self.0 &= rhs.0
332    }
333}
334
335impl BitXor for Bitboard {
336    type Output = Self;
337    fn bitxor(self, rhs: Self) -> Self::Output {
338        Self(self.0 ^ rhs.0)
339    }
340}
341
342impl<I: SquareIndexable> From<I> for Bitboard {
343    fn from(square_index: I) -> Self {
344        Self(square_index.shift())
345    }
346}
347
348impl<I: SquareIndexable> From<&[I]> for Bitboard {
349    fn from(square_index_slice: &[I]) -> Self {
350        let mut bb = Bitboard::EMPTY;
351        square_index_slice
352            .iter()
353            .for_each(|square| bb.set_square(square));
354        bb
355    }
356}
357
358impl From<File> for Bitboard {
359    fn from(file: File) -> Self {
360        use File::*;
361        match file {
362            A => Self::FILE_A,
363            B => Self::FILE_B,
364            C => Self::FILE_C,
365            D => Self::FILE_D,
366            E => Self::FILE_E,
367            F => Self::FILE_F,
368            G => Self::FILE_G,
369            H => Self::FILE_H,
370        }
371    }
372}
373
374impl From<Rank> for Bitboard {
375    fn from(rank: Rank) -> Self {
376        use Rank::*;
377        match rank {
378            R1 => Self::RANK_1,
379            R2 => Self::RANK_2,
380            R3 => Self::RANK_3,
381            R4 => Self::RANK_4,
382            R5 => Self::RANK_5,
383            R6 => Self::RANK_6,
384            R7 => Self::RANK_7,
385            R8 => Self::RANK_8,
386        }
387    }
388}
389
390/// Iterator type that yields each square in a bitboard through efficient generation.
391pub struct BitboardSquareIterator {
392    bb: Bitboard,
393}
394
395impl Iterator for BitboardSquareIterator {
396    type Item = Square;
397    fn next(&mut self) -> Option<Self::Item> {
398        let maybe_square = self.bb.get_lowest_square();
399        self.bb.clear_lowest_square();
400        maybe_square
401    }
402    fn size_hint(&self) -> (usize, Option<usize>) {
403        let size = self.bb.count_squares() as usize;
404        (size, Some(size))
405    }
406}
407impl ExactSizeIterator for BitboardSquareIterator {}
408
409/// Allow the squares of a Bitboard to be iterated directly and cheaply.
410impl IntoIterator for Bitboard {
411    type Item = Square;
412    type IntoIter = BitboardSquareIterator;
413    fn into_iter(self) -> Self::IntoIter {
414        BitboardSquareIterator { bb: self }
415    }
416}
417
418#[cfg(test)]
419mod tests {
420    use super::*;
421
422    #[test]
423    fn from_square_indexable() {
424        let a1 = Bitboard::from(Square::A1);
425        let a2 = Bitboard::from(Square::A2);
426        let a4 = Bitboard::from(Square::A4);
427        let a8 = Bitboard::from(Square::A8);
428        let d3 = Bitboard::from(Square::D3);
429        let h8 = Bitboard::from(Square::H8);
430        assert!(a1.has_square(Square::A1));
431        assert!(a2.has_square(Square::A2));
432        assert!(a4.has_square(Square::A4));
433        assert!(a8.has_square(Square::A8));
434        assert!(d3.has_square(Square::D3));
435        assert!(h8.has_square(Square::H8));
436        assert_eq!(a1.count_squares(), 1);
437        assert_eq!(a2.count_squares(), 1);
438        assert_eq!(a4.count_squares(), 1);
439        assert_eq!(a8.count_squares(), 1);
440        assert_eq!(d3.count_squares(), 1);
441        assert_eq!(h8.count_squares(), 1);
442    }
443
444    #[test]
445    fn from_square_indexable_slice() {
446        let slice1 = vec![A1, A2, A3];
447        let bb = Bitboard::from(slice1.as_slice());
448        assert_eq!(bb.count_squares(), 3);
449        assert!(bb.has_square(A1));
450        assert!(bb.has_square(A2));
451        assert!(bb.has_square(A3));
452    }
453
454    #[test]
455    fn to_north_west_south_east() {
456        let a1 = Bitboard::from(Square::A1);
457
458        let a2 = a1.to_north();
459        let b1 = a1.to_east();
460        let empty1 = a1.to_south();
461        let empty2 = a1.to_west();
462
463        assert_eq!(a2.count_squares(), 1);
464        assert_eq!(b1.count_squares(), 1);
465        assert_eq!(empty1.count_squares(), 0);
466        assert_eq!(empty2.count_squares(), 0);
467        assert!(a2.has_square(Square::A2));
468        assert!(b1.has_square(Square::B1));
469        assert!(empty1 == Bitboard::EMPTY);
470        assert!(empty2 == Bitboard::EMPTY);
471
472        let empty3 = a1.to_south().to_east().to_east();
473        let empty4 = a1.to_south().to_south().to_east();
474        let empty5 = a1.to_south().to_south().to_west();
475        let empty6 = a1.to_south().to_west().to_west();
476        let empty7 = a1.to_north().to_west().to_west();
477        let empty8 = a1.to_north().to_north().to_west();
478        assert_eq!(empty3.count_squares(), 0);
479        assert_eq!(empty4.count_squares(), 0);
480        assert_eq!(empty5.count_squares(), 0);
481        assert_eq!(empty6.count_squares(), 0);
482        assert_eq!(empty7.count_squares(), 0);
483        assert_eq!(empty8.count_squares(), 0);
484        assert!(empty3 == Bitboard::EMPTY);
485        assert!(empty4 == Bitboard::EMPTY);
486        assert!(empty5 == Bitboard::EMPTY);
487        assert!(empty6 == Bitboard::EMPTY);
488        assert!(empty7 == Bitboard::EMPTY);
489        assert!(empty8 == Bitboard::EMPTY);
490    }
491    #[test]
492    fn to_east_west_wrapping() {
493        // Test that a sideways move does not wrap to another rank.
494        let a4 = Bitboard::from(Square::A4);
495        let h4 = Bitboard::from(Square::H4);
496        assert_eq!(a4.to_west(), Bitboard::EMPTY);
497        assert_eq!(h4.to_east(), Bitboard::EMPTY);
498    }
499
500    #[test]
501    fn bb_from_shifts() {
502        let rank_1: u64 = 0x00000000000000FF;
503        let rank_8: u64 = 0xFF00000000000000;
504        assert_eq!(Bitboard::RANK_1.0, rank_1);
505        assert_eq!(Bitboard::RANK_8.0, rank_8);
506    }
507
508    #[test]
509    fn iterate_bitboard() {
510        let bb = Bitboard::FILE_A;
511        let vec: Vec<Square> = bb.into_iter().collect();
512        for square in [A1, A2, A3, A4, A5, A6, A7, A8] {
513            assert!(vec.contains(&square));
514        }
515
516        let mut empty = Bitboard::EMPTY.into_iter();
517        assert_eq!(empty.len(), 0);
518        assert_eq!(empty.next(), None);
519
520        let empty_vec: Vec<Square> = empty.into_iter().collect();
521        assert_eq!(empty_vec.len(), 0);
522    }
523}
blunders_engine/bitboard.rs

blunders_engine/
bitboard.rs
