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, [all possible states the keeper can reach without pushing]) rather than (boxes, representative keeper position), so we can reduce recomputation of the player 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 additional cool state pruning techniques out there?
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.
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.
Imagine providing AI with ability to poke around a large bank of gridbased game problem instances. Ask it to solve them and learn from them and then generate new problem instances.
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, [all possible states the keeper can reach without pushing]) rather than (boxes, representative keeper position), so we can reduce recomputation of the player 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 additional cool state pruning techniques out there?
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.
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.
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.
Imagine providing AI with ability to poke around a large bank of gridbased game problem instances. Ask it to solve them and learn from them and then generate new problem instances.
This was a coursework problem in my CS course, back in the day. For larger canvases, the state-space blows up and it gets slow/intractable to solve.
“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?
Terms like AI used to mean something specific