• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Standard techniques to debug min-max trees?

 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Ranch Hand
Posts: 148
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 40
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 40
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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. :-)
 
reply
    Bookmark Topic Watch Topic
  • New Topic