Verschiedenste Medien berichteten diese Woche unisono, dass ein Forscher aus Manchester jüngst herausgefunden habe, dass Poker ein unlösbares Spiel sei, da es zu komplex ist. Ebenso seien auch Schach, Go oder der Börsenhandel unlösbar insofern, als dass keine optimalen Strategien angegeben oder vom Menschen gefunden werden können.
Was ist an diesen Berichten dran?
Zunächst hat der Forscher aus Manchester, Dr. Tobias Galla, das gar nicht so “jüngst” herausgefunden. Das Paper Complex dynamics of complicated games, auf welches man sich bei den Berichten indirekt bezieht, stammt schon aus dem Jahr 2011. Galla beschäftigt sich hauptsächlich mit Spieltheorie, statistischen Mechaniken und evolutionären Lernalgorithmen bei Spielen.
In dem Paper zeigt Galla, dass komplexe Spiele anders gelöst werden müssen als sehr simple Spiele und (sehr einfach formuliert) dass ein reines Ausspielen und Testen aller Strategien in vielen Fällen nicht die optimale Strategie zu Tage fördert.
Tatsächlich sind sowohl Schach, als auch Go und Poker spieltheoretisch lösbar, denn diese Spiele haben eine endliche Zahl an Zuständen und eine endliche Zahl an möglichen Strategien. Für solche Spiele gibt es immer eine optimale Lösung – ein Nash-Gleichgewicht in gemischten Strategien. Was das überhaupt heißt, will ich kurz erläuert.
Nash-Gleichgewichte
Bei Zwei-Personen-Spielen ist ein Nash-Gleichgewicht ein Strategiepaar der beiden Spieler, bei dem die jeweiligen Strategien so gestrickt sind, dass keiner der beiden Spieler profitabel von seiner Strategie abweichen kann.
Schauen wir uns zur Erklärung ein einfaches Beispiel an: Das Spiel Stein, Schere, Papier. Dieses Spiel hat genau drei Einzelstrategien – man spielt Stein, Schere oder Papier.
Eine Gleichgewicht hier wäre, wenn beide Spieler mit einer Wahrscheinlichkeit von je einem Drittel Stein, Schere oder Papier spielten. Bei jeder anderen Strategie könnte der Gegner seine Gewinnwahrscheinlichkeit verbessern. Spielt Spieler A zum Beispiel in 50% der Fälle Stein und zu je 25% Schere oder Papier, könnte Spieler B immer Papier spielen und so die Hälfte aller Spiele gewinnen, anstatt nur ein Drittel, wie es es bei der Gleichgewichtsstrategie möglich wäre.
Bei vielen Spielen kann man solche Gleichgewichte nur in sogenannten gemischten Strategien geben. Das sind Strategien wie in dem Stein-Schere-Papier-Beispiel: In x Prozent der Fälle spielt man a, in y Prozent der Fälle b und so weiter. Eine reine Strategie wäre gegeben, wenn man immer genau eine der Einzelstrategien spielte.
1950 hat John Nash gezeigt, dass für die meisten Spiele mindestens ein solches Gleichgewicht in gemischten Strategien existieren muss. In reinen Strategien ist dies nicht immer möglich.
Insbesondere endliche Spiele haben immer ein solches Nash-Gleichgewicht.
Nash-Gleichgewichte beim Poker
Poker ist ein endliches Spiel – es gibt nur 52 Karten und begrenzt viele Spielzüge. Ergo gibt es auch für Poker eine Gleichgewichtsstrategie.
Spieltheoretisch sieht allerdings schon eine Einzelstrategie beim Poker reichlich komplex aus – sie gibt für jede mögliche Kartenverteilung und für jeden möglichen Spielverlauf an, welcher Zug zu machen ist. Nun gibt es beim Heads-Up-Hold’em schon allein über 2,7 Billionen verschiedene Kartenverteilungen1. Spielt man Limit, gibt es für jede diese Kartenverteilungen etwas über 10.000 verschiedene Setzfolgen2. Damit kommt auf etwa 20 Billiarden (20.000.000.000.000.000) mögliche und verschiedene Limit-Heads-Up-Hold’em-Spiele. Eine Einzelstrategie gibt nun für jedes dieser möglichen Spiele an, wie zu verfahren ist.
Kein Spieler hat auch nur ansatzweise so viele Kombinationen im Kopf, wenn er über eine Strategie nachdenkt, aber spieltheoretisch muss man von zig Billiarden verschiedenen Einzelstrategien ausgehen.
Die optimale Strategie beim Poker, beziehungsweise die Nash-Strategie, wird gleich noch komplexer. Denn sehr wahrscheinlich existiert diese nur in gemischten Strategien. Das heißt, keine einzige der zig Billiarden Strategien allein reicht aus, um ein Nash-Gleichgewicht herzustellen. Viel mehr sieht diese optimale Strategie so aus, dass jeder möglichen Einzelstrategie eine Wahrscheinlichkeit beigemessen wird, mit der diese ausgewählt wird.
Praktisch gesehen wird man diese optimale Strategie nie finden, aber es ist sicher, dass eine existiert und es ist zumindest ansatzweise vorstellbar, dass man irgendwann Computer herstellen kann, die mit so aberwitzig großen Datenmengen umgehen können und die diese Strategie finden könnten.
Poker ist zu komplex für Computer
An dieser Stelle kommt Dr. Tobias Galla daher und prüft, ob und wie Computer eine optimale Strategie überhaupt finden können.
Computern ist es zum Beispiel recht einfach möglich, für simple Spiele – wie obiges Stein, Schere, Papier, diese optimale Strategie zu finden. Dafür lässt man den Rechner sehr häufig gegen sich selbst spielen und passt die Strategie nach jedem Spiel ein wenig an. Einzelstrategien, die zum Erfolg führten, werden etwas häufiger gespielt, Einzelstrategien, die erfolglos blieben werden etwas seltener gespielt. Nach einer hinreichenden Wiederholung des Spiels konvergieren die Wahrscheinlichkeiten für die Einzelstrategien und heraus kommt eine Gleichgewichtsstrategie.
Nun ist Stein, Schere, Papier äußerst simpel – es gibt nur drei Einzelstrategien (eines der drei spielen). Funktioniert diese Vorgehensweise noch bei etwas komplexeren Spielen mit mehr verschiedenen Einzelstrategien?
Zum Test hat Galla ein rein fiktives Spiel mit 50 Einzelstrategien genommen und den Rechner gegen sich selbst spielen lassen. Das Ergebnis war eindeutig – der Rechner kommt in der Regel auf keine Gleichgewichtsstrategien. Egal wie lange man den Rechner gegen sich spielen ließ, er änderte immer wieder seine Bewertungen der Einzelstrategien und das Änderrungsverhalten der Strategien verlief chaotisch, das heißt nicht vorhersehbar.
Zwar gibt es notwendig auch bei diesem fiktiven Spiel mit 50 Einzelstrategien eine Gleichgewichtslösung, doch die Methode diese zu finden (erfolgreiche Strategien häufiger Spielen, erfolglose seltener), kam nicht zu dieser.
Wenn das Ganze schon bei einem Spiel mit 50 Einzelstrategien nicht funktioniert, kann man sich ausmalen, wie dieser Ansatz wohl bei Poker mit zig Billiarden Einzelstrategien funktionieren dürfte: Gar nicht.
Ebensolches gilt auch beim Schach oder Go, da diese eine zumindest in der Größenordnung ähnliche Komplexität besitzen.
Um derartig komplexe Spiele auf dem Rechner überhaupt lösen zu können, sind andere Algorithmen als der von Tobias Galla verwendete von Nöten.
Welchen Sinn hat denn eine optimale Strategie beim Poker?
Rein nach Definition hört sich eine optimale Strategie erst mal ganz gut an: Man spielt so, dass der Gegner, ganz egal wie er spielt, langfristig nicht besser abschneiden kann als wenn er auch die optimale Strategie spielte. Man wäre also quasi unschlagbar.
Aber ist das wirklich das Ziel der Übung? Ganz offensichtlich hat man beim Poker starke Anreize, von einer optimalen Strategie abzuweichen, wenn offensichtlich ist, dass der Gegner bestimmte Tendenzen hat. Gegen einen notorischen Bluffer callt man häufiger als spieltheoretisch optimal wäre, gegen einen Beton-Spieler wird man tighter. Ziel beim Poker ist es schließlich nicht, langfristig unschlagbar zu sein, sondern Gewinn zu machen.
Insofern wäre eine Nash-Strategie beim Poker nur bedingt sinnvoll. Relevant wäre sie im Grunde nur dann, wenn zwei Super-Rechner gegeneinander spielten, die versuchten sich über einen unvorstellbar langen Zeitraum zu messen. Aber von Rechnern, welche die zig Billiarden Einzelstrategien beim Poker überhaupt verarbeiten könnten, sind wir mindestens noch ein paar Jahrzehnte entfernt.
Dass Nash-Strategien häufig eher konter-intuitiv sind und nur bedingt im praktischen Gebrauch zur Anwendung kommen, zeigt sich in vielen Beispielen. Ein reichlich erstaunliches ist das Urlauberdilemma – ein fiktives Spiel bei dem beide Spieler in der Gleichgewichtsstrategie ihren eigenen Gewinn minimieren, um sicherzustellen, dass sie nicht schlechter als der Gegner abschneiden können.
1 Tatsächlich sind es (52 * 51 / 2) * (50 * 49 / 2) * (48 * 47 * 46 * 45 * 44 / 6! ) = 2.781.381.002.400
2 Das sind Folgen dieser Art: Preflop raise/call, Flop: check/bet/call, Turn bet/raise/call, etc. Für No-Limit-Spiele gibt es noch deutlich mehr solcher Setzfolgen, da zusätzlich der gesetzte Betrag variieren kann.