ogdoad 1.0.0

Clifford algebras (with nilpotents) over the field-like subclasses of combinatorial games: nimbers, surreals, surcomplex.
Documentation 
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
73
74
75
76
77

//! The graph-level engine: [`LoopyGraph`], a thin wrapper over
//! [`kernel::outcomes`](crate::games::kernel).

use crate::games::kernel::{self, Outcome};

use super::catalogue::LoopyValue;

/// A loopy game as a finite move graph (`succ[v]` = the positions reachable from
/// `v` in one move). The move graph may be cyclic; outcomes are computed by the
/// retrograde [`kernel::outcomes`](crate::games::outcomes) (Win / Loss / Draw,
/// where **Loss = P-position** and **Draw = the loopy escape**).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LoopyGraph {
    succ: Vec<Vec<usize>>,
}

impl LoopyGraph {
    /// Build from explicit adjacency lists.
    pub fn new(succ: Vec<Vec<usize>>) -> LoopyGraph {
        LoopyGraph { succ }
    }

    /// Build from a move rule on positions `0..n` (the rule may produce cycles).
    pub fn from_rule<F: Fn(usize) -> Vec<usize>>(n: usize, moves: F) -> LoopyGraph {
        LoopyGraph {
            succ: (0..n).map(moves).collect(),
        }
    }

    /// The adjacency lists.
    pub fn succ(&self) -> &[Vec<usize>] {
        &self.succ
    }

    /// Win / Loss / Draw of every position (retrograde analysis).
    pub fn outcomes(&self) -> Vec<Outcome> {
        kernel::outcomes(&self.succ)
    }

    /// The Loss positions = **P-positions** (the player to move loses).
    pub fn loss_set(&self) -> Vec<usize> {
        self.indices_with(Outcome::Loss)
    }

    /// The Win positions = N-positions (the player to move wins).
    pub fn win_set(&self) -> Vec<usize> {
        self.indices_with(Outcome::Win)
    }

    /// The Draw positions — the loopy degree of freedom (neither player can force a
    /// win). Empty iff the game is effectively non-loopy.
    pub fn draw_set(&self) -> Vec<usize> {
        self.indices_with(Outcome::Draw)
    }

    fn indices_with(&self, want: Outcome) -> Vec<usize> {
        self.outcomes()
            .into_iter()
            .enumerate()
            .filter(|(_, o)| *o == want)
            .map(|(i, _)| i)
            .collect()
    }

    /// A coarse reading of a position as a catalogue [`LoopyValue`], via its
    /// impartial outcome only: a **Loss** is `0`, a **Draw** is `dud`. A **Win** is
    /// `None` — its value is a nonzero loopy nimber (use [`loopy_nim_values`](crate::games::loopy_nim_values)), not
    /// a named catalogue stopper. This is deliberately partial: an impartial move
    /// graph cannot express the Left/Right asymmetry of `on`/`off`/`over`/`under`.
    pub fn classify(&self, v: usize) -> Option<LoopyValue> {
        match self.outcomes().get(v)? {
            Outcome::Loss => Some(LoopyValue::Zero),
            Outcome::Draw => Some(LoopyValue::Dud),
            Outcome::Win => None,
        }
    }
}