**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 Theory: History, 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 ...

**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 (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 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 ...

... 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)