igs/solver/
mod.rs

1use crate::game::{Game, SimpleGame, DecomposableGame};
2use crate::dbs::{NimbersProvider, NimbersStorer};
3use crate::moves::{ComponentsInfo, SimpleGameMoveSorter, DecomposableGameMoveSorter};
4use crate::nimber_set::NimberSet;
5
6pub mod def;
7pub use self::def::DefSimpleGameSolver as _;
8pub use self::def::DefDecomposableGameSolver as _;
9
10pub mod lvb;
11pub use self::lvb::LVBSimpleGameSolver as _;
12pub use self::lvb::LVBDecomposableGameSolver as _;
13
14pub mod br;
15pub use self::br::BRSimpleGameSolver as _;
16pub use self::br::BRDecomposableGameSolver as _;
17
18pub mod dedicated;
19pub use self::dedicated::{SolverForSimpleGame, SolverForDecomposableGame};
20
21pub mod stats;
22pub use stats::StatsCollector;
23use std::collections::HashMap;
24
25mod outcome;
26
27/// Solver that calculate nimbers of games.
28///
29/// It implements many methods:
30/// - by definition,
31/// - LV method (improved by Beling),
32/// - Beling's method (described by Beling and Rogalski)
33///
34/// Empty type "()" can be given as transposition_table or const_db to calculate without these nimber bases.
35/// Also a tuple of databases (const_db1, const_db2, ...) can be given as const_db to use multiple const databases.
36pub struct Solver<'g, G, TT = HashMap::<<G as Game>::Position, u8>, EDB = (), SORTER = (), STATS = ()>
37    where G: Game,
38          TT: NimbersProvider<G::Position> + NimbersStorer<G::Position>,
39          EDB: NimbersProvider<G::Position>,
40          STATS: StatsCollector
41{
42    /// Game to solve.
43    pub game: &'g G,
44
45    /// Transposition table used by the solver.
46    pub transposition_table: TT,
47
48    /// Const (usually end game) database used by the solver.
49    pub const_db: EDB,
50
51    /// Move sorter used by the solver.
52    pub move_sorter: SORTER,
53
54    /// Statistics collector.
55    pub stats: STATS
56
57    //pub allocator: Bump
58}
59
60impl<'a, G, TT, EDB, SORTER, STATS> Solver<'a, G, TT, EDB, SORTER, STATS>
61    where G: Game,
62          TT: NimbersProvider<G::Position> + NimbersStorer<G::Position>,
63          EDB: NimbersProvider<G::Position>,
64          STATS: StatsCollector
65{
66    #[inline(always)]
67    fn nimber_from_tt(&mut self, p: &G::Position) -> Option<u8> {
68        self.stats.tt_read();
69        self.transposition_table.get_nimber_and_self_organize(p)
70    }
71
72    #[inline(always)]
73    fn nimber_from_const_db(&mut self, p: &G::Position) -> Option<u8> {
74        self.stats.const_db_read();
75        self.const_db.get_nimber_and_self_organize(p)
76    }
77
78    #[inline(always)]
79    fn nimber_from_any_db(&mut self, p: &G::Position) -> Option<u8> {
80        self.nimber_from_const_db(&p).or_else(|| self.nimber_from_tt(&p))
81    }
82
83    pub fn new(game: &'a G, transposition_table: TT, const_db: EDB, move_sorter: SORTER, stats: STATS) -> Self {
84        Self { game, transposition_table, const_db, move_sorter, stats /*, allocator: Bump::with_capacity(16*1_024*1_024) Bump::new()*/ }
85    }
86}
87
88impl<G, TT, EDB, SORTER, STATS> Solver<'_, G, TT, EDB, SORTER, STATS>
89    where G: SimpleGame,
90          TT: NimbersProvider<G::Position> + NimbersStorer<G::Position>,
91          EDB: NimbersProvider<G::Position>,
92          SORTER: SimpleGameMoveSorter<G>,
93          STATS: StatsCollector
94{
95    #[inline(always)]
96    fn etc_simple(&mut self, position: &<G as Game>::Position) -> (u16, G::NimberSet, Vec<<G as Game>::Position>) {
97        self.stats.etc();
98        let moves_count = self.game.moves_count(&position);
99        let mut nimbers_to_skip = G::NimberSet::empty();
100        let mut moves: Vec::<G::Position> = Vec::with_capacity(moves_count as usize);
101        for m in self.game.successors_in_heuristic_ordered(&position) {
102            if let Some(v) = self.nimber_from_any_db(&m) {
103                self.stats.db_skip(v);
104                nimbers_to_skip.append(v);
105            } else {
106                moves.push(m);
107            }
108        }
109        self.move_sorter.sort_moves(&self.game, &mut moves);
110        (moves_count, nimbers_to_skip, moves)
111    }
112}
113
114impl<G, TT, EDB, SORTER, STATS, DP> Solver<'_, G, TT, EDB, SORTER, STATS>
115    where G: DecomposableGame<DecomposablePosition=DP>,
116          TT: NimbersProvider<G::Position> + NimbersStorer<G::Position>,
117          EDB: NimbersProvider<G::Position>,
118          SORTER: DecomposableGameMoveSorter<G>,
119          STATS: StatsCollector
120{
121    #[inline(always)]
122    fn etc_decomposable(&mut self, position: &&<G as Game>::Position) -> (u16, G::NimberSet, Vec<<G as Game>::Position>, Vec<ComponentsInfo>) {
123        self.stats.etc();
124        let moves_count = self.game.moves_count(position);
125        let mut nimbers_to_skip = G::NimberSet::empty();
126        let mut move_components: Vec::<G::Position> = Vec::with_capacity(moves_count as usize * 2);
127        let mut moves: Vec::<ComponentsInfo> = Vec::with_capacity(moves_count as usize);
128        for composed_move in self.game.successors_in_heuristic_ordered(&position) {
129            let info = self.decompose(&composed_move, &mut move_components);
130            if info.len == 0 {  // nimber is known, for sure nimber of position != info.nimber
131                nimbers_to_skip.append(info.nimber);
132            } else {
133                moves.push(info);
134            }
135        }
136        self.move_sorter.sort_moves(&self.game, &mut moves, &mut move_components);
137        (moves_count, nimbers_to_skip, move_components, moves)
138    }
139}
140
141
142impl<G, TT, EDB, SORTER, STATS, DP> Solver<'_, G, TT, EDB, SORTER, STATS>
143    where G: DecomposableGame<DecomposablePosition=DP>,
144          TT: NimbersProvider<G::Position> + NimbersStorer<G::Position>,
145          EDB: NimbersProvider<G::Position>,
146          STATS: StatsCollector
147{
148    /// Decomposes position `composed_move`, and returns info about its components.
149    /// Nimbers of components described by `const_db` or `transposition_table` are xored and stored in `info.nimber`.
150    /// The rest of components are pushed to `move_components` and account in `info.len`.
151    fn decompose(&mut self, composed_move: &DP, move_components: &mut Vec<<G as Game>::Position>) -> ComponentsInfo {
152        let mut info = ComponentsInfo::new(move_components.len());
153        for c in self.game.decompose(&composed_move) {
154            if let Some(v) = self.nimber_from_any_db(&c) {
155                self.stats.db_skip(v);
156                info.nimber ^= v;
157            } else {
158                move_components.push(c);
159                info.len += 1;
160            }
161        }
162        info
163    }
164
165}
igs/solver/mod.rs

igs/solver/
mod.rs
