public class Constants { private Constants(){ } public static final int BOARD_SIZE = 3; }
//enum Player public enum Player { //We denote: //Computer move by X //User move by O //If there is no move, by - COMPUTER("X"), USER("O"), NONE("-"); private Player(String text){ this.text = text; } private final String text; public String toString(){ return text; } }
// Representation of a cell in our 3X3 board public class Cell { private int x; //index of rows private int y; //index of columns private int minimaxValue; //-1 -> Lose, 0 -> Draw, 1 -> Win //If minimaxValue is -1, we shouldn't make our next move to this cell, opposite for 1 //Constructor public Cell(int x, int y) { this.x = x; this.y = y; } //Getters and Setters public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public int getMinimaxValue() { return minimaxValue; } public void setMinimaxValue(int score) { this.minimaxValue = score; } //Override toString method to return the current cell coordinates @Override public String toString() { return "(" + this.x + ", " + this.y + ")"; } }
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Board { private List<Cell> emptyCells; //List of cells private Scanner scanner; //Input from the user private Player[][] board; //Board private List<Cell> rootValues; //values assigned according to the Minmax algo. //Constructor public Board() { initializeBoard(); } //Initialize the Board private void initializeBoard() { this.rootValues = new ArrayList<>(); this.scanner = new Scanner(System.in); this.board = new Player[Constants.BOARD_SIZE][Constants.BOARD_SIZE]; //3X3 } //Checking condition for termination, else keep running the program public boolean isRunning() { if( isWinning(Player.COMPUTER) ) return false; //Computer has won if( isWinning(Player.USER)) return false; //User has won if( getEmptyCells().isEmpty() )return false; //Draw return true; } //Check the winning condition for comp/user public boolean isWinning(Player player) { if ( board[0][0] == player && board[1][1] == player && board[2][2] == player ) { //Diagonal has same moves X or O /* O O O */ return true; //Player has won } if( board[0][2] == player && board[1][1] == player && board[2][0] == player ){ //Diagonal has same moves X or O /* O O O */ return true; //Player has won } for (int i = 0; i < Constants.BOARD_SIZE; i++) { // Checking the rows if ( board[i][0] == player && board[i][1] == player && board[i][2] == player ) { //The row has same moves X or O /* O O O */ return true; } // Checking the columns if( board[0][i] == player && board[1][i] == player && board[2][i] == player ){ //The column has same moves X or O /* O O O */ return true; } } //else return false return false; } //If there are no player moves at a given cell, create an empty cell there public List<Cell> getEmptyCells() { emptyCells = new ArrayList<>(); for (int i = 0; i < Constants.BOARD_SIZE; ++i) { for (int j = 0; j < Constants.BOARD_SIZE; ++j) { if (board[i][j] == Player.NONE) { emptyCells.add(new Cell(i, j)); } } } return emptyCells; } //Make a move public void move(Cell point, Player player) { board[point.getX()][point.getY()] = player; } // Calculate the optimal move using Minmax algo. public Cell getBestMove() { int max = Integer.MIN_VALUE; int best = Integer.MIN_VALUE; for (int i = 0; i < rootValues.size(); ++i) { if (max < rootValues.get(i).getMinimaxValue()) { max = rootValues.get(i).getMinimaxValue(); best = i; } } return rootValues.get(best); } //Get the user's move as input public void makeUserInput() { System.out.println("User's move: "); int x = scanner.nextInt(); int y = scanner.nextInt(); Cell point = new Cell(x, y); move(point, Player.USER); //Make that move } //Display the current tictactoe board public void displayBoard() { System.out.println(); for (int i = 0; i < Constants.BOARD_SIZE; ++i) { for (int j = 0; j < Constants.BOARD_SIZE; ++j) { System.out.print(board[i][j] + " "); } System.out.println(); } } //Func that returns the minimum value public int returnMin(List<Integer> list) { int min = Integer.MAX_VALUE; int index = Integer.MIN_VALUE; for (int i = 0; i < list.size(); ++i) { if (list.get(i) < min) { min = list.get(i); index = i; } } return list.get(index); } //Func that returns the maximum value public int returnMax(List<Integer> list) { int max = Integer.MIN_VALUE; int index = Integer.MIN_VALUE; for (int i = 0; i < list.size(); ++i) { if (list.get(i) > max) { max = list.get(i); index = i; } } return list.get(index); } //Call the Minmax algo public void callMinimax(int depth, Player player){ rootValues.clear(); minimax(depth, player); } //Minmax algorithm to make decisions for the Computer public int minimax(int depth, Player player) { if (isWinning(Player.COMPUTER)) return +1; //Check if computer is winning if (isWinning(Player.USER)) return -1; //Check if user is winning List<Cell> availableCells = getEmptyCells(); //Check for available empty cells if (availableCells.isEmpty()) return 0; //The game is Drawn if there are no availableCells List<Integer> scores = new ArrayList<>(); // +1 , 0, -1 for (int i = 0; i < availableCells.size(); i++) { Cell point = availableCells.get(i); //For Computer if (player == Player.COMPUTER) { //X's turn select the highest from below minimax() call move(point, Player.COMPUTER); int currentScore = minimax(depth + 1, Player.USER); //recursive call to minmax algo //Here the game tree would be constructed scores.add(currentScore); if (depth == 0) { point.setMinimaxValue(currentScore); rootValues.add(point); } //For User } else if (player == Player.USER) {//O's turn select the lowest from below minimax() call move(point, Player.USER); scores.add(minimax(depth + 1, Player.COMPUTER)); } board[point.getX()][point.getY()] = Player.NONE; //Reset this point } if( player == Player.COMPUTER ){ return returnMax(scores); } return returnMin(scores); } public List<Cell> getAvailablePoints() { return emptyCells; } public void setAvailablePoints(List<Cell> availablePoints) { this.emptyCells = availablePoints; } //Set up the board at the start with '-' public void setupBoard() { for(int i=0;i<Constants.BOARD_SIZE;i++){ for(int j=0;j<Constants.BOARD_SIZE;j++){ board[i][j] = Player.NONE; } } } //Getters and Setters public Scanner getScanner() { return scanner; } public void setScanner(Scanner scanner) { this.scanner = scanner; } public Player[][] getBoard() { return board; } public void setBoard(Player[][] board) { this.board = board; } public List<Cell> getRootValues(){ return this.rootValues; } }
import java.util.Random; public class Game { private Board board; private Random random; //If Comp starts the game, it should start at a random cell //Constructor public Game(){ initializeGame(); displayBoard(); makeFirstMove(); playGame(); checkStatus(); } //Initialize the game private void initializeGame() { this.board = new Board(); this.board.setupBoard(); this.random = new Random(); } //Check who is winning private void checkStatus() { if (board.isWinning(Player.COMPUTER)) { System.out.println("Computer has won"); } else if (board.isWinning(Player.USER)) { System.out.println("Player has won"); } else { System.out.println("It's a draw!"); } } //Display the board private void displayBoard() { board.displayBoard(); } //Make the first move private void makeFirstMove() { //Ask the user to choose who starts. System.out.println("Who starts? 1 - Computer ; 2 - User"); int choice = board.getScanner().nextInt(); if(choice == 1){ Cell cell = new Cell(random.nextInt(Constants.BOARD_SIZE), random.nextInt(Constants.BOARD_SIZE)); board.move(cell, Player.COMPUTER); //Randomly make an initial move board.displayBoard(); } } // Main game loop private void playGame() { while ( board.isRunning() ) { //Get the user move as input System.out.println("User move: "); Cell userCell = new Cell(board.getScanner().nextInt(), board.getScanner().nextInt()); board.move(userCell, Player.USER); board.displayBoard(); if (!board.isRunning()) { break; } //Make the computer's move board.callMinimax(0, Player.COMPUTER); for (Cell cell : board.getRootValues()) { System.out.println("Cell values: " + cell + " minimaxValue: " + cell.getMinimaxValue()); } board.move(board.getBestMove(), Player.COMPUTER); board.displayBoard(); } } }
public class Main { public static void main(String[] args) { new Game(); } }
Output of the program is :
- - - - - - - - - Who starts? 1 - Computer ; 2 - User 1 - - - - - - - X - User move: 0 0 O - - - - - - X - Cell values: (0, 1) minimaxValue: -1 Cell values: (0, 2) minimaxValue: 0 Cell values: (1, 0) minimaxValue: -1 Cell values: (1, 1) minimaxValue: 0 Cell values: (1, 2) minimaxValue: -1 Cell values: (2, 0) minimaxValue: 1 Cell values: (2, 2) minimaxValue: -1 O - - - - - X X - User move: 2 2 O - - - - - X X O Cell values: (0, 1) minimaxValue: -1 Cell values: (0, 2) minimaxValue: -1 Cell values: (1, 0) minimaxValue: -1 Cell values: (1, 1) minimaxValue: 1 Cell values: (1, 2) minimaxValue: -1 O - - - X - X X O User move: 0 1 O O - - X - X X O Cell values: (0, 2) minimaxValue: 1 Cell values: (1, 0) minimaxValue: -1 Cell values: (1, 2) minimaxValue: -1 O O X - X - X X O Computer has won