Show HN: Sokoban AI Solver

I love seeing the term "AI" used in the classic sense. Old AI is full of fascinating developments. Expert systems, A* search, genetic algorithms over S-expressions for creating arbitrary solutions, and SAT algorithms were once thought to be that which would eventually scale into AGI.

I suspect that the next big AI breakthrough will result at least in part from constraining LLM decisions with old AI approaches. Frank Coyle presented the idea of ontologies constraining LLM output about a month ago: https://www.youtube.com/watch?v=Sir59K8ZDPU

Going beyond that, I wonder if an agent could keep a running list of assumptions & known facts (with confidence levels/intervals), test them (actively & passively), update them when observations contradict them, and act based on them -- not merely as an emergent behavior, but as a provably correct (old AI based) algorithm embedded in the transformer architecture.

I'm kind of surprised to find myself enjoying this because I've had a certain hatred for box pushing games. (maybe it's trauma from the sliding blocks in Pokemon games, heh). I guess I'm getting over it (maybe it's happy memories from Baba Is You).

Anyway, one thing that's fun here is that you can trigger the AI solve from any board state. So in particular on puzzle 12 I was interested to see that an initial push (to escape from the 'box' where you start) I'd written off as untenable turns out to be the optimal solution. Then of course it's fun to watch the solver tackle the initial conditions I solved under (and still beat my number of moves).

Might be kind of fun to play with "pessimizing" the puzzle - like, how can you move blocks around to provide a maximally adversarial place to hit the "solve with AI" button? (obviously you don't get to count your initial moves around the board, or you could just move back and forth to get the most pessimum (thanks, Mel) solution.)

Edit: Puzzle 14 feels odd. Super easy, why is it at 14? Maybe something tricky about it that I'm not seeing, perhaps the shape of the arena makes A* harder or something?

Also, 15 is interesting and highlights a theme I'd noticed, which is that often the initial moves of a puzzle seem pretty locked in, and the place where the AI shaves moves off my solution in in some clever approach to the "stacking" of boxes onto the goals. I guess that seems kind of obvious when I write it out.

Anyway, thanks for something to noodle on this morning!

Got me curious: is there some way to approximate solvability of a puzzle in a certain time frame, or is that completely intractable?

Also, what counts as "complexity" in Sokoban puzzles. Does it plateau at a point, where board size/box count starts scaling the solving time more linearly?

Intuitively, I feel like the final board might also be able to be tackled in browser, if you use WASM and speed up the solver.

I wonder: maybe the state is overly compressed? Could it speed things up to store (boxes, [every position the keeper can reach without pushing]) rather than (boxes, representative keeper position), so we can reduce recomputation of the keeper walking around?

I wonder: maybe A* is counterproductive, as obvious heuristics have traps? Maybe BFS is better?

I wonder: the search doesn't actually "skip over" walking states, it just hides them in the processing of each element in the queue, so adding them to the queue might actually be faster?

I wonder: are there any other simple pruning techniques that you could incorporate? Any learnings from state-of-the-art Sokoban solvers, like this one? -- https://ieee-cog.org/2020/papers/paper_44.pdf

Many interesting questions... sadly, the webpage is written by AI, so there's zero discussion of these tradeoffs, future avenues, or rejected ideas, in favor of meaningless self-congratulatory copy about the "provable optimum" and silly claims like a bucket queue being allocation-free.

“What runs here is a plain-JavaScript port of a native C++ optimal solver I wrote.”

Seems to be AI in the older sense from 10 years ago?

Doesn't this break down quickly as the area increases? (Ironically, the complexity goes down as there are more squares to use).

While impressive that the optimal can be proven, I feel like the example puzzles here aren't ones that are particularly hard to find solutions for (when move count doesnt matter). I'd be interested to see at least one example that has a lot of tricky dead states that would act as traps.

Compared to original sokoban game, the player's final position does not matter, and the number of boxes is strictly equal to the number of goal marks.

Fun game! Solver seems really smart. It would be great to disable double tap to zoom or make it slightly more adapted to phone screen sizes

I wonder how this would do with Thinky.gg games (Pathology or Sokopath). Are you familiar with the site? There's a group of engineers working on various types of solvers in the thinky.gg discord too.

pretty cool stuff, enjoyed it

Terms like AI used to mean something specific

[dead]