Hacker News Reader

Comment by yobbo | Hacker News Reader

For 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.

View on HN

Thanks. Given a solver, could we extrapolate a problem's branching factor? For classic Sokoban, I'd guess it's on the lower side?

I 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.

Hmm. 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.

Reply on news.ycombinator.com