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;
}
}
