Tutorials‎ > ‎

[Java] Tic Tac Toe AI with Minimax Tree and Alpha Beta Pruning

posted Oct 28, 2016, 3:53 AM by Denny Angkasa   [ updated Dec 5, 2016, 6:54 PM by Surya Wang ]

Introduction

Tic Tac Toe is a game where players take turns marking spaces in a 3x3 grid with their own symbol, either X or O. It is however, a flawed game in the meaning that when both players do not make a mistake, the game will for sure lead to a draw. In that case, it is possible to create an AI to play the game where it will never lose, only knowing how to win or draw the game. We will create the game and the AI in Java, console based.

Node Class

Node class is used to represent a node in the Minimax Tree. The board variable represents the current state of the board in the node. The nextPlayer variable represents the next player taking the turn. The parent variable represents the parent of the current node in the tree. The heuristic value represents the estimated value of the move of the node. The atDepth variable ensures that we only take a possible next move from atDepth == 1 (next move for the node). The traversalDepth variable represents the depth of the node in the tree.

public class Node {

String[][] board;
String nextPlayer;
Node parent;
int heuristicValue = 0;
int atDepth = 0;
int traversalDepth = 0;
public Node(){
board = new String[3][3];
parent = null;
}
public Node(String[][] board, Node parent, int heuristicValue, int atDepth, String nextPlayer, int traversalDepth){
this.board = board;
this.parent = parent;
this.heuristicValue = heuristicValue;
this.atDepth = atDepth;
this.nextPlayer = nextPlayer;
this.traversalDepth = traversalDepth;
}
}

Starting the game

We create a root node. A root node is the state of the board when the game begins (clean board). We start the game by asking if the player wants to move first. After this we’ll look at how to perform a move for the player.

int getIntInput()
{
    int i = -1;
    try{
        i = scanner.nextInt();
        scanner.nextLine();
    }catch(Exception e){
        scanner.nextLine();
    }
    
    return i;
}

boolean isPlayerMovingFirst(Node node)
{
    printBoard(node);
    String input = "";
    
    do
    {
        System.out.println("Do you want to move first? [y/n] ['e' to exit]: ");
        input = scanner.nextLine();
        
        if(input.equalsIgnoreCase("e"))
            System.exit(0);
    }while(!input.equalsIgnoreCase("y") && !input.equalsIgnoreCase("n"));
    
    if(input.equalsIgnoreCase("y"))
        return true;
    
    return false;
}

void startGame()
{
    Node root = new Node();
    clear();
    
    boolean playerMovesFirst = isPlayerMovingFirst(root);
    if(playerMovesFirst)
    {
        root.nextPlayer = "O";
        moveForPlayer(root);
    }
    else
    {
        root.nextPlayer = "X";
        moveForBot(root);
    }
}

public Main(){
    while(true){
        startGame();
        scanner.nextLine();
    }
}

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

Player’s move

To do a move for the player, we ask the player where they want to move. Then we have to validate if that move is valid. A move is valid if it is inside the board, and the place where the move will be placed in the board is not occupied. If the move is indeed valid, we produce a new node which is the successor of the previous node with the move the player just made. This new node with updated game state is then passed into the moveForBot function so that the bot can move. The bot will then produce a new successor node too and pass it to moveForPlayer function. This cycle will continue until the game ends in either the bot’s win or the bot’s draw, because apparently this bot cannot lose.


ArrayList<Point> getAvailableMoves(Node node)
{
    ArrayList<Point> availableMoves = new ArrayList<Point>();
    for(int i = 0; i<3; i++)
    {
        for(int j = 0; j<3; j++)
        {
            if(node.board[i][j] == null)
            {
                availableMoves.add(new Point(j, i));
            }
        }
    }
    
    return availableMoves;
}

Node getSuccessor(Node node, Point p) {
    
    if(isLeafNode(node)) return null;
    
    return new Node(updateBoard(node, p), node, evaluateHeuristicValue(node), node.atDepth+1, node.nextPlayer.equals("X") ? "O" : "X", node.traversalDepth+1);
}

void printBoard(Node node){
    String board[][] = node.board;
    
    clear();
    System.out.println("==========================");
    System.out.println("| Impossible Tic-Tac Toe |");
    System.out.println("==========================");
    
    System.out.println("-----------");
    System.out.println("|y\\x| 0 | 1 | 2 |");
    
    for(int i = 0; i<3; i++)
    {
        System.out.println("-----------");
        System.out.print("| " + i + " ");
        for(int j = 0; j<3; j++)
        {
            System.out.print("| ");
            if(board[i][j] != null)
                System.out.print(board[i][j]);
            else
                System.out.print(" ");
            System.out.print(" ");
        }
        System.out.println("|");
    }
    System.out.println("-----------");
}

void moveForPlayer(Node node)
{
    Node newNode = new Node();
    ArrayList<Point> availableMoves = getAvailableMoves(node);
    Point input = getInputFromPlayer(node, availableMoves);
    newNode = getSuccessor(node, input);
    
    printBoard(newNode);
    System.out.println("Computer's turn, press enter to continue");
    
    if(checkWin(newNode))
    {
        System.out.println("You Won! Press enter to play again");
    }
    else if(isLeafNode(newNode))
    {
        System.out.println("Draw Game! Press enter to play again");
    }
    else
    {
        scanner.nextLine();
        moveForBot(newNode);
    }
}

Point getInputFromPlayer(Node node, ArrayList<Point> availableMoves)
{
    Point move = new Point();
    do
    {
        int inputX, inputY;
        
        do
        {
            System.out.print("Input X: [0-2]: ");
            inputX = getIntInput();
        }while(inputX < 0 || inputX > 2);
        
        do
        {
            System.out.print("Input Y: [0-2]: ");
            inputY = getIntInput();
        }while(inputY < 0 || inputY > 2);
        
        move.x = inputX;
        move.y = inputY;
        
        if(!isValidMove(move, availableMoves))
            System.out.println("Your move is invalid!");
        
    }while(!isValidMove(move, availableMoves));
    
    return move;
}

Checking if the game has been won by a player or drawn

A player wins the game if he has 3 consecutive symbols in the board either vertically, horizontally, or diagonally. If a node is a leaf node, that means the next player has no possible moves left in the board (board is full), meaning the game ends in a draw.

boolean isLeafNode(Node node){
    return checkWin(node) || getAvailableMoves(node).size() == 0;
}

boolean checkWin(Node node){
    return checkWinRow(node) || checkWinColumn(node) || checkWinDiagonal(node);
}

boolean checkWinRow(Node node){
    
    String[][] board = node.board;
    return (board[0][0] != null && board[0][0] == board[0][1] && board[0][1] == board[0][2]) ||
            (board[1][0] != null && board[1][0] == board[1][1] && board[1][1] == board[1][2]) ||
            (board[2][0] != null && board[2][0] == board[2][1] && board[2][1] == board[2][2]);
}

boolean checkWinColumn(Node node){
    
    String[][] board = node.board;
    return (board[0][0] != null && board[0][0] == board[1][0] && board[1][0] == board[2][0]) ||
            (board[0][1] != null && board[0][1] == board[1][1] && board[1][1] == board[2][1]) ||
            (board[0][2] != null && board[0][2] == board[1][2] && board[1][2] == board[2][2]);
}

boolean checkWinDiagonal(Node node){
    
    String[][] board = node.board;
    return (board[0][0] != null && board[0][0] == board[1][1] && board[1][1] == board[2][2]) ||
            (board[0][2] != null && board[0][2] == board[1][1] && board[1][1] == board[2][0]);
}

The Minimax Tree and Alpha Beta Pruning algorithm

Minimax tree is a tree in which it represents 2 players. It alternates the represented player in each depth. For examples depth 1 represents player, depth 2 represents the bot, depth 3 represents the player, depth 4 represents the bot, and so on. It assumes that each player wants to take the move that is best for them. It will predict a certain number of turns ahead, so that it can produce a move that is an evaluation of the moves the player will take. The algorithm will take the best possible move to ensure that the player does not win the game. It evaluates which move is the best by their heuristic values. For examples a bad move in which player wins has the heuristic value of -1, meaning the bot must not take this move while a good move in which the bot prevents the player from winning (reaching 3 consecutive symbols) has the heuristic value of 1.

Then comes the alpha beta pruning implementation. As I explained in the paragraph above, the bot predicts a certain number of turns ahead, until either the MAX_TRAVERSAL_DEPTH is reached, or it reaches a leaf node. However, when a node already has a bad move in which for example it allows the player to win, we actually do not need to further evaluate the successor of this node since the bot will never take this move. Another case is that the move that has been evaluated is better than the move we are going to evaluate next. Alpha beta pruning allows us to prune the moves that we will not need to evaluate, optimizing the minimax tree algorithm. Below will be given the full code of the game.

The full code

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;


public class Main {
public static final int INFINITY = 99999;
public static final int MAX_TRAVERSAL_DEPTH = 6;
Scanner scanner = new Scanner(System.in);
int getIntInput()
{
int i = -1;
try{
i = scanner.nextInt();
scanner.nextLine();
}catch(Exception e){
scanner.nextLine();
}
return i;
}
void clear()
{
for(int i = 0; i<25; i++)
System.out.println();
}
public Main(){
while(true){
startGame();
scanner.nextLine();
}
}
void startGame()
{
Node root = new Node();
clear();
boolean playerMovesFirst = isPlayerMovingFirst(root);
if(playerMovesFirst)
{
root.nextPlayer = "O";
moveForPlayer(root);
}
else
{
root.nextPlayer = "X";
moveForBot(root);
}
}
boolean isPlayerMovingFirst(Node node)
{
printBoard(node);
String input = "";
do
{
System.out.println("Do you want to move first? [y/n] ['e' to exit]: ");
input = scanner.nextLine();
if(input.equalsIgnoreCase("e"))
System.exit(0);
}while(!input.equalsIgnoreCase("y") && !input.equalsIgnoreCase("n"));
if(input.equalsIgnoreCase("y"))
return true;
return false;
}
void moveForPlayer(Node node)
{
Node newNode = new Node();
ArrayList<Point> availableMoves = getAvailableMoves(node);
Point input = getInputFromPlayer(node, availableMoves);
newNode = getSuccessor(node, input);
printBoard(newNode);
System.out.println("Computer's turn, press enter to continue");
if(checkWin(newNode))
{
System.out.println("You Won! Press enter to play again");
}
else if(isLeafNode(newNode))
{
System.out.println("Draw Game! Press enter to play again");
}
else
{
scanner.nextLine();
moveForBot(newNode);
}
}
Point getInputFromPlayer(Node node, ArrayList<Point> availableMoves)
{
Point move = new Point();
do
{
int inputX, inputY;
do
{
System.out.print("Input X: [0-2]: ");
inputX = getIntInput();
}while(inputX < 0 || inputX > 2);
do
{
System.out.print("Input Y: [0-2]: ");
inputY = getIntInput();
}while(inputY < 0 || inputY > 2);
move.x = inputX;
move.y = inputY;
if(!isValidMove(move, availableMoves))
System.out.println("Your move is invalid!");
}while(!isValidMove(move, availableMoves));
return move;
}
boolean isLeafNode(Node node){
return checkWin(node) || getAvailableMoves(node).size() == 0;
}
boolean checkWin(Node node){
return checkWinRow(node) || checkWinColumn(node) || checkWinDiagonal(node);
}
boolean checkWinRow(Node node){
String[][] board = node.board;
return (board[0][0] != null && board[0][0] == board[0][1] && board[0][1] == board[0][2]) ||
(board[1][0] != null && board[1][0] == board[1][1] && board[1][1] == board[1][2]) ||
(board[2][0] != null && board[2][0] == board[2][1] && board[2][1] == board[2][2]);
}
boolean checkWinColumn(Node node){
String[][] board = node.board;
return (board[0][0] != null && board[0][0] == board[1][0] && board[1][0] == board[2][0]) ||
(board[0][1] != null && board[0][1] == board[1][1] && board[1][1] == board[2][1]) ||
(board[0][2] != null && board[0][2] == board[1][2] && board[1][2] == board[2][2]);
}
boolean checkWinDiagonal(Node node){
String[][] board = node.board;
return (board[0][0] != null && board[0][0] == board[1][1] && board[1][1] == board[2][2]) ||
(board[0][2] != null && board[0][2] == board[1][1] && board[1][1] == board[2][0]);
}
boolean isValidMove(Point move, ArrayList<Point> availableMoves)
{
for(int i = 0; i<availableMoves.size(); i++)
{
Point curr = availableMoves.get(i);
if(move.x == curr.x && move.y == curr.y)
return true;
}
return false;
}
void moveForBot(Node node)
{
Node newNode = new Node();
newNode.board = node.board;
newNode.nextPlayer = "X";
newNode = nextMove(newNode);
printBoard(newNode);
System.out.println("Your turn, press enter to continue");
if(checkWin(newNode))
{
System.out.println("You lost! Press enter to play again");
}
else if(isLeafNode(newNode))
{
System.out.println("Draw Game! Press enter to play again");
}
else
{
scanner.nextLine();
moveForPlayer(newNode);
}
}
Node nextMove(Node node){
getMiniMaxAlphaBeta(node, getAlpha(node), getBeta(node));
Node newNode = getMaxNodeFromPossibleMoves();
possibleNextMoves.clear();
return newNode;
}
Node getMaxNodeFromPossibleMoves()
{
Node maxNode = possibleNextMoves.get(0);
for(int i = 0, l = possibleNextMoves.size(); i<l; i++)
{
if(maxNode.heuristicValue < possibleNextMoves.get(i).heuristicValue)
{
maxNode = possibleNextMoves.get(i);
}
}
return maxNode;
}
int getMiniMaxAlphaBeta(Node node, int alpha, int beta)
{
if(isLeafNode(node) || node.traversalDepth >= MAX_TRAVERSAL_DEPTH)
return miniMaxLeafNode(node);
else if(node.nextPlayer.equals("O"))
return minimaxAlphaBetaForMinimizer(node, alpha, beta);
else
return minimaxAlphaBetaForMaximizer(node, alpha, beta);
}
int minimaxAlphaBetaForMinimizer(Node node, int alpha, int beta)
{
ArrayList<Node> allSuccessors = getAllSuccessors(node);
for(int i = 0, l = allSuccessors.size(); i<l; i++)
{
Node s = allSuccessors.get(i);
int currMin = getMiniMaxAlphaBeta(s, alpha, beta);
beta = Math.min(beta, currMin);
node.heuristicValue = Math.min(node.heuristicValue, beta);
if(alpha >= beta)
break;
}
if(possibleNextMoves(node) != null)
possibleNextMoves.add(node);
return beta;
}
int minimaxAlphaBetaForMaximizer(Node node, int alpha, int beta)
{
ArrayList<Node> allSuccessors = getAllSuccessors(node);
for(int i = 0, l = allSuccessors.size(); i<l; i++)
{
Node s = allSuccessors.get(i);
int currMax = getMiniMaxAlphaBeta(s, alpha, beta);
alpha = Math.max(alpha, currMax);
node.heuristicValue = Math.max(node.heuristicValue, alpha);
if(alpha >= beta)
break;
}
if(possibleNextMoves(node) != null)
possibleNextMoves.add(node);
return alpha;
}
int getAlpha(Node node)
{
if(isLeafNode(node))
return evaluateHeuristicValue(node);
return -INFINITY;
}
int getBeta(Node node)
{
if(isLeafNode(node))
return evaluateHeuristicValue(node);
return INFINITY;
}
ArrayList<Node> possibleNextMoves = new ArrayList<Node>();
int miniMaxLeafNode(Node node)
{
if(possibleNextMoves(node) != null)
possibleNextMoves.add(node);
return evaluateHeuristicValue(node);
}
ArrayList<Node> getAllSuccessors(Node node)
{
ArrayList<Node> successors = new ArrayList<Node>();
ArrayList<Point> availableMoves = getAvailableMoves(node);
for(int i = 0, l = availableMoves.size(); i<l; i++)
{
successors.add(getSuccessor(node, availableMoves.get(i)));
}
return successors;
}
Node possibleNextMoves(Node node){
if(node.atDepth == 1)
return node;
else
return null;
}
ArrayList<Point> getAvailableMoves(Node node)
{
ArrayList<Point> availableMoves = new ArrayList<Point>();
for(int i = 0; i<3; i++)
{
for(int j = 0; j<3; j++)
{
if(node.board[i][j] == null)
{
availableMoves.add(new Point(j, i));
}
}
}
return availableMoves;
}
Node getSuccessor(Node node, Point p) {
if(isLeafNode(node)) return null;
return new Node(updateBoard(node, p), node, evaluateHeuristicValue(node), node.atDepth+1, node.nextPlayer.equals("X") ? "O" : "X", node.traversalDepth+1);
}
int evaluateHeuristicValue(Node node)
{
if(node.nextPlayer == "X" && this.checkWin(node)==true) return -1;
if(node.nextPlayer == "O" && this.checkWin(node)==true) return 1;
return 0;
}
String[][] updateBoard(Node node, Point p) {
String[][] newBoard = copyBoard(node.board);
newBoard[p.y][p.x] = node.nextPlayer;
return newBoard;
}
String[][] copyBoard(String[][] aBoard) {
int boardSize = aBoard.length;
String[][] newBoard = new String[boardSize][boardSize];
for(int row = 0; row < boardSize; row++) {
for(int column = 0; column < boardSize; column++) 
newBoard[row][column] = aBoard[row][column];
}
return newBoard;
}
void printBoard(Node node){
String board[][] = node.board;
clear();
System.out.println("==========================");
System.out.println("| Impossible Tic-Tac Toe |");
System.out.println("==========================");
System.out.println("-----------");
System.out.println("|y\\x| 0 | 1 | 2 |");
for(int i = 0; i<3; i++)
{
System.out.println("-----------");
System.out.print("| " + i + " ");
for(int j = 0; j<3; j++)
{
System.out.print("| ");
if(board[i][j] != null)
System.out.print(board[i][j]);
else
System.out.print(" ");
System.out.print(" ");
}
System.out.println("|");
}
System.out.println("-----------");
}
public static void main(String[] args) {
new Main();
}
}

Comments