two_player/
valuation.rs

1use std::{
2    cmp::Ordering,
3    collections::{HashSet, VecDeque},
4    hash::Hash,
5};
6
7use crate::{player::Player, state::State};
8
9pub fn count_reachable_states<S: State + Clone + Eq + Hash + std::fmt::Debug>(
10    initial: S,
11) -> (usize, usize) {
12    let mut seen = HashSet::new();
13    let mut queue = VecDeque::new();
14
15    queue.push_back((0, initial));
16
17    let mut max_depth = 0;
18    while let Some((depth, state)) = queue.pop_front() {
19        if !seen.insert(state.clone()) {
20            continue;
21        }
22
23        max_depth = max_depth.max(depth);
24
25        for new_state in state.valid_moves() {
26            queue.push_back((depth + 1, new_state));
27        }
28    }
29
30    (seen.len(), max_depth)
31}
32
33#[derive(Debug, PartialEq, Eq, Hash)]
34pub struct Valuation {
35    pub winner: Player,
36    pub depth: usize,
37}
38
39impl Valuation {
40    pub fn cmp_with(&self, other: &Valuation, turn: Player) -> Ordering {
41        if self == other {
42            return Ordering::Equal;
43        }
44
45        if self.winner == other.winner {
46            let ord = if other.depth < self.depth {
47                Ordering::Less
48            } else {
49                Ordering::Greater
50            };
51            if turn == self.winner {
52                ord
53            } else {
54                ord.reverse()
55            }
56        } else if turn == other.winner {
57            Ordering::Less
58        } else {
59            Ordering::Greater
60        }
61    }
62
63    pub fn is_better_than(&self, other: &Valuation, turn: Player) -> bool {
64        other.cmp_with(self, turn).is_lt()
65    }
66}
67
68pub fn best_move_finite<S: State + Clone>(state: &S) -> Option<(Valuation, S)> {
69    if let Some(winner) = state.winner() {
70        return Some((Valuation { winner, depth: 0 }, state.clone()));
71    }
72
73    let turn = state.turn();
74
75    let mut best: Option<(Valuation, S)> = None;
76    for s in state.valid_moves() {
77        if let Some((mut best_val, _)) = best_move_finite(&s) {
78            if best
79                .as_ref()
80                .map_or(true, |b| best_val.is_better_than(&b.0, turn))
81            {
82                best_val.depth += 1;
83                best = Some((best_val, s));
84            }
85        }
86    }
87    best
88}
two_player/valuation.rs

two_player/
valuation.rs
