| ▲ | The Strongest Sokoban Solver(healeycodes.com) | |||||||||||||||||||||||||
| 97 points by ibobev 4 days ago | 18 comments | ||||||||||||||||||||||||||
| ▲ | xuesj 8 minutes ago | parent | next [-] | |||||||||||||||||||||||||
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. | ||||||||||||||||||||||||||
| ▲ | healeycodes 3 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
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)! | ||||||||||||||||||||||||||
| ▲ | quibono 5 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
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. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ▲ | atum47 2 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
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. | ||||||||||||||||||||||||||
| ▲ | vintermann 5 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
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. | ||||||||||||||||||||||||||
| ▲ | xpct 5 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
> 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! | ||||||||||||||||||||||||||
| ▲ | ZiiS 4 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
One of the clearest write-ups showing how coding agents can be applied to good engineering and help with comprehension. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ▲ | ngruhn 4 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
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 | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ▲ | asibahi 6 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
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. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ▲ | skrebbel 5 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
Wow this is an excellent writeup! Hats off. | ||||||||||||||||||||||||||
| ▲ | forrestthewoods 4 hours ago | parent | prev | next [-] | |||||||||||||||||||||||||
Very cool. Thanks for sharing. | ||||||||||||||||||||||||||
| ▲ | synapsomorphy 3 hours ago | parent | prev [-] | |||||||||||||||||||||||||
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. | ||||||||||||||||||||||||||