[rrobukef]

This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?

[jsnell]

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

[frankmcsherry]

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.

[jsnell]

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.

[rrobukef]

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.

[OskarS]

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 :)

[hinkley]

I think it warrants an explanation though. Why not DFS? Too hard to dedupe? What’s the branching factor and the duplication rate? If the algorithm is 50x faster due to lower overhead it might be worth it.

[ball_of_lint]

It would probably end up with similar memory requirements because it has to dedupe. Naively you would need to store all the visited states anyway just like with BFS.

You might see some interesting effects using a bloom filter and an IDDFS. It would turn the whole search probabilistic but might be fast enough that you could run it enough times to remove reasonable doubt.

[AstralStorm]

The problem seems to have many early branches making deep searches much less useful.