Domineering – auch bekannt unter den Namen Stop-Gate oder Crosscram [1] – ist ein strategisches Zwei-Personen-Spiel aus dem Bereich der mathematischen Spiele, das zur Klasse der sogenannten Kombinatorischen Spiele gehört. Das Spiel wurde etwa 1973 von Göran Andersson erfunden und später durch einen Beitrag von Martin Gardner der Öffentlichkeit vorgestellt.[2]
Es kann auf jeder beliebigen Anordnung von Feldern gespielt werden. Typische Spielfelder sind quadratische oder rechteckige Gitter (z. B. ), aber auch unregelmäßige Formen wie Polyominos oder Kombinationen verschiedener Gebiete sind möglich. Die von Andersson und Gardner vorgestellte Standardversion basiert auf einem Spielfeld mit Feldern.[2:1]
Domineering kann man unter einer Webseite der Universität Passau online spielen, wobei verschiedene KI-Algorithmen zur Auswahl stehen, die unterschiedliche Spielstrategien verfolgen und Schwierigkeitsgrade bieten.
¶ Regeln
Domineering wird auf einem rechteckigen Gitter gespielt, meist einem -Raster. Zwei Spieler, traditionell Vertikal und Horizontal genannt, setzen abwechselnd Dominosteine auf dem Spielfeld:
- Vertikal darf nur vertikal ausgerichtete -Dominosteine setzen.
- Horizontal darf nur horizontal ausgerichtete -Dominosteine setzen.
- Jeder Dominostein muss zwei benachbarte, freie Felder vollständig bedecken.
- Steine dürfen sich nicht überlappen, und jedes Feld darf nur einmal belegt werden.
- Sobald ein Spieler keinen gültigen Zug mehr machen kann, hat er verloren.
¶ Spielstellung
In Domineering wird jeder gültige Zug einem Wert zugeordnet, der den Vorteil des jeweiligen Spielers ausdrückt. Dabei gilt folgende Konvention:
- Ein vertikal gelegter Dominostein entspricht einem positiven Wert von .
- Ein horizontal gelegter Dominostein entspricht einem negativen Wert von .
Im Verlauf Verlauf eines Domineering-Spiels entstehen durch die gesetzten Steine immer neue Spielstellungen, die sich oft in mehrere disjunkten Teilspiele zerlegen lassen. Diese disjunkten Teilspiele beeinflussen sich nicht gegenseitig und können daher einzeln untersucht werden, um die Situation der Spielstellung präzise zu verstehen und den Gesamtwert zu bestimmen.
Der Gesamtwert einer Domineering-Stellung ergibt sich als Summe der Werte aller unabhängigen Teilspiele:
Daraus lässt sich der Gewinner bestimmen:
- Falls , hat Vertikal einen Vorteil bzw. gewinnt, falls keine Züge mehr möglich sind.
- Falls , hat Horizontal einen Vorteil bzw. gewinnt, falls keine Züge mehr möglich sind.
- Falls , gewinnt der zweite Spieler, unabhängig davon, wer begonnen hat.
Letzteres ergibt sich aus der Tatsache, dass in ausgeglichenen Spielstellungen jeder Zug den Gegner in eine ungünstigere Lage bringt, sodass derjenige, der zuerst ziehen muss, langfristig im Nachteil ist.
¶ Notation
In der kombinatorischen Spieltheorie wird jeder Spielstellung ein numerischer Wert zugewiesen, der den Vorteil eines Spielers gegenüber dem anderen quantifiziert. Diese Werte stammen aus der Klasse der sogenannten surrealen Zahlen.
Die Notation hilft insbesondere bei der Bewertung von Spielstellungen in zusammengesetzten Spielen wie Domineering, bei denen sich das Spielfeld durch Züge in unabhängige Teilspiele aufspalten kann. Solche Teilspiele können dann separat analysiert und ihre Werte zum Gesamtwert addiert werden.[3]
¶ Grundform: {L | R}
Eine Spielstellung wird als Spielwert der Form {L | R} notiert:
L(Left): die Menge aller möglichen Nachfolgespiele, die Vertikal (bzw. „Left“) durch einen gültigen Zug erreichen kann.R(Right): die Menge aller möglichen Nachfolgespiele, die Horizontal (bzw. „Right“) durch einen gültigen Zug erreichen kann.
Hat ein Spieler keine Zugmöglichkeit, bleibt die entsprechende Seite in der surrealen Zahl leer, zum Beispiel
{0 | },{ | 0}oder{ | }.
Der Spielwert liegt - sofern definiert - zwischen den Werten aus L und R.
Außerdem lässt sich eine komplexe Spielstellung rekursiv analysieren, wenn durch einen Zug weitere disjunkte Teilspiele entstehen. Die Abbildung 4 veranschaulicht dieses Prinzip.
Die Spielstellung lässt sich in surrealer Notation wie folgt darstellen:
{{0 | }, {0 | 0} | {0 | }, 0}
{{0 | }, {0 | 0} | {0 | }, 0} = {1, 0* | 1, 0} = {1 | 0}
¶ Wertbestimmung
Ein surrealer Zahlenwert ist genau dann definiert, wenn jeder Wert in L strikt kleiner ist als jeder Wert in R (also L < R gilt).
In diesem Fall lässt sich der Wert im einfachsten Fall (wenn jeweils nur ein Element in L und R vorhanden ist) näherungsweise als Mittelwert der beiden Werte berechnen.[3:1]
In der Praxis geht man davon aus, dass beide Spieler optimal spielen und stets die für sie günstigste Fortsetzung wählen.
Daher berücksichtigt man bei der Wertbestimmung einer definierten surrealen Zahl nur die besten Spielzüge.[3:2]
Für L wird die größte Zahl gewählt, für R die kleinste Zahl. Die Formel zur Wertbestimmung lautet:
Beispiel: Für die Mengen L = {1, 0} und R = {0, -1}, also die Spielstellung {{-1, 0}|{2, 1}}, würde man die Werte {0 | 1} wählen,
und daraus ergibt sich der Wert als Mittelwert:
Der Wert einer surrealen Zahl hat in Domineering folgende Bedeutung für die Bewertung einer Spielstellung:
- Ein positiver Wert zeigt, dass Vertikal in der aktuellen Spielstellung im Vorteil ist.
- Ein negativer Wert zeigt, dass Horizontal in der aktuellen Spielstellung im Vorteil ist.
- Ein Wert von
0zeigt, dass keiner der Spieler in der aktuellen Spielstellung im Vorteil ist und sich die Spielsituation dadurch nicht verändert.
¶ Nicht numerische Werte
Wenn jedoch L ≥ R gilt, ist der Spielwert nicht definiert. Solche Werte nennt man „fuzzy“. Das bedeutet, dass der Vorteil eines Spielers davon abhängt, wer zuerst zieht – es existiert somit kein eindeutiger, fester Wert und kein klarer Vorteil für einen bestimmten Spieler. Man nennt sie auch „heiße Spiele“.[3:3]
In der kombinatorischen Spieltheorie verwendet man daher auch nicht-numerische Werte wie {+1 | -1}, um Spielstellungen zu beschreiben, bei denen beide Spieler lohnenswerte Züge haben.
Ein klassisches Beispiel für ein fuzzy Spiel ist {+1 | -1}.
- Zieht Vertikal (Left) zuerst, sichert er sich eine weitere Zugmöglichkeit, die ihm den Vorteil von
+1verschafft. - Zieht hingegen Horizontal (Right) zuerst, sichert er sich eine weitere Zugmöglichkeit und damit den Vorteil von
-1.
Ein besonderer Fall unter den fuzzy Spielen ist {0 | 0}.
Diese Spielstellung ist neutral, aber instabil:
- Beide Spieler haben gleichwertige Züge, die den Gegner jedoch nicht sofort benachteiligen.
- Trotzdem ist die Spielstellung nicht vollkommen ausgeglichen, da der Spieler, der zuerst zieht, sich einen leichten Vorteil sichern kann.
- ist also kein echter Gleichstand, sondern ein symmetrisches heißes Spiel – neutral instabil.
- Fuzzy-Spiele der Form
{+X | −X}werden häufig in der Kurzschreibweise±Xnotiert – so schreibt man zum Beispiel{+1 | −1}einfach als±1.- Neutrale fuzzy-Spiele der Form
{X | X}werden dagegen oft alsX*bezeichnet – beispielsweise wird{0 | 0}als0*notiert.
¶ Besondere Spielwerte
| Spielstellung | Notation | Bedeutung / Erklärung | ||||
|---|---|---|---|---|---|---|
{ | } = 0 |
Niemand kann ziehen → Gleichstand | |||||
{ | 0} = -1 |
Nur Horizontal kann ziehen → Vorteil für Horizontal (−1) |
|||||
{0 | } = +1 |
Nur Vertikal kann ziehen → Vorteil für Vertikal (+1) |
|||||
{0 | 1} = +1/2 |
Mittelwert ist +1/2 → Vorteil für Vertikal |
|||||
{+1 | −1} = ±1 |
Fuzzy-Spiel → Vorteil hängt vom nächsten Spieler ab (±1) |
|||||
{0 | 0} = 0* |
Neutrales Fuzzy-Spiel ohne Vorteil (0*) |
¶ Algorithmische Aspekte
In diesem Abschnitt betrachten wir grundlegende Konzepte und Methoden zur effizienten Analyse und Lösung komplexer Spielstellungen. Dabei stehen insbesondere algorithmische Strategien im Fokus, die es ermöglichen, optimale Spielzüge systematisch zu bestimmen.
¶ Temperatur
Die Temperatur einer Spiels beschreibt, wie dringend ein Spielerzug in einer bestimmten Spielstellung ist. Sie ist ein Maß für die Dringlichkeit bzw. den Wert des besten nächsten Zugs – also dafür, wie stark sich der Spielwert ändern kann, wenn ein Spieler zieht.
- Hohe Temperatur: Der nächste Zug hat großen Einfluss auf das Ergebnis – es ist besonders wichtig, wer zuerst zieht.
- Niedrige Temperatur: Ein Zug verändert den Spielwert kaum noch – die Spielstellung ist relativ stabil.
- Temperatur 0: In diesem Fall handelt es sich meist um ein Fuzzy-Spiel ohne stabilen Vorteil – also um eine neutral instabile Spielstellung. Es ist egal, wer zuerst zieht – der Vorteil liegt fest auf einer Seite oder das Spiel ist vollständig ausgeglichen.
Formell
Für ein Spiel der Form{L | R}wird die Temperatur wie folgt definiert:• Wenn , dann gilt:
• Wenn , dann gilt:
Strategie: Bei mehreren gleichzeitig laufenden Teilspielen (z. B. in Domineering) wählt man in jedem Zug am besten das Teilspiel mit der höchsten Temperatur, um den größten Einfluss auf das Gesamtergebnis zu erzielen.
- Eine Spielstellung mit Temperatur 5 bedeutet, dass der nächste Zug den Spielwert um bis zu 5 verändern kann – z. B. von (wenn Vertikal zuerst zieht) bis (wenn Horizontal zuerst zieht).
- Eine Spielstellung mit Temperatur 0 wie
{0 | 1}hat einen festen Vorteil von+1/2für Vertikal – unabhängig davon, wer den nächsten Zug macht.
¶ Höchste Temperatur
Die bislang höchste gefundene Temperatur im Spiel Domineering beträgt 2.[4]
Ein Beispiel dafür ist eine Spielstellung der Form {2* | −2*}, die folgendermaßen aussieht:
2* und 0.
¶ Weiterführende Literatur und Quellen
Für eine vertiefte Auseinandersetzung mit der Temperatur in combinatorialen Spielen und deren Bedeutung siehe u. a.:
- Berlekamp, E. R., Conway, J. H. & Guy, R. K. (1982). Winning Ways for your Mathematical Plays. Academic Press – Grundlagen zur Temperatur und allgemeinen Spieltheorie.
- Uiterwijk, J. W. H. M. (2024). High Temperature Domineering Positions – systematische Klassifikation und Konstruktion hochtemperierter Positionen in Domineering.
¶ Perfektes Lösen
Das perfekte Lösen eines Spiels bezeichnet den Zustand, in dem für jede mögliche Spielsituation das Ergebnis eindeutig bestimmt ist. Das heißt, man weiß für alle denkbaren Stellungen, ob der Spieler, der am Zug ist, mit optimalem Spiel gewinnen, verlieren oder zumindest ein Unentschieden erreichen kann. Darüber hinaus beinhaltet perfektes Lösen auch die Existenz einer optimalen Strategie, die es erlaubt, das Spiel von jedem dieser Zustände aus ideal zu spielen.
Im Falle von Domineering bedeutet das, dass für jeden möglichen Brettzustand – egal, wie das Spielfeld gerade aussieht oder wie viele Züge bereits gemacht wurden – bekannt ist, welcher Spieler einen Gewinn erzwingen kann und welche Züge genau dazu führen. Dadurch kann man nicht nur das Endergebnis vorhersagen, sondern auch einen Zugplan entwickeln, der garantiert zum Sieg führt, wenn ein Sieg möglich ist.
¶ Lösungsansätze
Die Arbeit von Uiterwijk[5] stellt drei algorithmische Strategien zum systematischen Lösen von Domineering-Stellungen vor. Sie unterscheiden sich vor allem im Grad der Wissensnutzung und Effizienz.
¶ 1. Domi – Brute-Force-Ansatz
- Klassische --Suche mit Transpositionstabellen.
- Keine Heuristiken oder spielspezifisches Wissen.
- Nutzt Spiegelsymmetrien zur Zustandsreduktion.
- Charakter: Robust, aber rechenintensiv und ineffizient bei großen Feldern.
¶ 2. Obsequi – Wissensgestützter Ansatz
- Integriert eine statische Bewertungsfunktion zur Früherkennung günstiger Positionen.
- Verbessert die Zugreihenfolge durch Dominanz- und Ordnungsregeln.
- Optimierte Transpositionstabellen (z. B. mit TwoBig oder FindFirst).
- Charakter: Deutlich leistungsfähiger durch gezielte Spielfeldanalyse.
¶ 3. MUDoS – Wissensintensiver Ansatz (Perfektes Lösen)
- Nutzt umfassende Heuristiken, Mustererkennung und Domineering-spezifische Regeln.
- Viele Stellungen werden ohne Tiefensuche direkt bewertet.
- Arbeitet mit großen, flachen Transpositionstabellen im Deep-Schema.
- Charakter: Extrem effizient – löst viele Partien praktisch „aus dem Gedächtnis“.
MUDoS erzielt seine hohe Effizienz durch die Anwendung von zwölf speziell entwickelten Regeln, die auf strukturellen, symmetrischen und dominanzbasierten Eigenschaften des Spiels beruhen. Diese Regeln erlauben es, viele Stellungen direkt zu klassifizieren, ohne eine tiefgreifende Suche durchführen zu müssen. Dabei erkennt MUDoS etwa wiederkehrende Muster, symmetrische Stellungen, dominierende Teilbereiche oder isolierte Spielflächen, deren Ergebnis bereits bekannt ist.
Durch dieses tief eingebettete Spielverständnis gelingt es dem Programm, große Teile des Suchraums gezielt auszuschließen – oft reicht schon ein kurzer Blick auf die Stellung, um ihren Ausgang korrekt vorherzusagen.
¶ Ergebnisse (Stand: 2016)
Die Programme wurden auf quadratischen Brettern bis 11×11 getestet. Die Ergebnisse zeigen, wer unter optimalem Spiel gewinnt:
Die Anzahl der untersuchten Knoten gibt an, wie viele Spielstellungen im Suchbaum analysiert wurden – ein Maß für den Rechenaufwand und die Effizienz. Es wurden quadratische Domineering-Bretter mit Vertikal als Startspieler betrachtet. In der Ergebnisspalte steht „1“ für einen Sieg des ersten Spielers (Vertikal), „2“ für den zweiten Spieler (Horizontal). Ein „–“ zeigt an, dass das Programm die Stellung nicht lösen konnte.
| Brettgröße | Gewinner | Domi (Knoten) | Obsequi (Knoten) | MUDoS (Knoten) |
|---|---|---|---|---|
| Spieler | ||||
| Spieler | ||||
| Spieler | ||||
| Spieler | ||||
| Spieler | ||||
| Spieler | ||||
| Spieler | ||||
| Spieler | ||||
| Spieler | – | |||
| Spieler | – | – |
Das größte bisher gelöste Brett (11×11) wurde mit MUDoS innerhalb von 174 Tagen auf einem handelsüblichen Desktop-Rechner gelöst. Dabei wurden 259.689.994.008 Knoten mit einer durchschnittlichen Geschwindigkeit von etwa 17.211 Knoten pro Sekunde untersucht. Obwohl MUDoS damit langsamer als Obsequi ist, macht die deutlich bessere Knotenreduktion das mehr als wett.
MUDoS untersucht im Vergleich zu Obsequi nur einen Bruchteil der Knoten:
- : 1,19 %
- : 0,30 %
- : 0,00038 %
Das besonders geringe Verhältnis für das -Brett erklärt sich dadurch, dass Obsequi das Problem auf einem verteilten Netzwerk ohne gemeinsamen Speicher löste, was Transpositionstabellen erschwert. Während Obsequi mehrere Monate benötigte, löste MUDoS das -Brett in nur 21 Minuten auf einem einzigen Computer.
¶ Tabellarische Ergebnisse
Die folgende Tabelle bietet einen vollständigen und aktuellen Überblick über alle bisher gelösten Domineering-Bretter sowie deren Klassifikation nach Ausgangsstellung.
Legende zur Ergebnis-Tabelle
Die Tabelle klassifiziert jede Brettgröße nach dem Spieler, der unter perfektem Spiel gewinnen kann, oder ob es sich um eine P-Position handelt (eine Verliererstellung – unabhängig vom Spieler). Die Einträge geben den strategischen Ausgang der jeweiligen Startstellung an:
Symbol Bedeutung V Vertikal gewinnt bei perfektem Spiel H Horizontal gewinnt bei perfektem Spiel P P-Position: der Spieler am Zug kann nicht gewinnen (Verliererstellung) NH Unklar, ob es sich um P oder H handelt NV Unklar, ob es sich um P oder V handelt –V Sicher nicht Vertikal gewinnt (also H oder P) –H Sicher nicht Horizontal gewinnt (also V oder P) leer Keine Daten / Position noch nicht vollständig analysiert Zusätzliche Muster (1–6):
1) Für alle : Ergebnis ist H, außer bei (H oder P)
2) Für alle geraden : Gewinner ist H
3) Typisches Muster: H bei geraden, H oder P bei ungeraden n
4)–6) Entsprechende Regeln gelten für die Zeilenanzahl m, mit vertauschten Rollen (H V)
¶ Theoretische Erkenntnisse
Anhand der erzielten Ergebnisse formulierte Uiterwijk vier zentrale Theoreme[2:2], die das Verhalten von Domineering-Positionen systematisch beschreiben. Die Theoreme legen fest, für welche Brettgrößen ein Spieler unter perfektem Spiel sicher gewinnt, unabhängig vom Gegner:
-
Theorem 1: Alle -Bretter mit sind ein Gewinn für den Vertikal.
-
Theorem 2: Alle -Bretter mit sind ein Gewinn für den Vertikal.
-
Theorem 3: Alle -Bretter mit sind ein Gewinn für den Horizontal.
-
Theorem 4: Alle -Bretter für sowie alle -Bretter für sind ein Gewinn für den Horizontal.
Diese Theoreme helfen, gewonnene Einsichten auf andere Brettgrößen zu übertragen, und erklären die Muster, die in Abbildung 6 sichtbar werden.
¶ Ausblick
Domineering bleibt trotz seiner einfachen Spielregeln ein faszinierendes und tiefgründiges Studienobjekt der kombinatorischen Spieltheorie. Während kleinere Spielfelder bereits vollständig analysiert wurden, wachsen Komplexität und Rechenaufwand bei größeren Feldern exponentiell. Aktuelle Forschungen beschäftigen sich mit effizienteren Lösungsalgorithmen, der Klassifikation von Temperaturwerten sowie der systematischen Zerlegung in elementare Spielkomponenten.
Ein besonders spannender Aspekt ist die Analyse sogenannter heißer und kalter Positionen, sowie die Frage, welche Felderstrukturen universell vorteilhaft für einen Spieler sind. Darüber hinaus bietet Domineering eine wertvolle Testumgebung für AI-gestützte Suchverfahren und heuristische Spielbewertung.
¶ Glossar
- Fuzzy-Wert: Ein Spielwert ohne eindeutigen Sieger – der Ausgang hängt davon ab, wer beginnt.
- Surreale Zahl: Erweiterung der reellen Zahlen, geeignet zur Bewertung von Spielstellungen in kombinatorischen Spielen.
- Dominostein: Ein 1×2- oder 2×1-Spielstein, der zwei benachbarte Felder abdeckt.
- Temperatur: Maß für die Dringlichkeit eines Zuges in einer Spielstellung; gibt an, wie stark der Spielwert durch den nächsten Zug verändert werden kann.
- Transpositionstabelle: Datenstruktur zur Speicherung bereits berechneter Spielpositionen, um Wiederholungen bei der Suche zu vermeiden.
- Alpha-Beta-Suche: Algorithmus zur effizienten Durchmusterung von Spielbäumen durch Abschneiden von Zweigen, die keine besseren Ergebnisse liefern können.
- Brute-Force-Ansatz: Methode, bei der alle möglichen Züge und Spielverläufe vollständig durchsucht werden, ohne Heuristiken oder spezielles Wissen.
- P-Position: Position, bei der der Spieler, der am Zug ist, nicht gewinnen kann (Verliererstellung).
- Heuristik: Vorgehensweise oder Regel, die hilft, gute Entscheidungen zu treffen oder Suche zu vereinfachen, ohne alle Möglichkeiten zu prüfen.
¶ Bildquellen
-
Abb. 1: Visualisierung eines Spielverlaufs von Domineering auf einem 4×4-Feld.
Quelle: Byrdseed. Domineering.
Visualisierung bei byrdseed -
Abb. 2: Darstellung der Zerlegung eines Domineering-Spiels in unabhängige Teilspiele.
Quelle: Huntemann, S. & McKay, N. A. (2019). Counting Domineering Positions.
School of Mathematics and Statistics, Carleton University & University of New Brunswick.
PDF bei arXiv -
Abb. 3, 5: Spielwerte im Domineering für alle Regionen mit sechs Feldern.
Quelle: Berlekamp, E. R., Conway, J. H., & Guy, R. K. (2001). Winning Ways for Your Mathematical Plays, Vol. 1, Aufl. 2, S. 119–143
Academic Press.
PDF bei ludost.net -
Abb. 4: Beispielhafte Darstellung möglicher Spielzüge in surrealer Notation.
Quelle: Mathstrek Blog (2012). Domineering options illustration.
Abbildung bei mathstrek.blog -
Abb. 6: Domineering-Stellung mit Temperatur 2, Zerlegung in zwei Komponenten.
Quelle: Drummond-Cole, G. (2017). Temperature Two in Domineering.
PDF bei drummondcole.com -
Abb. 7: Übersicht der Ergebnis-Klassen für Domineering-Bretter verschiedener Größen.
Quelle: Uiterwijk, J. W. H. M. (2016). 11×11 Domineering is Solved: The First Player Wins.
Department of Data Science and Knowledge Engineering, Maastricht University, Niederlande.
PDF bei arXiv
¶ Referenzen
- Wikipedia: Combinatorial Game Theory.
https://en.wikipedia.org/wiki/Combinatorial_game_theory
Wikipedia: Domineering. Überblick über Spielregeln, Varianten und Analyse.
https://en.wikipedia.org/wiki/Domineering ↩︎Uiterwijk, J. W. H. M. (2014). Perfectly Solving Domineering Games.
Department of Data Science and Knowledge Engineering, Maastricht University.
In: Cazenave, T., Winands, M. H. M., Iida, H. (Hrsg.),
Computer Games – Workshop on Computer Games (CGW) at IJCAI 2013, Beijing, China, Revised Selected Papers.
Communications in Computer and Information Science, Vol. 408, Springer, S. 97–121.
Springer-Link | PDF bei ResearchGate ↩︎ ↩︎ ↩︎Berlekamp, E. R., Conway, J. H., & Guy, R. K. (2001). Winning Ways for Your Mathematical Plays, Vol. 1, Aufl. 2, S. 119–143
Academic Press.
TU Berlin | PDF bei Ludost.net ↩︎ ↩︎ ↩︎ ↩︎Huntemann, S., & Maciosowski, T. (2024). High Temperature Domineering Positions.
Mount Saint Vincent University & Concordia University of Edmonton.
arXiv:2408.16095 | PDF bei arXiv ↩︎Uiterwijk, J. W. H. M. (2016). 11×11 Domineering is Solved: The first player wins.
Department of Data Science and Knowledge Engineering, Maastricht University.
arXiv:1602.05404 | PDF bei arXiv ↩︎