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