A concept in
GameTheory. Most often applied to two-player
PerfectInformationGames such as
TicTacToe, othello, checkers,
GameOfChess and
GameOfGo. The root of the tree is the starting point of the game. Each possible move (alternating players with each level) is represented by a branch, and each node in the tree represents an intermediate state of the game. The leaves are the final states of the game (which can be a win for player 1, a win for player 2 or a draw, if it is possible in that particular game).
Many computer programs use
GameTree searches to play such games. A trivial game such as
TicTacToe can, in fact, be solved by searching the
GameTree exhaustively. In more interesting games, the game tree is much, much, much too large. Instead, the program will just search a small part of the
GameTree. Most commonly, this involves only looking ahead a limited number of moves. A
BoardEvaluator evaluates the approximate strength of each player's position at that point in the game using some heuristic and assigns that position a value. Typically, +infinity if it is a guaranteed win for player 1, -infinity for a guaranteed win for player 2, zero for a guaranteed draw and some other value for other situations. At each level above this, the move is chosen which gets the best value for that player.
Further techniques (which vary depending on the game) can be used to reduce the search space further. Top level sorting searches the most promising moves first in the hope that they will find a quick positive end and short-circuit the rest of the search (
BranchPruning). Moves that seem unlikely to be useful can be discarded or searched more shallowly to leave time for more interesting paths. Opening or end game databases let the search skip past some levels of the tree.
The size of a
GameTree for a given game often represents the difficulty in making a strong computer opponent. It is trivial to make a perfect
TicTacToe computer program. Computers surpassed humans in their checkers ability nearly a decade ago, though it may be a long time (or never) before they play it perfectly (excluding smaller sized boards). Computers are just now starting to surpass grandmasters at the
GameOfChess, and will likely never be able to play perfect chess. In the
GameOfGo, an amateur human playing for less than a year can beat the best computer players. In fact, in Go, a global game-tree search is fruitless. The number of possible moves (361 at the start of the game) is too huge. At most,
GameTrees can be used to evaluate small, local situations, or maybe to evaluate the relative importance of a handful of regions on the board.
--
TomSchumm
As of August 11, 2008, headlines are being made that a computer (albeit with a handicap in it's favor) bested a professional Go player. Details:
http://www.techcentral.ie/article.aspx?id=12440
See also,
GameOfGo,
GameOfChess,
TicTacToe,
GameTheory
CategoryGame