10 Replies - 3259 Views - Last Post: 29 April 2011 - 09:59 AM Rate Topic: -----

#1 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

TicTacToe structured AI Implementation

Posted 28 April 2011 - 11:40 AM

Hey all, I am making a little TicTacToe game in Swing and I got it working rather easily so I decided to add an AI and started searching various algorithms I could use, I found one that seemed understandable and rather easy here:
http://algojava.blog...oe-ai-java.html

However, the file itself did not include implementation of the algorithm merely the algorithm itself so I thought it would be rather easy to implement it however I have had a few issues namely when setting a position in the board to the player value that is changed. The compiler says that my newMove method is throwing out NullPointerException error , I am unsure as to how to amend this, the code is here:
NOTE: I know I copied and pasted to a large extent (:/) , I just wish to see the method in action.

import java.io.*;
public class MainFrame {

    /**
     * @param args the command line arguments
     */
    /* the board */
    public static int board[][];
    public static char sBoard[][];
    public static boolean endGame = false;
    /* empty */
    public static final int EMPTY = 0;
    /* player one */
    public static final int ONE = 1;
    /* player two */
    public static final int TWO = 2;
     public void TicTacToeAI() {
        board = new int[3][3];
    }
     /* 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];
    }
      /* 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;
    }
    /* 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;
                    endGame = true;
                    }
                }
            }
        return false;
    }
   public void paintBoard(char[][] displayBoard) {
       for (int i = 0; i < board.length; i++) {
           for (int j = 0; j < board[i].length; j++ ) {
           System.out.println(displayBoard[i][j]);
           }
       }
   }
   public void newMove(int xpos, int ypos, int token) {
    if (token == ONE) {
       board[xpos][ypos] = token;
    }
    if (token == TWO) {
        board[xpos][ypos] = token;
    }
    updateBoard(board);
    paintBoard(sBoard);
   }
   public void updateBoard(int [][] board) {
       for (int i = 0; i < board.length; i++) {
           for (int j = 0; j < board[i].length; j++) {
               if (board[i][j] == ONE) {
                   sBoard[i][j] = 'x';
               }
               else if (board[i][j] == TWO) {
                   sBoard[i][j] = 'o';
               }
               else {
                   sBoard[i][j] = '_';
               }
           }
       }
   }
    public static void main(String[] args) throws Exception {
     MainFrame mn = new MainFrame();
     BufferedReader inKb = new BufferedReader (new InputStreamReader (System.in));
     int token = 1;
     while (endGame == false) {
     System.out.println ("player " + token + " Enter your xpos value(x,y): ");
     int xpos = Integer.parseInt(inKb.readLine());
     System.out.println ("player " + token + " Enter your ypos value(x,y): ");
     int ypos = Integer.parseInt(inKb.readLine());
     mn.newMove( xpos, ypos, token);
     token = 2;
     for (int i = 0; i < board.length; i++) {
         for (int j = 0; j < board[i].length; j++) {
             mn.getBoardValue(i,j);
             mn.nextMove(token);
             mn.nextWinningMove(token);
         }
         mn.updateBoard(board);
     }
    //Note: token = current player
    }
    }

}



Any help or a link to a different Algorithm/method to use would be much appreciated.

thanks,
v0rtex

This post has been edited by v0rtex: 28 April 2011 - 11:43 AM


Is This A Good Question/Topic? 0
  • +

Replies To: TicTacToe structured AI Implementation

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,463
  • Joined: 27-December 08

Re: TicTacToe structured AI Implementation

Posted 28 April 2011 - 12:07 PM

Post the stack trace.
Was This Post Helpful? 0
  • +
  • -

#3 CodingShadows  Icon User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 19
  • Joined: 23-November 10

Re: TicTacToe structured AI Implementation

Posted 28 April 2011 - 12:18 PM

Board is not properly initialized, as confirmed by this modification:
   public void newMove(int xpos, int ypos, int token) {
   	if(board==null){
   		System.out.println("Erm... There appears to be no board.");
   		return;
   	}
    if (token == ONE) {
       board[xpos][ypos] = token;
    }
    if (token == TWO) {
        board[xpos][ypos] = token;
    }
    updateBoard(board);
    paintBoard(sBoard);
   }

Was This Post Helpful? 2
  • +
  • -

#4 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Re: TicTacToe structured AI Implementation

Posted 28 April 2011 - 12:30 PM

Sigh, I coded this before but I never backed up my code, I tried to set all the Board values to zero so that I could initialize atleast a default value to the board.
like so:
   public void initBoard() {
       for (int i = 0; i < 3; i++)
       {
           for (int j = 0 ; j < 3; j++) {
               board[i][j] = EMPTY;
           }

       }
    }


and the line:
 board[i][j] = EMPTY //where EMPTY = 0 

Gives out an error, I am guessing this is because I am trying to assign a integer to an integer array but I think this is necessary for the algorithm to work (I am probably wrong), I just noticed that the OP in the link I gave did this in his code:
  board[i][j] = token;


and sorry I forgot that
 int [] [] board = new int[3][3]; 
Only reserved memory :P
Any help is appreciated, thanks so far.
Was This Post Helpful? 0
  • +
  • -

#5 CodingShadows  Icon User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 19
  • Joined: 23-November 10

Re: TicTacToe structured AI Implementation

Posted 28 April 2011 - 12:43 PM

Your going to need to make sure that you do
board = new int[][]
before you assign the values to each element in the array. The sboard seems to need this as well.
This works, but I don't think it is the best way to do it:
    /* the board */
    public static int board[][] = {{0,0,0},{0,0,0},{0,0,0}};
    public static char sBoard[][] = {{0,0,0},{0,0,0},{0,0,0}};
    public static boolean endGame = false;
    /* empty */


Was This Post Helpful? 1
  • +
  • -

#6 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Re: TicTacToe structured AI Implementation

Posted 28 April 2011 - 12:54 PM

I'm not too convinced this method is the best way to do it, thanks though the code worked except that after the user enters in his position, the AI doesn't do its move?
I'm open to other suggestions on how to implement this AI for TicTacToe, tutorials would be more than awesome if you guys have any in mind. Thanks
Was This Post Helpful? 0
  • +
  • -

#7 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: TicTacToe structured AI Implementation

Posted 28 April 2011 - 09:14 PM

in your board[][] put 0 for not used 100 for X and 10 for O
If the total of a row/colum/diagonal is 300 the X won if it is 30 the O won

This post has been edited by pbl: 28 April 2011 - 09:15 PM

Was This Post Helpful? 0
  • +
  • -

#8 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Re: TicTacToe structured AI Implementation

Posted 29 April 2011 - 02:05 AM

pbl, do you have any pseudo code as to how I would implement this?
I'm really stuck with this little project :/
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,463
  • Joined: 27-December 08

Re: TicTacToe structured AI Implementation

Posted 29 April 2011 - 04:17 AM

If it is the X player's turn, mark the chosen space in the array with a 10. If it is the O player's turn, mark the chosen space in the array with a 100. Then sum up the rows, columns, and diagonals. If you find one with the sume of 30, X wins. A sum of 300 means that O wins.
Was This Post Helpful? 0
  • +
  • -

#10 CodingShadows  Icon User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 19
  • Joined: 23-November 10

Re: TicTacToe structured AI Implementation

Posted 29 April 2011 - 09:54 AM

@mosxn101 Try not to repeat the post two before your's.

Anyway, this is probably the better way to initialize the arrays:
     board = new int[3][3];
     sBoard= new char[3][3];
     for(int i = 0; i<3;i++){
     	for(int j = 0;j<3;j++){
     		board[i][j]=0;
     		sBoard[i][j]=0;
     	}
     }


And for me, your paintboard method prints out each cell on it's own line. I found it to work better like this:
   public void paintBoard(char[][] displayBoard) {
       for (int i = 0; i < board.length; i++) {
           for (int j = 0; j < board[i].length; j++ ) {
           System.out.print(displayBoard[i][j]);
           }
       System.out.println();
       }
   }


Also, your isWin method seems pretty confusing, and may be the source of some of your problems.

And please try to show some effort. People will be more willing to help you.
Was This Post Helpful? 0
  • +
  • -

#11 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Re: TicTacToe structured AI Implementation

Posted 29 April 2011 - 09:59 AM

Got it working, Thanks
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1