The Strongest Sokoban Solver

(healeycodes.com)

61 points | by ibobev 3 days ago

11 comments

  • healeycodes 28 minutes ago
    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)!
  • synapsomorphy 14 minutes ago
    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.

  • vintermann 2 hours ago
    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.
  • quibono 1 hour ago
    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.

    [0] https://archim.org.uk/publications/

    • mjdv 1 hour ago
      In fact it's even PSPACE-complete, which is (probably) much, much harder!
      • quibono 1 hour ago
        I've always struggled to understand what the difference is. Is PSPACE-completeness "worse" in a practical sense?

        I'm assuming P != NP (and NP != PSPACE).

        • mjdv 49 minutes ago
          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.

  • asibahi 3 hours ago
    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.

  • ngruhn 1 hour ago
    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
    • quibono 1 hour ago
      There are a few games with similar mechanics, "Baba is you" comes to mind as a very popular one. These can get very complicated very quickly.
  • ZiiS 1 hour ago
    One of the clearest write-ups showing how coding agents can be applied to good engineering and help with comprehension.
  • xpct 2 hours ago
    > 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!

  • skrebbel 2 hours ago
    Wow this is an excellent writeup! Hats off.
  • forrestthewoods 1 hour ago
    Very cool. Thanks for sharing.
  • alphayc 1 hour ago
    [flagged]