two_player/games/
three_mens_morris.rs

1//! [Three men's morris](https://en.wikipedia.org/wiki/Three_men%27s_morris)
2
3use std::fmt::Debug;
4
5use crate::{player::Player, state::State};
6
7fn piece_char(p: Option<Player>) -> char {
8    match p {
9        None => '.',
10        Some(Player::FirstPlayer) => 'X',
11        Some(Player::SecondPlayer) => 'O',
12    }
13}
14
15#[derive(Clone, PartialEq, Eq, Hash)]
16pub struct ThreeMensMorris {
17    board: [[Option<Player>; 3]; 3],
18    turn: Player,
19}
20
21impl Debug for ThreeMensMorris {
22    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
23        writeln!(f, "ThreeMensMorris {{")?;
24        writeln!(f, "  turn: {}", piece_char(Some(self.turn)))?;
25        writeln!(f, "  board:")?;
26        for row in self.board {
27            write!(f, "    ")?;
28            for p in row {
29                write!(f, "{}", piece_char(p))?;
30            }
31            writeln!(f)?;
32        }
33        write!(f, "}}")?;
34        Ok(())
35    }
36}
37
38impl ThreeMensMorris {
39    pub fn initial() -> Self {
40        Self {
41            board: Default::default(),
42            turn: Player::FirstPlayer,
43        }
44    }
45
46    pub fn board(&self) -> &[[Option<Player>; 3]; 3] {
47        &self.board
48    }
49
50    fn find(&self, piece: Option<Player>) -> Vec<(u8, u8)> {
51        self.board
52            .iter()
53            .enumerate()
54            .flat_map(|(y, row)| {
55                row.iter().enumerate().filter_map(move |(x, p)| {
56                    if p == &piece {
57                        Some((y as u8, x as u8))
58                    } else {
59                        None
60                    }
61                })
62            })
63            .collect()
64    }
65
66    fn is_winner(&self, piece: Player) -> bool {
67        fn diff(a: (u8, u8), b: (u8, u8)) -> (u8, u8) {
68            (a.0.wrapping_sub(b.0), a.1.wrapping_sub(b.1))
69        }
70
71        let positions = self.find(Some(piece));
72        if positions.len() < 3 {
73            return false;
74        }
75
76        diff(positions[0], positions[1]) == diff(positions[1], positions[2])
77    }
78}
79
80impl State for ThreeMensMorris {
81    fn turn(&self) -> Player {
82        self.turn
83    }
84
85    fn winner(&self) -> Option<Player> {
86        [Player::FirstPlayer, Player::SecondPlayer]
87            .into_iter()
88            .find(|p| self.is_winner(*p))
89    }
90
91    fn valid_moves(&self) -> impl Iterator<Item = Self> {
92        if self.winner().is_some() {
93            return Box::new(std::iter::empty()) as Box<dyn Iterator<Item = Self>>;
94        }
95
96        let current_pieces = self.find(Some(self.turn));
97
98        let empty_positions = self.find(None);
99        if current_pieces.len() < 3 {
100            Box::new(empty_positions.into_iter().map(|(y, x)| {
101                let mut new_state = self.clone();
102                new_state.board[y as usize][x as usize] = Some(self.turn);
103                new_state.turn = self.turn.opposite();
104                new_state
105            }))
106        } else {
107            Box::new(empty_positions.into_iter().flat_map(move |(to_y, to_x)| {
108                let current_pieces = current_pieces.clone();
109                current_pieces.into_iter().map(move |(from_y, from_x)| {
110                    let mut new_state = self.clone();
111                    new_state.board[from_y as usize][from_x as usize] = None;
112                    new_state.board[to_y as usize][to_x as usize] = Some(self.turn);
113                    new_state.turn = self.turn.opposite();
114                    new_state
115                })
116            }))
117        }
118    }
119}
120
121#[cfg(test)]
122mod test {
123    use super::*;
124    use crate::valuation::{best_move_finite, count_reachable_states};
125
126    #[test]
127    fn test_initial() {
128        let initial = ThreeMensMorris::initial();
129        assert_eq!(initial.turn(), Player::FirstPlayer);
130        assert_eq!(initial.winner(), None);
131        assert_eq!(initial.valid_moves().count(), 9);
132    }
133
134    #[test]
135    fn test_reachable_states() {
136        const TOTAL_STATES: usize = 5390;
137
138        // After 6 moves every piece has been placed.
139        // However as the last piece was placed by the second player,
140        // the first player can't be the winner.
141        // Thus it requires 7 moves to make the first player win with all 6 pieces placed.
142        const MAX_DEPTH: usize = 7;
143
144        let initial = ThreeMensMorris::initial();
145        assert_eq!(count_reachable_states(initial), (TOTAL_STATES, MAX_DEPTH));
146    }
147
148    #[ignore]
149    #[test]
150    fn test_best_move() {
151        let res = best_move_finite(&ThreeMensMorris::initial());
152        dbg!(res);
153    }
154}
two_player/games/three_mens_morris.rs

two_player/games/
three_mens_morris.rs
