Sign in to follow this  
xidis

minmax tree for tictactoe in java

Recommended Posts

xidis    127
I have really no java programming experience. The first program I wrote by myself was a two player tic tac toe game. I am now trying to make an ai version by using a min max tree. The code I have so far is below. The class consists of the main min max tree class, with a nested class representing the nodes of the tree. When the Min max tree class is initialized using the correct constructor, it will (at least I think it does) create the entire tree based on the parameters you pass it. The constructor for the TicTacToeNode class recursively initializes all the child nodes which then recursively initialize their child nodes. This continues until the board is full and thus there are no more children. A function is then called to determine the score for the final board and that is translated back up as the recursion is un-expanded. However, something doesnt work right and I cant place my finger on it. When I run a test run, the AI wont stop the player from scoring if it can and sometimes it overrides the players move, when it shouldnt. Please excuse the code for being un-organized, as it is my first time using java.
// TicTacToeAI.java

package calvin.tictactoe;

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


public class TicTacToeMinMaxTree {

	private char AIchar = 'X';
	private char playerChar = 'O';
	
	// Root Node of the tree, everything branches off of this node
	private TicTacToeNode rootNode;
	
	// MUST USE THIS CONSTRUCTOR
	public TicTacToeMinMaxTree(char[][] board_to_inherit) {
		
		rootNode = new TicTacToeNode(board_to_inherit, false);
		
	}
	
	// function to analyze full board, and reinitMove(newMove);turn value corresponding to full board
	private int calculateScore(char[][] b, char AI, char player) {
		
		if(whoWins(b, AI)) {
			//System.out.println("Ai win");
			return 1;
		}
		else if(whoWins(b, player)) {
			//System.out.println("Ai lose");
			return -1;
		}	
		else {
			//System.out.println("cat");
			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() {
		
		int[] ret = new int[2];
		// search the the children of root node looking for one with the matching score
		for(int i = 0; i != rootNode.childrenNodes.length; ++i)
			if(rootNode.childrenNodes[i].score == rootNode.score) 
			{
				ret[0] = rootNode.childrenNodes[i].move[0];
				ret[1] = rootNode.childrenNodes[i].move[1];
			}
			
		return ret;	
	}
	
	
	
	/////////////////////////////////////////////
	////////// NESTED CLASS /////////////////////
	////////// CHILD NODES  /////////////////////
	/////////////////////////////////////////////
	private class TicTacToeNode {
		
		// MUST USE THIS CONSTRUCTOR
		public TicTacToeNode(char[][] tttb, TicTacToeNode p, int[] newMove, boolean ai) {
				
			initMove(newMove);
			
			initAIboard(tttb, newMove, AIchar, playerChar);
			
			// Initialize whos turn it is
			aiControl(ai);
			
			// initialize array of TicTacToeBoard children
			numOfSpaces = boardFull(AIboard);

			availableMoves = new int[numOfSpaces][2];
			
			initAvailableMoves(AIboard);
			parentNode = p.parentNode;
			
			
			
			// recursively initialize all children
			// function to do that
			if(numOfSpaces != 0) {
				childrenNodes = new TicTacToeNode[numOfSpaces];
				initChildren();
			}
			
			// if it does get to the bottom
			// set the score for that child
			else 
				score = calculateScore(AIboard, AIchar, playerChar);
			
			
		}	
		
		public TicTacToeNode(char[][] tttb, boolean ai) {
				
			//initMove(newMove);
			
			initAIboard(tttb);
			
			// Initialize whos turn it is
			aiControl(ai);
			
			// initialize array of TicTacToeBoard children
			numOfSpaces = boardFull(AIboard);

			availableMoves = new int[numOfSpaces][2];
			
			initAvailableMoves(AIboard);
			//parentNode = p.parentNode;
			
			
			
			// recursively initialize all children
			// function to do that
			
				childrenNodes = new TicTacToeNode[numOfSpaces];
				initChildren();
			
			
			// if it does get to the bottom
			// set the score for that child
					
		}	
		
		private int numOfSpaces = 0;
		
		// Score for each node, inherited from children
		private int score = 0;
		
		private boolean aiTurn;
		
		
		
		// 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) {
				aiTurn = false;
				return false; }
				
			else { 
				aiTurn = true;
				return true; }
		}
		
		private void initAIboard(char[][] b, int[] nm, char AI, char player)
		{
			for(int i = 0; i != 3; i++)
				for(int j = 0; j != 3; j++)
					AIboard[i][j] = b[i][j];
			
			if (aiTurn) 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];
			
			//if (aiTurn) AIboard[nm[0]][nm[1]] = AI;
			//else AIboard[nm[0]][nm[1]] = player;
		}
		
		// 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;
		
		private void initChildren() {
			
			int moveCounter = 0;
			for(int i = 0; i != childrenNodes.length; ++i) {
				childrenNodes[i] = new TicTacToeNode(AIboard, this, availableMoves[moveCounter], aiTurn);
				++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 = 0;
			//find the max score if it is AI's turn
			if (aiTurn) {
				for(int i = 0; i != childrenNodes.length; ++i) {
					if (childrenNodes[i].returnScore() > tempScore)
						tempScore = childrenNodes[i].returnScore();
				}
			}
				
			else {
				for(int i = 0; i != childrenNodes.length; ++i) {
					if (childrenNodes[i].returnScore() < tempScore)
						tempScore = childrenNodes[i].returnScore();
				}
			}
			
			return tempScore;
		}
			
			
	}
	
}


Share this post


Link to post
Share on other sites

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