Editing Combinatorial game theory (section)

==Overview==
A game, in its simplest terms, is a list of possible "moves" that two players, called ''left'' and ''right'', can make.  The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a [[recursion|recursive]] mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has the notation '''{L|R}'''.  L is the [[set (mathematics)|set]] of game positions that the left player can move to, and R is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation.

Using [[Domineering]] as an example, label each of the sixteen boxes of the four-by-four board by A1 for the upper leftmost square, C2 for the third box from the left on the second row from the top, and so on. We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner. Then, the initial position can be described in combinatorial game theory notation as

:<math>\{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}.</math>

In standard Cross-Cram play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within the game states.

:::[[Image:20x20square.png]][[Image:20x20square.png]]
:::[[Image:20x20square.png]]

:<math>\{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}.</math>

The above game describes a scenario in which there is only one move left for either player, and if either player makes that move, that player wins. (An irrelevant open square at C3 has been omitted from the diagram.) The <nowiki>{|}</nowiki> in each player's move list (corresponding to the single leftover square after the move) is called the [[zero game]], and can actually be abbreviated 0.  In the zero game, neither player has any valid moves; thus, the player whose turn it is when the zero game comes up automatically loses.

The type of game in the diagram above also has a simple name; it is called the [[star (game theory)|star game]], which can also be abbreviated ∗.  In the star game, the only valid move leads to the zero game, which means that whoever's turn comes up during the star game automatically wins.

An additional type of game, not found in Domineering, is a ''[[loopy game]]'', in which a valid move of either ''left'' or ''right'' is a game that can then lead back to the first game. [[Checkers]], for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares. A game that does not possess such moves is called ''loopfree''.

There are also ''transfinite'' games, which have infinitely many positions—that is, ''left'' and ''right'' have lists of moves that are infinite rather than finite.