Tic Tac Toe with Minimax: the computer sometimes loses when the player goes first; works differently

Question

I am working on the Minimax algorithm for the unrivaled Tic Tac Toe. I need it to work for both the computer and the first, as well as for the first player. In the current version, the computer will never lose at the first start. However, it seems that Minimax never finds the best move (always returns -1 as a score) if the player goes first.

What causes the Minimax score to return -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 is 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 is the "Mark2" class, if there is any confusion:

 public enum Mark2 { BLANK, PLAYER, COMPUTER } 

Answer 1

After a long break, and with the help of @GuyAdini's answer, I had an epiphany. I wrote a test to calculate the appearance of three possible points returned by minimax (). As a result of this, nothing happened for 0, which led me to the fact that I needed the algorithm to be considered as a possible score.

I initially changed the initialization of the “score” as the smallest / maximum possible results (-1/1) and compared them. However, this forbade the result to receive the lowest / highest value solely from the set of points received and instead also included an initialized value. This ruined the results.

I added the following comparison to the conditional change in "rating":

 || availableIndex == 0 

This caused all other comparisons to be matched against the value that belonged to the set of returned estimates.

 public class Minimax { public static int minimax( Board board, Mark2 currentMark ) { int score = 0; 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 || availableIndex == 0 ) score = nextScore; } } return score; } } 

Answer 2

Look at something simpler - the 1x1 board, and the first player wins to place the sign there.

Now the computer starts, score = -1. There is no winning solution (one winning set is checked, this is not a 1-in-line), and there is free space. Therefore, we go back to try one available position.

Now Mark = PLAYER, and the board has a winning solution. Thus, the computer wins, score = -1.

Returning to the first call, the string "int nextScore = minimax (board, nextMark)"; returns -1 again, and the final result is -1.

The same thing happens to you with a bigger problem.

Answer 3

There are 3 possibilities in the Tic Tac Toe game, and not only 2: the winner is Player1, the winner is Player2, no one wins.

You should replace the lines as follows:

 int score = (currentMark == Mark2.COMPUTER) ? -1 : 1; 

in the following way:

 int score = (currentMark == Mark2.COMPUTER) ? -1 : ((currentMark == Mark2.PLAYER) ? 1 : 0);