Game Tree

A concept in GameTheory. Most often applied to two-player PerfectInformationGame?s 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

CategoryGame