GeeCON Prague 2014*
The moose likes Game Development and the fly likes Standard techniques to debug min-max trees? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Game Development
Bookmark "Standard techniques to debug min-max trees?" Watch "Standard techniques to debug min-max trees?" New topic
Author

Standard techniques to debug min-max trees?

Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8815
    
    5
Even "small" problems like tic-tac-toe need pretty big min-max trees to solve. For instance, a crude min-max tree for tic-tac-toe could theoretically create 9! (362k+) nodes!

That's a lot of nodes to look thru if you've got a bug. So the question is, are there standard debugging patterns for min-max trees?


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Darius Cooper
Greenhorn

Joined: Jul 10, 2008
Posts: 8
Interesting question. I don't know of any patterns, but when I did a little puzzle that generates a huge tree like that, I used two devices:
* First, my "StateNode" class has a toString() that gave me some key info, and I could call upon this selectively from elsewhere.
* Second, there were a few assertions I could make about my tree. I coded these into a method. Then, while in development, I would call this method at various points to see if my tree passed it's sanity checks.

What techniques do you use now, that may not be a pattern yet?
Bill Cruise
Ranch Hand

Joined: Jun 01, 2007
Posts: 148
I keep checking back to see if anyone comes up with an answer to this because I'd love to know.

Most of what I've read concentrates on pruning branches from the tree to reduce the search space. When you say "bug" are you talking about a possible bug in the routine that evaluates a position? From your question I can only guess that your AI isn't selecting the best move for a given position. This can result from not letting it look far enough ahead from a given node.
Kenneth Gustafsson
Ranch Hand

Joined: Jan 10, 2008
Posts: 40
There are lots of situations where you can't really get to grips with and have an overview of the entire state space when debugging. I would even say that it's true for most situations.If you're creating a text editor you can't simulate all possible input variants. And if you're creating a web browser you can't simulate all web page structures, and so on.

Debugging states of an min-max algorithm is no different from any other problem. You might be baffled by the fact that you're creating huge trees?

If your algorithm is recursive (which min-max usually is, but it may be implemented differently too) you might run out of stack space. Let it tackle a problem which you think is representative for what you want to do, if it fails due to stack space memory problems you need to deal with it. If you can't optimize it any further then you might want to change algorithm. Personally I think no one should use min-max, they should use alpha beta pruning.

Apart from that you need to do what you normally do. Write up a case analysis of the most important different structures/situations your code may face. Simulate and test each case separately, does it perform as expected?

Also throw at it lots of examples where you know the correct answer. As min-max is guaranteed to produce the best result as long as you have enough memory throw some semi-finished tic-tac-toe games at it. Let it have one, two, three and maybe four moves until it wins (or until you win, depending on what you want to test). That will keep the number of states in the tree low, you will have a complete overview of the state tree and you will know the expected output.

[ July 15, 2008: Message edited by: Kent Larsson ]
[ August 04, 2008: Message edited by: Kenneth Gustafsson ]
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8815
    
    5
Hey Kent,

I'm with you on most of what you said. I am in fact using a modified alpha-beta search.

I guess that a lot of the difficulty is in debugging complex recursive chunk of code. It almost seems like there ought to be some strategies unique to debugging recursive code...
Kenneth Gustafsson
Ranch Hand

Joined: Jan 10, 2008
Posts: 40
Yes. Well I think that you handle it mostly the same way as you do for recursion in math. By dividing it into the possible ways it may branch and trying out each of those cases. By proving that the parts are doing what they are supposed to you prove that the whole algorithm is sound. I think that's the strategy. :-)
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Standard techniques to debug min-max trees?