Heads-up Limit Hold'em Poker ist eine Zwei-Spieler-Untervariante von Texas Hold'em Poker, bei der die Wetteinsätze limitiert sind.
¶ Spielregeln
Gespielt wird mit einem Standard-Kartendeck aus 52 Karten, bestehend aus den Karten 2, 3, 4, 5, 6, 7, 8, 9, 10, Bube, Dame, König und Ass jeweils in den Farben ♥, ♦, ♣, ♠. Ziel ist es, eine möglichst "hohe Hand" also eine wertvolle Kombination aus fünf Karten, zu bilden.
Zu Beginn einer Partie teilt der Dealer beiden Spielern zwei verdeckte Karten aus, nachdem die Spieler bereits ihre obglitarischen "Blinds" gesetzt haben. Blinds sind Wetteinsätze, die bereits vor der Partie gesetzt werden, um sicherzustellen, dass in jeder Partie um einen bestimmten Mindestbetrag gespielt wird. Es gibt den Small Blind und den Big Blind. Der Small Blind wird vom Dealer gesetzt und der Big Blind vom Gegenspieler, wobei der Wert des Big Blinds dem doppelten Wert des Small Blinds entspricht.
Nachdem beide Spieler ihre eigenen Karten gesehen haben, folgen insgesamt vier weitere Setzrunden: Preflop, Flop, Turn und River. Vor dem Flop werden drei Karten offen in die Mitte des Tisches gelegt. Vor dem Turn und River folgt jeweils eine weitere offene Karte, sodass am Ende insgesamt fünf offene Karten zwischen den Spielern liegen.
Innerhalb einer Setzrunde haben die Spieler abwechselnd die Möglichkeit, den aktuellen Einsatz zu "callen" (mitzugehen), zu "raisen" also um einen festen Betrag zu erhöhen oder zu "folden", wodurch der Gegenspieler die Partie und somit den aktuellen Pot gewinnt. Pro Setzrunde gibt es einen "Raise-Cap", durch den die Anzahl der Erhöhungen des Wetteinsatzes limitiert ist.
Wird eine Partie nicht frühzeitig durch den Fold eines Spielers beendet, kommt es nach der letzten Setzrunde zum "Showdown". Im Showdown decken beide Spieler ihre Karten auf und der Spieler mit der höheren Hand gewinnt. Die Hand setzt sich aus den eigenen zwei Karten sowie den fünf offenen Karten zusammen. Das Ranking der möglichen Hände ist in Abb. 1[1] zu sehen.
¶ Komplexität
Bei Heads-Up Limit Hold'em Poker handelt es sich um ein endliches, Zwei-Spieler Nullsummenspiel mit unvollständiger Information. Das bedeutet, dass Spieler nicht über die gesamte Information der bisherigen Aktionen verfügen. Beispielsweise ist es einem Spieler nicht bekannt, welche zwei Karten seinem Gegner ausgeteilt wurden. Diese Eigenschaft macht Spiele deutlich schwieriger zu lösen, da es für einen Spieler unmöglich zu bestimmen ist, in welchem Spielzustand des Spielbaums er sich exakt befindet.
Heads-Up Limit Hold'em Poker ist die kleinste Pokervariante, die von Menschen kompetitiv gespielt wird mit einer Anzahl von etwa 3.16 x 1017 möglichen Spielzuständen.[2]
¶ Lösungsansatz
Um Spiele mit unvollständiger Information zu lösen, fasst man Spielzustände, die für einen Spieler nicht voneinander zu unterscheiden sind, zu "Information Sets" zusammen.
In Abb. 2[3] bilden die rot und blau umrandeten Knoten jeweils Teile eines Information Sets, da sie sich lediglich in den Karten von Spieler 2 unterscheiden, über die Spieler 1 jedoch keine vollständige Information hat. Insgesamt hat Heads-Up Limit Hold'em Poker selbst nach dem Entfernen einiger Information Sets aufgrund von Symmetrien noch 1.38 x 1013 verschiedene Information Sets.[2:1]
Im Jahr 2003 gelang es Billings et al.[4] mithilfe von Sequence-Form Linear Programming einige stark vereinfachte Formen von Heads-Up Limit Hold'em Poker zu lösen und das erste kompetitive Pokerprogramm zu entwickeln.[2:2] Jedoch wächst der Speicherbedarf unter Verwendung der linearen programmierung quadratisch mit der Anzahl der Information Sets. Daher etablierte sich in den folgenden Jahren ein neuer Ansatz: Counterfactual Regret Minimization (CFR). CFR ist ein iterativer Algorithmus, der entwickelt wurde, um in Spielen mit unvollständiger Information ein "Nash equilibrium" zu finden oder wenigstens zu approximieren. Ein Nash Equilibrium ist ein Zustand, in dem kein Spieler seinen erwarteten Gewinn durch eine Änderung seiner eigenen Strategie erhöhen kann, solange die Strategie des Gegenspielers gleich bleibt.
Bis 2012 konnten mithilfe des CFR Algorithmus immerhin vereinfachte Formen von Heads-Up Limit Hold'em Poker mit bis zu 3.8 x 1010 Information Sets gelöst werden.[2:3]
Bowling et al. gelang es dennoch, mit einer erweiterten CFR Variante eine nahezu optimale Strategie für Heads-Up Limit Hold'em Poker zu berechnen, obwohl die Anzahl der Information Sets deutlich höher ist als in bislang mit CFR gelösten Spielen.
Zur Reduktion des Speicherbedarfs verwendeten die Autoren zunächst Datenkompression. Strategie- und Regretwerte wurden nicht als Gleitkommazahlen gespeichert, sondern in der speichereffizienteren Festkommazahldarstellung. Während der Berechnung werden die Daten dekomprimiert, aktualisiert und anschließen wieder komprimiert.
Des Weiteren wurde der Spielbaum in mehrere "Subgames" unterteilt, wobei Information Sets nicht auf verschiedene Subgames verteilt werden dürfen. Diese Unterteilung in voneinander unabhängige Subgames ermöglicht es, die Berechnungen auf einem Cluster zu verteilen.
¶ CFR(+) angewandt auf Heads-Up Limit Hold'em Poker
Counterfactual Regret Minimization ist ein iterativer Algorithmus, der in jeder Iteration den gesamten Spielbaum durchläuft. Für jede Aktion eines Spielers in einem Information Set wird ein "Utility"-Wert berechnet. Dieser gibt an, welchen Erwartungswert jene Aktion hätte, wenn sie stets ausgewählt worden wäre, während alle anderen Entscheidungen gemäß der jeweiligen Strategien getroffen worden wären. Zusätzlich wird der Erwartungswert des gesamten Information Sets unter der aktuellen Strategie berechnet. Die Differenz dieser beiden Werte liefert den "Regret"-Wert. Ist dieser positiv, so muss die Strategie angepasst werden, da wir es "bereuen" jene Aktion nicht mit einer höheren Wahrscheinlichkeit zu spielen.
Mit jeder Iteration wird die Strategie somit schrittweise angepasst und konvergiert gegen ein Nash equilibrium.
CFR+ ist eine verbesserte Variante des CFR Algorithmus, bei der negative Regret-Werte ignoriert und auf null gesetzt werden. Das verringert den Speicherbedarf und wirkt sich, den Autoren nach, positiv auf die Konvergenzgeschwindigkeit des Algortihmus aus.[2:4] Im Gegensatz zum klassischen CFR Algorithmus wird beim CFR+ Algorithmus zudem als optimale Strategie nicht die durchschnittliche Strategie aller Iterationen gewählt, sondern die Strategie aus der letzten Iteration, um weiter Speicherbedarf zu sparen.
Abb. 3 zeigt einen winzigen Teil des Spielbaums einer Pokerpartie. Hierbei repräsentieren die Knoten Spielzustände und die Kanten mögliche Aktionen des jeweiligen Spielers. Mit einer blauen gestrichelten Linie verbundene Knoten gehören einem Information Set an, sind also für den jeweiligen Spieler nicht voneinander zu unterscheiden aufgrund der fehlenden Information über die Karten des Gegenspielers.
Den Kanten werden gemäß der aktuellen Strategie Werte aus dem Intervall [0;1] zugewiesen, die die Wahrscheinlichkeiten angeben, dass die jeweilige Aktion im aktuellen Information Set ausgeführt wird. Alle ausgehenden Kanten eines Knoten summieren sich demnach immer zu eins. Vor der ersten Iteration des Algorithmus können Strategie, und somit die Kantengewichte, beliebig gewählt werden.
In Abb. 4 besagt die Strategie von Spieler 1 beispielsweise, dass Spieler 1 zu 50% den Zug Raise wählen sollte, zu 45% Call und 5% Fold, vorrausgesetzt einen ♥-König sowie eine ♥-Dame ausgeteilt bekommen zu haben.
Innerhalb jeder Iteration werden nun die Erwartungswerte eines jeden Information Sets, sowie die Erwartungswerte der einzelnen Aktionen eines Information Sets, wie zuvor beschrieben, berechnet. Abb. 5 zeigt den letzt möglichen Zug von Spieler 1. Wählt er Fold, verliert er sicher den bislang gesetzten Betrag. Wählt er Call, kommt es zum Showdown, den Spieler 1 in diesem Beispiel gewinnt, falls Spieler 2 die Karten ♦-Ass und ♣-5 hält. Besitzt Spieler 2 hingegen ♦-Ass und ♣-6, verliert Spieler 1 den Showdown. Das Beispiel ist stark vereinfacht, da es annimmt, dass es nur diese beiden Möglichkeiten gibt, offensichtlich könnte Spieler 2 jedoch noch nahezu jedes andere Kartenpaar auf der Hand haben.
Wichtig ist, dass beiden Spielern in jeder Iteration die jeweilige Strategie des Gegenspielers bekannt ist. Somit lässt sich die bedingte Wahrscheinlichkeit berechnen, dass Spieler 2 ♦-Ass und ♣-5 oder eben ♦-Ass und ♣-6 auf der Hand hat, unter Berücksichtigung der bisherigen Aktionen sowie der Strategie von Spieler 2. Im dargestellten Beispiel hält Spieler 2 aus Sicht von Spieler 1 mit 75% Wahrscheinlichkeit ♦-Ass und ♣-6 und dementsprechend mit 25% Wahrscheinlichkeit ♦-Ass und ♣-5. Somit ergeben sich folgende Erwartungswerte bzw. Utilities:
Daraus lassen sich die Regret Werte als Differenzen der Utility eines Zuges und der Utility des Information Sets mit Strategie berechnen:
Negative Regret Werte werden null gesetzt und ignoriert. Ein positiver Regret Wert führt jedoch zu einer Anpassung der aktuellen Strategie. Demnach wird die Strategie von Spieler 1 in dem betrachteten Information Set so angepasst, dass der Zug Call in der nächsten Iteration etwas häufiger als zuvor gespielt wird.
¶ Ergebnisse
Bowling et al.[2:5] führten ihren finalen Durchlauf des CFR+ Algorithmus auf einem Cluster bestehend aus 200 Rechenknoten mit jeweils 32GB RAM aus. Insgesamt führten sie 1,579 Iterationen des Algortihmus über 68.5 Tage hinweg durch. Die berechnete Strategie erreichte eine "exploitability" von 0.986 milli Big Blinds per Game (mbb/g). Die exploitability misst den erwartenen Gewinn, den ein Gegenspieler mit einer worst-case Strategie gegen die berechnete Strategie maximal erreichen kann. Das bedeutet, dass die Autoren eine Strategie berechnet haben, die selbst gegen ihren worst-case Gegenspieler pro Spiel im Schnitt weniger als ein tausendstel des Big Blinds verliert. Ist der Big Blind 10€, so gewinnt der worst-case Gegner im Schnitt also weniger als einen Cent pro Partie. Diese Strategie ist nahe genug einer optimalen Strategie, sodass die Autoren Heads-Up Limit Hold'em Poker nun als "essentially weakly solved" ansehen. Den auf der berechneten Strategie beruhenden Agenten nannten die Autoren Cepheus. Zudem zeigten Bowling et al., dass der Dealer einen Vorteil von 87.7mbb/g bis 89.7mbb/g gegenüber seinem Gegenspieler hat.[2:6]
Cepheus gilt bis heute als nahezu perfekter Heads-Up Limit Hold'em Poker Agent. Hebt man die Einsatzlimitierung jedoch auf und betrachtet Heads-Up No-Limit Hold'em Poker, gibt es mittlerweile fortgeschrittenere Agenten. Die Anzahl der Information Sets in Heads-Up No-Limit Hold'em Poker beträgt mehr als 6 x 10161 und ist somit nicht allein mit dem CFR+ Algorithmus lösbar. Allerdings verwenden die moderneren Agenten ebenfalls einen CFR Ansatz als Basis.[5]
¶ Literatur
Bowling, M., Burch, N., Johanson, M., & Tammelin, O. (2017). Heads-up limit hold'em poker is solved. Communications of the ACM, 60(11), 81-88. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Bild verändert nach: Bowling, M., Burch, N., Johanson, M., & Tammelin, O. (2017). Heads-up limit hold'em poker is solved. Communications of the ACM, 60(11), 81-88. ↩︎
Billings, D., Burch, N., Davidson, A., Holte, R., Schaeffer, J., Schauenberg, T., & Szafron, D. (2003, August). Approximating game-theoretic optimal strategies for full-scale poker. In IJCAI (Vol. 3, p. 661). ↩︎
Zhang, K., Yang, Z., & Başar, T. (2021). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, 321-384. ↩︎