Cram (games)
Encyclopedia
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 each player 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
.
, 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.
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 whichever move Player 1 makes, 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 his first domino in the center two squares on the grid. Player 2 then makes his move, but Player 1 can play symmetrically thereafter, thus ensuring a win for Player 1.
It should be noted that symmetry play is a useless strategy in the misère version, because in that case it would only ensure the player that he loses.
, 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.
. It allowed them to compute the grundy-values up to the 3 × 18, 4 × 9 and 5 × 8 boards. They were also able to compute the outcome (but not the grundy-value) of the 5 × 9 and 7 × 7 boards.
The sequence of currently known Grundy values for 3 × n boards, from n=1 to n=18 is: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1. It doesn't show any apparent pattern.
The table below details the known results for boards with both dimensions greater than 4. 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.
in On Numbers and Games
as the unique number n such that G+n is a second player win in misère play. Even if it looks very similar to the usual Grundy-value in normal play, it is not as much 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.
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.
The table on the right details the known misère results for boards with both dimensions greater than 4.
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
played on a sheet of graph paper
Graph paper
Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting mathematical functions or experimental data and drawing diagrams. It is commonly found in mathematics and...
. It is the impartial version of Domineering
Domineering
Domineering is a mathematical game played on a sheet of graph paper, with any set of designs traced out. For example, it can be played on a 6×6 square, a checkerboard, an entirely irregular polygon, or any combination thereof. Two players have a collection of dominoes which they place on the grid...
and the only difference in the rules is that each player 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
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
in Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
.
Rules
The game is played on a sheet of graph paperGraph paper
Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting mathematical functions or experimental data and drawing diagrams. It is commonly found in mathematics and...
, with any set of designs traced out. It is most commonly played on rectangular board like a 6×6 square or a checkerboard
Checkerboard
A checkerboard or chequerboard is a board of chequered pattern on which English draughts is played. It is an 8×8 board and the 64 squares are of alternating dark and light color, often red and black....
, but it can also be played on an entirely irregular polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
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
Domineering
Domineering is a mathematical game played on a sheet of graph paper, with any set of designs traced out. For example, it can be played on a 6×6 square, a checkerboard, an entirely irregular polygon, or any combination thereof. Two players have a collection of dominoes which they place on the grid...
, the possible moves are the same for the two players, and Cram
Cram
Cram may refer to:* Cram , a surname, and list of notable persons having the surname* Cram , a TV game show that aired on the Game Show Network* Cram , a fictional type of bread in J. R. R...
is then an impartial game
Impartial game
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...
.
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.
Symmetry play
The winning strategyStrategy
Strategy, a word of military origin, refers to a plan of action designed to achieve a particular goal. In military usage strategy is distinct from tactics, which are concerned with the conduct of an engagement, while strategy is concerned with how different engagements are linked...
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
Symmetry
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
play. This means that whichever move Player 1 makes, 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 his first domino in the center two squares on the grid. Player 2 then makes his move, but Player 1 can play symmetrically thereafter, thus ensuring a win for Player 1.
It should be noted that symmetry play is a useless strategy in the misère version, because in that case it would only ensure the player that he loses.
Grundy value
Since Cram is an impartial gameImpartial game
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...
, the Sprague–Grundy theorem
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 nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to...
indicates that in the normal version any Cram position is equivalent to a nim-heap
Nim
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. 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....
of a given size, also called the Grundy value. Some values can be found in Winning Ways for your Mathematical Plays
Winning Ways for your Mathematical Plays
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...
, 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 | >3 | 0 | ≥1 |
| 7 | - | - | - | ≥1 | ≥1 | ? |
Known values
In 2009, Martin Schneider computed the grundy values up to the 3 × 9, 4 × 5 and 5 × 7 boards. In 2010, Julien Lemoine and Simon Viennot applied to the game of Cram algorithms that were initially developed for the game of SproutsSprouts (game)
Sprouts is a pencil-and-paper game with interesting mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967.- Rules :...
. It allowed them to compute the grundy-values up to the 3 × 18, 4 × 9 and 5 × 8 boards. They were also able to compute the outcome (but not the grundy-value) of the 5 × 9 and 7 × 7 boards.
The sequence of currently known Grundy values for 3 × n boards, from n=1 to n=18 is: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1. It doesn't show any apparent pattern.
The table below details the known results for boards with both dimensions greater than 4. 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.
Misère Grundy-value
The misère Grundy-value of a game G is defined by ConwayJohn Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
in On Numbers and Games
On Numbers and Games
On Numbers and Games is a mathematics book by John Horton Conway. The book is a serious mathematics book, written by a pre-eminent mathematician, and is directed at other mathematicians...
as the unique number n such that G+n is a second player win in misère play. Even if it looks very similar to the usual Grundy-value in normal play, it is not as much 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 | ? | ? | ? |
Known values
In 2009, Martin Schneider computed the misère grundy values up to the 3 × 9, 4 × 6, and 5 × 5 board. 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.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.
The table on the right details the known misère results for boards with both dimensions greater than 4.