I am working on a Minimax algorithm for unbeatable Tic Tac Toe. I need it to work both for when the Computer goes first as well as when the Player goes first. With the current version, the Computer will never lose when going first. However, it seems that Minimax never finds a best move (always returns -1 as the score) if the Player goes first.
What is causing the Minimax score returned to be -1 for the Computer if the Player makes the first move?
Example:
board.addMark( 1, Mark2.PLAYER ); // add a 'PLAYER' mark to an arbitrary location
Minimax.minimax( board, Mark2.COMPUTER ); // will always return -1
Here's the 'Minimax' class:
public class Minimax {
public static int minimax( Board board, Mark2 currentMark ) {
int score = (currentMark == Mark2.COMPUTER) ? -1 : 1;
int[] availableSpaces = board.getAvailableSpaces();
if ( board.hasWinningSolution() )
score = (board.getWinningMark() == Mark2.COMPUTER) ? 1 : -1;
else if ( availableSpaces.length != 0 ) {
Mark2 nextMark = (currentMark == Mark2.COMPUTER) ? Mark2.PLAYER : Mark2.COMPUTER;
for ( int availableIndex = 0; availableIndex < availableSpaces.length; availableIndex++ ) {
board.addMark( availableSpaces[availableIndex], currentMark );
int nextScore = minimax( board, nextMark );
board.eraseMark( availableSpaces[availableIndex] );
if ( currentMark == Mark2.COMPUTER && nextScore > score
|| currentMark == Mark2.PLAYER && nextScore < score )
score = nextScore;
}
}
return score;
}
}
Here is the 'Board' class:
public class Board {
private Mark2 gameBoard[];
private int blankSpaces;
private boolean solutionFound;
private Mark2 winningMark;
public final static int winSets[][] = {
{ 0, 1, 2 }, { 3, 4, 5 },
{ 6, 7, 8 }, { 0, 3, 6 },
{ 1, 4, 7 }, { 2, 5, 8 },
{ 0, 4, 8 }, { 2, 4, 6 }
};
public Board() {
gameBoard = new Mark2[9];
blankSpaces = 9;
for ( int boardIndex = 0; boardIndex < gameBoard.length; boardIndex++ ) {
gameBoard[boardIndex] = Mark2.BLANK;
}
}
public void addMark( int spaceIndex, Mark2 mark ) {
if ( gameBoard[spaceIndex] != mark ) {
gameBoard[spaceIndex] = mark;
if ( mark == Mark2.BLANK ) {
blankSpaces++;
} else {
blankSpaces--;
}
}
}
public void eraseMark( int spaceIndex ) {
if ( gameBoard[spaceIndex] != Mark2.BLANK ) {
gameBoard[spaceIndex] = Mark2.BLANK;
blankSpaces++;
}
}
public int[] getAvailableSpaces() {
int spaces[] = new int[blankSpaces];
int spacesIndex = 0;
for ( int boardIndex = 0; boardIndex < gameBoard.length; boardIndex++ )
if ( gameBoard[boardIndex] == Mark2.BLANK )
spaces[spacesIndex++] = boardIndex;
return spaces;
}
public Mark2 getMarkAtIndex( int spaceIndex ) {
return gameBoard[spaceIndex];
}
public boolean hasWinningSolution() {
this.solutionFound = false;
this.winningMark = Mark2.BLANK;
for ( int setIndex = 0; setIndex < winSets.length && !solutionFound; setIndex++ )
checkSpacesForWinningSolution( winSets[setIndex][0], winSets[setIndex][1], winSets[setIndex][2] );
return solutionFound;
}
public Mark2 getWinningMark() {
return this.winningMark;
}
private void checkSpacesForWinningSolution( int first, int second, int third ) {
if ( gameBoard[first] == gameBoard[second] && gameBoard[third] == gameBoard[first]
&& gameBoard[first] != Mark2.BLANK ) {
solutionFound = true;
winningMark = gameBoard[first];
}
}
public void printBoard() {
System.out.printf( " %c | %c | %c\n", getMarkCharacter( gameBoard[0] ), getMarkCharacter( gameBoard[1] ),
getMarkCharacter( gameBoard[2] ) );
System.out.println( "------------" );
System.out.printf( " %c | %c | %c\n", getMarkCharacter( gameBoard[3] ), getMarkCharacter( gameBoard[4] ),
getMarkCharacter( gameBoard[5] ) );
System.out.println( "------------" );
System.out.printf( " %c | %c | %c\n", getMarkCharacter( gameBoard[6] ), getMarkCharacter( gameBoard[7] ),
getMarkCharacter( gameBoard[8] ) );
}
public char getMarkCharacter( Mark2 mark ) {
char result = (mark == Mark2.PLAYER) ? 'O' : ' ';
result = (mark == Mark2.COMPUTER) ? 'X' : result;
return result;
}
}
And here's the 'Mark2' class if there was any confusion:
public enum Mark2 {
BLANK,
PLAYER,
COMPUTER
}
