turk/
lib.rs

1use std::ops::Not;
2
3#[derive(Copy, Clone, Debug, PartialEq, Eq)]
4pub enum Player {
5    One,
6    Two,
7}
8
9impl Not for Player {
10    type Output = Self;
11
12    fn not(self) -> Self::Output {
13        match self {
14            Player::One => Player::Two,
15            Player::Two => Player::One,
16        }
17    }
18}
19
20impl Into<usize> for Player {
21    fn into(self) -> usize {
22        match self {
23            Player::One => 1,
24            Player::Two => 2,
25        }
26    }
27}
28
29pub trait GameState: Clone {
30    type Move: Clone;
31
32    fn next_player(&self) -> Player;
33    fn apply_move(&mut self, mov: Self::Move);
34    fn for_each_move<F: FnMut(Self::Move)>(&self, f: F);
35    fn eval_score(&self, player: Player) -> i32;
36
37    fn can_move(&self) -> bool {
38        let mut can_move = false;
39        self.for_each_move(|_| can_move = true);
40        can_move
41    }
42
43    fn solve(&self, depth: usize) -> Option<Self::Move> {
44        minimax(self, self.next_player(), depth).1
45    }
46}
47
48fn minimax<G: GameState>(game: &G, player: Player, depth: usize) -> (i32, Option<G::Move>) {
49    if depth == 0 {
50        (game.eval_score(player), None)
51    } else {
52        let mut max_mov = None;
53
54        let min = game.next_player() != player;
55        game.for_each_move(|mov| {
56            let mut game = game.clone();
57            game.apply_move(mov.clone());
58            let score = minimax(&game, player, depth - 1).0;
59            if max_mov
60                .as_ref()
61                .map(|(s, _)| (score > *s) ^ min)
62                .unwrap_or(true)
63            {
64                max_mov = Some((score, mov));
65            }
66        });
67
68        max_mov
69            .map(|(score, mov)| (score, Some(mov)))
70            .unwrap_or_else(|| (game.eval_score(player), None))
71    }
72}
turk/lib.rs

turk/
lib.rs
