In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation.
The first two plies of the game tree for tic-tac-toe.
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. The second player has two
choices for the reply if the first player played in the center,
otherwise five choices. And so on.
The number of leaf nodes in the complete game tree is the number of
possible different ways the game can be played. For example, the game
tree for tic-tac-toe has 255,168 leaf nodes.
1 Solving game trees
1.1 Deterministic algorithm version 1.2 Randomized algorithms version
2 See also 3 References 4 Further reading
Solving game trees Deterministic algorithm version
An arbitrary game tree that has been fully colored
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 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 Ο(n), the following randomized algorithm has an expected run time of θ(n0.792). 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): '''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 "OR" operator, then once one True is found, the root is classified as True; conversely, if the root node is considered an "AND" operator then once one False is found, the root is classified as False.
Extensive form game
^ Nau, Dana (1982). "An investigation of the causes of pathology in
games". Artificial Intelligence. 19: 257–278.
Victor Allis (1994). Searching for Solutions in Games and Artificial
Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht,
The Netherlands. ISBN 90-900748-8-0.
Hu, Te Chiang; Shing, Man-tak (2002). Combinatorial Algorithms. Courier Dover Publications. ISBN 0-486-41962-2. Retrieved 2007-04-02. Judea Pearl, Heuristics, Ad