In AI search, we need a way of structuring the search space
so that we can traverse it systematically.
A common structure is a "tree".
Define a data structure with "parent" nodes
and "child" nodes beneath them, and child nodes beneath them, and so on.
Example with chess game:
The "parent" is the current state of the chess board.
The "children" are the immediate next moves.
Each "child" itself has "children" (moves from it) and so on.
Pick the best immediate "child" to move to.
This idea can be applied to many
problems, not just games.
With the "tree search" idea, do we have to draw tree graphs of every problem?
No.
You do not have to draw the graph:
The tree does not have to be actually drawn.
It can just be a data structure of Nodes linking to other Nodes
without any user interface.
You do not have to fully define the data structure:
As well as not drawing it, the data structure does not even have to be fully defined at the start (or at any point).
The children of a node can be calculated if and when that node is ever examined. Which may be never.
Example: Imagine each node is a state of the chess board.
Each child node is a possible next move from that state.
We calculate and examine the n possible next moves if and when that node is ever reached. Which may be never.
Trillions of possible nodes. But very few are ever put into the data structure.
And none are ever drawn.
Normally, we only draw the graph for debugging purposes.
Ancient Brain
