Was ist ein Spiel aus Sicht der Mathematik?

Spieltheorie, Teil 1 von 9

Während des Zweiten Weltkriegs sagte der Mathematiker John von Neumann in einem Londoner Taxi zu seinem Begleiter Jacob Bronowski etwas Merkwürdiges: Schach sei kein Spiel. Schach sei eine klar definierte Form des Rechnens – in jeder Stellung gebe es theoretisch einen richtigen Zug, auch wenn niemand ihn finden könne. Echte Spiele dagegen, wie das echte Leben, bestünden aus Bluff, kleinen Täuschungsmanövern und der Frage: „Was glaubt der andere, dass ich vorhabe?“ So erinnerte sich Bronowski an das Gespräch in Der Aufstieg des Menschen (1973) – eine Erinnerung, keine Mitschrift.

Wer Schach liebt, mag das fast als Provokation empfinden. Doch genau mit solchen Unterscheidungen beginnt die Spieltheorie. Von Neumann bewies 1928 ihren ersten zentralen Satz und machte sie gemeinsam mit dem Ökonomen Oskar Morgenstern in Spieltheorie und wirtschaftliches Verhalten (1944) zu einer eigenen Disziplin. In dieser Reihe führt unser Weg vom Schachbrett bis zu Verhandlungen und Vertrauen. Wir beginnen mit einer einfachen Frage: Was nennt eine Mathematikerin oder ein Mathematiker eigentlich ein Spiel?

Die drei Zutaten jedes Spiels

Für die Mathematik ist ein Spiel jede Situation, in der das Ergebnis von den Entscheidungen mehrerer Beteiligter abhängt – und alle wissen das. Darunter fallen Schach, aber auch eine Auktion, das Feilschen um den Preis einer Wohnung oder sogar die Frage, ob man ein Auto an der Kreuzung vorlässt.

Um ein Spiel zu beschreiben, braucht man drei Dinge:

• Spieler – wer Entscheidungen trifft: ein Mensch, ein Unternehmen, ein Staat, ein Programm.
• Strategien – alle Handlungsmöglichkeiten, die jedem Spieler offenstehen.
• Auszahlungen – was jeder für jede Kombination von Entscheidungen bekommt: Punkte, Geld, Sieg oder Niederlage.

Das einfachste Beispiel ist Schere, Stein, Papier. Zwei Spieler, je drei Optionen, und das ganze Spiel passt in eine Tabelle. Jedes Feld zeigt die Auszahlung für Spieler A: 1 steht für Sieg, −1 für Niederlage, 0 für Unentschieden.

Die Auszahlung für Spieler B ist immer dieselbe Zahl mit umgekehrtem Vorzeichen. Solche Spiele heißen Nullsummenspiele: Was der eine gewinnt, verliert der andere. Auch Schach, Dame und Go gehören dazu. Die meisten Situationen im Leben dagegen nicht – und um sie geht es in den späteren Teilen dieser Reihe.

Eine Strategie ist kein Zug

Im Alltag ist eine „Strategie“ eine grobe Idee: „Ich spiele defensiv.“ In der Spieltheorie ist sie eine vollständige Anleitung: was in jeder Situation zu tun ist, die auftreten kann – auch in denen, von denen man sicher ist, dass sie nie eintreten.

Nehmen wir ein Spiel, das man sofort mit jedem spielen kann (ein Lehrbeispiel). Auf dem Tisch liegen zehn Streichhölzer. Abwechselnd nimmt jeder ein oder zwei weg. Wer das letzte nimmt, gewinnt. Mathematiker nennen es ein Subtraktionsspiel, einen nahen Verwandten des klassischen Nim; dessen Name wird oft vom deutschen „nimm!“ abgeleitet.

Versuchen wir, es vom Ende her zu lösen:

1. Liegen vor Ihnen ein oder zwei Hölzer, nehmen Sie alle und gewinnen.
2. Liegen drei vor Ihnen, haben Sie verloren: Was Sie auch nehmen, der Gegner nimmt den Rest.
3. Bei vier oder fünf lassen Sie dem Gegner drei übrig und gewinnen.
4. Bei sechs sitzen Sie wieder in der Falle: Jeder Zug lässt dem Gegner vier oder fünf.

Das Muster ist erkennbar: Die Verluststellungen sind die Vielfachen von 3. Bei zehn Hölzern nimmt der erste Spieler also eines und lässt neun liegen. Danach ergänzt er den Zug des Gegners immer auf drei: Nimmt der andere eines, nimmt er zwei; nimmt der andere zwei, nimmt er eines. Der Sieg ist sicher, was der zweite Spieler auch tut.

Das ist eine Strategie im mathematischen Sinn: eine Regel, die für jede Stellung eine Antwort gibt. Und die Methode, mit der wir sie gefunden haben – vom Ende zum Anfang zu denken –, heißt Rückwärtsinduktion.

Genau diese Idee steckt hinter von Neumanns Bemerkung über Schach. Schach hat unvergleichlich mehr Stellungen, doch das Prinzip ist dasselbe: Irgendwo gibt es für jede von ihnen die richtige Antwort. Was daraus folgt – und was nicht –, ist Thema des nächsten Artikels.

Fünf Fragen, mit denen sich jedes Spiel einordnen lässt

Schach und Poker sind beide „Spiele“, doch mathematisch leben sie in verschiedenen Welten. Um zu sehen, wo die Grenze verläuft, genügt es, einem Spiel fünf Fragen zu stellen:

1. Wie viele Spieler? Ab drei entstehen Bündnisse, und die Analyse wird deutlich schwieriger.
2. Sind die Interessen entgegengesetzt? Nullsumme – oder kann man gemeinsam gewinnen oder gemeinsam verlieren?
3. Ist alles sichtbar? In einem Spiel mit vollkommener Information weiß, wer am Zug ist, alles, was bisher geschehen ist. Verdeckte Karten in der Hand des Gegners heben diese Bedingung auf.
4. Gibt es Zufall? Würfel, ein gemischtes Kartenspiel.
5. Abwechselnd oder gleichzeitig? Eine gleichzeitige Wahl wie bei Schere, Stein, Papier ist mathematisch dasselbe, als sähe man den Zug des Gegners nicht.

So lassen sich bekannte Spiele einordnen:

Achten Sie auf Backgammon. Hier gibt es Zufall, aber keine verborgene Information: Die Würfel fallen vor aller Augen. „Zufall“ und „Ungewissheit“ sind also nicht dasselbe. Beim Backgammon kennen Sie die Zukunft nicht. Beim Poker kennen Sie die Gegenwart nicht – das, was der Gegner schon in der Hand hält. Dieser Unterschied verändert alles.

Eine Anmerkung für Neugierige: Die Spieltheorie unterscheidet vollkommene Information (alle bisherigen Züge kennen) von vollständiger Information (die Regeln und Ziele aller Spieler kennen). Poker bietet die zweite – alle wissen, dass die anderen Chips gewinnen wollen –, aber nicht die erste.

Warum Bluffen beim Poker Mathematik ist und keine Charakterfrage

Im Schach ist nichts verborgen: Was der Gegner weiß, wissen Sie auch. Deshalb hängt der beste Zug nicht davon ab, ob der Gegner ihn erwartet. Theoretisch könnten Sie Ihren Plan laut ankündigen, und die Bewertung der Stellung bliebe dieselbe.

Beim Poker funktioniert das nicht. Wer immer mit starken Karten setzt und nie mit schwachen, macht seinen Einsatz zu einer aufgedeckten Karte. Ein aufmerksamer Gegner steigt einfach jedes Mal aus, wenn Sie setzen – und Ihre guten Hände bringen Ihnen nichts ein.

Schon von Neumann und Morgenstern fanden 1944 das Bluffen in einem vereinfachten Poker. 1950 schlug der Mathematiker Harold Kuhn ein noch kleineres Modell vor, das zum Lehrbuchbeispiel wurde. Sein „vereinfachtes Poker“ kommt mit drei Karten aus: Bube, Dame und König. Jeder Spieler erhält eine, die dritte bleibt verdeckt, und es ist nur ein einziger Einsatz erlaubt. Selbst in diesem Spielzeugspiel liefert die Rechnung ein Ergebnis, das Einsteiger überrascht: Die optimale Strategie muss Bluffs enthalten.

Ein Beispiel: Wenn der erste Spieler schiebt, soll der zweite mit der schwächsten Karte, dem Buben, genau in einem von drei Fällen setzen. Blufft er häufiger, wird sein Bluff gecallt; blufft er seltener, werden seine Einsätze zu ehrlich. Und wer in diesem Spiel zuerst handelt, verliert bei perfektem Spiel beider Seiten im Schnitt 1/18 Chip pro Hand: Der zweite Spieler handelt erst, nachdem er die Entscheidung des ersten gesehen hat.

Das ist der entscheidende Unterschied. In einem Spiel mit vollkommener Information ist die optimale Strategie ein bestimmter Zug in jeder Stellung. In einem Spiel mit verborgener Information ist sie oft ein Verhältnis: wie oft man das eine oder andere tut, damit der Gegner einen nicht „lesen“ kann. Mathematiker sprechen von einer gemischten Strategie – ihr ist ein eigener Artikel dieser Reihe gewidmet.

Das macht Schach nicht „einfacher“. Den richtigen Zug unter einer riesigen Zahl von Varianten zu finden, ist ebenso schwer, wie das richtige Bluff-Verhältnis zu halten. Es sind schlicht Schwierigkeiten unterschiedlicher Art.

Was das am Brett und darüber hinaus bedeutet

Diese Einteilung ist nicht nur akademisch. Sie hilft zu verstehen, in welcher Reihenfolge Maschinen den Menschen überholt haben. IBMs Deep Blue gewann 1997 einen Wettkampf gegen Garri Kasparow. DeepMinds AlphaGo besiegte Lee Sedol 2016 im Go mit 4:1. Top-Profis im No-Limit Texas Hold’em überzeugend zu schlagen, gelang Programmen dagegen erst 2017 – am bekanntesten Libratus – und auch nur im Eins-gegen-eins. An einem Tisch mit sechs Spielern schaffte es sein Nachfolger Pluribus im Jahr 2019.

Dabei geht es nicht nur um Rechenleistung. Ein Schach- oder Go-Programm beantwortet die Frage „Welcher Zug ist der beste?“. Ein Poker-Programm muss eine andere beantworten: „Wie oft mache ich welchen Zug, wenn der Gegner meine Gewohnheiten beobachtet?“. Maschinen mussten lernen, im richtigen Verhältnis zu bluffen.

Für menschliche Spieler ergeben sich daraus drei Fragen, die sich vor jeder wichtigen Entscheidung lohnen – am Brett und abseits davon:

• Was sieht mein Gegner? Wenn alles, muss Ihr Plan auch dann gut sein, wenn er durchschaut ist. Eine Schachfalle, die nur funktioniert, wenn niemand sie bemerkt, ist eine Wette auf einen Fehler, keine Strategie.
• Was sieht er nicht? Wenn etwas verborgen ist, wird Berechenbarkeit zur Schwäche.
• Ist das wirklich ein Nullsummenspiel? Auf dem Brett schon. Im Beruf, in Freundschaften oder in Verhandlungen oft nicht – und eine solche Situation wie eine Schachpartie zu behandeln, ist der teuerste Fehler von allen.

Übung

1. Ordnen Sie diese Spiele mit den fünf Fragen ein: Domino, Monopoly, Werwolf (auch als Mafia bekannt), Tic-Tac-Toe. Eines davon ist ein Zwei-Personen-Spiel mit vollkommener Information ganz ohne Zufall, und es ist längst gelöst: Bei richtigem Spiel beider Seiten endet es unentschieden. Welches?
2. Ändern Sie die Streichholzregel: Jetzt darf man ein, zwei oder drei nehmen. Bei wie vielen Hölzern auf dem Tisch ist der erste Spieler zum Verlieren verurteilt?
3. Spielen Sie das Streichholzspiel mit jemandem, der diesen Artikel nicht gelesen hat. Wie viele Partien braucht er, bis er das Muster erkennt?

Die Antworten stehen am Ende.

Fragen zur Diskussion

• Denken Sie an eine Partie, die Sie nicht wegen schwacher Züge verloren haben, sondern weil man Sie „gelesen“ hat. Was hat Sie verraten?
• Stimmen Sie von Neumann zu, dass Schach „kein echtes Spiel“ ist? Was fehlt seiner Definition aus Sicht einer Spielerin oder eines Spielers?
• Welche Situation in Ihrem Leben ähnelt am meisten dem Poker, welche dem Schach?

Als Nächstes in der Reihe: „Schach hat eine Antwort – aber niemand kennt sie“, über den Satz von Zermelo, das gelöste Damespiel und Go, das sich bis heute widersetzt.

Antworten. 1) Tic-Tac-Toe. Domino und Werwolf haben verborgene Information; Monopoly hat Würfel und mehr als zwei Spieler. 2) Wenn die Zahl der Hölzer ein Vielfaches von 4 ist: Der zweite Spieler ergänzt den Zug des Gegners immer auf vier.