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. Game theory is a branch of applied mathematics that studies strategic situations where players choose different actions in an attempt to maximize their returns. ... This article just presents the basic definitions. ... This article just presents the basic definitions. ... This article is about a recreational activity. ... This article just presents the basic definitions. ...

The first two ply of the game tree for tic-tac-toe.

The diagram shows the first two levels, or ply, 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 centre, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the centre, otherwise five choices. And so on. First two ply of a game tree for tic-tac-toe. ... First two ply of a game tree for tic-tac-toe. ... In chess, ply refers to a half-move: one turn of one of the players. ... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ...

The number of leaf nodes in the complete game tree is called the game tree complexity. It is the number of possible different ways the game can be played. The game tree complexity for tic-tac-toe is 26,830. In computer science, a leaf node is a node of a tree data structure that has zero child nodes. ... In game theory, game complexity is a measure of the complexity of a game. ...

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 ply from the current position as it can search in the time available. Hondas intelligent humanoid robot Artificial intelligence (AI) is defined as intelligence exhibited by an artificial entity. ... Minimax (sometimes minmax) is a method in decision theory for minimizing the maximum possible loss. ... Chess is an abstract strategy board game for two players. ...

Solving Game Trees

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 either a win or tie. The algorithm can be described recursively as follows.

1. Color the final ply of the game tree so that all wins for player 1 are colored one way, all wins for player 2 are colored another way, and all ties are colored a third way.
2. 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.
3. 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 following diagram shows a game tree for an arbitrary game, colored using the above algorithm. Image File history File links I created this image to depict an arbirtary game tree being solved, for the purposes of illustrating this proccess. ...

See also

• Alpha-beta pruning