Overview

From root to the leaf,
Like sap in the veins of trees,
The search traverses

A tree is a data structure consisting of a hierarchy of linked nodes, starting with a root node which represents an initial state and branching out to subsequent child nodes representing alternate states and ending in leaf nodes that have no children nodes connected. A state represents the all encompassing state of the game, for example, a state in a game of chess will take into account; piece positions, taken pieces, which players turn it is and the time elapsed. Nodes can have none, one or more child nodes. Moving between the nodes represents an action that can be taken to move between states. A solution is a path between the root node and the goal node.

Simple example of how a tree structure can be visualised. A being the root node.

There are different forms of tree search algorithms commonly used that mainly differ in what branches of the structure are explored and in what order[1]. A search strategy is deemed complete if it is guaranteed to find a solution if one exists. Whereas it is considered optimal if it is guaranteed to find the best solution when several solutions exist [2].

Tree Search Algorithms

• Uninformed Searches
• Monte Carlo Tree Search
• Minimax
• Best First Search

References

[1] G. Yannakakis and J. Togelius, "Artificial intelligence and games.", Springer International Publishing, 2018.
[2]"Tree Search", How2examples.com, 2019. [Online]. Available: http://how2examples.com/artificial-intelligence/tree-search. [Accessed: 15- Feb- 2019].