ogs/
rc2.rs

1use crate::{Solver, SolverEvent};
2use crate::{Game, BreakingMoveIterator};
3use crate::rcsplit::RCSplit;
4use crate::stats::NimberStats;
5use crate::BitSet;
6
7pub struct RC2Solver<const DYNAMIC_REBUILD: bool = true, S = ()> {
8    game: Game,
9    breaking: [Vec<u8>; 2], // breaking moves splitted to even and odd
10    nimbers: Vec<u16>,
11    nimber_num: NimberStats,
12    split: [RCSplit; 2],
13    pub stats: S
14}
15
16impl<const DYNAMIC_REBUILD: bool, S: SolverEvent> Solver for RC2Solver<DYNAMIC_REBUILD, S> {   
17    type Stats = S;
18    
19    #[inline] fn stats(&self) -> &Self::Stats { &self.stats }
20    #[inline] fn nimbers(&self) -> &[u16] { &self.nimbers }
21    #[inline] fn game(&self) -> &Game { &self.game }
22    #[inline] fn capacity(&self) -> usize { self.nimbers.capacity() }
23
24    #[inline] fn with_stats(game: Game, stats: S) -> Self {
25        let breaking = Self::split_breaking_moves(&game);
26        Self { game, breaking, nimbers: Vec::new(), nimber_num: Default::default(), stats, split: [RCSplit::new(0), RCSplit::new(1)] }
27    }
28
29    #[inline] fn with_capacity_stats(game: Game, capacity: usize, stats: S) -> Self {
30        let breaking = Self::split_breaking_moves(&game);
31        Self { game, breaking, nimbers: Vec::with_capacity(capacity), nimber_num: Default::default(), stats, split: [RCSplit::new(0), RCSplit::new(1)] }
32    }
33
34    fn print_nimber_stat_to(&self, f: &mut dyn std::io::Write) -> std::io::Result<()> {
35        writeln!(f, "{:+}", self.nimber_num)?;
36        if !self.breaking[0].is_empty() { writeln!(f, "{:.0}", self.split[0])?; }
37        if !self.breaking[1].is_empty() { writeln!(f, "{:.1}", self.split[1])?; }
38        Ok(())
39    }
40}
41
42impl<const DYNAMIC_REBUILD: bool, S> RC2Solver<DYNAMIC_REBUILD, S> {
43    fn split_breaking_moves(game: &Game) -> [Vec<u8>; 2] {
44        let mut result = [Vec::<u8>::new(), Vec::<u8>::new()];
45        for m in game.breaking.iter().copied() {
46            result[(m & 1) as usize].push(m);
47        }
48        result
49    }   
50}
51
52#[inline(always)] fn in_r<const D: u16>(breaking: &[Vec<u8>; 2], split: &mut [RCSplit; 2], nim_pos: u16) -> bool {
53    if breaking[D as usize].is_empty() {
54        false   // R does not exist so nothing is inside, R_positions is empty
55    } else {
56        split[D as usize].in_r(nim_pos, D)
57    }
58}
59
60impl<const DYNAMIC_REBUILD: bool, S: SolverEvent> Iterator for RC2Solver<DYNAMIC_REBUILD, S> {
61    type Item = u16;
62
63    fn next(&mut self) -> Option<Self::Item> {
64        let mut option_nimbers = [0u64; 1<<(16-6)]; // 2**16 bits
65        let n = self.nimbers.len();
66        self.game.consider_taking(&self.nimbers, &mut option_nimbers, &mut self.stats);
67        for d in [0, 1] {
68            for b in &self.breaking[d] {
69                let b = *b as usize;
70                if b+1 >= n { break }
71                let after_take = n - b;
72                for i in &self.split[d].r_positions {
73                    if *i >= after_take { break; }
74                    option_nimbers.add_nimber(self.nimbers[*i] ^ self.nimbers[after_take-i]);
75                    self.stats.break_option();
76                }
77            }
78        }
79        let nd = n as u16 & 1;
80        let mut result = (option_nimbers.mex() << 1) | nd;
81        let mut to_check = [
82            in_r::<0>(&self.breaking, &mut self.split, result),
83            in_r::<1>(&self.breaking, &mut self.split, result)
84        ];
85        let mut moves = [
86            BreakingMoveIterator::for_slice(n, &self.breaking[0]).fuse(),
87            BreakingMoveIterator::for_slice(n, &self.breaking[1]).fuse()
88        ];
89        while to_check[0] || to_check[1] {
90            for d in [0, 1] {
91                while to_check[d] {
92                    if let Some((a, b)) = moves[d].next() {
93                        let option_nimber = self.nimbers[a] ^ self.nimbers[b];
94                        option_nimbers.add_nimber(option_nimber);
95                        if (result>>1) == option_nimber {
96                            result = (option_nimbers.mex() << 1) | nd;
97                            to_check = [
98                                in_r::<0>(&self.breaking, &mut self.split, result),
99                                in_r::<1>(&self.breaking, &mut self.split, result)
100                            ];
101                        }
102                        self.stats.break_option();
103                    } else { to_check[d] = false; }
104                }
105            }
106        }
107        self.nimber_num.count(result);
108        self.nimbers.push(result>>1);
109        for d in [0, 1] {
110            if self.breaking[d].is_empty() { continue; }
111            if DYNAMIC_REBUILD {
112                if self.split[d].r.contain_nimber(result) {
113                    if n != 0 { self.split[d].r_positions.push(n); }
114                    if self.split[d].should_rebuild_d(result, &self.nimber_num) {
115                        self.split[d].update_d(&self.nimber_num, &self.nimbers, d as u16, &mut self.stats);
116                        //self.split[d].rebuild_d(&self.nimber_num, &self.nimbers, d as u16);
117                    }
118                    //self.split[d].rebuild_d(&self.nimber_num, &self.nimbers, d as u16);
119                } else {
120                    self.split[d].add_to_c(result);
121                }
122            } else {
123                if n.is_power_of_two() {
124                    self.split[d].rebuild_d(&self.nimber_num, &self.nimbers, d as u16, &mut self.stats);
125                } else if self.split[d].r.contain_nimber(result) {
126                    if n != 0 { self.split[d].r_positions.push(n); }
127                } else {
128                    self.split[d].add_to_c(result);
129                }
130            }
131        }
132        //self.split.rebuild(&self.nimber, &self.nimbers);
133        Some(result>>1)
134    }
135}
ogs/rc2.rs

ogs/
rc2.rs
