Iphone

I've been trying to teach myself some (simple!) AI and have done some studying on the above search techniques.

I think i can just about get the idea of the principles when faced with a diagram that "looks like" a tree i.e. with Nodes/Leafs etc but am getting horribly confused when trying to adapt it to a game of tic-tac-toe

My ultimate aim is to implement a MiniMax function, perhaps with Alpha/Beta pruning (if i can get that far!) but to start with - and considering the game tree is relatively small - i intend to just seach for all possible moves until the game is over.

However, i cant understand HOW the above techniques should be applied as i'm not really "searching", rather just generating every conceivable permutation of a 3x3 grid to find which ones are winners.

Given a tic-tac-toe board with squares numbered

012
345
678

On the first move,

For Breadth First Search, is the order of visiting each square before recursing to the next possible move 0-1-2-3-4-5-6-7-8 ??

Could it be 0-3-6? as all these possible squares (Nodes?) are at the same “level”?

For a Depth First Search, is it

0-3-6? If so, how does this compare to above?
0-3-7?

I suppose my main difficulty is that I don’t understand the concept of a “hierarchy” on this 3x3 grid.

Do I have to define some kind of tree structure before I can start searching?

If so, how are points 0 and 8 connected?

Anyhow, told you I was confused so any help, advice, web sites etc gratefully received.

Many thanks in anticipation

Iphone

Alright... (Sorry about my lag in my reply but life has been overly hectic and busy)

You will have to create your tree sort of like this:
root(All open moves)
0,1,2,3,4,5,6,7,8
then move down the tree (If you are familiar with trees you can point each leaf to the parent node and to each side by side leaf.

So then you point root to it's leaves aka 0,1,2,... Your linking of the tree is entirely up to you.

then move down a node:
0: then link all of it's leaves aka 1,2,3,4...

So you can travel down the tree from root to 0 then to any of the child leaves 1,2,3,4...

And the process repeats.

The other idea is you can link rows together too...
0
/ / | \ \
1-2-3-4-5....

You generate this with an array of moves, and as you move down a leaf. You toggle the array index to false so it can't be listed again. And generate your list that way.
Aka:
int row = 0;
parent = root;
//making row + 1
array[9] = {true, true, true...}
current = makenode(link up parent)
current set value(loop first true index of array)
update parent(link down current)
repeat for all true values
reset array move to first leaf, toggle leaf value to false and repeat with parent of leaf.

Do this for all of the leaves and nodes.

I hoped this helped out a lil.

I don't know how much you need help with the tree itself but that is the idea.