Thread: Tic-Tac-Toe Game Tree

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    76

    Tic-Tac-Toe Game Tree

    Ok. I've come off about a 2 month break from programming all together, and I'm going to try at making an effective Tic-Tac-Toe game first with just 2 players, then later on to AI using the minimax game tree... or if any others that would be good for this type of game. Now, could someone explain to me how this game tree would go about in code? I've read about it's theory and nodes... but I've never practiced linked lists or what not. So this is my first try at nodes, children... all that stuff. How would code logic go with the tree below?

    http://upload.wikimedia.org/wikipedi...-game-tree.png

    So far, I've learned the minimax tree uses a point system to determine the winner of the game. The max player, usually the human player, tries to get the points from the tree to a positive number? Then the min player, usually the computer, tries to get the overall point total to a negative number? Each node represents a certain number total in the game?

    Any help would be appreciated...along with some code examples.
    Thank you.

  2. #2
    Registered User
    Join Date
    Aug 2006
    Posts
    74
    I know nothing about Minmax tree, but a linked list is just a series of nodes basically. A tree structure is based on this same principle, but instead of sequential items in a list/queue fashion each node can point to multiple children.

    Example of a combo:
    Code:
    #include <list>
    using std::list;
    
    struct node // Will represent each tree node.
    {
       // Put data variables here that would go in each node. Ex:
      int value;
    
      list <node> children; // Contains a list of all this node's children.
    }
    
    class Tree
    {
      public:
        Tree() 
       {
         treeRoot.value = 5; 
    
         node tempChild;
    
         tempChild.value = 3;   
         treeRoot.children.push_back(tempChild);  // Add this node to the children of treeRoot.
    
         tempChild.value = 1;
         treeRoot.children.push_back(tempChild);
       };
      private:
        node treeRoot; // Base of your tree.
    }
    I believe the above code as is would make the following tree:
    Code:
                  5
                 / \
                3   1
    Last edited by Kurisu33; 08-27-2006 at 02:25 AM.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    You might be able to find some information on aihorizon.com, such as google("site:aihorizon.com tic tac toe").
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tic Tac Toe game
    By nafix in forum C Programming
    Replies: 6
    Last Post: 11-10-2007, 01:45 PM
  2. tic tac toe crashes :(
    By stien in forum Game Programming
    Replies: 4
    Last Post: 05-13-2007, 06:25 PM
  3. 2D RPG Online Game Project. 30% Complete. To be released and marketed.
    By drallstars in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 10-28-2006, 12:48 AM
  4. Tic Tac Toe -- Can you guys rate this please?
    By Estauns in forum Game Programming
    Replies: 2
    Last Post: 09-15-2001, 10:22 AM
  5. not 3x3 tic tac toe game AI
    By Unregistered in forum Game Programming
    Replies: 9
    Last Post: 08-29-2001, 04:02 AM