Gewinnstrategie für Brettspiele bestimmen

Die Frage, ob ein Brettspiel eine „Gewinnstrategie“ (oder eine Remis-Strategie) besitzt, fällt in der Mathematik und Informatik in den Bereich der Kombinatorischen Spieltheorie (Combinatorial Game Theory). Um eine solche Strategie zu erkennen und zu finden, müssen die Eigenschaften des Spiels untersucht und entsprechende mathematische Sätze und Algorithmen angewendet werden.

Hier sind die gängigen Theorien und Methoden zur Bestimmung und zum Nachweis einer Gewinnstrategie:

1. Prüfen, ob das Spiel die Voraussetzungen des Zermelo-Theorems erfüllt

Bevor man über Gewinnstrategien spricht, muss man klären, ob das Spiel ein „endliches Zwei-Personen-Nullsummen-Spiel mit vollständiger Information“ ist.

• Zwei Personen: Es gibt genau zwei Spieler.
• Nullsumme (oder Sieg/Unentschieden/Niederlage): Der Gewinn des einen ist der Verlust des anderen; es gibt keinen Doppelsieg.
• Vollständige Information: Es gibt keine verborgenen Informationen (wie verdeckte Karten beim Pokern); beide Spieler sehen den gesamten Spielzustand.
• Deterministisch: Keine Zufallselemente wie Würfeln.
• Endlichkeit: Das Spiel endet nach endlich vielen Zügen, es gibt keine unendlichen Schleifen.

Das Zermelo-Theorem besagt: Für jedes Spiel, das diese Bedingungen erfüllt, gibt es bei optimalem Spiel beider Seiten ein eindeutiges Ergebnis:

1. Der Startspieler gewinnt;
2. Der zweite Spieler gewinnt;
3. Beide erreichen ein Unentschieden (falls die Regeln dies zulassen, wie bei Schach oder Tic-Tac-Toe).

Das heißt, solange diese Bedingungen erfüllt sind (z.B. bei Schach, Go, Gomoku, Othello), existiert theoretisch immer eine Gewinn- oder Nichtverlier-Strategie. Die Frage ist nun, „welche der drei Möglichkeiten zutrifft“ und „wie man sie findet“.

2. Brute-Force-Suche und Rückwärtsinduktion (Spielbaum-Exploration)

Bei Spielen mit kleinem Zustandsraum können alle möglichen Stellungen aufgezählt und ein „Spielbaum“ erstellt werden.

• Methode (Rückwärtsinduktion): Beginne bei den Endzuständen (Sieg, Niederlage, Unentschieden) und arbeite zurück zum Start.
• Algorithmus (Minimax): Angenommen, beide Spieler machen keine Fehler; der Startspieler wählt den für ihn besten Zug (Max), der zweite Spieler den für den Startspieler schlechtesten (Min).
• Anwendungen:
  • Tic-Tac-Toe: Der Zustandsraum ist winzig; leicht abzuleiten, dass bei optimalem Spiel Unentschieden folgt.
  • Vier gewinnt (Connect Four): Wurde von Computern vollständig gelöst; es wurde bewiesen, dass der Startspieler gewinnt.

3. Strategie-Diebstahl-Argument (Strategy-Stealing Argument)

Dies ist eine sehr elegante Existenzbeweismethode (Widerspruchsbeweis). Sie zeigt, dass der Startspieler gewinnen muss, gibt aber nicht die konkreten Züge an.

• Logik: Angenommen, der zweite Spieler hätte eine Gewinnstrategie. Dann macht der Startspieler einen beliebigen ersten Zug und „stiehlt“ die Gewinnstrategie des zweiten Spielers, indem er sich selbst als zweiten Spieler betrachtet. Wenn in diesem Spiel ein zusätzlicher eigener Stein immer vorteilhaft ist, dann gewinnt der Startspieler mit der gestohlenen Strategie. Dies widerspricht der Annahme, dass der zweite Spieler gewinnt!
• Schlussfolgerung: In solchen Spielen, in denen der zweite Spieler nicht gewinnen kann und es kein Unentschieden gibt, muss der Startspieler gewinnen.
• Anwendungen:
  • Hex: Die Regeln erlauben kein Unentschieden, und ein zusätzlicher Stein ist nie schädlich. Daher bewies der Mathematiker John Nash mit dieser Methode, dass Hex vom Startspieler gewonnen wird.
  • Gomoku (ohne Verbote): Ebenfalls wurde bewiesen, dass der Startspieler gewinnt (später fanden Computer konkrete Gewinnzüge, was zur Einführung von „Verboten“ für Schwarz führte, um das Spiel auszugleichen).

4. Symmetrie finden (Symmetry / Pairing Strategy)

Wenn das Brett eine Symmetrie aufweist und die Spielregeln es erlauben, kann ein Spieler durch „Nachahmen“ der gegnerischen Züge eine Gewinnstrategie erhalten.

• Beispiel (Münzenspiel): Auf einem runden Tisch werden abwechselnd Münzen flach gelegt; wer keine Münze mehr platzieren kann, verliert. Der Startspieler legt die erste Münze genau in die Mitte; dann legt er jede weitere Münze spiegelsymmetrisch zur Mitte zur gegnerischen Münze. Diese Strategie garantiert einen Sieg des Startspielers.

5. Sprague-Grundy-Theorem (für unparteiische Spiele)

Wenn das Spiel „unparteiisch“ (Impartial Game) ist – d.h. für eine gegebene Stellung sind die legalen Züge für beide Spieler identisch (z.B. Nim) – dann kann das SG-Theorem angewendet werden.

• Methode: Jede komplexe Stellung wird in ein äquivalentes Nim-Spiel umgewandelt (Berechnung der SG-Funktion / XOR-Summe).
• Schlussfolgerung: Wenn die Nim-Summe (oder der SG-Wert) der Anfangsposition ungleich Null ist, gewinnt der Startspieler; ist sie Null, gewinnt der zweite Spieler.

Zusammenfassung

• Theoretisch: Jedes endliche Zwei-Personen-Spiel mit vollständiger Information ohne Zufall besitzt eine perfekte Strategie (Sieg oder Unentschieden).
• Wie findet man sie:
  1. Kleines Brett: Manuelle Rückwärtsinduktion.
  2. Mathematisches Modell (z.B. Nim): Berechnung des SG-Werts oder Symmetrie finden.
  3. Spezielle Eigenschaften: „Strategie-Diebstahl“ zum Beweis des Startspielersiegs.
  4. Großes Brett (z.B. Go, Schach): Derzeit können Menschen und KI nur „optimale Lösungen“ berechnen, die dem Sieg nahekommen, aber im streng mathematischen Sinne ist für diese komplexen Spiele, ob der Startspieler gewinnt oder es ein Unentschieden gibt, aufgrund der Rechenleistung nicht vollständig zu klären – das Ergebnis ist unbekannt.

Bei der Diskussion der Gewinnstrategie von Gomoku muss zunächst eine absolute Voraussetzung klargestellt werden: Hier geht es um das traditionelle Gomoku ohne Verbote (freies Gomoku).

Im verbotsfreien Gomoku hat der Startspieler (Schwarz) eine Gewinnstrategie. Deshalb müssen moderne offizielle Gomoku-Wettbewerbe (Renju) „Verbote für Schwarz“ (wie Drei-und-Drei-Verbot, Vier-und-Vier-Verbot, Überfünf-Verbot) und komplexe Eröffnungsregeln (wie die Yamaguchi-Regel) einführen, um diese Startspieler-Gewinnsituation zu durchbrechen und das Spiel fair zu machen.

Hier sind die Details der Gewinnstrategie für verbotsfreies Gomoku und wie sie entdeckt wurde:

I. Was ist die Gewinnstrategie bei Gomoku?

Die Gewinnstrategie bei Gomoku besteht nicht darin, eine feste „Zugfolge“ auswendig zu lernen, da die Verteidigungsmöglichkeiten des Gegners unzählig sind. Die Gewinnstrategie ist im Wesentlichen ein taktisches System, das durch ständigen Druck mit „absolutem Vorrang“ den Gegner zwingt, schließlich mehrfachen Bedrohungen ausgesetzt zu sein, die nicht gleichzeitig abgewehrt werden können.

Konkret basiert die Gewinnstrategie von Schwarz auf folgenden Kernpunkten:

1. Eröffnungswahl:
   Auf einem 15×15-Brett setzt Schwarz den ersten Stein auf den Tengen (Mitte). Wenn Weiß nach dem zweiten Zug verteidigt, kann Schwarz mit bestimmten Eröffnungsformationen (wie „Blütenmond“ (Hana-getsu) oder „Pumond“ (Ura-getsu)) den Sieg garantieren.
2. Kerntaktiken: VCT und VCF
   • VCF (Victory by Continuous Four – Sieg durch fortlaufende Vierer): Schwarz setzt bei jedem Zug einen „offenen Vierer“ (Weiß muss sofort blocken), und während dieser ununterbrochenen Vierer-Züge verbinden sich die Steine von Schwarz unmerklich zu einer Kette, die schließlich einen tödlichen Angriff (z.B. Vier-Drei) ermöglicht.
   • VCT (Victory by Continuous Threats – Sieg durch fortlaufende Drohungen): Schwarz setzt bei jedem Zug einen „lebenden Drei“ oder „offenen Vierer“, sodass Weiß nur passiv blocken kann, ohne kontern zu können.
3. Schaffen von Kreuzungspunkten (Töten vorbereiten):
   Durch die ständigen Angriffe zielt Schwarz darauf ab, auf dem Brett eine „Doppel-Drei“-, „Doppel-Vier“- oder „Vier-Drei“-Situation zu erzeugen. Da Weiß nur einen Punkt pro Zug blocken kann, ist er bei mehrfachen Bedrohungen überfordert, und Schwarz gewinnt.

II. Wie wurde diese Gewinnstrategie entdeckt und bewiesen?

1. Erfahrung und Intuition (frühe menschliche Phase)

Seit Jahrhunderten wussten Gomoku-Meister aus der Praxis, dass der Startspieler einen enormen Vorteil hat. Die Japaner erkannten bereits im späten 19. Jahrhundert, dass ein hochrangiger Schwarz-Spieler ohne Einschränkungen praktisch unschlagbar ist. Daher entwickelten sie nach und nach die Renju-Regeln mit Verboten. Zu diesem Zeitpunkt war der Startspielersieg jedoch nur ein „Erfahrungskonsens“, nicht streng bewiesen.

2. Mathematischer Existenzbeweis: Strategie-Diebstahl (Strategy-Stealing)

Mathematiker können mit einem logischen Argument namens „Strategie-Diebstahl“ beweisen, dass verbotsfreies Gomoku vom Startspieler gewonnen wird.
Die Logik ist einfach: Angenommen, der zweite Spieler (Weiß) hätte eine Gewinnstrategie. Dann setzt Schwarz einen beliebigen ersten Stein und tut so, als wäre er Weiß (betrachtet den ersten Stein als nicht vorhanden oder als zusätzlichen Zug) und wendet die Gewinnstrategie von Weiß an. Da im Gomoku ein eigener Stein auf dem Brett immer nur von Vorteil ist, würde Schwarz gewinnen. Dies widerspricht der Annahme, dass Weiß gewinnt.
Daher ist verbotsfreies Gomoku entweder ein Unentschieden oder ein Startspielersieg. Da ein Unentschieden auf dem Gomoku-Brett extrem unwahrscheinlich ist, folgt der Startspielersieg. Dies ist jedoch nur eine theoretische Aussage ohne konkrete Züge.

3. Vollständige Computerlösung (1992, L. Victor Allis)

Der wahre „Bezwinger“ der Gomoku-Gewinnstrategie war der niederländische Informatiker L. Victor Allis.

1992 schrieb er im Rahmen seiner Doktorarbeit ein Computerprogramm namens Victoria.

• Seine Methode: Der Spielbaum von Gomoku ist enorm; eine traditionelle Brute-Force-Suche (wie bei Tic-Tac-Toe) war damals unmöglich. Allis kombinierte geschickt menschliches Gomoku-Wissen (die oben genannten VCF-, VCT- und Algorithmen zur Erkennung doppelter Bedrohungen) mit einem neuartigen Algorithmus namens „Proof-number search“.
• Sein Ergebnis: Das Programm durchsuchte und berechnete erfolgreich alle kritischen Verzweigungen des verbotsfreien Gomoku auf einem 15×15-Brett und bewies zum ersten Mal in der Geschichte nicht nur, dass Schwarz gewinnt, sondern berechnete auch konkrete Gewinnpfade. Er zeigte auch, dass selbst unter bestimmten Eröffnungsbeschränkungen bestimmte Eröffnungen für Schwarz gewinnend sind.

Zusammenfassung:
Der Startspielersieg bei Gomoku war ein jahrhundertealter Erfahrungskonsens unter menschlichen Spielern, der schließlich 1992 von einem Informatiker durch einen speziell entwickelten Algorithmus vollständig gelöst wurde. Verbotsfreies Gomoku wird daher in der Informatik als „schwach gelöstes Spiel“ (Weakly Solved Game) bezeichnet – solange Schwarz keinen Fehler macht, gibt es einen garantierten Gewinnpfad, unabhängig von Weiß' Verteidigung.

Bevor wir weitere gelöste Spiele vorstellen, klären wir zunächst die drei Stufen der „Lösung“ in der Informatik, um das Verständnis zu erleichtern:

1. Ultra-schwach gelöst (Ultra-weakly solved): Es ist mathematisch bewiesen, wer gewinnt (oder ob es ein Unentschieden gibt), aber die konkreten Züge sind unbekannt (z.B. das „Strategie-Diebstahl“-Argument aus der vorherigen Antwort).
2. Schwach gelöst (Weakly solved): Der Computer hat einen konkreten Gewinn- (oder Remis-) Pfad vom Startzustand aus gefunden. Wenn man diesen Pfad befolgt, verliert man nicht; aber bei einer beliebigen anderen Stellung kennt der Computer möglicherweise nicht die optimale Lösung.
3. Stark gelöst (Strongly solved): Der Computer kennt die absolut optimale Lösung für jede legale Stellung (z.B. Tic-Tac-Toe).

Hier sind einige bekannte schwach (bis stark) gelöste Spiele sowie Spiele, die bis heute ungelöst sind.

---

I. Bekannte „gelöste“ Spiele

Neben verbotsfreiem Gomoku gibt es weitere bekannte Brettspiele, die von Computern vollständig durchschaut wurden:

1. Vier gewinnt (Connect Four)

• Ergebnis: Startspieler gewinnt (schwach gelöst).
• Lösungsprozess: Derselbe Informatiker, der Gomoku löste, L. Victor Allis, löste 1988 (fast gleichzeitig und unabhängig von James Dow Allen) Vier gewinnt. Wenn der Startspieler den ersten Stein in die mittlere Spalte setzt und perfekt spielt, gewinnt er. Setzt er in die benachbarten Spalten, ist es ein Unentschieden; setzt er am Rand, gewinnt der zweite Spieler.

2. Damespiel (Checkers / Draughts)

• Ergebnis: Bei perfektem Spiel Unentschieden (schwach gelöst).
• Lösungsprozess: Dies war ein bedeutender Meilenstein. Professor Jonathan Schaeffer von der University of Alberta leitete ein Team, das das Programm Chinook entwickelte. Sie rechneten 18 Jahre lang (von 1989 bis 2007) und durchsuchten $5 \times 10^{20}$ (500 Trillionen) Endspielstellungen. 2007 verkündeten sie in der Zeitschrift Science: Damespiel ist vollständig gelöst. Wenn beide Seiten keine Fehler machen, endet das Spiel unentschieden.

3. Mühle (Nine Men's Morris)

• Ergebnis: Bei perfektem Spiel Unentschieden (stark gelöst).
• Lösungsprozess: Dieses alte Spiel (das in vielen westlichen klassischen Filmen vorkommt) wurde 1993 von Ralph Gasser stark gelöst. Er bewies, dass sowohl in der Eröffnung als auch in jeder Mittelspielstellung bei fehlerfreiem Spiel ein Unentschieden folgt.

4. Othello / Reversi – Neuester Durchbruch!

• Ergebnis: Bei perfektem Spiel Unentschieden (schwach gelöst).
• Lösungsprozess: Dies ist ein sehr aktueller Durchbruch! Im Oktober 2023 gab der japanische Forscher Hiroki Takizawa bekannt, dass er mit modernen Supercomputern und optimierten Algorithmen nach mehrtägigen Berechnungen das 8×8-Standard-Othello schwach gelöst hat. Das Ergebnis: Bei perfektem Spiel beider Seiten endet das Spiel mit einem direkten Unentschieden.

---

II. Bis heute „ungelöste“ Spiele

Du fragst dich vielleicht: Wenn KI so stark ist (wie AlphaGo), sind dann nicht alle Brettspiele gelöst?
Die Antwort ist: Nein.

„KI schlägt Menschen“ und „ein Spiel mathematisch lösen“ sind völlig verschiedene Konzepte. KI schlägt Menschen, weil sie durch Wahrscheinlichkeitsrechnung Züge mit einer Gewinnwahrscheinlichkeit von 99% finden kann; „Lösung“ erfordert jedoch eine 100%ige vollständige Durchsuchung und einen zweifelsfreien Beweis.

Da die „Zustandsraumkomplexität“ (Anzahl möglicher Brettstellungen) und die „Spielbaumkomplexität“ (Anzahl aller möglichen Zugfolgen) der folgenden Spiele enorm sind, übersteigen sie die Rechenleistung aller existierenden und in den nächsten Jahrhunderten zu erwartenden Supercomputer.

1. Schach (Chess)

• Warum ungelöst: Die Anzahl legaler Stellungen im Schach beträgt etwa $10^{43}$, die Anzahl möglicher Partien sogar $10^{120}$ (diese Zahl wird als „Shannon-Zahl“ bezeichnet). Die Anzahl der Atome im beobachtbaren Universum liegt bei etwa $10^{80}$. Selbst wenn man alle Atome des Universums zu Computern machen würde, könnte man nicht alle Schachvarianten berechnen.
• Status: Obwohl Deep Blue und heutige Engines wie Stockfish alle menschlichen Meister überragen, ist Schach mathematisch immer noch ungelöst. Wir wissen nicht, ob eine perfekte Schachpartie mit einem Sieg von Weiß (Startspieler) oder einem Unentschieden endet (die meisten Experten neigen zu Unentschieden).

2. Chinesisches Schach (Xiangqi)

• Warum ungelöst: Das chinesische Schachbrett ist größer und bietet mehr Bewegungsraum; seine Zustandsraumkomplexität beträgt etwa $10^{48}$, noch einige Größenordnungen mehr als Schach.
• Status: Ähnlich wie beim Schach: Die besten Xiangqi-Programme (wie Wangzhongwang, Pikayu) lassen Menschen keine Chance, aber im streng mathematischen Sinne ist es ungelöst.

3. Go

• Warum ungelöst: Go ist der „Komplexitätskönig“ unter den Brettspielen. Auf dem standardmäßigen 19×19-Brett beträgt die Zustandsraumkomplexität erstaunliche $10^{170}$, die Spielbaumkomplexität sogar $10^{360}$. Im Vergleich zu Go ist die Komplexität von Schach vernachlässigbar.
• Status: Selbst der überragende AlphaGo und sein Nachfolger AlphaZero haben Go nicht „gelöst“. Sie nutzen neuronale Netze, um eine starke „intuitive Bewertung“ aufzubauen und wissen in den meisten Stellungen, wie man die höchste Gewinnwahrscheinlichkeit erzielt. Aber wenn man AlphaGo bitten würde zu beweisen, „ob Go vom Startspieler gewonnen wird oder ein Unentschieden ist“, könnte es das nicht.

Zusammenfassung

• Wenn die Komplexität eines Spiels unter $10^{20}$ (1000 Trillionen) liegt, wie bei Dame, Gomoku, Othello, können Menschen mit Supercomputern das Spiel vollständig „lösen“.
• Sobald die Komplexität $10^{40}$ übersteigt (also Schach, Xiangqi, Go), wird eine erschöpfende Lösung im physikalischen Rahmen unmöglich. Für diese Spiele können wir uns mit KI der „perfekten Wahrheit“ nur annähern, sie aber vielleicht nie vollständig erreichen.

Diese Frage ist sehr scharfsinnig! Deine Logik ist völlig richtig: Wenn man das Brett auf unendlich vergrößert, wird die Anzahl der Stellungen unendlich, und ein Computer kann unmöglich alle Züge „erschöpfend“ durchsuchen.

Aber: Verbotsfreies Gomoku auf einem unendlich großen Brett ist dennoch mathematisch und logisch „gelöst“ – das Ergebnis bleibt: Der Startspieler (Schwarz) gewinnt.

Wie kann es gelöst sein, wenn man nicht erschöpfend suchen kann? Hier kommt eine sehr einfache, aber auch sehr raffinierte „Dimensionsreduktions“-Logik zum Einsatz:

1. Die „Eingrenzungs“-Strategie (verschachtelter Beweis)

1992 hat der Computer bereits erschöpfend bewiesen: Auf einem 15×15-Brett hat Schwarz eine Gewinnlinie.

Wie gewinnt Schwarz nun auf einem unendlich großen Brett?
Ganz einfach: Schwarz zeichnet in Gedanken einen unsichtbaren 15×15-Rahmen in die Mitte des unendlichen Bretts und spielt exakt die bewiesene Gewinnstrategie aus dem 15×15-Brett nach.

Solange Weiß innerhalb dieses Rahmens spielt, antwortet Schwarz gemäß der bekannten Gewinnprogrammierung; wenn Weiß zehntausend Kilometer entfernt im unendlichen Raum spielt, ignoriert Schwarz ihn einfach und bildet innerhalb seines 15×15-Bereichs eine Fünferreihe. Da die Gewinnstrategie bei Gomoku auf „ununterbrochenem Druck“ (fortlaufende offene Vierer, lebende Dreier) basiert, hat Weiß keine freien Züge, um außerhalb zu stören – er muss im Hauptkampfgebiet verteidigen.

2. Je größer das Brett, desto vorteilhafter für den Startspieler

Im Gomoku ist der Brettrand eigentlich ein Helfer für den unterlegenen Spieler (Weiß) bei der Verteidigung.
Schwarz fürchtet beim Angriff am meisten, dass seine Steine „an die Wand stoßen“, bevor er fünf in eine Reihe bekommt.
Da Schwarz selbst auf einem beengten 15×15-Brett, wo er leicht an die Wand stößt, zu 100% gewinnen kann, hat er auf einem unendlich großen Brett keine Sorge mehr vor der Wand – der Sieg fällt nur noch leichter.

Zusammenfassung:
Gomoku auf unendlichem Brett wird nicht durch unendliche Rechenleistung gelöst, sondern durch menschliche mathematische Logik und Verschachtelung. Solange 15×15 gewinnbar ist, kann der Startspieler auf jedem größeren Brett (selbst unendlich) garantiert gewinnen.