Game tree

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

, 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. The second player has two choices for the reply if the first player played in the center, otherwise five choices.

And so on. In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe.

A game tree can be used to measure the complexity of a game, as it represents all the possible ways that the game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees.

If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minmax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.

, 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. The second player has two choices for the reply if the first player played in the center, otherwise five choices.

And so on. In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe.

A game tree can be used to measure the complexity of a game, as it represents all the possible ways that the game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees.

If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minmax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.

Deterministic algorithm version

With a complete game tree, it is possible to "solve" the game – that is to say, find a sequence of moves that either the first or second player can follow that will guarantee the best possible outcome for that player (usually a win or a tie). The deterministic algorithm (which is generally called backward induction or retrograde analysis) can be described recursively as follows.

Color the final ply of the game tree so that all wins for player 1 are colored one way (Blue in the diagram), all wins for player 2 are colored another way (Red in the diagram), and all ties are colored a third way (Grey in the diagram). Look at the next ply up. If there exists a node colored opposite as the current player, color this node for that player as well.

If all immediately lower nodes are colored for the same player, color this node for the same player as well. Otherwise, color this node a tie. Repeat for each ply, moving upwards, until all nodes are colored.

The color of the root node will determine the nature of the game. The diagram shows a game tree for an arbitrary game, colored using the above algorithm.

It is usually possible to solve a game (in this technical sense of "solve") using only a subset of the game tree, since in many games a move need not be analyzed if there is another move that is better for the same player (for example alpha-beta pruning can be used in many deterministic games). Any subtree that can be used to solve the game is known as a decision tree, and the sizes of decision trees of various shapes are used as measures of game complexity.

Randomized algorithms version

Randomized algorithms can be used in solving game trees. There are two main advantages in this type of implementation: speed and practicality. Whereas a deterministic version of solving game trees can be done in , the following randomized algorithm has an expected run time of 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. The following is an implementation of randomized game tree solution algorithm: def gt_eval_rand(u) -> bool: """Returns True if this node evaluates to a win, otherwise False""" if u.leaf: return u.win else: random_children = (gt_eval_rand(child) for child in random_order(u.children)) if u.op

"OR": return any(random_children) if u.op

"AND": return all(random_children) The algorithm makes use of the idea of "short-circuiting": if the root node is considered an " " operator, then once one is found, the root is classified as ; conversely, if the root node is considered an " " operator then once one is found, the root is classified as .

See also

Alpha-beta pruning Extensive form game Shannon number Game complexity

Further reading

Judea Pearl, Heuristics, Addison-Wesley, 1984

Text derived from https://en.wikipedia.org/w/index.php?oldid=1304729341 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.