1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
use crate::square::Square;
/// Finite set of up to 64 bits representing chess board squares
pub type Bitboard = u64;
/// Print bitboard on screen in the same way squares appear in memory
/// (i.e the board is actually flipped along X)
#[allow(dead_code)]
pub fn print(bb: Bitboard, title: &str) {
println!("\n {}", title);
for rank in (0..8).rev() {
print!("{}|", rank + 1);
for file in 0..8 {
let index = rank * 8 + file;
print!("{}", if bb >> index & 1 == 1 { "⚫" } else { ". " });
if file == 7 {
println!();
}
}
}
return println!(" a b c d e f g h");
}
/// Return bitboard cardinality, aka number of elements in the set
pub fn pop_count(mut bb: Bitboard) -> u8 {
let mut count = 0;
while bb > 0 {
count += 1;
bb &= bb - 1;
}
return count;
}
/// Return Bitboard with only Least Single Bit
pub fn ls1b(bb: Bitboard) -> Bitboard {
if bb == 0 {
return 0
}
bb & !(bb - 1)
}
const DE_BRUJIN_SEQUENCE: [u8; 64] = [
0, 1, 48, 2, 57, 49, 28, 3,
61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22,
45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16,
54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10,
25, 14, 19, 9, 13, 8, 7, 6
];
/// Return the square corresponding to Least Single Bit
/// using De Brujin method. For single Bitboards it works
/// like a mapper from Bitboards to Squares.
///
/// ```rust
/// # use chessnost::{bitboard::bitscan, square::Square};
/// assert_eq!(bitscan(5), Square::from(0));
/// assert_eq!(bitscan(4), Square::C1);
/// ```
pub fn bitscan(bb: Bitboard) -> Square {
// TODO: generate private De Brujin routine
debug_assert!(bb != 0, "Can not bitscan empty bitboard");
let magic: u64 = 0x03f79d71b4cb0a89;
let ls1b = ls1b(bb);
let index = DE_BRUJIN_SEQUENCE[(((ls1b as u128 * magic as u128) as u64) >> 58) as usize];
Square::from(index)
}
/// Perform bitscan and reset the *ls1b*
pub fn bitscan_and_reset(bb: &mut Bitboard) -> Square {
let square = bitscan(*bb);
*bb &= *bb - 1; // Reset ls1b
square
}
/// Convert bitboard into the list of squares
pub fn serialize_bitboard(mut bb: Bitboard) -> Vec<Square> {
let mut serialized = Vec::with_capacity(64);
while bb > 0 {
serialized.push(bitscan_and_reset(&mut bb));
}
serialized
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_pop_count() {
assert_eq!(pop_count(127), 7);
}
#[test]
fn test_ls1b() {
assert_eq!(ls1b(38), 2);
assert_eq!(ls1b(16), 16);
assert_eq!(ls1b(20), 4);
}
#[test]
fn test_bitscan() {
assert_eq!(bitscan(4), Square::from(2));
assert_eq!(bitscan(16), Square::from(4));
assert_eq!(bitscan(64), Square::from(6));
assert_eq!(bitscan(128), Square::from(7));
}
#[test]
fn test_bitscan_with_non_single_bb() {
assert_eq!(bitscan(5), Square::from(0));
assert_eq!(bitscan(6), Square::from(1));
assert_eq!(bitscan(7), Square::from(0));
}
#[test]
fn test_serialize_bitboard() {
let bb = 1 << 4 | 1 << 15 | 1 << 60;
let serialized = serialize_bitboard(bb);
assert_eq!(serialized[0], Square::from(4));
assert_eq!(serialized[1], Square::from(15));
assert_eq!(serialized[2], Square::from(60));
}
}
|
