undefined | Better HN

0 pointsfrankmcsherry7y ago0 comments

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.

0 comments

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

j / k navigate · click thread line to collapse