Cram (game)
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.[1]
Rules
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.
Symmetry play
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 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.
Normal version
Grundy value
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 | >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.[2] In 2010, Julien Lemoine and Simon Viennot applied to the game of Cram algorithms that were initially developed for the game of Sprouts.[3] 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.[4]
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 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.
Misère version
Misère Grundy-value
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.[5] 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 | ? | ? | ? |
Known values
In 2009, Martin Schneider computed the misère grundy values up to the 3 × 9, 4 × 6, and 5 × 5 board.[2] 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.[4]
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.[4]
The table on the right details the known misère results for boards with both dimensions greater than 3.
References
- Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Winning Ways for Your Mathematical Plays. A K Peters, Ltd.
- ↑ Gardner, Martin (1974). "Mathematical Games: Cram, crosscram and quadraphage: new games having elusive winning strategies". Scientific American 230 (2): 106–108.
- 1 2 Das Spiel Juvavum, Martin Schneider, Master thesis, 2009
- ↑ Julien, Lemoine; Simon, Viennot (2010). "Nimbers are inevitable". arXiv:1011.5841 [math.CO].
- 1 2 3 Computation records of normal and misère Cram, Julien Lemoine and Simon Viennot web site
- ↑ John H., Conway (2000). On Numbers and Games. A K Peters, Ltd.