Combinatorial Game Theory

Combinatorial game theory (CGT) is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT does not study games with imperfect or incomplete information (sometimes called games of chance, like poker). It restricts itself to games whose position is public to both players, and in which the set of available moves is also public (perfect information). Combinatorial games include well-known games like chess, checkers, Go, Arimaa, Hex, and Connect6. They also include one-player combinatorial puzzles, and even no-player automata, like Conway's Game of Life. In CGT, the moves in these games are represented as a game tree.

Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real-life decision making situations. CGT has a different emphasis than "traditional" or "economic" game theory, which was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive-form game). Essentially, CGT contributed new methods for analyzing game trees, for example using surreal numbers, which are a subclass of all two-player perfect-information games. The type of games studied by CGT is also of interest in artificial intelligence, particularly for automated planning and scheduling. In CGT there has been less emphasis on refining practical search algorithms (like the alpha-beta pruning heuristic, included in most artificial intelligence textbooks today), but more emphasis on descriptive theoretical results, like measures of game complexity or proofs of optimal solution existence without necessarily specifying an algorithm (see strategy-stealing argument for instance).

An important notion in CGT is that of solved game (which has several flavors), meaning for example that one can prove that the game of tic-tac-toe results in a draw if both players play optimally. While this is a trivial result, deriving similar results for games with rich combinatorial structures is difficult. For instance, in 2007 it was announced that checkers has been (weakly, but not strongly) solved—optimal play by both sides also leads to a draw—but this result was a computer-assisted proof. Other real world games are mostly too complicated to allow complete analysis today (although the theory has had some recent successes in analyzing Go endgames). Applying CGT to a position attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is tortuously difficult unless the game is very simple.

Read more about Combinatorial Game TheoryHistory, Examples, Overview, Nimbers

Other articles related to "combinatorial game theory, game, games, theory, game theory":

Combinatorial Game Theory - Nimbers
... An impartial game is one where, at every position of the game, the same moves are available to both players ... For any ordinal number, one can define an impartial game generalizing Nim in which, on each move, either player may replace the number with any smaller ordinal number the games ... The Sprague–Grundy theorem states that every impartial game is equivalent to a nimber ...
John S. Conway - Achievements - Combinatorial Game Theory
... widely known for his contributions to combinatorial game theory (CGT), a theory of partisan games ... He also wrote the book On Numbers and Games (ONAG) which lays out the mathematical foundations of CGT ... He developed detailed analyses of many other games and puzzles, such as the Soma cube, peg solitaire, and Conway's soldiers ...
7 Colors
7 Colors (aka Filler) is a Computer strategy game/Puzzle game, designed by Dmitry Pashkov ... The game was published by Infogrames for MS DOS, Commodore Amiga, and NEC PC-9801 ...
Hackenbush
... Hackenbush is a two-player mathematical game that may be played on any configuration of colored line segments connected to one another by their endpoints and to the ground ... According to the normal play convention of combinatorial game theory, the first player who is unable to move (because either all segments have been ... Note that the existence of an infinite number of line segments does not violate the game theory assumption that the game can be finished in a finite ...
Game - Types - Simulation
... Main article Simulation game The term "game" can include simulation or re-enactment of various activities or use in "real life" for various purposes e.g ... Well-known examples are war games and roleplaying ... The root of this meaning may originate in the human prehistory of games deduced by anthropology from observing primitive cultures, in which children's ...

Famous quotes containing the words theory and/or game:

    No theory is good unless it permits, not rest, but the greatest work. No theory is good except on condition that one use it to go on beyond.
    André Gide (1869–1951)

    Even an attorney of moderate talent can postpone doomsday year after year, for the system of appeals that pervades American jurisprudence amounts to a legalistic wheel of fortune, a game of chance, somewhat fixed in the favor of the criminal, that the participants play interminably.
    Truman Capote (1924–1984)