Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two and smaller remain, none of which can be split unequally. The game is usually played as a normal play game, which means that the last person who can make an allowed move wins.
A normal play game starting with a single heap of 8 is a win for the first player provided they start by splitting the heap into heaps of 7 and 1:
player 1: 8 → 7+1
Player 2 now has three choices: splitting the 7-heap into 6 + 1, 5 + 2, or 4 + 3. In each of these cases, player 1 can ensure that on the next move he hands back to his opponent a heap of size 4 plus heaps of size 2 and smaller:
player 2: 7+1 → 6+1+1 player 2: 7+1 → 5+2+1 player 2: 7+1 → 4+3+1 player 1: 6+1+1 → 4+2+1+1 player 1: 5+2+1 → 4+1+2+1 player 1: 4+3+1 → 4+2+1+1
Now player 2 has to split the 4-heap into 3 + 1, and player 1 subsequently splits the 3-heap into 2 + 1:
player 2: 4+2+1+1 → 3+1+2+1+1 player 1: 3+1+2+1+1 → 2+1+1+2+1+1 player 2 has no moves left and loses
The game can be analysed using the Sprague–Grundy theorem. This requires the heap sizes in the game to be mapped onto equivalent nim heap sizes. This mapping is captured in the On-Line Encyclopedia of Integer Sequences as OEIS: A002188 :
Heap size : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... Equivalent Nim heap : 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ...
Is the nim-sequence of Grundy's game eventually periodic?
Using this mapping, the strategy for playing the game Nim can also be used for Grundy's game. Whether the sequence of nim-values of Grundy's game ever becomes periodic is an unsolved problem. Elwyn Berlekamp, John Horton Conway and Richard Guy have conjectured [1] that the sequence does become periodic eventually, but despite the calculation of the first 235 values by Achim Flammenkamp, the question has not been resolved.
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.
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 a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.
In combinatorial game theory, an impartial game is a game 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.
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 nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.
Winning Ways for Your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games. It was first published in 1982 in two volumes.
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 take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.
In combinatorial game theory, a game is partisan if it is not impartial. That is, some moves are available to one player and not to the other.
In combinatorial game theory, the zero game is the game where neither player has any legal options. Therefore, under the normal play convention, the first player automatically loses, and it is a second-player win. The zero game has a Sprague–Grundy value of zero. The combinatorial notation of the zero game is: { | }.
Hexapawn is a deterministic two-player game invented by Martin Gardner. It is played on a rectangular board of variable size, for example on a 3×3 board or on a regular chessboard. On a board of size n×m, each player begins with m pawns, one for each square in the row closest to them. The goal of each player is to either advance a pawn to the opposite end of the board or leave the other player with no legal moves, either by stalemate or by having all of their pieces captured.
Hackenbush is a two-player game invented by mathematician John Horton Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.
In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set.
Subtract-a-square is a two-player mathematical subtraction game. It is played by two people with a pile of coins between them. The players take turns removing coins from the pile, always removing a non-zero square number of coins. The game is usually played as a normal play game, which means that the player who removes the last coin wins. It is an impartial game, meaning that the set of moves available from any position does not depend on whose turn it is. Solomon W. Golomb credits the invention of this game to Richard A. Epstein.
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 notation of octal games, Kayles is denoted 0.77.
The octal games are a class of two-player games that involve removing tokens from heaps of tokens. They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games.
Cram is a mathematical game played on a sheet of graph paper. It is the impartial version of Domineering and the only difference in the rules is that players may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by Geoffrey Mott-Smith, and "dots-and-pairs". Cram was popularized by Martin Gardner in Scientific American.
In the mathematical theory of games, genus theory in impartial games is a theory by which some games played under the misère play convention can be analysed, to predict the outcome class of games.
In combinatorial game theory, and particularly in the theory of impartial games in misère play, an indistinguishability quotient is a commutative monoid that generalizes and localizes the Sprague–Grundy theorem for a specific game's rule set.
In combinatorial game theory, poset games are mathematical games of strategy, generalizing many well-known games such as Nim and Chomp. In such games, two players start with a poset, and take turns choosing one point in the poset, removing it and all points that are greater. The player who is left with no point to choose, loses.
Patrick Michael Grundy was an English mathematician and statistician. He was one of the eponymous co-discoverers of the Sprague–Grundy function and its application to the analysis of a wide class of combinatorial games.
In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses. Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.