tic_tac_toe/
board.rs

1use crate::{
2    Team,
3    NUM_TILES,
4};
5
6// Allow unusual_byte_groupings as we group by 3 to visualize the board
7// Vertical Wins
8#[allow(clippy::unusual_byte_groupings)]
9const VERTICAL_WIN_1: u16 = 0b100_100_100;
10#[allow(clippy::unusual_byte_groupings)]
11const VERTICAL_WIN_2: u16 = 0b010_010_010;
12#[allow(clippy::unusual_byte_groupings)]
13const VERTICAL_WIN_3: u16 = 0b001_001_001;
14
15// Horizontal Wins
16#[allow(clippy::unusual_byte_groupings)]
17const HORIZONTAL_WIN_1: u16 = 0b111_000_000;
18#[allow(clippy::unusual_byte_groupings)]
19const HORIZONTAL_WIN_2: u16 = 0b000_111_000;
20#[allow(clippy::unusual_byte_groupings)]
21const HORIZONTAL_WIN_3: u16 = 0b000_000_111;
22
23// Diagonal win
24#[allow(clippy::unusual_byte_groupings)]
25const DIAGONAL_WIN: u16 = 0b100_010_001;
26
27// Anti-Diagonal win
28#[allow(clippy::unusual_byte_groupings)]
29const ANTI_DIAGONAL_WIN: u16 = 0b001_010_100;
30
31/// The win type
32#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
33pub enum WinType {
34    Horizontal,
35    Vertical,
36    Diagonal,
37    AntiDiagonal,
38}
39
40/// Winner Info
41#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
42pub struct WinnerInfo {
43    /// The winning team
44    pub team: Team,
45
46    /// The tile_indexes that are part of the win.
47    ///
48    /// Sorted from least to greatest.
49    pub tile_indexes: [u8; 3],
50
51    /// The win type
52    pub win_type: WinType,
53}
54
55impl WinnerInfo {
56    fn new(team: Team, i0: u8, i1: u8, i2: u8, win_type: WinType) -> Self {
57        Self {
58            team,
59            tile_indexes: [i0, i1, i2],
60            win_type,
61        }
62    }
63
64    /// Get the least tile index
65    pub fn start_tile_index(&self) -> u8 {
66        self.tile_indexes[0]
67    }
68
69    /// Get the highest tile index
70    pub fn end_tile_index(&self) -> u8 {
71        self.tile_indexes[2]
72    }
73}
74
75/// A Tic Tac Toe board
76#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
77pub struct Board {
78    // the bitboard
79    // 9 tiles, so it cannot fit in a u8 but can fit in a u16
80    x_state: u16,
81    o_state: u16,
82}
83
84impl Board {
85    /// Make a new [`Board`].
86    pub fn new() -> Self {
87        Board {
88            x_state: 0,
89            o_state: 0,
90        }
91    }
92
93    // TODO: Maybe just add this to the board.
94    /// Get the team whos turn it is.
95    pub fn get_turn(self) -> Team {
96        let num_x = self.x_state.count_ones();
97        let num_o = self.o_state.count_ones();
98
99        if num_x > num_o {
100            Team::O
101        } else {
102            Team::X
103        }
104    }
105
106    /// Returns true if it is a draw.
107    ///
108    /// This does not check for wins.
109    pub fn is_draw(self) -> bool {
110        (self.x_state | self.o_state).count_ones() >= u32::from(NUM_TILES)
111    }
112
113    /// Check if the given team won.
114    ///
115    /// This is designed to be fast.
116    pub fn has_won(self, team: Team) -> bool {
117        let state = match team {
118            Team::X => self.x_state,
119            Team::O => self.o_state,
120        };
121
122        ((state & VERTICAL_WIN_1) == VERTICAL_WIN_1)
123            || ((state & VERTICAL_WIN_2) == VERTICAL_WIN_2)
124            || ((state & VERTICAL_WIN_3) == VERTICAL_WIN_3)
125            || ((state & HORIZONTAL_WIN_1) == HORIZONTAL_WIN_1)
126            || ((state & HORIZONTAL_WIN_2) == HORIZONTAL_WIN_2)
127            || ((state & HORIZONTAL_WIN_3) == HORIZONTAL_WIN_3)
128            || ((state & DIAGONAL_WIN) == DIAGONAL_WIN)
129            || ((state & ANTI_DIAGONAL_WIN) == ANTI_DIAGONAL_WIN)
130    }
131
132    /// Get the winner if they exist
133    pub fn get_winner(self) -> Option<Team> {
134        if self.has_won(Team::X) {
135            Some(Team::X)
136        } else if self.has_won(Team::O) {
137            Some(Team::O)
138        } else {
139            None
140        }
141    }
142
143    /// Get the winner info, if there is a winner
144    ///
145    /// This is much slower than [`Self::get_winner`].
146    pub fn get_winner_info(self) -> Option<WinnerInfo> {
147        let winner = self.get_winner()?;
148
149        let state = match winner {
150            Team::X => self.x_state,
151            Team::O => self.o_state,
152        };
153
154        // Vertical 1
155        if (state & VERTICAL_WIN_1) == VERTICAL_WIN_1 {
156            return Some(WinnerInfo::new(winner, 2, 5, 8, WinType::Vertical));
157        }
158
159        // Vertical 2
160        if (state & VERTICAL_WIN_2) == VERTICAL_WIN_2 {
161            return Some(WinnerInfo::new(winner, 1, 4, 7, WinType::Vertical));
162        }
163
164        // Vertical 3
165        if (state & VERTICAL_WIN_3) == VERTICAL_WIN_3 {
166            return Some(WinnerInfo::new(winner, 0, 3, 6, WinType::Vertical));
167        }
168
169        // Horizontal 1
170        if (state & HORIZONTAL_WIN_1) == HORIZONTAL_WIN_1 {
171            return Some(WinnerInfo::new(winner, 0, 1, 2, WinType::Horizontal));
172        }
173
174        // Horizontal 2
175        if (state & HORIZONTAL_WIN_2) == HORIZONTAL_WIN_2 {
176            return Some(WinnerInfo::new(winner, 6, 7, 8, WinType::Horizontal));
177        }
178
179        // Horizontal 3
180        if (state & HORIZONTAL_WIN_3) == HORIZONTAL_WIN_3 {
181            return Some(WinnerInfo::new(winner, 0, 1, 2, WinType::Horizontal));
182        }
183
184        // Diagonal
185        if (state & DIAGONAL_WIN) == DIAGONAL_WIN {
186            return Some(WinnerInfo::new(winner, 0, 4, 8, WinType::Diagonal));
187        }
188
189        // Anti Diagonal
190        if (state & ANTI_DIAGONAL_WIN) == ANTI_DIAGONAL_WIN {
191            return Some(WinnerInfo::new(winner, 2, 4, 6, WinType::AntiDiagonal));
192        }
193
194        None
195    }
196
197    /// Set the tile at the index.
198    ///
199    /// # Panics
200    /// Panics if the index >= 9.
201    #[must_use]
202    pub fn set(mut self, index: u8, team: Option<Team>) -> Self {
203        assert!(index < NUM_TILES);
204        match team {
205            Some(Team::X) => {
206                self.x_state |= 1 << index;
207                self.o_state &= !(1 << index);
208            }
209            Some(Team::O) => {
210                self.x_state &= !(1 << index);
211                self.o_state |= 1 << index;
212            }
213            None => {
214                self.x_state &= !(1 << index);
215                self.o_state &= !(1 << index);
216            }
217        }
218        self
219    }
220
221    /// Get the tile at the index.
222    ///
223    /// # Panics
224    /// Panics if the index >= 9.
225    pub fn get(self, index: u8) -> Option<Team> {
226        assert!(index < NUM_TILES);
227        if self.x_state & (1 << index) != 0 {
228            Some(Team::X)
229        } else if self.o_state & (1 << index) != 0 {
230            Some(Team::O)
231        } else {
232            None
233        }
234    }
235
236    /// Get an iterator over child board states.
237    ///
238    /// # Returns
239    /// Returns an Iterator where Items are tuples.
240    /// The first item is the index of the placed tile.
241    /// The second is the resulting board state.
242    pub fn iter_children(self) -> ChildrenIter {
243        ChildrenIter::new(self)
244    }
245
246    /// Get an iterator over the tiles.
247    ///
248    /// The iterator starts at 0 at the top left and ends at 8 at the bottom right.
249    ///
250    /// # Returns
251    /// Returns a tuple pair, where the first element is the index and the second is the tile value.
252    pub fn iter(self) -> impl Iterator<Item = (u8, Option<Team>)> {
253        let mut index = 0;
254        std::iter::from_fn(move || {
255            if index >= NUM_TILES {
256                return None;
257            }
258
259            let index_mask = 1 << index;
260
261            let ret = if (self.x_state & index_mask) != 0 {
262                Some(Team::X)
263            } else if (self.o_state & index_mask) != 0 {
264                Some(Team::O)
265            } else {
266                None
267            };
268
269            let ret = Some((index, ret));
270            index += 1;
271            ret
272        })
273    }
274
275    /// Encode this board as a [`u16`].
276    pub fn encode_u16(self) -> u16 {
277        let mut ret = 0;
278        for i in (0..NUM_TILES).rev() {
279            let tile = self.get(i);
280
281            ret *= 3;
282            ret += match tile {
283                None => 0,
284                Some(Team::X) => 1,
285                Some(Team::O) => 2,
286            };
287        }
288        ret
289    }
290
291    /// Decode a [`u16`] into a board
292    pub fn decode_u16(mut data: u16) -> Self {
293        let mut ret = Self::new();
294        for i in 0..NUM_TILES {
295            let tile = match data % 3 {
296                0 => None,
297                1 => Some(Team::X),
298                2 => Some(Team::O),
299                unknown_tile => unreachable!("unknown tile \"{unknown_tile}\"",),
300            };
301            ret = ret.set(i, tile);
302
303            data /= 3;
304        }
305
306        ret
307    }
308}
309
310impl Default for Board {
311    fn default() -> Self {
312        Self::new()
313    }
314}
315
316#[derive(Debug)]
317pub struct ChildrenIter {
318    board: Board,
319    turn: Team,
320    index: u8,
321}
322
323impl ChildrenIter {
324    fn new(board: Board) -> Self {
325        let turn = board.get_turn();
326        Self {
327            board,
328            turn,
329            index: 0,
330        }
331    }
332}
333
334impl Iterator for ChildrenIter {
335    type Item = (u8, Board);
336
337    fn next(&mut self) -> Option<Self::Item> {
338        if self.board.get_winner().is_some() {
339            return None;
340        }
341
342        loop {
343            if self.index >= NUM_TILES {
344                return None;
345            }
346
347            let index_mask = 1 << self.index;
348            let tile_does_not_exist = ((self.board.x_state | self.board.o_state) & index_mask) == 0;
349
350            if tile_does_not_exist {
351                let board = self.board.set(self.index, Some(self.turn));
352                let item = Some((self.index, board));
353                self.index += 1;
354                return item;
355            }
356            self.index += 1;
357        }
358    }
359
360    fn size_hint(&self) -> (usize, Option<usize>) {
361        (0, Some(usize::from(NUM_TILES)))
362    }
363}
364
365impl std::iter::FusedIterator for ChildrenIter {}
tic_tac_toe/board.rs

tic_tac_toe/
board.rs
