void TTTTreeNode::init(char cCurrentplayer) {
TTTBoard* pBoard;
TTTTreeNode* pTTTTreeNode;
// change Player
this->cPlayer = (cCurrentplayer==PLAYER_1)?PLAYER_2:PLAYER_1;
// Game over, no more successors
if (this->board->isFilled()) return;
if (this->board->isWon()) return;
// Still possible moves
for (int iy=0; iy<BOARD_Y;++iy) {
for (int ix=0; ix<BOARD_X;++ix) {
pTTTTreeNode = NULL;
// find emtpy field
if (this->board->getField(ix, iy)==NULL) {
// crate new Board, idetically to the one stored in this node
pBoard = new TTTBoard(this->board);
// player sets stone
pBoard->setStone(this->cPlayer, ix, iy);
// create a new Node with the new board
pTTTTreeNode = new TTTTreeNode(pBoard);
// get the new node initialised
pTTTTreeNode->init(this->cPlayer);
}
this->attach(((iy*BOARD_Y)+ix), pTTTTreeNode);
}
}
}
int TTTTreeNode::count() {
int count = 1;
for (unsigned int i=0; i<this->successors.size();++i) {
if (this->successors!=NULL) count = count + this->successors->count();
}
return count;
}
tictactoe gametree
Hi!
I have Problems creating my gametree for TicTacToe
(this ganme:
X|0|0
-+-+-
0|X|X
-+-+-
X|X|0)
I´m using th class TTTTreeNode with the following funtions
The maximum amount of nodes in TiTacToeis imho 9! (= 362.880)
Some of the nodes contain win-situations therefore have no more sucessors.
As for this, the tree should contain less than 9! nodes.
I don´t use symetry or other optimisation
When I call init() from my root-node with an empty board, I get a tree that consists of 549946 nodes.
So eather the count()-method gives me a wrong number, or I made an error in the init-function.
Anyone sees the mistake?
Quote: Original post by davethebrave
The maximum amount of nodes in TiTacToeis imho 9! (= 362.880)
Some of the nodes contain win-situations therefore have no more sucessors.
As for this, the tree should contain less than 9! nodes.
...
Anyone sees the mistake?
Well, without looking at your code, I think this assumption is your mistake.
Think about it:
# of nodes Level 1: 9
# of nodes Level 2: 9*8
# of nodes Level 3: 9*8*7
...
# of nodes Level 9: 9!
Adding all those together, though, gives you a total number of nodes in your tree much greater than 9!
lol, i would have spent another week digging through my code without figuring that out!
thx a lot!
thx a lot!
This comment is a little off-topic, but I thought it should be mentioned that the number of nodes is much smaller if you consider transpositions. Notice that 3^9 = 19683 is small enough that you can keep a table of that size easily. A nice way of writing a tic-tac-toe program is to compute the scores of all the positions at initialization (it should take less than a second these days) and then just use the lookup table when playing.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement