Code, examples and computational materials for How to Solve a Game: Exact Search, Tablebases, Oracles and Computational Proof.
The book concentrates on the architecture of exact game solving: defining the state correctly, proving the rules engine, searching only where necessary, turning solved regions into reusable knowledge, and producing results that can be checked independently.
This companion provides the runnable side of the project: short teaching programs, reproducible experiments, verification tools, downloadable code and material from the Fanorona solver.
If you have a finite game of your own that you want to solve, the teaching packages below provide working Python examples corresponding to Chapters 1–14.
Work through the solver in stages
The teaching code follows the same progression used throughout the book:
rules → state → move generation → exhaustive search → memoisation → retrograde analysis → dense ranking → tablebase → oracle → proof search → certificate → verification
The programs are deliberately small. They are intended to be read, altered and copied when building a solver for another game.
Code downloads
The current teaching material is divided into three downloadable packages. Each package contains source code, README files and runnable verification examples.
Chapters 1–2
What it means to solve a game; exact state values; winning moves; strong solving of a finite region; independent verification; canonical state representation; persistent and transient state; and an example of history-dependent state.
v0.1
SHA-256:
8fe8f7dee99d19d08db5b394eacf1acbf6af4a9883c63d2d5bf26744d37d71b0
Chapters 3–8
Trusted rules engines and differential testing; exact forward search; memoisation; retrograde analysis; cycles and draws; dense ranking; and construction and verification of a persistent tablebase.
v0.1
SHA-256:
f0bb6491d0009939413284c2cdf390f086ebd5752dd012bbe082ba0217755b53
Chapters 9–14
Exact oracles and explicit coverage; proof-number search; predecessor engineering; hybrid exact solving; diagnostic experiments; and strategy certificates with an independent checker.
v0.1
SHA-256:
f4a64614d1ab6a0b303a6068567d2375475c41ba684992061e529410b81e80cd
I have a game I want to solve
Do not begin with the largest board, the fastest language or the most sophisticated search algorithm. Begin by making a small version of the game exact.
-
Write the rules as executable transitions.
Decide exactly what constitutes one persistent state and one complete legal move. -
Build a slow reference move generator.
Make correctness easy to inspect before introducing clever optimisations. -
Choose a tiny version of the game.
Reduce board size, material or another natural dimension until exhaustive search is practical. -
Solve that version by brute force.
Establish an exact baseline against which later algorithms can be tested. -
Measure the graph.
Count states, transpositions, cycles, branching and repeated subproblems. -
Decide where exact storage helps.
A solved region may become a tablebase, specialised solver or oracle. -
Search only above the exact boundary.
Do not repeatedly rediscover results that can be persisted and reused. -
Preserve evidence.
Try to make the final claim independently checkable rather than dependent on trusting one large discovery program.
Code by chapter
The table below shows which download contains the material corresponding to each chapter.
| Book chapter | Companion material | Package |
|---|---|---|
| 1. What Does It Mean to Solve a Game? | Exact state values, winning moves, strong solution of a finite region and independent checking. | Chapters 1–2 |
| 2. What Is a Game State? | Canonicalisation, persistent versus transient state and history-dependent state. | Chapters 1–2 |
| 3. Prove the Rules Engine Before You Solve the Game | Reference generator, faster generator and differential testing. | Chapters 3–8 |
| 4. Exact Forward Search | Naive recursive search compared with memoised exact search. | Chapters 3–8 |
| 5. Retrograde Analysis | Complete bottom-up solving of a finite state region. | Chapters 3–8 |
| 6. Cycles and Draws | Exact WIN / LOSS propagation followed by classification of unresolved cyclic regions. | Chapters 3–8 |
| 7. Dense State Ranking | Dense rank/unrank mapping and exhaustive round-trip tests. | Chapters 3–8 |
| 8. Building a Tablebase | Persistent binary tablebase, reload and complete verification. | Chapters 3–8 |
| 9. Oracles |
Exact answers within a proved domain and explicit
NOT_COVERED outside it.
|
Chapters 9–14 |
| 10. Proof-Number Search | Compact pedagogical implementation of proof-number search. | Chapters 9–14 |
| 11. Predecessor Engineering | Reverse generation proposes; forward generation confirms. | Chapters 9–14 |
| 12. Hybrid Exact Solving | Exact composition of search with a solved oracle region. | Chapters 9–14 |
| 13. How Not to Solve a Game | Measured examples of avoidable repeated work and poor solver architecture. | Chapters 9–14 |
| 14. Computational Proofs and Certificates | Strategy certificate generation and checking by a separate verifier. | Chapters 9–14 |
| 15. Fanorona | Production solver material, exact subgames, tablebases, repetition-aware proof search and checked certificates. | Fanorona Laboratory v0.1 |
Reference code and production code
Reference code
Short, readable and intended to expose the algorithm. This is the code to study or copy first when adapting the techniques to another game.
Production code
Designed to make the real computation practical. Production code may use dense storage, specialised representations, checkpointing, caches and other engineering that would obscure a teaching example.
A result does not become more exact because the implementation is faster. The production implementation makes the computation affordable; validation makes the result trustworthy.
Fanorona Laboratory
Fanorona is the principal real-world case study in the book. The material here comes from the actual solver project rather than the simplified teaching examples above.
Fanorona Laboratory v0.1 is a curated release of the real project archive. It contains selected production code, strong-solve and tablebase material, repetition-aware proof-search implementations, certificate builders and independent checkers, audit scripts, technical notes and selected result records.
SHA-256:
855a8918cd04c8bd084d04eeba111a5eee39aa0048c4f5cea2b88b987e7736ce
The project has not independently solved the standard 5×9 initial position. Results are classified below according to what has actually been established.
Strongly solved
- 3×7 Fanorona
- 5×5 Fanorona
- Every history-free standard 5×9 position with seven or fewer pieces
Independently validated
- Move generation
- Complete capture sequences
- Terminal rules
- Automatic third repetition
- Certificate checking
Independently certified
- 567-history duplicate class
- 546 directly supported parent obligations
- 12 additional loss-position classes
- Residual 1W5B layer
- First terminal-only seven-piece exact-history certificate
Prepared or experimental
- Further prepared seven-piece cases
- Learned move prior
- Guided DFPN experiments
- Frontier and scheduling experiments
Open
- Node65
- Complete root certificate
- Independent project result for the standard 5×9 initial position
The laboratory package is intentionally curated rather than a raw dump of the complete research working directory. Large generated tablebases, checkpoints, caches and build artefacts are excluded.
Reproducing the results
Material intended to reproduce a result from the book should identify:
- the program and release version;
- the command used;
- the expected output;
- required input or data files;
- the checksum where appropriate;
- the precise rule set and state representation to which the result applies.
Discovery machinery may be complicated; verification should be as small and explicit as practical.
Version information
Book:
How to Solve a Game: Exact Search, Tablebases, Oracles and
Computational Proof
Edition: First edition, 2026
Teaching-code release: v0.1
Fanorona Laboratory release: v0.1
Errata and updates
The printed book is a fixed edition. This page is the living record for corrections, revised references, updated code and changes in the status of the Fanorona project.
| Date | Location | Correction or update |
|---|---|---|
| 2026 | Historical prologue — references | Kawano corrected to Using Similar Positions to Search Game Trees; the full Allis Connect-Four report title corrected to A Knowledge-Based Approach of Connect-Four: The Game is Over, White to Move Wins ; Haworth’s Ströhlein paper corrected to ICGA Journal 42(2–3), 2020, pp. 165–170. |
Source and licence
The downloadable examples are intended to accompany the book and make the algorithms easy to inspect, reproduce and adapt.
The teaching packages contain simplified reference implementations. Fanorona Laboratory v0.1 contains selected source and evidence from the actual production/research project used for the book’s Fanorona case study.
Code and data licences are described within the distributed material. Third-party material retains its original licence and attribution.
Leave a Reply