alt Hacker NewsWow, thank you for your input! The "alternation" proxy for difficulty is fascinating to me, doesn't feel like something I would have thought of right away. And, I guess I wasn't aware of how much thought goes into designing Sokobans :)
I think the crates trumping other complexity metrics isn't entirely obvious to me. For problem 15 in the OP's post, author says it was too expensive to compute at runtime in the browser. From a human perspective, it's not apparent why, as a large part of the solution is very repetitive. It feels as if there should be a more condensed representation for iterating over problems like that one.
If I may gauge your opinion on it, have you looked into MazeBench? It comes from LLM benchmarking circles, but seems to suggest a search space that's too difficult for LLMs, even with tools, to solve. Curious how much overlap the PS/MIS solvers would have with solving something like this.
> From a human perspective, it's not apparent why, as a large part of the solution is very repetitive. It feels as if there should be a more condensed representation for iterating over problems like that one.
I'm not sure how 'in' you are, you might know this already, but for sokoban IIRC the recommended way is to treat things is topologically - you always do a flood-fill empty space from the player so that the decision isn't whether to go up/down/left/right on this turn but which accessible side of which crate to push. It decomposes quite well, and maybe makes the complexity a bit more obvious? Hmm...
I haven't looked into mazebench, but yes this is very related stuff.