#Artificial Intelligence

Tic Tac Toe Puzzle : An Artificially Intelligent Approach Using Min-Max Algorithm

I really enjoyed coding this animated game with my project partner Yulia. You can post your questions if  any clarification required.
--------------------------------------------------------------
The Heuristic for Min-Max Game Strategy :


 Return difference between winning options for X and winning options for O,
 E(P) = N(X) - N(O)
 check every row, column and diagonal for winning option
 accumulate total score for each player and find the difference
 if there are any X and O on the same row/column/diagonal - score = 0
 if there are 2 X/O (depends on player) - score increased on 100
 if there are 3 X/O (depends on player) - score increadsed on 1000

---------------------------------------------------------------

First File : TicTacToeHelper.Java


package game;

import java.util.ArrayList;



public class TicTacToeHelper {

public int current_score;
public int cntX;
public int cntO;
public int scoreX;
public int scoreO;
public static final Integer[] row1 = { 0, 1, 2 };
public static final Integer[] row2 = { 3, 4, 5 };
public static final Integer[] row3 = { 6, 7, 8 };
public static final Integer[] column1 = { 0, 3, 6 };
public static final Integer[] column2 = { 1, 4, 7 };
public static final Integer[] column3 = { 2, 5, 8 };
public static final Integer[] diagonal1 = { 0, 4, 8 };
public static final Integer[] diagonal2 = { 6, 4, 2 };

/*
* return difference between winning options for X and winning options for O
* E(P) = N(X) - N(O)
* check every row, column and diagonal for winning option
* accumulate total score for each player and find the difference
* if there are any X and O on the same row/column/diagonal - score = 0
* if there are 2 X/O (depends on player) - score increased on 100
* if there are 3 X/O (depends on player) - score increadsed on 1000
*
*/
public int heuristic_score(ArrayList<Integer> boardcopy) {

// get score E = N(X) - N(O)
scoreX = 0;
scoreO = 0;

//check row1
cntX =  get_score(boardcopy, row1, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, row1, 2);
scoreO = scoreO + cntO;

//check row2
cntX =  get_score(boardcopy, row2, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, row2, 2);
scoreO = scoreO + cntO;

//check row3
cntX =  get_score(boardcopy, row3, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, row3, 2);
scoreO = scoreO + cntO;

//check column1
cntX =  get_score(boardcopy, column1, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, column1, 2);
scoreO = scoreO + cntO;

//check column2
cntX =  get_score(boardcopy, column2, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, column2, 2);
scoreO = scoreO + cntO;

//check column3
cntX =  get_score(boardcopy, column3, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, column3, 2);
scoreO = scoreO + cntO;

//check diagonal1
cntX =  get_score(boardcopy, diagonal1, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, diagonal1, 2);
scoreO = scoreO + cntO;

//check diagonal2
cntX =  get_score(boardcopy, diagonal2, 1);
scoreX = scoreX + cntX;
cntO =  get_score(boardcopy, diagonal2, 2);
scoreO = scoreO + cntO;

current_score = scoreX - scoreO;
//System.out.println(" current score = "+ current_score+" : scoreX - ScoreO = "+ scoreX +" - "+scoreO  );
return current_score;
}

/*
* returns true if plaeyr has 3 X or O on row/column/diagonal,
* othervise, return false
*/

public boolean check_winner(ArrayList<Integer> boardcopy, int player)
{
int cnt = 0;
//check row1
cnt =  get_score(boardcopy, row1, player);
if(cnt>=1000)
return true;
//check row2
cnt =  get_score(boardcopy, row2, player);
if(cnt>=1000)
return true;
//check row3
cnt =  get_score(boardcopy, row3, player);
if(cnt>=1000)
return true;
//check column1
cnt =  get_score(boardcopy, column1, player);
if(cnt>=1000)
return true;
//check column2
cnt =  get_score(boardcopy, column2, player);
if(cnt>=1000)
return true;
//check column3
cnt =  get_score(boardcopy, column3, player);
if(cnt>=1000)
return true;
//check diagonal1
cnt =  get_score(boardcopy, diagonal1, player);
if(cnt>=1000)
return true;
//check diagonal2
cnt =  get_score(boardcopy, diagonal2, player);
if(cnt>=1000)
return true;


return false;
}


/*
* returns score for player(X or O) for specific row/column/diagonal
* if there are any X and O on the same row/column/diagonal - score = 0
* if there are 2 X/O (depends on player) - score = 100
* if there are 3 X/O (depends on player) - score = 1000
*
*/
public int get_score(ArrayList<Integer> arrcopy, Integer [] comp, int player)
   {
    //check any possible winner option for X and O
   // X=1; O=2;
   
  int score = 0;
    int cnt1 = 0;
    int cnt2 = 0;
    for(Integer r:comp )
    {
      if(arrcopy.get(r)==1)
      cnt1++;
       if(arrcopy.get(r)==2)
      cnt2++;
    }

   
    if(cnt1 !=0 && cnt2 != 0)
{// O and X on the same row
cnt1 = 0;
cnt2 = 0;
score = 0;

return score;
}
else  // no X and O at the same row/column/diagonal
{
if(player == 1)  // X
{
score = cnt1;
if(cnt1==2)
 score = 100;
if(cnt1==3)
 score = 1000;
}
 
if(player == 2)  // O
{
score = cnt2;
if(cnt2==2)
score = 100;
if(cnt2==3)
score = 1000;

}
}
   
    return score;
   
    }

//print board
public void print_board(ArrayList<Integer> board)
{

System.out.println("              -------");
System.out.println("              |"+board.get(0)+"|"+ board.get(1)+"|"+board.get(2)+"|");
System.out.println("              -------");
System.out.println("              |"+board.get(3)+"|"+ board.get(4)+"|"+board.get(5)+"|");
System.out.println("              -------");
System.out.println("              |"+board.get(6)+"|"+ board.get(7)+"|"+board.get(8)+"|");
System.out.println("              -------");

}

}

--------------------------------------------------------------------------

Second File : TicTacToeMinMax.Java

package game;

import java.applet.Applet;

import java.awt.Color;

import java.awt.Dimension;

import java.awt.Graphics;

import java.util.ArrayList;

/*

 *  Include My Name If you Use this Code....

 *  

 *  Max move first

 *  X - max level

 *  O - min level

 *  presentation of  X = 1

 * presentation of O = 2

 *  board presentation:

 * row1 = { 0, 1, 2 };

 * row2 = { 3, 4, 5 };

 * row3 = { 6, 7, 8 };

 * column1 = { 0, 3, 6 };

 * column2 = { 1, 4, 7 };

 * column3 = { 2, 5, 8 };

 * diagonal1 = { 0, 4, 8 };

 * diagonal2 = { 6, 4, 2 };  

 */

public class TicTacToeMinMax extends Applet {

boolean x_turn= true;

boolean o_turn;

static boolean winner = false;

int player = 1;

boolean level_min;

boolean level_max = true;

int max_depth = 3;

int min_depth = 2;

int depth;

int current_score;

int score_depth2;

int score_depth1;

int score_depth0;

int level_score;

int best_move;

int cntX;

int cntO;

int scoreX;

int scoreO;

Dimension d = new Dimension(200, 200);

ArrayList<Integer> board = new ArrayList<Integer>(9);

ArrayList<Integer> boardcopy = new ArrayList<Integer>(9);

//int[] board = new int[9];

//initialize board with alll positions 0

public TicTacToeMinMax()

{

for(int c=0; c<9; c++)

{

board.add(0);

}

}

/*

*  moveX return the best position for X using minmax algorithm and

*  go deep on 3 levels of children to bring the best move position on board for X

*  presentation: X = 1; O = 2

*  X move first

*  depth0:  Max level - current state of board - expect the best move of X  

*  depth1:  Min level - X turn: X try move to any available position on board

*  depth2:  Max level - O turn: for every possible X turn, O will try to find the best spot for O

*  depth3:  Min level - X turn: try to find the best position- block O from winning or win

*  

*           on last childrens level (depth3) calculate score for every child, select maximum score for X, percolate this score to level Max, depth 2

*           for depth1 percolate minimum of bringing scores from depth2 level, as soon as player O - minimum

*           then percolate the maximum of depth1 children to depth0 max level, since it was max level - select the biggest scored child

*           position of this child is the best move for player X         

*/

public int moveX(ArrayList<Integer> current_board)

{

TicTacToeHelper help = new TicTacToeHelper();

   level_max = true;

   player = 1;

depth  = max_depth; 

x_turn = true;

best_move = 0;

score_depth2 = 0;

score_depth1 = 0;

score_depth0 = 0;

//depth 0: initial state of board current_board; max level

int cnt0 = 0;

for(int i=0; i < 9; i++)    //current depth = 1; MIN level, X turn, player X       

{  

//for every empty spot on board check possible X position

level_score=0;

if(current_board.get(i)==0)   

{   //make a copy of current board

boardcopy.clear();

boardcopy.addAll(current_board);

boardcopy.set(i, new Integer(1));

                cnt0++;

// to get score - go level down - generate children

// for every possible move - generate children

int cnt1 = 0;

for(int k = 0; k < 9; k++)    //current depth = 2; MAX level, O turn,  O=2, player O

{

if(boardcopy.get(k)==0)

{

//possible position for O

boardcopy.set(k, new Integer(2));

cnt1++;

// to get score - go level down - generate children

// for every possible move - generate children

int cnt2 = 0;

for(int x= 0; x < 9; x++)          //current depth = 3; MIN level, X turn,  X=1, player X

{

if(boardcopy.get(x)==0)

{

//possible position for X

boardcopy.set(x, new Integer(1));

cnt2++;

// depth 3 - now get score

// get score E(P) = N(X) - N(O)

// score_depth3 = current_score

current_score = help.heuristic_score(boardcopy);  

// System.out.println("depth3: x["+x+"] = "+ current_score);

//to percolate score on next depth2 MAX level choose the biggest score - MAX

if(cnt2==1)  //first child score

score_depth2 = current_score;

else

{

if

(score_depth2 < current_score)   // bring the biggest score for X

score_depth2 = current_score;

}

// System.out.println("depth2: score for k["+k+"] = "+score_depth2);

//clear position from copy after evaluation

boardcopy.set(x, new Integer(0)); 

}

}

// keep MIN score, move to the next child node 

//to percolate score on next depth1 MIN level choose the smallest score - MIN

if(cnt1==1)  //first child score

score_depth1 = score_depth2 ;

else

{

if

(score_depth1 > score_depth2 )   // bring the smallest score for O

score_depth1 = score_depth2 ;

}

// System.out.println("depth1: score for i["+i+"] = "+score_depth1);

//clear position from copy after evaluation

boardcopy.set(k, new Integer(0)); // clear position after evaluation is done 

}

} // end of depth2

// get MAX score for X depth0

//to percolate score on next depth0 MAX level choose the biggest score - MAX

if(cnt0==1)  //first child score

{

score_depth0 = score_depth1;

best_move = i;

}

else

{

if(score_depth0 < score_depth1)   // bring the biggest score for X

{

score_depth0 = score_depth1;

best_move = i;

}

}

//System.out.println("X: depth0: score for i["+i+"] = "+score_depth0);

// removed possible position from  copy of board

boardcopy.set(i, new Integer(0));

}

 

} // end of depth1 

return best_move;  // depth0 

}

// O move-----------------------------------------------------------------------------

/*

*  moveO return the best position for O using minmax algorithm and

*  go deep on 2 levels of children to bring the best move position on board for X

*  presentation: X = 1; O = 2

*  

*  depth0:  Min level - current state of board - expect the best move of O  

*  depth1:  Max level - O turn: O try move to any available position on board

*  depth2:  Min level - X turn: X will try to find the best spot for X

*  

*           on last children level (depth2) calculate score for every child, select minimum score for O, percolate this score to level Min, depth 1

*           for depth1 percolate minimum of bringing scores from depth2 level, as soon as player O - minimum

*           then percolate the maximum of depth1 children to depth0 max level, since it was max level - select the biggest scored child

*           position of this child is the best move for player O         

*/

public int moveO(ArrayList<Integer> current_board)

{

TicTacToeHelper help = new TicTacToeHelper();

  

   player = 2;

depth  = min_depth; //2 

o_turn = true;

best_move = 0;

score_depth2 = 0;

score_depth1 = 0;

score_depth0 = 0;

//depth 0: initial state of board current_board; max level

int cnt0 = 0;

for(int i=0; i < 9; i++)    //current depth = 1; MIN level, O turn, player O       

{  

//for every empty spot on board check possible O position

level_score=0;

if(current_board.get(i)==0)   

{   //make a copy of current board

boardcopy.clear();

boardcopy.addAll(current_board);

boardcopy.set(i, new Integer(2));

                cnt0++;

// to get score - go level down - generate children

// for every possible move - generate children

int cnt1 = 0;

for(int k = 0; k < 9; k++)    //current depth = 2; MAX level, O turn,  O=2, player O

{

if(boardcopy.get(k)==0)

{

//possible position for O

boardcopy.set(k, new Integer(1));

cnt1++;

      

// get score E(P) = N(X) - N(O)

// score_depth2 = current_score

current_score = help.heuristic_score(boardcopy);  

// keep MAX score, move to the next child node 

//to percolate score on next depth1 MIN level choose the smallest score - MIN

if(cnt1==1)  //first child score

score_depth1 = current_score;

else

{

if(score_depth1 < current_score)   // bring the biggest score for X

score_depth1 = current_score;

}

//clear position from copy after evaluation

boardcopy.set(k, new Integer(0)); // clear position after evaluation is done 

}

} // end of depth2

// get MAX score for O depth0

//to percolate score on next depth0 MIN level choose the biggest score - MIN

if(cnt0==1)  //first child score

{

score_depth0 = score_depth1;

best_move = i;

}

else

{

if(score_depth0 > score_depth1)   // bring the biggest score for X

{

score_depth0 = score_depth1;

best_move = i;

}

}

//System.out.println("O: depth0: score for i["+i+"] = "+score_depth0);

// removed possible position from  copy of board

boardcopy.set(i, new Integer(0));

}

 

} // end of depth1 

return best_move;  // depth0 

} 

public void init() {

       super.init();

       setBackground(Color.white);

       //{{INIT_CONTROLS

       setLayout(null);

       resize(500,200);

       

       //}}

   }

 

public void paint(Graphics g)

   {

       

   

    TicTacToeMinMax m = new TicTacToeMinMax();

      TicTacToeHelper help = new TicTacToeHelper();

      int position = 0;

     // System.out.println("X move first .........................................");

      while(m.board.contains(0) && !winner)

      {

      int i, j;

      

    int xoff = d.width / 3;

    int yoff = d.height / 3;

    for (i = 0; i < 3; i++)

    {

       for (j = 0; j < 3; j++)

       {

               g.setColor(Color.black);

           g.drawRect(j * xoff + 2, i * yoff + 2, xoff - 4, yoff - 4);

           

       }

    }

         //max move first

    //  System.out.println("\nit is X turn now .......................................");

      position = m.moveX(m.board);

  m.board.set(position, new Integer(1));

  if(position <=2){

  i=0;

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  DrawX(g, d, i, position);

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  

  }

  else if(position>2 && position <=5){

  i=1;

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  DrawX(g, d, i, position-3);

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  }

  else{

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  DrawX(g, d, 2, position-6);

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  }

  

//  System.out.println("..  X was moved to position "+position+" (first maximum was selected)");

  help.print_board(m.board);

//check if X is winner

  winner = help.check_winner(m.board, 1);

  if(winner)

  {

  System.out.println("..  X won! End of game");

  break;

  }

  

 

  //min move

  if(m.board.contains(0))

  {

//   System.out.println("\nit is O turn now .......................................");

  position = m.moveO(m.board);

  m.board.set(position, new Integer(2));

  

  if(position <=2){

  i=0;

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  DrawO(g, d, i, position);

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  }

  else if(position>2 && position <=5){

  i=1;

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  DrawO(g, d, i, position-3);

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  }

  else{

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  DrawO(g, d, 2, position-6);

  try {

Thread.sleep(1000);

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

  }

//   System.out.println("..  O was moved to position: "+position+" (first minimum was selected)");

  help.print_board(m.board);

//check if O is winner

  winner = help.check_winner(m.board, 2);

  if(winner)

  {

  System.out.println("..  O won! End of game");

  break;

  }

  }

      } 

   }

 

public void DrawX(Graphics g, Dimension d, int row, int col)

   {

       int xStart, yStart, xOff, yOff;

       int i;

       xOff = d.width / 3;

       yOff = d.height / 3;

       xStart = xOff  * col;

       yStart = yOff * row;

       for (i = 0; i < 4; i++)

       {

           g.drawLine(xStart + i + 6, yStart + 6,

                     xStart + xOff + i - 10, yStart + yOff - 10);

           g.drawLine(xStart + xOff + i - 10, yStart + 6,

                      xStart + i + 6, yStart + yOff - 10);

       }

   }

 

public void DrawO(Graphics g, Dimension d, int row, int col)

   {

       int xStart, yStart, xOff, yOff;

       int i;

       xOff = d.width / 3;

       yOff = d.height / 3;

       xStart = xOff  * col;

       yStart = yOff * row;

       for (i = 0; i < 4; i++)

       {

           g.drawOval(xStart + i + 6, yStart + i + 6,

                      xOff - i * 2 - 10, yOff - i * 2 - 10);

       }

   }

 

 

}

--------------------------------------------------------------------------------