Function does not return negative value

Question

I am doing a small project on 4x4 tic-tac-toe game. I am using Alpha Beta Search for finding the next best move. In the alpha beta search, I am using a cutoff evaluation function that is being called in "utility" function of the following algorithm

I implemented everything successfully, but the problem is the utility function doesn't return a negative value and I really don't know why! Following is the function

private static int utility(GameTreeNode gtn, bool isMin = false)
{
    int nodeValue = 0;
    switch (gtn.NodeBoard.getBoardStatus())
    {
        case Status.Success:
            nodeValue = 50;
            if (isMin) nodeValue = -50;    /// here
            break;
        case Status.Incomplete:
            if (isMin)
                nodeValue = gtn.evaluate(State.X);
            else
                nodeValue = gtn.evaluate(State.O);
            break;
    }
    // case Status.Draw:
    return nodeValue;
}

isMin is set to true, when it is called from MinValue function

isMin is the move of O and the AI's move is X. If O wins the utility is supposed to return -50. But it returns only 0. I debugged the program and it actually assigns -50 to nodeValue (nodeValue changes in the debugger to -50), but when I receive in the Min or Max function, it is zero.

Note: All the int used in the entire project is signed int. No unsigned keyword is used, if you are thinking the function-caller is unsigned

The full code of alpha-beta search is here: http://pastie.org/8538015

Please friends, help as soon as possible.

Answer 1

Since you're using an optional parameter in your method signature, I'd caution you to pay attention to what your code is actually running when entering your function. You said you debugged it and the value gets assigned, but I don't have enough context to know if it only happens in one of many cases or not. Anyway, just be careful with those!

I would rewrite your function like this:

private static int utility(GameTreeNode gtn, bool isMin)
{
    switch (gtn.NodeBoard.getBoardStatus())
    {
        case Status.Success:
            return isMin 
                ? -50 
                : 50;
        case Status.Incomplete:
            return isMin 
                ? gtn.evaluate(State.X)
                : gtn.evaluate(State.O);
        default:
            throw new NotImplementedException("The status is not implemented.");
    }
}

A few improvements I see with this approach:

• You don't need to store a value and return it at the end. In your case, you're always storing 50 into nodeValue when you take the Status.Success path, and then sometimes assigning -50 to it. Unless you're adamant about one return in your function, I think this approach is more clear. Might just be my opinion though.
• There's a default in the switch statement so that you'll explicitly throw an exception in the case where you have a status that isn't implemented.
• There is no optional parameter to your function. I don't see the benefit of making this parameter optional. In my opinion, it only looks like it's adding room to make things harder to debug.

EDIT:

Based on the code at:http://pastie.org/8538015#33,43

It looks like the only time you can ever get utility to return a negative value is when if (gtn.Nodes.Count == 0) return utility(gtn, true); is hit in the private static int MinValue(GameTreeNode gtn, int alpha, int beta) function. Otherwise, unless there's more code which you haven't posted, no other call to the utility function will hit the logical path your going for. You've mentioned when you step into there, you can see the value for nodeValue get properly assigned.

I'm suggesting you change:

// if Terminal-test(state) then return utitly(state)
if (gtn.Nodes.Count == 0) return utility(gtn, true);
gtn.Value = Globals.MAXINT;

To

// if Terminal-test(state) then return utitly(state)
if (gtn.Nodes.Count == 0)
{
    int retVal = utility(gtn, true);
    return retVal;
}

gtn.Value = Globals.MAXINT;

At least temporarily, and then put a breakpoint on return retVal. If your utility function is actually setting the value you expect like you say, there's no way that it could magically go away when it returns it to the MinValue function. I have a feeling something fishy is happening and the code isn't actually executing the path you expect.