tic_tac_toe/
lib.rs

1#![allow(clippy::uninlined_format_args)]
2
3pub mod board;
4pub mod team;
5
6pub use self::{
7    board::{
8        Board,
9        WinType,
10        WinnerInfo,
11    },
12    team::Team,
13};
14
15/// The # of tic-tac-toe tiles
16pub const NUM_TILES: u8 = 9;
17
18/// Run minimax on a board.
19///
20/// This is negamax. The returned score is relative to the current player.
21///
22/// # Returns
23/// Returns a tuple. The first element is the score. The second is the move.
24pub fn minimax(board: Board, depth: u8) -> (i8, u8) {
25    let color = match board.get_turn() {
26        Team::X => 1,
27        Team::O => -1,
28    };
29
30    if depth == 0 {
31        return (0, 0);
32    }
33
34    match board.get_winner() {
35        Some(Team::X) => return (color, 0),
36        Some(Team::O) => return (-color, 0),
37        None => {}
38    }
39
40    if board.is_draw() {
41        return (0, 0);
42    }
43
44    let mut value = i8::MIN;
45    let mut best_index = 0;
46    for (index, child) in board.iter_children() {
47        let (new_value, _index) = minimax(child, depth - 1);
48        let new_value = -new_value;
49
50        if new_value > value {
51            value = new_value;
52            best_index = index;
53
54            // If value is the max value, stop search
55            if value == 1 {
56                return (value, index);
57            }
58        }
59    }
60
61    (value, best_index)
62}
63
64#[cfg(test)]
65mod test {
66    use super::*;
67    use std::collections::HashSet;
68
69    #[test]
70    fn minimax_all() {
71        let board = Board::new();
72        let (score, index) = minimax(board, 9);
73        assert_eq!(score, 0);
74        assert_eq!(index, 0);
75    }
76
77    #[test]
78    fn minimax_win_1() {
79        let board = Board::new()
80            .set(0, Some(Team::X))
81            .set(4, Some(Team::O))
82            .set(8, Some(Team::X))
83            .set(2, Some(Team::O));
84        let (score, index) = minimax(board, 9);
85        assert_eq!(score, 1, "expected X win");
86        assert_eq!(index, 6);
87    }
88
89    #[test]
90    fn minimax_win_2() {
91        let board = Board::new()
92            .set(0, Some(Team::X))
93            .set(1, Some(Team::O))
94            .set(2, Some(Team::X))
95            .set(4, Some(Team::O))
96            .set(3, Some(Team::X));
97        let (score, index) = minimax(board, 9);
98        assert_eq!(score, 1, "expected O win");
99        assert_eq!(index, 7);
100    }
101
102    #[test]
103    fn tabulate() {
104        let mut set = HashSet::with_capacity(1024 * 8);
105        set.insert(Board::new());
106
107        let mut stack = vec![Board::new()];
108        while let Some(board) = stack.pop() {
109            stack.extend(
110                board
111                    .iter_children()
112                    .map(|(_, board)| board)
113                    .filter(|child| set.insert(*child)),
114            );
115        }
116
117        assert!(set.len() == 5478);
118    }
119}
tic_tac_toe/lib.rs

tic_tac_toe/
lib.rs
