undefined | Better HN

0 pointsjsnell7y ago0 comments

As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth.

Totally happy to believe I'm wrong about that, though :)

[0] https://github.com/apocalyptech/snakebirdsolver

0 comments

frankmcsherry7y ago

It's a super interesting post, and I've no reason to think that iterative deepening would be better, just that it is designed to deal with exactly this problem. The lack of growth in novel states may invalidate its main hypothesis though (tree-like growth).

The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their DFS implementation retains state; not sure what to make of it, and not a Python reader:

> Depth-First should be a bit kinder to system memory, though it'll still chew up quite a bit remembering which game states we've seen before.

jsnellOP7y ago

Fair enough, and it's easy to test :)

I made a non-iterative DFS, but hardcoded the maximum depth to the optimal solution. On a trivial puzzle that should take <1ms, it takes 6 seconds. The BFS visits 303 states, the DFS 9M (but only 237 unique ones). This is with deduping the states on the path. If we allow the same state on the path multiple times, it'd be 12s, 50M visited states, 239 unique states. This is with a random visiting order, it'd be a bit worse with a static visiting order.

This is obviously not fully optimized code (whee, std::unordered_set). But fixing that won't help when we're off by 3-4 orders of magnitude. I think the shape of the search graph of this game just isn't well suited to any form of DFS, there are far too many alternate paths to each state.

rrobukef7y ago

Thank you. It's interesting to see the explosion of states. You could add a cache (per search depth) to deduplicate states again. It will reduce small cycles and the used memory is easier to control.

Kudos for the encoding. 0.7 bits per state is dense.

OskarS7y ago

The linked solver doesn't use iterative deepening, and it saves all states that the DFS solver encounters (negating the advantage of using DFS).

I think IDDFS might work really well here, even without a good heuristic. It's worth trying, at the very least.

EDIT: read your reply to the other user. Fair enough :)

j / k navigate · click thread line to collapse