Chomp


Chomp

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

Inhaltsverzeichnis

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 [1]. Er veröffentlichte 1952 das Spel van delers ("Spiel der Teiler"). Das ist die mehrdimensionale zahlentheoretische Variante von Chomp (siehe Verallgemeinerungen). 1974 folgte durch David Gale die Standardvariante [2], 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 [3]. 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).

 

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 Kombinatorischen Spieltheorie als neutrales (oder 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 [3].

Verallgemeinerungen der Spielidee

Chomp ist durch das rechteckige, gerasterte Spielfeld einfach darstellbar und spielbar. Es lässt sich allerdings auch zahlentheoretisch statt geometrisch formulieren. Dazu beginnt man mit einer natürlichen Zahl N, die das Produkt zweier Primzahlpotenzen ist: N = pn × qm (p, q verschiedene Primzahlen). Die Spieler wählen abwechselnd als Ankerzahlen 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.

 

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 [3]. 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

Quellen

  1. Fred Schuh: Spel van delers. Nieuw Tijdschrift voor Wiskunde 39 (1952), S. 299-304
  2. David Gale: A curious Nim-type game. Amer. Math. Monthly 81 (1974), S. 876-879
  3. a b c Elwyn R. Berlekamp et al.: Gewinnen - Strategien für mathematische Spiele, Band 3. Vieweg, Braunschweig/Wiesbaden 1986, ISBN 3-528-08533-9, S. 172f

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • chomp — [tʃɔmp US tʃa:mp, tʃo:mp] v [i]informal [Date: 1600 1700; Origin: CHAMP1] to eat something chomp on ▪ She was chomping on a bread roll. chomp away ▪ a boy chomping away on a banana ▪ British people chomp their way through more than a billion bars …   Dictionary of contemporary English

  • chomp — [chämp] vt., vi. [dial. var. of CHAMP1] 1. to chew hard and noisily 2. to bite down (on), repeatedly and restlessly [to chomp on a cigar] n. the act or sound of chomping chomp at the bit CHAMP AT THE BIT (see phrase under …   English World dictionary

  • Chomp — Chomp, v. i. To chew loudly and greedily; to champ. [Prov. Eng. & Colloq. U. S.] Halliwell. [1913 Webster] …   The Collaborative International Dictionary of English

  • chomp — [ tʃamp ] verb intransitive or transitive INFORMAL to bite something several times in a noisy way: chomp on: He was chomping on a roll …   Usage of the words and phrases in modern English

  • chomp — /chomp/, v.t., v.i., n. champ1. * * * …   Universalium

  • chomp — 1640s, U.S. and dialectal variant of CHAMP (Cf. champ). Related: Chomped; chomping …   Etymology dictionary

  • chomp — ► VERB ▪ munch or chew noisily or vigorously. ORIGIN imitative …   English terms dictionary

  • Chomp — For other uses, see Chomp (disambiguation). Chomp is a 2 player game of strategy played on a rectangular chocolate bar made up of smaller square blocks (rectangular cells). The players take it in turns to choose one block and eat it (remove from… …   Wikipedia

  • chomp — UK [tʃɒmp] / US [tʃɑmp] verb [intransitive/transitive] Word forms chomp : present tense I/you/we/they chomp he/she/it chomps present participle chomping past tense chomped past participle chomped informal to bite something several times in a… …   English dictionary

  • Chomp — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Chomp peut faire référence à : jeu de Chomp, un jeu mathématique inventé par David Gale un des ennemis de Mario, dans les jeux vidéo Mario Catégorie  …   Wikipédia en Français