Sign in to follow this  

tic tac toe min max tree

This topic is 4549 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I wrote a min max tree tic tac toe in java. the Ai does play but it appears there is a bug that causes the scoring to be off. For example, if the player is going first, which is what the tree is currently running on right now, and the player places there mark in any corners, the AI has to place theres in the center or they could lose. On the left side of board, it works and the AI always marks in the middle, however on the right side of the board, the ai doesnt mark in the middle. It seems there is a symmetry issue even though I never programmed it based on symmetry. I would be greatful if someone could take a look at my code and help me out. Thanks. Main program
// playTicTacToe.java

package calvin.tictactoe;

import calvin.tictactoe.*;
import java.io.*;
import java.util.*;

public class PlayTicTacToe {


	public static void main (String[] args) {
		//TicTacToeMinMaxTree AI;
		TicTacToeMinMaxTreeTest AI;
		TicTacToe t = new TicTacToe();
		t.draw();
		// main game loop
		boolean goFirst;
		Random r = new Random();
		if(r.nextInt(2) == 0)
			goFirst = false;
		else goFirst = true;

		
		// if player gets to go first
		//if(goFirst) {
			while(!t.boardFull() && !(t.whoWins('X') || t.whoWins('O'))) {
			
				// if player gets to go first
				if(!t.whoWins('X')) {
					//t.draw();
					System.out.println("Your turn...");
					t.mark('O');
					t.draw();
				}
				else break;
				
				if(!t.whoWins('O')) {
					System.out.println("Computers Turn...");
					//AI = new TicTacToeMinMaxTree(t.getBoard());
					AI = new TicTacToeMinMaxTreeTest(t.getBoard());
					t.mark(AI.returnFinalMove(), 'X');
					t.draw();
				}
				else break;
			}
		//}
			
		/*else {
			while(!t.boardFull() ) {
				
				if(!t.whoWins('O')) {
					boolean randomizeFirstMove = true;
					if(randomizeFirstMove) {
						Random ran = new Random();
						int[] te = new int[2];
						te[0] = ran.nextInt(3);
						te[1] = ran.nextInt(3);
						t.mark(te, 'X');
					}
					else {
						System.out.println("Computers Turn...");
						AI = new TicTacToeMinMaxTree(t.getBoard());
						t.mark(AI.returnFinalMove(), 'X');
						t.draw();
					}
				}
				else break;
				
				// if player gets to go first
				if(!t.whoWins('X')) {
					//t.draw();
					System.out.println("Your turn...");
					t.mark('O');
					t.draw();
				}
				else break;
			}
		
		}*/
	}
}



TicTacToe functions
//TicTacToe.java

package calvin.tictactoe;

import java.io.*;

public class TicTacToe
{
	// 2D array to hold TicTacToe board Information
	private static char[][] board = new char[3][3];
	
	// Array to hold input characters to place mark
	private char[] input = new char[2];
	
	// Array to hold integer coordinates
	private int[] coord = new int[2];
	
	// String to hold players name
	private String name;
	
	
	
	// static initializer to initialize the arrays
	static {
		// initialize board to be all blanks
		for(int i = 0; i != board.length; i++)
			for(int j = 0; j != 3; j++)
				 board[i][j] = ' ';
		
	}
	
	// draw the tictactoe board and reference grid
	public void draw() {
	
		System.out.println();
		System.out.println("   1   2   3");
		System.out.println("     |   |   ");
		System.out.println("A  " + board[0][0] + " | " + board[0][1] + " | " + board[0][2]);
		System.out.println("  ___|___|___");
		System.out.println("     |   |   ");
		System.out.println("B  " + board[1][0] + " | " + board[1][1] + " | " + board[1][2]);
		System.out.println("  ___|___|___");
		System.out.println("     |   |   ");
		System.out.println("C  " + board[2][0] + " | " + board[2][1] + " | " + board[2][2]);
		System.out.println("     |   |   ");
		System.out.println();
	}
	
	// choose spot on board and place mark
	public void mark(int[] mark, char c) {
		if(board[mark[0]][mark[1]] == ' ') {
			board[mark[0]][mark[1]] = c;
		}
		else //{
			System.err.println("Cant print there, error!!!");
			//System.exit(0); }
		//System.out.println("Final move is: " + mark[0] + " " + mark[1]);
	}
	
	public void mark(char mark_to_make) {
		
		
		// read into string
		System.out.println();
		System.out.println("Please enter the spot you wish to place your mark (Letter first, followed by number)");
		
		// loop to handle errors
		boolean valid_input;
		do {
		
		valid_input = true;
		
		String temp = "";
		try {
		InputStreamReader converter = new InputStreamReader(System.in);
		BufferedReader in = new BufferedReader(converter);
		temp = new String(in.readLine().toUpperCase());
		}
		catch(IOException e) { }
		
		
		input[0] = temp.charAt(0);
		input[1] = temp.charAt(1);
		
		// run tests to see if input is valid
		// once bottom of loop is reached and valid_input still is true
		// all tests have been passed
		
		// test input to see if it is good and if it is, create an index of spot
		try {
			coord = getIndex();
		}
		catch(Exception e) { System.out.println(e.getMessage()); valid_input = false; }
		
		// make sure space is available to place mark
		
		if (board[coord[0]][coord[1]] != ' ')
			valid_input = false;	
			
		// if we made it this far with valid_input = true, exit the loop, otherwise, try again
		} while(!valid_input);
		
		// now place mark on the board
		board[coord[0]][coord[1]] = mark_to_make;
	}
	
	// auxillary function to test if mark can be made
	private boolean ableToMark(){
		
		if (board[coord[0]][coord[1]] == ' ')
			return true;
		else return false;
	}
	
	// function to conver char array to int array
	private int[] getIndex() throws Exception {
		
		// create array to return
		int[] ret = new int[2];
		
		// check letters
		switch(input[0]) {
			case 'A': ret[0] = 0; break;
			case 'B': ret[0] = 1; break;
			case 'C': ret[0] = 2; break;
			default: throw new Exception("Invalid Letter");
		}
		
		// check numbers
		switch(input[1]) {
			case '1': ret[1] = 0; break;
			case '2': ret[1] = 1; break;
			case '3': ret[1] = 2; break;
			default: throw new Exception("Invalid Number");
		}
		
		return ret;
	}
	
	public boolean boardFull() {
		
		// check to see if the board is full
		int count_of_empty_spaces = 0;
		for(int i = 0; i != 3; i++)
			for(int j = 0; j != 3; j++)
				if (board[i][j] == ' ')
					++count_of_empty_spaces;
					
		// return true if there are no more spaces
		//System.out.println(count_of_empty_spaces);
		return (count_of_empty_spaces == 0);
	}
	

	
	public boolean whoWins(char c) {
	
		if (c == board[0][0] && board[0][0] == board[0][1] && board[0][1] == board[0][2]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[1][0] && board[1][0] == board[1][1] && board[1][1] == board[1][2]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[2][0] && board[2][0] == board[2][1] && board[2][1] == board[2][2]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[0][0] && board[0][0] == board[1][0] && board[1][0] == board[2][0]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[0][1] && board[0][1] == board[1][1] && board[1][1] == board[2][1]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[2][0] && board[2][0] == board[2][1] && board[2][1] == board[2][2]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[0][0] && board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
			System.out.println(c + " WINS!");
			return true; }
			
		else if (c == board[0][2] && board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
			System.out.println(c + " WINS!");
			return true; }
		
		else if (boardFull()) {
			System.out.println("Cat's Game");
			return true; }
				
		else return false;
	}
	
	// return the board
	public char[][] getBoard()
	{
		return board;
	}
}


TicTacToeMinMaxTree The recursively constructs itself through constructors. It keeps on calling constuctors to create new nodes until either a solution is found or the board is full.
// TicTacToeAI.java

/////////////////////////////////////////////
///
///           SOMETHING IS MESSED
///           UP WITH THE CALCULATIONS
///
///           THE NUMBER REFERENCE ON
///			  THE BOARD SCREWS WITH
///           SCORE CALCULATION DUE TO SYMMETRY
///           IN THE THRID COLUMN
///
//////////////////////////////////////////////

package calvin.tictactoe;

import java.io.*;
import calvin.tictactoe.*;
import java.util.*;

public class TicTacToeMinMaxTreeTest {

        // characters to represent players
        private char maxChar = 'X';
        private char minChar = 'O';
        
        // Root Node of the tree, everything branches off of this node
        private TicTacToeNode rootNode;
        
        // MUST USE THIS CONSTRUCTOR
        public TicTacToeMinMaxTreeTest(char[][] board_to_inherit) {
                
                rootNode = new TicTacToeNode(board_to_inherit, false);
                //System.out.println(returnaFinalMove())
        }
        
        // function to analyze full board
        private int calculateScore(char[][] b, char AI, char player) {
                
				if(whoWins(b, AI)) {
                        //System.out.print(1);
                        return 1;
                }
                else if(whoWins(b, player)) {
                        //System.out.print(-1);
                        return -1;
                }       
                else {
                        //System.out.print(0);
                        return 0;
                }
        }
        
        
        
        // function to determine the winner
        public boolean whoWins(char[][] board, char c) {
        
                if (c == board[0][0] && board[0][0] == board[0][1] && board[0][1] == board[0][2]) {
                        return true; }
                        
                else if (c == board[1][0] && board[1][0] == board[1][1] && board[1][1] == board[1][2]) {
                        return true; }
                        
                else if (c == board[2][0] && board[2][0] == board[2][1] && board[2][1] == board[2][2]) {
                        return true; }
                        
                else if (c == board[0][0] && board[0][0] == board[1][0] && board[1][0] == board[2][0]) {
                        return true; }
                        
                else if (c == board[0][1] && board[0][1] == board[1][1] && board[1][1] == board[2][1]) {
                        return true; }
                        
                else if (c == board[2][0] && board[2][0] == board[2][1] && board[2][1] == board[2][2]) {
                        return true; }
                        
                else if (c == board[0][0] && board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
                        return true; }
                        
                else if (c == board[0][2] && board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
                        return true; }
                
                                
                else return false;
        }
                
        private int boardFull(char[][] b) {
                
                // check to see if the board is full
                int count_of_empty_spaces = 0;
                for(int i = 0; i != 3; i++)
                        for(int j = 0; j != 3; j++)
                                if (b[i][j] == ' ')
                                        ++count_of_empty_spaces;
                                        
                // return true if there are no more spaces
                //System.out.println(count_of_empty_spaces);
                return count_of_empty_spaces;
        }
        
        // Move to take
        private int[] finalMove = new int[2];
        
        
        // return move to make
        public int[] returnFinalMove() {
                
		//System.out.println("function called");
                int[] ret = new int[2];
		int count = 0;
		int[][] temp;
                // search the the children of root node looking for one with the matching score
                //System.out.println("init array");
		for(int i = 0; i != rootNode.childrenNodes.length; ++i)
                        if(rootNode.childrenNodes[i].score == rootNode.score) 
                  		++count;
		
		//System.out.println("filling array");
		temp = new int[count][2];
		int moves = 0;
		for(int i = 0; i != rootNode.childrenNodes.length; ++i)
                        if(rootNode.childrenNodes[i].score == rootNode.score) {
				temp[moves][0] = rootNode.childrenNodes[i].move[0];
				temp[moves][1] = rootNode.childrenNodes[i].move[1];
				++moves;
			}
                //System.out.println("before random move");
		Random r = new Random();
		// print out root score
		System.out.println("rootNode score = " + rootNode.score);
		// print out childrenNodes scores
		System.out.print("ChildrenNode scores: ");
		for(int i = 0; i != rootNode.childrenNodes.length; ++i) {
			System.out.print(rootNode.childrenNodes[i].score + " ");
		}
		System.out.println();
		//System.out.println("count = " + count);
		int x = r.nextInt(count);
                // if scores are the same, randomly select move
		ret[0] = temp[x][0];
        ret[1] = temp[x][1];
		
		//System.out.println("returning move");
		return ret;     
        }
        
        
        /////////////////////////////////////////////
        ////////// NESTED CLASS /////////////////////
        ////////// CHILD NODES  /////////////////////
        /////////////////////////////////////////////
        private class TicTacToeNode {
                
                // MUST USE THIS CONSTRUCTOR
                public TicTacToeNode(char[][] tttb, TicTacToeNode p, int[] newMove, boolean ai) {
                                
                        
                        // initialize the move that this node took
                        initMove(newMove);
                        
                        
                        // Initialize whos turn it is
                        aiControl(ai);
                        
                        // initialize board
                        initAIboard(tttb, newMove, maxChar, minChar, ai);
                        
                        // used to calculate size of array for possible moves and possible children
                        numOfSpaces = boardFull(AIboard);
                        
                        // reference to parentnode, unused
                        parentNode = p.parentNode;
                        
                        
                        
                        // recursively initialize all children
                        // only if the board is not full and no one wins on the current move
                        if(numOfSpaces != 0 && !(whoWins(AIboard, 'X') || whoWins(AIboard, 'O'))) {
                                
                                availableMoves = new int[numOfSpaces][2];
                                
                                initAvailableMoves(AIboard);
                                
                                childrenNodes = new TicTacToeNode[numOfSpaces];
                                initChildren();
                        }
                        
                        // if the board is full or someone did win
                        // set the score for that child
                        else {
							try {
                                score = calculateScore(AIboard, maxChar, minChar);
							} catch(Exception e) { }
						//System.out.println(score);
                        }
                        
                }
                
                // constructor used to initialize root node
                public TicTacToeNode(char[][] tttb, boolean ai) {
                                
                        // initialize un-modified board
                        initAIboard(tttb);
                        
                        // Initialize whos turn it is
                        aiControl(ai);
                        
                        // initialize array of TicTacToeBoard children
                        numOfSpaces = boardFull(AIboard);

                        availableMoves = new int[numOfSpaces][2];
                        
                        initAvailableMoves(AIboard);                        
                        
                        // recursively initialize all children
                   				childrenNodes = new TicTacToeNode[numOfSpaces];
                                initChildren();
        
                        // if it does get to the bottom
                        // set the score for that child
                        System.out.println(score);
                }       
                
		private char returnChar() {
			if(max)
				return 'X';
			else return 'O';
		}
		
                private int numOfSpaces = 0;
                
                // Score for each node, inherited from children
                private int score = 0;
                
                private boolean max;
                
                
                
                // determine if the computer controlls currrent generation
                // take the current value and return the oppossite from the previous generation
                private boolean aiControl(boolean b) {
                        
                        if (b) {
                                max = false;
                                return false;
				
				 }
                                
                        else { 
                                max = true;
                                return true; }
                }
                
                private void initAIboard(char[][] b, int[] nm, char AI, char player, boolean who)
                {
                        for(int i = 0; i != 3; i++)
                                for(int j = 0; j != 3; j++)
                                        AIboard[i][j] = b[i][j];
                        
                        if (who) AIboard[nm[0]][nm[1]] = AI;
                        else AIboard[nm[0]][nm[1]] = player;
                }
                
                // overloaded initAiboard so it doenst add a new space
                private void initAIboard(char[][] b)
                {
                        for(int i = 0; i != 3; i++)
                                for(int j = 0; j != 3; j++)
                                        AIboard[i][j] = b[i][j];
                        
                       
                }
                
		private boolean test = false;
                // find out all the possible moves
                private void initAvailableMoves(char[][] b) {
                        
			int count = 0;
                        for(int i = 0; i != 3; i++)
                                for(int j = 0; j != 3; j++)
                                        if (b[i][j] == ' ')
                                        {
                                                availableMoves[count][0] = i;
                                                availableMoves[count][1] = j;
						
						++count;
                                        }
					
                }
                
                // Hold all the available moves
                private int[][] availableMoves;
                
                // New move for this instance
                private int[] move = new int[2];
                
                private void initMove(int[] m) {
                        move[0] = m[0];
                        move[1] = m[1];
                }
                
                
                // return score
                public int returnScore() {
                        return score;
                } 
                
                // Nodes own instance of TicTacToe board
                private char[][] AIboard = new char[3][3];
                
                // Node refering to parent
                private TicTacToeNode parentNode;
                
                // There can be a variable amount of children, create an array of nodes referring to children
                private TicTacToeNode[] childrenNodes;
                
                // initialize the children of a node, recursively
                // once recursion is done, set the score based on the children
                private void initChildren() {
                        
                        int moveCounter = 0;
                        for(int i = 0; i != childrenNodes.length; ++i) {
                                childrenNodes[i] = new TicTacToeNode(AIboard, this, availableMoves[moveCounter], max);
                                ++moveCounter;
                        }
                        
                        score = compareChildren();
                        
                }
                
                //function to compare children of the current node and set the score of the current node depending
                // on whose turn it is
                private int compareChildren() {
                        
                        int tempScore;
                        //find the max score if it is AI's turn
                        if (max) {
                                tempScore = childrenNodes[0].returnScore();
								for(int i = 0; i != childrenNodes.length; ++i) {
                                        if (childrenNodes[i].returnScore() > tempScore)
                                                tempScore = childrenNodes[i].returnScore();
                                }
                        }
                        // or find the min score if it isnt AI's turn        
                        else {
                                tempScore = childrenNodes[0].returnScore();
								for(int i = 0; i != childrenNodes.length; ++i) {
                                        if (childrenNodes[i].returnScore() < tempScore)
                                                tempScore = childrenNodes[i].returnScore();
                                }
                        }
                        
                        return tempScore;
                }
                        
                        
        }
        
}


To see what im talking about, it would be easiest to compile the code and run it on your own machine. Make a mark in A1, see what scores are generated, and then make a mark in A3 and see what scores are generated by the children. They will be different even though they should be the same. Again, Thanks.

Share this post


Link to post
Share on other sites

This topic is 4549 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this