Skip to content
ahrazzlePublic

About

sokoban eval by baneg

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

soko (soko-verified-mcp v0.4.0 — Domain-General Formal-Systems & Verified-Bar MCP Server)

Model Context Protocol (MCP) server and C++20 verification/search/prover toolkit implementing the Foundation-0 Repository Standard and Proven-Commons Verified Bar across arbitrary discrete state systems (formal_* suite) as well as Jonah Ostroff's PuzzleScript trilogy. The canonical catalog contains all 66 original rooms (I-1 through III-22), with dated source, tutorial and baseline provenance. See Agent quickstart and trilogy corpus parity evidence. (Part I, Part II: Monsters, Part III: The Bard and The Druid) on the Sokoban Eval Frontier benchmark (write-up).

Zero third-party Python packages are required (python >= 3.10 standard library only). On first Sokoban tool call, soko_mcp automatically compiles the C++20 engine (cpp/soko_engine.cpp) via g++ or clang++ (-O3 -pthread -std=c++20), while maintaining fail-closed dual-Python verification (PuzzleScriptOracle + zero-shared-code FlatBitmaskOracle) and honest capability reporting (soko_capabilities) even when no C++20 compiler is present.

Verification status (2026-11-14)

  • The test suite runs in CI on every push and pull request (.github/workflows/tests.yml). Before this date the repository had no CI, and the suite had failed on main since PR #9 without anyone noticing.
  • The vault-lineage imports had overwritten two hardened layers: the native engine's original-rule mechanics, and the repository's evidence-boundary contract. Between PR #9 and this date the C++ engine disagreed with both Python oracles on rooms with more than one active hero (I-22, II-12), and native prove_lb labelled zero-search and unsolvable results VERIFIED. Both are fixed. A seeded catalog-wide differential test (tests/test_engine_differential.py) guards native parity. The old engine agreed with the oracles on every sampled III-14, III-20 and II-22 route, so the bounds published for those boards are not affected.
  • SHA256SUMS locks checker and prover sources only (python3 -m soko_mcp.integrity). A matching lock shows the files are unchanged. It does not show that they are correct, which is why CI runs the tests. Compiled binaries are built from source and are not committed.
  • Experiments in experiments/causal_solver and experiments/exact_frontier need the optional extras: pip install ".[research]".

What's New in v0.4.0 (Two-Way Foundation-0 Synthesis)

  1. Foundation-0/gfq-codes Exact Rational LP Dual & Cost-Partitioned Quotient Certificates (formal_certify_lower_bound):
    • Adds proof_mode='cost_partitioned_quotients' (exact fractions.Fraction additive action-cost partitioning $\sum_m w_m(s,a,s') \le \text{cost}(s,a,s')$ across $M \ge 2$ Quotient Graph Homomorphisms, strictly dominating pointwise $\max_m h_m$) and proof_mode='rational_lp_dual' (exact fractions.Fraction state-equation / operator-counting Farkas dual multiplier verification $y \ge 0$, $y^\top(F(s')-F(s)) \le \text{cost}(s,a,s')$ with zero floating-point LP solver in the TCB).
  2. Foundation-0/finite-state-proofs Exact 4-Cell Row Strip Automaton (FastRowStripPDB) & F-11/F-12 Soundness Audit (cpp/frontier_iii14_iii20_prover.cpp):
    • Stress-testing v0.3.0's hand-written analytical h_iii14_fast across 15.5M concrete transitions uncovered two subtle inadmissibility hazards: F-11 (assuming 9 switch-weighing atoms instead of 7/8-atom hero tandem entry when open_pdoors != 0) and F-12 (independent xs/ys order-statistic window slicing dropping 10 -> 8 on a single Druid transmutation).
    • Replaces hand-written analytical formulas completely with a 100% pure 5-Quotient-PDB Homomorphism Suite (FastRowStripPDB tracking {empty, crate, wall}^4 on (4..7, y) across y = 2, 3, 4 via y <-> 6 - y vertical symmetry + PairAtomHomPDB + HarvestColPDB + BardDruidQuotientPDB), giving a sound lower bound >= 34 on the 14x7 III-14 fixture. The completed f-layer covers 79,587,434 exact Packed14 states, catches 22,551 live 64-bit hash collisions, and passes 123,784,748 runtime h(s) <= 1 + h(s') edge checks with 0 violations. The trailing FINAL_CERT counters run into the next layer until the 82 s cutoff and change with the machine.
    • Unlocks M.n <= 256 Multi-Core Exact-State Bucketed A* in cpp/soko_engine.cpp (covering III-20 15x9=135 and II-22 13x13=169), raising the generic MCP lower bound on III-20 from 25 (v0.3.0) to >= 48 at a 30 s budget (8,475,805 nodes expanded, 77,437 live 64-bit hash collisions caught, 25,096,136 runtime edge checks with 0 violations; wall time 10.8 to 14.5 s across three runs on the porting box and 19.2 s on the reviewer box). The search does not reach an exact optimum and returns no witness, so soko_prove_floor reports it as LOWER_BOUND_UNWITNESSED, not VERIFIED.
  3. Foundation-0/formal-claims-audit Static AST Soundness & Anti-Tautology Tool (formal_audit_checkers, the 20th MCP tool on this branch):
  4. Foundation-0/incentre-lattices Locked-Checker tracks/ Harness (tracks/iii-14/, tracks/iii-20/):
    • Adds standalone dual-oracle verify.py scripts and append-only results.tsv ledgers logging both breakthroughs and negative high-width LNS runs.
  5. 15x7 catalog board III-14, floor of 38 or more:

Earlier: v0.3.0

An optional global record-query system now builds unrestricted bounded SAT problems for III-14 and III-20, verifies complete SAT assignments, checks optional UNSAT certificates, and replays candidates in the pinned original game. It requires separate research dependencies and has not yet demonstrated a new record or end-to-end formal equivalence.

  1. PairAtomQuotientPDB + Multi-Core Exact-State Bucketed A (soko_prove_floor):*
    • Adds a 39.7M-state 2-Atom Quotient Homomorphism Pattern Database (PairAtomQuotientPDB) modeling unordered pairs of created weighing atoms ({crate@cell, interior_wall@cell, UNBORN, SPARE}), explicitly accounting for both rigid Bard 5x5 aura co-translation and wall-blocked/moving charmed crate pairs (including step 25 of III-14's 48-key route), Druid # <-> * transmutations, border re-petrification, and 10th-crate SPARE creation.
    • Replaces per-iteration IDA* re-expansion on grids <= 128 cells with Multi-Core Exact-State Bucketed A* (CompactNode full-state equality, zero hash-collision pruning, live collision counter, and runtime h(s) <= 1 + h(s') edge checks), raising the built-in MCP certified floor on III-14 from 29 (in v0.2.0) to >= 33 in ~6.6s with 100% exact-state deduplication. The larger v0.3.0 figure for III-14 is withdrawn because of F-11/F-12.
    • Adds WizardRayGoalBound for rooms with Wizard warpballs (III-15, III-20, II-22), eliminating the prior floor = 1 fallback on Wizard rooms.
  2. Automatic Inductive Invariant & Deadlock-Trap Synthesis (formal_synthesize_invariant):
    • Adds a 7th universal formal_* primitive supporting both Houdini greatest-fixpoint inductive safety invariant synthesis (synthesis_mode='houdini_safety') and irreversible forward-closed deadlock-trap synthesis (synthesis_mode='deadlock_trap') over reachable concrete subgraphs or explicit universal state domains (universe_code).
    • Certificates report proof_scope: complete_reachable_states only applies to states reachable from the initial state, while enumerated_closed_domain applies to the supplied, checked closed domain. Neither covers states outside its domain. explored_reachable_subgraph is incomplete; open_transitions counts outgoing transitions to states omitted by the limit, and no global induction or trap is established.
  3. Executable Capability Contract & Review Hardening (soko_capabilities + Blocking Fixes):
    • Adds soko_capabilities to report compiler/backend readiness and distinguish BACKEND_UNAVAILABLE from UNSOLVED_WITHIN_BUDGET.
    • Enforces strict REPO_ROOT path confinement (unconfined_paths) and mandatory checker_pins checks in soko_verify_tcb_lock, fail-closed C++ epistemic/witness validation in soko_prove_floor, and exact 9-step (RRRRRRRRR) I-1 benchmark metadata.

Connect as an MCP Server

Claude Code

claude mcp add soko-verified -- python3 -m soko_mcp

Gemini CLI / Cursor / Claude Desktop (mcpServers JSON)

{
  "mcpServers": {
    "soko-verified": {
      "command": "python3",
      "args": ["-m", "soko_mcp"],
      "cwd": "/path/to/soko"
    }
  }
}

Exposed MCP Primitives (20 Tools, 6 Resources, 4 Prompts)

Suite Primitive Name Purpose
Formal Tool formal_define_system AST-sandboxed dual-checker registration (spec_code != impl_code skeleton), negative controls, mutation kills & BFS fuzzing
Formal Tool formal_verify_trace Dual-checker step-by-step trace replay with rolling SHA-256 transcript digest and premise assertions
Formal Tool formal_solve_system Exact Dijkstra/BFS (goal synthesis or find_invariant_violation bug hunting), Diversified Beam, & Sliding-Window LNS
Formal Tool formal_certify_lower_bound Zero-trust PROVEN lower bounds via Quotient Homomorphisms, Inductive Potentials, Rational Cost-Partitioned Quotients, or Rational LP Duals
Formal Tool formal_synthesize_invariant Automatic Houdini inductive safety invariant synthesis (houdini_safety) & irreversible deadlock-trap synthesis (deadlock_trap)
Formal Tool formal_triage_portfolio Expected-verified-gain priority ranking across open instances
Formal Tool formal_export_ledger Export SHA-256-pinned PROVEN / VERIFIED / KNOWN / CONJECTURE claim ledger
Formal Tool formal_audit_checkers Static AST soundness & alpha-normalized anti-tautology auditor for single or dual Python checkers
Sokoban Tool soko_capabilities Inspect executable backend readiness, oracle count, lower-bound abstractions, and TCB manifest status
Sokoban Tool soko_list_rooms List built-in Frontier rooms (I-1, II-22, III-14, III-14-15x7, III-15, III-20, III-22)
Sokoban Tool soko_get_room Full source-pinned original room metadata, grid, tutorials and reference baseline provenance
Sokoban Tool soko_replay_original Replay UDLRA keys in the pinned original PuzzleScript browser engine
Sokoban Tool soko_play Stateless original-engine play with portable JSON checkpoints, undo and reset
Sokoban Tool soko_inspect_room Detect X/Y/180-degree symmetries, hero-switch chirality, switch deficits, and Bard constraints
Sokoban Tool soko_verify_route Per-frame trajectory digest verifier: always the two Python oracles (PuzzleScriptOracle + FlatBitmaskOracle), plus the C++20 engine when it compiles. Returns a certificate_sha256 bound to the instance, route and checker pins
Sokoban Tool soko_optimize_route Shorten seed routes via Sliding-Window Exact BFS + Chiral-Mirror Tube Beam + Iterative Refinement
Sokoban Tool soko_solve_room Solve (part, grid) rooms from scratch via bucket-diversified C++20 beam search
Sokoban Tool soko_prove_floor Multi-Core Exact-State Bucketed A* (<= 256 cells) + PairAtomQuotientPDB + BardDruidQuotientPDB + WizardRayGoalBound. Returns VERIFIED only for an exact optimum with a dual-oracle-checked witness on a board with a reference route; otherwise WITNESS_MATCHES_CLAIM_UNREFERENCED (no reference route) or LOWER_BOUND_UNWITNESSED (inexact search)
Sokoban Tool soko_run_planted_bug_audit Cross-oracle baseline parity + 10-mutation Proven-Commons Planted-Bug Suite (10/10 caught)
Sokoban Tool soko_verify_tcb_lock Path-confined source-manifest check (complete coverage of checker and prover sources, no compilation) and SHA-256 checker pin inspection; the local binary is hashed separately

Verified Frontier Route Ledger (a1kindus)

Room Keys Status SHA-256 (12) Notes & Submission String
III-20 (Primary) 84 VERIFIED eecbea96b091 Live Frontier record: ADDDRRADAAADRULARADAAADDLLALAAAARRRRUULAAUALLRADRRRRADRULRURRRRRARRUURURAURRRDDRAUUR
III-20 (Alt) 84 VERIFIED 4edff1ad8c90 Alternate 84-key ending (URU): ADDDRRADAAADRULARADAAADDLLALAAAARRRRUULAAUALLRADRRRRADRULRURRRRRARRUURURAURRRDDRAURU
III-14 (14x7 & 15x7) 48 VERIFIED cd934d25a629 Matches 48 shortest known. On the 15x7 catalog board, a floor of 38 or more was reproduced by grk-proof (review 5886834600) from the finished f=37 layer; see the merged ledger. 34 is an upper bound under sticky doors only. The 14x7 fixture still has the standalone-prover lower bound >= 34 (completed layer of 79,587,434 exact states): LLULULULRURURURURUAUDRRDDAUARRDLRAULDLDRARURDUUR
II-22 94 VERIFIED d5e82e8e3c65 Verified baseline (Frontier record 92): ADDUUULDDRDDLDULDDRLLLLULURDLDRURUAAUUULLLLLLLAAAULURUARRRARRRDRUUDRRRDLLLDDDLDRLALUADDDRDRRUR
III-15 69 VERIFIED 76e195c497c1 Equals the Frontier record: AULADDALAULDRALAULDALALURALADLUALALDRALAULDALALURALADLUALALDLRAUAULLU
I-1 fixture / III-22 9 VERIFIED 179f01ec4093 Proven optimal on the legacy fixture:I-1 board and on III-22: RRRRRRRRR. The original I-1 room in the catalog (13x5) is a different board, with record and floor 8

CLI & Test Quickstart

# Verify the source lock (complete coverage, no compilation) and run every test suite
python3 -m soko_mcp.integrity
pip install ".[research]"   # optional: z3 / python-sat for the research experiments' tests
python3 -m unittest discover -s tests -v

# Run CLI commands directly
python3 -m soko_mcp capabilities
python3 -m soko_mcp tcb-lock
python3 -m soko_mcp audit
python3 -m soko_mcp prove-floor --room III-14 --max-bound 33 --budget-sec 10
python3 -m soko_mcp verify --room III-20 --route ADDDRRADAAADRULARADAAADDLLALAAAARRRRUULAAUALLRADRRRRADRULRURRRRRARRUURURAURRRDDRAUUR

# Run locked track verifiers (Foundation-0 / incentre-lattices pattern)
python3 tracks/iii-14/verify.py
python3 tracks/iii-20/verify.py

About

sokoban eval by baneg

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages