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
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, } } } pub trait GameState: Clone { type Move: Clone; fn next_player(&self) -> Player; fn apply_move(&mut self, mov: Self::Move); fn get_moves(&self) -> Vec<Self::Move>; fn eval_score(&self) -> i32; fn solve_depth(&self, player: Player, depth: usize) -> Option<Self::Move> { min( self, if self.next_player() == player { -1 } else { 1 }, depth, ).1 } } fn min<G: GameState>(game: &G, flip: i32, depth: usize) -> (i32, Option<G::Move>) { if depth == 0 { (game.eval_score(), None) } else { game.get_moves() .into_iter() .map(|mov| { let mut this = game.clone(); this.apply_move(mov.clone()); (flip * min(&this, -1, depth - 1).0, Some(mov)) }) .min_by(|(a, _), (b, _)| a.cmp(b)) .unwrap_or_else(|| (game.eval_score(), None)) } }