Minimax based Tic Tac Toe

Question

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.

Answer 1

Welcome to Code Review. I run your code and the game works well, probably there is something you have to adjust about strategy, because it does not always choose the best move to win the match or at least tie. In your code there are some repetitions about method to check if the player or the computer wins like your code below:

private static boolean playerWon(String[][] board) {}
private static boolean playerHasThreeInRow(String[][] board) {}
private static boolean playerHasThreeInCol(String[][] board) {}
private static boolean playerHasThreeInDiag(String[][] board) {}
private static boolean compWon(String[][] board) {}
private static boolean compHasThreeInRow(String[][] board) {}
private static boolean compHasThreeInCol(String[][] board) {}
private static boolean compHasThreeInDiag(String[][] board) {}
private static boolean tie(String[][] board) {}

You created separated methods for the player and the computer doing the same thing while computer is also a player and the only difference between human player and computer is that one use X and the other use O. You can rewrite your methods to check if there is a winner in this way:

private final static String[] THREE_X = {"X", "X", "X"};
private final static String[] THREE_O = {"O", "O", "O"};
    
private static boolean areThreeInRow(String[][] board, String s) {
    String[] threeOfS = s.equals("X") ? THREE_X : THREE_O; 
        
    return IntStream.range(0, 3)
            .mapToObj(i -> board[i])
            .anyMatch(row -> Arrays.equals(row, threeOfS));
}
    
private static boolean areThreeInColumn(String[][] board, String s) {
    String[] threeOfS = s.equals("X") ? THREE_X : THREE_O;
        
    return IntStream.range(0, 3)
            .mapToObj(j -> new String[] {board[0][j], board[1][j], board[2][j]})
            .anyMatch(column -> Arrays.equals(column, threeOfS));
}
    
private static boolean areThreeInDiagonal(String[][] board, String s) {
   String[] threeOfS = s.equals("X") ? THREE_X : THREE_O;
   String[] main = { board[0][0], board[1][1], board[2][2]};        
   String[] secondary = { board[0][2], board[1][1], board[2][0]};
       
   return Arrays.equals(main, threeOfS) || Arrays.equals(secondary, threeOfS);
}
    
private static boolean isTie(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;
}

I had created two static arrays THREE_X and THREE_O so if one of them is present on the board the match ends with a winner. I decided to add to the signature of the methods the parameter s representing the symbol (X or O) the player adopted. I decided to use the IntStream class and the function anyMatch to check if someone of the rows or the columns contains three equal symbols independently from the fact you are checking if human player or computer is the winner, passing from 7 different methods to only 4.

I rewrite the methods playerWon and compWon in this way:

private static boolean symbolWon(String[][] board, String symbol) {
    return areThreeInColumn(board, symbol)   ||
           areThreeInDiagonal(board, symbol) || 
           areThreeInRow(board, symbol);
}

private static boolean playerWon(String[][] board) {
    String symbol = "X";
    
    return symbolWon(board, symbol);
}
    
private static boolean compWon(String[][] board) {
    String symbol = "O";
        
    return symbolWon(board, symbol);
}

You can choose to modify these methods passing the symbol assigned to human player and computer.

Minor changes: you have to close the Scanner resource to avoid memory leak : use the try with resources statement. The followind code :

public static void main(String[] args) {
    go();
}

It is correct and reminds to python, but it would better directly include the Scanner and its code inside the main .