depth_sweep/
depth_sweep.rs

1//! Canonical-state census across every depth (ply count) of Quantik,
2//! depth 1 through 16. Extends the depth-4 orbit-size survey: at each
3//! depth, folds every legal child onto its canonical representative
4//! (192-element symmetry group), tracks path-count multiplicity, and
5//! reports the orbit-size distribution — same technique as
6//! `depth4_orbit_histogram`, just carried through the whole game instead
7//! of stopping at depth 4.
8//!
9//! Unlike a full raw-state enumeration (which blows up combinatorially —
10//! ~232M raw transitions already at depth 5), this folds onto canonical
11//! representatives at *every* level, so the frontier processed at each
12//! step is bounded by the canonical state count, not the raw one.
13
14use quantik_core::bitboard::Bitboard;
15use quantik_core::game::{check_winner, has_winning_line, WinStatus};
16use quantik_core::moves::{apply_move, generate_legal_moves};
17use quantik_core::symmetry::SymmetryHandler;
18use std::collections::{BTreeMap, HashMap};
19use std::time::Instant;
20
21fn main() {
22    let mut frontier: HashMap<[u8; 16], (Bitboard, u64)> = HashMap::new();
23    frontier.insert(Bitboard::EMPTY.to_le_bytes(), (Bitboard::EMPTY, 1));
24
25    println!(
26        "depth,canonical_states,raw_boards,p0_wins_raw,p1_wins_raw,with_legal_moves,mean_orbit,min_orbit,max_orbit,elapsed_s"
27    );
28
29    for depth in 1..=16u32 {
30        let started = Instant::now();
31        let mut next: HashMap<[u8; 16], (Bitboard, u64)> = HashMap::new();
32        let mut p0_wins_raw: u64 = 0;
33        let mut p1_wins_raw: u64 = 0;
34
35        for (bb, mult) in frontier.values() {
36            for mv in generate_legal_moves(bb) {
37                let child = apply_move(bb, &mv);
38                if has_winning_line(&child) {
39                    match check_winner(&child) {
40                        WinStatus::Player0Wins => p0_wins_raw += mult,
41                        WinStatus::Player1Wins => p1_wins_raw += mult,
42                        WinStatus::NoWin => unreachable!(),
43                    }
44                    continue;
45                }
46                let canon = SymmetryHandler::find_canonical(&child);
47                let key = canon.to_le_bytes();
48                let entry = next.entry(key).or_insert((canon, 0));
49                entry.1 += mult;
50            }
51        }
52        frontier = next;
53
54        let canonical_states = frontier.len();
55        let raw_boards: u64 = frontier.values().map(|(_, m)| *m).sum();
56        let with_moves = frontier
57            .values()
58            .filter(|(bb, _)| !generate_legal_moves(bb).is_empty())
59            .count();
60
61        let mut orbit_sizes: Vec<usize> = frontier
62            .values()
63            .map(|(bb, _)| SymmetryHandler::orbit_size(bb))
64            .collect();
65        orbit_sizes.sort_unstable();
66        let mean = if orbit_sizes.is_empty() {
67            0.0
68        } else {
69            orbit_sizes.iter().sum::<usize>() as f64 / orbit_sizes.len() as f64
70        };
71        let min = orbit_sizes.first().copied().unwrap_or(0);
72        let max = orbit_sizes.last().copied().unwrap_or(0);
73
74        // Per-depth orbit-size histogram, written alongside the summary line.
75        let mut hist: BTreeMap<usize, u64> = BTreeMap::new();
76        for bb in frontier.values() {
77            *hist.entry(SymmetryHandler::orbit_size(&bb.0)).or_insert(0) += 1;
78        }
79        let hist_str: Vec<String> = hist.iter().map(|(s, c)| format!("{s}:{c}")).collect();
80
81        println!(
82            "{depth},{canonical_states},{raw_boards},{p0_wins_raw},{p1_wins_raw},{with_moves},{mean:.2},{min},{max},{:.3}",
83            started.elapsed().as_secs_f64()
84        );
85        eprintln!("  depth {depth} orbit histogram: {}", hist_str.join(" "));
86
87        if canonical_states == 0 {
88            eprintln!("frontier empty at depth {depth} — every line of play has ended by here");
89            break;
90        }
91        if with_moves == 0 {
92            eprintln!("all depth-{depth} states are dead ends (no legal moves) — game always over by depth {}", depth + 1);
93        }
94    }
95}
depth_sweep/depth_sweep.rs

depth_sweep/
depth_sweep.rs
