game_solver/
lib.rs

1use std::{
2    collections::HashMap,
3    hash::{BuildHasher, Hash},
4};
5
6/// Represents a player in a two-player combinatorial game.
7#[derive(PartialEq, Eq, Debug)]
8pub enum Player {
9    P1,
10    P2,
11}
12
13impl Player {
14    /// Get the player opposite to this one.
15    #[must_use]
16    pub const fn opposite(&self) -> Self {
17        match self {
18            Self::P1 => Self::P2,
19            Self::P2 => Self::P1,
20        }
21    }
22}
23
24/// Represents a combinatorial game.
25pub trait Game {
26    /// The type of move this game uses.
27    type Move: Copy;
28
29    /// The iterator type for possible moves.
30    type Iter: Iterator<Item = Self::Move>;
31
32    /// Returns the player whose turn it is.
33    fn player(&self) -> Player;
34
35    /// Scores a position. The default implementation uses the size minus the number of moves (for finite games)
36    fn score(&self) -> u32;
37
38    /// Get the max score of a game.
39    fn max_score(&self) -> u32;
40
41    /// Get the min score of a game. This should be negative.
42    fn min_score(&self) -> i32;
43
44    /// Returns true if the move was valid, and makes the move if it was.
45    fn make_move(&mut self, m: Self::Move) -> bool;
46
47    /// Returns a vector of all possible moves.
48    ///
49    /// If possible, this function should "guess" what the best moves are first.
50    /// For example, if this is for tic tac toe, it should give the middle move first.
51    /// This allows alpha-beta pruning to move faster.
52    // fn possible_moves(&self) -> iterator?
53    fn possible_moves(&self) -> Self::Iter;
54
55    /// Returns true if the move is a winning move.
56    fn is_winning_move(&self, m: Self::Move) -> bool;
57}
58
59/// A transposition table for a game.
60/// Transposition tables implement caching for minimax algorithms.
61///
62/// Transposition tables should optimally be O(1) for get, has, and insert.
63/// The best structure for this is a `HashMap`.
64///
65/// all `HashMap`s already implement `TranspositionTable`.
66pub trait TranspositionTable<T: Eq + Hash + Game> {
67    fn get(&self, board: &T) -> Option<i32>;
68    fn insert(&mut self, board: T, score: i32);
69    fn has(&self, board: &T) -> bool;
70}
71
72impl<K: Eq + Hash + Game, S: BuildHasher + Default> TranspositionTable<K> for HashMap<K, i32, S> {
73    fn get(&self, board: &K) -> Option<i32> {
74        self.get(board).copied()
75    }
76
77    fn insert(&mut self, board: K, score: i32) {
78        self.insert(board, score);
79    }
80
81    fn has(&self, board: &K) -> bool {
82        self.contains_key(board)
83    }
84}
85
86/// Runs the two-player minimax variant on a game.
87/// It uses alpha beta pruning (e.g. you can specify \[-1, 1\] to get only win/loss/draw moves).
88///
89/// This function requires a transposition table. If you only plan on running this function once,
90/// you can use a the in-built `HashMap`.
91fn negamax<T: Game + Clone + Eq + Hash>(
92    game: &T,
93    transposition_table: &mut dyn TranspositionTable<T>,
94    mut alpha: i32,
95    mut beta: i32,
96) -> i32 {
97    for m in &mut game.possible_moves() {
98        if game.is_winning_move(m) {
99            return game.score() as i32 - 1;
100        }
101    }
102
103    {
104        let max = transposition_table
105            .get(game)
106            .unwrap_or(game.max_score() as i32);
107        if beta > max {
108            beta = max;
109            if alpha >= beta {
110                return beta;
111            }
112        }
113    }
114
115    for m in &mut game.possible_moves() {
116        let mut board = game.clone();
117        board.make_move(m);
118
119        let score = -negamax(&board, transposition_table, -beta, -alpha);
120
121        if score >= beta {
122            return beta;
123        }
124        if score > alpha {
125            alpha = score;
126        }
127    }
128
129    transposition_table.insert(game.clone(), alpha);
130
131    alpha
132}
133
134pub fn solve<T: Game + Clone + Eq + Hash>(game: &T) -> i32 {
135    let min = game.min_score();
136    let max = game.max_score() as i32 + 1;
137
138    let mut alpha = min;
139    let mut beta = max;
140
141    while alpha < beta {
142        let med = alpha + (beta - alpha) / 2;
143        let r = negamax(game, &mut HashMap::new(), med, med + 1);
144
145        if r <= med {
146            beta = r;
147        } else {
148            alpha = r;
149        }
150    }
151
152    alpha
153}
154
155/// Utility function to get a list of the move scores of a certain game.
156///
157/// This is mainly intended for front-facing visual interfaces
158/// for each move.
159///
160/// We flip the sign of the score because we want the score from the perspective of the player playing
161/// the move, not the player whose turn it is.
162pub fn move_scores<T: Game + Clone + Eq + Hash>(
163    game: &T,
164) -> impl Iterator<Item = (<T as Game>::Move, i32)> + '_ {
165    game.possible_moves().map(move |m| {
166        let mut board = game.clone();
167        board.make_move(m);
168        (m, -solve(&board))
169    })
170}
game_solver/lib.rs

game_solver/
lib.rs
