## 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:
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; } } ```

1. Whats about Minimax or Alpha-Beta search?

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

2. wow this is crack

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

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

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

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;
}