cozy_chess_types/bitboard.rs
1use crate::{Square, File, Rank};
2
3use core::ops::*;
4
5/// A [bitboard](https://www.chessprogramming.org/Bitboards).
6/// A bitboard is an ordered set of squares.
7///
8/// Operators are overloaded to work as set operations accordingly:
9/// ```
10/// # use cozy_chess_types::*;
11/// let a1 = Square::A1.bitboard();
12/// let b1 = Square::B1.bitboard();
13/// let c1 = Square::C1.bitboard();
14/// let x = a1 | b1;
15/// let y = a1 | c1;
16/// // Union
17/// assert_eq!(x | y, a1 | b1 | c1);
18/// // Intersection
19/// assert_eq!(x & y, a1);
20/// // Symmetric difference
21/// assert_eq!(x ^ y, b1 | c1);
22/// // Difference
23/// assert_eq!(x - y, b1);
24/// // Complement
25/// assert_eq!(!x, BitBoard::FULL - x);
26/// ```
27#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default, Hash)]
28pub struct BitBoard(
29 /// The backing [`u64`]. A square is present in the set if the bit at `1 << square as u8` is set.
30 pub u64
31);
32
33macro_rules! impl_math_ops {
34 ($($trait:ident, $fn:ident;)*) => {$(
35 impl $trait for BitBoard {
36 type Output = Self;
37
38 #[inline(always)]
39 fn $fn(self, rhs: Self) -> Self::Output {
40 Self($trait::$fn(self.0, rhs.0))
41 }
42 }
43 )*};
44}
45impl_math_ops! {
46 BitAnd, bitand;
47 BitOr, bitor;
48 BitXor, bitxor;
49}
50
51macro_rules! impl_math_assign_ops {
52 ($($trait:ident, $fn:ident;)*) => {$(
53 impl $trait for BitBoard {
54 #[inline(always)]
55 fn $fn(&mut self, rhs: Self) {
56 $trait::$fn(&mut self.0, rhs.0)
57 }
58 }
59 )*};
60}
61impl_math_assign_ops! {
62 BitAndAssign, bitand_assign;
63 BitOrAssign, bitor_assign;
64 BitXorAssign, bitxor_assign;
65}
66
67impl Sub for BitBoard {
68 type Output = Self;
69
70 #[inline(always)]
71 fn sub(self, rhs: Self) -> Self::Output {
72 self & !rhs
73 }
74}
75
76impl SubAssign for BitBoard {
77
78 #[inline(always)]
79 fn sub_assign(&mut self, rhs: Self) {
80 *self = *self - rhs;
81 }
82}
83
84impl Not for BitBoard {
85 type Output = Self;
86
87 #[inline(always)]
88 fn not(self) -> Self::Output {
89 Self(!self.0)
90 }
91}
92
93macro_rules! impl_convert {
94 ($($type:ty),*) => {$(
95 impl From<$type> for BitBoard {
96 fn from(value: $type) -> Self {
97 value.bitboard()
98 }
99 }
100 )*};
101}
102impl_convert!(File, Rank, Square);
103
104// Rustdoc currently has a bug where it attempts to guess how to display a constant for some reason.
105// This has the amazing effect of expanding the `bitboard!` macro's implementation,
106// making the docs completely unreadable. This is why constants defined with `bitboard!` use two constants.
107// Relevant issues:
108// https://github.com/rust-lang/rust/issues/99630
109// https://github.com/rust-lang/rust/issues/98929
110
111impl BitBoard {
112 /// An empty bitboard.
113 /// # Examples
114 /// ```
115 /// # use cozy_chess_types::*;
116 /// assert_eq!(BitBoard::EMPTY, bitboard! {
117 /// . . . . . . . .
118 /// . . . . . . . .
119 /// . . . . . . . .
120 /// . . . . . . . .
121 /// . . . . . . . .
122 /// . . . . . . . .
123 /// . . . . . . . .
124 /// . . . . . . . .
125 /// });
126 /// ```
127 pub const EMPTY: Self = Self(0);
128
129 /// A bitboard with every square.
130 /// # Examples
131 /// ```
132 /// # use cozy_chess_types::*;
133 /// assert_eq!(BitBoard::FULL, bitboard! {
134 /// X X X X X X X X
135 /// X X X X X X X X
136 /// X X X X X X X X
137 /// X X X X X X X X
138 /// X X X X X X X X
139 /// X X X X X X X X
140 /// X X X X X X X X
141 /// X X X X X X X X
142 /// });
143 /// ```
144 pub const FULL: Self = Self(!0);
145
146 /// The edges on the board.
147 /// # Examples
148 /// ```
149 /// # use cozy_chess_types::*;
150 /// assert_eq!(BitBoard::EDGES, bitboard! {
151 /// X X X X X X X X
152 /// X . . . . . . X
153 /// X . . . . . . X
154 /// X . . . . . . X
155 /// X . . . . . . X
156 /// X . . . . . . X
157 /// X . . . . . . X
158 /// X X X X X X X X
159 /// });
160 /// ```
161 pub const EDGES: Self = Self::__EDGES;
162 const __EDGES: Self = bitboard! {
163 X X X X X X X X
164 X . . . . . . X
165 X . . . . . . X
166 X . . . . . . X
167 X . . . . . . X
168 X . . . . . . X
169 X . . . . . . X
170 X X X X X X X X
171 };
172
173 /// The corners of the board.
174 /// # Examples
175 /// ```
176 /// # use cozy_chess_types::*;
177 /// assert_eq!(BitBoard::CORNERS, bitboard! {
178 /// X . . . . . . X
179 /// . . . . . . . .
180 /// . . . . . . . .
181 /// . . . . . . . .
182 /// . . . . . . . .
183 /// . . . . . . . .
184 /// . . . . . . . .
185 /// X . . . . . . X
186 /// });
187 /// ```
188 pub const CORNERS: Self = Self::__CORNERS;
189 const __CORNERS: Self = bitboard! {
190 X . . . . . . X
191 . . . . . . . .
192 . . . . . . . .
193 . . . . . . . .
194 . . . . . . . .
195 . . . . . . . .
196 . . . . . . . .
197 X . . . . . . X
198 };
199
200 /// The dark squares on the board.
201 /// # Examples
202 /// ```
203 /// # use cozy_chess_types::*;
204 /// assert_eq!(BitBoard::DARK_SQUARES, bitboard! {
205 /// . X . X . X . X
206 /// X . X . X . X .
207 /// . X . X . X . X
208 /// X . X . X . X .
209 /// . X . X . X . X
210 /// X . X . X . X .
211 /// . X . X . X . X
212 /// X . X . X . X .
213 /// });
214 /// ```
215 pub const DARK_SQUARES: Self = Self::__DARK_SQUARES;
216 const __DARK_SQUARES: Self = bitboard! {
217 . X . X . X . X
218 X . X . X . X .
219 . X . X . X . X
220 X . X . X . X .
221 . X . X . X . X
222 X . X . X . X .
223 . X . X . X . X
224 X . X . X . X .
225 };
226
227 /// The light squares on the board.
228 /// # Examples
229 /// ```
230 /// # use cozy_chess_types::*;
231 /// assert_eq!(BitBoard::LIGHT_SQUARES, bitboard! {
232 /// X . X . X . X .
233 /// . X . X . X . X
234 /// X . X . X . X .
235 /// . X . X . X . X
236 /// X . X . X . X .
237 /// . X . X . X . X
238 /// X . X . X . X .
239 /// . X . X . X . X
240 /// });
241 /// ```
242 pub const LIGHT_SQUARES: Self = Self::__LIGHT_SQUARES;
243 const __LIGHT_SQUARES: Self = bitboard! {
244 X . X . X . X .
245 . X . X . X . X
246 X . X . X . X .
247 . X . X . X . X
248 X . X . X . X .
249 . X . X . X . X
250 X . X . X . X .
251 . X . X . X . X
252 };
253
254 /// Sus.
255 /// # Examples
256 /// ```
257 /// # use cozy_chess_types::*;
258 /// assert_eq!(BitBoard::AMOGUS, bitboard! {
259 /// . . . . . . . .
260 /// . . . . . . . .
261 /// . . X X X . . .
262 /// . . X . X X . .
263 /// . . X X X X . .
264 /// . . X . X . . .
265 /// . . . . . . . .
266 /// . . . . . . . .
267 /// });
268 /// ```
269 #[doc(hidden)]
270 pub const AMOGUS: Self = bitboard! {
271 . . . . . . . .
272 . . . . . . . .
273 . . X X X . . .
274 . . X . X X . .
275 . . X X X X . .
276 . . X . X . . .
277 . . . . . . . .
278 . . . . . . . .
279 };
280
281 /// Flip the bitboard's ranks.
282 /// # Examples
283 /// ```
284 /// # use cozy_chess_types::*;
285 /// let bb = bitboard! {
286 /// . . . . . . . .
287 /// . . . . . . . .
288 /// . . X X X . . .
289 /// . . X . X X . .
290 /// . . X X X X . .
291 /// . . X . X . . .
292 /// . . . . . . . .
293 /// . . . . . . . .
294 /// };
295 /// assert_eq!(bb.flip_ranks(), bitboard! {
296 /// . . . . . . . .
297 /// . . . . . . . .
298 /// . . X . X . . .
299 /// . . X X X X . .
300 /// . . X . X X . .
301 /// . . X X X . . .
302 /// . . . . . . . .
303 /// . . . . . . . .
304 /// });
305 /// ```
306 #[inline(always)]
307 pub const fn flip_ranks(self) -> Self {
308 Self(self.0.swap_bytes())
309 }
310
311 /// Flip the bitboard's files.
312 /// # Examples
313 /// ```
314 /// # use cozy_chess_types::*;
315 /// let bb = bitboard! {
316 /// . . . . . . . .
317 /// . . . . . . . .
318 /// . . X X X . . .
319 /// . . X . X X . .
320 /// . . X X X X . .
321 /// . . X . X . . .
322 /// . . . . . . . .
323 /// . . . . . . . .
324 /// };
325 /// assert_eq!(bb.flip_files(), bitboard! {
326 /// . . . . . . . .
327 /// . . . . . . . .
328 /// . . . X X X . .
329 /// . . X X . X . .
330 /// . . X X X X . .
331 /// . . . X . X . .
332 /// . . . . . . . .
333 /// . . . . . . . .
334 /// });
335 /// ```
336 #[inline(always)]
337 pub const fn flip_files(self) -> Self {
338 // https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating#Horizontal
339 const K1: u64 = 0x5555555555555555;
340 const K2: u64 = 0x3333333333333333;
341 const K4: u64 = 0x0F0F0F0F0F0F0F0F;
342 let mut new = self.0;
343 new = ((new >> 1) & K1) | ((new & K1) << 1);
344 new = ((new >> 2) & K2) | ((new & K2) << 2);
345 new = ((new >> 4) & K4) | ((new & K4) << 4);
346 Self(new)
347 }
348
349 /// Count the number of squares in the bitboard.
350 /// # Examples
351 /// ```
352 /// # use cozy_chess_types::*;
353 /// assert_eq!(BitBoard::EMPTY.len(), 0);
354 /// let bb = bitboard! {
355 /// . . . . . . . .
356 /// . . . . . . . .
357 /// . . X X X . . .
358 /// . . X . X X . .
359 /// . . X X X X . .
360 /// . . X . X . . .
361 /// . . . . . . . .
362 /// . . . . . . . .
363 /// };
364 /// assert_eq!(bb.len(), 12);
365 /// ```
366 #[inline(always)]
367 pub const fn len(self) -> u32 {
368 self.0.count_ones()
369 }
370
371 /// Check if a [`Square`] is set.
372 /// # Examples
373 /// ```
374 /// # use cozy_chess_types::*;
375 /// let bb = bitboard! {
376 /// . . . . . . . .
377 /// . . . . . . . .
378 /// . . X X X . . .
379 /// . . X . X X . .
380 /// . . X X X X . .
381 /// . . X . X . . .
382 /// . . . . . . . .
383 /// . . . . . . . .
384 /// };
385 /// assert!(bb.has(Square::C3));
386 /// assert!(!bb.has(Square::B2));
387 /// ```
388 #[inline(always)]
389 pub const fn has(self, square: Square) -> bool {
390 !self.is_disjoint(square.bitboard())
391 }
392
393 /// Check if a bitboard contains no squares in common with another.
394 /// # Examples
395 /// ```
396 /// # use cozy_chess_types::*;
397 /// let bb_a = bitboard! {
398 /// X X X . . . . .
399 /// X . X X . . . .
400 /// X X X X . . . .
401 /// X . X . . . . .
402 /// . . . . . . . .
403 /// . . . . . . . .
404 /// . . . . . . . .
405 /// . . . . . . . .
406 /// };
407 /// let bb_b = bitboard! {
408 /// . . . . . . . .
409 /// . . . . . . . .
410 /// . . . . . . . .
411 /// . . . . . . . .
412 /// . . . . X X X .
413 /// . . . . X . X X
414 /// . . . . X X X X
415 /// . . . . X . X .
416 /// };
417 /// assert!(bb_a.is_disjoint(bb_b));
418 /// ```
419 #[inline(always)]
420 pub const fn is_disjoint(self, other: BitBoard) -> bool {
421 self.0 & other.0 == Self::EMPTY.0
422 }
423
424 /// Check if a bitboard is a subset of another.
425 /// # Examples
426 /// ```
427 /// # use cozy_chess_types::*;
428 /// let bb = bitboard! {
429 /// . . . . . . . .
430 /// . X X X X X . .
431 /// . X X X X X X .
432 /// . X X . X X X .
433 /// . X X X X X X .
434 /// . X X X X X . .
435 /// . X X . X X . .
436 /// . . . . . . . .
437 /// };
438 /// let subset = bitboard! {
439 /// . . . . . . . .
440 /// . . . . . . . .
441 /// . . X X X . . .
442 /// . . X . X X . .
443 /// . . X X X X . .
444 /// . . X . X . . .
445 /// . . . . . . . .
446 /// . . . . . . . .
447 /// };
448 /// assert!(subset.is_subset(bb));
449 /// ```
450 #[inline(always)]
451 pub const fn is_subset(self, other: BitBoard) -> bool {
452 other.0 & self.0 == self.0
453 }
454
455 /// Check if a bitboard is a superset of another.
456 /// # Examples
457 /// ```
458 /// # use cozy_chess_types::*;
459 /// let bb = bitboard! {
460 /// . . . . . . . .
461 /// . . . . . . . .
462 /// . . X X X . . .
463 /// . . X . X X . .
464 /// . . X X X X . .
465 /// . . X . X . . .
466 /// . . . . . . . .
467 /// . . . . . . . .
468 /// };
469 /// let superset = bitboard! {
470 /// . . . . . . . .
471 /// . X X X X X . .
472 /// . X X X X X X .
473 /// . X X . X X X .
474 /// . X X X X X X .
475 /// . X X X X X . .
476 /// . X X . X X . .
477 /// . . . . . . . .
478 /// };
479 /// assert!(superset.is_superset(bb));
480 /// ```
481 #[inline(always)]
482 pub const fn is_superset(self, other: BitBoard) -> bool {
483 other.is_subset(self)
484 }
485
486 /// Checks if the [`BitBoard`] is empty.
487 /// # Examples
488 /// ```
489 /// # use cozy_chess_types::*;
490 /// assert!(BitBoard::EMPTY.is_empty());
491 /// let bb = bitboard! {
492 /// . . . . . . . .
493 /// . . . . . . . .
494 /// . . X X X . . .
495 /// . . X . X X . .
496 /// . . X X X X . .
497 /// . . X . X . . .
498 /// . . . . . . . .
499 /// . . . . . . . .
500 /// };
501 /// assert!(!bb.is_empty());
502 /// ```
503 #[inline(always)]
504 pub const fn is_empty(self) -> bool {
505 self.0 == Self::EMPTY.0
506 }
507
508 /// Grabs the first square if the bitboard is not empty.
509 /// # Examples
510 /// ```
511 /// # use cozy_chess_types::*;
512 /// assert!(BitBoard::EMPTY.next_square().is_none());
513 /// let bb = bitboard! {
514 /// . . . . . . . .
515 /// . . . . . . . .
516 /// . . X X X . . .
517 /// . . X . X X . .
518 /// . . X X X X . .
519 /// . . X . X . . .
520 /// . . . . . . . .
521 /// . . . . . . . .
522 /// };
523 /// assert_eq!(bb.next_square(), Some(Square::C3));
524 /// ```
525 #[inline(always)]
526 pub const fn next_square(self) -> Option<Square> {
527 Square::try_index(self.0.trailing_zeros() as usize)
528 }
529
530 /// Iterate the squares in the bitboard, ordered by square.
531 /// # Examples
532 /// ```
533 /// # use cozy_chess_types::*;
534 /// let bb = BitBoard::FULL;
535 /// let squares = &Square::ALL;
536 /// for (s1, &s2) in bb.iter().zip(squares) {
537 /// assert_eq!(s1, s2);
538 /// }
539 /// ```
540 #[inline(always)]
541 pub fn iter(self) -> BitBoardIter {
542 BitBoardIter(self)
543 }
544
545 /// Iterate all subsets of a bitboard.
546 /// Subsets are produced in lexicographic order; Each subset is greater than the last.
547 /// ```
548 /// # use cozy_chess_types::*;
549 /// let bb = bitboard! {
550 /// . . . . . . . .
551 /// . . . . . . . .
552 /// . . X X X . . .
553 /// . . X . X X . .
554 /// . . X X X X . .
555 /// . . X . X . . .
556 /// . . . . . . . .
557 /// . . . . . . . .
558 /// };
559 /// for subset in bb.iter_subsets() {
560 /// assert!(subset.is_subset(bb));
561 /// }
562 /// ```
563 #[inline(always)]
564 pub fn iter_subsets(self) -> BitBoardSubsetIter {
565 BitBoardSubsetIter {
566 set: self,
567 subset: Self::EMPTY,
568 finished: false
569 }
570 }
571}
572
573impl IntoIterator for BitBoard {
574 type Item = Square;
575
576 type IntoIter = BitBoardIter;
577
578 #[inline(always)]
579 fn into_iter(self) -> Self::IntoIter {
580 self.iter()
581 }
582}
583
584impl FromIterator<Square> for BitBoard {
585 fn from_iter<T: IntoIterator<Item = Square>>(iter: T) -> Self {
586 iter.into_iter().fold(Self::EMPTY, |bb, sq| bb | sq.bitboard())
587 }
588}
589
590/// An iterator over the squares of a bitboard.
591///
592/// This `struct` is created by [`BitBoard::iter`]. See its documentation for more.
593pub struct BitBoardIter(BitBoard);
594
595impl Iterator for BitBoardIter {
596 type Item = Square;
597
598 #[inline(always)]
599 fn next(&mut self) -> Option<Self::Item> {
600 let square = self.0.next_square();
601 if let Some(square) = square {
602 self.0 ^= square.bitboard();
603 }
604 square
605 }
606
607 #[inline(always)]
608 fn size_hint(&self) -> (usize, Option<usize>) {
609 (self.len(), Some(self.len()))
610 }
611}
612
613impl ExactSizeIterator for BitBoardIter {
614 #[inline(always)]
615 fn len(&self) -> usize {
616 self.0.len() as usize
617 }
618}
619
620/// An iterator over the subsets of a bitboard.
621///
622/// This `struct` is created by [`BitBoard::iter_subsets`]. See its documentation for more.
623pub struct BitBoardSubsetIter {
624 set: BitBoard,
625 subset: BitBoard,
626 finished: bool
627}
628
629impl Iterator for BitBoardSubsetIter {
630 type Item = BitBoard;
631
632 #[inline(always)]
633 fn next(&mut self) -> Option<Self::Item> {
634 if self.finished {
635 return None;
636 }
637 let current = self.subset;
638 // Carry-Rippler trick to enumerate all subsets of a set.
639 // https://www.chessprogramming.org/Traversing_Subsets_of_a_Set#All_Subsets_of_any_Set
640 self.subset.0 = self.subset.0.wrapping_sub(self.set.0) & self.set.0;
641 self.finished = self.subset.is_empty();
642 Some(current)
643 }
644}
645
646/// [`BitBoard`] literal macro.
647/// ```
648/// # use cozy_chess_types::*;
649/// let bb = bitboard! {
650/// . . . X . . . .
651/// . . . X . . . .
652/// . . . X . . . .
653/// . . . X . . . .
654/// . . . X . . . .
655/// X X X . X X X X
656/// . . . X . . . .
657/// . . . X . . . .
658/// };
659/// assert_eq!(bb, File::D.bitboard() ^ Rank::Third.bitboard());
660/// ```
661#[macro_export]
662macro_rules! bitboard {
663 (
664 $a8:tt $b8:tt $c8:tt $d8:tt $e8:tt $f8:tt $g8:tt $h8:tt
665 $a7:tt $b7:tt $c7:tt $d7:tt $e7:tt $f7:tt $g7:tt $h7:tt
666 $a6:tt $b6:tt $c6:tt $d6:tt $e6:tt $f6:tt $g6:tt $h6:tt
667 $a5:tt $b5:tt $c5:tt $d5:tt $e5:tt $f5:tt $g5:tt $h5:tt
668 $a4:tt $b4:tt $c4:tt $d4:tt $e4:tt $f4:tt $g4:tt $h4:tt
669 $a3:tt $b3:tt $c3:tt $d3:tt $e3:tt $f3:tt $g3:tt $h3:tt
670 $a2:tt $b2:tt $c2:tt $d2:tt $e2:tt $f2:tt $g2:tt $h2:tt
671 $a1:tt $b1:tt $c1:tt $d1:tt $e1:tt $f1:tt $g1:tt $h1:tt
672 ) => {
673 $crate::bitboard! { @__inner
674 $a1 $b1 $c1 $d1 $e1 $f1 $g1 $h1
675 $a2 $b2 $c2 $d2 $e2 $f2 $g2 $h2
676 $a3 $b3 $c3 $d3 $e3 $f3 $g3 $h3
677 $a4 $b4 $c4 $d4 $e4 $f4 $g4 $h4
678 $a5 $b5 $c5 $d5 $e5 $f5 $g5 $h5
679 $a6 $b6 $c6 $d6 $e6 $f6 $g6 $h6
680 $a7 $b7 $c7 $d7 $e7 $f7 $g7 $h7
681 $a8 $b8 $c8 $d8 $e8 $f8 $g8 $h8
682 }
683 };
684 (@__inner $($occupied:tt)*) => {{
685 const BITBOARD: $crate::BitBoard = {
686 let mut index = 0;
687 let mut bitboard = $crate::BitBoard::EMPTY;
688 $(
689 if $crate::bitboard!(@__square $occupied) {
690 bitboard.0 |= 1 << index;
691 }
692 index += 1;
693 )*
694 let _ = index;
695 bitboard
696 };
697 BITBOARD
698 }};
699 (@__square X) => { true };
700 (@__square .) => { false };
701 (@__square $token:tt) => {
702 compile_error!(
703 concat!(
704 "Expected only `X` or `.` tokens, found `",
705 stringify!($token),
706 "`"
707 )
708 )
709 };
710 ($($token:tt)*) => {
711 compile_error!("Expected 64 squares")
712 };
713}
714pub use bitboard as bitboard;
715
716impl core::fmt::Debug for BitBoard {
717 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
718 if f.alternate() {
719 write!(f, "bitboard! {{")?;
720 for &rank in Rank::ALL.iter().rev() {
721 write!(f, "\n ")?;
722 for &file in &File::ALL {
723 if self.has(Square::new(file, rank)) {
724 write!(f, " X")?;
725 } else {
726 write!(f, " .")?;
727 }
728 }
729 }
730 write!(f, "\n}}")?;
731 Ok(())
732 } else {
733 write!(f, "BitBoard({:#018X})", self.0)
734 }
735 }
736}