Monday, December 29, 2008

How To Create Tic Tac Toe AI (Java)


Please also check this

TicTacToe 7x7 (NEW)

TicTacToe Minimax Algorithm (NEW)

 


What is TicTacToe ?

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, hugs and kisses, and many other names, is a pencil-and-paper game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first. (source: http://en.wikipedia.org/wiki/Tic-Tac-Toe)

Now I will present a simple code to create Tic Tac Toe AI.


I will create one java file: TicTacToeAI.java

The Variable


1
2
3
4
5
6
7
8
  /* the board */
    private int board[][];    
    /* empty */
    public static final int EMPTY = 0;
    /* player one */
    public static final int ONE = 1;
    /* player two */
    public static final int TWO = 2;   


Simple Constructor
it will initialize all value in board to 0.

1
2
3
    public TicTacToeAI() {
        board = new int[3][3];
    }


Method

if position (i,j) is outside the boundary it will return EMPTY


1
2
3
4
5
6
    /* get the board value for position (i,j) */
    public int getBoardValue(int i,int j) {
        if(i < 0 || i >= 3) return EMPTY;
        if(j < 0 || j >= 3) return EMPTY;
        return board[i][j];
    }


My winning move definition is one single move that lead to victory.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    /* calculate the winning move for current token */
    public int []nextWinningMove(int token) {
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)            
                if(getBoardValue(i, j)==EMPTY) {
                    board[i][j] = token;
                    boolean win = isWin(token);
                    board[i][j] = EMPTY;
                    if(win) return new int[]{i,j};
                }
        return null;
    }


I calculate the best move based on this priority:
1. lead to win
2. prevent enemy to win
3. center position
4. first available position

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    /* calculate the best move for current token */
    public int []nextMove(int token) {
                
        /* if we can move on the next turn */
        int winMove[] = nextWinningMove(token);
        if(winMove!=null) return winMove;

        /* choose the move that prevent enemy to win */
        for(int i=0;i<3;i++) 
            for(int j=0;j<3;j++)
                if(getBoardValue(i, j)==EMPTY)
                {
                    board[i][j] = token;
            boolean ok = nextWinningMove(token==ONE ? TWO : ONE ) == null;                    
                    board[i][j] = EMPTY;
                    if(ok) return new int[]{i,j};
                }
        
        /* lucky position in the center of board*/
        if(getBoardValue(1, 1)==EMPTY) return new int[]{1,1};
        
        /* choose available move */
        for(int i=0;i<3;i++) 
            for(int j=0;j<3;j++)
                if(getBoardValue(i, j)==EMPTY)
                    return new int[]{i,j};
        
        /* no move is available */
        return null;
    }



    /* determine if current token is win or not win */
    public boolean isWin(int token) {
        final int DI[]={-1,0,1,1};
        final int DJ[]={1,1,1,0};
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) {    
                
                /* we skip if the token in position(i,j) not equal current token */
                if(getBoardValue(i, j)!=token) continue;
                
                for(int k=0;k<4;k++) {
                    int ctr = 0;
                while(getBoardValue(i+DI[k]*ctr, j+DJ[k]*ctr)==token) ctr++;
                    if(ctr==3) return true;
                }
            }
        return false;
    }
}

8 comments:

  1. Whats about Minimax or Alpha-Beta search?

    ReplyDelete
    Replies
    1. https://algojava.blogspot.co.id/2017/01/tictactoe-ai-with-minimax-algorithm.html

      Delete
  2. wow this is crack

    ReplyDelete
  3. I tried Tic tac toe using minimax algorithm
    http://themakeinfo.com/2015/02/ai-based-tic-tac-toe-in-java/

    ReplyDelete
  4. final int DI[]={-1,0,1,1}; final int DJ[]={1,1,1,0};
    What does it mean?can u please explain me?

    ReplyDelete
  5. It's incremental value for row and column.
    -1 and 1 = north-east
    0 and 1 = east
    1 and 1 = south-east
    1 and 0 = south

    ReplyDelete
  6. yo dude please please please reply to me, ill love you! how does this part of the code work i dont understand can you just explain it to me? Thanks!!!!

    public boolean isWin(int token) {
    // It's incremental value for row and column. e.g. -1 and 1 = north-east
    final int DI[]={-1,0,1,1}; //row
    final int DJ[]={1,1,1,0}; // column
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++) {

    /* we skip if the token in position(i,j) not equal current token */
    if(getBoardValue(i, j)!=token) continue;

    for(int k=0;k<4;k++) {
    int ctr = 0;
    while(getBoardValue(i+DI[k]*ctr, j+DJ[k]*ctr)==token) ctr++;
    if(ctr==3) return true;
    }
    }
    return false;
    }

    ReplyDelete