combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...

, an impartial game is a

game A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...

in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players. Impartial games include Nim, Sprouts,

Kayles Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns to knock out either one pin, or two adjacent pins, until all the pins are gone. Using the ...

Quarto Quarto (abbreviated Qto, 4to or 4º) is the format of a book or pamphlet produced from full sheets printed with eight pages of text, four to a side, then folded twice to produce four leaves. The leaves are then trimmed along the folds to produc ...

Cram Cram may refer to: * Cram (surname), a surname, and list of notable persons having the surname * Cram.com, a website for creating and sharing flashcards * Cram (Australian game show), a television show * ''Cram'' (game show), a TV game show that ...

Chomp Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it" (remove from the board), tog ...

, Subtract a square, Notakto, and poset games. Go and

chess Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...

are not impartial, as each player can only place or move pieces of their own color. Games such as

poker Poker is a family of comparing card games in which players wager over which hand is best according to that specific game's rules. It is played worldwide, however in some places the rules may vary. While the earliest known form of the game w ...

dice Dice (singular die or dice) are small, throwable objects with marked sides that can rest in multiple positions. They are used for generating random values, commonly as part of tabletop games, including dice games, board games, role-playing g ...

dominos Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...

are not impartial games as they rely on chance. Impartial games can be analyzed using the

Sprague–Grundy theorem In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...

, stating that every impartial game under the

normal play convention A normal play convention in a game is the method of determining the winner that is generally regarded as standard. For example: *Preventing the other player from being able to move *Being the first player to achieve a target *Holding the highest va ...

is equivalent to a

nimber In mathematics, the nimbers, also called ''Grundy numbers'', are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with ''nimber addition'' and ' ...

. The representation of this nimber can change from game to game, but every possible state of any variation of an impartial game board should be able to have some nimber value. For example, several nim heaps in the game nim can be calculated, then summed using nimber addition, to give a nimber value for the game. A game that is not impartial is called a

partisan game In combinatorial game theory, a game is partisan (sometimes partizan) if it is not impartial. That is, some moves are available to one player and not to the other. Most games are partisan. For example, in chess, only one player can move the white ...

, though some partisan games can still be evaluated using nimbers such as

Domineering Domineering (also called Stop-Gate or Crosscram) is a mathematical game that can be played on any collection of squares on a sheet of graph paper. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular polyomino, or a ...

. Domineering would not be classified as an impartial game as players use differently acting pieces, one player with vertical dominoes, one with horizontal ones, thereby breaking the rule that each player must be able to act using the same operations.

Requirements

All impartial games must meet the following conditions: * Two players must alternate turns until a final state is reached. * A winner is chosen when one player may no longer change position or make any operation. * There must be a finite number of operations and positions for both players. For example, in Nim, players must take away a subset of a stack that is currently in play. As there is a finite number of coins in any stack, a player may only remove a finite number of coins. * All operations must be able to be done by both sides. In all Impartial games, the players are making actions to some game board whether in the form of stacks for Nim or rows and columns Cram. Both players are acting on the board till the board can no longer change in some way. * No action in the game may be reliant on chance. Any inclusion of chance would mean there is not perfect information about the game, furthermore actions could not be minmaxed ruling out any form inductive strategy.

Requirements

References

Further reading