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?

▲

jan_Inkepa 23 minutes ago | parent | next [-]

There's computational complexity, then there's human complexity. I've thought a lot about this over the years (I've made a bunch of puzzle games, and puzzlescript, an engine/language for making grid-based puzzle games), and the only paper I've read that's made me think 'huh' was "Difficulty Rating of Sokoban Puzzle" by Jarušek and Pelánek ( https://www.fi.muni.cz/~xpelanek/publications/stairs2010-fin... ).

While I have a feeling that subject 'difficulty' is necessarily a slippery concept, they focus on 'context switching' as a key element of difficulty. In sokoban terms - how often you have to alternate between pushing one box and pushing another. This too can be gamed/trivialized, but, when I used it as a heuristic is was very good at generating the most horrifically difficult levels, much moreso than just going for 'solution length'.

On more general notions of complexity. In sokoban terms, the number of crates trumps everything else - for solvers I've written you quickly get exponential explosions with the number of crates. Nothing else really is significant.

I've also been working on solvers for more general classes of these games (puzzlescript games) and it's surprising how powerful generic solvers still are. PuzzleScript+MIS https://dekeyser.ch/puzzlescriptmis/ (not by me) is one powerful tool that uses PuzzleScript as a basis. I've worked on speeding up the solver a bunch (not currently integrated), figuring out good general heuristics for different kinds of games ( https://github.com/increpare/puzzlescript-labs has various experiments in this direction, including a modded version of PS+MIS). It's a nice optimizaiton problem for focusing on making numbers go down - there are lots of games to test on.

▲

FartyMcFarter 19 minutes ago | parent | prev | next [-]

According to Wikipedia Sokoban is NP-hard, which means there's no known polynomial time algorithm to solve it. It also means it's unlikely such an algorithm exists, as that would imply P=NP which is not believed to be the case.

▲

yobbo an hour ago | parent | prev [-]

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.

▲

xpct an hour ago | parent [-]

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

▲

mightybyte an hour ago | parent [-]

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.

	▲	xpct 21 minutes ago \| parent [-]
		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.