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 LLMs via ontologies built with old AI approaches. Frank Coyle presented this idea about a month ago: https://www.youtube.com/watch?v=Sir59K8ZDPU
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.
Hmm, I would say even older than that (which, of course, is in no way intended to be a value statement of any kind, I like the website and the project, cool idea! :D).
If you squint a little, the linked project is basically a https://en.wikipedia.org/wiki/A*_search_algorithm with optimized implementation, heuristics and so on. I also think that A* was associated with AI due to its use in path finding in early robotics - But I am not sure!
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.
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.
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 LLMs via ontologies built with old AI approaches. Frank Coyle presented this idea about a month ago: https://www.youtube.com/watch?v=Sir59K8ZDPU
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?
Hmm, I would say even older than that (which, of course, is in no way intended to be a value statement of any kind, I like the website and the project, cool idea! :D).
In 2015, https://en.wikipedia.org/wiki/AlphaGo came around and latest from there on, AI was associated heavily with NNs, deep learning and so on (but not with the transformer architecture which became popular later, the foundational paper itself was published in 2017: https://en.wikipedia.org/wiki/Attention_Is_All_You_Need).
If you squint a little, the linked project is basically a https://en.wikipedia.org/wiki/A*_search_algorithm with optimized implementation, heuristics and so on. I also think that A* was associated with AI due to its use in path finding in early robotics - But I am not sure!
No, that's still AI in today's sense, just not an LLM.
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.
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
Not really: https://en.wikipedia.org/wiki/Artificial_intelligence#Techni...