Effiziente Berechnung des Epsilon-Nash-Equilibriums einer Poker-Variante

Poker ist eine Menge von verschiedenen, komplexen Null-Summen Spielen. Die Komplexität hat ihren Ursprung in Zufallsereignissen und den unvollständigen Informationen der Spieler. Für Null-Summen Spiele existiert mindestens eine Strategie, das sogenannte Nash-Equilibrium, die eine Erwartungswert größer gleich Null besitzt und damit als perfekte Strategie gelten kann. Schon in seinem berühmten Beweis aus dem Jahr 1951 schlussfolgerte der Nobelpreisträger John Nash, dass "die Analyse eines realistischeren Pokerspiels, welches über unser vereinfachtes Model hinaus ginge, eine interessante Angelegenheit" sein müsste. Obwohl der Beweis der Existenz des Nash-Equilibriums von 1951 stammt, gelangen erst ab 2006, durch die Entdeckung des CFR Algorithmus, die ersten, vielversprechenden Versuche das Nash-Equilibrium mithilfe von Software zu berechnen. Diese Arbeit stellt mit dem CGH einen neuen Algorithmus vor, der im Vergleich zum CFR um Größenordnungen schneller das Nash-Equilibrium approximiert. Außerdem werden neue Verfahren zur Erzeugung von verlustfreieren Abstraktionen für die Spielkarten vorgestellt, die eine noch fehlerfreiere Approximation des Nash-Equilibriums ermöglichen. ... mehrDiese neuen Methoden werden an der populären Poker-Variante "Texas No Limit Hold'em Heads-up" evaluiert.

Abstract in englisch:
Poker consists of many complex, zero-sum games. Its complexity is a consequence of random events in the game and the incomplete information available to the players. The Nash equilibrium is a strategy for zero-sum games which has an expected payoff of zero or better, thus making it a perfect strategy. In his renowned original 1951 proof John Nash commented that "The analysis of a more realistic poker game than our very simple model should be quite an interesting affair". However, despite evidence of the existence of a Nash equilibrium dating back to 1951, the first significant attempt to calculate it came with the discovery of the CFR algorithm in 2006.
This dissertation introduces CGH, a new algorithm which calculates an approximate Nash equilibrium orders of magnitude faster than CFR, and also allows much more complicated problems to be solved. Additionally, it introduces new techniques for generating lossless abstractions of the cards, which allow a more precise approximation of the Nash equilibrium. These new methods are applied to the popular poker game "Texas No Limit Hold'em Heads-up".