Searching For Depth and Breadth First

[Segvoia]

hello

I suppose my main difficulty is that I don’t understand the concept of a “hierarchy” on this 3x3 grid.
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.

Please help me in understanding 3 X 3 grid

[opaper]

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.

[MindSpace]

BFS is an uninformed search method that aims to expand and examine all nodes of a graph or combinations of sequence by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it. It does not use a heuristic.

From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed".

[Modifier]

In a connected graph, you can always reach all nodes (or vertices) starting from any given node (called the root) by traversing edges. When traversing an edge from one node to another, the first is typically referred to as the "parent", and the second as the "child". Two commonly used graph traversal methods are called "breadth first" and "depth first".

The root node is the one that is initially green. As the search encounters new nodes, they become green as well. In a breadth-first traversal, you start at the root and visit all of its children in some order. Each child is marked as having been visited. Next, a child is selected and all of its children (that is, grandchildren of the root) are visited, except those, if any, that are marked. This is repeated for the other children of the root. When that is finished, a grandchild is selected, etc. The traversal terminates when all nodes have been marked.
A depth-first search is done by visiting a child node (and marking it), from there selecting a grandchild, visiting and marking it, etc. Each such branch of the search concludes when there is no unmarked child to search. At that stage, you return to the parent of the last child visited, select another unvisited child, traverse to that child, and repeat. If there is no such unvisited child, you continue back up the "parent chain" until one is found with an unvisited child, whereupon you recursively visit that child in depth-first fashion.
In practice, depth-first searches are often implemented with a stack data structure. This allows the program to keep a record of children yet to be visited, in LIFO (last in, first out) order. Breadth-first searches can be accomplished using a queue structure to enforce their FIFO (first in, first out) nature.
Note that once completed, a search gives a "spanning tree", that is, a tree emanating from the root node and hitting all other nodes.