Shogi4 is a public-domain 4×4 drop-shogi by Oca Studios. This repo is a complete, oracle-validated strong-solution engine for it. Its rules, lost from the public web, were recovered from the official Android package; the solver was built from scratch, cross-checked three ways against an independent implementation, and run at 2.1 billion positions on rented hardware. The full solve is designed, tested on closed games, and calibrated, but not run at full scale: it would take roughly 50 to 100 TB and 130 to 190 core-years, which the result does not justify.

A narrative writeup (Partially Solving Shogi4) is on brianhliou.com, and the recovered rules are at mistboard.com/rules/shogi4.

The third entry in a small-shogi solving trilogy:

• A from-scratch rules engine (Rust in solver/, Python reference oracle in engine/), recovered from the decompiled app and cross-validated: perft matches to the digit, a 4,000-position differential test passes with zero mismatches, and three independent solvers agree to the unit.
• A dense-rank index (position ↔ integer bijection), the flat-array replacement for a hash map that lets the value table scale past memory. Its full-game domain is N = 410,297,064,507,360, exactly twice the independent arrangement count.
• A push-based retrograde solver over the rank index using un-move generation, plus a sharded BSP distributed design tested on closed games: confluent across shard counts, with a verification audit at ~55% of solve cost and deterministic crash recovery.
• A sourced research ledger in research/findings.md: every number with its provenance.

The largest solve is a reduced game, the two kings plus one of each piece type (2,100,849,024 positions), on a 16-core / 64 GB box in 5.3 hours:

It also calibrates cost per edge at scale (~697 ns/edge out of cache), which anchors the full-solve projection. This is a reduced game used to push the engine far past the small validation subgames; drops conserve material, so the real game never reaches it.

cd solver
cargo test --release

Ten tests reproduce every correctness claim: perft, the cross-language oracle diff, all three solvers agreeing, the rank bijection, un-move generation, the left-right symmetry fold, and the verification audit.

solver/      Rust engine, solver, and the validation suite (the production artifact)
engine/      Python reference oracle (a port of the decompiled app) + golden fixtures
research/    findings.md (sourced ledger), open questions, prior art, run logs
docs/        the research brief and the partial-run runbook
explorer/    interactive board / rules viewer

Shogi4 by Oca Studios, "Four" series, released public domain. Rules recovered from the official Android package com.ocastudios.shogi4 and documented at mistboard.com/rules/shogi4.

Built by Brian Liou, sibling to dobutsu-shogi. See LICENSE.