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 ]