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

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

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! :-)

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.