Cram (Spiel)

Cram – auch unter dem Namen Domino Juvavum und im englischen Sprachraum als plugg und dots-and-pairs bekannt – ist ein mathematisches Spiel, das z. B. auf kariertem oder Millimeterpapier in einem vorher festgelegten Feld der Größe n × m gespielt wird, indem beide Spieler abwechselnd jeweils einen ihrer Steine der Größe 2×1 (daher der Namensbezug zum Domino) horizontal oder vertikal auf freien Felderns des Spielfeldes platzieren.

Das Spiel wird auf kariertem oder Millimeterpapier oder auch auf einem Schachfeld gespielt. Die rechteckige Spielfeldgröße wird vor Spielbeginn festgelegt. Das Spielfeld muss nicht quadratisch sein, kann sogar völlig unregelmäßige Form aufweisen.

Jeder der zwei Spieler hat einen Satz von Spielsteinen, von denen jeder genau zwei über Kante aneinander angrenzende Felder bedecken kann. In der Abbildung sind die Steine zur Veranschaulichung der Zugfolge rot und blau gefärbt; sie können aber auch für beide Spieler die gleiche Farbe aufweisen. Wenn ein Spieler an der Reihe ist, muss er genau einen Spielstein platzieren, und zwar horizontal oder vertikal, wobei weder der vereinbarte Spielfeldrand überschritten noch auf einem bereits belegten Feld gestapelt werden darf. Es besteht Setzpflicht; wenn ein Spieler in dieser Situation keine zwei nebeneinander liegenden freien Felder mehr findet, hat er in der normalen Variante verloren. In der umgekehrten Variante bedeutet die Unfähigkeit zur Platzierung eines Steins den Sieg.

Die Gewinnstrategie für die normale Variante auf rechteckigen Spielfeldern ist einfach, wenn von deren beiden Dimensionen ≥1 eine gerade Anzahl von Feldern aufweist: Weisen beide Dimensionen eine gerade Anzahl von Feldern auf, gewinnt der zweite Spieler durch rotationssymmetrische Erwiderung der Züge seines Gegenübers. Im anderen Fall gewinnt der erste Spieler, indem er den ersten Stein genau in der Mitte des Spielfelds platziert und damit eine Konfiguration schafft, in der er die folgenden Züge seines Gegenübers wiederum rotationssymmetrisch erwidern kann.

In der umgekehrten Variante ist solcherart symmetrisches Spiel sinnlos, weil es dort die Niederlage „sichern“ würde.

Da Cram ein neutrales Spiel ist, besagt der Satz von Sprague-Grundy, dass in der normalen Variante jegliche Position auf dem Spielfeld äquivalent ist zu einem Nim-Stapel einer bestimmten Größe, die auch Grundy-Wert genannt wird. Für zweidimensional geradzahlige Spielfeldgrößen ist der Grundy-Wert 0, für m=2 und ungerade n ist er 1, für gerade m und ungerade n ist er ≥1; für vertauschte Werte m und n gilt dasselbe.

2009 berechnete Martin Schneider die Grundy-Werte der normalen Variante für Spielfelder bis zu den Größen 3 × 9, 4 × 5 and 5 × 7.^[1] 2010 erweiterten Julien Lemoine und Simon Viennot diese Ergebnisse bis 3 × 18, 4 × 9 and 5 × 8, indem sie Algorithmen auf Cram anwendeten, die ursprünglich für das Spiel Sprouts entwickelt worden waren.^[2] Sie waren außerdem in der Lage, die Spielergebnisse (jedoch nicht die Grundy-Werte) für Spielfelder der Größe 5 × 9 and 7 × 7 zu berechnen.^[3]

Die Folge gegenwärtig bekannter Grundy-Werte für Spielfelder der Größe 3 × n von n=1 bis n=18 ist 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1 und weist keine erkennbare Regelmäßigkeit auf, die auf weitere Werte schließen ließe.

Die Tabelle zeigt die bekannten Grundy-Werte für Spielfelder, die in beiden Dimensionen größer als 3 sind. Da die Matrix der Grundy-Werte symmetrisch bezüglich ihrer Hauptdiagonalen ist, ist nur der obere Teil der Tabelle angegeben.

Der umgekehrte Grundy-Wert eines Spielfeldes G wurde durch Conway definiert. Obwohl er dem Grundy-Wert der normalen Variante sehr zu ähneln scheint, ist er nicht genauso mächtig.

2009 berechnete Martin Schneider die Grundy-Werte der umgekehrten Variante für Spielfelder bis zu den Größen 3 × 9, 4 × 6, and 5 × 5.^[1] 2010 erweiterten Julien Lemoine und Simon Viennot diese Ergebnisse bis 3 × 15, 4 × 9, 5 × 7 und 6 × 6.^[3]

Die Folge gegenwärtig bekannter Grundy-Werte der umgekehrten Variante für Spielfelder der Größe 3 × n von n=1 bis n=15 lautet 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. Man nimmt an, dass diese Folge mit der Periode 3 fortgesetzt werden kann.^[3]

Die Tabelle zeigt die bekannten Grundy-Werte der umgekehrten Variante für Spielfelder, die in beiden Dimensionen größer als 3 sind.

• Conway: Über Zahlen und Spiele Vieweg Verlagsgesellschaft, ISBN 978-3-528-08434-9 (Auflage: 1983).

1. ↑ ^{a b} Das Spiel Juvavum (Memento vom 10. März 2012 im Internet Archive), Martin Schneider, Master-Arbeit, 2009
2. ↑ Julien Lemoine, Simon Viennot, Nimbers are inevitable (2010) arXiv 1011.5841
3. ↑ ^{a b c} Computation records of normal and misère Cram, Website von Julien Lemoine und Simon Viennot