haitaka_types/bitboard.rs
1//! A [`BitBoard`] implementation
2use crate::{File, Rank, Square};
3use core::ops::*;
4
5/// A [bitboard](https://www.chessprogramming.org/Bitboards).
6/// A bitboard is an ordered set of squares. The set contains a square if bit `1 << square as usize` is set.
7///
8/// Logical operators are overloaded to work as set operations.
9///
10/// # Examples
11///
12/// ```
13/// # use haitaka_types::*;
14/// let a1 = Square::A1.bitboard();
15/// let b1 = Square::B1.bitboard();
16/// let c1 = Square::C1.bitboard();
17/// let x = a1 | b1;
18/// let y = a1 | c1;
19/// // Union
20/// assert_eq!(x | y, a1 | b1 | c1);
21/// // Intersection
22/// assert_eq!(x & y, a1);
23/// // Symmetric difference
24/// assert_eq!(x ^ y, b1 | c1);
25/// ```
26#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default, Hash)]
27pub struct BitBoard(
28 /// The backing [`u128`].
29 pub u128,
30);
31
32macro_rules! impl_math_ops {
33 ($($trait:ident, $fn:ident;)*) => {$(
34 impl $trait for BitBoard {
35 type Output = Self;
36
37 #[inline(always)]
38 fn $fn(self, rhs: Self) -> Self::Output {
39 self.$fn(rhs)
40 }
41 }
42 )*};
43}
44impl_math_ops! {
45 BitAnd, bitand;
46 BitOr, bitor;
47 BitXor, bitxor;
48}
49
50macro_rules! impl_math_assign_ops {
51 ($($trait:ident, $fn:ident;)*) => {$(
52 impl $trait for BitBoard {
53 #[inline(always)]
54 fn $fn(&mut self, rhs: Self) {
55 $trait::$fn(&mut self.0, rhs.0)
56 }
57 }
58 )*};
59}
60impl_math_assign_ops! {
61 BitAndAssign, bitand_assign;
62 BitOrAssign, bitor_assign;
63 BitXorAssign, bitxor_assign;
64}
65
66impl Sub for BitBoard {
67 type Output = Self;
68
69 /// Calculate the set difference (a - b).
70 #[inline(always)]
71 fn sub(self, rhs: Self) -> Self::Output {
72 self & !rhs
73 }
74}
75
76impl SubAssign for BitBoard {
77 #[inline(always)]
78 fn sub_assign(&mut self, rhs: Self) {
79 *self = *self - rhs;
80 }
81}
82
83impl Not for BitBoard {
84 type Output = Self;
85
86 #[inline(always)]
87 fn not(self) -> Self::Output {
88 self.not()
89 }
90}
91
92impl Shl<usize> for BitBoard {
93 type Output = BitBoard;
94
95 #[inline(always)]
96 fn shl(self, rhs: usize) -> BitBoard {
97 self.shl(rhs)
98 }
99}
100
101impl Shr<usize> for BitBoard {
102 type Output = BitBoard;
103
104 #[inline(always)]
105 fn shr(self, rhs: usize) -> BitBoard {
106 self.shr(rhs)
107 }
108}
109
110// Convert File, Rank or Square to BitBoard
111macro_rules! impl_convert {
112 ($($type:ty),*) => {$(
113 impl From<$type> for BitBoard {
114 fn from(value: $type) -> Self {
115 value.bitboard()
116 }
117 }
118 )*};
119}
120impl_convert!(File, Rank, Square);
121
122//
123// Logical operators and shifts implemented as `const` functions.
124//
125impl BitBoard {
126 /// Invert all bits of this bitboard.
127 #[inline(always)]
128 pub const fn not(self) -> Self {
129 Self(!self.0 & BitBoard::BOARD_MASK)
130 }
131
132 /// Return the intersection of two bitboards.
133 #[inline(always)]
134 pub const fn bitand(self, rhs: Self) -> Self {
135 Self(self.0 & rhs.0)
136 }
137
138 /// Return the union of two bitboards.
139 #[inline(always)]
140 pub const fn bitor(self, rhs: Self) -> Self {
141 Self(self.0 | rhs.0)
142 }
143
144 /// Return the symmetric set difference (xor) of two bitboards.
145 #[inline(always)]
146 pub const fn bitxor(self, rhs: Self) -> Self {
147 Self(self.0 ^ rhs.0)
148 }
149
150 /// Decrement. Substracts 1 from the internal u128.
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// # use haitaka_types::*;
156 /// assert_eq!(BitBoard::EMPTY.dec(), BitBoard::FULL);
157 /// assert_eq!(Square::A1.bitboard().dec(), BitBoard::EMPTY);
158 /// assert_eq!(Square::A2.bitboard().dec(), BitBoard(0x1FF));
159 /// ```
160 #[inline(always)]
161 pub const fn dec(self) -> Self {
162 Self::new(self.0.wrapping_sub(1))
163 }
164
165 /// Shift left along files ("down" the board towards rank I).
166 ///
167 /// # Example
168 /// ```
169 /// # use haitaka_types::*;
170 /// let bb1 = bitboard! {
171 /// . . . . . . X X X
172 /// . . . . . . X . X
173 /// . . . . . . X X X
174 /// . . . . . . . . .
175 /// . . . . . . . . .
176 /// . . . . . . . . .
177 /// X X X . . . . . .
178 /// X . X . . . . . .
179 /// X X X . . . . . .
180 /// };
181 /// let bb2 = bitboard! {
182 /// . . . . . . . . .
183 /// . . . . . . X X X
184 /// . . . . . . X . X
185 /// . . . . . . X X X
186 /// . . . . . . . . .
187 /// . . . . . . . . .
188 /// . . . . . . . . .
189 /// X X X . . . . . .
190 /// X . X . . . . . .
191 /// };
192 /// assert_eq!(bb1.shl(1), bb2);
193 /// ```
194 #[inline(always)]
195 pub const fn shl(self, rhs: usize) -> Self {
196 if rhs == 0 {
197 self
198 } else if rhs >= 9 {
199 BitBoard::EMPTY
200 } else {
201 BitBoard::new((self.0 << rhs) & Rank::SOUTH[rhs - 1].0)
202 }
203 }
204
205 /// Shift right along files ("up" the board towards rank A).
206 ///
207 /// # Example
208 ///
209 /// ```
210 /// # use haitaka_types::*;
211 /// let bb1 = bitboard! {
212 /// . . . . . . X X X
213 /// . . . . . . X . X
214 /// . . . . . . X X X
215 /// . . . . . . . . .
216 /// . . . . . . . . .
217 /// . . . . . . . . .
218 /// X X X . . . . . .
219 /// X . X . . . . . .
220 /// X X X . . . . . .
221 /// };
222 /// let bb2 = bitboard! {
223 /// . . . . . . X . X
224 /// . . . . . . X X X
225 /// . . . . . . . . .
226 /// . . . . . . . . .
227 /// . . . . . . . . .
228 /// X X X . . . . . .
229 /// X . X . . . . . .
230 /// X X X . . . . . .
231 /// . . . . . . . . .
232 /// };
233 /// assert_eq!(bb1.shr(1), bb2);
234 /// assert_eq!(bb1.shr(9), BitBoard::EMPTY);
235 /// ```
236 #[inline(always)]
237 pub const fn shr(self, rhs: usize) -> Self {
238 if rhs == 0 {
239 self
240 } else if rhs >= 9 {
241 BitBoard::EMPTY
242 } else {
243 BitBoard::new((self.0 >> rhs) & Rank::NORTH[9 - rhs].0)
244 }
245 }
246
247 /// Shift the bit set pattern North.
248 ///
249 /// The `shift_*` functions assume the usual rendering of the Shogi board
250 /// where square A1 is the top-most, right-most square ("north east") and
251 /// I9 the lowest, left-most one ("south west").
252 #[inline(always)]
253 pub const fn shift_north(self, dy: usize) -> Self {
254 self.shr(dy)
255 }
256
257 /// Shift the bit set pattern South.
258 #[inline(always)]
259 pub const fn shift_south(self, dy: usize) -> Self {
260 self.shl(dy)
261 }
262
263 /// Shift the bit set pattern vertically.
264 ///
265 /// This shifts the bit set up if `dy < 0`, otherwise down.
266 ///
267 /// # Panics
268 /// This will panic if the shift amount is out of range (abs(dy) > 9).
269 ///
270 #[inline(always)]
271 pub const fn shift_along_file(self, dy: i32) -> Self {
272 if dy < -9 || dy > 9 {
273 panic!("Shift amount out of range");
274 }
275 if dy <= 0 {
276 // north
277 self.shr(-dy as usize)
278 } else {
279 self.shl(dy as usize)
280 }
281 }
282
283 /// Shift the bit set pattern horizontally.
284 ///
285 /// This shifts the bit set right if `dx < 0`, otherwise left.
286 ///
287 /// # Panics
288 /// This will panic if the shift amount is out of range (abs(dx) > 9).
289 ///
290 #[inline(always)]
291 pub const fn shift_along_rank(self, dx: i32) -> Self {
292 if dx < -9 || dx > 9 {
293 panic!("Shift amount out of range");
294 }
295 if dx <= 0 {
296 self.shift_east(-dx as usize)
297 } else {
298 self.shift_west(dx as usize)
299 }
300 }
301
302 /// Shift the bit set pattern right (east).
303 ///
304 /// # Panics
305 /// Panics if the shift amount is too large.
306 /// Caller should make sure that `abs(dx) <= 9`.
307 ///
308 /// # Examples
309 ///
310 /// ```
311 /// # use haitaka_types::*;
312 /// let bb1 = bitboard! {
313 /// . . . . . . X X X
314 /// . . . . . . X . X
315 /// . . . . . . X X X
316 /// . . . . . . . . .
317 /// . . . . . . . . .
318 /// . . . . . . . . .
319 /// X X X . . . . . .
320 /// X . X . . . . . .
321 /// X X X . . . . . .
322 /// };
323 /// let bb2 = bitboard! {
324 /// . . . . . . . X X
325 /// . . . . . . . X .
326 /// . . . . . . . X X
327 /// . . . . . . . . .
328 /// . . . . . . . . .
329 /// . . . . . . . . .
330 /// . X X X . . . . .
331 /// . X . X . . . . .
332 /// . X X X . . . . .
333 /// };
334 /// assert_eq!(bb1.shift_east(1), bb2);
335 /// ```
336 #[inline(always)]
337 pub const fn shift_east(self, dx: usize) -> Self {
338 BitBoard(self.0 >> (9 * dx))
339 }
340
341 /// Shift the bit set pattern left (west).
342 ///
343 /// # Panics
344 /// Panics if the shift amount is too large.
345 /// Caller should make sure that `abs(dx) <= 9`.
346 ///
347 /// # Example
348 ///
349 /// ```
350 /// # use haitaka_types::*;
351 /// let bb1 = bitboard! {
352 /// . . . . . . X X X
353 /// . . . . . . X . X
354 /// . . . . . . X X X
355 /// . . . . . . . . .
356 /// . . . . . . . . .
357 /// . . . . . . . . .
358 /// X X X . . . . . .
359 /// X . X . . . . . .
360 /// X X X . . . . . .
361 /// };
362 /// let bb2 = bitboard! {
363 /// . . . . . X X X .
364 /// . . . . . X . X .
365 /// . . . . . X X X .
366 /// . . . . . . . . .
367 /// . . . . . . . . .
368 /// . . . . . . . . .
369 /// X X . . . . . . .
370 /// . X . . . . . . .
371 /// X X . . . . . . .
372 /// };
373 /// assert_eq!(bb1.shift_west(1), bb2);
374 #[inline(always)]
375 pub const fn shift_west(self, dx: usize) -> Self {
376 BitBoard((self.0 << (9 * dx)) & BitBoard::BOARD_MASK)
377 }
378
379 /// Shift bit set pattern so that square 'from' is mapped to square 'to'.
380 ///
381 /// This maps square `from` to square `to` and applies the same translation
382 /// to all other squares.
383 ///
384 /// # Examples
385 ///
386 /// ```
387 /// use haitaka_types::*;
388 /// let bb = Square::A1.bitboard();
389 /// let shifted = bb.shift(Square::B1, Square::G2);
390 /// assert_eq!(shifted, Square::F2.bitboard());
391 /// ```
392 pub const fn shift(self, from: Square, to: Square) -> Self {
393 let dx = to.file() as i32 - from.file() as i32;
394 let dy = to.rank() as i32 - from.rank() as i32;
395
396 self.shift_along_file(dy).shift_along_rank(dx)
397 }
398}
399
400//
401// Core implementation
402//
403impl BitBoard {
404 // TODO: It may be possible to optimize the code a bit by only using
405 // BOARD_MASK during comparisons, so not when called BitBoard::new.
406 // This would make it possible to get rid of BitBoard::new.
407
408 /// Mask to select only the first 81 bits used in a the board position.
409 pub const BOARD_MASK: u128 = (1 << Square::NUM) - 1;
410
411 /// Create a new `BitBoard`.
412 ///
413 /// Note that `BitBoard(value)`` and `BitBoard::new(value)` behave differently.
414 /// `BitBoard(value)`` does not mask out the unused high bits, while
415 /// `BitBoard::new(value)` does ensure the high bits are set to zero. In some
416 /// internal functions we do want to use the full `u128` bit set.
417 #[inline(always)]
418 pub const fn new(value: u128) -> Self {
419 Self(value & Self::BOARD_MASK)
420 }
421
422 /// An empty bitboard.
423 ///
424 /// # Examples
425 ///
426 /// ```
427 /// # use haitaka_types::*;
428 /// assert_eq!(BitBoard::EMPTY, bitboard! {
429 /// . . . . . . . . .
430 /// . . . . . . . . .
431 /// . . * . . . * . .
432 /// . . . . . . . . .
433 /// . . . . * . . . .
434 /// . . . . . . . . .
435 /// . . * . . . * . .
436 /// . . . . . . . . .
437 /// . . . . . . . . .
438 /// });
439 /// ```
440 pub const EMPTY: Self = Self(0);
441
442 /// A bitboard containing all squares.
443 ///
444 /// # Examples
445 ///
446 /// ```
447 /// # use haitaka_types::*;
448 /// assert_eq!(BitBoard::FULL, bitboard! {
449 /// X X X X X X X X X
450 /// X X X X X X X X X
451 /// X X X X X X X X X
452 /// X X X X X X X X X
453 /// X X X X X X X X X
454 /// X X X X X X X X X
455 /// X X X X X X X X X
456 /// X X X X X X X X X
457 /// X X X X X X X X X
458 /// });
459 /// ```
460 pub const FULL: Self = Self::new(!0);
461
462 /// The edges on the board.
463 ///
464 /// # Examples
465 ///
466 /// ```
467 /// # use haitaka_types::*;
468 /// assert_eq!(BitBoard::EDGES, bitboard! {
469 /// X X X X X X X X X
470 /// X . . . . . . . X
471 /// X . . . . . . . X
472 /// X . . . . . . . X
473 /// X . . . . . . . X
474 /// X . . . . . . . X
475 /// X . . . . . . . X
476 /// X . . . . . . . X
477 /// X X X X X X X X X
478 /// });
479 /// ```
480 pub const EDGES: Self = Self::__EDGES;
481 const __EDGES: Self = bitboard! {
482 X X X X X X X X X
483 X . . . . . . . X
484 X . . . . . . . X
485 X . . . . . . . X
486 X . . . . . . . X
487 X . . . . . . . X
488 X . . . . . . . X
489 X . . . . . . . X
490 X X X X X X X X X
491 };
492
493 /// The non-edges of the board.
494 pub const INNER: Self = Self::__INNER;
495 const __INNER: Self = bitboard! {
496 . . . . . . . . .
497 . X X X X X X X .
498 . X X X X X X X .
499 . X X X X X X X .
500 . X X X X X X X .
501 . X X X X X X X .
502 . X X X X X X X .
503 . X X X X X X X .
504 . . . . . . . . .
505 };
506
507 /// The corners of the board.
508 ///
509 /// # Examples
510 ///
511 /// ```
512 /// # use haitaka_types::*;
513 /// assert_eq!(BitBoard::CORNERS, bitboard! {
514 /// X . . . . . . . X
515 /// . . . . . . . . .
516 /// . . . . . . . . .
517 /// . . . . . . . . .
518 /// . . . . . . . . .
519 /// . . . . . . . . .
520 /// . . . . . . . . .
521 /// . . . . . . . . .
522 /// X . . . . . . . X
523 /// });
524 /// ```
525 pub const CORNERS: Self = Self::__CORNERS;
526 const __CORNERS: Self = bitboard! {
527 X . . . . . . . X
528 . . . . . . . . .
529 . . . . . . . . .
530 . . . . . . . . .
531 . . . . . . . . .
532 . . . . . . . . .
533 . . . . . . . . .
534 . . . . . . . . .
535 X . . . . . . . X
536 };
537
538 // The 9x9 board makes it a bit more complicated to flip files and ranks.
539 // The usual bag of bit hacks usually cannot be simply applied:
540 // https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating#Horizontal
541
542 /// Flip the bitboard's files.
543 ///
544 /// This mirrors the bitboard vertically in file 5.
545 ///
546 /// # Examples
547 /// ```
548 /// # use haitaka_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 /// };
560 /// assert_eq!(bb.flip_files(), bitboard! {
561 /// . . . . . . . . .
562 /// . . . . . . . . .
563 /// . . . . X X X . .
564 /// . . . X X . X . .
565 /// . . . X X X X . .
566 /// . . . . X . X . .
567 /// . . . . . . . . .
568 /// . . . . . . . . .
569 /// . . . . . . . . .
570 /// });
571 /// ```
572 #[inline(always)]
573 pub const fn flip_files(self) -> Self {
574 const FILE_MASKS: [u128; 9] = [
575 0x1FF, // File 1
576 0x1FF << 9, // File 2
577 0x1FF << 18, // File 3
578 0x1FF << 27, // File 4
579 0x1FF << 36, // File 5
580 0x1FF << 45, // File 6
581 0x1FF << 54, // File 7
582 0x1FF << 63, // File 8
583 0x1FF << 72, // File 9
584 ];
585
586 Self::new(
587 ((self.0 & FILE_MASKS[0]) << 72)
588 | ((self.0 & FILE_MASKS[1]) << 54)
589 | ((self.0 & FILE_MASKS[2]) << 36)
590 | ((self.0 & FILE_MASKS[3]) << 18)
591 | (self.0 & FILE_MASKS[4])
592 | ((self.0 & FILE_MASKS[5]) >> 18)
593 | ((self.0 & FILE_MASKS[6]) >> 36)
594 | ((self.0 & FILE_MASKS[7]) >> 54)
595 | ((self.0 & FILE_MASKS[8]) >> 72),
596 )
597 }
598
599 /// Flip the bitboard's ranks.
600 ///
601 /// This mirrors the bitboard horizontally in rank E.
602 ///
603 /// # Examples
604 /// ```
605 /// # use haitaka_types::*;
606 /// let bb = bitboard! {
607 /// . . . . . . . . .
608 /// . . . . . . . . .
609 /// . . X X X . . . .
610 /// . . X . X X . . .
611 /// . . X X X X . . .
612 /// . . X . X . . . .
613 /// . . . . . . . . .
614 /// . . . . . . . . .
615 /// . . . . . . . . .
616 /// };
617 /// assert_eq!(bb.flip_ranks(), bitboard! {
618 /// . . . . . . . . .
619 /// . . . . . . . . .
620 /// . . . . . . . . .
621 /// . . X . X . . . .
622 /// . . X X X X . . .
623 /// . . X . X X . . .
624 /// . . X X X . . . .
625 /// . . . . . . . . .
626 /// . . . . . . . . .
627 /// });
628 /// ```
629 #[inline(always)]
630 pub const fn flip_ranks(self) -> Self {
631 const RANK_ONE: u128 = 0x1008040201008040201;
632
633 const RANK_MASKS: [u128; 9] = [
634 RANK_ONE,
635 RANK_ONE << 1,
636 RANK_ONE << 2,
637 RANK_ONE << 3,
638 RANK_ONE << 4,
639 RANK_ONE << 5,
640 RANK_ONE << 6,
641 RANK_ONE << 7,
642 RANK_ONE << 8,
643 ];
644
645 Self::new(
646 ((self.0 & RANK_MASKS[0]) << 8)
647 | ((self.0 & RANK_MASKS[1]) << 6)
648 | ((self.0 & RANK_MASKS[2]) << 4)
649 | ((self.0 & RANK_MASKS[3]) << 2)
650 | (self.0 & RANK_MASKS[4])
651 | ((self.0 & RANK_MASKS[5]) >> 2)
652 | ((self.0 & RANK_MASKS[6]) >> 4)
653 | ((self.0 & RANK_MASKS[7]) >> 6)
654 | ((self.0 & RANK_MASKS[8]) >> 8),
655 )
656 }
657
658 /// Rotate this Bitboard 180 degrees.
659 ///
660 /// This maps bits 0..81 to bits 81..0, reversing the bits and rotating the board.
661 ///
662 /// # Examples
663 ///
664 /// ```
665 /// # use haitaka_types::*;
666 /// let bb = bitboard! {
667 /// X . . . . . . . .
668 /// . . . . . . . . .
669 /// . . X X X . . . .
670 /// . . X . X X . . .
671 /// . . X X X X . . .
672 /// . . X . X . . . .
673 /// . . . . . . . . .
674 /// . . . . . . . X .
675 /// . . . . . . . . .
676 /// };
677 /// let rr = bitboard! {
678 /// . . . . . . . . .
679 /// . X . . . . . . .
680 /// . . . . . . . . .
681 /// . . . . X . X . .
682 /// . . . X X X X . .
683 /// . . . X X . X . .
684 /// . . . . X X X . .
685 /// . . . . . . . . .
686 /// . . . . . . . . X
687 /// };
688 /// assert_eq!(bb.rotate(), rr);
689 /// assert_eq!(rr.rotate(), bb);
690 /// assert_eq!(bb.flip_files().flip_ranks(), rr);
691 /// assert_eq!(bb.flip_ranks().flip_files(), rr);
692 /// ```
693 #[inline(always)]
694 pub const fn rotate(self) -> Self {
695 Self(self.0.reverse_bits() >> (128 - Square::NUM))
696 }
697
698 /// Reverse the bits of this bitboard.
699 ///
700 /// Note: This function does not shift the board. Bit 0 becomes bit 127 and vice-versa.
701 #[inline(always)]
702 pub const fn rev(self) -> Self {
703 Self(self.0.reverse_bits())
704 }
705
706 /// Return the count of bits set to 1.
707 ///
708 /// This is an alias for [`BitBoard::count_ones`].
709 ///
710 /// # Examples
711 ///
712 /// ```
713 /// # use haitaka_types::*;
714 /// assert_eq!(BitBoard::EMPTY.len(), 0);
715 /// let bb = bitboard! {
716 /// . . . . . . . . .
717 /// . . . . . . . . .
718 /// . . X X X . . . .
719 /// . . X . X X . . .
720 /// . . X X X X . . .
721 /// . . X . X . . . .
722 /// . . . . . . . . .
723 /// . . . . . . . . .
724 /// . . . . . . . . .
725 /// };
726 /// assert_eq!(bb.len(), 12);
727 /// ```
728 #[inline(always)]
729 pub const fn len(self) -> u32 {
730 self.0.count_ones()
731 }
732
733 /// Returns the number of ones in the binary representation of `self`.
734 #[inline(always)]
735 pub const fn count_ones(self) -> u32 {
736 self.0.count_ones()
737 }
738
739 /// Returns the number of zeros in the binary representation of `self``.
740 ///
741 /// Warning: This discounts the upper 47 bits of the backing `u128` which
742 /// are assumed to be zero.
743 #[inline(always)]
744 pub const fn count_zeros(self) -> u32 {
745 self.0.count_zeros() - 47
746 }
747
748 /// Check if a [`Square`] is set.
749 ///
750 /// # Examples
751 ///
752 /// ```
753 /// # use haitaka_types::*;
754 /// let bb = bitboard! {
755 /// . . . . . . . . .
756 /// . . . . . . . . .
757 /// . . X X X . . . .
758 /// . . X . X X . . .
759 /// . . X X X X . . .
760 /// . . X . X . . . .
761 /// . . . . . . . . .
762 /// . . . . . . . . .
763 /// . . . . . . . . .
764 /// };
765 /// assert!(bb.has(Square::C5));
766 /// assert!(!bb.has(Square::D6));
767 /// assert!(bb.has(Square::F5));
768 /// assert!(!bb.has(Square::F6));
769 /// assert!(bb.has(Square::F7));
770 /// ```
771 #[inline(always)]
772 pub const fn has(self, square: Square) -> bool {
773 // Warning: This is an optimized version of `has`
774 // which relies on the file-major mapping of squares to bits.
775 // Changing that layout will break this function.
776 self.0 & (1u128 << square as usize) != 0
777 }
778
779 /// Remove a square from this [`BitBoard`].
780 ///
781 /// If the bitboard doesn't contain the square, this
782 /// simply returns a copy of the original bitboard.
783 ///
784 /// # Examples
785 ///
786 /// ```
787 /// use haitaka_types::*;
788 /// let bb = Square::E5.bitboard();
789 /// let ff = bb.rm(Square::E5);
790 /// assert_eq!(ff, BitBoard::EMPTY);
791 /// ```
792 #[inline(always)]
793 pub const fn rm(self, square: Square) -> Self {
794 self.bitand(square.bitboard().not())
795 }
796
797 /// Check if a bitboard contains no squares in common with another.
798 ///
799 /// Returns true iff the intersection of the two bitboards is empty.
800 ///
801 /// # Examples
802 ///
803 /// ```
804 /// # use haitaka_types::*;
805 /// let bb_a = bitboard! {
806 /// X X X . . . . . .
807 /// X . X X . . . . .
808 /// X X X X . . . . .
809 /// X . X . . . . . .
810 /// . . . . . . . . .
811 /// . . . . . . . . .
812 /// . . . . . . . . .
813 /// . . . . . . . . .
814 /// . . . . . . . . .
815 /// };
816 /// let bb_b = bitboard! {
817 /// . . . . . . . . .
818 /// . . . . . . . . .
819 /// . . . . . . . . .
820 /// . . . . . . . . .
821 /// . . . . . . . . .
822 /// . . . . X X X . .
823 /// . . . . X . X X .
824 /// . . . . X X X X .
825 /// . . . . X . X . .
826 /// };
827 /// assert!(bb_a.is_disjoint(bb_b));
828 /// ```
829 #[inline(always)]
830 pub const fn is_disjoint(self, other: BitBoard) -> bool {
831 self.0 & other.0 == Self::EMPTY.0
832 }
833
834 /// Check if a bitboard is a subset of another.
835 ///
836 /// # Examples
837 ///
838 /// ```
839 /// # use haitaka_types::*;
840 /// let big = bitboard! {
841 /// . . . . . . . . .
842 /// . X X X X X . . .
843 /// . X X X X X X . .
844 /// . X X . X X X . .
845 /// . X X X X X X . .
846 /// . X X X X X . . .
847 /// . X X . X X . . .
848 /// . . . . . . . . .
849 /// . . . . . . . . .
850 /// };
851 /// let small = bitboard! {
852 /// . . . . . . . . .
853 /// . . . . . . . . .
854 /// . . X X X . . . .
855 /// . . X . X X . . .
856 /// . . X X X X . . .
857 /// . . X . X . . . .
858 /// . . . . . . . . .
859 /// . . . . . . . . .
860 /// . . . . . . . . .
861 /// };
862 /// assert!(small.is_subset(small));
863 /// assert!(small.is_subset(big));
864 /// assert!(!big.is_subset(small));
865 /// ```
866 #[inline(always)]
867 pub const fn is_subset(self, other: BitBoard) -> bool {
868 other.0 & self.0 == self.0
869 }
870
871 /// Check if a bitboard is a superset of another.
872 ///
873 /// # Examples
874 ///
875 /// ```
876 /// # use haitaka_types::*;
877 /// let bb = bitboard! {
878 /// . . . . . . . . .
879 /// . . . . . . . . .
880 /// . . X X X . . . .
881 /// . . X . X X . . .
882 /// . . X X X X . . .
883 /// . . X . X . . . .
884 /// . . . . . . . . .
885 /// . . . . . . . . .
886 /// . . . . . . . . .
887 /// };
888 /// let superset = bitboard! {
889 /// . . . . . . . . .
890 /// . X X X X X . . .
891 /// . X X X X X X . .
892 /// . X X . X X X . .
893 /// . X X X X X X . .
894 /// . X X X X X . . .
895 /// . X X . X X . . .
896 /// . . . . . . . . .
897 /// . . . . . . . . .
898 /// };
899 /// assert!(superset.is_superset(bb));
900 /// ```
901 #[inline(always)]
902 pub const fn is_superset(self, other: BitBoard) -> bool {
903 self.0 & other.0 == other.0
904 }
905
906 /// Checks if the [`BitBoard`] is empty.
907 ///
908 /// # Examples
909 /// ```
910 /// # use haitaka_types::*;
911 /// assert!(BitBoard::EMPTY.is_empty());
912 /// let bb = bitboard! {
913 /// . . . . . . . . .
914 /// . . . . . . . . .
915 /// . . X X X . . . .
916 /// . . X . X X . . .
917 /// . . X X X X . . .
918 /// . . X . X . . . .
919 /// . . . . . . . . .
920 /// . . . . . . . . .
921 /// . . . . . . . . .
922 /// };
923 /// assert!(!bb.is_empty());
924 /// assert!(BitBoard::new(0).is_empty());
925 /// ```
926 #[inline(always)]
927 pub const fn is_empty(self) -> bool {
928 self.0 == Self::EMPTY.0
929 }
930
931 /// Grabs the first square if the bitboard is not empty.
932 ///
933 /// "First" means the first square when scanning from A1 to I9.
934 ///
935 /// # Examples
936 /// ```
937 /// # use haitaka_types::*;
938 /// assert!(BitBoard::EMPTY.next_square().is_none());
939 /// let bb = bitboard! {
940 /// . . . . . . . . .
941 /// . . . . . . . . .
942 /// . . X X X . . . .
943 /// . . X . X X . . .
944 /// . . X X X X . . .
945 /// . . X . X . . . .
946 /// . . . . . . . . .
947 /// . . . . . . . . .
948 /// . . . . . . . . .
949 /// };
950 /// assert_eq!(bb.next_square(), Some(Square::D4));
951 /// ```
952 #[inline(always)]
953 pub const fn next_square(self) -> Option<Square> {
954 if self.0 > 0 {
955 Some(Square::index_const(self.0.trailing_zeros() as usize))
956 } else {
957 None
958 }
959 }
960
961 /// Iterate over the squares in the bitboard, ordered by square.
962 ///
963 /// The order follows the default enumeration of [`Square::ALL`],
964 /// which is the file-major order of A1, B1, C1, ... G9, H9, I9.
965 ///
966 /// # Examples
967 ///
968 /// ```
969 /// # use haitaka_types::*;
970 /// let bb = BitBoard::FULL;
971 /// let squares = &Square::ALL;
972 /// for (s1, &s2) in bb.iter().zip(squares) {
973 /// assert_eq!(s1, s2);
974 /// }
975 /// ```
976 #[inline(always)]
977 pub fn iter(self) -> BitBoardIter {
978 BitBoardIter(self)
979 }
980
981 /// Iterate over all subsets of a bitboard.
982 ///
983 /// Subsets are produced in lexicographic order. Each subset is greater than the last.
984 ///
985 /// ```
986 /// # use haitaka_types::*;
987 /// let bb = bitboard! {
988 /// . . . . . . . . .
989 /// . . . . . . . . .
990 /// . . X X X . . . .
991 /// . . X . X X . . .
992 /// . . X X X X . . .
993 /// . . X . X . . . .
994 /// . . . . . . . . .
995 /// . . . . . . . . .
996 /// . . . . . . . . .
997 /// };
998 /// for subset in bb.iter_subsets() {
999 /// assert!(subset.is_subset(bb));
1000 /// }
1001 /// ```
1002 #[inline(always)]
1003 pub fn iter_subsets(self) -> BitBoardSubsetIter {
1004 BitBoardSubsetIter {
1005 set: self,
1006 subset: Self::EMPTY,
1007 finished: false,
1008 }
1009 }
1010}
1011
1012impl IntoIterator for BitBoard {
1013 type Item = Square;
1014
1015 type IntoIter = BitBoardIter;
1016
1017 #[inline(always)]
1018 fn into_iter(self) -> Self::IntoIter {
1019 self.iter()
1020 }
1021}
1022
1023impl FromIterator<Square> for BitBoard {
1024 fn from_iter<T: IntoIterator<Item = Square>>(iter: T) -> Self {
1025 iter.into_iter()
1026 .fold(Self::EMPTY, |bb, sq| bb | sq.bitboard())
1027 }
1028}
1029
1030/// An iterator over the squares of a bitboard.
1031///
1032/// This `struct` is created by [`BitBoard::iter`]. See its documentation for more.
1033pub struct BitBoardIter(BitBoard);
1034
1035impl Iterator for BitBoardIter {
1036 type Item = Square;
1037
1038 #[inline(always)]
1039 fn next(&mut self) -> Option<Self::Item> {
1040 let square = self.0.next_square();
1041 if let Some(square) = square {
1042 self.0 ^= square.bitboard();
1043 }
1044 square
1045 }
1046
1047 #[inline(always)]
1048 fn size_hint(&self) -> (usize, Option<usize>) {
1049 (self.len(), Some(self.len()))
1050 }
1051}
1052
1053impl ExactSizeIterator for BitBoardIter {
1054 #[inline(always)]
1055 fn len(&self) -> usize {
1056 self.0.len() as usize
1057 }
1058}
1059
1060/// An iterator over the subsets of a bitboard.
1061///
1062/// This `struct` is created by [`BitBoard::iter_subsets`]. See its documentation for more.
1063pub struct BitBoardSubsetIter {
1064 set: BitBoard,
1065 subset: BitBoard,
1066 finished: bool,
1067}
1068
1069impl Iterator for BitBoardSubsetIter {
1070 type Item = BitBoard;
1071
1072 #[inline(always)]
1073 fn next(&mut self) -> Option<Self::Item> {
1074 if self.finished {
1075 return None;
1076 }
1077 let current = self.subset;
1078 // Carry-Rippler trick to enumerate all subsets of a set.
1079 // https://www.chessprogramming.org/Traversing_Subsets_of_a_Set#All_Subsets_of_any_Set
1080 self.subset.0 = self.subset.0.wrapping_sub(self.set.0) & self.set.0;
1081 self.finished = self.subset.is_empty();
1082 Some(current)
1083 }
1084}
1085
1086/// [`BitBoard`] literal macro.
1087///
1088/// The macro takes as input a visual rendering of the Shogi board from the
1089/// perspective of the Sente player. This is the way Shogi diagrams are usually
1090/// displayed with square I9 in the left bottom (south-west) corner and square A1
1091/// in the right top (north-east) corner.
1092///
1093/// The macro reads dot (.) or star (*) as empty squares and X as occupied.
1094/// Other characters will lead to a compilation error. The '*' is used to indicate
1095/// special empty squares (for instance, the piece position in an attack pattern).
1096///
1097/// Internally we layout the board by files: file 1 (squares A1, B1, C1 ...)
1098/// corresponds to the least significant bits in the underlying u128 value, followed
1099/// by file 2 (A2, B2, ... I2), up to file 9.
1100///
1101/// # Example
1102///
1103/// ```
1104/// # use haitaka_types::*;
1105/// let bb = bitboard! {
1106/// . . . X . . . . .
1107/// . . . X . . . . .
1108/// . . . X . . . . .
1109/// . . . X . . . . .
1110/// . . . X . . . . .
1111/// X X X . X X X X X
1112/// . . . X . . . . .
1113/// . . . X . . . . .
1114/// . . . X . . . . .
1115/// };
1116/// assert_eq!(bb, File::Six.bitboard() ^ Rank::F.bitboard());
1117/// ```
1118#[macro_export]
1119macro_rules! bitboard {
1120 ( $a9:tt $a8:tt $a7:tt $a6:tt $a5:tt $a4:tt $a3:tt $a2:tt $a1:tt
1121 $b9:tt $b8:tt $b7:tt $b6:tt $b5:tt $b4:tt $b3:tt $b2:tt $b1:tt
1122 $c9:tt $c8:tt $c7:tt $c6:tt $c5:tt $c4:tt $c3:tt $c2:tt $c1:tt
1123 $d9:tt $d8:tt $d7:tt $d6:tt $d5:tt $d4:tt $d3:tt $d2:tt $d1:tt
1124 $e9:tt $e8:tt $e7:tt $e6:tt $e5:tt $e4:tt $e3:tt $e2:tt $e1:tt
1125 $f9:tt $f8:tt $f7:tt $f6:tt $f5:tt $f4:tt $f3:tt $f2:tt $f1:tt
1126 $g9:tt $g8:tt $g7:tt $g6:tt $g5:tt $g4:tt $g3:tt $g2:tt $g1:tt
1127 $h9:tt $h8:tt $h7:tt $h6:tt $h5:tt $h4:tt $h3:tt $h2:tt $h1:tt
1128 $i9:tt $i8:tt $i7:tt $i6:tt $i5:tt $i4:tt $i3:tt $i2:tt $i1:tt
1129 ) => {
1130 $crate::bitboard! { @__inner
1131 $a1 $b1 $c1 $d1 $e1 $f1 $g1 $h1 $i1
1132 $a2 $b2 $c2 $d2 $e2 $f2 $g2 $h2 $i2
1133 $a3 $b3 $c3 $d3 $e3 $f3 $g3 $h3 $i3
1134 $a4 $b4 $c4 $d4 $e4 $f4 $g4 $h4 $i4
1135 $a5 $b5 $c5 $d5 $e5 $f5 $g5 $h5 $i5
1136 $a6 $b6 $c6 $d6 $e6 $f6 $g6 $h6 $i6
1137 $a7 $b7 $c7 $d7 $e7 $f7 $g7 $h7 $i7
1138 $a8 $b8 $c8 $d8 $e8 $f8 $g8 $h8 $i8
1139 $a9 $b9 $c9 $d9 $e9 $f9 $g9 $h9 $i9
1140 }
1141 };
1142 (@__inner $($occupied:tt)*) => {{
1143 const BITBOARD: $crate::BitBoard = {
1144 let mut index = 0;
1145 let mut bitboard = $crate::BitBoard::EMPTY;
1146 $(
1147 if $crate::bitboard!(@__square $occupied) {
1148 bitboard.0 |= 1 << index;
1149 }
1150 index += 1;
1151 )*
1152 let _ = index;
1153 bitboard
1154 };
1155 BITBOARD
1156 }};
1157 (@__square X) => { true };
1158 (@__square .) => { false };
1159 (@__square *) => { false };
1160 (@__square $token:tt) => {
1161 compile_error!(
1162 concat!(
1163 "Expected only `X` or `.` tokens, found `",
1164 stringify!($token),
1165 "`"
1166 )
1167 )
1168 };
1169 ($($token:tt)*) => {
1170 compile_error!("Expected 81 squares")
1171 };
1172}
1173pub use bitboard;
1174
1175impl core::fmt::Debug for BitBoard {
1176 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1177 if f.alternate() {
1178 write!(f, "bitboard! {{")?;
1179 for &rank in Rank::ALL.iter() {
1180 write!(f, "\n ")?;
1181 for &file in File::ALL.iter().rev() {
1182 if self.has(Square::new(file, rank)) {
1183 write!(f, " X")?;
1184 } else {
1185 write!(f, " .")?;
1186 }
1187 }
1188 }
1189 write!(f, "\n}}")?;
1190 Ok(())
1191 } else {
1192 write!(f, "BitBoard({:#018X})", self.0)
1193 }
1194 }
1195}