Anfang des Jahrs sorgte der Cepheus-Bot der Universität Alberta für Schlagzeilen. Dies ist die erste Maschine, die Limit-Hold’em in der Heads-Up-Variante gelöst hat.
In mehreren Magazinen hieß es gleich laut und rumpelnd: Poker ist gelöst! Ist da etwas dran? Natürlich nicht, denn gelöst ist nur eine einzige Variante von Poker – Limit Hold’em mit zwei Spielern und es handelt sich hierbei auch noch um eine sogenannte “schwache” Lösung. Was meint das überhaupt? Schauen wir dazu auf ein bisschen Spieltheorie:
Was heißt es, ein Spiel zu lösen?
Seitdem es Computer gibt, versuchen Menschen, mit ihnen Lösungen für Spiele zu finden. Eine Lösung für ein Spiel hat man, wenn man eine Strategie angeben kann, mit der man immer gewinnt oder zumindest nicht verliert.
Von einer “starken Lösung” spricht man, wenn man einen Algorithmus angeben kann, der – egal wie die Spielsituation grade aussieht – ein optimaler Zug berechnet werden kann. Dame-Spiele mit 8 Steinen, Schachendspiele mit maximal 7 Steinen oder auch Gomoku sind stark gelöst. Der Computer schaut sich hier die Spielsituation an, kann sagen, wer gewinnt und den korrekten Zug angeben.
Viele Spiele sind jedoch nur “schwach gelöst” – hier kann eine optimale Strategie vom Ausgangspunkt des Spiels angegeben werden. Allerdings kann der Computer nicht notwendig aus jeder Position heraus den optimalen Spielzug finden. Schwach gelöste Spiele sind zum Beispiel Mühle oder Checkers.
Bei schwach gelösten Spielen kann der Algorithmus Probleme mit suboptimal spielenden Gegnern haben. Das Checkers-Programm Chinook zum Beispiel verliert zwar nie gegen einen Spieler (zwei perfekte Spieler spielen immer Unentschieden), aber wenn der Gegner Fehler macht, kann es passieren, dass das Programm diese Fehler nicht ausnutzt und nur unentschieden spielt, obwohl ein Sieg möglich ist.
Und wie ist Heads-Up Limit Hold’em nun gelöst?
Die zuvor als Beispiele erwähnten Spiele sind allesamt Spiele mit perfekter Information – jeder Spieler kennt zu jedem Zeitpunkt die gesamte Spielsituation und es gibt keinen Zufall.
Bei Poker ist es anders, weswegen das Spiel deutlich schwieriger für einen Computer ist. Nicht nur gibt es unzählige Kombinationen von Handkarten, Board-Karten und bisherigen Setzfolgen, sondern eben auch noch zufällige Elemente für die folgenden Karten.
Die Wissenschaftler von der Universität Alberta benötigten über 260 Terabyte Speicher, fast 5.000 Prozessorkerne und über zwei Monate Rechenzeit, um Heads-Up Limit-Hold’em durchzurechnen.
Ganz banal gesprochen spielte der Computer ständig gegen sich selbst, bewertete sein Spiel nach jedem Ergebnis neu und passte seine Strategien ein wenig an. dabei verwendete man einen sogenannten Counterfactual Regret Minimization Algorithmus. Dieser – wieder sehr einfach gesprochen – wertet Strategien, die zu Verlusten führen, ab.
Nach 68 Tagen Rechenzeit war der Algorithmus fertig, die Strategien änderten sich nicht mehr.
Das fertige Ergebnis ist eine auf 12 Terabyte komprimierte Datenbank, die für jede Spielsituation Anweisungen parat hält. So sagt die Datenbank etwa, dass der Computer die Hand Zehn-Vier-Offsuit vom Button vor dem Flop in 25,2% der Fälle folden soll, in 0,2% der Fälle callen soll und in 74,6% der Fälle raisen soll.
Eine schwache Lösung für Poker
Was kann diese Maschine nun leisten? Der Bot, der auf den Namen Cepheus getauft wurde, spielt mehr oder weniger perfektes Limit-Hold’em Heads-Up.
“Mehr oder weniger perfekt” heißt hier: Egal, wie man gegen den Bot spielt, die langfristige Erwartung der Gegner liegt bestenfalls bei plus/minus Null1.
Der Bot passt sich allerdings nicht seinen Gegnern an, sondern spielt stur immer die selbe Strategie. Sprich: Der Bot bemüht sich nicht, möglichst viel zu gewinnen – etwa indem er gegen zu tighte Spieler etwas looser wird.
Der Bot ist nicht dazu ausgelegt (und auch nicht in der Lage) maximale Gewinne gegen schwächere Gegner zu machen, sondern stellt lediglich sicher, dass er auf lange Sicht nicht verliert.
Insofern kann man bei Cepheus nur von einer schwachen Lösung für Limit-Heads-Up-Hold’em sprechen.
Wie spielt Cepheus überhaupt?
Beim Cepheus Poker Project kann man gegen Cepheus spielen oder die Strategie-Datenbank abfragen.
Im praktischen Spiel zeigt sich, dass der Bot – wie alle Heads-Up-Limit-Bots – aggressiv und loose spielt. Allerdings erweckt er einen nicht ganz so aggressiven Eindruck wie etwa der Neo Poker Bot.
Wie loose der Bot spielt, zeigt ein Blick auf die Preflop-Strategien. Vom Button aus zum Beispiel raist der Bot fast alle Hände fast immer – auch Hände wie T5o oder J3o. Nur die schlechtesten ungleichfarbigen Hände werden entsorgt. Gegen einen Raise spielt der Bot im Big Blind fast alle Hände weiter, wie dieses Diagramm zeigt:
Entwarnung für No-Limit
Für No-Limit-Hold’em muss man sich ob des Bots noch keine Sorgen machen. Zwar gibt es inzwischen viele Bots, die sehr patent No-Limit-Hold’em spielen können, aber von einer spieltheoretisch optimalen Lösung ist man noch meilenweit weg.
Die Komplexität von No-Limit-Hold’em liegt deutlich über der von Limit-Hold’em.
Jeremy Hsu berichtet im IEEE Spectrum, dass No-Limit-Spiele 147 Größenordnungen komplexer sind. Sprich: Wenn man für Limit-Hold’em 260 Terabyte Speicher braucht, sind es für No-Limit-Hold’em 10147 mal so viel – eine im Moment reichlich fantastische Zahl.
Mit neuen Algorithmen, schnelleren Rechnern und Kompressionsmethoden wird man irgendwann wohl auch eine Lösung für No-Limit-Spiele finden. Bis dahin allerdings wird noch eine Menge Zeit vergehen.
Am Ende sind diese spieltheoretisch optimal spielenden Bots für den praktischen Gebrauch auch nicht mehr relevant. Beim Poker geht es schließlich darum, das meiste Geld von seinen Mitspielern zu gewinnen und nicht darum, sicherzustellen, langfristig nicht zu verlieren.
Limit-Hold’em durch Cepheus gelöst
Welche Zukunft hat die AI beim Poker? Englisch?
Wie Cepheus Limit-Holdem gelöst hat, englisch
1 Eine genau auf diesen Bot ausgerichtete Gegenstrategie könnte rein theoretisch langfristig 0,001 Big Blinds pro Spiel gewinnen.
Dieser Artikel erschien auf PokerOlymp am 27.02.2015.
