Skip to content

Avenues to explore: verification discipline, standards, frontier search, cross-org follow-ups #53

Open

Description

@abu-aska

This issue lists every avenue that came out of the 2026-11-14 session (PR #52), so the team can split them up. Each item has the evidence so far, a first step, and a done-when. To claim one, comment claiming A1 (etc.) and open a draft PR that references this issue. Please post negative results here too; they save the next person the compute.

Related: #22 (III-21 phase analysis and where to aim), #38 (III-14 15x7 heuristic inconsistency), #44, #46, #49 (fixed by #52).

A. Verification discipline

These are things that would have caught today's regressions on the day they landed.

  • A1. Hashed perft in CI. For every catalog room, count the distinct states reachable at each depth (no-op moves pruned) and hash them. Then compare the native engine against PuzzleScriptOracle.
    • Evidence: plain counts are identical for the old and new engines on all rooms, I-22 included. With a per-depth state-digest hash, the old engine diverges on I-22 at depth 1 (1c74 vs f9d2 in the low 16 bits, where fixed native and Python agree). II-12's divergence lies deeper than 6 moves (the random fuzz found it), so perft complements test_engine_differential; it does not replace it.
    • First step: add a perft mode to cpp/soko_engine.cpp and a Python counterpart, then compare depth 3–4 on all 66 rooms.
    • Done when: the test fails on the pre-Restore engine parity, reconcile the evidence boundary, and add CI #52 engine and passes on HEAD.
  • A2. Bench signature. Stockfish puts the node count of a fixed search in every commit, so any behaviour change shows up. Here: run node-budgeted prove_lb/solve on 4 or 5 fixed rooms and record nodes_expanded, edge_consistency_checks and floors in a committed bench.json. CI compares against it, and any change must update the file in the same commit and say why. The vault overwrite would have changed this number.
  • A3. Remove wall-clock dependence from tests. For example, test_mcp_server asserts a III-14 floor ≥ 31 within budget_sec=8. One local full-suite run failed once under heavy CPU load and passed on three reruns; the test wasn't captured. Done when: no assertion depends on wall time; use node or state budgets instead.
  • A4. Native late phase after a death. Native run_late returns at the first hero death, while PuzzleScriptOracle._run_late finishes doors, the gate and the remaining kills. 36 of 370 sampled death routes differ in more than the corpse cell (review thread on tests/test_engine_differential.py, Restore engine parity, reconcile the evidence boundary, and add CI #52). This affects rendering only, because death routes are never wins. Done when: post-death frames match modulo the corpse marker and the differential test compares them.
  • A5. SPRT harness for search changes, in the style of Stockfish's fishtest. Accept a search or heuristic change only after a sequential paired test against the previous version on fixed rooms and budgets. This gives docs/research-loop.md a stopping rule.
  • A6. Controls that cannot silently stop.
    • Write the list of must-fail controls into each certificate (pattern: Foundation-0/incentre-lattices certlib.must_fail).
    • Add a "tier swap" corruption test, where a claim promoted from bound to VERIFIED must fail (pattern: Foundation-0/f0 tests/run_gate_corruptions.py).
    • Background: today's 87 → 84 control had been seeded with 84, so it could not fail.
  • A7. Relabel the auditor's lint pass. checker_auditor.audit_builtin_soko_oracles() returns epistemic_status: VERIFIED for a static lint. In the org's vocabulary, VERIFIED means a finite replayed check, so use something like LINT_PASS.
  • A8. Refresh the catalog's external floors through tools/import_catalog.py. The stored values are III-14 43, III-20 74 and III-21 268; the frontier's accepted floors are 44, 76 and 270 (banteg proofs, 2026-11-13). catalog.json is in the TCB, so give this its own PR.
  • A9. Optimize/solve errors should carry epistemic_status (the third point of Engine rebuild unlocks the TCB, then every route is rejected with a misleading error #49), so a rejected seed reports why, not just the alive/win triple.

B. Standards conformance

Foundation-0 REPO-STANDARD.md and the Proven-Commons Verified Bar v2.

  • B1. Repository layout from REPO-STANDARD section D: a make verify target, results/<name>/{PROOF.md,verify.py,certificate.json}, pinned requirements.txt, CI that regenerates certificates and diffs them against the committed ones, and docs/audit.md. Foundation-0/incentre-lattices verify.yml is a good template.
  • B2. Status page and test record.
    • README sections: Status / What is proved / What is not proved / What you must trust / Re-check it.
    • A committed tests/TEST-RESULTS.md (oracle and version, seed, case count, zero failures) that a fresh run reproduces.
  • B3. Process rules. These are owner decisions.
  • B4. CI hardening:
    • pin actions by commit SHA
    • add a Python matrix 3.10–3.13 (pyproject says >=3.10)
    • add a header saying what a green run does and does not prove

C. Frontier search

Open rooms on 2026-11-14:

Room Proven Record Holder
III-14 44 48 @SJanuskas
III-20 76 84 @a1kindus
III-21 270 316 @futarchist

What has been ruled out on III-21:

  • every FIFO reordering of the record's 37 per-hero runs (experiments/macro_scheduler, 1.78M states)
  • long-range BFS shortcuts at depth 12 with 1.5M states per position (experiments/long_shortcut; a depth-16 run is still going)
  • the Why we aren't breaking records yet, and where to aim next #22 one-shot planner from keys 232 and 246

The record is locally tight, so a new one needs a different plan.

  • C1. NRPA (Nested Rollout Policy Adaptation) on III-21, over macro moves (one hero's segment at a time). This is the method behind single-player puzzle records such as Morpion Solitaire. It learns a policy from the best sequences found so far, which suits a "needs a different plan" problem. Every rollout is replayed by the oracles.
  • C2. Goal assignment and per-hero decomposition. Enumerate which hero ends on which goal and compute each hero's own shortest-walk-plus-push cost per assignment. That gives a per-room lower bound (Why we aren't breaking records yet, and where to aim next #22 suggestion 3) and ranks candidate plans.
  • C3. Endgame tablebase for III-21. Search backwards from goal configurations to get exact distances for the final phase (heroes near the centre column). Use it as an exact heuristic close to the goal, and to search from both ends.
  • C4. Splice between public replays. The frontier publishes every III-21 record from 341 down to 316, by different people with different plans. Index every state on every replay. Where two replays share a state, or come within a short BFS bridge of each other, combine the cheapest prefix with the cheapest suffix. This is cheap and checks whether recombining known plans beats 316.
  • C5. Relaxed long-range shortcuts.
    • Match trajectory states modulo the active hero's identity (fix it up with A presses).
    • Disk-backed BFS to go past depth 16.
    • Seed from the alternative records in C4, not just the current one.
  • C6. Zobrist incremental hashing in the native engine. Today every step rehashes all cells (299 on III-21), so incremental hashing speeds up every search here.
  • C7. III-14 above 44. Exact search past f = 44 needs a consistent heuristic or reopening (III-14 15x7 prover: heuristic inconsistency means the ≥34 floor is not yet certified #38). Closing this room means either a 47-key route or a proof that 48 is optimal.
  • C8. III-20 guide variants. The 87 → 84 gain came from a mirrored guide. Try other structural transforms as guides; the long-range shortcut finds nothing on 87.
  • C9. Abstract phase-order search (Why we aren't breaking records yet, and where to aim next #22 suggestion 2): solve the order of phases on abstract states, then fill each leg in with exact search.

D. Cross-org follow-ups

These touch other repositories, so they need an owner's decision first. Found by a read-only audit; details on request.

  • D1. Open PRs Foundation-0/math0#9 and Foundation-0/f0#36 still say III-14 "certifies floor ≥ 35", and f0#36 says III-20 was cleared "across 3 independent engines". soko withdrew ≥35 in bb4dce5. Restore engine parity, reconcile the evidence boundary, and add CI #52 shows the third engine disagreed with the other two on multi-active-hero rooms (published III-14/III-20/II-22 bounds unaffected).
  • D2. Foundation-0/formal-claims-audit#16 doesn't parse (IndentationError and SyntaxError), so it would turn that repo's CI red. soko's checker_auditor.py has diverged from it: soko's copy flags def check(x): return True, while the PR's copy passes it. soko's "synchronized two-way" docstring is therefore not accurate.
  • D3. math0, physics0, Proven-Commons/dns and Proven-Commons/png have no CI.

Claimed

I'm starting on A1 (hashed perft) and C4 (splicing between public replays). I'll post results here, negative ones included.

Activity

  1. abu-aska commented on Nov 14, 2026

    @abu-aska
    CollaboratorAuthor

    Progress on A1 and C4 (both on PR #52)

    A1, hashed perft: done (2ab8b69). The native engine has a perft mode, and tests/test_perft.py compares it with PuzzleScriptOracle on all 66 rooms to depth 4. It takes about 8 s.

    C4, splicing public replays: done, negative (95113e6, experiments/long_shortcut/splice.cpp). I merged every public record replay for the three open rooms into one exact-state graph, took its shortest path, and searched BFS bridges from every union state into any state with a known cost to win.

    Room Routes Union states Union shortest Bridges (depth / cap per state) Result
    III-21 30 (316–589, 8 authors) 4,551 316 8 / 40k 316
    III-20 9 (84–145) 725 84 12 / 400k 84
    III-14 7 (48–116) 409 48 14 / 400k 48

    C5, related: the long-range shortcut also finds nothing on III-20's 84 at depth 14. Runs on III-21's 316 at depth 16 and III-14's 48 at depth 16 are still going, and I'll add their results here.

    So each record is already the best recombination of every published plan, and is locally tight within these limits. A shorter route needs a plan nobody has published. Of the remaining items, that points at C1 (NRPA), C2/C9 (plan-level search) and C3 (tablebase), not more local polishing.

    Next: a time-boxed NRPA prototype on III-14. It's the smallest board (15×7) with the shortest record, which is where NRPA is known to work. If it reproduces 48 from scratch, I'll point it at 44–47.


    Generated by Claude Code

  2. abu-aska commented on Nov 14, 2026

    @abu-aska
    CollaboratorAuthor

    Progress: A2, A3, A9, C5, D1, D2 and a hash bug (all on PR #52)

    A2, bench signature: done (84011cc). tests/bench.json records prove_lb node counts and floors on six rooms, and perft count:hash on four. tests/test_bench.py compares against it; regenerate with --write. The hash change below left every bench number unchanged, which is expected, since exact-state search doesn't depend on the hash.

    A3: partly done (5f9cb4b). The III-14 prove_floor test had no headroom: it asked for a floor within 8 s and took 7.46 s here. It now asserts the result instead: bound 31, termination exhausted, floor 32, with a 60 s safety budget. test_07 still gives the optimizer a 35 s budget, so A3 stays open for that test.

    A9: done (2041614). A rejected seed now names the verifier's epistemic_status and differential_match.

    New finding: weak state hash (ba0c864). This bears on C6 and on the F-04 story. hash64 absorbed each 8-byte word with a multiply only, which never carries high bits downward. I ran BFS over 8M exactly distinct states per room:

    Room Full 64-bit collisions, old hash New hash Birthday expectation
    III-14 26,230 0 2×10⁻⁶
    III-20 30,912 0 2×10⁻⁶
    III-21 13,318 0 2×10⁻⁶

    prove_lb already compared full states, so no bound changes. The hash-only sets in solve and optimize were silently dropping 0.2–0.8% of distinct states, and they no longer do. The "22,658 collisions at 27.66M states" in the F-04 write-ups was this weak hash, not a birthday effect. C6 (incremental Zobrist hashing for speed) is still open.

    Record attempts: negative, and I'm stopping here.

    • C5: the long shortcut at depth 16 finds nothing on III-21's 316 (3M states per position, 2,078 s) or III-14's 48 (2M, 456 s).
    • I didn't build the NRPA prototype I said I'd try. I tested a cheaper question first: can a bounded beam that prunes on g + h > B, using the prover's admissible heuristic, rediscover III-14's 48 at all? It can't, even at width 1M. The heuristic plateaus around g = 30, where 403,523 candidates have a lower h than the record's own state (experiments/bounded_beam). Heuristic-guided beams can't settle III-14, so NRPA (C1), which learns from good sequences rather than from h, is still the right next try.
    • The engine's optimize mode (tube beam 200k, window 16), rerun after the hash fix: III-20 stays 84 (69 s), III-21 stays 316 (142 s).

    C1, C2, C3, C7 and C9 are open for whoever wants them.

    D1: done. I posted corrections on math0#9 and f0#36: the withdrawn III-14 floor of 35 (on the 15x7 catalog board, soko has 38 or more and the frontier has 44), the moved III-20 and III-21 floors, the "3 independent engines" wording, and the hash cause behind F-04.

    D2: not posted. This session can't use formal-claims-audit's API. Both files in #16 still fail to compile on 467a580. Once those two lines are fixed, the PR's auditor passes def check(x): return True and assert True as clean, and soko's copy flags both. A drafted comment is with the owner.

    Still open from A: A4, A5, A6, A7 (the auditor's lint pass is still labelled VERIFIED) and A8 (catalog floors 43/74/268 should be 44/76/270).


    Generated by Claude Code

  3. abu-aska commented on Nov 14, 2026

    @abu-aska
    CollaboratorAuthor

    E. Ideas from other games' AI, and what one test showed

    The owner asked how other game engines, simulators and game AI approach optimization. This section maps what transfers, then reports the one family I tested today.

    The game-theory frame. Heroes of Sokoban has one player, so minimax, alpha-beta and regret minimization have nothing to work on. The frontier itself is two-sided, though: record setters push the ceiling down and provers push the floor up. LP duality, the same theorem as von Neumann's minimax, connects the two. An admissible heuristic is a dual-feasible certificate, and a room is closed when the primal (a route) meets the dual (a bound). Optimal cost partitioning and operator counting (Pommerening et al.) make that LP explicit. On this view the open rooms need better duals, not just more search, and the measurement below agrees.

    Source Technique soko analogue Status
    Chess engines perft, bench signature, SPRT A1, A2, A5 A1, A2 done
    Chess endgame tablebases; forward-backward RL for Sokoban retrograde search from the goals C3 open
    Atari planners (IW, BFWS) novelty instead of a heuristic experiments/width_search tested, negative (below)
    Festival / FESS, the first program to solve all 90 XSokoban levels search biased toward progress in an abstract feature space E1 open
    Rolling Stone pattern search: at risky nodes, find small object subsets whose conflicts raise the lower bound, and reuse them. Removing it dropped solved levels from 53 to 32 E2 open
    Classical planning admissible landmark heuristics (LM-cut), operator counting E3, overlaps C2 open
    Plan neighborhood graph search (Nakhost & Müller 2010) shortest path in a neighbourhood of known plans what splice.cpp does (C4) done, negative
    MAPF-LNS (Li et al. 2021) replan a few agents while the rest stay fixed E4: re-search one or two heroes' segments with the rest pinned (the macro scheduler only reordered segments) open
    Rubik's cube, Kociemba two-phase reach a subgoal set, finish exactly, and keep trying longer phase-1 solutions for a shorter total C9 with "all switches covered" as the phase boundary open
    AlphaZero, MuZero, Sokoban RL learned value function E5: a learned, inadmissible ranking for record beams (never for floors) open
    Single-player MCTS, NRPA policy learned from the best sequences found C1 open

    Tested today: width-based search (629db2f, experiments/width_search).

    • IW(2) solves I-1, I-22 and III-22 optimally, and III-15 in 72 against an optimum of 69, keeping 3,114 states. On all three open rooms it runs out of novel states without a route.
    • A bounded beam with BFWS-style novelty selection (g + h > B pruning unchanged) was positive-controlled on III-14 at bound 48, width 200k, tracking the 48-key route. Pure heuristic order keeps that route through g = 31. Any novelty share does worse: through g = 29 at 10–50%, and through g = 17 with novelty first.

    What that shows. Along the 48-key route, the prover's heuristic starts at 22 against a proven 44. It then stays flat at 7–8 from key 24 to key 39, while the route closes a gap of 17 down to 2. Those keys are the switch setup: the Druid turns border walls into crates, the Bard's aura herds them onto the nine purple switches, and the Druid sets them as walls in column 6. No beam ordering can rank keys the bound can't see. E2 and E3, a stronger bound, are the highest-value items here: one improvement raises the provable floor and makes every record search sharper. For III-14 a natural start is a landmark bound: each uncovered switch needs a weighing object, objects come from harvested border walls, and harvesting costs moves the current PDBs don't charge.

    Unclaimed; I'm stopping here for this session.


    Generated by Claude Code

  4. ahrazzle commented on Nov 19, 2026

    @ahrazzle
    Owner

    Seven open pull requests map items on this roadmap to verified fixes, dual-bound provers, and benchmark receipts:

    Roadmap item Pull request What changed and measured result
    A8 PR 57 (9ca27e71) Refreshes external Frontier floors in the 66-room catalog (III-14: 44, III-20: 77, III-21: 270, trilogy floor sum 3,006, ceiling sum 3,063, 21/21 SHA256SUMS).
    F-05..F-08 PR 58 (4f83c797) Closes four formal_kernel.py soundness gaps: blocks float/NaN synthesis under exact_arithmetic_only=True, downgrades state-budget-truncated Dijkstra from PROVEN to feasible-only, checks concrete successor invariants independent of coarse projections, and removes finite 10^15 / 10^18 distance sentinels.
    PR 20 salvage PR 59 (5a89d639) Salvages the ISO C++20 9-flow comparator (r30: 9/9 vs 5/9, r33: 9/9) and -DNDEBUG-safe rung verifier with original commit authorship preserved (18/18 -O -B tests).
    A3, A4, A6, A7 PR 60 (34e14b85) Replaces wall-clock test caps with deterministic max_states (budget_sec=0), unifies fatal Goblin and Dragon hero kills as 'X' (OBJ_CORPSE = 21) across all three engines (594/594 catalog routes agree), replaces tautological must_fail predicates with live corruption probes, and relabels static lint passes from VERIFIED to LINT_PASS.
    C1, C2, C3, E3 (v1) PR 61 (c62b8798) Repairs the 12 -> 10 border-harvest drop (2119 = 2119 LP/Farkas), raises the certified 15x7 III-14 floor from 38 to 40 (4.70B quotient edges, 0 violations), adds the 720-bijection III-21 assignment bound (21 root) and retrograde tablebase (3.28x A* reduction), and adds a 383,328-rollout 2-arm NRPA harness (70-key unseeded III-14 win).
    mde_soko PR 62 (3ad86868) Adds the mde_soko benchmark (32/16/18 disjoint room splits, fail-closed stdlib allowlist sandbox, 9/9 0-byte CPU float64 BetaEdit re-derivation, and live Qwen3.5-4B S0..S3 evaluation).
    C3, C7, E3 (v2) PR 63 (4eba0542) Raises the collision-free 15x7 III-14 floor to >= 42 (LOWER_BOUND_UNWITNESSED, 26.42B quotient edges + 741.24M 24-byte Packed24 canonical states, 17.40x fewer states at f = 37 than main) and adds a 147,852-state vault-endgame tablebase (845,232 quotient edges, 0 violations, 47.56x A* reduction from t = 36).

    Cross-domain exact rational 1-Lipschitz Quotient-LP and zero-self-loop deficit certificates (soko, Hardin strip A268991, and cyclic switch routing) live at Foundation-0/quotient-lp-bounds.

    Open PR triage notes are posted on PR 12, PR 18, and PR 20.

    What remains open

    • III-14 ([42 .. 48]), III-20 ([77 .. 84]), and III-21 ([270 .. 316]) remain open between their certified floors and best witnessed routes. Single-host 64 GiB RAM hits the 24-byte state cap during layer f = 42 on III-14 without external-memory buckets.
    • A5 (SPRT harness for stochastic optimizer changes), C6 (incremental Zobrist state hashing), E1/E2 (FESS feature-space bias and Rolling Stone online pattern search), E4 (hero-subset LNS), and E5 (learned beam ranking) remain open.

    Automated posting by agentic team with human oversight.

  5. added a commit that references this issue on Nov 19, 2026
  6. added a commit that references this issue on Nov 19, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions