imported>SchlurcherBot: Bot: http → https

2025-12-10T18:41:27Z

Bot: http → https

Neue Seite

'''Chomp''' ist ein 2-Personen-Spiel, das mit Papier und Bleistift gespielt werden kann.

== Name und Regel ==

Das Spielfeld ist ein Rechteck, eingeteilt in ein Raster gleich großer Felder. Die Ähnlichkeit mit einer Schokoladentafel hat dem Spiel seinen Namen gegeben, denn das englische Verb ''to chomp'' heißt ''abbeißen''. Man kann Chomp gut auf Papier mit Rechenkästchen spielen. Die Spieler entfernen abwechselnd Felder (z. B. durch Markierung der Kästchen) nach der folgenden Regel: Der Spieler am Zug entscheidet sich für eines der noch vorhandenen Felder ''(Ankerfeld)'' und entfernt alle noch vorhandenen Felder in demjenigen Rechteck, das das Ankerfeld als linke obere Ecke hat und das unten und rechts bis zum Spielfeldrand reicht. Der Spieler, der das linke obere Feld nehmen muss, verliert das Spiel.

== Geschichte ==
[[Fred Schuh]] gilt als Erfinder von Chomp <ref>Fred Schuh: ''Spel van delers''. Nieuw Tijdschrift voor Wiskunde 39 (1952), S. 299–304</ref>. Er veröffentlichte 1952 das ''Spel van delers'' (''Spiel der Teiler''). Das ist die mehrdimensionale zahlentheoretische Variante von Chomp (siehe [[#Verallgemeinerungen der Spielidee|Verallgemeinerungen]]). 1974 folgte durch [[David Gale (Ökonom)|David Gale]] die Standardvariante <ref>David Gale: ''A curious Nim-type game''. Amer. Math. Monthly 81 (1974), S. 876–879</ref>, die durch [[Martin Gardner]] den Namen Chomp erhielt. Seither sind mehrere Publikationen mit Analysen von Chomp erschienen; eine Gewinnstrategie konnte aber bisher nicht entwickelt werden.

In der deutschen Übersetzung des Standardwerks der mathematischen Spiele ''Winning Ways'' von E. R. Berlekamp et al. wurde als Bezeichnung für das Chomp-Spiel ''Futtern'' gewählt <ref name="Berlekamp" />. Dieser Name scheint sich aber nicht durchgesetzt zu haben.

== Beispiel ==
Das folgende Bild zeigt einen typischen Ablauf beim Chomp-Spiel. Da das Ausgangsrechteck 3 Zeilen und 6 Spalten aufweist, wird dieses Spiel als (3,6)-Chomp bezeichnet. Legale Spielsituationen weisen am unteren Rand der noch vorhandenen Felder eine „Treppe“ von links unten nach rechts oben auf (weiße Felder).

 

[[Datei:Chomp beispiel.png|Beispiel für ein Chomp-Spiel]]

Spieler B muss das letzte Feld (angekreuzt) nehmen und verliert. Die Ankerfelder sind jeweils durch einen Punkt markiert.

== Theorie des Spiels ==
Aus theoretischen Gründen verzichtet man auf die Wegnahme des linken oberen Felds, so dass nicht der Verlierer, sondern der Gewinner den letzten Zug macht; insbesondere soll das Rechteck mehr als ein Feld aufweisen. Mit dieser Vereinbarung lässt sich Chomp innerhalb der [[Kombinatorische Spieltheorie|Kombinatorischen Spieltheorie]] als [[Neutrale Spiele|neutrales]] (oder [[Objektive Spiele|objektives]]) 2-Personen-Spiel klassifizieren. Solche Spiele besitzen immer eine [[Gewinnstrategie]] für entweder den anziehenden Spieler (1. Zug) oder den nachziehenden Spieler (2. Zug). Das Gleiche gilt für jede denkbare Spielsituation zwischen dem ersten und dem letzten Zug.

Bei Chomp gibt es eine Gewinnstrategie für den anziehenden Spieler. Das weist man mit einem sogenannten [[Strategiediebstahl]] nach: Gäbe es eine Gewinnstrategie für den Nachziehenden, so müsste es einen gewinnbringenden Antwortzug auf die Wegnahme des rechten unteren Felds geben. Das Ankerfeld dieses Antwortzugs hätte aber der Anziehende gleich im ersten Zug wählen können; das würde ihm eine Gewinnstrategie verschaffen. Also ist die Annahme einer Gewinnstrategie für den Nachziehenden falsch.

Der Strategiediebstahl ist bei Chomp keine konstruktive Gewinnstrategie. Das bedeutet, dass lediglich die Existenz einer Gewinnstrategie bewiesen wird, aber die Gewinnstrategie selbst daraus nicht abzuleiten ist. Für beliebiges (n,m)-Chomp (d. h. für n Zeilen, m Spalten) ist keine Gewinnstrategie bekannt, wohl aber für kleine Zahlenpaare (n,m), außerdem für alle Zahlenpaare (n,n), (n,2) und (2,m).

Die Gewinnstrategie ist im Allgemeinen nicht eindeutig. Das kleinste bekannte Beispiel, bei dem es mehr als eine Gewinnstrategie gibt, ist (8,10)-Chomp <ref name="Berlekamp">Elwyn R. Berlekamp et al.: ''Gewinnen - Strategien für mathematische Spiele'', Band 3. Vieweg, Braunschweig/Wiesbaden 1986, ISBN 3-528-08533-9, S. 172f</ref>.

== Verallgemeinerungen der Spielidee ==
Chomp ist durch das rechteckige, gerasterte Spielfeld einfach darstellbar und spielbar. Es lässt sich allerdings auch [[Zahlentheorie|zahlentheoretisch]] statt geometrisch formulieren. Dazu beginnt man mit einer [[Natürliche Zahlen|natürlichen Zahl]] N, die das Produkt zweier Primzahlpotenzen ist: N = pn × qm (p, q verschiedene [[Primzahl]]en). Die Spieler wählen abwechselnd als ''Ankerzahlen'' [[Faktor (Mathematik)|Faktoren]] von N; dabei darf nicht die 1 und kein bereits gewählter Faktor oder ein Vielfaches davon gewählt werden. Der Spieler, für den nur die 1 übrig bleibt, verliert. Dieses Spiel ist spieltheoretisch identisch mit (n+1,m+1)-Chomp, denn das folgende Bild zeigt, dass man alle Faktoren von N in einem (n+1,m+1)-Rechteck anordnen kann; die Ankerzahlen entsprechen dann den Ankerfeldern. Nach Entfernung eines Ankerfelds bleiben nur noch Faktoren übrig, die keine Vielfachen der Ankerzahl sind. Im Bild ist das Ankerfeld in der (i+1)-ten Zeile und der (k+1)-ten Spalte; alle grün umrandeten Felder entfallen. Dann sind nur noch Felder übrig, die keine Vielfachen von pi × qk sind.

 

[[Datei:Chomp prim.png|Erster Zug bei einem zahlentheoretischen Chomp-Spiel]]

 

Die zahlentheoretische Definition des Chomp-Spiels erlaubt zwei Verallgemeinerungen. Wenn r Primzahlen statt zwei Primzahlen im Produkt für N auftreten dürfen, führen die gleichen Spielregeln zum ''r-dimensionalen Chomp'' <ref name="Berlekamp" />. Ferner kann man die Beschränkung auf endlich viele Felder aufheben; dann sind als Ankerzahlen alle Produkte der r vorgegebenen Primzahlen mit beliebig hohen Potenzen erlaubt, sofern sie keine bereits gewählten Ankerzahlen oder Vielfache davon sind.

== Siehe auch ==
* [[Nim-Spiel]]

== Einzelnachweise ==
<references />

== Weblinks ==
{{Commonscat}}
* [https://www.win.tue.nl/~aeb/games/chomp.html Ausführliche Beschreibung von Chomp (engl.)]
* [https://www.ossiemanners.co.uk/ Chomp als Download (engl.)]
* [http://lpcs.math.msu.su/~pentus/abacus.htm Chomp online spielen (engl.)]
* [https://stedwick.github.io/munch/ (5,6)-Chomp gegen einen Computer mit perfekter Strategie (engl.)]
* [[:en:David Gale|Biographie David Gale (engl.)]]

[[Kategorie:Papier-und-Bleistift-Spiel]]
[[Kategorie:Strategiespiel]]

Chomp - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https