Sortiert nach mathematischem Teilgebiet. = in dieser Sammlung spielbar. Die Formeln sagen jeweils knapp, worum es im Kern geht.
Kombinatorische Spiele · perfekte Information (Minimax)
- Dame / Checkers spielen — Zwei-Personen-Nullsummenspiel mit perfekter Information.
Spielwert über Minimax v = maxₐ minᵦ …; 8×8-Dame ist gelöst: Remis bei perfektem Spiel (Schaeffer 2007).
- Vier gewinnt (Connect Four) — Stellungsspiel auf 7×6.
Vollständig gelöst (Allis 1988): Anziehender erzwingt Sieg; Zustandsraum ≈ 4,5·10¹².
- Hex — Verbindungsspiel auf rautenförmigem Brett.
Determiniert (kein Remis möglich, Sperner/Brouwer-artig); Strategie-Klau-Argument ⇒ Anziehender gewinnt (nicht-konstruktiv); allgemein PSPACE-vollständig.
- Schach · Go — die „großen" Suchspiele.
Verallgemeinert n×n: Schach EXPTIME-vollständig, Go PSPACE-/EXPTIME-hart; praktisch Minimax+Heuristik bzw. Monte-Carlo-Tree-Search + neuronale Netze.
Kombinatorische Spieltheorie · unparteiische Spiele (Sprague–Grundy)
- Nim spielen — der Prototyp aller unparteiischen Spiele.
Grundy-Wert G = a₁ ⊕ a₂ ⊕ … ⊕ aₙ (XOR); Verluststellung ⇔ Nim-Summe = 0 (Satz von Bouton). Jedes unparteiische Spiel ist nach Sprague–Grundy zu einem Nim-Haufen äquivalent.
- Wythoff-Nim — Nim mit zwei Haufen + Diagonalzug.
P-Stellungen = (⌊φn⌋, ⌊φ²n⌋) mit φ = (1+√5)/2 — Beatty-Folgen des goldenen Schnitts.
- Käsekästchen (Dots and Boxes) — Linien ziehen, Kästchen schließen.
Endspiel über Nimber-Theorie; „Long-Chain-Rule": Gewinner steuert die Parität #lange Ketten ≡ Startpunkte (mod 2).
- Sprouts — topologisches Punkte-Verbinden.
Euler-Formel beschränkt die Zugzahl: bei n Startpunkten zwischen 2n und 3n−1 Zügen; Gewinnanalyse via Nimber + Computer.
Stochastische Entscheidungen · optimales Stoppen (MDP)
- Farkle spielen — Press-your-luck-Würfeln.
Markov-Entscheidungsproblem; Bellman-Gleichung V(s) = max( sichern(s), 𝔼[V(s′)] ). Optimale Politik maximiert den erwarteten Rundenwert.
- Pig spielen — das minimale Press-your-luck (1 Würfel).
Erwartungswert pro Wurf = (20 − k)/6 → Faustregel „halte bei 20". Exakt optimale Politik per Wertiteration (Neller & Presser 2004) weicht im Endspiel ab.
- Yahtzee / Kniffel — Kombinationen über feste Runden.
Endlicher MDP; die optimale Strategie liefert 𝔼[Punkte] ≈ 254,59.
- 2048 — Kacheln schieben gegen Zufall.
Stochastisches Ein-Personen-Spiel; Expectimax (Erwartungswert über zufällig erscheinende Kacheln).
- Backgammon — Würfel + Strategie + Verdopplungswürfel.
Stochastisches Nullsummenspiel; Equity = 𝔼[Ergebnis]. Cube-Theorie: Take-Point ≈ 25 % Equity (toter Würfel). TD-Gammon lernte es per Reinforcement Learning.
Markov-Ketten · reiner Zufall ohne Entscheidungen
- Monopoly — Brett als Zustandsraum.
Markov-Kette über die 40 Felder; stationäre Verteilung π = πP nennt die häufigsten Felder (Gefängnis verzerrt alles) → ROI-Analyse der Straßen.
- Leiterspiel (Snakes & Ladders) — reine Glücksbewegung.
Absorbierende Markov-Kette; erwartete Spieldauer = (Fundamentalmatrix N = (I−Q)⁻¹) · 1, ausgewertet im Startzustand.
- Risk-Würfelduell — Angreifer vs. Verteidiger.
Gewinnwahrscheinlichkeiten über die Ordnungsstatistik der gewürfelten Augen (höchste gegen höchste).
Unvollständige Information · Bayes & Gleichgewichte
- Cabo spielen — Karten-Gedächtnisspiel, niedrige Summe gewinnt.
Spiel mit unvollständiger Information; minimiere 𝔼[Handsumme]. Entscheidung über Vergleich mit dem Deck-Mittel (≈ 6,2) + Bayes’sches Gedächtnis; „Cabo"-Ruf = optimales Stoppen unter Strafe.
- Poker (Heads-up) — Bluffen mit verdeckten Karten.
Extensives Spiel mit imperfekter Information; Lösung = Nash-Gleichgewicht (GTO), das die Ausbeutbarkeit minimiert. Optimale Bluff-Frequenz macht den Gegner indifferent.
- Schere–Stein–Papier — das Lehrbuch-Nullsummenspiel.
Eindeutiges Nash-Gleichgewicht = gleichverteilte gemischte Strategie (⅓, ⅓, ⅓), Spielwert 0.
- Liar’s Dice / Perudo — Würfel verdeckt, Gebote bluffen.
Bayes’sche Aktualisierung der verborgenen Würfelverteilung + gemischte Bluff-Strategien.
- Schiffe versenken — sequentielle Suche.
Optimale Schussfolge über eine A-posteriori-Wahrscheinlichkeitskarte (Dichte aller noch passenden Schiffslagen) + Paritäts-Trick.
Information & Inferenz · Entropie und Suche
- Mastermind — Farbcode erraten.
Knuths Minimax-Algorithmus löst 4×6 in ≤ 5 Zügen; jeder Tipp minimiert die größte verbleibende Kandidatenmenge (Worst-Case-Informationsgewinn).
- Wordle — Wort in 6 Versuchen.
Greedy maximiert den erwarteten Informationsgewinn H = −Σ pᵢ·log₂ pᵢ (Bits pro Tipp).
- Minesweeper — Minen aus Zahlen ableiten.
Constraint-Satisfaction; das allgemeine Konsistenzproblem ist NP-vollständig. Lokale Minenwahrscheinlichkeiten via Abzählung der Modelle.
Kombinatorik & endliche Geometrie
- Set — Kartenspiel mit 4 Merkmalen à 3 Werten.
Karten = Punkte im affinen Raum AG(4, 𝔽₃); ein „Set" = eine Gerade (a + b + c ≡ 0 mod 3). Größte set-freie Menge = Cap-Set-Problem (Durchbruch 2016: Croot–Lev–Pach / Ellenberg–Gijswijt).
- Dobble / Spot It — zwei Karten teilen genau ein Symbol.
Endliche projektive Ebene der Ordnung 7: bis zu 7²+7+1 = 57 Karten, je zwei schneiden sich in genau einem Symbol.
- Sudoku — Lateinisches Quadrat mit Blockbedingung.
Constraint-Satisfaction; verallgemeinert NP-vollständig. Minimale Anzahl eindeutiger Hinweise = 17 (bewiesen 2012, McGuire et al.).
Der rote Faden all dieser Spiele ist dieselbe Frage in verschiedenen Gewändern: Was ist der optimale Zug – und wie rechnet man ihn exakt aus? Genau das machen Farkle, Dame und Nim in dieser Sammlung sichtbar.