FWIW there's a proof of Sokoban being NP-complete in a Cambridge University student publication called Eureka [0], edition 54.
So, quite a lot more complex than one might think.
My first ever published game was a sokoban clone. I wrote a solver, then I used it to create levels. Since I know the best possible solution, I rate the players moves count with 1, 2 or 3 stars.
https://victorqribeiro.itch.io/qubes
I did released it for Android also, but it needs updating.
Decades ago I built a Sokoban solver, then a more generic puzzle solver which could handle a wide range of similar games (such as Atomix). It's fun to see someone else finding all of these heuristics. Excluding dead squares and searching backwards to meet in the middle I definitively implemented, and I thought of many of these others too (though whether I got around to implementing them is another question!). This post is praiseworthy for showing how intuitive these tricks are once you know them.
One of the clearest write-ups showing how coding agents can be applied to good engineering and help with comprehension.
I was thinking about Order of the Sinking Star's state in terms of a graph. Mapping structs to vertices and edges, each vertex an instance. This is a recently released game inspired by Sokoban. Is kind of cool how you can break the whole system into a fine-grained graph encompassing all state, or extract the key state from each puzzle. Some are more conducive to this than others! I think this naturally also brings in the concept of compression, with the raw state of every item on the board being the full uncompressed version.
> Just to be ultra clear here, as you may be skim reading...
This caught me completely off-guard, and I was indeed skim reading. Nonetheless, very well written article!
I did not know about Sokoban, but sounds like the rock pushing puzzle in Pokemon red/blue/yellow was inspired by it. There was this "Jev plays pokémon" livestream at some point and the model was stuck on this puzzle for hours
"As is common for this era, I did not handwrite a single line of code..."
That's the spirit... :-D
This is an interesting read ive been playing Jon Blow's latest game.
Maybe i will apply some of these heuristics myself when solving puzzles.
Wow this is an excellent writeup! Hats off.
I played this game about 35 years, it's fun to me, and I spend a lot time to play it, but I did not plan to develop a solver.
We probably have to create a separate track for human only solvers and machine solvers soon.
And we will need strict rules on the human only solvers. The fun is lost when you lose to a solver written by a frontier agent swarm, while if a new solver written by a human outcompetes you, it feels all fair and square and you can go back to the drawing board.
Yes a human steered this solver, but it doesn’t feel the same competitively, like doped vs non doping athlete. Till 2026 we never had to think of this for cognitive tasks but the age to do so is coming now.
Very cool. Thanks for sharing.
[flagged]
Sokoban is cool, but far from the most interesting thing here, which is the design of experiment factories for verifiable domains.
The base building blocks you need to make this work:
- dataset
- unhackable success metric
- hardened, isolated f(dataset, solver) -> metric
- helps a ton but not required: human with strong intuitive domain understanding
This is exactly the kind of RL environment in which the models are forged, so they're truly excellent at basically all stages of this process.
I'm working on something similar for image and video compression. The SOTA approach for these things currently is mostly deep neural networks. But agent powered experiment factories let you cover FAR more ground in algorithm-space than before, which makes deterministic and explicit algorithms, with little or no heuristics (aka floating point weights) feasible once again.
Explicit algorithms (SGD) grew implicit ones (neural nets) that are more powerful and general, but also more opaque and less efficient. Now those implicit ones have made search over explicit algorithms vastly faster, which is making them increasingly competitive with neural methods.
Author here. The owner of sokobano.de/wiki/index.php?title=Solver_Statistics is currently independently verifying the performance of my solver (and the early signs look good)!