300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
Gesamtzahl der Spiele: 775599
Gesamtzahl der Siege: 486693
Gesamtzahl der Siege: 486693
Spielanleitung:
- Jeder Spieler nimmt abwechselnd Süßigkeiten vom Spielbrett.
- Welche Bonbons entfernt werden, hängt von dem Quadranten ab, aus dem das Bonbon ausgewählt wurde.
- Der obere linke Quadrant entfernt alle Süßigkeiten von oben und links des ausgewählten Bonbons, der obere rechte oben und rechts, der untere linke unten und links und der untere rechte unterhalb und rechts des ausgewählten Bonbons.
Wie man gewinnt:
- Der Spieler, der das letzte Plättchen entfernt, gewinnt das Spiel.
Spieler 1 ist an der Reihe
Breite des Bretts:
Höhe des Brettes:
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
Der Algorithmus, den Sie in diesem Tutorial lernen, ist in der Lage, eine große Klasse von Spielen optimal zu spielen, so dass es sich auszahlt, einige Zeit damit zu verbringen, ihn zu lernen. Der Schlüssel wird die berühmte Sprague-Grundy-Theorie sein. Wenn Sie Tipps zum Spielen von iChomp erhalten möchten, ohne die Sprague-Grundy-Theorie zu lernen, dann scrollen Sie nach unten zum entsprechenden Abschnitt. Bevor wir ins Detail gehen, müssen wir ein paar Begriffe klären.
Anmerkung
-
Kombinatorische Spiele: Zwei-Personen-Spiele mit perfekten Informationen und Gewinn- oder Verlustergebnis und ohne Zufallszüge.
Unparteiische Spiele: kombinatorische Partien, bei denen die erlaubten Züge nur von der Stellung abhängen und nicht davon, welcher der beiden Spieler sich gerade bewegt. Außerdem sind die Auszahlungen symmetrisch. Mit anderen Worten, der einzige Unterschied zwischen Spieler 1 und Spieler 2 besteht darin, dass Spieler 1 zuerst an der Reihe ist. Beispiel: Chomp.
Partisanenspiele: Spiele, die nicht unparteiisch sind. Beispiel: Schach.
Normales Spiel: Der Spieler, der den letzten Zug macht, gewinnt, d.h. der Spieler, der keinen Zug machen kann, d.h. der nichts zu nehmen hat, verliert.
Misère-Spiel: Der Spieler, der den letzten Zug macht, verliert.
Chomp: das Spiel, das auf unserer Spieleseite vorgestellt wird und einen Quadranten und Misère-Spiel verwendet.
Verwendet das Nim-Spiel, wie es auf unserer Spieleseite gespielt wird, normales oder misère-Spiel?
- Unser Nim-Spiel verwendet Misère-Spiel, denn der Spieler, der das letzte Spiel gewinnt, verliert das Spiel.
Verwendet das Chomp-Spiel, wie es auf unserer Chomp-Spielseite gespielt wird, normales oder Misère-Spiel?
- Das Chomp-Spiel, wie es auf unserer Spielseite gespielt wird, verwendet Misère-Spiel, da der Spieler, der die letzten Süßigkeiten nimmt, verliert.
Warum macht es keinen Sinn, normales Spiel für Chomp zu verwenden?
- Bei normalem Spiel würde das bedeuten, dass derjenige gewinnt, der das letzte Plättchen nimmt. Daher könnte der Spieler, der zuerst an der Reihe ist, sofort gewinnen, indem er das Plättchen in der oberen linken Ecke nimmt.
Verwendet das iChomp-Spiel, wie es auf dieser Webseite gespielt wird, Normal oder Misère Play?
- Bei iChomp gewinnt der Spieler, der das letzte Plättchen nimmt, also verwendet dieses Spiel das normale Spiel.
Hast du einen Vorschlag, wie man das Chomp-Spielbrett ändern könnte, um das normale Spiel zu verwenden und immer noch das gleiche Spiel zu spielen?
-
Man könnte mit einer Position beginnen, an der das (vergiftete) Bonbon in der oberen linken Ecke bereits von Anfang an fehlt. Das letzte Bonbon von einem solchen Brett zu nehmen, bedeutet, dass man im normalen Spiel gewinnen würde. In Misère Play und mit diesem Plättchen müsste der andere Spieler es nehmen und verlieren, was das gleiche Ergebnis ist.
Ein Plättchen in der linken oberen Ecke zu haben und Misère Play zu verwenden oder dieses Plättchen nicht gleich zu Beginn des Spiels zu haben und das normale Spiel zu verwenden, ist also genau das gleiche Spiel.
Über iChomp
- Das iChomp-Spiel ist so konzipiert, dass es die Vereinigung von vier ist Kauen Spiele, die zur gleichen Zeit gespielt werden, alle nach der Regel des normalen Spiels. Das macht das Spiel in zweierlei Hinsicht schöner, die im Folgenden erläutert werden. Außerdem ist iChomp nicht viel schwieriger zu spielen als Chomp, wenn man die Sprague-Grundy-Theorie anwendet, die ebenfalls weiter unten beschrieben wird.
Über die Sprague-Grundy-Theorie
-
Die Klasse von Spielen, auf die es zutrifft, sind Unparteiische kombinatorische Spiele. Diese Theorie tut zwei Dinge für uns:
- Es gibt uns einen Algorithmus, der für jede Partie (d.h. jede Stellung) eine Zahl bestimmt (wir nennen es den SG-Wert), so dass die Zahl nur dann 0 ist, wenn es sich um eine Verluststellung handelt (in der Literatur zur kombinatorischen Spieltheorie als "P-Stellung" bezeichnet, wobei "P" angibt, dass der "p"revious Spieler" einen Gewinnzug gespielt hat). Das heißt, wenn dieser SG-Wert 1, 2, 3 ist, ... dann ist dies eine Gewinnstellung (in der Literatur "N"-Position genannt). In diesem Fall kann derjenige, der sich bewegt, einen Sieg erzwingen, wenn er optimal spielt.
- Der zweite Zweck der SG-Theorie ist es, zu beschreiben, wie man ein Spiel gewinnt, das aus mehreren gleichzeitig gespielten Positionen besteht. Ein Zug in einer solchen kombinierten Partie wird gemacht, indem ein Zug in einer der kombinierten Stellungen gemacht wird.
Was man wissen muss, ist der SG-Wert jeder der kombinierten Positionen. Um sie zu erhalten, muss man den SG-Wert nach jedem Zug in einer dieser kombinierten Stellungen kennen. Diese werden ebenfalls benötigt, um optimal zu spielen.
Zum Beispiel: Im Nim-Spiel hat man ein oder zwei oder mehr Stapel Streichhölzer. Wenn wir den SG-Wert für das Ausspielen jedes einzelnen Stapels kennen, dann sagt uns die SG-Theorie, wie wir mit all diesen Stapeln optimal spielen können, indem wir die entsprechende Anzahl von Streichhölzern von einem dieser Stapel entfernen.
Warum iChomp?
-
iChomp ist eine neue Version von Chomp, die von Caribou Contests eingeführt wurde und auf dieser Webseite gespielt wird. Das "i" in iChomp steht für "isotrop", d.h. alle Richtungen werden gleich behandelt.
Im normalen Chomp werden durch das Entfernen einer Kachel auch alle Kacheln östlich und südlich davon entfernt. So spielen die Richtungen Ost und Süd eine besondere Rolle.
In iChomp können auch alle Kacheln in andere Richtungen entfernt werden, je nachdem, wo sich die entfernte Kachel befindet, die der Mitte am nächsten ist. Befindet sich diese Kachel z.B. in nordwestlicher Richtung der Mitte, dann werden auch alle Kacheln im Norden oder Westen entfernt.
Das Entfernen künstlicher Regeln, zum Beispiel die Regel, dass Ost und Süd etwas Besonderes sind, wird in der Regel als mathematisch schöner angesehen.
Es gibt noch eine weitere Verschönerung, die iChomp im Vergleich zu Chomp hat.
In Chomp spielt die Kachel in der linken oberen Ecke im Vergleich zu anderen Kacheln eine besondere Rolle. Wenn das das einzige Plättchen auf dem Brett ist, ist das Spiel vorbei. Wird ein weiteres Plättchen entfernt, geht das Spiel weiter. Man könnte Chomp ohne dieses Eckplättchen beginnen, so dass alle Plättchen gleich behandelt werden, aber das wäre dann eine künstliche Regel, warum man das Spiel ohne dieses Plättchen beginnen sollte und nicht auch ohne andere Plättchen.
In iChomp sind alle Kacheln zu Beginn vorhanden und werden alle gleich behandelt. Jede Kachel kann entfernt werden, ohne das Spiel automatisch zu beenden.
Es stellen sich einige Fragen:
Ist iChomp ein triviales Spiel, weil es die Kombination oder 4 triviale Chomp-Spiele im "normalen Spiel" ist?
-
Die Antwort ist nein. Zum Beispiel ist das Nim-Spiel mit einem einzigen Stapel von Streichhölzern trivial. Unter "Normales Spiel" kann man den ganzen Stapel in einem Zug entfernen und gewinnen. In Nim unter "Misère Play", Man kann alle Spiele bis auf eines entfernen und gewinnen. Nichtsdestotrotz ist die Kombination solcher 1-Stapel-Nim-Spiele zu einem Mehrstapel-Nim-Spiel wie auf unserer Nim-Spiele-Seite nicht trivial.
Ähnlich verhält es sich hier: Eine einzelne Partie mit dem Eckplättchen und dem "normalen Spiel" ist trivial, da man alle Spielsteine in einem Zug entfernen und gewinnen könnte. Aber die Kombination von 4 solcher Spiele ist nicht trivial.
Zusammenfassung des Vergleichs
- IChomp ist mathematisch schöner als Chomp, weil es die südöstlichen Richtungen nicht künstlich herausgreift und keiner Kachel eine besondere Rolle zuweist. Der Preis scheint zu sein, dass iChomp viel schwieriger zu spielen ist als Chomp, aber die SG-Theorie hilft. Es reicht aus, den SG-Wert von Chomp-Positionen bis zu einer gewissen Größe zu kennen, um den SG-Wert von iChomp-Positionen bis zu einer 4-fachen Größe leicht berechnen zu können und somit zu wissen, wie man iChomp bis zu dieser 4-fachen Größe optimal spielt.
-
Die Antwort ist nein. Zum Beispiel ist das Nim-Spiel mit einem einzigen Stapel von Streichhölzern trivial. Unter "Normales Spiel" kann man den ganzen Stapel in einem Zug entfernen und gewinnen. In Nim unter "Misère Play", Man kann alle Spiele bis auf eines entfernen und gewinnen. Nichtsdestotrotz ist die Kombination solcher 1-Stapel-Nim-Spiele zu einem Mehrstapel-Nim-Spiel wie auf unserer Nim-Spiele-Seite nicht trivial.
In der SG-Theorie wird eine mathematische Operation namens XOR benötigt. Falls Sie damit nicht vertraut sind, ist der folgende Abschnitt nützlich.
Was ist XOR?
-
Exklusives Oder, kurz XOR, ist eine logische Operation, die für Binärdaten ausgeführt wird. Bei Verwendung von Binärdaten können wir einen von zwei Werten haben: true (=1) oder false (=0). Der XOR-Vorgang für zwei Binärwerte wird in der folgenden Tabelle definiert.
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
Während es einfach ist, diese Operation für Werte von 1 (wahr) oder 0 (falsch) zu verwenden, müssen wir für unsere Berechnungen in der Lage sein, XOR für zwei Zahlen durchzuführen. Dies ist auch möglich, jedoch ist ein neuer Schritt erforderlich, bevor wir das XOR durchführen können.
Was zuerst passieren muss, ist, dass die Zahlen in binär umgewandelt werden müssen, d.h. von der Basis 10 auf die Basis 2 umgerechnet werden müssen.
Wie kann man eine Zahl von der Basis 10 in die Basis 2 umrechnen?
-
Der folgende Algorithmus kann verwendet werden, um eine Zahl n zur Basis 10 in das Format zur Basis 2 umzuwandeln. (Denken Sie daran, dass 20 = 1 ist):
- Finde den höchsten Exponenten p von 2, so dass 2p ≤ n ist.
- Zeichne eine 1 auf und subtrahiere 2p von n.
- Wenn p = 0 ist, dann stoppen, sonst 1 von p subtrahieren und fortfahren.
- Wenn 2 p > n ist, dann nimm eine 0 auf, ansonsten subtrahiere 2p von n und zeichne eine 1 auf.
- Kehren Sie zu Schritt 3 zurück.
Die Folge von 1en und 0en, die Sie nach diesem Algorithmus aufgezeichnet haben, ist die binäre Darstellung der Zahl n. Beispiel:
Konvertieren wir die Zahl 13 in das Format zur Basis 2. Wir beginnen damit, die höchste Potenz von 2 zu finden, die kleiner oder gleich 13 ist, was 2,3 oder 8 ist. Wir nehmen dann eine 1 auf und subtrahieren 8 von 13, was uns 5 ergibt. Als nächstes prüfen wir 2(3−1) = 22 = 4. Da 4 ≤ 5 ist, nehmen wir eine 1 auf und subtrahieren 4 von 5, was uns 1 ergibt. Die nächstniedrigere Potenz von 2 ist 21 = 2. 2 > 1, also nehmen wir eine 0 auf. Die nächste Potenz von 2 ist 20 = 1, was gleich unserem n von 1 ist, also nehmen wir eine 1 auf und subtrahieren 1 von 1, was uns 0 ergibt. Da p = 0 ist, stoppen wir den Algorithmus. Daher ist 13 (Basis 10) = 1101 (Basis 2).
Nachdem wir zwei Zahlen in eine binäre Darstellung umgewandelt haben, können wir nun die XOR-Operation für die entsprechenden Ziffern der beiden Binärzahlen durchführen. Das Ergebnis ist eine Binärzahl, die dann wieder in die Basis 10 umgewandelt werden kann, wenn dies für die zukünftige Verwendung dieses XOR-Werts bequemer ist. Beispiel:
Berechnen wir das XOR der Zahlen 6 und 13. Die binäre Darstellung für diese beiden Zahlen ist 6 = 110 und 13 = 1101. Zuerst fügen wir links von der kleineren Zahl eine 0 hinzu, so dass beide die gleiche Anzahl von Ziffern haben, also 6 = 0110. Wir können dann das XOR durchführen, indem wir sie aneinanderreihen und die Operation für jede der einzelnen Ziffern ausführen:
0110 XOR 1101 ------ 1011
Also 6 XOR 13 = 1011 (Basis 2) = 1×23+0×22+1×2 1+1×20 = 8+2+1 = 11 (Basis10).
Lassen Sie uns unser Verständnis von XOR mit ein paar Fragen überprüfen.
Was ist m XOR m für eine beliebige Zahl m?
- Für jede Zahl m haben wir m XOR m = 0 weil 0 XOR 0 = 0 und auch 1 XOR 1 = 0.
Ist n XOR m = m XOR n für beliebige Zahlen n, m?
- Ja, denn 1 XOR 0 = 0 XOR 1 (=1).
Was ist 0 XOR m für eine beliebige Zahl m?
- 0 XOR m = m, weil 0 XOR 0 = 0 und 0 XOR 1 = 1.
Wenn eine Zahl m mit einer Zahl n bis m XOR n XOR vertauscht wird, welche Ziffern von m werden dann vertauscht?
- Wenn eine Ziffer in m mit 0 XOR versehen ist, dann ist die Ziffer unverändert (denn 0 XOR 0 = 0 und 1 XOR 0 = 1). Wenn eine Ziffer in m mit 1 XOR versehen wird, dann wird die Ziffer umgedreht (weil 0 XOR 1 = 1 und 1 XOR 1 = 0). Somit vertauscht XOR n alle Ziffern, bei denen die entsprechende Ziffer in n eine 1 ist.
-
Der folgende Algorithmus kann verwendet werden, um eine Zahl n zur Basis 10 in das Format zur Basis 2 umzuwandeln. (Denken Sie daran, dass 20 = 1 ist):
Der Algorithmus zur Berechnung des SG-Werts einer Chomp-Position.
-
Der folgende Algorithmus berechnet den SG-Wert einer beliebigen Stellung P in einem unparteiischen kombinatorischen Spiel. Wir erklären es anhand des Chomp-Spiels.
- Jede Spielposition, die eine Verluststellung ist, erhält den SG-Wert 0. In Chomp ist ein einzelnes Plättchen (in der nordwestlichen Ecke) die einzige Stellung ohne Folgezug und daher eine Verluststellung mit SG-Wert 0.
- Wir benötigen die SG-Werte aller Positionen, die von Position P aus in einem Zug erreicht werden können. Wenn also Position P n Plättchen hat, dann gibt es n-1 mögliche Züge: Mit Ausnahme des Plättchens in der nordwestlichen Ecke können alle anderen Plättchen zusammen mit allen Plättchen südlich/östlich dieses Plättchens entfernt werden.
- Der SG-Wert einer Position P ist die kleinste nicht-negative Zahl, die nicht in dieser Liste von n-1 erreichbaren SG-Werten enthalten ist.
Dieser Algorithmus ist rekursiv, da wir für die Berechnung des SG-Wertes der Position P die SG-Werte aller von P aus erreichbaren Positionen in einem Zug benötigen. Es funktioniert trotzdem, weil die benötigten SG-Werte kleinere Positionen von weniger Kacheln betreffen und der SG-Wert der kleinstmöglichen Position (eine Kachel in der Nordwestecke) bekannt ist.
Versuchen Sie, die 3. Eigenschaft im obigen Spiel zu überprüfen, indem Sie eine größere Breite und Höhe des Bretts auswählen und auf "Brett randomisieren" klicken.
- Wenn Sie mit der Maus über eine Kachel fahren, werden diese Kachel und die anderen Kacheln, die entfernt werden sollen, hervorgehoben. Die Zahl in diesem Plättchen ist der SG-Wert des Quadranten unter 'Normales Spiel' (nicht 'Misère Play'), der sich ergeben würde, wenn dieses Plättchen angeklickt wird. Sie können überprüfen, ob die Zahl, die im Text "SG-Wert Basis Zehn:" neben dem Quadranten angezeigt wird, die kleinste Zahl ist, die nicht im Quadranten angezeigt wird. Sie können auch überprüfen, dass, wenn Sie auf eine Kachel klicken, die Zahl, die sich darin befand, jetzt als "SG-Wert Basis Zehn:" der neuen Position angezeigt wird.
So beschleunigen Sie die Bestimmung von SG-Werten:
Da die gleiche Stellung von verschiedenen Positionen aus in einem Zug erreicht werden kann und bei der Berechnung des SG-Wertes einer größeren Stellung immer wieder auftauchen kann, wäre es eine Verschwendung von Mühe, ihn immer wieder neu zu berechnen. Sobald der SG-Wert einer Position P berechnet ist, sollte er daher für die spätere Verwendung gespeichert werden.
Wenn man den SG-Wert aller Positionen bis zu einer bestimmten Größe berechnen möchte, dann ist der folgende Ansatz sinnvoll. Wir beginnen damit, der einzigen Position mit einem Plättchen (in der nordwestlichen Ecke) den SG-Wert Null zuzuweisen. Dann verwenden wir den obigen Algorithmus, um die SG-Werte aller Positionen mit 2 Kacheln, dann mit 3 Kacheln usw. zu berechnen.
Der Algorithmus zur Berechnung des SG-Wertes einer iChomp-Position
-
Eine iChomp-Position besteht aus 4 Chomp-Positionen, eine in jedem Quadranten des Boards.
- Zuerst bestimmen wir den SG-Wert jeder der 4 Chomp-Positionen mit Hilfe der Chomp 'Misère Play'-Regel. Der leere Quadrant ist keine Chomp-Position, daher geben wir ihm den Wert −1.
- Wir addieren dann 1 zu jedem Wert.
- Für jede der 4 resultierenden Zahlen berechnen wir die binäre Darstellung.
- Wir berechnen den XOR-Wert der 4 Binärwerte und erhalten den SG-Wert dieser Position (in binärer Form). Wenn dieser Wert Null ist, handelt es sich um eine Verlustposition, andernfalls um eine Gewinnposition.
-
Wir addieren eine 1, um den SG-Wert einer Chomp-Stellung unter 'Normales Spiel' aus dem SG-Wert unter 'Misère Play' zu erhalten. Der folgende Satz erklärt es.
Theorem:
--------
Um den SG-Wert einer Chomp-Position unter "Normales Spiel" zu erhalten (d.h. das letzte Plättchen gewinnt das Spiel, was nicht die übliche Art ist, Chomp zu spielen), muss man 1 zum SG-Wert der gleichen Position unter "Misère Play" addieren (d.h. das letzte Plättchen verliert, was die übliche Art ist, Chomp zu spielen).
Können Sie versuchen, den Satz durch Induktion zu beweisen?
-
Beweis (durch Induktion (und sehr detailliert)):
Basisfall (1 Kachel):
-------------------
Im 'Normalen' ist ein leeres Brett ohne Plättchen eine Verluststellung und hat daher den SG-Wert Null. Darüber hinaus ist unter "Normales Spiel" für ein Brett mit einem Plättchen (in der oberen linken Ecke) der einzige mögliche Zug, dieses Plättchen zu entfernen, was eine Position mit SG-Wert 0 ergibt. Unter "Normales Spiel" ist also der kleinste nicht-negative SG-Wert, der nicht durch einen Zug erreicht werden kann, 1, also der SG-Wert einer Stellung mit einem Plättchen unter "Normales Spiel".
Unter "Misère Play" ist ein Plättchen eine Verlustposition mit SG-Wert 0.
Somit ist bei 1 Plättchen der SG-Wert für 'Normales Spiel' um 1 größer als der Wert für 'Misère Play'.
Induktiver Schritt
---------------
Induktionshypothese (n Kacheln):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Wir gehen davon aus, dass es eine Zahl n gibt, so dass für alle Positionen mit ≥1 und ≤n Plättchen der SG-Wert unter 'Normales Spiel' um eins größer ist als unter 'Misère Play'. Induktionsanspruch (n+1 Kacheln):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Wir werden zeigen, dass dies dann auch für alle Positionen mit n+1 Kacheln der Fall ist.
Induktionsschritt (n Kacheln → n+1 Kacheln):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Für jede Stellung erlauben "Misère Play" und "Normal Play" die gleichen Züge, außer dass "Normal Play" auch erlaubt, alle Plättchen durch das obere linke Eckplättchen zu nehmen.
Wenn die Stellung n+1 Kacheln hat, dann erzeugt ein Zug eine Stellung mit höchstens n Kacheln, auf die wir die Induktionshypothese anwenden können:
Die Liste der erzielbaren SG-Werte unter 'Normales Spiel' ergibt sich also aus der Liste der erreichbaren SG-Werte unter 'Misère Play', jeweils erhöht um 1 und durch Addition des Wertes 0 durch Entnahme aller Plättchen.
Daher ist die kleinste nicht-negative Zahl, die unter "Normales Spiel" NICHT erreichbar ist, um 1 höher als die kleinste nicht-negative Zahl, die unter "Misère Play" NICHT erreichbar ist. Mit anderen Worten, für die ursprüngliche Position mit n+1 Plättchen ist der SG-Wert unter 'Normales Spiel' um eins höher als der SG-Wert unter 'Misère Play'. ∎ (Damit ist der Beweis abgeschlossen.)
-
Beweis (durch Induktion (und sehr detailliert)):
Warum haben wir eine "1" hinzugefügt?
Wie man iChomp spielt
-
Ziel ist es, einen Zug so zu machen, dass der SG-Wert der resultierenden Position Null ist. Welchen Zug man auch immer macht, er muss in einem der 4 Quadranten liegen. Das bedeutet, dass der SG-Wert der Position, an der der Zug gemacht wurde, und die SG-Werte der anderen 3 unveränderten Quadranten, die alle XOR'ed sind, Null ergeben müssen. Dies ist nur dann der Fall, wenn die anderen 3 SG-Werte XOR'ed nach der Verschiebung genau den SG-Wert des neuen Quadranten ergeben (siehe weiter unten für einen Beweis dieser Aussage). Das Verfahren ist daher wie folgt:
- (einfach) Fall: Zwei der 4 Quadranten haben den gleichen SG-Wert. Dann ergibt XOR dieser beiden gleichen Werte Null, so dass beide Quadranten ignoriert werden müssen.
- Wenn die anderen beiden Quadranten ebenfalls gleiche SG-Werte haben, dann ist der SG-Wert der gesamten Position Null und die Position ist eine Verlustposition. Entferne dann nur ein Plättchen aus einem beliebigen Quadranten, um die Niederlage hinauszuzögern und mehr Chancen für den Gegner zu haben, nicht optimal zu spielen.
- Wenn die anderen beiden Quadranten ungleiche SG-Werte haben, wählen Sie den Quadranten mit einem größeren SG-Wert. Mache einen Zug dorthin, indem du auf ein Plättchen klickst, in das eine Zahl eingraviert ist, die dem SG-Wert des anderen Quadranten entspricht. Das Ergebnis sind 2 Quadrantenpaare mit paarweise gleichem SG-Wert und Gesamt-XOR-Wert von Null - eine Verlustposition.
- (Allgemeiner) Fall:
- Berechnen Sie die 4 iChomp-SG-Werte, z.B. W,X,Y,Z der 4 Quadranten (jeweils die Chomp-SG-Werte dieses Quadranten plus 1) und konvertieren Sie sie zur Basis Zwei.
- Finde dann die Position ganz links, so dass eine ungerade Zahl dieser 4 Zahlen eine 1 an dieser Stelle hat. Wenn z.B. die 4 Zahlen
w=11011
Dann ist die Position ganz links mit einer 1 die 5. Position (wir beginnen mit dem Zählen der Positionen von rechts). w und y haben dort eine 1, d.h. zwei Zahlen (w und y) haben dort eine 1. Zwei ist eine gerade Zahl, daher müssen wir diese Position ignorieren. Die nächste Position ist die 4. Position, wieder von rechts gezählt. Auch hier haben gleich viele Zahlen eine 1 (w und x). Auch diese Position müssen wir ignorieren. Die 3. Position hat 3 Zahlen mit einer 1 (x, y, z). 3 ist eine ungerade Zahl, also wählen wir eine dieser 3 Zahlen, z. B. y=10100.
x= 1101
y=10100
z= 100- Wenn es in allen Positionen eine gerade Anzahl von 1en gibt, dann ist der XOR-Wert aller 4 Zahlen Null und dies ist eine Verlustposition. Zum Beispiel
w'=11011
haben eine gerade Anzahl von Einsen in jeder Position. Das XOR dieser 4 Zahlen ist Null, dies ist eine Verlustposition. In diesem Fall entfernt man nur ein Plättchen aus einem Quadranten, um die Niederlage hinauszuzögern und mehr Chancen für den Gegner zu haben, nicht optimal zu spielen.
x'= 1011
y'=10110
z'= 110 - Wenn mindestens eine Position eine ungerade Anzahl von 1en hat, dann haben wir eine Zahl gefunden, wie y oben (nicht y').
- Wir XOR die anderen 3 Zahlen, in unserem Fall w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. Dieser Wert ist immer kleiner als die Zahl, die wir ausgewählt haben, hier y = 10100 (siehe Beweise weiter unten).
- Im Quadranten mit dem gewählten Wert, hier y, machen wir einen Zug, der zu einer Position führt, deren SG-Wert gleich dem XOR der anderen 3 Werte ist, in unserem Beispiel 10011.
- Um zu wissen, welche Kachel wir anklicken müssen, konvertieren wir entweder 10011 zur Basis Zehn (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) und klicken auf die Kachel mit der Zahl 19, oder wir berechnen in binärer Form 10100 − 10011 = 1 und wandeln dies in die Basis Zehn (= 1) um und wissen, dass die anzuklickende Kachel den Wert 1 kleiner als y (=20) haben sollte, d.h. auf die Kachel mit der Zahl 19 zu klicken.
Warum ist das ein gewinnbringender Schachzug?
-
Bitte erinnern Sie sich an die Eigenschaften von XOR, wie zuvor gezeigt, um die folgenden Fragen zu beantworten.
wenn u = w XOR x XOR y XOR z, was ist dann y XOR u ?
-
Durch die Verwendung von XOR-Regeln, die wir zuvor gelernt haben, erhalten wir
y XOR u
= y XOR w XOR x XOR y XOR z
= y XOR y XOR w XOR x XOR z
= 0 XOR w XOR x XOR z
= w XOR x XOR z.
Wenn y durch y XOR u ersetzt wird, was ist dann das neue XOR aller 4 SG-Werte?
-
Das neue XOR wäre
(y XOR u) XOR w XOR x XOR z
= (w XOR x XOR z) XOR (w XOR x XOR z)
= 0
aufgrund von m XOR m = 0 für eine beliebige Zahl m.
Das bedeutet, dass der neue SG-Wert des gesamten Boards Null wäre, so dass dies eine beabsichtigte Verlustposition wäre.
Warum sollte es einen Zug geben, der einen SG-Wert y in einen niedrigeren Wert umwandelt?
- Nach der Definition: Eine Stellung hat genau dann einen SG-Wert von y, wenn es Züge gibt, die Positionen mit SG-Werten 0,1,..,(y-1) erzeugen. Wenn also y > (y XOR u), dann muss es einen Zug geben, der einen SG-Wert (y XOR u) erzeugt < y.
Was noch zu beantworten bleibt, ist:
Warum sollte es einen Quadranten mit einem SG-Wert y geben, der y > (y XOR u) erfüllt?
-
Zur Erinnerung:
Früher, als wir etwas über die Eigenschaften von XOR erfuhren, sahen wir: XOR u dreht alle Ziffern um, für die die entsprechende Ziffer in u eine 1 ist.
Wenn Sie 0 ≠, dann enthält U eine höchste Potenz von 2, z. B. 2P. Diese Potenz von 2 muss in einer ungeraden Anzahl der 4 SG-Werte vorkommen, also in mindestens einem, sagen wir y.
Das bedeutet, dass bei der Berechnung von y XOR u diese 1 in y durch die entsprechende 1 in u in eine 0 umgewandelt wird. Möglicherweise befinden sich rechts von dieser 1 weitere binäre Ziffern, die in y umgedreht sind. Der größtmögliche Wert von y − (y XOR u) tritt auf, wenn die Ziffern in y rechts von dieser 1 Nullen sind und die Ziffern in u rechts von dieser 1 Einsen sind. In diesem Fall ändert u = 111..111 y = *100..00 (wobei * für eine beliebige Anzahl von Ziffern steht) in y XOR u = *011..11. Ihr Unterschied ist:
y − (y XOR u)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
Das bedeutet, dass y mindestens eins größer als (y XOR u) ist. ∎
-
Durch die Verwendung von XOR-Regeln, die wir zuvor gelernt haben, erhalten wir
Probieren Sie diesen Algorithmus aus, indem Sie gegen "Schwierigkeitsgrad: Schwer" spielen und gewinnen.
-
Wählen Sie zunächst "Schwierigkeitsgrad: Schwer", um ein optimales Computerspiel zu gewährleisten. Wenn du trotzdem gewinnst, dann hast du jeden Zug optimal gespielt.
Der SG-Wert jedes Quadranten ist in Basis 10 und Basis 2 dargestellt. Vergewissern Sie sich, dass es sich bei dieser Zahl um den kleinsten Wert handelt, der nicht im Quadranten angezeigt wird.
Darunter ist das XOR aller 4 SG-Werte mit dem Namen u dargestellt. Überprüfen Sie den Wert von Ihnen, indem Sie einfach ein beliebiges Paar von zwei 1en in den 4 SG-Werten auf 0 ändern, wenn die beiden 1en an der gleichen Position sind. Setze dann die restlichen 1en in eine Binärzahl ein und rechne diese zur Basis 10 um.
Um einen Umzug durchzuführen, gehen Sie wie oben beschrieben vor:
- Finde einen der 4 SG-Werte, z.B. y, der eine 1 an der gleichen Stelle wie die 1 ganz links in u hat.
- Berechnen Sie y XOR u in binärer Form und konvertieren Sie es dann zur Basis 10.
- Klicken Sie im y-Quadranten auf die Kachel mit dem berechneten y-XOR u.
- Spielen Sie Ihre Züge auf diese Weise, bis Sie gewonnen haben.
- Spielen Sie erneut, aber dieses Mal beginnen Sie mit einem zufälligen Zug. Wenn Sie nicht Glück hatten und aus Versehen einen Gewinnzug gespielt haben, werden Sie dieses Spiel nicht gewinnen können, auch wenn Sie dann versuchen, optimal zu spielen.
Alle obigen Anweisungen gehen davon aus, dass man den SG-Wert der 4 Quadranten kennt, was bedeutet, dass man den SG-Wert jedes Quadranten nach jedem möglichen Zug kennt.
Können Sie SG-Werte von einigen Chomp-Positionen (in 'Misère Play') finden?
-
Um den SG-Wert einer Position zu berechnen, muss man die SG-Werte aller Positionen kennen, die von ihr aus in einem Zug erreicht werden können. Dies ist ein rekursiver Prozess. Daher müssen wir mit den Positionen mit der geringsten Anzahl von Kacheln beginnen und uns nach oben arbeiten.
Können Sie die SG-Werte von 1,2,3 finden,... Kacheln in einer Reihe?
-
Nur 1 Kachel (in der oberen linken Ecke) zu haben, ist eine Verlustposition mit dem SG-Wert 0.
Bei 2 Plättchen (in der obersten Reihe oder linken Spalte) ist der einzige mögliche Zug, ein Plättchen zu nehmen und die angegebene Position mit dem SG-Wert 0 zu erhalten. Der kleinste nicht-negative SG-Wert, der nicht durch einen Zug erreicht werden kann, ist also 1, d.h. der SG-Wert einer Stellung mit 2 Kacheln ist 1.
Wenn man 3 Kacheln in der obersten Reihe hat, kann man entweder 1 oder 2 Kacheln nehmen und die SG-Werte 1 und 0 erhalten, so dass der SG-Wert also 2 ist.
In ähnlicher Weise ist der SG-Wert von n Kacheln in der obersten Zeile n-1.
Betrachten wir 3 Kacheln, 2 in der oberen Reihe und 2 in der linken Spalte. Wir können nur 1 Kachel entfernen und einen SG-Wert von 1, aber nicht 0 erreichen, so dass der kleinste SG-Wert, der nicht erreicht werden kann, 0 ist, was also der SG-Wert dieser Position ist. Dies ist eine Verlustposition.
Können Sie den SG-Wert einer Position mit m+n−1 Kacheln finden, von denen n in der obersten Reihe und m Kacheln in der linken Spalte stehen?
- Man kann Kacheln nur aus der obersten Reihe oder aus der linken Spalte entfernen. Der SG-Wert ist also derselbe wie bei zwei Quadranten, einem mit n Kacheln in der obersten Zeile und einem mit m Kacheln in der linken Spalte. Der SG-Wert ist also (m-1) XOR (n-1). Dies ist das Gleiche wie das Spielen von NIM mit zwei Stapeln und der "Normales Spiel"-Regel, bei der Streichhölzer in einem Zug nur von einem Stapel entfernt werden können.
Kann man den SG-Wert einer Position mit Kacheln nur in den oberen beiden Reihen finden?
-
Die Formeln für diese Positionen sind komplizierter. Soweit wir wissen, waren sie bisher noch nicht veröffentlicht worden. Sie können versuchen, sie für eine kleine Anzahl von Kacheln zu überprüfen.
Sei n und m die Anzahl der Kacheln in der oberen und zweiten Reihe.
Wenn n gerade ist, dann
k = (n-2)/2
Wenn m gerade ist, dann
a = m/2
SG-Wert = 2*k+a+1
sonst (m ist ungerade)
a = (m-1)/2
wenn ein ≤ (k/2) dann SG-Wert = 2*k-a
sonst SG-Wert = 3*(k-a)
sonst (n ist ungerade)
k = (n-1)/2
Wenn m gerade ist, dann
a = m/2
wenn ein ≤ (k/2) dann SG-Wert = 2*k-a
sonst SG-Wert = 3*(k-a)
sonst (m ist ungerade)
a = (m-1)/2
SG-Wert = 2*k+a+1
Überprüfe anhand des obigen Spielbretts, ob die Formeln korrekt sind.
- Wählen Sie die minimale Bretthöhe so aus, dass Quadranten mit nur zwei Kachelreihen vorhanden sind. Nach der Anwendung der obigen Formeln sollten Sie einen SG-Wert erhalten, der um eins niedriger ist als der unter "SG-Wert Basis zehn:" angezeigte Wert, da die Formeln für "Misère Play" gelten, während iChomp "Normales Spiel" verwendet.
-
Nur 1 Kachel (in der oberen linken Ecke) zu haben, ist eine Verlustposition mit dem SG-Wert 0.
Wie kann man iChomp einigermaßen gut spielen, ohne die SG-Werte zu kennen?
-
Wir beginnen mit einer Beobachtung: Die Regeln von Chomp machen keinen Unterschied zwischen Ost- und Südrichtung.
Was ist die Konsequenz für SG-Werte von zwei Positionen, die spiegelsymmetrisch zueinander sind, unter Spiegelung auf der Diagonalen, die von der linken oberen Ecke aus beginnt?
- Da Ost- und Südrichtung ineinander gespiegelt werden, bedeutet dies, dass beide den gleichen SG-Wert haben müssen.
Was bedeutet das für iChomp, wenn 2 Quadranten Positionen haben, die unter Drehung der Quadranten und/oder diagonaler Spiegelung symmetrisch sind?
- Beide Quadranten können ignoriert werden. Warum? Beide Quadranten haben den gleichen SG-Wert im Misère-Spiel und nach Addition von 1 auch den gleichen SG-Wert im normalen Spiel. XOR dieser beiden gleichen Werte ergibt Null. Daher haben beide Quadranten keinen Einfluss auf den SG-Wert der gesamten Boardposition.
Welche Spielstrategie sollte also funktionieren?
-
Man sollte einen Zug machen, der zwei Paare von Quadranten erzeugt, so dass die Quadranten in jedem Paar symmetrische Positionen mit gleichen SG-Werten haben, z.B. A und A und B und B. Dann ist der SG-Wert der Kombination aller 4 Quadranten A XOR A XOR B XOR B = 0 XOR 0 = 0 oder (A XOR B) XOR (A XOR B) = 0, also immer 0. Einer schuf eine Verlustposition.
Ebenso sollte man KEINEN Zug machen, bei dem zwei symmetrische Quadranten übrig bleiben und zwei weitere, von denen einer vom Gegner in einem Zug in den anderen umgewandelt werden kann. Dies würde es dem Gegner ermöglichen, eine Verlustposition zu schaffen.
Einige Testfragen
-
Hier kommen einige Fragen, mit denen Sie Ihr Verständnis von Chomp, iChomp und der SG-Theorie testen können.
Reicht das Wissen über SG-Werte aus, um Chomp perfekt zu spielen?
- Ja. Wenn der SG-Wert einer Stellung Null ist, dann handelt es sich um eine Verlustposition (weil es keinen Zug gibt, der sie auf Null setzt, also gibt es keinen Gewinnzug, also ist es eine Verlustposition). Wenn der SG-Wert größer als Null ist, dann bedeutet dies, dass es eine Bewegung gibt, um den SG-Wert der resultierenden Position auf Null zu setzen, also gibt es einen Gewinnzug.
Muss man die SG-Werte der Chomp-Positionen kennen, um Chomp perfekt spielen zu können?
- Nein. Um Chomp zu spielen, müssen wir einen Zug finden, der eine Verluststellung erzeugt. Wenn kein solcher Zug existiert, handelt es sich um eine Verluststellung und jeder Zug kann gespielt werden. Aber wenn ein solcher Zug gefunden wird, kann man aufhören zu suchen. Der SG-Wert wird nicht benötigt.
Wozu sind SG-Werte dann gut?
- Sie werden nur benötigt, um mehrere Chomp-Spiele parallel als neues Spiel zu spielen, wie in iChomp.
Wie viel schwieriger ist es in Chomp, den SG-Wert einer Stellung zu berechnen, als einen Gewinnzug?
-
Um Chomp zu spielen, müssen wir einen Zug finden, der eine Verluststellung erzeugt. Wenn kein solcher Zug existiert, handelt es sich um eine Verluststellung und jeder Zug kann gespielt werden. Aber wenn ein solcher Zug gefunden wird, kann man aufhören zu suchen.
Der Aufwand, den SG-Wert einer Position zu finden, ist in der Regel höher. Um den SG-Wert zu finden, muss man immer ALLE Züge durchsuchen, um alle SG-Werte der resultierenden Stellungen zu finden und den kleinsten nicht-negativen Wert zu finden, der in einem Zug nicht erreicht werden kann. Dieser Wert ist der SG-Wert der Position.
So konnten wir in unseren (Caribou-)Berechnungen alle Verlustpositionen (und damit Gewinnstellungen) mit bis zu 93 Kacheln ermitteln. Mit vergleichbarem Rechenaufwand konnten wir den SG-Wert aller Chomp-Positionen mit bis zu 82 Kacheln berechnen.
In diesem Sinne ist die Bestimmung von SG-Werten rechnerisch aufwendiger als die Bestimmung eines Gewinnzuges.
Wenn Nim mit 4 Stapeln schwieriger zu spielen ist als NIM mit 1 Stapel, ist dann iChomp mit 4 Quadranten viel schwieriger zu spielen als Chomp mit 1 Quadranten?
-
In Nim ist der SG-Wert eines Stapels einfach die Anzahl der Streichhölzer in diesem Stapel. (Bitte bestätigen Sie dies, indem Sie die obigen Kommentare zur Berechnung von SG-Werten auf einen einzelnen Stapel in Nim anwenden.) Die einzige Komplikation beim Spielen mehrerer Stapel in Nim besteht darin, die unterschiedlichen SG-Werte dieser Stapel zu XOR zu verwenden, um den SG-Wert aller Stapel zu erhalten.
In Chomp ist es rechenintensiv, den SG-Wert einer Position (die in einem Quadranten liegt) zu erhalten. Sobald die SG-Werte der 4 Quadranten bekannt sind, müssen diese Werte in iChomp ebenfalls mit XOR versehen werden, aber das ist viel einfacher, als den SG-Wert eines Quadranten zu finden.
Um Chomp optimal zu spielen, muss man den SG-Wert der Stellung nicht kennen, ein Gewinnzug ist gut genug, aber wie oben gezeigt, ist der Unterschied nicht so groß.
Die Antwort ist also NEIN, es ist nicht viel schwieriger, iChomp optimal zu spielen als Chomp.
Kann ein Zug in Chomp eine Stellung erzeugen, die einen höheren SG-Wert hat?
- Ja. Der SG-Wert einer Position ist der kleinste Wert, der nicht durch eine Bewegung erzeugt werden kann.
Kann es in Chomp verschiedene Züge geben, die eine Position mit dem gleichen SG-Wert erzeugen?
-
Ja. Sie können Beispiele sehen, indem Sie die Spielbrettgröße erhöhen und auf die Schaltfläche "SG-Werte von Zügen anzeigen" klicken. Zum Beispiel ist die Position
###
##
#
hat 3 Gewinnzüge, die alle eine Stellung mit SG-Wert von 0 erzeugen. Wir haben sogar eine Stellung mit 7 Gewinnzügen gefunden:
+ 10 6 15 2 20 21 14 22 11 0 23 7 26 13 7 11 9 14 0 19 5 17 11 14 18 0 24 23 8 3 19 2 0 20 11 4 0 5 1 8 0 0 4 23 25 24
Folgen oder abonnieren für Updates: