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

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, 开发者_如何学Pythonbut not parts of it.

---

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.

---

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

---

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

---

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

---

Implementing the Tic Tac Toe game is probably the simplest problem to solve in terms of AI and search space.

The key is to approach the problem with Minimax, Iterative deepening Depth-first search and Alpha-beta pruning algorithms.

Here's my implementation of the game in Python, which is only ~200 lines of code and has the capability to play a game as Human vs. Human, Human vs. Computer, and Computer vs. Computer. It also keeps the statistics on depths and number of nodes reached/pruned leading up to the best move.

I highly recommend edX.org Artificial Intelligence course, which gives the the fundamental knowledge on current AI topics and solutions.