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

Asked 2010-04-30T12:04:15.573

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.

Edit Report

1 Answer

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

answered 2010-04-30T12:24:44.647

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

1 Answer

Your Answer