Tic-Tac-Toe AI: How to Make the Tree?

Question

I'm having a huge block trying to understand "trees" while making a Tic-Tac-Toe bot. I understand the concept, but I can't figure out to implement them.

Can someone show me an example of how a tree should be generated for such a case? Or a good tutorial on generating trees? I guess the hard part is generating partial trees. I know how to implement generating a whole tree, but not parts of it.

Answer 1

I don't think you need to keep a tree in memory. You simply need to implement a recursive function that works something like:

Move getBestMove(Board state, boolean myTurn)

Then you simply recurse until you've reached a winning, losing or draw-state.

The call-stack would over time look like a tree if you drew it on paper. You should return the move that leads to a node at which the opponent (definitely / most likely) looses (even though he also plays using getBestMove)

For a state-space as little as tic-tac-toe however, you could simply do a full look-up-table with the best moves! :-)

Answer 2

Imagine that at any point in a tic-tac-toe board, every single possible move is a branch. The current state of the board is the root. One move is a branch. Now pretend (one at a time), that each branch becomes the current state. Each possible move becomes a new branch. The leaf of the tree is when the last move is made and the board is full.

The reason you need to have a tree, is that once it is built, you need to figure out which branch has the most leaves that are 'WIN' scenarios. You build the branch of all possible outcomes, add up the total number of WINs, and then make the move that has the chance to end up with the most wins.

Make the tree something like this:

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

Now, you iterate through the list of branches in the tree, and for each branch, iterate through its branches. This can be done with a recursive function:

int recursiveTreeWalk( std::list< Node >& partialTree)
{

   for each branch in tree
       if node has no branches
           calculate win 1/0;
       else
           recursiveTreeWalk( branch );

   partialTree.m_winCount = sum of branch wins;
}

// initial call
recursiveTreeWalk( tree )

Very pseudo-code.

Answer 3

If you want to generate the tree in memory (which is not necessary), perhaps an algorithm like the following could be used (pseudo-code):

GenTree(State s):
  T <- empty tree  // T is a tree of States
  SetRoot(T, s)

  ForEach (s' in Successors(s)):
    AddChild(T, GenTree(s'))

  return T

// Call it
GenTree(currentMove)

where

Successors(s)  // returns a list of successor states of s
AddChild(p, n)  // adds n to the list of p's children

Answer 4

You might find this codeproject article interesting :

Solve Tic Tac Toe with the MiniMax algorithm

It's in C#, but it won't be any problem to adapt it in C++.

This article was also a good read for me when I tried to implement my first Tic-Tac-Toe game in C++ :

Minimax Explained