Sokoban AI Solver - Optimal puzzle solver in JavaScript
This is an interactive Sokoban puzzle solver that runs entirely in the browser. It features a custom AI that finds the provably fewest-moves solution for each board, using advanced techniques like macro-push A* search, compact bitmask states, and deadlock pruning. The solver is a plain-JavaScript port of a native C++ optimal solver, and it solves boards 1–14 to the proven optimum in milliseconds. For the largest board (15), the optimal solution was computed offline and is played back. The interface includes controls for arrow keys or WASD, undo, and reset, making it easy to play and learn from the AI's strategies.
The AI returns the provably fewest-moves solution, not just some solution, using a move-optimal macro-push A* search that skips over individual walking steps.
- TimTheTinker
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.
- tintor
This Sokoban solver works on tiny and simple Sokoban levels, lagging behind the several SOTA Sokoban solvers that are available.
http://www.sokobano.de/wiki/index.php?title=Solver_Statistic...
- epiccoleman
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 […]
- GPerson
“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?
- npinsker
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.