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