Game tree

If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used.

[2] The diagram shows the first two levels, or plies, in the game tree for tic-tac-toe.

The rotations and reflections of positions are equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner.

Except for the case of "pathological" game trees[3] (which seem to be quite rare in practice), increasing the search depth (i.e., the number of plies searched) generally improves the chance of picking the best move.

The deterministic algorithm (which is generally called backward induction or retrograde analysis) can be described recursively as follows.

Whereas a deterministic version of solving game trees can be done in Ο(n), the following randomized algorithm has an expected run time of θ(n0.792) if every node in the game tree has degree 2.

Moreover, it is practical because randomized algorithms are capable of "foiling an enemy", meaning an opponent cannot beat the system of game trees by knowing the algorithm used to solve the game tree because the order of solving is random.