Thread: TicTacToe Tree Help...

Hello, i've been reading a little about linked lists and trees and such and i'm trying to make a (simple <- keyword, ha) decision tree. As of now i'm just trying to setup the tree.

I need some help, maybe everyone can see what i'm trying to do from the code here, thanks!

Code:

#include <iostream>

using namespace std;

enum{COMPUTER = 1, PLAYER = 2, EMPTY = 0};

//For the purposes of the Tree the boxes will be referred to by the tree as such:
/*       [1][2][3]
		 [4][5][6]
		 [7][8][9]  		  */

//Tree Structure
struct node
{
	int nBoard[3][3];
	int depth;
	int value;
	node *parent;
	node *link[9];
};

//Coordinate Structure
struct coordinate
{
	int c;
	int r;
}_coordinate;

//Global Variables
int board[3][3] = {{EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}};
node *start;
node *current;

//Function Prototypes
void displayBoard(int board[3][3]);
void computerMove(int board[3][3]);
void chooseMove(int board[3][3]);
bool createTree();
void addNodes(node *parent);
void copyParentBoard(node *parent);

//Main
int main()
{
	displayBoard(board);
	cin.ignore();
	return 0;
}

//Display The Board Function
void displayBoard(int board[3][3])
{
	//Display The Board Function
	cout<<"\n\n";
	cout<<"\t   1  2  3\n";
	cout<<"\t   _  _  _\n";
	for(int c=0; c<3; c++)
	{
		cout<<"\t";
		cout<<(c+1)<<" ";
		for(int r=0; r<3; r++)
		{
			if(board[c][r] == COMPUTER)
			{
				cout<<"|O|";
			}
			else if(board[c][r] == PLAYER)
			{
				cout<<"|X|";
			}else{
				cout<<"|_|";
			}
		}
		cout<<"\n";
	}
}

//Move the Computer Function
void computerMove(int board[3][3])
{
	//Moves the Computer
}

//Choose the Move Function
void chooseMove(int board[3][3])
{
	//choose the best move
}

//Function which sets up the Tree
bool createTree()
{
	//Setup the Tree, once
	//Setup Start node
	start->parent = NULL;
	start->depth = 0;
	start->nBoard[3][3] = NULL;
	start->value = 0;
	
	return true;
}

void addNodes(node *parent, int cDepth)
{
	//Add the 9 Nodes to the parent
	node *nNode1, *nNode2, *nNode3, *nNode4, *nNode5, *nNode6, *nNode7, *nNode8, *nNode9;
	nNode1 = new node;
	nNode2 = new node;
	nNode3 = new node;
	nNode4 = new node;
	nNode5 = new node;
	nNode6 = new node;
	nNode7 = new node;
	nNode8 = new node;
	nNode9 = new node;
	//Setup Variables
	nNode1->depth = nNode2->depth = nNode3->depth = nNode4->depth = nNode5->depth =
nNode6->depth = nNode7->depth = nNode8->depth = nNode9->depth = cDepth;
	nNode1->parent = nNode2->parent = nNode3->parent = nNode4->parent = nNode5->parent = 
nNode6->parent = nNode7->parent = nNode8->parent = nNode9->parent = parent;
	//Adjust Parent Node - Link to Children
	parent->link[0] = nNode1;
	parent->link[1] = nNode2;
	parent->link[2] = nNode3;
	parent->link[3] = nNode4;
	parent->link[4] = nNode5;
	parent->link[5] = nNode6;
	parent->link[6] = nNode7;
	parent->link[7] = nNode8;
	parent->link[8] = nNode9;
}

void copyParentBoard(node *parent)
{
	for(int n=0; n<9; n++)
	{	
		for(int col=0; col<3; col++)
		{
			for(int row=0; row<3; row++)
			{
				&parent->link[n]->nBoard[col][row] = parent->nBoard[col][row];
			}
		}
	}
}

I realize this is probably completely wrong, ha, but i'm trying, as you can also see i'm getting into the meat of the tree and pseudocoding the rest, i actually have a program working now but without the AI which is the fundamental part.

Thanks!

Code:

void addNodes(node *parent, int cDepth)
{
	//Add the 9 Nodes to the parent
	node *nNode1, *nNode2, *nNode3, *nNode4, *nNode5, *nNode6, *nNode7, *nNode8, *nNode9;
	nNode1 = new node;
	nNode2 = new node;
	nNode3 = new node;
	nNode4 = new node;
	nNode5 = new node;
	nNode6 = new node;
	nNode7 = new node;
	nNode8 = new node;
	nNode9 = new node;
	//Setup Variables
	nNode1->depth = nNode2->depth = nNode3->depth = nNode4->depth = nNode5->depth =
nNode6->depth = nNode7->depth = nNode8->depth = nNode9->depth = cDepth;
	nNode1->parent = nNode2->parent = nNode3->parent = nNode4->parent = nNode5->parent = 
nNode6->parent = nNode7->parent = nNode8->parent = nNode9->parent = parent;
	//Adjust Parent Node - Link to Children
	parent->link[0] = nNode1;
	parent->link[1] = nNode2;
	parent->link[2] = nNode3;
	parent->link[3] = nNode4;
	parent->link[4] = nNode5;
	parent->link[5] = nNode6;
	parent->link[6] = nNode7;
	parent->link[7] = nNode8;
	parent->link[8] = nNode9;
}

You should be able to make that much cleaner and more readable with a for loop.

Currently all you call is displayBoard(), from main(). Is there something wrong with it? Maybe you need to initialize the board first?

Also see this page from aihorizon.com: http://www.aihorizon.com/essays/basi...es/minimax.htm

Yeah i hear what you're saying with the loop, i agree i just couldn't figure out everything exactly at the moment, i guess i could change Node1, node2, etc... into an array and then use a loop.

Anyways... Yeah i tried calling it and i get errors with the pointers i think cause they are like run-time errors.

This is tough, ha for such a simple game.

Does anyone know any tutorials or example codes that are trying to achieve what i am by the same means?


I'm just struggling with this a lot, ha

Thanks for any help you can give!

Well, I can tell you why you get segmentation faults.

Code:

//Function which sets up the Tree
bool createTree()
{
	//Setup the Tree, once
	//Setup Start node
	start->parent = NULL;
	start->depth = 0;
	start->nBoard[3][3] = NULL;
	start->value = 0;
	
	return true;
}

You merrily access start, assuming it will be allocated. It isn't.

Also, instead of this

Code:

			if(board[c][r] == COMPUTER)
			{
				cout<<"|O|";
			}
			else if(board[c][r] == PLAYER)
			{
				cout<<"|X|";
			}else{
				cout<<"|_|";
			}

Why not use a switch statement or even something like this?

Code:

char opponentchar[] = "_OX";

This is tough, ha for such a simple game.

I've written many "simple" games; tic-tac-toe, checkers, etc . . . very few of them have passable AI.

Yeah i hear what you're saying with the loop, i agree i just couldn't figure out everything exactly at the moment, i guess i could change Node1, node2, etc... into an array and then use a loop.

My thoughts exactly.

Does anyone know any tutorials or example codes that are trying to achieve what i am by the same means?

Mmm, well, besides this which I mentioned earlier, not really. I'll look around. [edit] The Wikipedia entry has some information. Every little bit helps. http://en.wikipedia.org/wiki/Tic-tac-toe [/edit]

Okay, ha i fixed the segmentation fault

I read the wikipedia stuff and the AI Horizon bit, but i cant find the source code there unless im not looking at it right, haha And i don't get the segmentation fault anymore, i dunno if it's working i have to write a function to display the tree.

Uh.... so i'll work on the loop for the nodes and i like your idea for displaying the board, very simple i like it, thanks

So i'll keep working and let everyone know how i'm doin.

Thanks!

Code:

#include <iostream>

using namespace std;

enum{COMPUTER = 1, PLAYER = 2, EMPTY = 0};

//For the purposes of the Tree the boxes will be referred to by the tree as such:
/*       [1][2][3]
		 [4][5][6]
		 [7][8][9]  		  */

//Tree Structure
struct node
{
	int nBoard[3][3];
	int depth;
	int value;
	node *parent;
	node *link[9];
};

//Coordinate Structure
struct coordinate
{
	int c;
	int r;
}_coordinate;

//Global Variables
int board[3][3] = {{EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}};
node *start;
node *current;

//Function Prototypes
void displayBoard(int board[3][3]);
void computerMove(int board[3][3]);
void chooseMove(int board[3][3]);
bool createTree();
void addNodes(node *parent, int cDepth);
void copyParentBoard(node *parent);
void deleteTree(node *leaf);

//Main
int main()
{
	start = new node;
	displayBoard(board);
	cin.ignore();
	cout<<"Test Create Tree...";
	if(createTree() == false)
	{
		//error occurred
		return 1;
	}
	cin.ignore();
	cout<<"Test Delete Tree...";
	deleteTree(start);
	cin.ignore();
	return 0;
}

//Display The Board Function
void displayBoard(int board[3][3])
{
	//Display The Board Function
	char piece[]="_XO";
	cout<<"\n\n";
	cout<<"\t   1  2  3\n";
	cout<<"\t   _  _  _\n";
	for(int c=0; c<3; c++)
	{
		cout<<"\t";
		cout<<(c+1)<<" ";
		for(int r=0; r<3; r++)
		{
			cout<<"|";
			cout<<piece[(board[c][r])];
			cout<<"|";
		}
		cout<<"\n";
	}
}

//Move the Computer Function
void computerMove(int board[3][3])
{
	//Moves the Computer
}

//Choose the Move Function
void chooseMove(int board[3][3])
{
	//choose the best move
}

//Function which sets up the Tree
bool createTree()
{
	//Setup the Tree, once
	//Setup Start node
	start->parent = NULL;
	start->depth = 0;
	start->nBoard[3][3] = NULL;
	start->value = 0;
	//Create First Level
	int cDepth=1;
	addNodes(start, cDepth);
	copyParentBoard(start);
	cDepth++;
	return true;
}

void addNodes(node *parent, int cDepth)
{
	//Add the 9 Nodes to the parent
	node *nNode[9];
	for(int n=0; n<9; n++)
	{
		nNode[n] = new node;
		nNode[n]->depth = cDepth;
		nNode[n]->parent = parent;
		parent->link[n] = nNode[n];
	}
}

void copyParentBoard(node *parent)
{
	for(int n=0; n<9; n++)
	{	
		for(int col=0; col<3; col++)
		{
			for(int row=0; row<3; row++)
			{
				parent->link[n]->nBoard[col][row] = parent->nBoard[col][row];
			}
		}
	}
}

void deleteTree(node *leaf)
{
	if(leaf->depth != 0)
	{
		node *parent = leaf->parent;
		for(int d=0; d<9; d++)
		{
			delete parent->link[d];
		}
		deleteTree(parent);
	}
	else if(leaf->depth == 0)
	{
		delete leaf;
	}
}

So here it is now, i'm working on the displaying of the tree now.

Okay... So More problems, ha...

Segmentation Faults perhaps again?

Code:

#include <iostream>

using namespace std;

enum{COMPUTER = 1, PLAYER = 2, EMPTY = 0};

//For the purposes of the Tree the boxes will be referred to by the tree as such:
/*       [1][2][3]
		 [4][5][6]
		 [7][8][9]  		  */

//Tree Structure
struct node
{
	int nBoard[3][3];
	int depth;
	int value;
	node *parent;
	node *link[9];
};

//Coordinate Structure
struct coordinate
{
	int c;
	int r;
}_coordinate;

//Global Variables
int board[3][3] = {{EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}};
node *start;
node *current;

//Function Prototypes
void displayBoard(int board[3][3]);
void computerMove(int board[3][3]);
void chooseMove(int board[3][3]);
bool createTree();
void addNodes(node *parent, int cDepth);
void copyParentBoard(node *parent);
void deleteTree(node *leaf);
void displayPly(node *parent);

//Main
int main()
{
	start = new node;
	displayBoard(board);
	cin.ignore();
	cout<<"Test Create Tree...";
	if(createTree() == false)
	{
		//error occurred
		return 1;
	}
	cin.ignore();
	cout<<"Testing Display Tree...";
	displayPly(start);
	cin.ignore();
	cout<<"Test Delete Tree...";
	deleteTree(start);
	cin.ignore();
	return 0;
}

//Display The Board Function
void displayBoard(int board[3][3])
{
	//Display The Board Function
	char piece[]="_XO";
	cout<<"\n\n";
	cout<<"\t   1  2  3\n";
	cout<<"\t   _  _  _\n";
	for(int c=0; c<3; c++)
	{
		cout<<"\t";
		cout<<(c+1)<<" ";
		for(int r=0; r<3; r++)
		{
			cout<<"|";
			cout<<piece[(board[c][r])];
			cout<<"|";
		}
		cout<<"\n";
	}
}

//Move the Computer Function
void computerMove(int board[3][3])
{
	//Moves the Computer
}

//Choose the Move Function
void chooseMove(int board[3][3])
{
	//choose the best move
}

//Function which sets up the Tree
bool createTree()
{
	//Setup the Tree, once
	//Setup Start node
	start->parent = NULL;
	start->depth = 0;
	start->nBoard[3][3] = NULL;
	start->value = 0;
	//Create First Level
	int cDepth=1;
	addNodes(start, cDepth);
	copyParentBoard(start);
	cDepth++;
	return true;
}

void addNodes(node *parent, int cDepth)
{
	//Add the 9 Nodes to the parent
	node *nNode[9];
	for(int n=0; n<9; n++)
	{
		nNode[n] = new node;
		nNode[n]->depth = cDepth;
		nNode[n]->parent = parent;
		parent->link[n] = nNode[n];
	}
}

void copyParentBoard(node *parent)
{
	for(int n=0; n<9; n++)
	{	
		for(int col=0; col<3; col++)
		{
			for(int row=0; row<3; row++)
			{
				parent->link[n]->nBoard[col][row] = parent->nBoard[col][row];
			}
		}
	}
}

void deleteTree(node *leaf)
{
	if(leaf->depth != 0)
	{
		node *parent = leaf->parent;
		for(int d=0; d<9; d++)
		{
			delete parent->link[d];
		}
		deleteTree(parent);
	}
	else if(leaf->depth == 0)
	{
		delete leaf;
	}
}

void displayPly(node *parent)
{
	cout<<"Parent Node Information:\n";
	cout<<"Depth: "<<parent->depth<<"\n";
	displayBoard(parent->nBoard);
	cout<<"\n\n";
	cout<<"Children Nodes:\n";
	for(int dn=0; dn<9; dn++)
	{
		cout<<"Child Node "<<dn<<":\n";
		cout<<"Depth: ";
		cout<<parent->link[dn]->depth;
		displayBoard(parent->link[dn]->nBoard);
		cin.ignore();
	}
}

This thread reminds me of this one (on theprogrammingsite) . . . http://board.theprogrammingsite.com/...er=asc&start=0

I get one warning when I compile your code, on this line:

Code:

start->nBoard[3][3] = NULL;

Code:

107 C:\dwk\c\ttttemp.cpp [Warning] converting to non-pointer type `int' from NULL

I'm guessing you want to set each element in start->nBoard[][] to be set to zero. In that case, try memset:

Code:

memset(start->nBoard, 0, 3*3*sizeof(int));

Erhm, what's this for?

Code:

	//Create First Level
	int cDepth=1;
	addNodes(start, cDepth);
	copyParentBoard(start);
	cDepth++;

If you want the variable to retain its value between function calls, pass it to the function or make the variable static.

Here's what's causing this segmentation fault. displayPly() calls displayBoard() with an nBoard that has not been initialized.

Code:

//Display The Board Function
void displayBoard(int board[3][3])
{
	//Display The Board Function
	char piece[]="_XO";
	cout<<"\n\n";
	cout<<"\t   1  2  3\n";
	cout<<"\t   _  _  _\n";
	for(int c=0; c<3; c++)
	{
		cout<<"\t";
		cout<<(c+1)<<" ";
		for(int r=0; r<3; r++)
		{
			cout<<"|";
			cout<<piece[(board[c][r])];
			cout<<"|";
		}
		cout<<"\n";
	}
}

// ...

void displayPly(node *parent)
{
	cout<<"Parent Node Information:\n";
	cout<<"Depth: "<<parent->depth<<"\n";
	displayBoard(parent->nBoard);
	cout<<"\n\n";
	cout<<"Children Nodes:\n";
	for(int dn=0; dn<9; dn++)
	{
		cout<<"Child Node "<<dn<<":\n";
		cout<<"Depth: ";
		cout<<parent->link[dn]->depth;
		displayBoard(parent->link[dn]->nBoard);
		cin.ignore();
	}
}

In addNodes(), you need to have the memset call I mentioned above.

Code:

void addNodes(node *parent, int cDepth)
{
	//Add the 9 Nodes to the parent
	node *nNode[9];
	for(int n=0; n<9; n++)
	{
		nNode[n] = new node;
		nNode[n]->depth = cDepth;
		nNode[n]->parent = parent;
		parent->link[n] = nNode[n];
	}
}

Something like

Code:

memset(nNode[n]->nBoard, 0, 3*3*sizeof(int));

(This segfaults because you try to access an element in piece[] that is far beyond its end -- or even before the beginning because it is a signed int.)

I'm just curious as to why you have this

Code:

int nBoard[3][3];

in your structure when you have a global variable that is much the same thing.

Code:

int board[3][3] = {{EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}};

That could be initialized with memset BTW or like this:

Code:

int board[3][3] = {{0}};

This works because any initializers left out are automatically set to zero; since you want them to all be zero, you can leave (almost) all of the initalizers out.

Actually, global variables are automatically initialized to zero so you could just do this.

Code:

int board[3][3];

Okay... whoa, ha there's a lot there. Let me see here if i can clear things up.

Well the nBoard variable is in each node. It's the nodes board, how do i put this...

On the tree each node has a board, cause each node corresponds to a particular move in the game, so the idea i had was have each node have a board variable, and then have the nodes compare their 'theoretical' board to the actual board and make the appropriate move.

See what i'm saying?

thanks! i'll try the memset thingy. =)

well dwks knows i'm also doing some stuff with binary trees, and for those of you who connected the dots, ha yes i wanted to try to get binary trees down and then pretty much just soup that up to this tree i'm trying to implement

I dunno if that'll work or not, but i'll focus on getting the plain old binary tree down at the moment.

Thanks!

If you want a long read you could always read Prelude's article on Binary trees.
Part 1: http://eternallyconfuzzled.com/tuts/..._tut_bst1.aspx
Part 2: http://eternallyconfuzzled.com/tuts/..._tut_bst2.aspx
Part 3: http://eternallyconfuzzled.com/tuts/..._tut_bst3.aspx

yeah haha, i started on that and gave it a shot. It helped me understand a bit but... i was hoping for some source code for a full program which creates a tree. I learn a lot better from source code And explaination. Haha, but yeah i started reading the first one.