Game tree
In game theory, a game tree is a directed graph whose nodess are positions in a game and whose edgess 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 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. 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. 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.
|
|
