5 ms·
Show HN: Sokoban AI Solver
- GPerson 2mo ago“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?
- nairboon 2mo agoNo, that's still AI in today's sense, just not an LLM.
- deleted 2mo ago[deleted]
- GPerson 2mo agoOn further reflection I actually now disagree that a an algorithm based puzzle solver was ever referred to as AI, even in the context of video games, in which AI refers to the behavior of NPCs.
- dev_dan_2 2mo agoHmm, 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 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 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 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!
- j16sdiz 2mo ago[dead]
- mohamedkoubaa 2mo agoTerms like AI used to mean something specific
- layer8 2mo agoNot really: https://en.wikipedia.org/wiki/Artificial_intelligence#Techniques https://en.wikipedia.org/wiki/Artificial_intelligence#Techni...
- deleted 2mo ago[deleted]
- cbondurant 2mo agoWhile 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.
- Retr0id 2mo agoThis 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.
- conmod278 2mo agoImagine 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.
- npinsker 2mo agoIntuitively, 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 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.
- throwaway219450 2mo agoShowing the exploration would be nice. À la RedBlob tutorials, seeing the solver work is part of the fun. As is I have no intuition for where the algorithm would spend all its time and where it can easily rule out. 1GB of RAM for the final puzzle isn’t too bad for a browser demo if you warn the user and don’t run automatically (is the state space compressible?)
- qbane 2mo agoCompared 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.
- enjoyyourlife 2mo agoThat's by design. This is a variant originally from an AI class I took
- Sebastian_09 2mo agoFun 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
- CatalystPz 2mo agopretty cool stuff, enjoyed it
- enjoyyourlife 2mo agoThanks!
- k2xl 2mo agoI 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.
- xpct 2mo agoGot 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?
- yobbo 2mo agoFor games in general, one measure of complexity is branching factor. It means average number of possible actions or states at each turn. It is knowable. "Solvability" would mean number of turns to solve the game. It is known for some puzzles and can be found by brute force, otherwise you need to figure out a proof.
- xpct 2mo agoThanks. Given a solver, could we extrapolate a problem's branching factor? For classic Sokoban, I'd guess it's on the lower side?
- mightybyte 2mo agoI think there are two ways one could look at this. One is to make each move be a move of the player's location. If you do that, then the branching factor is obviously < 8. But there's a second way you could define a "move" for the purposes of a solver. And that would be to only consider pushes. In that case, the branching factor would be < 8*num_stones. In either case, I think when trying to assess complexity it might also be useful to consider the "narrowness" of the winning move sequence. Positions where the number of moves that win/make progress towards the goal is a small fraction of the number of available moves would arguably be harder or more complex than positions where a larger percentage of the moves win/make progress. In other words, finding a smaller needle and/or in a larger haystack makes the problem harder / more complex.
- xpct 2mo agoHmm. The push representation makes sense because solve progress is entirely dependent on it. And the movement state tree can be reduced to the push tree, which would only prune useless paths. The push tree can probably also be pruned for moves that leave to softlock, but I wonder whether it can be reduced to a different representation still. Push tree already requires us to maintain a mask of where we can move to, so it's not computationally free. I can imagine representing box pushes as every position we can push it to in the current setup, but that would also make it more computationally expensive. I feel like there's an interesting tradeoff of storing/computing cheap representations vs exploring a smaller tree.
- TimTheTinker 2mo agoI 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 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.
- dietr1ch 2mo ago> I suspect that the next big AI breakthrough will result at least in part from constraining LLM decisions with old AI approaches. AFAIK bridging deductive and inductive AI has been understood as the trick for "AGI" for a long time, probably even before it was called AGI. I really want this winter of deductive AI to be short. We need both sides and can't afford a long winter like the one inductive AI suffered.
- skew-aberration 2mo agoFWIW when I first studied automatic theorem proving as a (high school) student in 2013, this was already widely discussed. They were trying to add neural networks inside the solvers, rather than current paradigm of a neural networks using theorem provers as tools. Presumably the history of logic + natural language computers would go back a lot further.
- Someone 2mo ago> I suspect that the next big AI breakthrough will result at least in part from constraining LLM decisions with old AI approaches. > 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 I don’t think that’s “going beyond that”. It’s a blackboard system from the 1980s (https://en.wikipedia.org/wiki/Blackboard_system https://en.wikipedia.org/wiki/Blackboard_system)
- epiccoleman 2mo agoI'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!
- cbondurant 2mo agoI think 14 exists as a test case for having a larger search space that needs to be efficiently ignored. Its not difficult solution wise, but if it is particularly slow that means you're doing a bad job at pruning potential steps. Making sure you're doing good early pruning of the empty chambers.
- epiccoleman 2mo agoYeah, that was kinda what I figured too, maybe something about the "pinwheel" shape makes the pruning harder (since beyond each bottleneck there's a large amount of useless search space.) Kinda tempted to go play with it now and see if it becomes more obvious...
- amelius 2mo agoDoesn't this break down quickly as the area increases? (Ironically, the complexity goes down as there are more squares to use).
- tintor 2mo agoThis 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_Statistics http://www.sokobano.de/wiki/index.php?title=Solver_Statistic...
- h2aichat 2mo agoAddictive ;-)