Bild 1
Bild 1 zeigt eine 4 × 10 - Matrix bei Spielbeginn. Beide Spieler nehmen abwechselnd Steine nach der folgenden Regel weg: Der Spieler am Zug entscheidet sich für einen der noch liegenden Steine (Ankerstein) und nimmt alle Steine weg, die in dem Rechteck liegen, das den Ankerstein als linke untere Ecke hat und das oben und rechts bis zum Spielfeldrand reicht. Als "legale" Spielsituationen entstehen so aus den noch liegenden Steinen "Treppen" von links oben nach rechts unten. Ein typisches Bild zeigt Bild 4 weiter unten. Dies führt zur ersten Frage in diesem Monatsproblem:
Wieviele solcher Treppen gibt es für ein n × m -Chomp-Spiel?
Ausgehend von Bild 1 sind in Bild 2 die beiden ersten Züge eines möglichen Spiels gezeigt. Der Anziehende nimmt die grün dargestellten Steine, der Nachziehende die roten. Die Ankersteine sind invertiert dargestellt.
Bild 2
Derjenige Spieler, der den Stein in der linken unteren Ecke des Spielfelds nimmt, hat verloren.
Überlegen Sie, warum die folgenden Gesetzmäßigkeiten gelten. Die beiden ersten sind ganz einfach:
1.
Liegt noch ein "L" auf dem Feld, also nur Spielsteine in der linken Spalte und der unteren Zeile, so gewinnt der Spieler am Zug genau dann, wenn das "L" verschieden lange Arme hat (siehe Bild 3).
Bild 3
Links: Spieler am Zug verliert. Rechts: Spieler am Zug gewinnt.
2.
Wenn kein "L" auf dem Feld liegt, aber gleich viele Steine (mehr als einer) in der linken Spalte wie in der unteren Zeile liegen, so gewinnt der Spieler, der am Zuge ist (siehe Bild 4). Eine Folge davon ist: Chomp auf quadratischen Spielfeldern ( n = m ) ist uninteressant.
Bild 4
Spieler am Zug gewinnt.
3.
Dies ist schon etwas schwerer: Liegen nur noch zwei gleich lange Zeilen oder zwei gleich lange Spalten von Steinen, so gewinnt der Spieler am Zuge (siehe Bild 5). Also ist Chomp auf zweireihigen Spielfeldern ( 2 × m oder n × 2 ) uninteressant. Die Gewinnstrategie beantwortet auch die allgemeinere Frage, in welchen Fällen der Spieler am Zuge oder sein Gegner bei zwei ungleich langen Zeilen oder Spalten gewinnt.
Bild 5
Spieler am Zug gewinnt.
4.
Es gibt eine Gewinnstrategie für den Anziehenden. Das heißt aber nicht, dass Chomp generell uninteressant wäre. Denn anscheinend kennt bisher niemand diese Strategie. Für genügend große Spielfelder (z.B. 12 × 16 ) hilft es wenig zu wissen, dass der Anziehende theoretisch gewinnt (d.h. wenn er keine Fehler macht).
Die Überlegung, warum es eine Gewinnstrategie für den Anziehenden gibt, ist eigentlich ganz einfach und sofort einsichtig, wenn man sie kennt. Diese Überlegung ist nicht "konstruktiv", d.h. sie beinhaltet nicht die Gewinnstrategie selbst. Da Chomp ein Spiel mit nur endlich vielen möglichen Spielabläufen ist, muss es entweder eine Gewinnstrategie für den Anziehenden oder eine für den Nachziehenden geben. Es reicht also, letzteres zu widerlegen. Wem dies noch nicht reicht, kann sich den Hinweis anschauen.
5.
Für "kleine" n × m -Matrizen ist der gewinnbringende Anfangszug eindeutig bestimmt. Erst beim 8 × 10 -Chomp hat man zwei gewinnbringende Züge für den Anziehenden gefunden. Beweisen Sie, dass für alle zweireihigen und alle quadratischen Chomp-Spiele der gewinnbringende Anfangszug eindeutig ist.
Zum Schluss sollen Sie ein konkretes Spiel analysieren, und zwar das kleinste Chomp-Spiel, das nicht durch die Ergebnisse aus 1.-3. abgedeckt ist:
Bestimmen Sie die Gewinnstrategie des Anziehenden für ein 3 × 4 - Spiel.