Combinatorial game theory
From Simple English Wikipedia, the free encyclopedia
 |
The English used in this article may not be easy for everybody to understand. You can help Wikipedia by making this page or section simpler. |
Combinatorial game theory is a mathematical theory of games. It is sometimes called CGT. It is part of general game theory. It came from ideas from the solution to the game of Nim. It also partly came from looking at the oriental game Go.
CGT proves things about combinatorial games. A game must meet several conditions to be a combinatorial game. These are:
- The game has two players.
- The last player to move wins. If a player can not move on his turn, that player loses.
- Players alternate turns.
- The game has an end. It can not go on forever.
- The game can not end in a tie or draw.
- There is no information kept from the players (like there is in poker, for example)
- There are no chance moves. Luck is not a part of the game.
Very few of the games that people play for fun meet these conditions. For example, chess has draws.
These combinatorial games can be represented by trees, each vertice of which is the game resulting from a particular move from the game directly below it on the tree. These games can be assigned game values. Finding these game values is of great interests to CG theorists, as is the theoretical concept of game addition. The sum of two games is the game in which each player on her/his turn must move in only one of the two games, leaving the other as it was.
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.
[edit] 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. One could also, however, 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}. L are the games the left player can move to. R are the games the right player can move to. If you know chess notation, then the usual chess setup is the game
 |
The dots "..." mean there are many moves, so not all are shown.
Chess is very complex. It is better to think of easier games. Nim, for example, is much simpler to think about. Nim is played like this:
- There are zero or more piles of counters.
- On a turn, a player may take as many counters from one pile as that player wants.
- The player who cannot make a move loses.
The easiest game of Nim starts with no counters at all! In such a case, neither player can move. That is shown as {|}. Both sides are empty, because neither player can move. The first player to go cannot move, and so will lose. In CGT, people often write {|} as the symbol 0 (zero).
The next-easiest game has only one pile, with just one counter. If the left player goes first, that player must take the counter, leaving right with no moves ({|}, or 0). If instead right moves first, there will be no more moves for left. So both left and right can make a move to 0. That is shown as {{|}|{|}}, or {0|0}. The first player to move will win. Games equal to {0|0} are very important. They are written with the symbol, * (star).
