3 ms·
While A* could be used to solve Sokoban, wouldn't some sort of Monte-Carlo Tree Search be better at it? I wonder how would it compare to this model.
by eterevsky 3y ago
While A* could be used to solve Sokoban, wouldn't some sort of Monte-Carlo Tree Search be better at it? I wonder how would it compare to this model.
- espadrine 3y agoThe part of MCTS that matters for solving it is the Bellman equation, which is a component of the Bellman-Ford shortest-path algorithm, so all of those methods are part of a continuum. Which one works best is pretty sensitive to the exploratory decisionmaking algorithm: do I search this cell first, or that one? That heuristic is the differentiator, whether it is put on top of a Dijkstra-style algorithm (A*) or a Bellman-Ford-style algorithm (MCTS).