The Combinatorial game theory reference article from the Simple Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

# Combinatorial game theory

Videos show Africa through the eyes of children
Combinatorial game theory is a mathematical theory of games. It is sometimes called CGT. It is part of general game theory. It grew out of ideas from the solution to the game of Nim.

CGT proves things about certain two player games. These games can be reduced to tree-like structures. Players take turns making moves. A player loses the game if there is no move on their turn. It may seem like there are few interesting games like that. However, a large number of new and old games can be analyzed with the theory. It partly grew out of looking at the oriental game Go.

Elwyn Berlekamp, John Conway and Richard Guy are the founders of the theory. They worked together in the 1960s. Their published work was called Winning Ways for Your Mathematical Plays.

## Definitions

In the theory, there are two players called left and right. A game is something that allows left and right to make moves to other games. For example, in the game of chess, there is a usual starting setup. However, one could also think of a chess game after the first move as a different game, with a different setup. So each position is also called a game.

Games have the notation {L|R}. are the games the left player can move to. are the games the right player can move to. If you know chess notation, then the usual chess setup is the game

The dots "..." indicate there are many moves, so we do not show them all.

Chess is very complex. It is nicer to think of much easier games. Nim is much simpler to analyze. Nim is played like this:

1. There are zero or more piles of counters.
2. On a turn, a player may take as many counters as they like from one pile.
3. The player who cannot make a move, loses.

The easiest game of nim starts with no counters at all! Then, neither player can move. This is shown as
> as the symbol 0 (zero).

The next easiest game has only one pile, with just one counter. If the left player goes first, they must take this counter, leaving right with no moves (
>|{|}}, or {0|0}. The first player to move will win. Games equal to {0|0} are very important. We write them with the symbol, * (star).