Thursday, July 5, 2012

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



Posted by at 1 comment:
Subscribe to: Comments (Atom)