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.

Dameon

Increase the stack size?

__________________
MD5(sig) = bcef75433db02e9ad9bf81d6f7c5c270

Ooble

You could loop back - for each state, see if it's somewhere else in the tree and point back to that state if it is, stopping yourself from creating duplicate data.

__________________
Me :: You :: Them

Sane

How do I increase stack size?


The problem isn't duplicated states. If I were traversing duplicated states, the depth would be infinite (because the graph is cyclical). And besides, the whole point of DP is it handles these repeated subproblems implicitely.

There are 20,000 distinct states. The problem is as I traverse these distinct states, they are all reachable from each other through cross edges, so a branch of depth 20,000 immediately unfolds when DFS'd. If it were BFS'd, the depth is only about 15. I need a technique to somehow BFS the graph while DPing it through post-traversal.

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

Sane

Shoot.

I use Dev-C++ with GCC. No changing of the stack size for me. Unless I can get a hold of a program (such as editbin.exe and dumpbin.exe) to modify it manually. Either way, I think that is a cheap way around this problem.

Edit: A correction to when I said 10-20 possible moves. Often, states have as many as 200 cross edges to different branches (200 possible moves). That's why the graph unfolds into one main branch so easily; there is almost always an undiscovered state that can be accessed. But it also means the BFS'd graph is very (very) shallow. Maybe even closer to 10 levels.

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

The Dark

You could keep your own stack of items to work on (separate from the program stack) and use a loop to pick the last item on the stack. This depends on being able to keep all your context in your own stack entry.

Seif

I believe its possible to set the applications stack size when using the gnu linker with -stack <size>.

other ideas would be,

1. Check you aren't losing stack space due to alignment.
2. Play with the optimization switches with your compiler. In some cases you can get the compiler to omit generating stack allocations wherever it can.
3. Use the heap. keep track of where your at and make your own stack.

Sane

Agh! I got it! How could I be so silly.

Of course I can BFS and DP at the same time. To solve the subproblems in the correct order, simply traverse the completed BFS queue in reverse!

This is actually essentially the same thing as making my own stack, because just as much memory will be used. The the only difference is the problems get solved in a different order. So I could do it either way.

Finally got it after 72 hours of thought. And after all that, I think I will actually go with the custom stack.

Thanks guys.

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