two_player/games/
fibonacci_nim.rs

1//! [Fibonacci nim](https://en.wikipedia.org/wiki/Fibonacci_nim)
2
3use crate::{player::Player, state::State};
4
5#[derive(Debug, Clone)]
6pub struct FibonacciNimState {
7    remaining: usize,
8    quota: usize,
9    turn: Player,
10}
11
12impl FibonacciNimState {
13    pub fn initial(start: usize) -> Self {
14        Self {
15            remaining: start,
16            quota: start - 1,
17            turn: Player::FirstPlayer,
18        }
19    }
20
21    pub fn remaining(&self) -> usize {
22        self.remaining
23    }
24
25    pub fn quota(&self) -> usize {
26        self.quota
27    }
28}
29
30impl State for FibonacciNimState {
31    fn turn(&self) -> Player {
32        self.turn
33    }
34
35    fn winner(&self) -> Option<Player> {
36        if self.remaining == 0 {
37            Some(self.turn.opposite())
38        } else {
39            None
40        }
41    }
42
43    fn valid_moves(&self) -> impl Iterator<Item = Self> {
44        (1..=self.quota).map(|i| {
45            let remaining = self.remaining - i;
46            Self {
47                remaining,
48                quota: (2 * i).min(remaining),
49                turn: self.turn.opposite(),
50            }
51        })
52    }
53}
54
55#[cfg(test)]
56mod test {
57    use super::*;
58    use crate::valuation::best_move_finite;
59
60    #[test]
61    fn test_initial() {
62        let initial = FibonacciNimState::initial(5);
63        assert_eq!(initial.turn(), Player::FirstPlayer);
64        assert_eq!(initial.winner(), None);
65        assert_eq!(initial.valid_moves().count(), 4);
66    }
67
68    #[test]
69    fn test_small_game() {
70        let state = FibonacciNimState::initial(2);
71        assert_eq!(state.turn(), Player::FirstPlayer);
72        assert_eq!(state.winner(), None);
73        let moves: Vec<_> = state.valid_moves().collect();
74        assert_eq!(moves.len(), 1, "{state:?} -> {moves:?}");
75
76        let state = &moves[0];
77        assert_eq!(state.turn(), Player::SecondPlayer);
78        assert_eq!(state.winner(), None);
79        let moves: Vec<_> = state.valid_moves().collect();
80        assert_eq!(moves.len(), 1, "{state:?} -> {moves:?}");
81
82        let state = &moves[0];
83        assert_eq!(state.winner(), Some(Player::SecondPlayer), "{state:?}");
84    }
85
86    #[test]
87    fn test_best_move() {
88        let fib = [2, 3, 5, 8, 13, 21];
89
90        for n in 2..22 {
91            let initial = FibonacciNimState::initial(n);
92            let expected_winner = if fib.contains(&n) {
93                Player::SecondPlayer
94            } else {
95                Player::FirstPlayer
96            };
97            let Some((valuation, best_move)) = best_move_finite(&initial) else {
98                panic!("No best move for {initial:?}");
99            };
100            assert_eq!(
101                valuation.winner, expected_winner,
102                "{initial:?} -> ({valuation:?}, {best_move:?})"
103            );
104        }
105    }
106}
two_player/games/fibonacci_nim.rs

two_player/games/
fibonacci_nim.rs
