Advertisement

tictactoe gametree

Started by November 17, 2005 10:07 AM
2 comments, last by alvaro 19 years ago
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

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; 
} 



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!
Advertisement
lol, i would have spent another week digging through my code without figuring that out!

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