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 diagram shows the first two levels, or *plies*, in the game tree for tic-tac-toe. We consider all the rotations and reflections of positions as being 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 26,830 leaf nodes.

Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using the minimax algorithm or its variants. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a **partial game tree**: typically as many plies from the current position as it can search in the time available. Except for the case of "pathological" game trees (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.

Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.

Read more about Game Tree: Solving Game Trees

### Other articles related to "game, game tree, games, tree, trees":

... textbooks, initially define the extensive-form

**game**as being just a

**game tree**with payoffs (no imperfect or incomplete information), and add the other elements in subsequent ... we present upfront the finite extensive-form

**games**as (ultimately) constructed here ... from Hart (1992), an n-player extensive-form

**game**thus consists of the following A finite set of n (rational) players A rooted

**tree**, called the

**game tree**Each terminal (leaf) node of the

**game tree**has ...

**Game Tree**s

... 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 ... 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 ... of the root node will determine the nature of the

**game**...

... introduced by George Stockman in 1979, that conducts a state space search traversing a

**game tree**in a best-first fashion similar to that of the A* search ... SSS* is based on the notion of solution

**trees**... Informally, a solution

**tree**can be formed from any arbitrary

**game tree**by pruning the number of branches at each MAX node to one ...

### Famous quotes containing the words tree and/or game:

“As a *tree* my sin stands

To darken all lands;

Death is the fruit it bore.”

—Christina Georgina Rossetti (1830–1894)

“A man’s idea in a card *game* is war—cruel, devastating and pitiless. A lady’s idea of it is a combination of larceny, embezzlement and burglary.”

—Finley Peter Dunne (1867–1936)