myopic_core/bitboard/
mod.rs

1use std::{fmt, ops};
2
3use itertools::Itertools;
4
5use crate::bitboard::iterator::BitBoardIterator;
6use crate::square::Square::H1;
7use crate::{Dir, Square};
8use std::iter::FromIterator;
9
10pub mod constants;
11mod cords;
12mod iterator;
13
14/// A bitboard is a value type wrapping a 64 bit integer which represents
15/// a set of squares on a chess board. Each bit is mapped to a particular
16/// square on the board, 0 -> H1, 1 -> G1,..., 8 -> H2,..., 63 -> A8. For
17/// example if we know a piece to reside on a particular square we can
18/// use a bitboard to to capture the available moves for that piece.
19#[derive(Copy, Clone, PartialEq, Ord, PartialOrd, Eq, Hash)]
20pub struct BitBoard(pub u64);
21impl BitBoard {
22    /// Check if this bitboard contains a particular square.
23    pub fn contains(self, square: Square) -> bool {
24        self.0 & (1u64 << (square as u64)) != 0
25    }
26
27    /// Check if this set is a superset of the other.
28    pub fn subsumes(self, other: BitBoard) -> bool {
29        (other - self).is_empty()
30    }
31
32    /// Check if this bitboard is empty, i.e contains no squares.
33    pub fn is_empty(self) -> bool {
34        self.0 == 0
35    }
36
37    /// Check if this bitboard contains at least one square.
38    pub fn is_populated(self) -> bool {
39        self.0 != 0
40    }
41
42    /// Check if the intersection of this bitboard and the other is
43    /// non-empty.
44    pub fn intersects(self, other: BitBoard) -> bool {
45        !(self & other).is_empty()
46    }
47
48    /// Computes the number of squares in this bitboard using the
49    /// popcount algorithm.
50    pub fn size(self) -> usize {
51        self.0.count_ones() as usize
52    }
53
54    pub fn iter(self) -> impl Iterator<Item = Square> {
55        self.into_iter()
56    }
57
58    /// Finds the first square in this set if it is non-empty.
59    pub fn first(self) -> Option<Square> {
60        self.into_iter().next()
61    }
62
63    /// Returns a bitboard with the least set bit of this bitboard
64    /// or nothing if this bitboard is empty.
65    pub fn least_set_bit(self) -> BitBoard {
66        let trailing = self.0.trailing_zeros();
67        if trailing == 64 {
68            BitBoard::EMPTY
69        } else {
70            BitBoard(1u64 << trailing)
71        }
72    }
73
74    /// Computes the 'cord' between two squares. Imagine a queen sat
75    /// on the source square on and empty board. If the queen can move
76    /// to the target square then this method returns the set of
77    /// squares which the queen slides along to get to this target
78    /// square (inclusive of both ends) otherwise the empty bitboard
79    /// is returned.
80    pub fn cord(source: Square, target: Square) -> BitBoard {
81        cords::get_cord(source, target)
82    }
83
84    /// The empty bitboard (set of no squares).
85    pub const EMPTY: BitBoard = BitBoard(0u64);
86    /// The complete bitboard (set of all squares).
87    pub const ALL: BitBoard = BitBoard(!0u64);
88
89    /// Array of bitboards represented the eight ranks, ordered 1 to 8.
90    pub const RANKS: [BitBoard; 8] = [
91        BitBoard(255),
92        BitBoard(65280),
93        BitBoard(16711680),
94        BitBoard(4278190080),
95        BitBoard(1095216660480),
96        BitBoard(280375465082880),
97        BitBoard(71776119061217280),
98        BitBoard(18374686479671623680),
99    ];
100
101    /// Array of bitboards represented the eight files, ordered H to A.
102    pub const FILES: [BitBoard; 8] = [
103        BitBoard(72340172838076673),
104        BitBoard(144680345676153346),
105        BitBoard(289360691352306692),
106        BitBoard(578721382704613384),
107        BitBoard(1157442765409226768),
108        BitBoard(2314885530818453536),
109        BitBoard(4629771061636907072),
110        BitBoard(9259542123273814144),
111    ];
112}
113
114/// A bitboard is a set of squares and is therefore iterable.
115impl IntoIterator for BitBoard {
116    type Item = Square;
117    type IntoIter = BitBoardIterator;
118    fn into_iter(self) -> Self::IntoIter {
119        BitBoardIterator(self.0)
120    }
121}
122
123/// A set of squares can be built from an iterator traversing squares.
124impl FromIterator<Square> for BitBoard {
125    fn from_iter<I: IntoIterator<Item = Square>>(iter: I) -> Self {
126        iter.into_iter().fold(BitBoard::EMPTY, |a, b| a | b)
127    }
128}
129
130/// We can collect an iterator of bitboards into a single bitboard under
131/// the logical OR binary operator on sets.
132impl FromIterator<BitBoard> for BitBoard {
133    fn from_iter<I: IntoIterator<Item = BitBoard>>(iter: I) -> Self {
134        iter.into_iter().fold(BitBoard::EMPTY, |a, b| a | b)
135    }
136}
137
138/// Operator implementations for bitboards which all use the underlying u64
139/// value.
140impl ops::Shr<u8> for BitBoard {
141    type Output = Self;
142    fn shr(self, shift: u8) -> Self {
143        BitBoard(self.0 >> shift as u64)
144    }
145}
146
147impl ops::Shl<u8> for BitBoard {
148    type Output = Self;
149    fn shl(self, shift: u8) -> Self {
150        BitBoard(self.0 << shift as u64)
151    }
152}
153
154impl ops::Not for BitBoard {
155    type Output = Self;
156    fn not(self) -> Self {
157        BitBoard(!self.0)
158    }
159}
160
161impl ops::Sub<BitBoard> for BitBoard {
162    type Output = Self;
163    fn sub(self, other: BitBoard) -> Self {
164        BitBoard(self.0 & !other.0)
165    }
166}
167
168impl ops::Sub<Square> for BitBoard {
169    type Output = Self;
170    fn sub(self, other: Square) -> Self {
171        BitBoard(self.0 & !loc(other))
172    }
173}
174
175impl ops::BitXor<BitBoard> for BitBoard {
176    type Output = Self;
177    fn bitxor(self, other: BitBoard) -> Self {
178        BitBoard(self.0 ^ other.0)
179    }
180}
181
182impl ops::BitXor<Square> for BitBoard {
183    type Output = Self;
184    fn bitxor(self, rhs: Square) -> Self {
185        BitBoard(self.0 ^ loc(rhs))
186    }
187}
188
189impl ops::BitOr<BitBoard> for BitBoard {
190    type Output = Self;
191    fn bitor(self, other: BitBoard) -> Self {
192        BitBoard(self.0 | other.0)
193    }
194}
195
196impl ops::BitOr<Square> for BitBoard {
197    type Output = Self;
198    fn bitor(self, other: Square) -> Self {
199        BitBoard(self.0 | loc(other))
200    }
201}
202
203impl ops::BitAnd<BitBoard> for BitBoard {
204    type Output = Self;
205    fn bitand(self, other: BitBoard) -> Self {
206        BitBoard(self.0 & other.0)
207    }
208}
209
210impl ops::BitAnd<Square> for BitBoard {
211    type Output = Self;
212    fn bitand(self, other: Square) -> Self {
213        BitBoard(self.0 & loc(other))
214    }
215}
216
217impl ops::BitXorAssign<BitBoard> for BitBoard {
218    fn bitxor_assign(&mut self, rhs: BitBoard) {
219        self.0 = self.0 ^ rhs.0;
220    }
221}
222
223impl ops::BitXorAssign<Square> for BitBoard {
224    fn bitxor_assign(&mut self, rhs: Square) {
225        self.0 = self.0 ^ (1u64 << (rhs as u64));
226    }
227}
228
229impl ops::BitOrAssign<BitBoard> for BitBoard {
230    fn bitor_assign(&mut self, rhs: BitBoard) {
231        self.0 = self.0 | rhs.0;
232    }
233}
234
235impl ops::BitOrAssign<Square> for BitBoard {
236    fn bitor_assign(&mut self, rhs: Square) {
237        self.0 = self.0 | (1u64 << (rhs as u64));
238    }
239}
240
241impl fmt::Debug for BitBoard {
242    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
243        write!(f, "{{{}}}", self.into_iter().join(", "))
244    }
245}
246
247impl fmt::Display for BitBoard {
248    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
249        write!(f, "{{{}}}", self.into_iter().join(", "))
250    }
251}
252
253fn loc(sq: Square) -> u64 {
254    1u64 << (sq as u64)
255}
256
257#[allow(dead_code)]
258fn create_files() -> Vec<BitBoard> {
259    (H1.search(Dir::W) | H1)
260        .into_iter()
261        .map(|sq| sq.search(Dir::N) | sq)
262        .collect()
263}
264
265#[allow(dead_code)]
266fn create_ranks() -> Vec<BitBoard> {
267    (H1.search(Dir::N) | H1)
268        .into_iter()
269        .map(|sq| sq.search(Dir::W) | sq)
270        .collect()
271}
272
273#[cfg(test)]
274mod test {
275    use crate::bitboard::BitBoard;
276    use crate::square::Square::*;
277
278    use super::*;
279
280    #[test]
281    fn test_from_square_iter() {
282        assert_eq!(F1 | G6, vec!(F1, G6).into_iter().collect());
283    }
284
285    #[test]
286    fn test_into_iter() {
287        assert_eq!(vec![F1, G6], (F1 | G6).into_iter().collect::<Vec<Square>>());
288    }
289
290    #[test]
291    fn test_display() {
292        let result = A1 | H7 | D5;
293        assert_eq!("{a1, d5, h7}".to_owned(), format!("{}", result));
294    }
295
296    #[test]
297    fn test_size() {
298        assert_eq!(0, BitBoard::EMPTY.size());
299        assert_eq!(64, BitBoard::ALL.size());
300        assert_eq!(3, (A3 | G6 | H4).size());
301    }
302
303    #[test]
304    fn test_create_files() {
305        assert_eq!(H1 | H2 | H3 | H4 | H5 | H6 | H7 | H8, create_files()[0]);
306    }
307
308    #[test]
309    fn test_create_ranks() {
310        assert_eq!(A3 | B3 | C3 | D3 | E3 | F3 | G3 | H3, create_ranks()[2]);
311    }
312
313    #[test]
314    fn test_lsb() {
315        assert_eq!(BitBoard::EMPTY, BitBoard::EMPTY.least_set_bit());
316        assert_eq!(G1.lift(), (E4 | G1).least_set_bit());
317        assert_eq!(E3.lift(), (E3 | G5).least_set_bit());
318        assert_eq!(A8.lift(), A8.lift().least_set_bit());
319    }
320}
myopic_core/bitboard/mod.rs

myopic_core/bitboard/
mod.rs
