Cram (game)
Cram - also known under the name Domino Juvavum and in the English-speaking world as plugg and dots-and-pairs - is a mathematical game that z. B. is played on squared or graph paper in a previously determined field of size n × m by both players alternately place one of their stones of size 2 × 1 (hence the name reference to the domino) horizontally or vertically on free fields of the playing field.
regulate
The game is played on squared or graph paper or on a chess field. The rectangular playing field size is determined before the start of the game. The playing field does not have to be square, it can even have a completely irregular shape.
Each of the two players has a set of pieces, each of which can cover exactly two fields that are adjacent to each other. In the picture the stones are colored red and blue to illustrate the sequence of moves; but they can also have the same color for both players. When it is a player's turn, he must place exactly one token, either horizontally or vertically, and neither exceeding the agreed edge of the field nor stacking it on an already occupied field. There is a compulsory setting; If a player cannot find two free spaces next to each other in this situation, he has lost in the normal variant. In the reverse variant, the inability to place a stone means victory.
Symmetrical game
The winning strategy for the normal variant on rectangular playing fields is simple if of the two dimensions ≥1 has an even number of fields: If both dimensions have an even number of fields, the second player wins by reciprocating the moves of his opponent in a rotationally symmetrical manner. In the other case, the first player wins by placing the first stone exactly in the middle of the playing field and thus creating a configuration in which he can reciprocate the following moves of his opponent in a rotationally symmetrical manner.
In the reverse variant, such a symmetrical game is pointless because there it would "secure" the defeat.
Normal variant
Grundy values
| n × m | 4th | 5 | 6th | 7th | 8th | 9 |
|---|---|---|---|---|---|---|
| 4th | 0 | 2 | 0 | 3 | 0 | 1 |
| 5 | - | 0 | 2 | 1 | 1 | ≥1 |
| 6th | - | - | 0 | > 3 | 0 | ≥1 |
| 7th | - | - | - | ≥1 | ≥1 | ? |
Since Cram is a neutral game , the Sprague-Grundy theorem states that in the normal variant, any position on the playing field is equivalent to a Nim pile of a certain size, which is also called the Grundy value . For two-dimensional even-numbered playing field sizes the basic y-value is 0, for m = 2 and odd n it is 1, for even m and odd n it is ≥1; for swapped values m and n the same applies.
Known values
In 2009, Martin Schneider calculated the Grundy values of the normal variant for playing fields up to the sizes 3 × 9, 4 × 5 and 5 × 7. In 2010, Julien Lemoine and Simon Viennot extended these results to 3 × 18, 4 × 9 and 5 × 8 by applying algorithms to cram that were originally developed for the game Sprouts . They were also able to calculate game results (but not Grundy values) for 5 × 9 and 7 × 7 fields.
The sequence of currently known Grundy values for playing fields of size 3 × n 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 and shows no recognizable regularity that would suggest further values.
The table shows the known Grundy values for playing fields that are greater than 3 in both dimensions. Since the matrix of the Grundy values is symmetrical with respect to their main diagonals, only the upper part of the table is given.
Reverse variant
Grundy values
| n × m | 4th | 5 | 6th | 7th | 8th | 9 |
|---|---|---|---|---|---|---|
| 4th | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | - | 2 | 1 | 1 | ? | ? |
| 6th | - | - | 1 | ? | ? | ? |
The inverse Grundy value of a field G was defined by Conway . Although it seems very similar to the Grundy value of the normal variant, it is not as powerful.
Known values
In 2009, Martin Schneider calculated the Grundy values of the reverse variant for playing fields up to the sizes 3 × 9, 4 × 6, and 5 × 5. In 2010 Julien Lemoine and Simon Viennot extended these results to 3 × 15, 4 × 9, 5 × 7 and 6 × 6.
The sequence of currently known Grundy values of the reverse variant for playing fields of size 3 × n from n = 1 to n = 15 is 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. It is assumed that this sequence can be continued with period 3.
The table shows the known Grundy values of the reverse variant for playing fields that are larger than 3 in both dimensions.
literature
- Conway : About numbers and games Vieweg Verlagsgesellschaft, ISBN 978-3-528-08434-9 (edition: 1983).
Individual evidence
- ↑ a b The game Juvavum ( Memento from March 10, 2012 in the Internet Archive ), Martin Schneider, Master's thesis, 2009
- ↑ Julien Lemoine, Simon Viennot, Nimbers are inevitable (2010) arXiv 1011.5841
- ↑ a b c Computation records of normal and misère Cram , website by Julien Lemoine and Simon Viennot