fast_tak/
move_gen.rs

1use takparse::{Direction, Move, MoveKind, Piece, Square};
2
3use crate::{game::Game, reserves::Reserves, stack::Stack, GameResult};
4
5impl<const N: usize, const HALF_KOMI: i8> Game<N, HALF_KOMI> {
6    /// Populate moves vector with all possible moves for the current position.
7    ///
8    /// # Panics
9    ///
10    /// If the move vector is not empty.
11    pub fn possible_moves(&self, moves: &mut Vec<Move>) {
12        debug_assert!(moves.is_empty());
13        let n = u8::try_from(N).unwrap();
14        // On the first two plies the only possible moves are placing a flat.
15        if self.is_swapped() {
16            self.add_opening_moves(moves);
17            return;
18        }
19
20        // Go over every start position and add the possible moves.
21        for x in 0..n {
22            for y in 0..n {
23                let square = Square::new(x, y);
24                match self.board.get(square).and_then(Stack::top) {
25                    Some((piece, color)) => {
26                        if color == self.to_move {
27                            self.add_spreads(square, piece, moves);
28                        }
29                    }
30                    None => self.add_places(square, moves),
31                }
32            }
33        }
34    }
35
36    fn add_opening_moves(&self, moves: &mut Vec<Move>) {
37        let n = u8::try_from(N).unwrap();
38        for x in 0..n {
39            for y in 0..n {
40                let square = Square::new(x, y);
41                let Some(stack) = self.board.get(square) else {
42                    continue;
43                };
44                if stack.is_empty() {
45                    moves.push(Move::new(square, MoveKind::Place(Piece::Flat)));
46                }
47            }
48        }
49    }
50
51    fn add_places(&self, square: Square, moves: &mut Vec<Move>) {
52        let Reserves { stones, caps } = self.get_reserves();
53        if stones > 0 {
54            moves.push(Move::new(square, MoveKind::Place(Piece::Flat)));
55            moves.push(Move::new(square, MoveKind::Place(Piece::Wall)));
56        }
57        if caps > 0 {
58            moves.push(Move::new(square, MoveKind::Place(Piece::Cap)));
59        }
60    }
61
62    fn add_spreads(&self, square: Square, piece: Piece, moves: &mut Vec<Move>) {
63        // Struct to store unfinished spread moves.
64        struct Spread<const N: usize> {
65            square: Square,
66            hand: u8,
67            drops: [u8; N],
68            drop_counts: usize,
69        }
70
71        let n = u8::try_from(N).unwrap();
72
73        let Some(stack) = self.board.get(square) else {
74            return;
75        };
76        #[allow(clippy::cast_possible_truncation)]
77        let max_carry: u8 = stack.size().min(N as u32) as u8;
78
79        let mut spreads = Vec::new();
80        for pickup in 1..=max_carry {
81            for direction in [
82                Direction::Up,
83                Direction::Down,
84                Direction::Left,
85                Direction::Right,
86            ] {
87                assert!(spreads.is_empty());
88                // Start by picking up `pickup` amount.
89                spreads.push(Spread {
90                    square,
91                    hand: pickup,
92                    drops: [0; N],
93                    drop_counts: 0,
94                });
95                while let Some(mut spread) = spreads.pop() {
96                    if let Some(next) = spread.square.checked_step(direction, n) {
97                        // check if it is possible to drop on the next square
98                        if !match self.board.get(next).and_then(Stack::top) {
99                            None => true,
100                            Some((Piece::Flat, _color)) => true,
101                            Some((Piece::Cap, _color)) => false,
102                            Some((Piece::Wall, _color)) => spread.hand == 1 && piece == Piece::Cap,
103                        } {
104                            continue;
105                        }
106
107                        for drop in 1..spread.hand {
108                            let mut drops = spread.drops;
109                            drops[spread.drop_counts] = drop;
110                            spreads.push(Spread {
111                                square: next,
112                                hand: spread.hand - drop,
113                                drops,
114                                drop_counts: spread.drop_counts + 1,
115                            });
116                        }
117
118                        // Drop the rest
119                        spread.drops[spread.drop_counts] = spread.hand;
120                        moves.push(Move::new(
121                            square,
122                            MoveKind::Spread(
123                                direction,
124                                spread
125                                    .drops
126                                    .into_iter()
127                                    .take(spread.drop_counts + 1)
128                                    .map(u32::from)
129                                    .collect(),
130                            ),
131                        ));
132                    }
133                }
134            }
135        }
136    }
137}
138
139#[must_use]
140pub fn perf_count<const N: usize, const HALF_KOMI: i8>(
141    game: &Game<N, HALF_KOMI>,
142    depth: usize,
143) -> usize {
144    if depth == 0 || game.result() != GameResult::Ongoing {
145        1
146    } else if depth == 1 {
147        let mut moves = Vec::new();
148        game.possible_moves(&mut moves);
149        moves.len()
150    } else {
151        let mut moves = Vec::new();
152        game.possible_moves(&mut moves);
153        moves
154            .into_iter()
155            .map(|m| {
156                let mut clone = game.clone();
157                if clone.play(m).is_err() {
158                    return 0;
159                };
160                perf_count(&clone, depth - 1)
161            })
162            .sum()
163    }
164}
165
166#[cfg(test)]
167mod tests {
168    use crate::{move_gen::perf_count, Game};
169
170    #[test]
171    fn move_stack_perft() {
172        let game = Game::<5, 0>::from_ptn_moves(&["d3", "c3", "c4", "1d3<", "1c4-", "Sc4"]);
173        assert_eq!(perf_count(&game, 1), 87);
174        assert_eq!(perf_count(&game, 2), 6_155);
175        assert_eq!(perf_count(&game, 3), 461_800);
176    }
177
178    #[test]
179    fn respect_carry_limit_perft() {
180        let game = Game::<5, 0>::from_ptn_moves(&[
181            "c2", "c3", "d3", "b3", "c4", "1c2+", "1d3<", "1b3>", "1c4-", "Cc2", "a1", "1c2+", "a2",
182        ]);
183        assert_eq!(perf_count(&game, 1), 104);
184        assert_eq!(perf_count(&game, 2), 7_743);
185        assert_eq!(perf_count(&game, 3), 592_645);
186    }
187
188    #[test]
189    fn suicide_perft() {
190        let game = Game::<5, 0>::from_ptn_moves(&[
191            "c4", "c2", "d2", "c3", "b2", "d3", "1d2+", "b3", "d2", "b4", "1c2+", "1b3>", "2d3<",
192            "1c4-", "d4", "5c3<23", "c2", "c4", "1d4<", "d3", "1d2+", "1c3+", "Cc3", "2c4>",
193            "1c3<", "d2", "c3", "1d2+", "1c3+", "1b4>", "2b3>11", "3c4-12", "d2", "c4", "b4", "c5",
194            "1b3>", "1c4<", "3c3-", "e5", "e2",
195        ]);
196        assert_eq!(perf_count(&game, 1), 85);
197        assert_eq!(perf_count(&game, 2), 11_206);
198        assert_eq!(perf_count(&game, 3), 957_000);
199    }
200
201    #[test]
202    fn endgame_perft() {
203        let game = Game::<5, 0>::from_ptn_moves(&[
204            "a5", "b4", "c3", "d2", "e1", "d1", "c2", "d3", "c1", "d4", "d5", "c4", "c5", "b3",
205            "b2", "a2", "Sb1", "a3", "Ce4", "Cb5", "a4", "a1", "e5", "e3", "c3<", "Sc3", "c1>",
206            "c1", "2d1+", "c3-", "c3", "a3>", "a3", "d1", "e4<", "2c2>", "c2", "e2", "b2+", "b2",
207        ]);
208        assert_eq!(perf_count(&game, 1), 65);
209        assert_eq!(perf_count(&game, 2), 4_072);
210        assert_eq!(perf_count(&game, 3), 272_031);
211        assert_eq!(perf_count(&game, 4), 16_642_760);
212    }
213
214    #[test]
215    fn reserves_perft() {
216        let game = Game::<5, 0>::from_ptn_moves(&[
217            "a1", "b1", "c1", "d1", "e1", "e2", "d2", "c2", "b2", "a2", "a3", "b3", "c3", "d3",
218            "e3", "a4", "b4", "c4", "d4", "e4", "a5", "a4-", "b4-", "c4-", "d4-", "e4-", "a4",
219            "b4", "c4", "d4", "e4", "2a3>", "c4>", "2e3<", "a3", "4b3-", "b3", "c4", "e3", "d5",
220            "d2<", "d2", "2d4-", "d4", "c5", "b5", "2c2>", "d1+", "c2", "e2+", "d1", "e2", "c5<",
221            "c5", "e4<", "Se4", "2b5-", "e4-", "a3-",
222        ]);
223        assert_eq!(perf_count(&game, 1), 152);
224        assert_eq!(perf_count(&game, 2), 15_356);
225        assert_eq!(perf_count(&game, 3), 1_961_479);
226        // assert_eq!(perf_count(game.clone(), 4), 197_434_816);
227    }
228
229    #[test]
230    fn perft_5() {
231        type G = Game<5, 0>;
232        assert_eq!(perf_count(&G::default(), 0), 1);
233        assert_eq!(perf_count(&G::default(), 1), 25);
234        assert_eq!(perf_count(&G::default(), 2), 600);
235        assert_eq!(perf_count(&G::default(), 3), 43_320);
236        assert_eq!(perf_count(&G::default(), 4), 2_999_784);
237    }
238
239    #[test]
240    fn perft_6() {
241        type G = Game<6, 0>;
242        assert_eq!(perf_count(&G::default(), 0), 1);
243        assert_eq!(perf_count(&G::default(), 1), 36);
244        assert_eq!(perf_count(&G::default(), 2), 1_260);
245        assert_eq!(perf_count(&G::default(), 3), 132_720);
246        assert_eq!(perf_count(&G::default(), 4), 13_586_048);
247        // assert_eq!(perf_count(&G::default(), 5), 1_253_506_520);
248    }
249}
fast_tak/move_gen.rs

fast_tak/
move_gen.rs
