I am attempting to make an unbeatable Tic Tac Toe game using a simplified minimax algorithm. The code looks like this:
private static int findBestMove(String[][] board, boolean comp) {
// comp returns true if the computer is the one looking for the best move
// findBestMove is always called by the program as findBestMove(board, true)
// since the computer is the only one that uses it
// If the board in its current state is a win for the
// player, return -1 to indicate a loss
if (playerWon(board)) return -1;
// If the board in its current state is a win for the
// computer, return 1 to indicate a win
if (compWon(board)) return 1;
// If the board in its current state is a tie
// return 0 to indicate a tie
if (tie(board)) return 0;
// Set the default possible outcome as the opposite of what
// the respective player wants
int bestPossibleOutcome = comp ? -1 : 1;
// Loop through the board looking for empty spaces
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
// Once an empty space is found, create a copy of the board
// with that space occupied by the respective player
if (board[i][j].equals(" ")) {
String[][] newBoard = new String[3][3];
for (int a = 0; a < 3; a++) {
System.arraycopy(board[a], 0, newBoard[a], 0, 3);
}
newBoard[i][j] = comp ? "O" : "X";
// Recursively call findBestMove() on this copy
// and see what the outcome is
int outCome = findBestMove(newBoard, !comp);
// If this is the computer's turn, and the outcome
// is higher than the value currently stored as the
// best, replace it
if (comp && outCome > bestPossibleOutcome) {
bestPossibleOutcome = outCome;
// r and c are instance variables that store the row
// and column of what the computer's next move should be
r = i;
c = j;
// If this is the player's turn, and the outcome
// is lower than the value currently stored as the
// best, replace it
} else if (!comp && outCome < bestPossibleOutcome) {
bestPossibleOutcome = outCome;
}
}
}
}
// Return the ultimate value deemed to be the best
return bestPossibleOutcome;
}
The idea is that after I run this program, the instance variables r and c should contain the row and column, respectively, of the computer's best move. However, the program only successfully prevents a loss about half the time, and I can't tell if the other half is luck, or if the program is actually working.
I am aware that the computer will respond to every scenario exactly the same way each game. That is fine.
In the event anyone would like to run the program, I have included the full class below:
import java.util.Scanner;
public class TicTacToe {
private static int r;
private static int c;
private static void printBoard(String[][] board) {
System.out.println(" 0 1 2");
System.out.println("0 " + board[0][0] + " | " + board[0][1] + " | " + board[0][2] + " ");
System.out.println(" ---+---+---");
System.out.println("1 " + board[1][0] + " | " + board[1][1] + " | " + board[1][2] + " ");
System.out.println(" ---+---+---");
System.out.println("2 " + board[2][0] + " | " + board[2][1] + " | " + board[2][2] + " ");
}
private static boolean playerWon(String[][] board) {
return playerHasThreeInCol(board) || playerHasThreeInDiag(board) || playerHasThreeInRow(board);
}
private static boolean playerHasThreeInRow(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0].equals(board[i][1]) && board[i][0].equals(board[i][2]) && board[i][0].equals("X")) return true;
}
return false;
}
private static boolean playerHasThreeInCol(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[0][i].equals(board[1][i]) && board[0][i].equals(board[2][i]) && board[0][i].equals("X")) return true;
}
return false;
}
private static boolean playerHasThreeInDiag(String[][] board) {
if (board[0][0].equals(board[1][1]) && board[0][0].equals(board[2][2]) && board[0][0].equals("X")) return true;
return board[0][2].equals(board[1][1]) && board[0][2].equals(board[2][0]) && board[0][2].equals("X");
}
private static boolean compWon(String[][] board) {
return compHasThreeInCol(board) || compHasThreeInDiag(board) || compHasThreeInRow(board);
}
private static boolean compHasThreeInRow(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0].equals(board[i][1]) && board[i][0].equals(board[i][2]) && board[i][0].equals("O")) return true;
}
return false;
}
private static boolean compHasThreeInCol(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[0][i].equals(board[1][i]) && board[0][i].equals(board[2][i]) && board[0][i].equals("O")) return true;
}
return false;
}
private static boolean compHasThreeInDiag(String[][] board) {
if (board[0][0].equals(board[1][1]) && board[0][0].equals(board[2][2]) && board[0][0].equals("O")) return true;
return board[0][2].equals(board[1][1]) && board[0][2].equals(board[2][0]) && board[0][2].equals("O");
}
private static boolean tie(String[][] board) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) return false;
}
}
return true;
}
private static int findBestMove(String[][] board, boolean comp) {
if (playerWon(board)) return -1;
if (compWon(board)) return 1;
if (tie(board)) return 0;
int bestPossibleOutcome = comp ? -1 : 1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
String[][] newBoard = new String[3][3];
for (int a = 0; a < 3; a++) {
System.arraycopy(board[a], 0, newBoard[a], 0, 3);
}
newBoard[i][j] = comp ? "O" : "X";
int outCome = findBestMove(newBoard, !comp);
if (comp && outCome > bestPossibleOutcome) {
bestPossibleOutcome = outCome;
r = i;
c = j;
} else if (!comp && outCome < bestPossibleOutcome) {
bestPossibleOutcome = outCome;
}
}
}
}
return bestPossibleOutcome;
}
private static void go() {
Scanner input = new Scanner(System.in);
String[][] board = new String[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
board[i][j] = " ";
}
}
printBoard(board);
for (int i = 0;; i++) {
if (i % 2 == 0) {
while (true) {
System.out.println("Enter position: ");
String position = input.nextLine();
int row, column;
try {
row = Integer.parseInt(position.substring(0, 1));
column = Integer.parseInt(position.substring(1, 2));
} catch (Exception e) {
System.out.println("Invalid entry. ");
continue;
}
if (row < 0 || row > 2 || column < 0 || column > 2) {
System.out.println("That position is not on the board. ");
continue;
}
if (!board[row][column].equals(" ")) {
System.out.println("That space is already taken. ");
continue;
}
board[row][column] = "X";
break;
}
} else {
System.out.println("\nMy move: ");
findBestMove(board, true);
board[r][c] = "O";
}
printBoard(board);
if (playerWon(board)) {
System.out.println("You win!");
break;
} else if (compWon(board)) {
System.out.println("I win!");
break;
} else if (tie(board)) {
System.out.println("Tie game");
break;
}
}
}
public static void main(String[] args) {
go();
}
}
I'm not asking for anyone to rewrite the whole thing for me, but if you can point out any obvious mistakes or point me in the right direction, that would be appreciated. I am also open to any suggestions or comments that you may have.
I haven't extensively tested it yet, but I believe that I resolved the issue. The new code looks like this:
private static void findBestMove(String[][] board) {
double bestMove = Double.NEGATIVE_INFINITY;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
board[i][j] = "O";
double score = minimax(board, false);
board[i][j] = " ";
if (score > bestMove) {
bestMove = score;
r = i;
c = j;
}
}
}
}
}
private static double minimax(String[][] board, boolean comp) {
if (playerWon(board)) {
return -1;
}
if (compWon(board)) {
return 1;
}
if (tie(board)) return 0;
double bestScore;
if (comp) {
bestScore = Double.NEGATIVE_INFINITY;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
board[i][j] = "O";
double score = minimax(board, false);
board[i][j] = " ";
bestScore = Math.max(score, bestScore);
}
}
}
} else {
bestScore = Double.POSITIVE_INFINITY;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
board[i][j] = "X";
double score = minimax(board, true);
board[i][j] = " ";
bestScore = Math.min(score, bestScore);
}
}
}
}
return bestScore;
}
I abstracted the minimax algorithm away from the next move coordinate setter, which I think may have made a difference. Otherwise, it is very similar.