Sane

While constructing an AI for a board game, I've run into a problem that I've now given a good 48 hours of inconclusive thought.

Each turn in the board game has around 10-20 possible moves. Also, there are roughly 20,000 or so different board combinations.

The graph is undirected and cyclical. In other words, you can move back and forth between two board states, and also back to previous board states. Furthermore, as a consequence of having 10-20 possible moves, there's always a way to get to every other possible board setup from the one you are currently on.

This causes a huge issue when running a DFS to solve each subproblem. Even if I force it to be directed and acyclical, the graph can still reach a depth of ~ 20,000 by finding alternate routes to unravel every one of the possible 20,000 setups before even beginning to post-traverse.

And here's the problem: A recursive depth of 10,000 causes a stack overflow.

I was thinking of implementing a queue and BFSing it. However, I need the post-traversal side of recursion in order to express the problem in terms of the result of each subproblem (remember that this is DP and not finding a specific node in a graph).

Logically all 20,000 don't need to be unravelled in one branch. That's just how it ends up when I DFS it. So are there any known techniques for overcoming the problem of a DP graph that unravels very deep subproblems? I need some way to limit the depth, yet still have the subproblems solved in the correct order...

__________________
Looking for tough programming challenges? Try participating in Sane's Monthly Algorithms Challenges!
Composing Techno is a little side hobby of mine. Techno by DJ Sane. All free for download.