The Strongest Sokoban Solver

(healeycodes.com)

134 points | by ibobev 4 days ago

16 comments

  • healeycodes 10 hours 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)!
    • joe-esquibel 5 hours ago
      "I think in this agentic age of software, you have to want the goal as much as the agent. Yes, anyone can build software. But you need to care about it, you need to love it. The human focus and effort remains." Great quote
  • quibono 12 hours 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 12 hours ago
      In fact it's even PSPACE-complete, which is (probably) much, much harder!
      • quibono 11 hours 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 11 hours 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.

        • tetha 7 hours ago
          Complexity theory has a couple of interesting "sandwiches" as a prof called them.

          For example, we know that LOGTIME is a subset of PTIME, which is a subset of NPTIME and PSPACE, both of which are a subset of EXPTIME. We also know that EXPTIME is strictly bigger than LOGTIME and PTIME.

          So somewhere between PTIME, NP, PSPACE and EXPTIME, there must be a change in computational capability. We just don't know where.

          This also exists between constant-depth circuit networks and algorithms using LOGSPACE. A circuit network of depth of log^2(input_size) can compute more than any nondeterministic LOGSPACE algorithm, which can compute more than a circuit network of constant depth using threshold gates. We also know that a deeper circuit network has strictly more computational power than the constant depth one.

          But where is the specific jump in computational power? We don't know.

          That makes the "practical applications" very strange to consider.

          I keep jesting, the funniest resolution of P vs NP would be that P = NP, except it has a cost factor that stops any practical collapse, like a proven minimum of O(n^<number of atoms in the universe>). That'd be the most annoying resolution of them all.

        • emil-lp 7 hours ago
          If a problem is in NP, which all NP-complete problems are, then the yes-instances of the problem have "small" solutions that can be verified efficiently.

          Take sudoku. If I give you a difficult board, and also the solution, it is easy to verify that it is correct.

          Small efficient certificates do not exist for PSPACE-complete problems. Indeed for Sokoban, some instances require exponentially long sequences of pushes to solve.

  • atum47 9 hours ago
    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 12 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.
  • ZiiS 12 hours ago
    One of the clearest write-ups showing how coding agents can be applied to good engineering and help with comprehension.
    • SamBam 7 hours ago
      Agreed. If the author had used AI to write a math proof, they'd be one of those authors who could fully explain every line in the proof, and probably simplify it too. Kudos!
  • the__alchemist 7 hours ago
    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.
  • xpct 12 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!

  • ngruhn 11 hours 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 11 hours 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.
      • mjr00 5 hours ago
        Baba Is You is awesome. The latest Jonathan Blow game, Order of the Sinking Star, is also about 75% sokoban puzzles by volume, and is massive. I recommend both to any puzzle fans who somehow have not played them. (Both of these games get a lot more intricate than just straightforward sokoban, in case that wasn't obvious.)
      • tarsierscripter 7 hours ago
        NetHack has had a bunch of Sokoban levels for many years! They are complicated by the addition of enemies that spawn for you to fight (which can block boulders you’re trying to push) as well as items that may be resting in/on the pits you’d want to push the boulders into.
  • Kuyawa 3 hours ago
    "As is common for this era, I did not handwrite a single line of code..."

    That's the spirit... :-D

  • asibahi 13 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.

    • Etherlord87 9 hours ago
      This is the kind of thinking you will have to use, and then a lot more of it!
      • asibahi 5 hours ago
        I despise timing puzzles.
  • skrebbel 12 hours ago
    Wow this is an excellent writeup! Hats off.
  • xuesj 7 hours ago
    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.
  • sashank_1509 6 hours ago
    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.

  • forrestthewoods 11 hours ago
    Very cool. Thanks for sharing.
  • alphayc 11 hours ago
    [flagged]
  • synapsomorphy 10 hours 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.

    • joe-esquibel 5 hours ago
      Exactly, I think algorithm development is becoming more like scientific research with hypotheses and evidence. Experiment factories is new to me but I guess it's also what I've been unconsciously developing towards after I created functional code factory for my own project.