Cram is a mathematical game played on a sheet of graph paper (or any type of grid). 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 . [1]
The game is played on a sheet of graph paper, with any set of designs traced out. It is most commonly played on rectangular board like a 6×6 square or a checkerboard, but it can also be played on an entirely irregular polygon or a cylindrical board.
Two players have a collection of dominoes which they place on the grid in turn. A player can place a domino either horizontally or vertically. Contrary to the related game of Domineering, the possible moves are the same for the two players, and Cram is then an impartial game.
As for all impartial games, there are two possible conventions for victory: in the normal game, the first player who cannot move loses, and on the contrary, in the misère version, the first player who cannot move wins.
The winning strategy for normal Cram is simple for even-by-even boards and even-by-odd boards. In the even-by-even case, the second player wins by symmetry play. This means that for any move by Player 1, Player 2 has a corresponding symmetric move across the horizontal and vertical axes. In a sense, player 2 'mimics' the moves made by Player 1. If Player 2 follows this strategy, Player 2 will always make the last move, and thus win the game.
In the even-by-odd case, the first player wins by similar symmetry play. Player 1 places their first domino in the center two squares on the grid. Player 2 then makes their move, but Player 1 can play symmetrically thereafter, thus ensuring a win for Player 1. [2]
Symmetry play is a useless strategy in the misère version, because in that case it would only ensure the player that they lose.
Since Cram is an impartial game, the Sprague–Grundy theorem indicates that in the normal version any Cram position is equivalent to a nim-heap of a given size, also called the Grundy value. Some values can be found in Winning Ways for your Mathematical Plays, in particular the 2 × n board, whose value is 0 if n is even and 1 if n is odd.
The symmetry strategy implies that even-by-even boards have a Grundy value of 0, but in the case of even-by-odd boards it only implies a Grundy value greater or equal to 1.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 2 | 0 | 3 | 0 | 1 |
| 5 | - | 0 | 2 | 1 | 1 | 1 |
| 6 | - | - | 0 | 5 | 0 | 1 |
| 7 | - | - | - | 1 | 3 | 1 |
In 2009, Martin Schneider computed the Grundy values up to the 3 × 9, 4 × 5 and 5 × 7 boards. [3] In 2010, Julien Lemoine and Simon Viennot applied to the game of Cram algorithms that were initially developed for the game of Sprouts. [4] It allowed them to compute the Grundy values up to the 3 × 20, 4 × 9, 5 × 9, 6 × 7 and 7 × 7 boards. [5] Piotr Beling extended these results up to the 6 × 9, 7 × 8, and 7 × 9 boards. [6]
The sequence of currently known Grundy values for 3 × n boards, from n=1 to n=20 is: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1, 0, 2. It doesn't appear to show any pattern.
The table below details the known results for boards with both dimensions greater than 3. Since the value of an n × m board is the same as the value of a m × n board, we give only the upper part of the table.
The misère Grundy-value of a game G is defined by Conway in On Numbers and Games as the unique number n such that G+n is a second player win in misère play. [7] Even if it looks very similar to the usual Grundy-value in normal play, it is not as powerful. In particular, it is not possible to deduce the misère Grundy value of a sum of games only from their respective misère Grundy values.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | - | 2 | 1 | 1 | ? | ? |
| 6 | - | - | 1 | ? | ? | ? |
In 2009, Martin Schneider computed the misère grundy values up to the 3 × 9, 4 × 6, and 5 × 5 board. [3] In 2010, Julien Lemoine and Simon Viennot extended these results up to the 3 × 15, 4 × 9 and 5 × 7 boards, along with the value of the 6 × 6 board. [5]
The sequence of currently known misère Grundy values for 3 × n boards, from n=1 to n=15 is: 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. This sequence is conjectured to be periodic of period 3. [5]
The adjacent table details the known misère results for boards with both dimensions greater than 3.
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.
Sprouts is an impartial paper-and-pencil game which can be analyzed for its mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s. The setup is even simpler than the popular dots and boxes game, but gameplay develops much more artistically and organically.
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.
TacTix is a two-player strategy game invented by Piet Hein, a poet well known for dabbling in math and science, best known for his game Hex.
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.
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.
Domineering 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 combination of any number of such components. Two players have a collection of dominoes which they place on the grid in turn, covering up squares. One player places tiles vertically, while the other places them horizontally. As in most games in combinatorial game theory, the first player who cannot move loses.
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", together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.
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.
In the mathematics of combinatorial games, the sum or disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. The sum game finishes when there are no moves left in either of the two parallel games, at which point the last player to move wins. This operation may be extended to disjunctive sums of any number of games, again by playing the games in parallel and moving in exactly one of the games per turn. It is the fundamental operation that is used in the Sprague–Grundy theorem for impartial games and which led to the field of combinatorial game theory for partisan games.
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.
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.
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. The game ends when all the boards contain a three-in-a-row of Xs, at which point the player to have made the last move loses the game. However, in this game, unlike tic-tac-toe, there will always be a player who wins any game of Notakto.
Tic-tac-toe is an instance of an m,n,k-game, where two players alternate taking turns on an m×n board until one of them gets k in a row. Harary's generalized tic-tac-toe is an even broader generalization. The game can also be generalized as a nd game. The game can be generalised even further from the above variants by playing on an arbitrary hypergraph where rows are hyperedges and cells are vertices.
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.