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)!
It's difficult to give any strong answers. Since there's no proof that NP != PSPACE, we don't actually concretely know what the difference between the classes is, and the plain assumption that NP != PSPACE doesn't tell you where to look.
I am also not an expert on complexity theory.
But intuitively: if you try to work with these two types of problems, you find that NP-complete problems are way more amenable to _pretty good_ solutions. There are very effective SAT solvers out there, and ILP solvers. Finding a TSP solution on almost any graph on tens of thousands of nodes is quite easy, and making good adversarial instances is hard. There are many programming challenges around NP-complete problems online that attract effective solvers, e.g. PACE, and previously [:(] Google Hashcode. PSPACE-complete problems on the other hand feel really, really intractable, where even solving small instances is very difficult, and I think the article we're commenting on gives a good feeling for that.
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.
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.
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
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.
So, quite a lot more complex than one might think.
[0] https://archim.org.uk/publications/
I'm assuming P != NP (and NP != PSPACE).
I am also not an expert on complexity theory.
But intuitively: if you try to work with these two types of problems, you find that NP-complete problems are way more amenable to _pretty good_ solutions. There are very effective SAT solvers out there, and ILP solvers. Finding a TSP solution on almost any graph on tens of thousands of nodes is quite easy, and making good adversarial instances is hard. There are many programming challenges around NP-complete problems online that attract effective solvers, e.g. PACE, and previously [:(] Google Hashcode. PSPACE-complete problems on the other hand feel really, really intractable, where even solving small instances is very difficult, and I think the article we're commenting on gives a good feeling for that.
https://victorqribeiro.itch.io/qubes
I did released it for Android also, but it needs updating.
This caught me completely off-guard, and I was indeed skim reading. Nonetheless, very well written article!
Maybe i will apply some of these heuristics myself when solving puzzles.
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.