Es gibt keine erreichbare Schachstellung mit mehr als 218 möglichen Zügen

 (lichess.org)
1 Punkte von GN⁺ 2025-09-27 | 1 Kommentare | Auf WhatsApp teilen
  • Es gibt keine Stellung mit mehr möglichen Zügen als die 218-Züge-Schachstellung, die 1964 von Nenad Petrović veröffentlicht wurde
  • Da es praktisch unmöglich ist, alle Stellungen zu durchsuchen, wurde die Grenze mithilfe mathematischer Optimierung und computergestützter Modellierung bewiesen
  • Durch das Entfernen unnötiger Figuren, das Zulassen teilweiser Figurenplatzierungen und die Vereinfachung der Rochade wurde der Suchraum effektiv reduziert
  • Abschließend wurde mit dem Optimierungstool Gurobi bestätigt, dass 218 Züge das Maximum sind; zusätzlich wurden Rekorde wie 144 Züge (ohne Umwandlungen) verifiziert
  • Diese Forschung beseitigt für Entwickler von Schach-Engines und Kompressionsverfahren die Unsicherheit über die maximale Zuganzahl

Einleitung: die Debatte um die 218-Züge-Schachstellung

Seit der Veröffentlichung einer Stellung mit 218 möglichen Zügen durch den Schachkompositions-Großmeister Nenad Petrović im Jahr 1964 gab es immer wieder Versuche, diesen Rekord zu brechen. Der Autor wollte als Informatiker dieser Frage ein Ende setzen, indem er alle Stellungen mit dem Computer analysierte. Es gibt zwar etwa 4,8 × 10^44 erreichbare Schachstellungen, doch eine derart gewaltige Suche ist in der Praxis unmöglich.

Einführung mathematischer Optimierung

Minimierung unnötiger Figuren und Kombinationen

  • Zusätzliche schwarze Figuren vergrößern die Zahl der Züge nur in begrenzten Fällen
    • etwa wenn sie von weißen Bauern geschlagen werden können oder eine Schachsituation gegen den gegnerischen König vermieden wird
  • Die meisten schwarzen Figuren können entfernt werden, ohne die maximale Zahl möglicher Züge zu beeinflussen
  • Solange die Figurenanzahl zulässig bleibt, können schwarze Figuren durch schwächere Figuren ersetzt oder ihre Platzierung unter gewissen Nebenbedingungen (wie Fesselungen) angepasst werden
  • Bei weißen Figuren ist die Lage umgekehrt: Würden sie in einer optimalen Stellung alle durch starke Figuren wie Damen ersetzt, könnten illegale Stellungen entstehen, weshalb eine feinere Abstimmung nötig ist

Schachsituationen und Begrenzung der Zugzahl

  • Ein schwarzer König im Schach ist keine legale Stellung und muss daher nicht betrachtet werden
  • Wenn der weiße König im Schach steht, sind die Zugmöglichkeiten stark eingeschränkt (maximal 120 Züge), sodass 218 unerreichbar sind
  • Daher kann die Suche auf Stellungen ohne Schachgebot beschränkt werden

Teilweise Figurenplatzierung und mathematische Modellierung

Um die kombinatorische Komplexität zu reduzieren, wurde ein Modell mit teilweiser (fractional) Figurenplatzierung, Zügen und gelockerten Schachregeln verwendet

  • Zum Beispiel kann eine Figur mit 27,3 % Wahrscheinlichkeit auf e4 stehen und mit 72,7 % auf einer anderen Position
  • Dieser Ansatz wurde mit modernen Optimierungstools wie Gurobi als Integer Linear Programming (ILP) umgesetzt
  • Anfangs scheiterte dies an Speicher- und Laufzeitgrenzen (Speichermangel nach etwa 55.000 Sekunden)
  • Um den Suchraum weiter zu vereinfachen, wurden zusätzliche Maßnahmen angewandt, darunter eine vereinfachte Rochaderegel, das Ignorieren von Schach, das Ignorieren von Fesselungen und die Vereinfachung der En-passant-Bedingungen

Optimierung und Schlussfolgerung

Schließlich wurde das Modell durch zusätzliche Nebenbedingungen verbessert, die unnötige Kombinationssuche ausschließen, und die Optimierung mit Gurobi abgeschlossen

  • Die Obergrenze wurde schrittweise von 305 Zügen über 271,67 auf 218 Züge gesenkt
  • Es wurde bestätigt, dass nur 12 repräsentative Stellungen mit 218 möglichen Zügen erreichbar sind
  • Für diese Stellungen wurde mittels Proof Games nachgewiesen, dass sie legal und ohne Weiteres erreichbar sind

Außerdem wurden 144 Züge als Maximum ohne Umwandlungen, 288 Züge in illegalen Stellungen sowie 271 Züge in legalen, aber nicht erreichbaren Stellungen verifiziert

Ergebnisse und Bedeutung

  • Dank dieser Forschung können Entwickler von Schach-Engines und Forscher zu Kompressionsalgorithmen sicher sein, dass ein Limit von 256 Zügen für Dinge wie Speicherdesign ausreicht
  • Es ist mathematisch bewiesen, dass es keine Stellung gibt, in der auf legalem Weg mehr als 218 Züge in einem Zug verfügbar sind

FAQ-Zusammenfassung

  • Eine Schachpartie kann länger sein als 218 Züge, doch diese Forschung behandelt die maximale Zahl möglicher Optionen in einem einzelnen Zug
  • Falls manche Stellungen unerreichbar erscheinen, wird darauf hingewiesen, dass es verschiedene Wege geben kann, etwa wenn der vorherige Zug mit einem Schlag endete
  • Die Forschungsmethode nutzt eine mathematische Orakeltechnik, um in einem riesigen kombinatorischen Raum „absolut unmögliche Kombinationen“ schnell auszusortieren
  • Zur Absicherung der Glaubwürdigkeit wurden sowohl der verwendete Code als auch die mathematische Gültigkeit der abgeleiteten Beweise offengelegt

Künftige Aufgaben und weitere Forschungsvorschläge

Mit dieser Technik lassen sich auch andere Schachfragen angehen, etwa „die meisten Schlagzüge“, „die meisten Pattstellungen“, „die meisten Schachgebote“, „die meisten Schachmatts“ oder „die meisten Matt in zwei“. In manchen Fällen könnten dafür jedoch eigene kreative Optimierungsalgorithmen nötig sein.

Fazit

  • 218 ist die offizielle maximale Anzahl möglicher Züge in einer Schachstellung für einen einzelnen Zug
  • Praktisch bedeutet das, dass Schachsoftware und Forscher ihre Strukturen auf 218 (oder 256) auslegen können
  • Der zugehörige Code und die Optimierungsergebnisse wurden auf GitHub veröffentlicht

Referenz

  • Enthält Links zu Proof Games und Stellungen, darunter Nenad Petrovićs 218-Züge-Stellung und Jenő Báns 144-Züge-Stellung (ohne Umwandlungen)
  • Ausführliche Erklärungen und der Code sind im Github-Repository zu finden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-09-27
Hacker-News-Kommentare
  • Auch wenn sie es nicht direkt so formuliert haben, ist hier gemeint: „In dieser Position hat der Spieler 218 legale Züge zur Auswahl“
    • Danke, ich bin überrascht, dass ich den Artikel die ganze Zeit falsch gelesen hatte. Ich hatte es so verstanden, dass „die maximale Anzahl an Zügen, die nötig ist, um irgendeine Schachposition zu erreichen, 218 beträgt“. Deshalb habe ich mich gefragt, warum der Artikel für mich überhaupt keinen Sinn ergab
    • Ich hatte auch gedacht: „Wie viele Züge braucht man in einer Partie, um diese Position zu erreichen?“
    • Ja, es ist wirklich seltsam, dass der Ausdruck „possible moves“ im Artikel kein einziges Mal vorkommt. Das Schlüsselwort ist „possible“. Der Artikel formuliert es durchgehend eher als „have moves“, was für Laien ungewohnt ist. Vielleicht ist das in der Schachterminologie üblicher
    • Danke. Ich war von dem Artikel verwirrt und dachte, es gehe um die Position, die als einzige die meisten Züge benötigt
  • Ich möchte Lichess ausdrücklich loben. Ein fantastischer Service mit großartigen Inhalten, kostenlos, und sogar Funktionen, die bei Chess.com kostenpflichtig sind, sind dort gratis verfügbar. Auch die vielen Varianten sind wirklich beeindruckend
    Auf Lichess ist das Spielniveau in Varianten wie 960 oder Crazyhouse viel höher als auf Chess.com
    • Es ist kostenlos, bietet dieselben Funktionen wie kommerzielle Server, ist Open Source und entwicklerfreundlich. Dazu keine Werbung, wirklich gar keine, auch nicht für kostenlose Accounts, und eine transparente Organisationsstruktur nach französischem Recht
      Es ist buchstäblich absurd gut. Wenn möglich, sollte man es unterstützen
  • Im Beitrag https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow erklärt der Autor, dass er anfangs einige komplexe Regeln entfernt hat und bereit war, sie bei Bedarf wieder einzuführen, falls das gefundene Ergebnis diese Regeln verletzen würde
    Interessant ist, dass Mixed-Integer-Linear-Programming-(MILP)-Solver genau so etwas bereits unterstützen. Im Fachjargon heißt das „row generation“ und wird typischerweise verwendet, wenn man ein Problem als Matrix schreibt, bei der die Zeilen die Nebenbedingungen und die Spalten die Variablen sind
    Das dynamische Hinzufügen neuer Zeilen ist gleichbedeutend damit, Nebenbedingungen nur dann einzuführen, wenn sie verletzt werden
    Diese Methode wird vor allem beim Traveling Salesman Problem eingesetzt
    (Nebenbei: In Wikipedia gibt es Column generation, aber keinen Eintrag zu row generation)
    • Hallo, ich bin der Autor des Lichess-Artikels
      Das Abschwächen oder Weglassen von Schachregeln hatte auch Auswirkungen auf die Wahl der Variablen. Vor dem mathematischen Modellieren habe ich Dinge wie lazy constraints ausprobiert, aber das brachte keine nennenswerte Beschleunigung. Schon allein nicht zu berücksichtigen, ob der weiße König im Schach steht, führte zu vielen Vereinfachungen
    • Diese Art von Vorgehen wird gewöhnlich eher als lazy constraints bezeichnet (Erklärung dazu)
    • Ich frage mich wirklich, ob ein MILP-Solver in diesem gewaltigen Suchraum überhaupt terminieren kann; mein Gefühl sagt eher nein
  • Mal ganz ehrlich aus Neugier: Wenn der Integer-Programming-Solver von Gurobi keine bessere Lösung als 218 gefunden hat, garantiert das dann auch, dass es keine bessere als 218 gibt? Und ist das gleichbedeutend mit einem mathematischen Beweis?
    (Vorausgesetzt, Gurobi hat keinen Bug, und auch die Problemdefinition und Implementierung des Autors sind fehlerfrei.)
    Ich frage mich, ob Gurobi in einem lokalen Maximum stecken könnte oder ob wirklich ein globales Optimum bewiesen wurde
    • Gurobi liefert nicht nur die beste bisher gefundene ganzzahlige Lösung, sondern auch eine Schranke für die mögliche optimale Lösung. Dafür werden verschiedene Techniken verwendet, etwa die lineare Relaxation des Problems, Cutting Planes usw. Wenn der Solver also keinen Bug hat, ist das Ergebnis tatsächlich optimal
    • Hier der Autor!
      Wenn Gurobi und mein Code wie beabsichtigt funktionieren und ich beim Vereinfachen des Schachmodells keinen logischen Fehler gemacht habe, dann habe ich bewiesen, dass „die maximale Anzahl möglicher legaler Züge unter allen Schachpositionen, die aus der Ausgangsstellung durch eine legale Zugfolge erreichbar sind, sowohl nach oben als auch nach unten durch 218 beschränkt ist“. Gurobi hat also durch Schranken über den gesamten Suchraum gezeigt: besser als das geht es nicht
    • Ich weiß nicht genau, wie Gurobi hier konkret eingesetzt wurde, aber im Allgemeinen erzeugen solche kombinatorischen Optimierungssolver einen Beweisbaum, der zeigt, dass für keine Variablenbelegung eine bessere Lösung möglich ist. In einfachen Fällen kann man diesen Baum tatsächlich durchgehen und den Widerspruch nachvollziehen. Beim Fall aus dem Artikel wäre dieser Beweisbaum vermutlich enorm groß. Wenn man möchte, könnte man ihn aber prüfen
    • Theoretisch ist es kein Beweis, praktisch aber fast wie einer

  • Es gibt keine erreichbare Schachposition mit mehr als 218 Zügen
    „mit höchstens 218 legalen Folgezügen“ wäre deutlich klarer formuliert

Alle rund 8,7x10^45 erreichbaren Schachpositionen überprüfen?
Diese Zahl ist in Wirklichkeit zu hoch angesetzt
https://github.com/tromp/ChessPositionRanking schätzt die Zahl legaler Schachpositionen genauer auf etwa 4,8x10^44

  • Ist diese Schätzung nicht einfach nur ungefähr um den Faktor 20 anders? In dieser Größenordnung scheint das kein großer Unterschied zu sein
  • Das eine sind „legale“ Positionen, das andere ist der „gesamte Problemraum“
    Aus Sicht des Computings ist der gesamte Problemraum wichtiger, weil man alles erst einmal „berechnen“ muss, bevor man feststellen kann, ob es legal ist. Es gibt keine einfache Methode, nur über legale Positionen zu iterieren
  • Hallo zusammen
    Ein Bekannter hat mich darauf hingewiesen, dass mein Artikel hier diskutiert wird
    Entschuldigt bitte den weniger klaren Titel; ich hoffe, inzwischen ist es klarer geworden. Danke für das Feedback und die freundlichen Worte
    Wenn ihr auch Fragen zu ähnlichen Beweisen über Schachfakten habt, beantworte ich sie gern ^^
    Danke
    Tobi
    • Nur um sicherzugehen: Gemeint ist also, dass es für keine Brettstellung mehr als 218 auswählbare Züge gibt? Verstehe ich das richtig?
  • Wie viele Bits braucht man mindestens, um ein erreichbares Schachbrett darzustellen?
    Update: Im Artikel ist von etwa 8,7x10^45 erreichbaren Schachpositionen die Rede, und https://github.com/lechmazur/ChessCounter verwendet diese Zahl als obere Schranke
    (Das entspricht ungefähr 153 Bit)
    • Wenn es eher etwa 4,8x10^44 sind, dann ergibt log2(4.8x10^44) ungefähr 149 Bit
      Für eine effiziente Dekodierung braucht man aber 153 Bit, nämlich den aufgerundeten log2-Wert der von ChessPositionRanking empfohlenen Zahl (8726713169886222032347729969256422370854716254). ChessCounter liefert keinen Code für effiziente Dekodierung
    • Der König kann auf jedes der 64 Felder
      Dasselbe gilt für Turm/Dame/Springer, aber diese können im Schach geschlagen worden sein, also braucht man insgesamt 65 Zustände für jedes dieser 5 Stücke
      Läufer können nur auf die Hälfte dieser Felder, also je 33 Zustände
      Bauern haben 4 Umwandlungsarten, können geschlagen sein und stehen je nach Fall auf ungefähr 20 bis 30 möglichen Positionen; insgesamt also etwa 290 Zustände pro Bauer
      Damit kommt man für eine Farbe auf ungefähr 112 Bit zur Darstellung des Brettzustands, aufgerundet also 224 Bit für beide Seiten zusammen
      En passant und Rochade-Einschränkungen lassen sich durch Aufrunden ohne zusätzliche Bits unterbringen; es kommen nur ein paar Zustände pro Figur hinzu
      Das ist vermutlich die kompakteste Form einer Darstellung mit fester Länge
      Bei einer sparsamen Darstellung könnte man, da die beiden Könige immer vorhanden sind, die noch lebenden Figuren über eine n-stellige Dezimalzahl und n+2 Zahlen zu je 64 Bit für die Positionen kodieren; Rochade, en passant usw. bräuchten dann nur wenig Zusatzinformation. Wenn im Mittel ungefähr die Hälfte der Figuren verschwunden ist, braucht man im Schnitt etwa 180 Bit pro Brettzustand
      Für die Zughistorie braucht man ebenfalls ungefähr 10 Bit pro Zugpaar, also 5 Bit pro Ply, daher reichen die Bits nur für etwa 18 Züge. Das ist etwas kürzer als die Mitte einer durchschnittlichen Schachpartie
      Noch stärker zu komprimieren scheint nur mit einem enorm großen Wörterbuch möglich zu sein
    • Figurentyp und Farbe lassen sich in 4 Bit kodieren
      Dann kann man das gesamte Brett mit fester Länge als 64*4=256 Bit = 32 Byte kodieren
      Oder, in einer variablen Darstellung nur für vorhandene Figuren, verwendet man für jedes Feld einen Index mit 6 Bit, also insgesamt Anzahl*10 Bit
      Die Ausgangsstellung wäre dann zum Beispiel 32*10=320 Bit = 40 Byte
    • Der 8.7e45-Wert „restricted“ in dem GitHub-Projekt beschränkt einige Bauernumwandlungsmuster
      5.68e50 „general“ ist die echte obere Schranke und erlaubt alle möglichen Umwandlungen
  • Der schwarze Bauer auf b2 reduziert die möglichen Züge der anderen Figuren ziemlich stark
    Dieser Bauer hat selbst nur einen möglichen Zug, nämlich den benachbarten Springer zu schlagen. Wenn er nicht da wäre, könnten vier weiße Damen und Springer nach b2 ziehen. Allerdings wäre der schwarze König dann bereits schachmatt, sodass diese Züge real gar nicht möglich wären
    Es ist verlockend, die Dame auf e5 woanders hinzusetzen, sodass es nicht sofort Schachmatt ist und das Feld b2 offener wird
    P.S.: Es sieht so aus, als müsse dieser Bauer dort am Leben bleiben, um Patt zu verhindern
    • In der Stellung mit Weiß am Zug kann sich der schwarze Bauer auf b2 nicht bewegen
      Wenn Schwarz am Zug wäre, könnte er sich wegen des weißen Damenzugs auf e5 ebenfalls nicht bewegen, weil der König dadurch gefesselt ist. Ohne diese Fesselung hätte er 4 mögliche Züge. Unterverwandlung ist auch möglich
    • Ich war auch von der Formulierung „die schwarzen Figuren sind nutzlos“ verwirrt. Man könnte doch einfach eine der beiden Damen schwarz machen, statt zwei Damen einander anzusehen, und so Schlagzüge erzeugen … aber dann wurde mir klar, dass am Ende nur eine Seite am Zug sein kann
    • Hier der Autor
      Die Stellung ist mit Weiß am Zug. Selbst wenn der Bauer auf b2 den schwarzen König nicht durch die weiße Dame fesseln würde, könnte sich der schwarze Bauer nicht bewegen
      Der Bauer auf b2 ist zwingend notwendig, um den schwarzen König vor Schach zu schützen. Sonst wäre die Stellung selbst nicht legal
      Ich habe wirklich alles sehr sorgfältig geprüft, also keine Sorge: Jeder Versuch, für Weiß mehr als 218 Züge zu konstruieren, ist gescheitert. Trotzdem bin ich überrascht und dankbar, dass sich so viele für meinen Artikel interessieren, haha ^^
    • Weiß ist am Zug. Wenn Schwarz im Schach stünde und Weiß am Zug wäre, dann wäre die Stellung nicht legal und nicht erreichbar. Es gäbe keine Möglichkeit, dass Schwarz das in seinem vorherigen Zug legal herbeigeführt hätte
      Man könnte meinen, man könne einen der schwarzen Bauern in einen weißen Springer verwandeln, um die Zahl der Züge zu erhöhen, aber beide Springer sind bereits vorhanden, und alle Bauern sind schon umgewandelt, also geht das nicht. (Wenn man beide Bauern ändern würde, könnte Schwarz diese Stellung im vorherigen Zug nicht erreicht haben.)
  • Ich bin verwirrt. Aber nach dem Modell mit 271: Welche Änderungen haben denn anschließend zur optimalen Lösung geführt? Da steht nur „mit diesem verbesserten Modell …“
    • Hier der Autor!
      Hast du den ganzen Artikel gelesen?
      Es sind nicht 271, sondern 271.666... :) Diese Zahl stammt aus einem Modell, in dem alle Entscheidungen, also 0 oder 1, zu kontinuierlichen Werten zwischen 0.0 und 1.0 relaxiert wurden. Man tut also so, als könne eine Figur zu 0.23 existieren. Auch die Möglichkeit, einen bestimmten Zug auszuführen, wird dann etwa als 0.843 behandelt.
      Mit dieser Art von „Black Magic“ wird die Berechnung viel schneller, und man bekommt mehr mögliche Züge heraus, als es in Wirklichkeit geben kann.
      So kann man diese Methode nutzen, um schnell Teilräume auszuschließen, die potentiell ungünstig sind. Ohne solche Techniken wäre es unmöglich, den gesamten Suchraum vollständig zu durchsuchen
  • Übersehe ich etwas, oder ist die am Anfang gezeigte Stellung in Wirklichkeit gar nicht erreichbar? Weiß ist am Zug, aber die schwarzen Bauern stehen auf ihren Ausgangsfeldern, und der König hat keine angrenzenden freien Felder; er scheint von Figuren und Bauern eingeschlossen zu sein, also sieht es so aus, als könne diese Stellung gar nicht erreicht werden
    • Der Beweis, dass diese Stellung tatsächlich erreichbar ist, steht hier: https://lichess.org/study/PLtuv3v5/zWPNxbSA
      Ich glaube übrigens, du irrst dich in der Annahme, die schwarzen Bauern stünden auf ihren Ausgangsfeldern. Tatsächlich ist der schwarze Bauer bis auf die gegenüberliegende Brettseite vorgedrungen, also in die weiße Hälfte
    • Der schwarze Bauer befindet sich auf der weißen Brettseite, also auf der 1. oder 2. Reihe