Bleib

„Chomp“ ist ein Strategiespiel für zwei Spieler, das auf einem rechteckigen Raster aus Feldern gespielt wird, das oft als Schokoladentafel dargestellt wird. Die Spieler „fressen“ abwechselnd ein Feld sowie alle Felder oberhalb und rechts davon. Das Feld in der unteren linken Ecke ist „vergiftet“ – der Spieler, der gezwungen ist, es zu fressen, verliert. Trotz seiner einfachen Regeln weist Chomp tiefgreifende mathematische Eigenschaften auf und steht in Zusammenhang mit wichtigen Konzepten der kombinatorischen Spieltheorie.

Spielregeln

1. Das Spiel beginnt mit einem rechteckigen Raster (z. B. 5×4), das als in Quadrate unterteilte Schokoladentafel dargestellt wird.
2. Die Spieler sind abwechselnd am Zug.
3. In jedem Zug wählt ein Spieler ein beliebiges verbleibendes Feld aus. Dieses Feld sowie alle Felder darüber und rechts davon werden entfernt („gegessen“).
4. Das Feld unten links ist vergiftet (oft mit einem Totenkopf oder einer anderen Farbe markiert).
5. Der Spieler, der gezwungen ist, das vergiftete Feld zu essen, verliert.

Strategien

• Der erste Spieler gewinnt: Es wurde mathematisch bewiesen (mit einem Argument des „Strategie-Stehlens“), dass der erste Spieler auf jedem rechteckigen Raster, das größer als 1×1 ist, immer eine Gewinnstrategie hat. Der Beweis ist jedoch nicht konstruktiv – er beweist, dass eine Gewinnstrategie existiert, ohne zu verraten, wie diese aussieht.
• Eröffnung durch „Eckhappen“: Im ersten Zug ist es oft eine starke Eröffnung, nur das Feld in der oberen rechten Ecke zu essen, da dies maximale Flexibilität bewahrt.
• L-förmige Positionen: Wenn die verbleibenden Felder eine L-Form mit gleich langen Schenkeln bilden, ist die Position für den Spieler, der am Zug ist, oft verloren.
• Symmetriestrategie: Auf quadratischen Spielfeldern (NxN) kann der erste Spieler gewinnen, indem er im ersten Zug das Feld in der oberen rechten Ecke frisst und anschließend die Züge des Gegners spiegelt. Auf rechteckigen Spielfeldern funktioniert dies nicht.
• Auswendiglernen kleiner Spielfelder: Bei kleinen Spielfeldern (bis zu 5x4) lassen sich Gewinn- und Verlustpositionen durch eine vollständige Analyse des Spielbaums auswendig lernen.
• Optionen einschränken: Versuche, deinen Gegner in Positionen mit wenigen verbleibenden Feldern zu bringen, um ihn in die „vergiftete Ecke“ zu drängen.

Chomp wurde unabhängig voneinander vom Mathematiker David Gale im Jahr 1974 und von Fred Schuh im Jahr 1952 erfunden (der es in seinem niederländischsprachigen Buch über mathematische Spiele anders nannte). Gale veröffentlichte das Spiel im „American Mathematical Monthly“, wo es schnell die Aufmerksamkeit von Mathematikern und Spieltheoretikern auf sich zog.

Die bekannteste mathematische Eigenschaft des Spiels ist sein Beweis des „Strategiediebstahls“. Die Argumentation lautet: Wenn der erste Spieler keine Gewinnstrategie hat, dann hat der zweite Spieler eine. Doch der erste Spieler könnte bei seinem ersten Zug immer nur das Feld in der rechten oberen Ecke essen – wenn der zweite Spieler dann eine gewinnbringende Antwort hat, hätte der erste Spieler stattdessen denselben Zug als ersten Zug machen können. Dieser Widerspruch beweist, dass der erste Spieler eine Gewinnstrategie haben muss. Dieser Beweis sagt jedoch nichts darüber aus, wie diese Strategie tatsächlich aussieht.

Bei nicht quadratischen rechteckigen Gittern bleibt die Ermittlung der optimalen Strategie ein offenes Problem der Mathematik. Zwar haben Computer kleine Gitter erschöpfend durchgespielt, doch ist keine allgemeine Formel bekannt. Dies macht „Chomp“ zu einem der am einfachsten zu formulierenden ungelösten Probleme der kombinatorischen Spieltheorie.

Chomp weist tiefe Verbindungen zu anderen Bereichen der Mathematik auf, darunter teilweise geordnete Mengen (Posets) und Teiler-Gitter. Eine Variante namens „Schurs Spiel“ oder „Divisor Chomp“ ersetzt das rechteckige Gitter durch Teiler einer Zahl – die Spieler wählen einen Teiler und entfernen alle seine Vielfachen. Das Spiel wurde an Universitäten als Lehrmittel eingesetzt, um Studierenden die Spieltheorie, Beweistechniken und die rechnerische Komplexität näherzubringen.