Heap Game
   HOME

TheInfoList



OR:

In
combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Research in this field has primarily focused on two-player games in which a ''position'' ev ...
, an impartial game is a
game A game is a structured type of play usually undertaken for entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator sports or video games) or art ...
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 th ...
,
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 ...
,
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), to ...
,
Subtract a square Subtract-a-square (also referred to as take-a-square) is a two-player mathematical subtraction game. It is played by two people with a pile of coins (or other tokens) between them. The players take turns removing coins from the pile, always removi ...
,
Notakto Notakto is a tic-tac-toe variant, also known as neutral or impartial tic-tac-toe. The game is a combination of the games tic-tac-toe and Nim, played across one or several boards with both of the players playing the same piece (an "X" or cross). ...
, and poset games. Go and
chess Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
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 Card game#Comparing games, comparing card games in which Card player, players betting (poker), wager over which poker hand, hand is best according to that specific game's rules. It is played worldwide, with varying rules i ...
,
dice A die (: dice, sometimes also used as ) is a small, throwable object with marked sides that can rest in multiple positions. Dice are used for generating random values, commonly as part of tabletop games, including dice games, board games, ro ...
or
dominos Dominoes is a family of tile-based games played with gaming pieces. 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 called '' pips'' or ''dots'') ...
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 ...
, 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 (not to be confused with Grundy chromatic numbers), are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordin ...
. 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, or the payoffs are not symmetric. Most games are partisan. For example, in chess, on ...
, though some partisan games can still be evaluated using nimbers such as Domineering. 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.


Heap game

Heap games are a subclass of impartial games that involve the disjunctive sum of various single-heap games. ''Single-heap positions'', or ''Γ-heaps'' are games represented naturally by the ordinal amount of a heap of tokens, where players play according to a specific ruleset on that single heap. Every option of a heap game must be representable as H^_ = H_ + H_ + H_ + ..., where each H^ is another heap game. The nim-value of a game is represented as the nim-addition of each heap in a heap game. Examples include: *
Octal games Octal games are a subclass of heap games that involve removing tokens (game pieces or stones) from heaps of tokens. They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games. Revised and reprinte ...
* Nim *
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 th ...


References


Further reading

*; ; *; ; ; ; {{cite book, title=vol. 4, isbn=1-56881-144-6, last1=Berlekamp, first1=Elwyn R., last2=Conway, first2=John Horton, last3=Guy, first3=Richard K., date=15 June 2004 Combinatorial game theory