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

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.

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.

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?

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!