MiniMax return reverse utility value

Question

I am trying to print out the visited sate and utility of Mini Max. I'm having problem when the value return from the terminal state back to its root, thus causing 4 of my visited state utility value to be incorrect. I just can't figure out what cause this error. I pretty sure my Min and Max method is correct.

Answer 1

Taking the first state in your list, you need to explain why ooxxxo-xo should be 1. If I re-write this how I think I'm supposed to read it, the state reads as:

oox
xxo
-xo

If we correctly apply x as the next move, we would get the right answer. So, perhaps the problem is in your move generation.

Looking at this, you have a single static array which is storing the moves, but when you make recursive calls, you will overwrite this moves over and over again. Instead, you need a local copy of the moves for each recursive call. So, moving your definition of minChildren and maxChildren into MinTurn and MaxTurn should fix at least one problem in the code. (I haven't verified that there aren't other problems.)

To be clear, your call stack goes something like this:

MaxTurn call
  Set maxChildren to legal moves // <--- A
  Call MinTurn recursively
    MinTurn call
      Set minChildren to legal moves
      Call MaxTurn recursively
        MaxTurn call
          Set maxChildren to legal moves // <--- B
          Call MinTurn recursively

When you reach the line marked B you are overwriting the maxChildren which are computed at line A. Thus, when the program returns to A, the available moves will have been overwritten and may be different that what was previously expected.

---

After fixing that, I believe your new problem is just in the way you are printing things. If you look at your printing code, you log the current max value, not the value returned by the child:

int maxValue = Setting.NEGATIVE_INFINITY;
maxChildren = generateMoves(state);
for (State aChildren : maxChildren) {
    maxValue = Math.max(maxValue, MinTurn(aChildren)); // <-- A
    nodes.add(aChildren.getState() + " " + maxValue); // <--B
}

So, in the line marked B you are printing maxValue for all children seen so far. If you want to see the value of the child, you shouldn't immediately take the max in line A. Instead you store the result and log it. Then, take the max.

You're having trouble with this state:

oox
xxo
-x-

This is printed from the parent state where the search presumably starts from:

oox
xxo
---

The first move is to put the x in the bottom left corner, which wins the game and gives a value of 1. When the second move is applied, leading to the state with the x in the middle, the maxValue is still 1 from the previous move.

Your code should look something like this:

int nextValue = MinTurn(aChildren)
maxValue = Math.max(maxValue, nextValue);
nodes.add(aChildren.getState() + " " + nextValue);