🔢 mathematics

Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

Dieser Artikel präsentiert eine umfassende computergestützte Studie von 4 x n Chomp, die über 4,3 Millionen P-Positionen tabelliert, um vier strukturelle Vermutungen bezüglich einzigartiger Erweiterungen, asymptotischer Verhältnisse, period-112-modularer Muster und linearer Kegelformen aufzustellen, die eine reichhaltigere deterministische Struktur im Spiel offenbaren als bisher angenommen.

Ursprüngliche Autoren: Arnav Garg

Veröffentlicht 2026-04-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Arnav Garg

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich ein Spiel namens Chomp vor, das auf einem rechteckigen Schokoriegel gespielt wird. Der Riegel besteht aus einem Gitter aus Quadraten. Zwei Spieler ziehen abwechselnd. Bei Ihrem Zug wählen Sie ein Quadrat aus und „essen" es zusammen mit allem, was sich darüber und rechts davon befindet. Der Haken? Das Quadrat oben links ist vergiftet. Wenn Sie gezwungen sind, dieses letzte Quadrat zu essen, verlieren Sie.

Mathematiker haben die Gewinnstrategie für sehr kleine oder sehr spezifische Schokoriegel herausgefunden, doch für einen Riegel, der 4 Quadrate breit und n Quadrate lang ist, blieb das Muster bis jetzt ein Rätsel.

Dieser Artikel ist wie eine riesige, hochgeschwindigkeitsfähige Detektivgeschichte, in der der Autor einen superschnellen Computer einsetzte, um jede einzelne „Verliererposition" (eine Stelle, an der der Spieler, der am Zug ist, bei perfektem Spiel des Gegners verlieren wird) für Schokoriegel bis zu 500 Quadraten Länge zu kartieren.

Hier ist das, was der Autor fand, einfach erklärt:

1. Die „Ein-und-Fertig"-Regel (Eindeutige Erweiterung)

Stellen Sie sich den Schokoriegel als vier Reihen vor. Die oberen drei Reihen haben bestimmte Längen (nennen wir sie A, B und C).

Die Entdeckung: Der Autor fand heraus, dass es für jede spezifische Kombination von Längen der oberen drei Reihen höchstens eine spezifische Länge für die vierte Reihe gibt, die eine „Verliererposition" erzeugt.
Die Analogie: Stellen Sie sich vor, Sie bauen einen Turm mit drei Blöcken bestimmter Größen. Wenn Sie wollen, dass der Turm „instabil" ist (eine Verliererposition), gibt es nur eine spezifische Größe des vierten Blocks, die ihn instabil macht. Sie können nicht einfach irgendeinen vierten Block wählen; die Mathematik zwingt zu einer einzigen, eindeutigen Antwort. Dies deutet darauf hin, dass das Spiel viel vorhersehbarer und „deterministischer" ist, als man dachte.

2. Der „Goldene Schnitt" der Schokolade (Asymptotische Verhältnisse)

Je länger der Schokoriegel wird (stellen Sie sich vor, er wird bis ins Unendliche gestreckt), desto mehr nehmen die Reihen eine bestimmte Form an.

Die Entdeckung: Die Längen der Reihen hören auf, sich zufällig zu ändern, und folgen stattdessen einem festen Muster. Wenn die oberste Reihe eine Länge von 100 hat, ist die zweite Reihe immer etwa 76 Einheiten lang, die dritte etwa 50 und die vierte etwa 22.
Die Analogie: Es ist wie ein wachsender Baum. Egal wie hoch der Baum wird, die Äste wachsen immer in denselben relativen Proportionen. Der Autor berechnete diese „Wachstumsraten", konnte aber noch keine einfache mathematische Formel (wie einen Bruch) finden, um sie exakt zu beschreiben. Sie liegen nahe an einigen berühmten Zahlen, doch das genaue Geheimnis bleibt verborgen.

3. Der „Versteckte Rhythmus" (Periode 112)

Der Autor suchte nach einem sich wiederholenden Muster in den Daten, wie einem Beat in einem Lied.

Die Entdeckung: Die Daten wiederholen ein bestimmtes Muster alle 112 Schritte.
Die Analogie: Stellen Sie sich eine Uhr vor, die nicht jede Sekunde tickt, sondern einen komplexen Rhythmus hat, der sich alle 112 Ticks zurücksetzt. Der Autor fand heraus, dass dieser Rhythmus wahrscheinlich eine Mischung aus zwei kleineren Rhythmen ist: einer, der sich alle 7 Schritte wiederholt (vererbt von der 3-Reihen-Version des Spiels), und einem anderen mysteriösen, der sich alle 8 Schritte wiederholt. Die Zahl 112 ist einfach das „kleinste gemeinsame Vielfache", bei dem sich diese beiden Rhythmen perfekt synchronisieren.

4. Die „Trichter"-Form (Lineare Kegelmengen-Geometrie)

Wenn man alle möglichen „Verliererpositionen" in ein Diagramm einträgt, sehen sie nicht wie eine zufällige Wolke aus Punkten aus.

Die Entdeckung: Sie bilden eine ordentliche, trichterähnliche Form (einen Kegel). Wenn die Reihen länger werden, wächst die „Breite" der gültigen Verliererpositionen in einer geraden, vorhersehbaren Linie.
Die Analogie: Stellen Sie sich vor, Sie gießen Sand in einen Trichter. Der Sand häuft sich nicht zufällig an; er bildet einen glatten, sich erweiternden Kegel. Der Autor fand heraus, dass die „gültigen" Verliererpositionen in diesem Spiel in eine ähnliche glatte, sich erweiternde Form passen, mit einem winzigen Wackeln, das durch den oben erwähnten 112-Schritte-Rhythmus verursacht wird.

Warum ist das wichtig?

Vor diesem Artikel war die 4-Reihen-Version von Chomp eine Blackbox. Wir wussten, dass der erste Spieler normalerweise gewinnt, aber wir wussten nicht warum oder wie die Verliererstellen angeordnet waren.

Der Autor fand 4,3 Millionen spezifische Verliererpositionen.
Er bewies, dass das Spiel wahrscheinlich strengen Regeln (der „Eindeutigen Erweiterung") folgt und nicht dem Chaos.
Er fand einen versteckten Rhythmus (112), der die Struktur des Spiels steuert.

Was der Artikel NICHT behauptet:

Er behauptet nicht, dass dies hilft, andere Spiele zu lösen (wie Schach oder Go).
Er behauptet nicht, dass dies medizinische oder reale Anwendungen hat.
Er beweist nicht, dass diese Regeln zu 100 % für unendliche Bretter gelten; er beweist nur, dass sie für den getesteten 500-Schritte-Bereich gelten. Der Autor nennt sie „Vermutungen" (starke Vermutungen basierend auf Beweisen) anstelle von bewiesenen Gesetzen.

Kurz gesagt: Der Autor nahm ein chaotisches, komplexes Spiel, führte eine massive Computersimulation durch und fand heraus, dass sich unter dem Chaos eine sehr ordentliche, rhythmische und vorhersehbare Struktur verbirgt, die darauf wartet, vollständig verstanden zu werden.

1. Problemstellung

Das Paper untersucht das kombinatorische Spiel Chomp, das auf einem rechteckigen Gitter der Größe $4 \times n$ gespielt wird.

Spielregeln: Die Spieler entfernen abwechselnd ein Quadrat sowie alle Quadrate darüber und rechts davon. Das oben links liegende Quadrat $(1,1)$ ist „vergiftet"; der Spieler, der gezwungen ist, es zu nehmen, verliert.
Ziel: Identifizierung von P-Positionen (Positionen, die für den vorherigen Spieler gewinnend sind, bzw. verlustbringend für den Spieler, der am Zug ist).
Kontext: Während die Fälle $1 \times n$ und $2 \times n$ vollständig gelöst sind und der Fall $3 \times n$ teilweise algorithmische Lösungen aufweist, fehlte für den Fall $4 \times n$ eine systematische computergestützte Analyse. Das Paper zielt darauf ab, diese Lücke zu schließen, indem P-Positionen tabelliert und zugrunde liegende strukturelle Muster identifiziert werden.

2. Methodik

Der Autor entwickelte einen optimierten Retrograde-Löser in C++, um P-Positionen für Brettbreiten bis zu $n = 500$ zu berechnen.

Zustandsrepräsentation:
- Positionen werden als nicht-abnehmende Tupel $(a, b, c, d)$ dargestellt, wobei $a \ge b \ge c \ge d \ge 0$ die Anzahl der Quadrate in jeder Reihe bezeichnet.
- Bitpacking: Jedes Tupel wird unter Verwendung von vier 16-Bit-Feldern in eine einzelne uint64-Ganzzahl kodiert, um den Speicherverbrauch zu minimieren und die Hash-Geschwindigkeit zu maximieren.
Algorithmus-Design:
- Sparsame Speicherung: Nur P-Positionen werden in einem Hash-Set gespeichert. Der Löser bricht die Berechnung für N-Positionen (gewinnend für den aktuellen Spieler) ab, sobald ein Zug zu einer bekannten P-Position gefunden wird.
- Bottom-Up-Auswertung: Zustände werden in aufsteigender Reihenfolge der Gesamtzellanzahl verarbeitet, wodurch sichergestellt wird, dass alle Nachfolger vor der Auswertung eines Zustands gelöst sind.
Leistung:
- Berechnung von 4.316.097 P-Positionen für $n \le 500$ .
- Ausführungszeit: ca. 70 Minuten auf einem Apple M4-Prozessor.
- Speicherverbrauch: Spitzenauslastung von 45 MB.
Verifizierung:
- Validierung gegen die bekannte $2 \times n$ -Formel (wobei $c=d=0$ impliziert $b=a-1$ ).
- Kreuzprüfung mit einem unabhängigen Python-Löser für den $3 \times n$ -Teilfall ( $d=0$ ) bis $n=50$ .
- Korrektur eines anfänglichen Fehlers bei der Spaltenausrichtung in der Datenausgabe.

3. Hauptbeiträge und Ergebnisse

Die Analyse des berechneten Datensatzes führte zu vier primären strukturellen Vermutungen:

A. Vermutung 1: Eigenschaft der eindeutigen Erweiterung

Aussage: Für jedes gültige Tripel von Reihenlängen $(a, b, c)$ existiert höchstens eine ganze Zahl $d$ , sodass $(a, b, c, d)$ eine P-Position ist.
Implikation: Die Projektionsabbildung $\pi: (a, b, c, d) \to (a, b, c)$ ist auf der Menge der P-Positionen injektiv.
Bedeutung: Dies legt nahe, dass das $4 \times n$ -Spiel eine „deterministische Hebung" des $3 \times n$ -Spiels ist. Zwar erweitert sich nicht jedes $(a, b, c)$ zu einer P-Position (nur etwa 20 % tun dies), aber falls eine Erweiterung existiert, ist die Länge der vierten Reihe $d$ eindeutig festgelegt. Dies steht im Gegensatz zum Fall $3 \times n$ , für den bisher keine derart einfache injektive Abbildung etabliert war.

B. Vermutung 2: Asymptotische Verhältnisse

Aussage: Wenn die Brettbreite $a \to \infty$ $a \to \infty$ geht, konvergieren die Verhältnisse der Reihenlängen in P-Positionen zu festen Konstanten:
- $b/a \to L_1 \approx 0,762$
- $c/a \to L_2 \approx 0,499$
- $d/a \to L_3 \approx 0,224$
Methodik: Geschätzt mittels Fenster-Medians, gleitender Fenster und Anpassung von Potenzgesetzkurven.
Beobachtung: Es wurde keine exakte algebraische Identität für diese Konstanten gefunden. Allerdings ist $L_3 \approx 0,224$ bemerkenswert nahe an $\cos(3\pi/7) \approx 0,2225$ , was auf eine potenzielle verborgene algebraische Beziehung hindeutet.

C. Vermutung 3: Modulare Struktur mit Periode 112

Aussage: Die Menge der Tripel $(a, b, c)$ , die sich zu P-Positionen erweitern lassen, weist eine modulare Struktur mit einer Grundperiode von 112 auf.
Evidenz:
- Die Autokorrelationsanalyse der Sequenz der $d$ -Werte zeigt einen scharfen Peak bei der Verzögerung 112.
- Ein logistischer Klassifikator, der nur $c$ und $(a-b) \pmod{112}$ verwendet, sagt die Erweiterbarkeit mit 79 % Genauigkeit voraus.
- Chi-Quadrat-Tests bestätigen, dass der Modul 112 die stärkste statistische Trennung bietet ( $\chi^2 = 12.433$ ) im Vergleich zu anderen Moduli.
Interpretation: $112 = \text{kgV}(7, 8) \times 2$ . Der Faktor 7 stammt wahrscheinlich von der Periodizität des $3 \times n$ -Teilspiels, während der Faktor 8 ungeklärt bleibt (Bit-Packing-Artefakte wurden ausgeschlossen).

D. Vermutung 4: Lineare Kegelgeometrie

Aussage: Die Menge der erweiterbaren Tripel $(a, b, c)$ bildet einen linearen Kegel in $\mathbb{R}^3$ .
Geometrie: Für ein festes $c$ bildet der gültige Bereich von $(a, b)$ einen zusammenhängenden Streifen. Die Breite dieses Streifens wächst linear mit $c$ :
$\text{width}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$
wobei $f$ eine beschränkte periodische Funktion ist. Die Steigung $11/8 = 1,375$ wurde aus schnittbasierten Messungen abgeleitet.

4. Bedeutung und zukünftige Richtungen

Strukturelle Einsicht: Die Ergebnisse deuten darauf hin, dass $4 \times n$ Chomp eine reichhaltigere, deterministischere Struktur besitzt als bisher vermutet, die aufgrund der Eigenschaft der „eindeutigen Erweiterung" möglicherweise einfacher ist als der Fall $3 \times n$ .
Verallgemeinerung: Der Autor hypothesiert, dass sich die Eigenschaft der eindeutigen Erweiterung auf $k \times n$ Chomp für alle $k$ verallgemeinern lässt, was impliziert, dass alle Chomp-Spiele rekursiv durch den gelösten Fall $2 \times n$ bestimmt sind.
Offene Fragen:
1. Beweis: Kann die Eigenschaft der eindeutigen Erweiterung kombinatorisch bewiesen werden?
2. Algebraische Grenzen: Sind die asymptotischen Verhältnisse Wurzeln eines gemeinsamen Polynoms?
3. Höhere Dimensionen: Gilt dies für $5 \times n$ ? (Erfordert einen Zustandsraum von $O(n^5)$ ).
4. Ursprung der Periode: Was ist die Quelle der period-8-Komponente im 112-Zyklus?
5. Geschlossene Form: Können die etwa 20 % erweiterbaren Tripel durch eine geschlossene Form-Maske beschrieben werden?

Das Paper vermerkt zudem die Einreichung der Sequenz der $d$ -Werte bei der On-Line Encyclopedia of Integer Sequences als A395126. Der Code und die Daten sind über das GitHub-Repository des Autors öffentlich verfügbar.