Monday, August 25, 2014

Minimax Algorithm Tic Tac Toe AI In Java [Minimax][Full tree Search][Artificial Intelligence][Java]

The minimax tree has leaf values like -1 0 or 1. Min selects the minimum i.e. -1. Max selects the maximum among the available after Min would have taken its move. i.e. 0 or 1. So it has available moves like -1, -1, 0, 0, +1, +1 at the top most node (root, which is the present game state) and selects the first +1 value as it has a chance of victory no matter what other opponent does (it has already been calculated like if the opponent does this, I can do this (it always assumes the opponent takes the smartest move to destroy you) and I can win). There is no summation of values taking place like +3, +4, +1 so that max selects +3 and like that. This kind of approach is used in other implementation where you don't have the time to evaluate the whole tree and just want to evaluate the tree at the (say 4th) level and then rank the states accordingly like I have 3 rows in which I can get 3 Xs so that gives a score +1000, 2 rows = +100 and 1 row = +10. -ve values for the opponents position. So you get values like +1200 or -2300 at the leaves from where you select the move which is favorable (this player is not perfect, it can lose. It has not evaluated all the possibilites. It has just gone to some extent of computation to get some available move in some limited time).

This AI is a perfect player i.e. it can never lose. It wins or it draws the match.

Source: The code isn't really hard. Function names are self explanatory. Comments are added wherever necessary. I've supposed that 2 is the human player playing the game and 1 is the computer. If you want to see the actual calculations, just uncomment the commented lines.

[Make sure you have JDK 8.0 Installed] If not, here's a link: http://www.oracle.com/technetwork/java/javase/downloads/jre8-downloads-2133155.html

import java.util.*;

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointsAndScores {

    int score;
    Point point;

    PointsAndScores(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

class Board {
 
    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3];

    public Board() {
    }

    public boolean isGameOver() {
        //Game is over is someone has won, or board is full (draw)
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            //System.out.println("X Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                // System.out.println("X Row or Column win");
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            // System.out.println("O Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                //  System.out.println("O Row or Column win");
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    }

    public Point returnBestMove() {
        int MAX = -100000;
        int best = -1;

        for (int i = 0; i < rootsChildrenScores.size(); ++i) { 
            if (MAX < rootsChildrenScores.get(i).score) {
                MAX = rootsChildrenScores.get(i).score;
                best = i;
            }
        }

        return rootsChildrenScores.get(best).point;
    }

    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2); 
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    }

    public int returnMin(List<Integer> list) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < list.size(); ++i) {
            if (list.get(i) < min) {
                min = list.get(i);
                index = i;
            }
        }
        return list.get(index);
    }

    public int returnMax(List<Integer> list) {
        int max = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < list.size(); ++i) {
            if (list.get(i) > max) {
                max = list.get(i);
                index = i;
            }
        }
        return list.get(index);
    }

    List<PointsAndScores> rootsChildrenScores;
 
    public void callMinimax(int depth, int turn){
        rootsChildrenScores = new ArrayList<>();
        minimax(depth, turn);
    }
    
    public int minimax(int depth, int turn) {

        if (hasXWon()) return +1;
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 

        List<Integer> scores = new ArrayList<>(); 

        for (int i = 0; i < pointsAvailable.size(); ++i) {
            Point point = pointsAvailable.get(i);  

            if (turn == 1) { //X's turn select the highest from below minimax() call
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                scores.add(currentScore);

                if (depth == 0) 
                    rootsChildrenScores.add(new PointsAndScores(currentScore, point));
                
            } else if (turn == 2) {//O's turn select the lowest from below minimax() call
                placeAMove(point, 2); 
                scores.add(minimax(depth + 1, 1));
            }
            board[point.x][point.y] = 0; //Reset this point
        }
        return turn == 1 ? returnMax(scores) : returnMin(scores);
    }
}

public class TicTacToe {

    public static void main(String[] args) {
        Board b = new Board();
        Random rand = new Random();
        
        b.displayBoard();

        System.out.println("Who's gonna move first? (1)Computer (2)User: ");
        int choice = b.scan.nextInt();
        if(choice == 1){
            Point p = new Point(rand.nextInt(3), rand.nextInt(3));
            b.placeAMove(p, 1);
            b.displayBoard();
        }
        
        while (!b.isGameOver()) {
            System.out.println("Your move: ");
            Point userMove = new Point(b.scan.nextInt(), b.scan.nextInt());

            b.placeAMove(userMove, 2); //2 for O and O is the user
            b.displayBoard();
            if (b.isGameOver()) {
                break;
            } 
            b.callMinimax(0, 1);
            for (PointsAndScores pas : b.rootsChildrenScores) {
                System.out.println("Point: " + pas.point + " Score: " + pas.score);
            }
            b.placeAMove(b.returnBestMove(), 1);
            b.displayBoard();
        }
        if (b.hasXWon()) {
            System.out.println("Unfortunately, you lost!");
        } else if (b.hasOWon()) {
            System.out.println("You win! This is not going to get printed.");
        } else {
            System.out.println("It's a draw!");
        }
    }
}

Sample run:

0 0 0
0 0 0
0 0 0
Who's gonna move first? (1)Computer (2)User:
2
Your move:
2 2

0 0 0
0 0 0
0 0 2
Point: [0, 0] Score: -1
Point: [0, 1] Score: -1
Point: [0, 2] Score: -1
Point: [1, 0] Score: -1
Point: [1, 1] Score: 0
Point: [1, 2] Score: -1
Point: [2, 0] Score: -1
Point: [2, 1] Score: -1

0 0 0
0 1 0
0 0 2
Your move:
0 0

2 0 0
0 1 0
0 0 2
Point: [0, 1] Score: 0
Point: [0, 2] Score: -1
Point: [1, 0] Score: 0
Point: [1, 2] Score: 0
Point: [2, 0] Score: -1
Point: [2, 1] Score: 0

2 1 0
0 1 0
0 0 2
Your move:
2 1

2 1 0
0 1 0
0 2 2
Point: [0, 2] Score: -1
Point: [1, 0] Score: -1
Point: [1, 2] Score: -1
Point: [2, 0] Score: 0

2 1 0
0 1 0
1 2 2
Your move:
0 2

2 1 2
0 1 0
1 2 2
Point: [1, 0] Score: -1
Point: [1, 2] Score: 0

2 1 2
0 1 1
1 2 2
Your move:
1 0

2 1 2
2 1 1
1 2 2
It's a draw!

Update:
Here is an improved version. We don't need to evaluate more when we already have found a winning move, so we just skip rest of the evaluations as soon as we get +1 (for max) or -1 (for min) for some state for the next move.

Source:


import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointAndScore {

    int score;
    Point point;

    PointAndScore(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

class Board {
 
    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3];

    public Board() {
    }

    public boolean isGameOver() {
        //Game is over is someone has won, or board is full (draw)
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            //System.out.println("X Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                // System.out.println("X Row or Column win");
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            // System.out.println("O Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                //  System.out.println("O Row or Column win");
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    } 
    
    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2); 
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    } 
    
    Point computersMove; 
    
    public int minimax(int depth, int turn) {  
        if (hasXWon()) return +1; 
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 
 
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
         
        for (int i = 0; i < pointsAvailable.size(); ++i) {  
            Point point = pointsAvailable.get(i);   
            if (turn == 1) { 
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                max = Math.max(currentScore, max);
                
                if(depth == 0)System.out.println("Score for position "+(i+1)+" = "+currentScore);
                if(currentScore >= 0){ if(depth == 0) computersMove = point;} 
                if(currentScore == 1){board[point.x][point.y] = 0; break;} 
                if(i == pointsAvailable.size()-1 && max < 0){if(depth == 0)computersMove = point;}
            } else if (turn == 2) {
                placeAMove(point, 2); 
                int currentScore = minimax(depth + 1, 1);
                min = Math.min(currentScore, min); 
                if(min == -1){board[point.x][point.y] = 0; break;}
            }
            board[point.x][point.y] = 0; //Reset this point
        } 
        return turn == 1?max:min;
    }  
}

public class TicTacToe {

    public static void main(String[] args) {
        Board b = new Board();
        Random rand = new Random();
        
        b.displayBoard();

        System.out.println("Select turn:\n\n1. Computer 2. User: ");
        int choice = b.scan.nextInt();
        if(choice == 1){
            Point p = new Point(rand.nextInt(3), rand.nextInt(3));
            b.placeAMove(p, 1);
            b.displayBoard();
        }
        
        while (!b.isGameOver()) {
            System.out.println("Your move: ");
            Point userMove = new Point(b.scan.nextInt(), b.scan.nextInt());

            b.placeAMove(userMove, 2); //2 for O and O is the user
            b.displayBoard();
            if (b.isGameOver()) break;
            
            b.minimax(0, 1);  
            
            b.placeAMove(b.computersMove, 1);
            b.displayBoard();
        }
        if (b.hasXWon()) 
            System.out.println("Unfortunately, you lost!");
        else if (b.hasOWon()) 
            System.out.println("You win!"); //Can't happen
        else 
            System.out.println("It's a draw!");
    }
}


Output: 

0 0 0
0 0 0
0 0 0
Select turn:

1. Computer 2. User:
2
Your move:
2 2

0 0 0
0 0 0
0 0 2
Score for position 1 = -1
Score for position 2 = -1
Score for position 3 = -1
Score for position 4 = -1
Score for position 5 = 0
Score for position 6 = -1
Score for position 7 = -1
Score for position 8 = -1

0 0 0
0 1 0
0 0 2
Your move:
0 0

2 0 0
0 1 0
0 0 2
Score for position 1 = 0
Score for position 2 = -1
Score for position 3 = 0
Score for position 4 = 0
Score for position 5 = -1
Score for position 6 = 0

2 0 0
0 1 0
0 1 2
Your move:
0 1

2 2 0
0 1 0
0 1 2
Score for position 1 = 0
Score for position 2 = -1
Score for position 3 = -1
Score for position 4 = -1

2 2 1
0 1 0
0 1 2
Your move:
2 0

2 2 1
0 1 0
2 1 2
Score for position 1 = 0
Score for position 2 = -1

2 2 1
1 1 0
2 1 2
Your move:
1 2

2 2 1
1 1 2
2 1 2
It's a draw!

More: 

Tic-Tac-Toe (JavaFX UI)
Minimax With Alpha-Beta Pruning (Tic-Tac-Toe)

Connect 4 AI (Minimax)
Conncet 4 AI (Minimax + Alpha-Beta Pruning)

   

13 comments:

  1. Well explained code! :)

    ReplyDelete
  2. Good one :)
    How much did it take you to code it ?

    ReplyDelete
  3. I won! //It Happened :)

    ReplyDelete
  4. how to print all state using minimax, when the board is blank? can you show that?

    ReplyDelete
  5. you have an incorrect implementation - so did i; the following are the changes. the current implementation does not maximize the chances of winning - it only makes sure you never lose! some cases it will avoid the 'easiest winning move in favor of a move to not lose'. my next post will be 'to win first, than to defend'.


    ReplyDelete
  6. apologies - that would become the maximin algorithm - i spoke too early. but during game play seems sometimes that will also be good. maximizing one's own payoff (i will try and modify - do give me few days to attempt all possibilities and then will post the code)

    ReplyDelete
  7. There are some scenarios when I nearly wins but the AI doesn't block it....

    ReplyDelete
  8. why it is not working in n*n matrix
    if we change those values of 3*3 to 4*4 , it stops working
    why so?

    ReplyDelete
  9. available state is still using a 3x3 field thats why its not working.

    ReplyDelete