Cram (game): Difference between revisions
Mindmatrix (talk | contribs) typos, tweaks, and other cleanup |
Extended confirmed users 79,276 edits Expanding bare references using ReferenceExpander Tag: Reverted |
||
| Line 50: | Line 50: | ||
=== Known values === |
=== Known values === |
||
In 2009, Martin Schneider computed the Grundy values up to the 3 × 9, 4 × 5 and 5 × 7 boards.<ref name="Schneider"> |
In 2009, Martin Schneider computed the Grundy values up to the 3 × 9, 4 × 5 and 5 × 7 boards.<ref name="Schneider">{{Citation|last=Schneider|first=Martin|title=juvavum|date=2021-11-06|url=https://github.com/martinschneider/juvavum/blob/2b45ea43169d7f1057365526a1a4f2f46b6f8be8/juvavum_thesis.pdf|access-date=2023-02-12}}</ref> In 2010, Julien Lemoine and Simon Viennot applied to the game of Cram algorithms that were initially developed for the game of [[Sprouts (game)|Sprouts]].<ref>{{cite arXiv|first1=Lemoine|last1=Julien|first2= Viennot|last2=Simon|title=Nimbers are inevitable|year=2010|eprint=1011.5841|class=math.CO}}</ref> It allowed them to compute the Grundy values up to the 3 × 20, 4 × 9, 5 × 9, 6 × 7 and 7 × 7 boards.<ref name="sproutsWiki">{{Cite web|title=records [SproutsWiki]|url=http://sprouts.tuxfamily.org/wiki/doku.php?id=records#cram|access-date=2023-02-12|website=sprouts.tuxfamily.org}}</ref> |
||
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 show any apparent pattern. |
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 show any apparent pattern. |
||
Revision as of 12:17, 12 February 2023
Cram is a
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
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 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.
Symmetry play is a useless strategy in the misère version, because in that case it would only ensure the player that they lose.
Normal version
Grundy value
Since Cram is an
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 | ≥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 × 20, 4 × 9, 5 × 9, 6 × 7 and 7 × 7 boards.[4]
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 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 | ? | ? | ? |
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 adjacent table 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.
- .
- ^ a b Schneider, Martin (2021-11-06), juvavum (PDF), retrieved 2023-02-12
- ].
- ^ a b c "records [SproutsWiki]". sprouts.tuxfamily.org. Retrieved 2023-02-12.
- ^ John H., Conway (2000). On Numbers and Games. A K Peters, Ltd.