Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm working on a school project, I have to build a tic tac toe game with the AI based on the MiniMax algorithm. The two player mode works like it should.

I followed the code example on http://ethangunderson.com/blog/minimax-algorithm-in-c/. The only thing is that I get a NullPointer Exception when I run the code. And I can't wrap my finger around it.

I placed a comment in the code where the exception is thrown. The recursive call is returning a null pointer, what is very strange because it can't.. When I place a breakpoint on the null return with the help of a if statement, then I see that there ARE still 2 to 3 empty places.. I probably overlooking something.

Hope someone can tell me what I'm doing wrong.

Here is the MiniMax code (the tic tac toe code is not important):

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package MiniMax;

import Game.Block;
import Game.Board;
import java.util.ArrayList;


public class MiniMax {
public static Place getBestMove(Board gameBoard, Block.TYPE player) {
    Place bestPlace = null;
    ArrayList<Place> emptyPlaces = gameBoard.getEmptyPlaces();
    Board newBoard;

    //loop trough all the empty places
    for(Place emptyPlace : emptyPlaces) {
        newBoard = gameBoard.clone();
        newBoard.setBlock(emptyPlace.getRow(), emptyPlace.getCell(), player);

        //no game won and still room to move
        if(newBoard.getWinner() == Block.TYPE.NONE && newBoard.getEmptyPlaces().size() > 0) {                
            //is an node (has children)
            Place tempPlace = getBestMove(newBoard, invertPlayer(player));

            //ERROR is thrown here! tempPlace is null.
            emptyPlace.setScore(tempPlace.getScore());
        } else {
            //is an leaf
            if(newBoard.getWinner() == Block.TYPE.NONE) {
                emptyPlace.setScore(0);
            } else if(newBoard.getWinner() == Block.TYPE.X) {
                emptyPlace.setScore(-1);
            } else if(newBoard.getWinner() == Block.TYPE.O) {
                emptyPlace.setScore(1);
            }

            //if this move is better then our prev move, take it!
            if((bestPlace == null)
                    || (player == Block.TYPE.X && emptyPlace.getScore() < bestPlace.getScore())
                    || (player == Block.TYPE.O && emptyPlace.getScore() > bestPlace.getScore())) {
                bestPlace = emptyPlace;
            }
        }
    }

    //This should never be null, but it does..
    return bestPlace;
}

private static Block.TYPE invertPlayer(Block.TYPE player) {
    if(player == Block.TYPE.X) {
        return Block.TYPE.O;
    }

    return Block.TYPE.X;
}
}
share|improve this question

1 Answer 1

up vote 2 down vote accepted

You are only updating bestPlace in the second branch of the outermost if. Simply put the if((bestPlace == null)... block outside that branch so that it gets executed at each iteration:

        /* ... */
        } else if(newBoard.getWinner() == Block.TYPE.O) {
            emptyPlace.setScore(1);
        }
    }

    //if this move is better then our prev move, take it!
    if((bestPlace == null)
            || (player == Block.TYPE.X && emptyPlace.getScore() < bestPlace.getScore())
            || (player == Block.TYPE.O && emptyPlace.getScore() > bestPlace.getScore())) {
        bestPlace = emptyPlace;
    }
}
/* ... */
share|improve this answer
    
+1 - this can be found also in C implementation, which Sven linked. Sven, if you are rewriting some code, you should rewrite it correctly ;) –  zacharmarz Nov 21 '11 at 12:43
    
Thx! Can't believe I looked over it! @zacharmarz haha next time I will :) –  Sven Nov 21 '11 at 13:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.