1. Choose the problem before the method
We wanted a complete, challenging Sokoban game before starting another training run. Our small starter rooms were too simple to justify a strong-player claim. We replaced them with the 137-puzzle LOMA community collection and retained local imports for other level files.
Then we asked a simpler question: can an ordinary search algorithm already solve the campaign? It could. We verified a legal complete route for every puzzle, without a neural network, training examples or reinforcement learning.
Play the LOMA campaign →. The player game has no hint or automatic-solution control; this solver is an offline verification tool.
2. A finite board does not mean a short game
The state records the player position and the three pot positions. Walls and flower beds are fixed for a puzzle. A move either walks onto empty floor or pushes one pot into the empty cell beyond it. Repeating a walk can continue indefinitely, even though the number of distinct board states is finite.
Known rules make exact simulation possible. They do not make every Sokoban puzzle easy: the general decision problem is PSPACE-complete, a formal result about how difficult larger instances can become. Our small three-pot collection is a much more limited case. See the University of Alberta research bibliography.
For a useful simplification, hold the pots fixed and find every square the player can reach by walking. Two player positions in the same reachable region allow the same next pushes. The search can treat those positions as one planning state instead of exploring every redundant walk.
3. Search over pushes, then reconstruct the walking
- Find reachable floorWalk without moving any pots
- Try legal pushesCheck both the standing cell and destination
- Keep new statesMerge equivalent regions and reject wall corners
- Replay the routeValidate every step in the game engine
A queue explores plans with one push, then two pushes, then three. To push right, the player must be able to stand immediately left of a pot, and the destination immediately right must be free. A pot moved into a non-target corner bounded by walls is permanently trapped, so that branch can be discarded.
We identify a state using sorted pot positions and a representative of the reachable walking region. Previously explored states are skipped. Each retained push stores its shortest walking segment and its parent state; reaching all targets lets us reconstruct a complete route.
4. What we verified, and what we did not
| Measurement | Result |
|---|---|
| Legally completed puzzles | 137 / 137 |
| Pots per puzzle | 3 |
| Minimum pushes across the collection | 7–69 |
| First puzzle | 23 pushes; verified route: 127 movements |
| Final puzzle | 42 pushes; verified route: 88 movements |
| Bound used for every initial-board verification | 10,000 queued search nodes |
| Training runs | 0 |
Every action was replayed through the actual pure game engine. Tests check that actions change the state legally, saved states remain valid, all targets are filled and Restart returns the exact starting layout. Browser tests also play complete puzzles through keyboard and touch controls.
This is complete coverage of one finite collection, not generalization to unseen caves or evidence of a learned skill. Search-budget exhaustion on a larger imported puzzle would not establish that it is impossible. Our pruning handles simple wall corners; it is not comprehensive deadlock detection.
5. Sokoban can still be a machine-learning problem
Finite actions and deterministic rules do not disqualify a task from machine learning. The useful research question is whether a model learns something that transfers beyond the examples it saw.
A future model could predict promising pushes, estimate distance to a solution or recognize more deadlocks, helping a search solve larger puzzles under a smaller computation budget. Another study could learn a policy from pixels or demonstrations. Training on these same 137 layouts and replaying memorized routes would be a weak test.
We would need disjoint training and unseen evaluation layouts, a fixed thinking budget and a comparison against this classical solver. Measure solved puzzles, pushes, total movements and computation separately. A lower training loss alone would not establish a better player.
Imagination-Augmented Agents combines learned environment predictions with a neural policy and studies planning tasks including Sokoban. It is a useful research direction, not an architecture we implemented or a result we can claim.
6. Stop when the current job is already solved
For shipping this campaign, all puzzles are playable and verified. A trained model is unnecessary for that job. The player game stays focused on the puzzle: no automatic hints, no hosted inference and no account requirement.
We stop here rather than start an open-ended training run. Revisit ML only with a concrete hypothesis, unseen-puzzle evaluation and a bounded experiment budget. Choosing search is a useful engineering outcome, not a failed ML experiment.
7. Keep the evidence and credit the levels
- Download the verification summary: algorithm, scope, counts and limitations.
- LOMA collection and publication permission, organized by Aymeric du Peloux with twelve contributing authors.
- Original LOMA level text and per-puzzle authors and publication notice.
- Sokoban search research, including work on deadlocks, domain knowledge and complexity.
- Weber et al.: Imagination-Augmented Agents for Deep Reinforcement Learning.