Modelleren van Tegenstanders in Texas Hold'em Poker Michiel De Muynck
Promotor: prof. dr. ir. Benjamin Schrauwen Begeleiders: Philémon Brakel, Aäron van den Oord Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2012-2013
Voorwoord Eerst en vooral wens ik mijn begeleiders, Phil´emon Brakel en A¨aron van den Oord, te bedanken voor alle steun en begeleiding die ze mij doorheen het jaar voortdurend hebben gegeven. Hun advies was keer op keer bijzonder waardevol. Daarnaast wens ik ook dr. Francis Wyffels en medestudenten Jeroen De Smedt, Tim Schittekatte en Arne Van Damme te bedanken voor de interessante discussies over machine learning en poker die gevoerd werden tijdens de bijeenkomsten met de begeleiders. Vervolgens zou ik graag ook mijn vrienden en familie bedanken voor de morele steun doorheen het jaar en alle jaren ervoor. Tenslotte bedank ik ook mijn promotor prof. dr. Benjamin Schrauwen en het Reservoir Lab voor de kans om dit boeiende onderwerp in dit interessante en snel ontwikkelende onderzoeksdomein te kunnen onderzoeken.
Toelating tot bruikleen
De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.
The author gives permission to make this master dissertation available for consultation and to copy parts of this master dissertation for personal use. In the case of any other use, the limitations of the copyright have to be respected, in particular with regard to the obligation to state expressly the source when quoting results from this master dissertation.
Michiel De Muynck, augustus 2013
Offline Modeling of Opponents in Texas Hold’em Poker Michiel De Muynck Supervisor(s): Benjamin Schrauwen, Phil´emon Brakel, A¨aron van den Oord Abstract— This article proposes a new technique for opponent modeling in Texas Hold’em poker that is able to train a broad class of strategy models on hand histories where information about folded cards is missing. This article also describes how this technique can be used to build a mixture model capable of modeling the strategy of a player relatively accurately with very few observations. Keywords— Opponent modeling, Texas Hold’em poker, hand history, machine learning
I. Introduction Poker is a very interesting game that includes both stochasticity and hidden information, which separates it from other commonly researched games like chess and go. There are still a wide range of unsolved questions with regards to how to build the best poker bot. There are two ways to approach building a bot for Texas Hold’em poker. In one way, the bot tries to minimize its own exploitability. This type of bot will win on average against most opponents but will rarely win a lot against even very weak opponents, because it ignores all past observations of the opponent. The other type of bot uses the past observations of the opponent to try to model the weaknesses of that opponent and exploit those weaknesses to gain much bigger profits. By doing so, it opens itself up to exploitation if the model of the opponent is wrong, so it is very important to build models that are as accurate as possible. This is made more difficult by two facts: 1. When a game ends in all but one player folding, nobody has to show their hand. The cards that the opponent had will forever remain unknown then. 2. Human players usually play less than 100 hands against each other before switching to a different opponent. This means that the model has to be accurate with only a few observations. In previous work, these difficulties were usually handled by using models that only use features that only depend on information that is always known, even when the hands were folded. The interactions between the possible hands of the opponent and the public cards were only indirectly modelled. This article presents the following contributions: • A method to train strategy models that can explicitly model the interactions between possible private and public information, presented in section IV, with two possible models to which this method can be applied, described in the next sections.
•
A method to train a mixture model of other strategy models, that can be used to model the strategy of an opponent accurately after only a few observations, presented in section VIII. II. Rules of Texas Hold’em
In this section, the most important rules and terminology of Texas Hold’em poker are briefly described. In the beginning of the game, each player receives two private cards, called their hand. Then there are 4 rounds of betting, called the pre-flop, the flop, the turn and the river. In each round, every player takes actions, one player at a time, until everyone either calls or folds. The possible actions are: 1. Fold: Throw your private cards away and lose all rights to win the pot. 2. Call: Put enough chips in the pot to make the chips you’ve put in the pot this round match the bet size of this round. 3. Raise: Increase the current round’s bet size by making the number of chips you’ve put in the pot this round match the new betsize. A check is another word for a call when the bet size is 0, and an all-in is a raise where you put all your chips in the pot. After the pre-flop, 3 public cards are revealed to everyone. After the flop and turn, one public card is revealed. If at one point everyone except one person has folded, that remaining person wins the pot. If more than one person hasn’t folded by the time the river is over, called a showdown, the person with the best hand wins. The strength of a player’s hand is measured by the best combination of 5 cards that that player can form with his 2 private cards and the 5 public cards. The possible hand strengths are, in order: no pair, one pair, two pair, three of a kind, straight, flush, full house, four of a kind, and straight flush. If multiple people have the same hand strength, the pot is shared between them. Before the game begins, one person puts in a specified amount in the pot called the small blind, and another person twice as much, called the big blind. In a variant of Texas Hold’em called Limit Texas Hold’em, a player can only raise by a specified amount, usually the big blind. Not having the choice of how much to raise with means the game has a lot less states, which is why it is the poker variant of choice in much of the literature and in this article.
III. Related work The first bot described in the literature that was capable of playing Texas Hold’em on a reasonably competitive level was Loki, designed by D. Papp. et al. in 1998 [2]. The opponent modeling aspect of this bot measures the frequencies of the past actions of the opponent in every possible “context” that the opponent can be in. This context is in Loki the combination of the round number and current bet size. This was later improved in 2002 by A. Davidson et al. in a bot called Poki [3]. Here, this frequentist method was replaced by an artificial neural network that predicts the actions of a player. The features of this network however still primarily encode the action sequence of the game. Poki also introduced a new method of searching the game tree of an imperfect information game, called miximax, that still makes use of the context tree of Loki to estimate the value of a showdown situation. For each showdown context, a histogram of observed hand strenghts is maintained. If on divides the game into a lot of contexts, then a lot of observations are needed before the histograms become accurate. In 2004, D. Billings et al. introduced a new technique in a bot called VexBot [1] that maintains multiple context trees of different sizes and initializes them with game-theoretic values. In 2006, G. Van Den Broeck et al. introduced a new technique that replaces the miximax exhaustive search with a variant of Monte Carlo Tree Search that works on games with imperfect information [5]. For the opponent modeling technique, regression trees were used to predict the action of a player given the public information of this game, and to predict the hand of the player in a showdown. IV. Generic opponent modeling This article proposes a new technique to model the strategy of an opponent given a sequence of observations of this opponent. The technique is applicable to any model with any number of real-valued parameters that is able to provide the following for each possible configuration of parameters: 1. For any given decision of a player, the model must be able to predict a probability distribution over the possible actions that that player can take. No possible action may ever be given a probability of exactly 0. 2. For any given decision of a player, the model must be able to provide partial derivatives with respect to each parameter of the log likelihood of each of the predicted actions. With these quantities, it is possible to calculate the log likelihood that the modeled strategy would produce the entire sequence of observations, as well as the partial derivatives with respect to each parameter of this log likelihood. If the (negative of) this log likelihood is seen as an error function, these parameters can be optimized with a range of optimization algorithms including gradient descent. It can be proven that the following procedure calculates the aforementioned partial derivatives: 1. For each observed game, do:
2. Iterate each possible combination of private cards of all the players. Calculate how likely the model thinks it is that the players would have played the observed actions with those private cards. 3. Normalize these likelihoods to get the likelihood of the combination of private cards given the actions. 4. Iterate each possible combination of cards again, and for each do: (i) For each decision that each player makes with their private cards, calculate the partial derivatives with respect to the model’s parameters of the model’s log likelihood of the observed actions. (ii) Add these derivatives together and multiply the result by the likelihood of the combination of private cards given the actions, as calculated in step 3. 5. Add the weighted partial derivatives together to get the partial derivatives of the total log likelihood of the game. 6. Add these together to get the partial derivatives of the log likelihood of all observations. Iterating all possible combinations of cards is an expensive calculation. However, with the simplifying assumption that the private cards of the players are independent, the private cards of each player can be iterated separately. It is then also possible to model the strategy of only one of the players in the game. V. Bucket abstractions This article proposes two types of models that can be used in the above method. The first is a bucket abstraction, similar to those used in techniques like CFRM [4]. The bucket abstraction divides all of the possible decisions of a player into a number of buckets, and gives to all decisions in the same bucket the same distribution over the n possible actions a1 to an . The buckets use exponential soft-max: a bucket where n decisions are possible has n parameters θ1 to θn : eθi P (ai ) = Pn j=1
eθj
The partial derivatives of these likelihoods to each parameter are easy to calculate. One of the parameters is redundant, as adding a constant to each parameter results in the same strategy. This can be prevented by fixing one of the parameters to always be 0. VI. Weighted average of models Instead of assigning each decision to a bucket, it is also possible to assign to each decision a distribution over multiple buckets or even models. If a decision is assigned to N models or buckets, with pi being the weight with which the decision is assigned to bucket i, and θ is the vector (i) of the parameters of all models, and fa (θ) is the likelihood that model i gives to action a for this decision, then the likelihood that the entire model gives to action a is PN (i) i=1 pi fa (θ). The partial derivatives of the log of the
(i)
1
above likelihood can easily be rewritten in terms of fa (θ) (i) and ∂θ∂k log(fa (θ)), which can both be calculated by the submodels.
frequency fold call raise
0.8
Another type of model that can be used are neural networks. The neural network can be given any structure, as long as the final layer of the network uses the softmax activation function. The partial derivatives of this activation function are easy to calculate, and for the rest of the network the standard backpropagation algorithm can be used. Unlike in the neural network used in Poki, the features do not have to be calculated from public information. As a result, much more expressive features, such as whether the player has a pair or a flush or straight draw, or whether his hand has improved compared to the previous round, can be used. VIII. Mixture model The gradient descent procedure can train a strategy model for a sequence of observations, but complex models with many parameters will require many observations to become accurate. In a real game, however, it is important to get an accurate model with very few observations. That is why this article proposes a second technique, based on the EM algorithm, that is able to train a mixture model of strategies on a set of observed games such as a hand history. This mixture model consists of K mixture components, which are strategies corresponding to a parametrized model that fulfills the requirements of a model from section IV. The proposed method goes as follows: 1. For each player i in the hand history, calculate the likelihood that the strategy of mixture component j would play all the games of player i the way player i did. After normalisation, these are the responsibilities of component j for player i. 2. The parameters of each mixture component j are updated by running one iteration of (stochastic) gradient descent on the hand history, where the weight of a hand is the responsibility of component j for the hand’s player. This is similar to the EM-algorithm, but instead of fully optimizing the parameters of the models in step 2 (the Mstep), only one iteration of gradient descent is performed. The running time of the above algorithm scales linearly with K. This can be prevented by in the M-step assigning a hand randomly to one of the mixture components, with the probability of assigning a hand of a player to a component being the responsibility of the two. It is not necessary to assign all hands of a player to the same component. The mixture model can be used as follows: if a new player is observed playing a sequence of games, the likelihood that each mixture component strategy would have played the observed games can be calculated. These likelihoods, or rather their corresponding responsibilities, can be used as weights for a weighted average of the strategies
probability
VII. Neural Networks 0.6 0.4 0.2 0
0
0.2
0.4
0.6
0.8
1
E[HS] Fig. 1. Toy strategy that factors only E[HS] into its decision (solid lines) compared to a bucketing abstraction model trained on a million hands of that strategy (marks). The bars indicate how often each E[HS] occurs.
of the mixture components. This weighted average is the model of the player’s strategy. IX. Results A. Toy strategy It is important to verify empirically that the described technique is actually capable of modelling the strategy of an opponent. For this, we use a simplistic toy strategy that looks only at Expected Hand Strength E[HS] to decide its actions. E[HS] is the expected value of the probability of winning if the opponent’s hand is uniformly random and there will be no more folds in the game. The distribution that the toy strategy gives to each action is given by the solid lines in figure 1. This toy strategy is played against itself to generate a hand history of a million hands. Then a bucketing abstraction model with 50 buckets, one for when E[HS] is between 0 and 0.02, one for E[HS] between 0.02 and 0.04, etc. is trained on this dataset. The result is given by the marks in figure 1. It is clear that the trained strategy approximates the actual strategy very closely. B. Comparison of strategy models It is also important to evaluate how well each model performs on more realistic data. For this, a hand history of one million hands of 2-player Limit Texas Hold’em played on iPoker has been purchased from PokerTableRatings.com. Table I gives the average negative log likelihood that each model has for half of this dataset, after training the models on the other half. The Random model always gives an equal chance to all the possible actions. It is used as a reference point. The model denoted as ANN-Poki in table I is a neural network similar to the one used in Poki [3]. The features
Model Random ANN-Poki CT-Loki CT-Vexbot Regression tree Bucketing ANN
- avg. log likelihood 9.431 6.302 6.965 6.19 6.158 5.748 5.566
TABLE I Average negative log likelihoods of the hand history of a variety of models after training, measured in bits.
encode public information about the bet sequence, such as the last action of the opponent and the round number. The models CT-Loki and CT-Vexbot are frequentist models similar to the opponent modeling used in respectively Loki [2] and Vexbot [1]. For each possible context, which is the combination of current round number and current bet size, CT-Loki counts the frequency of the actions of the opponent. CT-Vexbot uses multiple of these “context trees” and predicts a weighted average of the predictions of each tree. The model named Regression tree in table I is a model that uses a regression tree to predict the next action based on the public information of the current game, similar to [5]. The above models use only features that encode public information, so no gradient descent is necessary to train these algorithms. The next models are trained using the stochastic gradient descent algorithm described in section IV. The Bucketing model corresponds to the model described in section V. The model named ANN is the neural network described in section VII. C. Mixture model It is also necessary to verify empirically how well the mixture model technique works. One way this was achieved was by defining multiple toy strategies and generating a hand history where each player plays according to one of these strategies. If the number of mixture components matches the number of toy strategies used, the mixture components after training consistently converge to the toy strategies. The mixture model was also used on the realistic hand history to measure how useful the mixture model can be. This was performed as follows: The hand history was again divided into a training and validation hand history, each containing 500000 games. Then two mixture models are trained on the dataset, one with neural networks as mixture components, the other with bucketing abstractions. Both have 10 mixture components. On the other half of the dataset, it is measured (using log likelihood) how well these mixture models can predict
Fig. 2. Average log likelihood of the actions of a player after observing n previous hands of that player.
a game of a player after observing the n previous hands of that player in the dataset. These n observations are used to calculate the responsibilities of each mixture component for the player, and the new game is then predicted using a weighted average of the mixture components. The results are shown in figure 2. The two mixture models are compared to the action-predicting opponent models used in Vexbot [1] and the regression tree used in [5]. It is clear that the mixture model can predict the opponent more accurately with fewer observations than the previous models. D. Conclusion These results show that the proposed gradient descent method is capable of training a strategy model on a hand history for a broad class of models. These trained models can used to train a mixture model, which was shown to be able to model the strategy of a player very accurately with only a few observations. The methods presented in this article can’t be applied directly to models that have discrete parameters for which the partial derivatives log likelihood can’t be calculated. This might be possible by replacing the weighted sum of partial derivatives with multiple parameter updates, one for each term, that use weighted samples. Whether this is possible or not remains to be investigated. References [1] D. Billings, A. Davidson, T. Schauenberg, N. Burch, M. Bowling, R. Holte, J. Schaeffer, and D. Szafron. Game tree search with adaptation in stochastic imperfect information games. In In Computers and Games, pages 21–34. Springer-Verlag, 2004. [2] D. Billings, J. Schaeffer, and D. Szafron. Opponent modeling in poker. pages 493–499. AAAI Press, 1998. [3] A. Davidson, D. Billings, J. Schaeffer, and D. Szafron. Improved opponent modeling in poker. pages 493–499. AAAI Press, 2000. [4] M. Johanson. Robust strategies and counter-strategies: Building a champion level computer poker player. Master’s thesis, University of Alberta, 2007. [5] G. Van Den Broeck, K. Driessens, and J. Ramon. Monte-carlo tree search in poker using expected reward distributions. In Proceedings of the 17th European conference on Machine Learning, pages 289–293, 2006.
Inhoudsopgave Voorwoord
ii
Toelating tot bruikleen
iii
Extended abstract
iv
Inhoudsopgave
viii
1 Inleiding 1.1 Waarom poker? . . . . . . . . . . . . . . 1.2 Regels van Texas Hold’em poker . . . . . 1.3 Nash equilibrium en opponent modeling 1.4 Opponent modeling . . . . . . . . . . . . 1.5 Hand histories . . . . . . . . . . . . . . . 1.6 Doelstellingen . . . . . . . . . . . . . . .
. . . . . .
1 1 2 5 7 8 9
2 Notatie en definities 2.1 Gebruikte notaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Strategie¨en . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Nash equilibrium en opponent modeling . . . . . . . . . . . . . . . . . . .
10 10 12 13
3 Bestaand werk 3.1 Loki . . . . . . . . . . . . . . . . . 3.2 Poki . . . . . . . . . . . . . . . . . 3.3 PsOpti . . . . . . . . . . . . . . . . 3.4 Vexbot . . . . . . . . . . . . . . . . 3.5 Counterfactual Regret Minimisation 3.6 Restricted Nash Response (RNR) . 3.7 Data-Biased RNR (DBR) . . . . .
15 15 17 18 19 20 21 22
. . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . (CFRM) . . . . . . . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . .
. . . . . . .
. . . . . . .
3.8 3.9
Monte Carlo Tree Search (MCTS) . . . . . . . . . . . . . . . . . . . . . . . DIVAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Generieke spelersmodellen 4.1 Gradient descent . . . . . . . . . . . . . . 4.1.1 Log-likelihood . . . . . . . . . . . . 4.1.2 Algemene methode . . . . . . . . . 4.1.3 Gebruikte modellen . . . . . . . . . 4.1.4 Bucketing abstractie . . . . . . . . 4.1.5 Neurale netwerken . . . . . . . . . 4.1.6 Gewogen gemiddelde van modellen 4.1.7 Optimalisatie: hand hashes . . . . 4.2 Gebruik van het model . . . . . . . . . . . 4.3 Andere optimalisatiemethoden . . . . . . . 4.4 Conclusie . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
5 Mixture model van strategie¨ en 5.1 Bestaande unsupervised learning technieken . . . . . . 5.1.1 K-means clustering . . . . . . . . . . . . . . . . 5.1.2 Mixture modellen en Expectation Maximization 5.2 Berekeningsmethode . . . . . . . . . . . . . . . . . . . 5.3 Harde assignatie tijdens trainen . . . . . . . . . . . . . 5.4 Stochastische assignatie . . . . . . . . . . . . . . . . . . 5.5 Initialisatiefase . . . . . . . . . . . . . . . . . . . . . . 5.6 Gebruik van het mixture model . . . . . . . . . . . . . 5.7 Exploitatie . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . 6 Experimentele Resultaten 6.1 Datasets . . . . . . . . . . . . . . . . . . . 6.1.1 HHExchange . . . . . . . . . . . . 6.1.2 Man-Machine Poker Championship 6.1.3 Datamining . . . . . . . . . . . . . 6.1.4 Gefabriceerde data . . . . . . . . . 6.2 Generieke spelersmodellen . . . . . . . . . 6.2.1 Toy strategie . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . .
23 24
. . . . . . . . . . .
26 27 29 34 36 37 42 50 52 53 54 55
. . . . . . . . . .
57 59 59 60 62 64 65 66 67 68 69
. . . . . . .
71 71 71 72 72 73 74 74
6.3 6.4
6.2.2 Bucketing abstractie . . . 6.2.3 Vergelijking van modellen Mixture model . . . . . . . . . . Conclusie . . . . . . . . . . . . .
. . . .
. . . .
7 Besluit en mogelijk verder onderzoek
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
77 79 81 84 87
INLEIDING
1
Hoofdstuk 1 Inleiding 1.1
Waarom poker?
De studie van artifici¨ele intelligentie en machinaal leren is steeds hand in hand gegaan met de studie van spellen zoals schaken en poker. Deze spellen zijn immers een uitstekende benchmark voor de vooruitgang van artifici¨ele intelligentie. Er zijn een aantal factoren die hiertoe bijdragen: De regels van spellen zijn eenvoudig en liggen vast. Dit maakt het mogelijk om puur virtueel spellen te simuleren die exact overeenkomen met hoe het spel in de echte wereld zou gespeeld worden. In andere onderzoeksdomeinen, zoals bijvoorbeeld het maken van een robot die leert navigeren over ruw terrein, is dit veel moeilijker. Elk spel heeft een duidelijke, kwantificeerbare uitkomst. In schaken zijn er drie mogelijke uitkomsten: men wint, men verliest of men speelt gelijk. In poker wint men een bepaalde hoeveelheid geld of chips. Men weet steeds op het einde hoe goed elke speler gepresteerd heeft, zonder dat men hiervoor datasets nodig heeft die manueel gelabeld zijn met gewenste uitkomsten. Er zijn experten waaraan men zich kan meten. Men kan steeds spelers rechtstreeks met elkaar vergelijken door ze tegen elkaar te laten spelen. Zo heeft men niet alleen een goed beeld op welke technieken er beter werken voor bepaalde spellen dan andere, men kan de ontwikkelde computer-spelers ook laten spelen tegen mensen waarvan er op voorhand geweten is hoe goed ze het spel ongeveer beheersen. Kijken naar wie men kan verslaan en wie niet geeft een goede benchmark voor de vooruitgang van de artifici¨ele intelligentie.
2 Er zijn echter zeer veel verschillende spellen, en de technieken die gebruikt worden voor bepaalde spellen zijn dikwijls helemaal anders dan de technieken gebruikt voor andere spellen. De meeste schaakprogramma’s trachten zo veel mogelijk posities en zetten te bekijken en maken gebruik van heuristieken om het zoeken te versnellen. In andere spellen zoals backgammon, waar er dobbelstenen gebruikt worden, maken de beste bots gebruik van machine learning. In poker is er naast de stochastischisteit ook verborgen informatie, waardoor nog andere technieken nodig zijn. Binnen poker zelf zijn er ook nog een groot aantal verschillende varianten die elk hun eigen technieken vereisen, aangezien het aantal mogelijke toestanden tussen varianten vaak vele grootte-ordes verschilt. Als onderwerp van deze thesis is gekozen om Texas Hold’em te bestuderen, meer specifiek de Fixed Limit Heads-Up variant, waarvan de regels beschreven worden in sectie 1.2. Dit is in de literatuur ook de meest bestudeerde variant. Een groot deel van de literatuur die handelt over Fixed Limit Heads-Up Hold’em gaat over het ontwerpen van een zo sterk mogelijke bot die zo goed mogelijk speelt tegen andere bots. Hoewel het maximale potentieel hier zeker nog niet bereikt is, is dit niet de doelstelling van deze thesis. Het is namelijk een verschillende doelstelling om zo goed mogelijk te leren spelen tegen zeer sterke tegenstanders dan om tegen imperfecte tegenstanders (zoals mensen) zo veel mogelijk te winnen. Sectie 1.3 beschrijft het verschil tussen de twee verder in detail.
1.2
Regels van Texas Hold’em poker
Een spel van Texas Hold’em poker begint met een aantal spelers die aan een pokertafel zitten en elk een “hand” van 2 kaarten krijgen. Enkel de speler die de hand krijgt kan die kaarten zien. Dit is dus een vorm van private informatie die voor de andere spelers verborgen blijft gedurende het spel. Vooraleer de spelers echter hun kaarten mogen bekijken moeten een aantal spelers echter eerst een bepaald bedrag, de “blinds”, inzetten. Wie dat moet doen wordt bepaald op basis van wie er de button heeft. Deze button wordt na elk spel volgens klokwijzerzin doorgegeven. De speler die links van de button zit moet een small blind inzetten. Deze small blind is een vast, op voorhand afgesproken bedrag dat de voornaamste factor is in hoe veel er gedurende het spel gemiddeld zal ingezet worden. De speler links van de small blind moet
1.2 Regels van Texas Hold’em poker
3
een big blind inzetten, een bedrag van twee keer de small blind. Als er slechts twee spelers meedoen aan het spel (heads-up) dan zijn de regels echter lichtjes anders en moet de speler met de button de small blind betalen en zijn tegenstander de big blind. Bij het begin van een spel is de speler links van de big blind degene die eerst aan zet is. Hij bekijkt zijn kaarten en beslist of hij wil folden, callen of raisen: Als hij foldt, dan stopt het spel voor hem. Zijn kaarten worden onderaan het kaartspel teruggestoken en de speler verliest al het geld dat hij tijdens dat spel heeft ingezet. De kaarten worden niet getoond aan de andere spelers en blijven voor altijd geheim. Als de speler callt, dan zet hij net voldoende geld in totdat het bedrag dat hij deze ronde ingezet heeft overeenkomt met de huidige bet-grootte. Deze bet-grootte is gelijk aan het hoogste bedrag dat iemand gedurende deze ronde in totaal heeft ingezet. Als de speler niet voldoende geld heeft om dit bedrag te kunnen inzetten is hij all-in en kan hij niets meer doen tot op het einde van het spel. Als de speler raiset, dan zet hij meer in dan nodig is om te callen en verhoogt hij daarmee de bet-grootte. De minimum hoeveelheid waarmee hij de bet-grootte kan vermeerderen, de “minimum raise”, is gelijk aan de grootte van de vorige raise als er tijdens deze ronde al een raise gebeurd is. Anders is de minimum raise gelijk aan de big blind. De maximum raise hangt af van de poker-variant. Als een speler na zijn raise geen geld meer overheeft is hij all-in en moet hij wachten tot het einde van het spel.
Nadat de speler zijn actie gedaan heeft is het aan de speler links van hem om zijn actie te doen, dan de speler links daarvan, enzovoort. Als niemand geraised heeft stopt de ronde nadat iedereen ´e´en actie gedaan heeft, anders stopt het wanneer de speler die laatst geraised heeft opnieuw aan beurt is. Op het einde van de eerste ronde, genaamd de pre-flop, wordt al het geld dat ingezet werd verzameld in het midden in de pot. De bet-grootte wordt dus terug op nul gezet. In de volgende rondes zal het dus soms mogelijk zijn om te callen terwijl de bet-grootte nog op nul staat en men dus niets extra moet inzetten. Dit wordt in de pokerwereld doorgaans geen call genoemd maar een check. Als een speler raiset terwijl de bet-grootte nul is wordt dit een bet genoemd.
4
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Combinatie Royal flush Straight flush 4 of a kind Full house Flush Straight 3 of a kind 2 pair Pair High card
Voorbeeld A♠ K♠ Q♠ 8♣ 7♣ 6♣ 7♠ 7♥ 7♣ K♥ K♣ K♠ J♦ 9♦ 5♦ J♠ T♦ 9♠ A♥ A♠ A♣ K♥ K♣ Q♦ 5♦ 5♠ A♣ K♥ J♣ T♣
J♠ 5♣ 7♦ 9♥ 3♦ 8♠ 7♥ Q♠ J♠ 6♣
T♠ 4♣ 3♥ 9♦ 2♦ 7♥ 5♠ 3♦ T♠ 5♦
Frequentie 0.0032% 0.0279% 0.168% 2.60% 3.03% 4.62% 4.83% 23.5% 43.8% 17.4%
Tabel 1.1: Rangschikking van handen in poker Na de pre-flop worden er drie nieuwe kaarten op tafel gelegd. Dit is de flop. Opnieuw volgt een ronde van inzetten, maar nu is de speler links van de button eerst aan beurt. Na de flop wordt er opnieuw een kaart op tafel gelegd, de turn-kaart. Daarna volgt weer een ronde van inzetten, identiek als na de flop. Dan komt de river-kaart en wordt er opnieuw ingezet. Als op een bepaald moment er nog slechts ´e´en speler overblijft die niet gefoldt heeft, dan wint die speler het spel en krijgt hij al het geld dat gedurende het spel werd ingezet. Hij moet zijn kaarten niet tonen aan zijn tegenstanders. Als er na de river nog twee of meer spelers overblijven die niet gefold hebben dan volgt de showdown, waarin alle overblijvende spelers hun kaarten tonen. De winnaar wordt bepaald op basis van wie de beste combinatie kan vormen van zijn hand met de 5 publieke kaarten. In tabel 1.1 staat de rangschikking van beste naar slechtste combinaties van pokerhanden samen met de frequentie waarmee ze voorkomen als beste combinatie uit 7 kaarten. Een betere soort combinatie verslaat altijd een hand van een slechtere soort, maar binnen dezelfde soort is er ook een ordening: een paar azen verslaat bijvoorbeeld een paar zessen. Een gelijkspel komt enkel voor als de soort combinatie en alle kaarten (op kleur na) hetzelfde zijn. Als gelijkspel optreedt wordt de pot gelijk verdeeld onder de winnaars. Binnen Texas Hold’em bestaan er een aantal varianten over het maximum bedrag dat mag worden ingezet bij een (re)raise: No limit: In no limit mag men steeds zoveel inzetten als men wil. Men kan dus op
1.3 Nash equilibrium en opponent modeling
5
elk moment all-in gaan. Pot limit: In pot limit is de maximale inzet gelijk aan de pot die men zou bekomen na eerst te callen. Indien men meer heeft dan dat kan men dus niet all-in gaan, maar elk mogelijk bedrag tussen de minimum en maximum raise is geldig. Fixed limit: In fixed limit is de maximum raise gelijk aan de minimum raise. Als men (re)raiset heeft men dus geen keuze over de hoeveelheid. Fixed limit heeft ook nog twee extra regels die uniek zijn aan fixed limit: de minimum raise na de turn en river gelijk is aan twee keer de big blind, niet ´e´en keer, en men mag maar (re)raisen tot de bet-grootte 4 keer de minimum raise is.
Merk op dat door de twee extra regels in fixed limit er een limiet staat op hoe groot de pot uiteindelijk kan worden. In heads-up limit bijvoorbeeld kan de totale pot uiteindelijk maximaal 48 keer de big blind bedragen. Indien een speler meer heeft dan de helft hiervan (wat meestal het geval is), dan is een all-in door die speler niet mogelijk en is hoe veel hij bij zich heeft (zijn “stack-grootte”) in feite niet relevant.
1.3
Nash equilibrium en opponent modeling
Er is reeds veel onderzoek gedaan naar het maken van bots die sterk zijn in het spelen van poker. Deze bots zijn ruwweg onder te verdelen in twee categorie¨en: bots die trachten zo goed mogelijk trachten te spelen tegen een perfecte tegenstander, en bots die aannemen dat de tegenstander niet perfect is en trachten de imperfecties van de tegenstander uit te buiten. In de pokerliteratuur worden dit respectievelijk bots die het Nash-equilibrium benaderen en bots die aan opponent modeling doen genoemd. Nash equilibrium Sommige poker bots trachten zo perfect mogelijk te spelen en zo weinig mogelijk fouten te maken. Dit wordt gedaan door aan te nemen dat de tegenstander perfect speelt. Dit wil zeggen dat men doet alsof de tegenstander de strategie van de speler steeds exact kent en zijn strategie zodanig zal aanpassen dat het de strategie van de speler maximaal uitbuit. In dit geval zal de bot dus proberen om zo weinig mogelijk uitbuitbaar te zijn. Indien de bot er in slaagt om minimaal uitbuitbaar te zijn bevinden de bot en zijn perfecte tegenstander zich in een Nash equilibrium. Gemiddeld gezien zullen geen van de twee spelers dan geld winnen.
6 De voordelen van het trachten het Nash equilibrium te benaderen zijn: Aangezien men minimaal uitbuitbaar is zal men tegen elke tegenstander gemiddeld gezien minstens gelijk spelen. Men kan dus gemiddeld gezien nooit chips verliezen door een Nash equilibrium te spelen. Ook als men het Nash equilibrium niet helemaal bereikt maar sterk benadert zal men tegen elke tegenstander gemiddeld gezien nooit veel chips verliezen, zelfs als die tegenstander perfect speelt. Als de tegenstander echter niet perfect speelt maar af en toe fouten maakt, dan zal men gemiddeld gezien tegen deze tegenstander winnen, zelfs als men het Nash equilibrium zelf niet helemaal bereikt.
Het heeft echter ook een aantal nadelen: Hoewel het tegen een zwakke tegenstander gemiddeld gezien wel zal winnen, het zal niet bijzonder veel winnen. Het houdt helemaal geen rekening met hoe de tegenstander aan het spelen is. De tegenstander kan consistent dezelfde fouten blijven maken, maar het Nash equilibrium zal zijn strategie niet aanpassen om daar gebruik van te maken. In het zero-sum poker spel verliest een Nash equilibrium gemiddeld gezien nooit geld. Dit verandert echter als het casino na elk hand een rake int. Dit wil zeggen dat de winnaar van een pot slechts bijvoorbeeld 95% van de pot krijgt, en het resterende geld naar het casino gaat. In dit geval is poker geen zero-sum spel meer en kan een bot die perfect het Nash equilibrium volgt toch gemiddeld geld verliezen terwijl andere bots wel geld winnen.
Opponent modeling Door deze nadelen is er ook veel onderzoek gebeurd naar bots die niet trachten om zo weinig mogelijk exploiteerbaar te zijn, maar die aannemen dat de tegenstander zelf exploiteerbaar is en fouten maakt. De bot zal dan doen aan opponent modeling en trachten deze fouten die de tegenstander consistent maakt in kaart te brengen en ervan gebruik te maken. Het voordeel van dit soort strategie is duidelijk: Als de tegenstander effectief dezelfde fouten blijft maken die men gemodelleerd heeft, dan kan men deze uitbuiten om gemiddeld gezien veel meer chips te winnen dan een Nash equilibrium strategie ooit zou kunnen.
1.4 Opponent modeling
7
Het opponent modeling heeft echter ook een aantal significante nadelen: Door de tegenstander te trachten te exploiteren zal men zijn strategie moeten aanpassen, en op die manier zelf exploiteerbaar worden. Indien het model van de tegenstander verkeerd is kan men dus veel chips verliezen. Indien de tegenstander zijn strategie opeens helemaal verandert, dan is het model van die tegenstander verkeerd en kan men chips verliezen. Indien de tegenstander weet dat de bot aan opponent modeling doet, dan dan die tegenstander modelleren hoe de bot hem modelleert, en daarvan gebruik maken. Op zijn beurt is het dan mogelijk om te modelleren hoe de tegenstander dat doet, enzovoort. Elke soort van deze opponent modeling zal exploiteerbaar zijn door een andere soort. Meestal zullen de spelers die elkaar modelleren echter convergeren naar het Nash equilibrium.
Het succes van een bot die doet aan opponent modeling hangt dus rechtstreeks af van hoe goed het model van de tegenstander is. Het trachten te exploiteren van de fouten die men gemodelleerd heeft kan nooit werken als het model van de tegenstander verkeerd is. Daarom is het doel van deze thesis om zo goed mogelijke modellen te bouwen van de gemiddelde menselijke tegenstander.
1.4
Opponent modeling
Er zijn veel verschillende mogelijke manieren waarop een tegenstander kan gemodelleerd worden. De meest relevante daarvan die in de literatuur reeds voorgesteld en onderzocht werden beschrijf ik in hoofdstuk 3. Er is echter een onderscheid te maken tussen een aantal categorie¨en: Statische en dynamische modellen Indien men veronderstelt dat de tegenstander een vaste strategie heeft die hij van spel tot spel niet verandert, dan bouwt men een statisch model van de tegenstander. Indien deze veronderstelling niet gemaakt wordt, en men expliciet rekening houdt met het feit dat de strategie van de tegenstander verandert of kan veranderen van spel tot spel, dan bouwt men een dynamisch model. De veronderstelling van een statische strategie is enkel correct als de tegenstander niet doet aan opponent modeling en bijvoorbeeld het Nash equilibrium probeert te benaderen,
8 of als de tegenstander vastberaden een bepaalde strategie volgt. Voor een groot deel van zowel bots als mensen klopt deze veronderstelling dus niet. Hoewel het hierdoor lijkt alsof dynamische modellen steeds superieur zijn aan statische modellen, is dit in de praktijk meestal niet het geval. Als de strategie van een speler verandert is dit meestal zeer onregelmatig en moeilijk te modelleren. Daarnaast kunnen statische modellen nog steeds goed werken als de strategie van de tegenstander nooit ver afwijkt van zijn oorspronkelijke strategie, en bijvoorbeeld binnen dezelfde “stijl” blijft. Generieke en adaptieve modellen Een andere classificatie die loodrecht op de vorige staat is tussen generieke en adaptieve modellen. In een generiek model zal men enkel leren wat de gemiddelde tegenstander doet. Dit soort model zal dus geen onderscheid maken tussen welke tegenstander welk hand gespeeld heeft, en doen alsof alle handen door dezelfde tegenstander gespeeld werden. Dit heeft als voordeel dat men veel data heeft, maar tenzij de gemiddelde tegenstander zeer zwak is zal dit geen grove fouten aanduiden die men sterk kan exploiteren. Adaptieve modellen daarentegen zullen zich aanpassen aan de specifieke tegenstander waartegen men speelt. Dit betekent dat men voor elke tegenstander een verschillend model opbouwt, wat toelaat om deze tegenstanders veel beter te exploiteren op hun specifieke fouten. Het nadeel is echter dat men veel minder data per model heeft, dikwijls minder dan honderd handen per tegenstander. Merk op dat het mogelijk is om een generiek model te bouwen voor enkel een deelverzameling van de tegenstanders, of om de handen van sommige spelers meer te laten doorwegen dan die van andere. Dit zal in deze thesis gebruikt worden in hoofdstuk 5.
1.5
Hand histories
Spellen die op een computer gespeeld werden worden vaak opgeslagen in een zogenaamde hand history. Deze hand histories kunnen later gebruikt worden voor verschillende doelen: om te analyzeren hoe goed de strategie van de speler gewerkt heeft, om in latere spellen tegen dezelfde tegenstander statistieken te kunnen opvragen over hoe die speler speelde, enzovoort. Deze hand histories bevatten alle informatie die zichtbaar was voor de speler op het einde van het spel. Als een tegenstander kaarten gefold heeft, dan zullen deze er dus meestal
1.6 Doelstellingen
9
niet instaan, aangezien de tegenstander deze kaarten niet moet tonen. Na het spel zijn de gefolde kaarten enkel gekend door het online casino en de speler die de kaarten had. Zoals eerder vermeld werd in sectie 1.2 moet een speler die als enige overblijft in een spel waarin alle tegenstanders gefold hebben zijn kaarten ook niet tonen na het spel. Deze blijven dus ook geheim, en men kan deze kaarten beschouwen alsof ze gefold waren. Het is niet nodig om deel te nemen aan een spel om hand histories over dat spel op te slaan. Het is ook mogelijk om tafels waaraan men niet deelneemt te bewaren in hand histories. Dit noemt men gedataminede hand histories. Uiteraard bevatten deze hand histories van geen enkele speler informatie over gefolde kaarten.
1.6
Doelstellingen
Het is een lastige uitdaging om ondanks deze ontbrekende informatie toch goede tegenstandersmodellen op te bouwen. In deze thesis staat het aanpakken van deze uitdaging centraal. De modellen die onderzocht worden zullen de private informatie van de tegenstander expliciet modelleren, ook al ontbreekt die dikwijls in de hand histories. Er zal steeds verondersteld worden dat de tegenstander een statische strategie heeft. Zowel generieke als adaptieve modellen worden onderzocht, waarbij de adaptieve modellen zullen verderbouwen op de generieke modellen. De doelstellingen van deze thesis zijn dus tweeledig: 1. Het opbouwen van generieke modellen die de private informatie van de tegenstander expliciet modelleren en onderzoeken hoe deze modellen kunnen getraind worden op basis van hand histories. Dit gebeurt in hoofdstuk 4. 2. Het opstellen van een adaptief model dat weinig observaties van een specifieke tegenstander nodig heeft om die tegenstander toch accuraat te kunnen modelleren. Dit gebeurt in hoofdstuk 5. Eerst worden echter in hoofdstuk 2 de gebruikte notaties en definities ge¨ıntroduceerd die in deze thesis gebruikt worden. In hoofdstuk 3 wordt vervolgens het onderzoek dat in de literatuur reeds werd verricht voorgesteld. Daarna bespreken hoofdstuk 4 en 5 hoe de bovenstaande doelstellingen werden aangepakt. Tenslotte worden in hoofdstuk 6 de experimentele resultaten voorgesteld.
10
Hoofdstuk 2 Notatie en definities 2.1
Gebruikte notaties
Om wiskundige berekeningen te kunnen noteren is het nodig om een formele notatie in te voeren. Dit begint met een formele beschrijving van poker: Poker is een spel waarbij N spelers beurtelings acties ondernemen, waarbij niet iedere speler evenveel informatie heeft maar waar iedere speler beschikt over private informatie, en waarbij er probabilistische gebeurtenissen voorkomen. Poker behoort dus tot de klasse van eindige extensieve spellen met onvolledige informatie [13, p. 200]. Dit soort spel is gedefini¨eerd als de combinatie van: Een eindige verzameling N van spelers. Een eindige verzameling H van histories. Een history is een sequentie van acties die voldoet aan:
– De lege sequentie ∅ ∈ H. – Elke prefix van een history in H zit ook in H. Concatenatie van een history h en een actie a wordt genoteerd als h ◦ a ofwel als (h, a) Een verzameling Z van terminale histories zodanig dat geen element van Z prefix is van een history in H \ Z. Een speler-functie P layer die aan elke niet-terminale history een element uit N ∪{c} toekent. P layer(h) is de speler die aan beurt is na history h. N is hier de verzameling
2.1 Gebruikte notaties
11
van spelers, en c is een symbool dat de “kansspeler” voorstelt. De verzameling van acties A(h) waaruit die speler op dat moment kan kiezen is de verzameling {a : h ◦ a ∈ H}. Als P layer(h) = c, dan wordt de volgende actie die genomen wordt bepaald door toeval.1 Een functie fc die aan elke history h waar P layer(h) = c een probabiliteitsmaat fc (·|h) over A(h) toekent. fc (a|h) is de kans dat na history h actie a voorkomt. De kansen voor verschillende histories zijn onafhankelijk van elkaar. Elke speler i ∈ N heeft een partitie Ii over {h ∈ H : P layer(h) = i} met die eigenschap dat als h en h0 in dezelfde partitie zitten, dan is A(h) = A(h0 ). Deze partitie Ii is de informatie-partitie van speler i, en een verzameling Ii ∈ Ii is een informatieset van speler i. A(Ii ) staat voor A(h) en P layer(Ii ) staat voor P layer(h) van een willekeurige h ∈ Ii . Elke speler i ∈ N heeft een utility functie ui van Z naar R. Als N = {1, 2} en u1 (h) = −u2 (h) ∀ h ∈ Z, dan is het spel een zero-sum extensief spel.
Het zijn de informatiepartities die zorgen voor onvolledige informatie. Als twee histories in dezelfde informatieset van een speler zitten, dan kan die speler geen onderscheid maken tussen de twee histories. In poker bijvoorbeeld zitten alle toestanden die enkel verschillen in de private kaarten van de andere spelers in dezelfde informatieset. Er staan in feite geen beperkingen op hoe de informatiepartities kunnen gekozen worden. Het is dus perfect mogelijk om de informatiepartities zo te kiezen dat een speler sommige acties of observaties die hij eerder in het spel gemaakt heeft vergeet. Indien dat het geval is spreken we van imperfect recall. Formeel wordt perfect recall als volgt defini¨eerd: als Xi (h) de sequentie van informatiesets waarin speler i zich tijdens het spel gevonden heeft en als voor elke twee histories h en h0 die zich in dezelfde informatieset bevinden Xi (h) = Xi (h0 ) geldt, dan heeft het spel perfect recall voor speler i. Als dit niet het geval is dan heeft speler i imperfect recall. Poker is in zijn normale vorm een spel met perfect recall.
1
[13] gebruikt als spelerfunctie P , ik gebruik P layer om later verwarring met probabiliteiten te vermijden.
12
2.1.1
Strategie¨ en
Indien een aantal spelers een spel spelen moeten zij dus gedurende het spel telkens als zij aan beurt zijn een actie kiezen. Hoewel een menselijke speler of een computerprogramma de beslissing over welke actie ze zullen nemen kunnen uitstellen tot wanneer hun beurt effectief komt, toch is het mogelijk om formeel een strategie te beschouwen als een statisch plan dat voor alle informatiesets beschrijft hoe ze zullen spelen. Alle informatie die een speler heeft op het moment dat hij een actie moet kiezen zit immers vervat in de informatieset waarin hij zich bevindt. Het moment waarop de keuze gemaakt wordt is in feite irrelevant. Een strategie verandert dus niet terwijl het spel gespeeld wordt. Uiteraard kan de strategie van een speler tussen twee spellen door wel veranderen. Er kan een verschil gemaakt worden tussen zogenaamde pure strategie¨en en gedragsmatige strategie¨en: Een pure strategie kent aan elke informatieset Ii van speler i een actie toe uit A(Ii ) die de speler altijd zal nemen als hij zich in die informatieset bevindt. Een gedragsmatige strategie daarentegen kent aan elke informatieset Ii van speler i een probabiliteitsdistributie toe over A(Ii ). Als speler in informatieset Ii komt zal hij willekeurig een actie kiezen volgens die distributie. Het kiezen van de acties in verschillende informatiesets gebeurt onafhankelijk van elkaar, aangezien afhankelijkheden zouden betekenen dat de speler meer informatie heeft dan in welke informatieset hij zich bevindt.
Uiteraard zijn alle pure strategie¨en ook behavorial strategie¨en. Formeel worden strategie¨en gedefini¨eerd als volgt: Een strategie van speler i, genoteerd als σi , is een functie die aan elke informatieset Ii een distributie over acties A(Ii ) toekent. Een strategieprofiel σ is een verzameling strategie¨en σ1 , σ2 , ... voor elke speler in het spel. De notatie σ−i staat voor de verzameling van alle strategie¨en in σ behalve σi . De probabiliteit dat een history voorkomt als iedere speler speelt volgens strategieprofiel σ wordt genoteerd als π σ (h). Dit kan gefactoriseerd worden in de bijdragen van elk van de spelers: Y π σ (h) = πiσ (h). i∈N ∪{c}
2.2 Nash equilibrium en opponent modeling
13
Hierin staat πiσ (h) voor het product van de probabiliteiten die speler i gaf aan de σ acties die hij genomen heeft gedurende het spel. π−i (h) is gedefini¨eerd als de bijdragen σ σ van alle spelers behalve i, formeel: π−i (h) = π (h)/πiσ (h). De kans dat, als er volgens strategieprofield σ gespeeld wordt, actie a in history h genomen wordt wordt genoteerd als π σ (a|h) = π σ (h ◦ a)/π σ (h). De kans om een informatieset I te bereiken wordt genoteerd als π σ (I) =
P
h∈I
π σ (h).
De verwachte waarde van het spel voor speler i van een strategieprofiel σ wordt P genoteerd als ui (σ) = h∈Z ui (h)π σ (h).
2.2
Nash equilibrium en opponent modeling
Er zijn twee mogelijke doelstellingen die een pokerspeler kan hebben: ofwel probeert men tegen om het even welke tegenstander zo weinig mogelijk te verliezen, en veronderstelt men dat de tegenstander bijna perfect speelt, ofwel veronderstelt men dat de tegenstander consistent fouten maakt die men kan modelleren en exploiteren. Dit is het verschil tussen het zo dicht mogelijk proberen benaderen van het Nash equilibrium en opponent modeling. Een Nash equilibrium is een strategieprofiel dat “optimaal” is in het opzicht dat als iedereen zijn strategie bekend zou maken aan de andere spelers, toch niemand zijn strategie zou willen veranderen. Formeel is het gedefini¨eerd als een strategieprofiel σ zodanig dat ui (σ) ≥ ui (σi0 , σ−i ) ∀σi0 ∈ Σi , ∀i ∈ N.
(2.2.1)
De waarde vi van het spel voor speler i is gedefini¨eerd als de verwachte waarde ui (σ) voor een Nash equilibrium. Dat deze waarde dezelfde is in alle Nash equilibria is gekend als de Minimax stelling, bewezen in 1928 door John Von Neumann [12]. Het is voor spellen met enorm veel mogelijke toestanden echter bijna onmogelijk om zo’n Nash equilibrium exact te berekenen. Daarom is het niet de bedoeling om het Nash equilibrium exact te berekenen maar zo dicht mogelijk te benaderen. Hoe dicht men tegen het Nash equilibrium zit kan uitgedrukt worden in de exploitabiliteit van een strategie. Die is gedefini¨eerd voor speler 1 in een spel van twee spelers als ex(σ1 ) = max (v1 − u1 (σ1 , σ20 )). 0 σ2 ∈Σ2
14 Deze exploitabiliteit geeft aan hoe veel een speler dus gemiddeld zal verliezen tegen een “worst case” tegenstander. Deze worst case tegenstander van een strategie σ1 wordt de Best Response op σ1 genoemd, en is formeel gedefini¨eerd als elke strategie σ2 waarvoor de bovenstaande vergelijking geldt. Een belangrijke heuristiek die later nog vaak gebruikt wordt is de Hand Strength (HS). Dit is het percentage van handen die de tegenstander kan hebben waartegen men momenteel sterker staat. Dit zal laag zijn voor een hand met veel potentieel maar weinig gegarandeerde waarde, zoals een flush draw (4 van de 5 kaarten nodig om een flush te vormen). Daarom wordt ook de Expected Hand Strength E[HS] metriek vaak gebruikt, die aangeeft wat de verwachte HS is op de river, als er verder niet meer gefoldt wordt. Deze heuristiek worden verder uitgelegd in sectie 3.5.
BESTAAND WERK
15
Hoofdstuk 3 Bestaand werk In dit hoofdstuk worden de voornaamste vormen van opponent modeling beschreven die in de literatuur bestudeerd werden. Aangezien er veel verschillende vormen van poker bestaan, is er ook een grote verscheidenheid aan opponent modeling technieken ontworpen, waarvan sommige technieken echter niet toepasbaar zijn op alle pokervarianten. Nash equilibria kunnen bijvoorbeeld exact berekend worden voor sommige varianten met weinig toestanden, zoals Kuhn poker [11, pp. 97-103], maar niet voor bijvoorbeeld Texas Hold’em. Dit hoofdstuk zal zich voornamelijk toespitsen op de technieken die relevant zijn voor Texas Hold’em.
3.1
Loki
Loki, een poker bot ontworpen in 1998 door D. Papp et al. [14] [4], is een van de eerste poker bots beschreven in de literatuur die aan opponent modeling deed en Texas Hold’em op een redelijk competitief niveau kon meespelen. De bot maakt voor de beslissing over welke actie hij zal nemen gebruik van een regelgebaseerd systeem waarbij de Effective Hand Strength (EHS) (niet te verwarren met de verder beschreven Expected Hand Strength E[HS]) en de Pot Odds de doorslaggevende rol spelen.
Effective Hand Strength (EHS) is een getal dat aangeeft hoe sterk de hand is die men momenteel heeft, in vergelijking met hoe sterk de gemiddelde hand van de tegenstander is. Het wordt als volgt berekend: EHS = HS + (1 − HS)P pot.
16 De HS hierin staat voor de directe Hand Strength. Dit is het percentage van handen waartegen men momenteel beter is als men enkel kijkt naar de publieke kaarten die momenteel op tafel liggen. Handen waartegen men gelijk staat tellen mee voor de helft. Als de publieke kaarten 4♠ 6♠ K♦ zijn en men een hand 3♠ 5♠ heeft, en dus bijna een flush en een straight heeft, zal dit een zeer lage HS hebben, aangezien het hand tegen bijna alle andere kaarten slechter staat. Toch is dat geen slechte hand. Daarom wordt in de berekening van EHS de Positieve potentiaal (PPot) meegerekend, die de kans is dat men een willekeurige hand van de tegenstander die men nu niet verslaat na de river wel zal verslaan.
Pot odds is de verhouding van de grootte van de pot ten opzichte van wat het zou kosten om te callen. De pot odds kunnen vergeleken worden met de kans om te winnen om te kijken of een call positieve verwachte waarde heeft, als men aanneemt dat er verder niet meer zal ingezet worden.
In functie van de doelstellingen van deze thesis is het echter interessanter om te kijken naar hoe de opponent modeling ge¨ımplementeerd is in Loki. In de berekeningen van EHS wordt er in Loki niet verondersteld dat elk hand van de tegenstander even waarschijnlijk is, maar deze handen worden gewogen volgens een weight table. Deze weight table bevat voor elk hand de geschatte kans dat de tegenstander dat hand heeft (niet genormaliseerd). Deze tabel wordt als volgt berekend: Telkens als de tegenstander een actie neemt wordt er bijgehouden hoe vaak de tegenstander reeds die actie genomen heeft in die context. De context is in Loki de combinatie van de ronde (pre-flop, flop, ...) en het aantal te callen bets. Als de tegenstander opnieuw in deze context komt, dan wordt er verondersteld dat de tegenstander steeds met de slechtste kaarten foldt, met de beste raiset, en met de rest callt. Samen met de frequentie waarin de tegenstander elke actie doet komt deze veronderstelling komt overeen met drie intervallen van EHS-waarden waarmee de tegenstander elke actie doet. Elk van deze intervallen heeft een gemiddelde EHS-waarde µactie . Als de tegenstander nu een actie a doet, dan wordt voor elk van de mogelijke handen van de tegenstander het gewicht in de weight table vermenigvuldigd met een geschatte kans dat de tegenstander die actie a zou doen met dat hand. Deze kans wordt ad-hoc berekend
3.2 Poki
17
op basis van hoe ver de EHS van dat hand ligt van µa . Het zijn deze geschatte kansen die het model van de tegenstander vormen in Loki.
Loki werd in 1999 verbeterd door J. Schaeffer et al. [16]. Daarin werd gebruik gemaakt van selective sampling om de rest van het spel meerdere keren te simuleren en zo accuratere beslissingen te kunnen nemen over welke actie er het best genomen wordt. De techniek gebruikt om de tegenstanders te modelleren bleef echter grotendeels hetzelfde.
3.2
Poki
In 2000 werd Loki verder verbeterd door A. Davidson et al. [7]. Er werden neurale netwerken getraind op 19 features waaronder de vorige actie van de speler, of de speler eerst aan zet is, of de tegenstander reeds chips ingezet heeft deze ronde, enz. Uit de resultaten bleek dat twee van deze features, namelijk de vorige actie van de speler en hoe veel bets de speler de vorige keer moest callen, de voornaamste doorslag gaven in het neuraal netwerk. Het neuraal netwerk zelf was echter te traag om te gebruiken in de bot, aangezien er met het neuraal netwerk veel minder simulaties per seconde zouden kunnen uitgevoerd worden. Daarom werden enkel deze twee belangrijkste features toegevoegd aan het bestaand systeem. Dit zorgde ervoor dat in 2002 A. Davidson Loki volledig herschreven heeft met als doel de selective sampling te vervangen door een andere manier van zoeken waarmee de neurale netwerken wel als opponent modeling techniek konden gebruikt worden in de bot [6]. De nieuwe bot werd Poki genoemd, en bevatte twee grote verbeteringen ten opzichte van Loki: verbeterde opponent modeling en een miximax zoektechniek. Opponent Modeling Bij het ontwerpen van Poki werden verschillende opponent modeling technieken onderzocht. De eerste is het expert systeem dat Loki gebruikt, beschreven in sectie 3.1. De tweede is het hierboven beschreven neuraal netwerk met 19 features en 1 verborgen laag van 4 neuronen. Ten derde werden ook beslissingsbomen onderzocht. Uit dit onderzoek bleek dat neurale netwerken het meest accuraat werkten, en dat beslissingsbomen net iets minder nauwkeurig waren. Beide waren echter een grote vooruitgang op het systeem gebruikt in Loki.
18 Er werd ook een meta-predictor systeem onderzocht dat elk van deze technieken liet stemmen en per tegenstander bijhield hoe nauwkeurig elke predictor werkt. Dit werd gebruikt om een gewogen gemiddelde te nemen van de probabiliteits-triples (kans op folden, kans op callen, kans op raisen) die elke techniek voorspelde. Dit meta-predictor systeem werkte iets naukeuriger dan de individuele systemen apart, maar het verschil was zeer klein. Miximax is de techniek die in Poki gebruikt wordt om de spelboom te doorzoeken. Het is zeer gelijkaardig aan minimax dat in vele spellen met perfecte informatie zoals schaken gebruikt wordt. Het verschil is dat in minimax de tegenstander steeds verondersteld wordt om de best mogelijke actie te nemen, terwijl in miximax een opponent modeling module voorspelt met welke kans de tegenstander elk van de acties zal nemen. De waarde van de knoop waar de tegenstander aan zet is, is dan de verwachte waarde over alle acties die mogelijk zijn in die knoop. In knopen waar de bot zelf aan zet is wordt steeds de beste actie genomen. De waarde van een knoop waar gefold wordt is duidelijk: de speler die niet gefold heeft wint de pot. De waarde van een showdown-knoop wordt als volgt berekend: Voor elke sequentie van acties die eindigen in een showdown wordt een histogram bijgehouden van de Hand Strengths (zie sectie 3.1) die tegenstander in die showdown reeds getoond heeft. De kans om te winnen in die showdown met een hand van een bepaalde Hand Strength wordt dan berekend door deze Hand Strength te vergelijken met het histogram.
3.3
PsOpti
Limit Texas Hold’em poker met twee spelers heeft ongeveer 9.17 · 1017 toestanden. Dit is veel te groot om een exact Nash equilibrium voor te berekenen. Daarom hebben D. Billings et al. in 2003 een abstractie van de spelboom ge¨ıntroduceerd die O(107 ) toestanden heeft, waarvoor het Nash equilibrium wel exact kan berekend worden, bij het ontwikkelen van de bot PsOpti [1]. Het Nash equilibrium van dit vereenvoudigd spel kan dan exact berekend worden door de structuur van de spelboom en vergelijking 2.2.1 van de definitie van het Nash equilibrium neer te schrijven als lineaire vergelijkingen en op te lossen met een lineaire programmeertechniek zoals de Simplex methode. Er zijn meerdere aspecten van het spel die geabstraheerd worden:
3.4 Vexbot
19
In Limit Hold’em mag er normaal per ronde 3 keer geraised worden (2 keer in de pre-flop). Dit aantal werd in het abstracte spel met 1 verminderd. De strategie pre-flop strategie van de spelers werd op voorhand gedefini¨eerd en vastgelegd. In het abstracte spel hebben de spelers geen keuze over hun pre-flop acties. Alle toestanden die volgen op een kansknoop (dit is een toestand waar nieuwe publieke kaarten getoond worden) worden gegroepeerd in buckets. Handen met een gelijkaardige Hand Strength komen terecht in dezelfde bucket. Er wordt telkens ´e´en speciale bucket voorzien voor handen met een slechte Hand Strength maar een grote kans om te verbeteren. PsOpti gebruikt 7 buckets per speler per ronde.
Ondanks het feit dat deze abstractie O(1011 ) keer minder toestanden heeft dan het volledige spel bleek het Nash equilibrium voor dit abstracte spel toch relatief dicht bij het Nash equilibrium van het volledige spel te liggen.
3.4
Vexbot
Vexbot, ontworpen in 2004 door D. Billings et al. [2], bouwt opnieuw voort op Poki. Zoals uitgelegd in sectie 3.2, is in Poki de waarde van een bladknoop bij het doorzoeken van de miximax-boom bepaald door het histogram van Hand Strengths die de tegenstander in die knoop reeds getoond heeft. De boom van mogelijke sequenties van acties in Heads-Up Limit Hold’em, de context tree, is echter relatief groot: er zijn 6561 mogelijke actiesequenties die leiden tot een showdown, en dus 13122 HS-histogrammen die moeten bijgehouden worden. Sommige van deze actiesequenties komen relatief vaak voor, andere echter zeer weinig. Er zijn dus veel handen nodig alvorens deze HS-histogrammen nauwkeurig worden. In Vexbot werden twee verbeteringen aan deze techniek ge¨ıntroduceerd: 1. In Poki worden de histogrammen op zeer simplistische standaardwaarden ge¨ınitialiseerd. In Vexbot zijn de initi¨ele histogrammen gebaseerd op spel-theoretische waarden, berekend door PsOpti. Dit betekent dat als er geen data over de tegenstander is in een bepaalde positie, dat die tegenstander verwacht wordt te spelen volgens PsOpti, een benaderd Nash Equilibrium.
20 2. In Poki wordt er ´e´en context tree van 13122 histogrammen bijgehouden. In Vexbot worden er naast deze context tree nog drie andere, geabstraheerde context trees met minder knopen bijgehouden. De grofste van deze abstracties bevat slechts 9 histogrammen. In de miximax-berekening wordt dan een gewogen gemiddelde gebruikt van deze context trees. Als de fijnste abstractie (d.w.z. geen abstractie) bijvoorbeeld 5 datapunten heeft voor een bepaalde showdown, dan krijgt het (1 − m5 ) van het gewicht, als de tweede abstractie 20 datapunten heeft krijgt het (1−m20 ) van het overblijvende gewicht, enz. De waarde m = 0.95 werd gebruikt in Vexbot. Hierdoor kan Vexbot veel nauwkeurigere beslissingen maken dan Poki als er nog maar weinig handen gespeeld zijn. Voor de acties van de speler te voorspellen wordt een zeer gelijkaardig model gebruikt, maar in plaats van histogrammen over de Hand Strength worden nu histogrammen over de mogelijke acties bijgehouden.
3.5
Counterfactual Regret Minimisation (CFRM)
Vexbot is in staat om PsOpti te verslaan. Dit komt voornamelijk doordat het aantal toestanden in de abstractie in PsOpti slechts O(107 ) bedraagt, waardoor het een redelijk grove abstractie is. Met een nauwkeurigere abstractie zou PsOpti sterker moeten zijn, maar het is niet eenvoudig om voor veel grotere abstracties het exacte Nash equilibrium te berekenen, aangezien de rekenkracht en het geheugen dat daarvoor nodig is zeer groot wordt. Daardoor hebben in 2007 M. Johanson et al. [8] een techniek bedacht genaamd Counterfactual Regret Minimisation (CFRM) die het Nash equilibrium iteratief kan benaderen. Deze techniek berekent geen exact Nash equilibrium, maar kan wel toegepast worden op veel grotere spellen, met tot O(1010 ) toestanden. Dit betekent dat men een abstractie kan gebruiken die veel dichter bij het echte spel aanleunt, waardoor het (benaderde) Nash equilibrium uit het abstract spel veel dichter bij het echte Nash equilibrium aanleunt. Dat het Nash equilibrium in een fijnere abstractie steeds overeenkomt met een strategie met kleinere exploitabiliteit in het echte spel is echter niet altijd waar. Er zijn gevallen waar het Nash equilibrium van een abstractie die in alle opzichten een strikte verfijning is van een andere abstractie toch meer exploiteerbaar is in het originele spel dan het Nash
3.6 Restricted Nash Response (RNR)
21
equilibrium van de grovere abstractie. Dit enigszins onintu¨ıtieve resultaat werd in 2009 aangetoond door Waugh et al. [18]. Wat voornamelijk de kwaliteit van een bucketing abstractie bepaalt is in welke mate strategisch gelijkaardige toestanden in dezelfde buckets terechtkomen. Het kiezen van welke toestanden in welke buckets terechtkomen is dus een belangrijke taak. De abstractie gebruikt in [8] maakt gebruik van Expected Hand Strength E[HS] (niet te verwarren met Effective Hand Strength EHS uitgelegd in sectie 3.1). Dit is de kans dat de hand die men heeft zal winnen tegen een willekeurig hand van de tegenstander na de river. Het is in andere woorden de verwachte Hand Strength na de river. Ook E[HS2 ] wordt gebruikt. Dit is de verwachte waarde van het kwadraat van de Hand Strength na de river. Dit kwadrateren heeft het effect dat handen die momenteel nog niet sterk zijn maar wel potentieel hebben om veel te verbeteren, zoals bijvoorbeeld handen die net geen flush vormen, een hogere score krijgen. De structuur van de abstractie is gelijkaardig aan die gebruikt door PsOpti: aan het begin van elke ronde, waar de E[HS] van elk hand dus verandert door de nieuwe kaarten die in het spel komen, worden alle toestanden ondergebracht in buckets op basis van hun E[HS2 ]. Deze buckets vormen een boomstructuur: er kunnen nooit twee toestanden in dezelfde bucket zitten die in de vorige ronde elk in een andere bucket zaten. De abstractie is dus een perfect recall abstractie. De CFRM-techniek is enkel bewezen om te convergeren naar het Nash equilibrium voor spellen met perfect recall, maar later werd empirisch aangetoond dat CFRM ook kan werken voor imperfect recall abstracties [19]. Deze techniek werkt bijzonder goed en was in staat om in 2007 in de Man-Machine Poker Competitie ongeveer gelijk te spelen tegen twee van de beste professionele pokerspelers [8]. CFRM wordt daarom gebruikt in zeer veel moderne poker-bots, en in de literatuur zijn er vele verbeteringen en varianten van de techniek voorgesteld en onderzocht. Aangezien deze technieken echter voornamelijk als doel hebben om dichter bij het Nash equilibrium te komen, en niet doen aan opponent modeling, worden deze hier niet besproken.
3.6
Restricted Nash Response (RNR)
Het berekenen van een strategie die een opgegeven strategie van de tegenstander σopp maximaal exploiteert is eenvoudig, en kan bijvoorbeeld gebeuren via de miximax techniek beschreven in sectie 3.2. Het probleem is echter dat deze maximaal exploitatieve strategie
22 steeds een pure strategie zal zijn, en dat deze counter-strategie bijgevolg zeer slecht zal presteren als de tegenstander het model σopp niet volledig volgt. Daarom is het nuttig om robuuste counter-strategie¨en te berekenen, die wel het model σopp van de tegenstander zullen proberen te exploiteren, maar zelf niet exploiteerbaarder zijn dan een bepaalde exploiteerbaarheid . De strategie¨en die uit de verzameling van alle strategie¨en met exploiteerbaarheid of minder het model σopp het meest exploiteren noemt men -safe counter-strategie¨en, en de CFRM-techniek kan gebruikt worden om zo’n strategie¨en te berekenen, als volgt: Er wordt een Nash-equilibrium berekend in een spel waarbij speler twee extra restricties krijgt: Met kans p moet speler twee de gemodelleerde strategie σopp volgen, en met kans 1 − p zijn strategie vrij kiezen. Het Nash equilibrium (σ1∗ , σ2∗ ) dat hieruit voortkomt heet een (p, σopp ) restricted Nash equilibrium. Hierbij is σ1∗ een p-restricted Nash Response (RNR) op strategie σopp . Door Johanson et al. is aangetoond dat als een strategie σ1 een p-RNR is voor een strategie σ2 , dat er dan een bestaat waarvoor σ1 een -safe best response is tegen σ2 [9]. Deze techniek werkt bijzonder goed, maar heeft wel twee nadelen: kan niet rechtstreeks gekozen worden, maar volgt uit de keuze van p. Indien men dus een -safe counter-strategie wenst te berekenen voor een vooropgestelde , dan moet men het algoritme steeds opnieuw uitvoeren met steeds een andere p om zo te binair te zoeken naar welke p er overeenkomt met de . De verhouding tussen p en is voor elke strategie verschillend. Voor grote abstracties moet het CFRM-algoritme uren tot dagen lopen voordat het convergeert naar het Nash equilibrium. Als men een constant veranderend model van de tegenstander heeft is het niet mogelijk om met deze techniek in een aantal seconden een RNR strategie te berekenen tegen dat model.
3.7
Data-Biased RNR (DBR)
De parameter p in het RNR algoritme kan gebruikt worden om een balans te vinden tussen exploitatie en exploitabiliteit: hoe meer men het model van de tegenstander σopp vertrouwt, hoe groter men p kan kiezen. Het kan echter gebeuren dat men een model van
3.8 Monte Carlo Tree Search (MCTS)
23
de tegenstander heeft waar men veel data heeft over hoe de tegenstander speelt in bepaalde situaties, maar veel minder in andere. Dan is er geen goede p die men kan kiezen. Als men een kleine p kiest, dan zal men de informatie die men heeft over de tegenstander niet ten volle benutten, en in de situaties waar men veel weet over de tegenstander nog steeds veilig spelen. Als men echter een grote p kiest, dan zal de counter-strategie de situaties waar er weinig data over is vlugger exploiteren dan de situaties waar veel data over is, aangezien het de gemodelleerde strategie in die minder voorkomende situaties meestal onnauwkeurig en zeer exploiteerbaar is. Daarom hebben Johanson et al. in 2009 een techniek voorgesteld, genaamd Data-Biased RNR (DBR), die de p vervangt door een functie Pconf dat voor elke informatieset afzonderlijk weergeeft hoe veel men het model van de tegenstander in die informatieset vertrouwt. Dit zorgt ervoor dat de counterstrategie geforceerd wordt om voornamelijk de situaties waar men relatief zeker is van de strategie van de tegenstander te exploiteren. In de informatiesets waar men weinig weet over de tegenstander veronderstelt men immers dat de tegenstander het Nash equilibrium zeer dicht benadert. DBR is een uitstekende techniek om een model van de tegenstander te exploiteren. Het enige grote nadeel is dat DBR, net zoals RNR, een berekening is van meerdere uren. Het is dus niet mogelijk om van een veranderend model van de tegenstander in real-time een exacte DBR-counterstrategie te berekenen.
3.8
Monte Carlo Tree Search (MCTS)
Het eerder besproken miximax algoritme is in staat om een boom van informatiesets te overlopen om de verwachte waarde van het spel in een toestand, gegeven een model van de tegenstander, te berekenen. In de pre-flop of de flop duurt het echter te lang om deze boom volledig te doorlopen. Daarom worden in Poki niet steeds alle subbomen overlopen, maar enkel een willekeurig gekozen sample ervan. Het is echter mogelijk om een nauwkeurigere schatting van de waarde van het spel in een toestand te krijgen door de samples niet uniform te verdelen over alle deelbomen maar om meer samples te geven aan de deelbomen die waarschijnlijker zijn om voor te komen. Dit kan gebeuren met een techniek genaamd Monte Carlo Tree Search (MCTS), die in spellen zoals Go reeds werd toegepast en leidde tot zeer sterke bots [10].
24 MCTS wordt echter doorgaans toegepast op spellen met perfecte informatie. In 2006 werd door G. Van Den Broeck et al. voor het eerst een variant op MCTS voorgesteld die ook kan werken op spellen met imperfecte informatie zoals poker [17]. Deze techniek heeft, net als miximax, een opponent modeling module nodig die voor elke beslissingsknoop van de tegenstander een distributie kan voorspellen van de mogelijke acties van de tegenstander. De opponent modeling module die gebruikt werd in [17] was een regressieboom waarbij de features steeds publiek zichtbare informatie zijn, zoals de grootte van de pot, de ronde, enz. Ook statistieken over de vorige spellen van de speler, zoals hoe vaak de speler gemiddeld gefold en geraised heeft, worden gebruikt als features. De regressieboom werd getraind met het Weka-M5P algoritme. Net als in miximax is er ook een model nodig dat in elke mogelijke showdown kan voorspellen wat de probabiliteit van elke hand van de speler is. Dit model was in Poki een histogram van de hand strengths die de tegenstander in die showdown reeds getoond heeft, en in Vexbot een gewogen gemiddelde van dergelijke histogrammen. In dit onderzoek werd hiervoor een regressieboom met dezelfde features als het actie-voorspellend model gebruikt.
3.9
DIVAT
Naast het berekenen van strategie¨en, modellen en counter-strategie¨en zijn er een aantal ´ en daarvan is als men andere problemen in poker die in de literatuur bestudeerd werden. E´ twee spelers een aantal spellen tegen elkaar ziet spelen, hoe men zo accuraat mogelijk kan schatten welke speler er beter is en hoe veel chips die speler gemiddeld per spel zou winnen tegen zijn tegenstander. Het doel is dus om een schatter te bouwen die zonder bias en met zo klein mogelijke variantie de verwachte winst van speler 1 in een spel tegen speler 2 schat. Uiteraard is de effectieve winst in een spel een goede schatter voor de verwachte winst. Maar het is niet de schatter met de kleinste variantie. Als men bijvoorbeeld de speler ziet all-in gaan op de turn, en de tegenstander callt, dan tonen beide spelers hun kaarten. Stel dat gelijkspel niet mogelijk is, dan kan men gemakkelijk berekenen wat de kans p is dat speler 1 de pot van K chips wint. In het spel zelf zal ´e´en van de twee spelers winnen, waardoor de effectieve winst ofwel K chips voor de ene of K chips voor de andere speler is. Een betere schatting voor de verwachte winst van speler 1 is echter (2p − 1)K chips.
3.9 DIVAT
25
Deze all-in situatie is echter maar een voorbeeld van een situatie waarin een betere schatter mogelijk is. In 2006 hebben Billings et al. een nieuwe schatter voorgesteld, genaamd Ignorant Value Assessment Tool (DIVAT), die het principe erachter veralgemeent [3]. Deze techniek vertrekt van een functie V die aan elke toestand een waarde toekent voor speler 1. Deze functie V mag alles zijn, maar er is aangetoond door Zinkevich et al. dat de schatter met laagste variantie wordt bereikt als V overeenkomt met de echte waarde van het spel in elke toestand [20]. In DIVAT komt de functie V overeen met de verwachte waarde van het spel als beide spelers een eenvoudige regelgebaseerde strategie zonder bluffen volgen. De schatter zelf werkt als volgt: vertrek van de effectieve winst of verlies die speler 1 gemaakt heeft, en voor elke toestand die tijdens het spel is voorgekomen waar er een kansgebeurtenis optrad (bvb. tonen van nieuwe kaarten op de flop), trek de advantage die speler 1 gekregen heeft in die toestand af. Deze advantage is het verschil tussen de verwachte waarde van V in alle mogelijke toestanden die konden volgen na de kansgebeurtenis, en de waarde van V na de gebeurtenis die in het spel is voorgekomen.
In het verlengde van dit onderzoek werd in 2008 door Bowling et al. een techniek voorgesteld die niet alleen kan schatten hoe veel een speler tegen een andere speler gemiddeld wint, maar ook kan schatten hoe veel een andere strategie zou winnen indien die strategie in de plaats zou spelen van ´e´en van de spelers [5]. Het heeft daarvoor echter welk vrij veel informatie nodig over hoe het oorspronkelijke spel gespeeld werd: Stel dat in de oorspronkelijke spellen speler A tegen speler B speelde, en er nu wil geschat worden hoe goed strategie σC zou werken tegen speler B. Daarvoor zijn niet alleen alle private kaarten van speler A nodig (ook als hij gefold heeft), maar ook in elke toestand waar A aan zet was moet geweten zijn welke kansdistributie speler A gaf aan elk van de mogelijke acties die hij kon nemen. Als elke situatie die σC wenst te spelen ooit is voorgekomen dan heeft de schatter geen bias.
26
Hoofdstuk 4 Generieke spelersmodellen Alle opponent modeling technieken besproken in het vorige hoofdstuk zijn zeer slecht in staat om de vele mogelijke interacties tussen de mogelijke private informatie van een speler en de publieke kaarten te modelleren. Neem als voorbeeld een tegenstander die een zeer hoge waarde hecht aan straights en niet zal twijfelen om te callen of te raisen met 4 van de 5 kaarten die nodig zijn om een straight te maken, maar anders vrij vlug foldt. Als men dit weet, dan kan men dit exploiteren door iets vaker te bluffen als een straight niet waarschijnlijk is en iets vaker te folden als een straight wel goed mogelijk is. Geen van de bestaande modellen is echter in staat om dit soort tegenstander te modelleren. De opponent modeling module in Poki en Vexbot beschouwen enkel publieke informatie zoals de grootte van de pot als features. Het is theoretisch gezien wel mogelijk om een ad-hoc heuristiek “kans op een straight” als feature toe te voegen, maar dat is een zeer moeilijk te defini¨eren feature. De kans dat een speler (bijna) een straight heeft voor gegeven publieke kaarten hangt immers sterk af van zijn pre-flop strategie. De HS-histogrammen in Poki en Vexbot zijn ook niet in staat om dergelijke interacties met de publieke kaarten te modelleren. De histogrammen geven wel een algemeen beeld over hoe waarschijnlijk de tegenstander is om bepaalde actiesequenties te doen voor kaarten met een hoog potentieel tegenover kaarten waarvan de waarde op de flop reeds relatief vast ligt, maar de histogrammen kunnen bijvoorbeeld geen verschil maken tussen straights en flushes. Er is dus nood aan een techniek die wel in staat is om een model van de tegenstander op te bouwen dat wel in staat is om de interacties tussen de mogelijke private kaarten van de
4.1 Gradient descent
27
tegenstander en de publieke kaarten, dat bijvoorbeeld wel het onderscheid kan herkennen tussen een straight draw en een flush draw. Dit is het doel van dit en het volgende hoofdstuk.
4.1
Gradient descent
Het doel is dus om een algemeen model van de strategie van de tegenstander te trainen op basis van een hand history. Dit zal gebeuren door te vertrekken van een willekeurige strategie en daarna deze strategie iteratief aan te passen om dichter en dichter bij de effectieve strategie van de tegenstander. Specifiek zal er gebruik gemaakt worden van gradient descent. Dit werkt als volgt: De modellen die we beschouwen hebben een aantal, stel K, re¨ele parameters, die op een bepaalde manier een statische strategie σw beschrijven. Anders uitgedrukt komt met elke mogelijke vector w van K re¨ele getallen een strategie σw overeen, op een manier die bepaald wordt door het model. Verschillende modellen kunnen een verschillend aantal parameters K hebben, dus deze K hangt af van model tot model. Om te kunnen dichter en dichter komen bij de effectieve strategie van de tegenstander moet er gebruik gemaakt worden van een maat Q die aangeeft hoe ver een bepaalde strategie staat van de strategie van de tegenstander. Dit is de foutfunctie, en het doel van gradient descent is om deze foutfunctie te minimaliseren. Deze foutfunctie Q is een re¨ele functie over w. Hoe lager Q(w), hoe beter de strategie σw overeenkomt met de observaties in de hand history. De manier waarop gradient descent dichter en dichter komt bij de beste parameters is door de “richting” te berekenen waarin w moet aangepast worden om Q(w) te verkleinen. Deze richting is formeel gedefini¨eerd als de vector ∇Q(w). Gradient descent vertrekt van een bepaalde w en zal dan telkens opnieuw w aanpassen in de richting van ∇Q(w). De grootte van de aanpassing die gradient descent in elke iteratie maakt wordt bepaald door de learning rate α. Concreet komt het er op neer dat in elke iteratie de volgende berekening gedaan wordt: w := w − α∇Q(w)
(4.1.1)
28 In andere woorden wordt voor elke k ∈ [1, K] tegelijk de volgende berekening wordt uitgevoerd: ∂Q(w) wk := wk − α (4.1.2) ∂wk De learning rate α speelt een zeer belangrijke rol in hoe snel gradient descent convergeert en hoe dicht het geraakt bij de optimale parameters. Met een te grote α zal het algoritme te grote stappen zetten en rondspringen in de parameterruimte en mogelijks zelfs niet convergeren. Met een te kleine α zal het algoritme zeer traag werken en veel iteraties nodig hebben om te convergeren. Merk op dat de ideale α sterk afhangt van de gebruikte foutfunctie Q: Q vermenigvuldigen met een constante c heeft hetzelfde effect als α vermenigvuldigen met c. De learning rate moet echter geen constante blijven doorheen het algoritme. Het is mogelijk om voor elke iteratie een andere learning rate te kiezen. Het kan zeer voordelig zijn om de learning rate initieel vrij hoog te houden om vlug tot een benaderde oplossing te komen, en dan de learning rate van iteratie tot iteratie te laten dalen om de convergentie te verbeteren. Het is ook mogelijk dat gradient descent vastgeraakt in lokale optima waar ∇Q(w) = 0 maar waar Q(w) toch niet minimaal is. Dan zit het algoritme vast en moet er opnieuw begonnen worden vanuit een andere w. Als de parameterruimte zulke lokale optima bevat moet er voorzichtig omgesprongen worden met het resultaat van de gradient descent en gecontroleerd worden of het resultaat geen lokaal optimum is. Keuze van de foutfunctie Het grote probleem dat nu overblijft is de keuze van deze foutfunctie Q. Er zijn twee eisen waaraan deze functie moet voldoen: De functie moet berekenbaar zijn in elk punt w ∈ RK en moet, als de hand history oneindig veel spellen bevat, minimaal zijn als σw gelijk is aan de strategie die gebruikt werd door de tegenstander. De parti¨ele afgeleide naar elke parameter ∂Q(w)/∂wk moet berekenbaar zijn in elk punt w ∈ RK .
Het feit dat er informatie ontbreekt in de hand histories maakt het vinden van een dergelijke foutfunctie niet eenvoudig. Er werd in deze thesis slechts ´e´en functie gevonden die voldoet aan alle eisen: de negatieve log likelihood dat de hand history voortgebracht werd door strategie σw .
4.1 Gradient descent
4.1.1
29
Log-likelihood
Als Xw een discrete stochastische variabele is waarvan de distributie afhangt van parameter w, dan is de likelihood functie een functie over w met als domein alle mogelijke waarden van Xw . De functie is gedefini¨eerd als: P (Xw = x). Dit is de kans dat X gelijk is aan x gegeven dat de parameter van X waarde w heeft. Dit is geen conditionele probabiliteit over w, aangezien w geen stochastische variabele is maar een parameter van X. Voor het opbouwen van een goede foutfunctie voor het trainen van modellen op hand histories beschouwen we nu alsof w de verzameling van parameters is van de modellen van alle spelers die meedoen aan ´e´en bepaald spel. Dan is σ w het strategieprofiel dat overeenkomt met deze w, en kunnen we als P (Xw = x) de kans beschouwen dat een spel waar de spelers σ w volgen hand history x voortbrengt. Uiteraard bestaat een normale hand history uit meer dan ´e´en spel, waarin sommige spelers enkel meedoen aan een deel van de spellen uit de hand history. Om de berekeningen niet overbodig complex te maken, maken we hier de veronderstelling dat alle spelers aan alle spellen meedoen. Daarbovenop zijn alle modellen die we hier beschouwen statisch, dus het strategieprofiel σ w geldt voor alle spellen in de hand history. Als we dus hand histories met meer dan ´e´en spel beschouwen, dan is de kans P (Xw = x) dat strategieprofiel σ w de hand history x met n spellen voortbrengt gelijk aan het product van de kansen dat de individuele spellen xi in de hand history werden voortgebracht door σ w , aangezien deze kansen onafhankelijk zijn van elkaar. In andere woorden: P (Xw = x) =
n Y
P (Xw,i = xi )
i=1
Gemiddelde negatieve log likelihood Om deze likelihood als foutfunctie te kunnen gebruiken moeten de parti¨ele afgeleiden van deze likelihood naar alle parameters kunnen berekend worden. Dit is echter niet eenvoudig doordat de likelihood een product van zeer veel termen is. Als we echter de log nemen van de likelihood, dan wordt het product een som, waardoor
30 het afleiden veel eenvoudiger wordt. De log likelihood wordt dan: log P (Xw = x) =
n X
log P (Xw,i = xi ).
i=1
Dit is veel eenvoudiger om af te leiden. En aangezien de log-functie een strikt stijgende functie is, heeft dit gebruiken van de log-functie geen verschil op de ligging van het punt waar de functie maximaal wordt. Er zijn nog twee andere kleine aanpassingen die kunnen gedaan worden voor we komen tot de uiteindelijke foutfunctie: 1. Aangezien in gradient descent de foutfunctie geminimaliseerd wordt in plaats van gemaximaliseerd, wordt de negatieve log likelihood genomen. 2. De totale negatieve log likelihood zal stijgen met elk spel dat men toevoegt aan de hand history. De waarde van de log likelihood zal dus sterk afhangen van n, het aantal spellen. Dit zou betekenen dat men de ideale learning rate α ook afhangt van n. Om dit te vermijden wordt de log likelihood gedeeld door n. Dit is de gemiddelde log likelihood. De uiteindelijke foutfunctie is dus: 1 Q(w) = − log P (Xw = x) n Berekenen van Q(w) Als een spel in een hand history xi geen gefolde handen bevat dan is het berekenen van P (Xw,i = xi ) zeer gemakkelijk. σ w beschrijft immers rechtstreeks met welke kans elk van de spelers de acties zouden doen die gedaan werden in de hand history, en de exacte history h die in het spel is voorgekomen is in dit geval gekend. De totale kans is dan een eenvoudige vermenigvuldiging van de kansen van de individuele gebeurtenissen en acties: w
P (Xw,i = xi ) = π σ (h) Als er in de hand history echter gefold werd, dan is er ontbrekende informatie. Als de private kaarten van een speler ontbreken dan tellen alle mogelijke private kaarten mee in de kans dat de hand history voorkomt. Als alle private kaarten ontbreken, en C de verzameling is van alle mogelijke manieren waarop de private kaarten verdeeld kunnen zijn over de spelers, dan herleidt de likelihood zich tot: X P (Xw,i = x) = P (c) P (Xw,i = xi | c) (4.1.3) c∈C
4.1 Gradient descent
31
Alle mogelijke combinaties van private kaarten die de spelers kunnen hebben worden dus overlopen, waarna de kans dat ze met die kaarten de hand history zouden voortbrengen direct volgt. Situaties waarbij enkel sommige spelers verborgen kaarten hebben (dit kan enkel met meer dan twee spelers) verlopen analoog. Berekenen van ∇Q(w) Het afleiden van deze foutfunctie naar elke parameter wk gebeurt als volgt: ∂ ∂ 1 Q(w) = − log P (Xw = x) ∂wk ∂wk n n 1X ∂ =− log P (Xw,i = xi ) n i=1 ∂wk
Elke term van deze som kan afzonderlijk afgeleid worden. ∂ log P (Xw,i ∂wk
∂ P (Xw,i = xi ) ∂wk = xi ) = P (Xw,i = xi )
(4.1.4)
Als de private kaarten van beide spelers in een spel xi gekend zijn, dan is dit eenvoudig te berekenen (zie verder). Als de private kaarten echter niet bekend zijn dan moeten alle mogelijke combinaties van private kaarten C overlopen worden:
=
∂ X P (c) P (Xw,i = xi | c) ∂wk c∈C P (Xw,i = xi )
De kans P (c) dat de spelers de combinatie van private kaarten c gekregen hebben hangt niet af van w, dus dit mag buiten de afgeleide gebracht worden: =
X c∈C
P (c) ∂ P (Xw,i = xi | c) P (Xw,i = xi ) ∂wk
Vermenigvuldig en deel nu met P (Xw,i = xi | c) ∂ X P (c) P (Xw,i = xi | c) ∂w P (Xw,i = xi | c) k = P (Xw,i = xi ) P (Xw,i = xi | c) c∈C =
X c∈C
P (c | Xw,i = xi )
∂ P (Xw,i = xi | c) ∂wk P (Xw,i = xi | c)
(4.1.5)
32 De linkerfactor in deze som is de kans dat de spelers private kaarten c hadden, gegeven dat ze de rest van het spel volgens xi gespeeld hebben en strategieprofiel σ w volgden. Deze is eenvoudig te berekenen door voor alle mogelijke handen te berekenen hoe waarschijnlijk ze waren om met dat hand het spel zo te spelen, en dan te hernormaliseren. P (c | Xw,i = xi ) = X
P (c) P (Xw,i = xi | c) P (c0 ) P (Xw,i = xi | c0 )
c0 ∈C
De rechterfactor in 4.1.5 is bijna hetzelfde als in 4.1.4, waar de berekening stopte voor spellen waar de private kaarten gekend zijn. Maar in 4.1.5 zijn de private kaarten ook gekend door het conditioneren op c. Alle berekeningen die nu volgen bouwen voort op 4.1.5, maar zijn compleet analoog voor 4.1.4 als alle private kaarten gekend zijn. Wat dus nog moet uitgewerkt worden in berekenbare termen is ∂ P (Xw,i = xi | c) ∂ ∂wk log P (Xw,i = xi | c) = P (Xw,i = xi | c) ∂wk Deze kans P (Xw,i = xi | c) is de kans dat strategieprofiel σ w het spel xi zou voortbrengen als alle spelers private kaarten c hadden. Aangezien de acties die genomen worden in elke toestand die tijdens het spel is voorgekomen kunnen beschouwd worden als onafhankelijke stochastische gebeurtenissen, kan deze kans herschreven worden als een product van de kansen van deze gebeurtenissen. Dit product wordt een som onder de log: ∂ X w log π σ (a | h) ∂wk h◦a∈x i X ∂ w = log π σ (a | h) ∂wk h◦a∈x =
(4.1.6)
i
Met de notatie h ◦ a ∈ xi worden hier alle histories h bedoeld die in spel xi voorgekomen w zijn waarna dan actie a werd genomen. π σ (a | h) is de kans op die actie volgens σ w , volgens de definities in sectie 2.1. w Van deze ∂/∂wk log π σ (a | h) vereisen we nu dat die kan berekend worden door het model. Dit blijkt geen al te grote beperking te zijn: alle modellen moeten reeds in staat zijn om voor elke h de probabiliteitsdistributie over A(h) te berekenen (aangezien ze σ w bepalen). Vele modellen zijn ook in staat om de parti¨ele afgeleiden van (de log van) deze distributie naar elke parameter te berekenen.
4.1 Gradient descent
33
Alle grootheden nodig om ∇Q(w) te berekenen zijn nu gekend. Onafhankelijke handen In de voorgaande berekeningen wordt er dikwijls gesommeerd over alle mogelijke combinaties van private kaarten c ∈ C. Dit is echter een zeer grote sommatie. Zonder met publieke kaarten rekening te houden zijn er 52 = 1326 mogelijke handen die een speler 2 kan hebben. Er zijn echter 52!/4 · 48! = 1624350 mogelijke manieren waarop de private ´ en iteratie van het gradient descent zou dus kaarten van 2 spelers kunnen verdeeld zijn. E´ zeer lang duren. Daarom is het een nuttige vereenvoudiging om aan te nemen dat de private kaarten van elke speler onafhankelijk zijn van de private kaarten van zijn tegenstanders. Dit is uiteraard geen correcte veronderstelling, maar het toelaten van de mogelijkheid dat een tegenstander mogelijks dezelfde private kaarten kan hebben zal slechts een klein effect hebben op de strategie¨en van de spelers. Als twee spelers immers dezelfde hand hebben, dan is het in elke mogelijke showdown gelijkspel en krijgen ze al het geld dat ze ingezet hebben terug. Het is maar in zeer specifieke situaties dat de mogelijkheid dat de tegenstander dezelfde private kaarten kan hebben een significant verschil zal uitmaken op de strategie¨en van een speler. De veronderstelling van onafhankelijke private kaarten maakt de berekeningen wel veel gemakkelijker. Als Ci de mogelijke private kaarten van speler i zijn dan kan vergelijking 4.1.3 X P (Xw,i = x) = P (c) P (Xw,i = xi | c) c∈C
vereenvoudigd worden tot =
X X
P (c1 , c2 ) P (Xw,i = xi | c1 , c2 )
c1 ∈C1 c2 ∈C2 w
≈ πcσ (xi )
X
c1 ∈C1
w
P (c1 ) π1σ (xi |c1 )
X
w
P (c2 ) π2σ (xi |c2 )
c2 ∈C2
w
waarin πjσ (xi |cj ) staat voor de kans dat speler j alle acties gedaan zou hebben van hand history xi als hij kaarten cj had. Dit hangt niet af van de kaarten van de tegenstander. Met dezelfde veronderstelling kan een analoge vereenvoudiging gedaan worden voor vergelijking 4.1.5.
34
4.1.2
Algemene methode
Het is nuttig om in woorden te herhalen en samen te vatten hoe nu juist de volledige berekening verloopt. Dit gebeurt als volgt: Een model heeft de volgende vereisten: Het moet met een vector van k re¨ele parameters w de strategie σw van een speler beschrijven. Dit betekent dat het model in staat moet zijn om (gegeven w) voor elke toestand h waar die speler aan zet is, een distributie te geven over de mogelijke acties A(h). Het moet kunnen berekenen in welke richting w moet aangepast worden om een actie a in toestand h waarschijnlijker te maken. Specifiek moet de parti¨ele afgeleide naar wk kunnen berekend worden van de log van de kans van die actie.
Het berekenen van de gemiddelde negatieve log likelihood van een hand history voor een model gebeurt als volgt: 1. Elk spel in de hand history wordt overlopen. Voor elk spel gebeurt de volgende berekening: 2. Voor elke speler afzonderlijk wordt berekend wat de kans is dat ze het spel zo gespeeld zouden hebben, als hun strategie de strategie beschreven door het model was: (a) Als de private kaarten van de speler gekend zijn dan is dit triviaal. (b) Als de private kaarten van de speler niet gekend zijn dan worden alle mogelijke private kaarten van die speler (die niet overlappen met de publieke kaarten) overlopen. De kansen dat de spelers met elk van die mogelijke kaarten zo zouden gespeeld hebben worden uitgemiddeld. 3. Deze kansen worden vermenigvuldigd tot de totale likelihood van het spel. 4. Deze likelihood wordt vermenigvuldigd met de kans op de zichtbare kaarten (publieke en zichtbare private kaarten).1 5. Hiervan wordt de negatieve log genomen. De gemiddelde negatieve log van deze likelihood over alle spellen is het resultaat van de berekening. 1
Deze stap kan beschouwd worden als optioneel, aangezien deze kansen niet afhangen van de parameters w van het model. Het verschil in log likelihood is slechts een constante die opnieuw niet afhangt van w.
4.1 Gradient descent
35
Het berekenen van de parti¨ ele afgeleiden van deze gemiddelde negatieve log likelihood naar elk van de parameters gebeurt als volgt: 1. Elk spel in de hand history wordt overlopen. Voor elk spel gebeurt de volgende berekening: 2. Voor elke speler wordt berekend hoe waarschijnlijk het is dat hij elk van de mogelijke private kaarten heeft als hij gespeeld zou hebben volgens het model, gegeven de observaties in de hand history. (a) Als het spel eindigde in een showdown dan is deze distributie triviaal. Er is dan immers maar 1 hand die de speler kan hebben. (b) Als de private kaarten van de speler niet genoteerd staan in de hand history dan worden alle mogelijke private kaarten die niet conflicteren met de publieke kaarten in de hand history overlopen. Er wordt gekeken met welke kans de speler die kaarten zo zou gespeeld hebben, waarna deze kansen genormaliseerd worden. Het resultaat is de kans dat ze die kaarten hadden in dat spel, volgens het model. 3. Elk van deze mogelijke private kaarten wordt nu overlopen, alle toestanden in het spel worden sequentieel overlopen. Aan het model wordt gevraagd om de parti¨ele afgeleiden naar alle parameters van de log likelihood dat het model geeft (met die private kaarten in die toestand) aan de actie die in de hand history genomen werd. 4. Deze parti¨ele afgeleiden worden vermenigvuldigd met de eerder berekende kans dat de speler aan zet die private kaarten heeft, en vervolgens gesommeerd. 5. Het gemiddelde hiervan over alle spellen is het vereiste resultaat. Merk op dat in de bovenstaande berekeningen het model geen model is van ´e´en van de spelers, maar van het volledige strategieprofiel. Als het doel is om enkel een model te trainen voor ´e´en van de spelers, dan is het eenvoudig om de berekening aan te passen om enkel te kijken naar de (mogelijke) private kaarten en acties van die ene speler. Het is ook mogelijk om de log likelihood van enkel de acties van ´e´en van de spelers te berekenen. Dit heet de log likelihood van een hand. De log likelihood van alle acties van alle spelers in een spel heet de log likelihood van het spel. Het trainen van een model van een speler op een hand history gebeurt zoals uitgelegd in sectie 4.1:
36 1. Er wordt gestart van een model met willekeurige parameters w. 2. De volgende berekening wordt herhaald voor een vast aantal iteraties: (a) De parti¨ele afgeleiden naar elke parameter van de log likelihood van de hand history voor de parameters w wordt berekend. (b) Deze afgeleiden worden vermenigvuldigd met een learning rate α en dan opgeteld bij de parameters w om nieuwe parameters te bekomen. 3. Dit wordt een aantal keer herhaald met andere startparameters. De configuratie van parameters met de kleinste negatieve log likelihood wordt onthouden. Dit is om te voorkomen dat het eindresultaat een lokaal minimum is dat ver van het globaal minimum ligt.
Dit geeft een methode die de parameters iteratief zal aanpassen om dichter en dichter te komen bij de echte strategie die gebruikt werd om de hand history voort te brengen. De iteraties van dit algoritme duren echter zeer lang, aangezien er voor elk spel in de hand history waar gefold werd alle 1326 mogelijke private handen moeten overlopen worden en het model voor elke actie 1326 keer moet ge¨evalueerd worden en 1326 keer moet gevraagd worden om parti¨ele afgeleiden te berekenen. Daarom wordt er in deze thesis gebruik gemaakt van een variant op gradient descent genaamd stochastic gradient descent. In plaats van per iteratie de hele hand history te overlopen worden de parti¨ele afgeleiden berekend voor mini-batches van ´e´en of een klein aantal willekeurig gekozen spellen uit de hand history. Dezelfde update gebeurt als in het gewone gradient descent, maar met een kleinere α. Het voordeel van deze methode is dat de iteraties veel kleiner zijn en de parameters veel vaker aangepast worden. Zeker voor grote hand histories versnelt dit de convergentie zeer veel. Een andere optimalisatie die het algoritme versnelt wordt besproken in sectie 4.1.7.
4.1.3
Gebruikte modellen
De voorgaande bespreking ging volledig over algemene modellen waar er twee eisen aan gesteld werden (zie sectie 4.1.2). De grote vraag die nu overblijft is welke modellen er voldoen aan deze vereisten en hoe goed ze in staat zijn om een speler te modelleren.
4.1 Gradient descent
37
De restrictie dat alle parameters re¨ele getallen zijn elimineert rechtstreeks een aantal modellen. Modellen waarvan de structuur getraind wordt, zoals regressiebomen, hebben discrete parameters die niet of zeer moeilijk om te zetten zijn in re¨ele parti¨eel afleidbare parameters. Daarnaast mag een model ook nooit een kans van exact 0 geven aan een actie die realistisch gezien wel kan voorkomen. Indien dit wel gebeurt, en de actie komt voor in een spel, dan is de negatieve log likelihood van dat spel ∞, waardoor de gemiddelde negatieve log likelihood van de hele dataset ∞ wordt. Modellen die een actie voorspellen in plaats van een distributie over de acties, zoals support vector machines (SVMs), zijn dus ook niet zonder aanpassingen bruikbaar. De modellen die wel bruikbaar zijn in de methode die in deze thesis besproken worden vallen te classificeren in twee categorie¨en: bucketing abstracties en neurale netwerken. Deze worden besproken in respectievelijk secties 4.1.4 en 4.1.5.
4.1.4
Bucketing abstractie
Het is nuttig om te kijken wat het eenvoudigste niet-triviale model is dat voldoet aan de vereiste eigenschappen van een model. Uiteraard voldoet een model zonder parameters dat telkens een uniforme distributie geeft aan de mogelijke acties ook aan de voorwaarden, maar dit is geen interessant model om te onderzoeken. Het eenvoudigste model negeert alle context van een toestand geeft aan elk van de drie mogelijke acties (fold, call en raise) dezelfde distributie in alle toestanden. Aangezien de derde kans uit de eerste twee kan berekend worden heeft dit model dus twee onafhankelijke parameters. Deze twee parameters geven we de naam f en c. Elke mogelijke combinatie (f, c) ∈ R2 moet een geldige strategie beschrijven. Dit gebeurt via een vorm van exponenti¨ele softmax, als volgt: Als alle drie de acties mogelijk zijn in de huidige toestand, dan is
ef ef + e c + 1 ec P (call) = f e + ec + 1 1 P (raise) = f e + ec + 1 P (f old) =
38 de distributie waar (f, c) mee overeenkomt. Merk op dat men dit kan beschouwen alsof er een derde parameter r is, waarbij de 1 in de bovenstaande berekeningen vervangen wordt door er , maar dat de parameters (f, c, r) steeds zo genormaliseerd worden dat r = 0. Het is immers zo dat in dat geval (f, c, r) dezelfde strategie beschrijft als (f + x, c + x, r + x). Men kan dan x = −r kiezen. Als slechts twee acties mogelijk zijn, dan is de berekening analoog als hierboven. Als het niet mogelijk is om te folden, dan is
ec P (call) = c e +1 1 . P (raise) = c e +1 Als het niet mogelijk is om te raisen, dan is ef ef + ec ec P (call) = f . e + ec
P (f old) =
Het is in elke positie mogelijk om te callen. Het komt nooit voor dat er minder dan twee acties mogelijk zijn in Heads-Up Limit Hold’em.
Dit model voldoet aan de eisen dat met elke combinatie van parameters (f, c) ∈ R2 een geldige strategie overeenkomt. In dit model zijn daarbovenop de strategie¨en uniek: er zijn geen twee combinaties van parameters die dezelfde strategie beschrijven. De tweede en laatste eis van het model is dat in elke toestand en elk punt (f, c) ∈ R2 de parti¨ele afgeleide van de log likelihood van een actie a naar elk van de parameters f en c kan berekend worden. Dit is inderdaad mogelijk, en verloopt als volgt: Als alle drie de acties mogelijk zijn, dan zijn er twee gevallen:
1. De parti¨ele afgeleide van de log likelihood van actie a naar de parameter die overeenkomt met a wordt berekend. Als bijvoorbeeld de parti¨ele afgeleide naar f van de log likelihood van folden berekend wordt, dan is het resultaat: ∂ ∂ ef log P (f old) = log f ∂f ∂f e + ec + 1 ef = 1− f e + ec + 1
4.1 Gradient descent
39
Het geval voor callen en de parameter c is volledig analoog. 2. De parti¨ele afgeleide van de log likelihood van actie a naar een parameter die niet overeenkomt met a wordt berekend. Als bijvoorbeeld de parti¨ele afgeleide naar f van de log likelihood van callen wordt berekend, dan is het resultaat: ∂ ∂ ec log P (call) = log f ∂f ∂f e + ec + 1 −ef = f e + ec + 1 De afgeleide naar f van de kans op raisen heeft dezelfde waarde. Het geval voor de parameter c verloopt opnieuw volledig analoog. Als er slechts twee acties mogelijk zijn dan zijn de berekeningen zeer gelijkaardig. Enkel het geval waar folden niet mogelijk is wordt hier besproken. Als dus de parti¨ele afgeleide naar c van de log likelihood van raisen berekend wordt, dan geeft dit:
∂ ∂ 1 log P (raise) = log c ∂c ∂c e +1 −ec = c e +1 De andere gevallen verlopen opnieuw volledig analoog. Het is duidelijk dat dit een zeer eenvoudig model is. Het geeft dezelfde distributie over de acties aan alle toestanden in het spel (op normalisatie na). Dit betekent echter niet dat het model volledig onbruikbaar is. Het kan nuttig zijn als primitieve bouwsteen voor complexere strategie¨en. Dit eenvoudige model wordt een bucket genoemd. Als voorbeeld van een complexere strategie kunnen sommige toestanden aan ´e´en bepaalde bucket toegekend worden en andere toestanden aan andere buckets. De distributie over acties die deze strategie dan geeft aan een toestand is de distributie die de toegekende bucket eraan geeft. Alle berekeningen van parti¨ele afgeleiden in een toestand worden ook gewoon doorgegeven aan de bucket die bij de toestand hoort. Dit soort strategie noemt men een bucketing strategie. De sterkte en het vermogen om spelers te modelleren van een bucketing strategie hangt zeer sterk samen met hoe veel buckets er zijn en hoe deze buckets worden toegekend. In technieken zoals CFRM ([8], sectie 3.5) wordt ook gebruik maken van een bucketing strategie om het volledige spel te vereenvoudigen naar een abstract spel waarvoor het
40 mogelijk is om het Nash equilibrium te berekenen of te benaderen. Het is het dus zeker nuttig om naar de literatuur te kijken welke bucketing abstracties er reeds ontwikkeld en onderzocht zijn. Het moet hierbij wel opgemerkt worden dat er een verschil is in de aard van de buckets, ook al bepalen ze beide een distributie over mogelijke acties: De buckets in CFRM komen overeen met een informatieset in het abstracte spel. Alle histories in een informatieset moeten voor de speler aan zet ononderscheidbaar zijn, dus de verzameling van acties die mogelijk zijn moet voor elke toestand in de informatieset dezelfde zijn. Dit betekent dat in dezelfde bucket steeds dezelfde acties mogelijk zijn. In de hierboven gedefini¨eerde buckets hoeft dat niet het geval te zijn. In CFRM is het mogelijk dat de bucket een kans 0 toekent aan ´e´en van de mogelijke acties. De hierboven gedefini¨eerde buckets gebruiken exponenti¨ele softmax en kunnen bijgevolg nooit een kans 0 geven aan een mogelijke actie.
De CFRM techniek is enkel wiskundig bewezen om te convergeren naar het Nash equilibrium als de gebruikte abstractie een perfect-recall abstractie is. Dit betekent dat er geen twee toestanden mogen zijn die in dezelfde bucket zitten maar in een vorige ronde van het spel elk in een andere bucket zaten. De meeste bucketing abstracties gebruikt in CFRM zijn bijgevolg een boomstructuur. De bucketing abstracties in deze thesis zijn niet gebonden aan die beperking en moeten geen boomstructuur vormen. In [19] is CFRM echter toegepast op abstracties met imperfect recall, waaruit empirisch bleek dat CFRM toch ook goed kan werken voor abstracties zonder perfect recall. Een belangrijk verschil met de CFRM-techniek is dat er slechts een beperkte hoeveelheid handen beschikbaar zijn om de buckets hun waarden te geven. Te veel buckets gebruiken zal leiden tot overfitting, te weinig buckets gebruiken zal leiden tot underfitting. Een hand history bestaat uit maximaal O(106 ) handen, maar als deze wordt verdeeld in een trainings- en een validatieset, en als deze later verdeerd worden onder de verschillende mixtures bij het mixture model in hoofdstuk 5, dan is O(105 ) een nauwkeurigere schatting van het aantal beschikbare datapunten. De bucketing abstractie zal dus ten hoogste O(104 ) buckets per ronde mogen bevatten. Aangezien de bucketing abstractie geen perfect recall-abstractie moet zijn, moeten de verdelingen van de buckets per ronde niet van elkaar afhangen. Het is nuttig om per
4.1 Gradient descent
41
ronde te beslissen hoe de buckets verdeeld worden. De precieze keuze van hoe veel buckets er per situatie worden gebruikt is minder belangrijk door de verder besproken optimalisatie waarbij buckets automatisch herordend worden. Pre-flop: In de pre-flop maken kleuren niet uit. Het maakt enkel uit of de private kaarten van dezelfde kleur zijn (suited) of niet. Er zijn 169 mogelijke situaties voor de flop. De meest logische keuze is dan om 169 buckets te gebruiken, ´e´en per hand. Er zijn 8 verschillende actiesequenties die binnen de pre-flop blijven. In totaal zijn er dus 169·8 = 1352 buckets op deze ronde. Flop: Er zijn 7 verschillende pre-flop actiesequenties die resulteren in een flop, en elk van deze sequenties kunnen gevolgd worden door 10 mogelijke actiesequenties die binnen de flop blijven. Er zijn dus 70 verschillende actiesequenties die eindigen in een toestand in de flop. Deze 70 situaties worden nu opgesplitst in elk 64 buckets, op basis van de E[HS2 ] zowel voor als na de flop, net als in [8]. Op basis van wat de E[HS2 ] was voor de flop worden alle handen onderverdeeld in 8 verzamelingen van toestanden met ongeveer evenveel handen in elke verzameling, waarna op basis van de E[HS2 ] na de flop deze verzamelingen verder opgesplitst worden in elk 8 buckets. Dit geeft 70 · 8 · 8 = 4480 verschillende buckets. Turn: Er zijn 7·9·10 = 790 verschillende actiesequenties die eindigen in een toestand in de turn. Dit is te veel om allemaal in afzonderlijke verzamelingen buckets op te splitsen. Daarom wordt er enkel gekeken naar de totale grootte van de pot op de turn. Deze bedraagt maximaal 32 big blinds op de turn. Deze 32 situaties worden elk opgesplitst in 5 · 5 · 5 buckets op basis van de E[HS2 ] voor de flop, op de flop en op de turn, analoog aan hoe dit gebeurt in de flop. Dit geeft 32 · 53 = 4000 buckets op de turn. River: De pot kan nu maximaal 48 big blinds bedragen. Deze 48 situaties worden op basis van de E[HS2 ] opgesplitst in 3 buckets voor elke ronde, analoog aan de flop en de turn. Dit geeft 48 · 34 = 3888 buckets.
Automatische herorganisatie van buckets Vele van deze buckets komen echter overeen met toestanden die zeer weinig voorkomen, terwijl andere buckets zeer vaak zullen voorkomen in een spel. De toestand waar de speler zwakke kaarten heeft en beide spelers checken zal bijvoorbeeld veel vaker voorkomen dan de toestand waarbij een speler met zwakke kaarten zal blijven raisen. Het is dus niet effici¨ent om de buckets uniform te verdelen over alle mogelijke toestanden.
42 Een mogelijke optimalisatie is dus om te trachten deze buckets te herverdelen zodanig dat een situatie die vaak voorkomt opgesplitst wordt in meer buckets en nauwkeuriger kan gemodelleerd worden, en om buckets die zelden voorkomen samen te nemen zodat er geen overfitting ontstaat. Dit kan gebeuren door het model zonder aanpassingen eerst te trainen op een hand history. Dit getrainde model beschrijft nu een strategieprofiel σ. Het is dan eenvoudig om te berekenen hoe waarschijnlijk een toestand of bucket voorkomt volgens dit strategieprofiel. Dit kan rechtstreeks gebruikt worden om de buckets te herordenen zodanig dat de kans op elke bucket meer uniform verdeeld is. De eenvoudigste optie is om enkel de laatste opsplitsing volgens E[HS2 ] te bekijken. Neem als voorbeeld de flop: daar worden elk van de 70 actiesequenties volgens de E[HS2 ] van voor de flop verdeeld in 10 verzamelingen van toestanden, die dan elk opgesplitst worden in 10 buckets volgens de E[HS2 ] op de flop. Maar als men kan berekenen hoe waarschijnlijk de verzameling van toestanden voorkomt, dan kan men de verzameling in meer of minder buckets opsplitsen. De vraag is nu: in hoe veel buckets moet een verzameling van toestanden opgesplitst worden? Door het aantal spellen in de hand history te vermenigvuldigen met de kans om de verzameling toestanden te bereiken kan men schatten hoe veel spellen er ongeveer effectief die toestand bereiken. Als men verwacht om ongeveer k spellen nodig te hebben om een bucket voldoende te trainen, dan kan men het aantal buckets instellen op 1/k van het verwachte aantal spellen. De optimale waarde van deze k wordt onderzocht in sectie 6.2.2. Het minimum en maximum aantal clusters waarin een verzameling toestanden kan worden opgesplitst wordt ingesteld op respectievelijk 1 en 30. Met deze herordening van buckets geeft dit een ander model dat opnieuw moet getraind worden. Dit model zal na trainen iets nauwkeuriger zijn dan het vorige, en kan opnieuw gebruikt worden om de kans op elke toestand te berekenen. Dit zal echter slechts een zeer klein verschil opleveren, en dit wordt in deze thesis daarom niet gedaan.
4.1.5
Neurale netwerken
Een ander soort modellen dat onderzocht wordt in deze thesis is het artifici¨ele neurale netwerk (ANN). Dit is een vrij populaire methode die reeds zijn nut bewezen heeft in poker-bot zoals Poki (zie sectie 3.1 en 3.2). Ze hebben als voordeel dat ze niet-lineaire functies van de invoer kunnen leren, en dat ze opgebouwd zijn uit lagen waarbij elke laag
4.1 Gradient descent
43 Invoerlaag
Verborgen Verborgen laag 1 laag 2
Uitvoerlaag
Feature #1 Uitvoer #1 Feature #2 Uitvoer #2 Feature #3
Figuur 4.1: Voorbeeld van een neuraal netwerk potentieel complexere eigenschappen van de invoer en de vorige lagen kan modelleren. Werking van neurale netwerken Een neuraal netwerk is opgebouwd uit meerdere neuronen, onderverdeeld in lagen gaande van laag 1, de invoer-laag, tot laag L, de uitvoer-laag. Figuur 4.1 geeft een voorbeeld van een neuraal netwerk met 4 lagen. Als aan het neuraal netwerk invoer wordt aangelegd, dan worden alle neuronen in de invoer-laag in een bepaalde mate geactiveerd, waarna de neuronen in de volgende laag geactiveerd worden, enzovoort. Tussen elke paar neuronen in twee opeenvolgende lagen is er een verbinding. Het gewicht van de verbinding tussen neuron i in laag j en neuron k in laag j + 1 wordt genoteerd als (j) θi,k . Dit gewicht geeft aan in welke mate de activatie van de eerste neuron bijdraagt aan de activatie van de tweede. Deze gewichten kunnen negatief zijn: een grote activatie van de eerste neuron zal dan de activatie van de tweede neuron tegenwerken. (j)
De activatie van de i-de neuron van laag j wordt genoteerd als ai . Voor de invoer-laag is (1) ai gelijk aan de waarde van feature i. Als de activaties van laag j gekend zijn kunnen de activaties van laag j + 1 als volgt berekend worden: ! X (j+1) (j) (j) ai =g θk,i ak k
De functie g hierin is de actievatiefunctie. Deze functie zorgt voor de niet-lineariteit tussen de invoer en de uitvoer. Een activatiefunctie wordt meestal zo gekozen dat het gedrag rond x = 0 ongeveer lineair is, maar voor zeer grote invoer de functie platter en platter wordt en binnen bepaalde grenzen blijft. Veelgebruikte activatiefuncties zijn de
44
0.9 0.5
0.7
−4
−2
2 0.3
4
−4
−2
2
4
−0.5
0.1
(a) Logistische functie
(b) tanh(x)
Figuur 4.2: Twee veelgebruikte activatiefuncties logistische functie
1 1 + e−x en de functie tanh(x) (zie figuur 4.2). Het is mogelijk om verschillende activatiefuncties te kiezen voor elk van de verschillende lagen, of zelfs voor elk van de individuele neuronen. Er worden meestal ook een bias unit toegevoegd aan elke laag behalve de uitvoer-laag. Dit is een neuron die steeds de waarde 1 heeft. Het gewicht van de verbinding tussen de bias (j) neuron van laag j en neuron i van laag j +1 wordt genoteerd als θ0,i . Er zijn uiteraard geen verbindingen naar de bias neuronen, maar voor de rest kunnen deze neuronen beschouwd worden als normale neuronen. Neuraal netwerk als strategiemodel Om bruikbaar te zijn in de gradi¨ent descent methode moet het model voldoen aan de volgende voorwaarden (zie sectie 4.1.2): 1. In elke mogelijke toestand van het spel moet het model een probabiliteitsdistributie kunnen produceren over de mogelijke acties zodanig dat de kans van een mogelijke actie nooit 0 of 1 is. 2. De parti¨ele afgeleiden van de log likelihood naar elk van de modelparameters van een arbitraire actie in een arbitraire toestand moeten kunnen berekend worden. De voorwaarde dat de kans op een actie nooit exact 0 of 1 mag zijn is geen probleem voor een normaal neuraal netwerk. Als qua activatiefunctie bijvoorbeeld de logistische functie gebruikt wordt dan is kan de uitvoer van geen enkele neuron 0 of 1 zijn.
4.1 Gradient descent
45
Om echter een probabiliteitsdistributie te vormen moeten de kansen sommeren tot 1. De meest natuurlijke manier om dit te doen is met het gebruik van de softmax activatiefunctie. Dit vervangt de activatiefunctie in de laatste laag. Normaal werkt een activatiefunctie van een neuron enkel op dat neuron, maar de softmax-functie S werkt in op de hele laag tegelijk. Als xi de waarde van neuron i is voordat de activatiefunctie toegepast wordt dan is exi Si (x) = P xj je
de waarde van neuron i na toepassen van de activatiefunctie. Deze softmax zorgt ervoor dat de uitvoer een probabiliteitsdistributie vormt. Aan de eerste voorwaarde is dus voldaan. Berekenen van parti¨ ele afgeleiden (j) De parameters van een neuraal netwerk zijn de gewichten θi,k van de verbindingen. Het zijn deze gewichten die bepalen wat de uitvoer van het netwerk is. Dit zijn dus de parameters die we willen trainen via de gradient descent methode. Om dit te kunnen doen moeten de parti¨ele afgeleiden naar elke parameter van de log likelihood van elke actie berekend kunnen worden. Dit gebeurt als volgt: De log van de kans die het neuraal netwerk met n features en m parameters geeft aan een positie met features x en parameters θ kan beschouwd worden als een functie F (x, θ) ∈ Rn+m → R3 . Deze functie kan op zich beschouwd worden als een concatenatie van twee functies: F =Q◦N De functie N ∈ Rn+m → R3 hierin is het neurale netwerk zonder softmax, dus met lineaire outputs. De functie Q ∈ R3 → R3 is de log van de hierboven beschreven softmax. De gezochte parti¨ele afgeleiden zijn dan ∂/∂θi Fj (x, θ) voor elke i, j, x en θ. Dit is het rechterdeel van de jacobiaan van F : ∂F1 ∂F1 ∂F1 ∂F1 · · · · · · ∂x1 ∂xn ∂θ1 ∂θm . . . .. . . .. .. .. .. J(F ) = .. . ∂F3 ∂F3 ∂F3 ∂F3 ··· ··· ∂x1 ∂xn ∂θ1 ∂θm Deze jacobiaan kan berekend worden via de kettingregel voor functies van meerdere veranderlijken Jx (f ◦ g) = Jg(x) (f ) Jx (g)
46 Hierin staat Jx (f ) voor de jacobiaan van f ge¨evalueerd in punt x. Merk op dat om een element van Jx (f ◦ g) in kolom i te berekenen enkel de waarden van kolom i uit Jx (g) nodig zijn. Dit betekent dat om een afgeleide van F naar een parameter te berekenen geen afgeleiden van N naar de features nodig zijn. De kettingregel staat geschreven in termen van matrices. Het kan duidelijker zijn om deze te herschrijven in termen van de elementen van de matrices: 3 X ∂ ∂ ∂ Fj (x, θ) = Qj (N (x, θ)) Nk (x, θ) ∂θi ∂Nk (x, θ) ∂θi k=1
(4.1.7)
Het berekenen van de parti¨ele afgeleiden ontbindt zich dus in twee delen: 1. Het berekenen van hoe de foutfunctie Q verandert met zijn k-de argument. Deze berekeningen zijn analoog aan deze voor de exponenti¨ele softmax voor buckets in sectie 4.1.4. ∂ exj ∂ Qj (x) = log P xi ∂xk ∂x ie k 1 − Pexkx als j = k i ie d= − e xk P als j = 6 k e xi i
2. Het berekenen van hoe uitvoer k van het netwerk verandert met parameter θj . Dit kan gebeuren met het backpropagatie-algoritme beschreven in [15]. Dit algoritme werkt door de “fout” in activatie te berekenen in de uitvoer-laag (waar de huidige en gewenste uitvoer gekend zijn), en deze fout telkens voor de vorige lagen te berekenen en achterwaarts te laten propageren door het netwerk. Deze fout in elke neuron kan gebruikt worden om de parti¨ele afgeleiden van de gewichten van de verbindingen te berekenen. Op deze manier kunnen de gewenste parti¨ele afgeleiden dus berekend worden en kan het gradient descent algoritme uitgevoerd worden. In de voorgaande discussie werd steeds impliciet aangenomen dat alle drie de acties mogelijk waren. De situaties waar er slechts twee acties mogelijk zijn zijn echter volledig analoog. De term die hoort bij de onmogelijke actie verdwijnt dan gewoon telkens uit de noemer, en uit de som in 4.1.7. Features
4.1 Gradient descent #
Type
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R R 0/1 0/1 0/1 0/1 0/1 0/1 0/1 R 0/1 0/1 0/1 R R 0/1 0/1 0/1
47 Beschrijving Pot odds (zie sectie 3.1) Bet ratio: #bets / (#bets + #calls) Heeft deze ronde chips ingezet 1 bet te callen Meer dan 1 bet te callen Het is de turn Het is de river De laatste actie van de speler was een call De laatste actie van de speler was een bet of raise 0.1 ∗ aantal spelers in het spel Er zijn nog 2 spelers in het spel De speler is eerst aan zet De speler is laatst aan zet Geschatte Hand Strength van de tegenstander (zie sectie 3.1) Geschatte Hand Potential van de tegenstander (zie sectie 3.1) Regelgebaseerd systeem voorspelt call Regelgebaseerd systeem voorspelt raise Poki speelt mee en heeft nog niet gefold
Tabel 4.1: Features gebruikt voor het neurale netwerk in Poki Zoals bij de meeste modellen speelt de gebruikte invoer een zeer belangrijke rol in de prestaties van het model. Met slechte inputs zal een neuraal netwerk de spelers niet goed kunnen voorspellen. Het is dus belangrijk om goede features te kiezen. In Poki (beschreven in sectie 3.2) werden ook reeds neurale netwerken gebruikt. De 18 features die daar als invoer gebruikt werden zijn weergegeven in tabel 4.1 [6, p. 41-42]. Sommige van deze features zijn niet zinvol in heads-up limit poker, zoals feature 9 en 10 die het aantal spelers encoderen. De rest van de features encoderen voornamelijk de acties van de spelers, er wordt bij het berekenen van de features amper gekeken naar de publieke kaarten. In de MCTS-bot beschreven in sectie 3.8 werden features toegevoegd die statistieken over het voorbije gedrag van de speler encoderen, zoals de frequentie waarmee de speler gefold en geraised heeft in de voorbije spellen. Dit is reeds een vorm van specifieke opponent modeling. In dit hoofdstuk wordt echter verondersteld dat alle handen gespeeld worden
48 door dezelfde strategie, waardoor deze feature niet zinvol is. Specifieke opponent modeling wordt beschreven in hoofdstuk 5. De features in de MCTS-bot worden echter opnieuw voornamelijk bepaald door de acties van de spelers, en bevatten de features zeer weinig informatie over de publieke kaarten. In deze thesis werden uit de features van deze twee bots de volgende features geselecteerd als nuttige features voor heads-up limit Texas Hold’em: De pot odds. Dit is feature 0 uit tabel 4.1. De bet ratio: #bets / (#bets + #calls). Dit is feature 1 uit tabel 4.1. De speler heeft deze ronde chips ingezet. Dit is feature 2 uit tabel 4.1. De speler heeft gedurende het volledige spel reeds een bet of raise gedaan. De speler heeft na de flop reeds een bet of raise gedaan. De tegenstander heeft deze ronde een bet of raise gedaan. Dit is feature 3 uit tabel 4.1. De laatste actie van de speler was een bet of raise. Dit is feature 8 uit tabel 4.1. De speler is eerst aan zet. Dit is feature 11 uit tabel 4.1. Het aantal small blinds in de pot ∗ 0.1.
Deze features encoderen de publiek zichtbare informatie. Merk op dat deze features geen informatie bevatten over de publieke kaarten. Het is immers moeilijk om deze informatie om te zetten in nuttige features. Met de technieken uit dit hoofdstuk kunnen echter modellen getraind worden die ook private informatie als features encoderen, wat veel expressievere features geeft: De speler heeft een private kaart die ook op de tafel ligt (in een andere kleur). Dit betekent dat de speler minstens een paar heeft. In pokertermen noemt men de hand “connected”. De speler heeft “top pair”: zijn hand heeft verbonden met de hoogste publieke kaart.
4.1 Gradient descent
49
De speler heeft een “flush draw”: De speler heeft nog maar 1 kaart nodig om een flush te vormen. De speler heeft een “straight draw”: De speler heeft nog maar 1 kaart nodig om een straight te vormen. De speler heeft een “open ended straight draw”: De speler heeft 4 kaarten op een rij. De speler heeft de best mogelijke “kicker”: De speler heeft de hoogste kaart die niet op tafel ligt. De speler heeft een pocket pair die hoger is dan elke publieke kaart. De speler heeft een pocket pair maar er is een publieke kaart die hoger is. De speler heeft three-of-a-kind. De speler heeft 2 pair. De speler heeft een straight. De speler heeft een flush. De speler heeft een full house of beter. E[HS] en E[HS2 ] van de huidige en alle voorgaande ronden worden gezien als feature. Op de river is E[HS] = HS en E[HS2 ] = HS2 . Enkel HS wordt dan gebruikt als feature. De E[HS] van de speler is verbeterd ten opzichte van de vorige ronde.
De bovenstaande features encoderen de relatie van de hand ten opzichte van de publieke kaarten. Informatie over de hand van de speler zelf kan echter ook nuttig zijn: De hoogste private kaart van de speler wordt als een re¨eel getal ge¨encodeerd, als volgt: Een aas is 1, een koning is 10/11, een dame is 9/11, ..., een twee is 0. De laagste kaart wordt op dezelfde manier ge¨encodeerd.
´ en van de twee private kaarten van de speler is een aas. E´ De hand van de speler is “suited”. Dit wil zeggen dat de private kaarten van dezelfde kleur zijn.
50 De speler heeft een “pocket pair”. Dit wil zeggen dat de private kaarten van de speler een paar vormen.
Merk op dat geen van de bovenstaande features encodeert in welke ronde van het spel de speler zich bevindt. Dit komt omdat het gedrag van spelers dikwijls van ronde tot ronde veel verandert. Op de flop zijn handen met een hoog potentieel, zoals flush of straight draws, relatief waardevol. Men kan een “semi-bluff” doen, waarbij als de bluff mislukt er nog een turn- en riverkaart komen die de hand kunnen vervolledigen. Op de river is een draw waardeloos en weegt de rechtstreekse hand strength veel meer door. Ook de waarden van de features hangen sterk af van de ronde. E[HS] ligt voor de flop bijvoorbeeld meestal tussen 0.3 en 0.7, terwijl E[HS] op de river ongeveer uniform verdeeld is tussen 0 en 1. De grootte van de pot is een ander voorbeeld van een feature waarvan de betekenis sterk afhangt van de ronde. Daarnaast heeft de river ook meer features dan de flop (de E[HS] en E[HS2 ] van alle vorige ronden). Daarom wordt er per ronde een ander neuraal netwerk met andere parameters gebruikt. In de pre-flop wordt een bucketing strategie met 169 buckets gebruikt, ´e´en voor elke mogelijke hand, per actiesequentie die binnen de pre-flop blijft. Dit zijn 169·8 = 1352 buckets in totaal. Op de flop heeft het netwerk 32 features, op de turn 34 en op de river 35.
4.1.6
Gewogen gemiddelde van modellen
In de voorgaande secties kwam ´e´en informatieset I steeds overeen met ´e´en model, zij het een bucket of een neuraal netwerk. Het is echter mogelijk om met een informatieset een distributie toe te kennen over N modellen of buckets. Stel dat pi (I) staat voor het gewicht van model i in informatieset I, en θ staat voor de vector van parameters van deze modellen samen. De modellen kunnen sommige parameters delen of de modellen kunnen elk hun eigen parameters hebben. Dan kan de likelihood dat model i geeft aan een actie a (i) beschouwd worden als een functie fa (I, θ). De likelihood die dit model dan geeft aan actie a in informatieset I is N X
pi (I) fa(i) (I, θ)
i=1
Om dit model te kunnen gebruiken in de gradient descent methode moeten de parti¨ele afgeleiden van de log likelihood van elke actie naar elk van de parameters θk kunnen
4.1 Gradient descent
51
berekend worden. Dit gebeurt als volgt:
N X ∂ log pi (I) fa(i) (I, θ) ∂θk i=1
!
=
N ∂ X pi (I) fa(i) (I, θ) ∂θk i=1 N X
pj (I) fa(j) (I, θ)
j=1
=
N X
pi (I)
i=1 N X
∂ (i) f (I, θ) ∂θk a
pj (I) fa(j) (I, θ)
j=1
=
N X
pi (I) fa(i) (I, θ)
i=1
N X
∂ log fa(i) (I, θ) ∂θk
pj (I) fa(j) (I, θ)
j=1
(i)
(i)
De grootheden fa (I, θ) en ∂/∂θk log(fa (I, θ)) hierin kunnen berekend worden door model i. Dit zijn immers respectievelijk de likelihood van een actie in een informatieset I en de parti¨ele afgeleiden van de log likelihood van een actie, die elk model moet kunnen berekenen. Een vraag is nu hoe de gewichten van de modellen in elke informatieset, pi (I) gekozen moeten worden. Het is uiteraard mogelijk om de gewichten voor alle informatiesets gelijk te kiezen. Het model is dan een eenvoudig gewogen gemiddelde van deelmodellen. In de bucketing abstracties gedefini¨eerd in sectie 4.1.4 werd gebruik gemaakt van E[HS2 ] om gelijkaardige handen in dezelfde bucket te steken. De E[HS2 ]-waarden van de grenzen tussen buckets worden zodanig berekend dat er ongeveer evenveel handen in elke cluster zitten. Dit is een harde clustering: handen die in dezelfde bucket terechtkomen krijgen exact dezelfde probabiliteitsdistributies toegekend. De handen die op de grens tussen twee buckets liggen zullen hierdoor iets minder nauwkeurig voorspeld worden. Een eenvoudige manier om dit te verbeteren is om gebruik te maken van lineaire interpolatie tussen buckets. In plaats van de grenzen worden de E[HS2 ]-waarden van de middelpunten van de buckets berekend, en een hand wordt toegekend aan de twee buckets waar het tussen
52 ligt, proportioneel volgens hoe dicht het ligt bij elk van de twee clusters. Dit is een vorm van “zachte” clustering. Het is ook mogelijk om het gewicht van model i in informatieset I, pi (I) te laten afhangen van de parameters θ. De parti¨ele afgeleiden kunnen dan nog steeds berekend worden. Dit leidt tot een soort meta-model waarbij de deel-modellen individueel leren om de acties van de speler te voorspellen, en het meta-model leert welk van de modellen in welke informatiesets het meest nauwkeurig is. Dit werd in deze thesis echter niet verder onderzocht.
4.1.7
Optimalisatie: hand hashes
Telkens als de private kaarten van een speler niet gekend zijn, dan zullen in de berekening van de log likelihood of de parti¨ele afgeleiden van de log likelihood alle mogelijke private kaarten moeten overlopen worden. Er zijn zo 52 = 1326 mogelijke handen die moeten 2 overlopen worden, en zelfs als men de handen excludeert die conflicteren met de publieke kaarten dan blijven er nog steeds O(103 ) handen over. Voor elke van deze mogelijke handen moet het model ge¨evalueerd worden, wat voor een neuraal netwerk bijvoorbeeld vrij traag is. Er is een manier om het model voor minder handen te moeten evalueren. Dit zal uitgelegd worden aan de hand van een voorbeeld. Stel dat de publieke kaarten K♠ 6♥ 6♠ zijn. Elke rationele speler zal de handen A♦ 3♠ en A♣ 3♠ op identiek dezelfde manier spelen. Er kan dus verondersteld worden dat zowel het probabiliteitstriple als alle parti¨ele afgeleiden in beide situaties hetzelfde zijn, waardoor het model maar voor 1 van de twee situaties moet ge¨evalueerd worden. Dit kan veralgemeend worden: als twee situaties enkel verschillen op een rotatie van kleuren na, dan zijn de probabiliteitstriples en parti¨ele afgeleiden in beide situaties gelijk. Deze moeten dan enkel voor 1 situatie ge¨evalueerd worden en kunnen hergebruikt worden in de andere situaties. Om dat te kunnen doen moeten de probabiliteitstriples en parti¨ele afgeleiden echter opgeslagen worden op zo’n manier dat ze effici¨ent kunnen opgezocht worden voor nieuwe situaties die enkel op een rotatie van kleuren verschilt. Dit kan met behulp van een hash tabel waarbij:
4.2 Gebruik van het model
53
Als twee situaties op een rotatie van kleuren na gelijk zijn, dan moeten de hashes van beide situaties gelijk zijn. Als twee situaties na een rotatie van kleuren verschillend zijn, dan moeten de hashes verschillend zijn, tenzij er een hashcollisie optreedt.
Een dergelijke hash kan berekend worden door een hash te berekenen van de kaarten van elke kleur, en dan deze 4 hashes op te vermenigvuldigen. Door de commutativiteit van de vermenigvuldiging zullen twee situaties die op een rotatie van kleuren na gelijk zijn dezelfde hash krijgen. In de hashes van de kaarten van elke kleur moet er wel onderscheid gemaakt worden tussen welke kaarten privaat en welke kaarten publiek zijn. De volgorde van de private kaarten maakt echter niet uit, en moet dus eerst genormaliseerd worden (bijvoorbeeld geordend van groot naar klein). In het bovenstaande voorbeeld wordt de hash dan berekend als volgt: hash = h(“3|K6”) · h(“A|”) · h(“|6”) · h(“|”) mod 264 Hierin is h(s) een functie die een string s hasht naar een getal in [0, 264 [. Er moet nu nog geschat worden wat de kans op een ongewenste hash-collisie is. Er zijn maximaal 1326 verschillende situaties die moeten overlopen worden. Als dit allemaal verschille situaties zijn (ook na rotatie van kleuren) dan is de kans dat twee verschillende situaties dezelfde hash hebben ongeveer 1326 · 1325 = 4.76222 · 10−14 64 2·2 Een hashcollisie zal dus uiterst zelden optreden.
4.2
Gebruik van het model
De methode die in dit hoofdstuk werd voorgesteld is in staat om een model van de strategie van een speler op te bouwen. Deze strategie geeft aan elke mogelijke informatieset een kans over de acties die mogelijk zijn in die toestand. Als er echter tegen een tegenstander gespeeld wordt, en men wil het model gebruiken om de actie van de tegenstander te voorspellen, maar dan weet men niet in welke informatieset de tegenstander zich bevindt. Dit kan echter als volgt berekend worden:
54 Stel dat men zelf speler 1 is en men de actie van speler 2 wil voorspellen. De private kaarten c1 zijn uiteraard gekend, evenals de acties die reeds gebeurd zijn en publieke kaarten, samen genoteerd als x. Als ook nog de kaarten van speler 2, c2 , gekend zijn dan komt met al deze informatie een unieke history hc1 ,c2 ,x overeen. De kans dat de speler nu actie a neemt is P (a | x, c1 ) =
X
P (c2 | x, c1 ) P (a | x, c1 , c2 )
c2
=
X c2
=
X c2
=
X c2
P (x | c1 , c2 ) P P (a | x, c1 , c2 ) 0 c0 P (x | c1 , c2 ) 2
π σ (h ) P σ c1 ,c2 ,x π σ (a|hc1 ,c2 ,x ) 0 c0 π (hc1 ,c2 ,x ) 2
) )π σ (h π σ (h P 2 σ c1 ,c2 ,x −2 σ c1 ,c2 ,x π σ (a|hc1 ,c2 ,x ) 0 0 π (h )π (h ) 0 c1 ,c2 ,x −2 c1 ,c2 ,x 2 c 2
σ σ (hc1 ,c02 ,x ) voor elke c02 aangezien de beslissingen van de andere (hc1 ,c2 ,x ) = π−2 Hierin is π−2 spelers en de publieke kaarten niet afhangen van de private kaarten van speler 2.
=
X c2
) π σ (h P 2 σ c1 ,c2 ,x π σ (a|hc1 ,c2 ,x ) 0 (h ) π c1 ,c2 ,x c0 2
(4.2.1)
2
Alle grootheden in de bovenstaande formule kunnen berekend worden en hangen enkel af van de strategie van speler 2. In woorden verloopt de berekening als volgt: Alle mogelijke private kaarten van speler 2 worden overlopen, en aan het model wordt gevraagd wat de kansen zijn dat speler 2 de geziene acties zou gedaan hebben met elk van de mogelijke kaarten. Dit geeft (na normalisatie) de kans dat speler 2 die kaarten heeft. Nu wordt aan het model gevraagd wat de kans is dat de speler actie a zou nemen als hij die kaarten zou hebben. Deze kansen worden gewogen met de kans dat de speler die kaarten heeft.
4.3
Andere optimalisatiemethoden
In dit hoofdstuk werd gebruik gemaakt van gradient descent en stochastic gradient descent. Om dit mogelijk te maken was het nodig om voor elke mogelijke combinatie van parameters
4.4 Conclusie
55
de foutfunctie te kunnen evalu¨eren en de parti¨ele afgeleiden van de foutfunctie naar elk van de parameters te kunnen berekenen. Er zijn echter een hele reeks methoden die de parameters van een model kunnen optimaliseren en daarbij enkel deze twee dingen nodig hebben. Er kan bijvoorbeeld gebruik gemaakt worden van een momentum-term in de update-regel. Deze zorgt ervoor dat de parameterupdates een “snelheid” krijgen die in sommige gevallen de convergentie van het algoritme kan verbeteren. Andere methoden zoals BFGS schatten de tweede-orde parti¨ele afgeleiden van Q naar elk mogelijk paar van parameters en gebruiken dit om nauwkeurigere updates te doen. In het algemeen zullen deze geavanceerdere methoden minder iteraties nodig hebben om te convergeren naar een lokaal maximum. Deze methoden werden in deze thesis echter niet verder onderzocht.
4.4
Conclusie
Als men een tegenstander wenst te modelleren die men ziet spelen, dan komt men het probleem tegen dat men geen informatie heeft over het private kaarten van die speler als die speler gefold heeft. Daarom maken de meeste opponent modeling technieken enkel gebruik van features die steeds berekend kunnen worden, ook als er gefold wordt. Het is echter zeer moeilijk om de publieke kaarten en hun verband met de mogelijke handen van de tegenstander te encoderen als nuttige features. In dit hoofdstuk werd een manier voorgesteld om modellen te gebruiken die ook private informatie van de tegenstanders gebruiken als features. Dit soort features kan de huidige toestand veel beter weergeven, maar het was voordien niet duidelijk hoe dit soort modellen konden getraind worden op hand histories waar gefolde kaarten uit ontbreken. In dit hoofdstuk werd een methode voorgesteld om dit te doen voor een bepaalde klasse van modellen die voldoen aan twee bepaalde voorwaarden. Twee soorten modellen werden voorgesteld die voldoen aan deze voorwaarden: bucketing abstracties en neurale netwerken. De capaciteit om de tegenstanders te modelleren van deze twee modellen wordt onderzocht in hoofdstuk 6. De voorgestelde modellen hebben veel parameters, waardoor er veel data van een strategie nodig is om deze strategie te modelleren. De modellen zijn dus minder bruikbaar als er
56 maar een klein aantal handen van de speler gezien zijn. Hoofdstuk 5 beschrijft hoe dan toch complexe modellen van deze speler kunnen opgebouwd worden.
¨ MIXTURE MODEL VAN STRATEGIEEN
57
Hoofdstuk 5 Mixture model van strategie¨ en Met de technieken uit hoofdstuk 4 kunnen modellen getraind worden van de gemiddelde speler in een hand history. De gemiddelde strategie van een deelverzameling of zelfs van ´e´en enkele speler kan getraind worden. De kwaliteit en de complexiteit van het model dat men kan trainen hangt echter zeer sterk af van het aantal informatie dat men heeft over de tegenstander(s). In een normale hand history zitten er zeer veel spellen, waardoor men zeer complexe modellen kan trainen voor de gemiddelde speler in zo’n hand history. Als men echter live tegen een tegenstander speelt, en nog maar zeer weinig spellen gezien of gespeeld heeft tegen die speler, dan is het met de technieken uit het vorig hoofdstuk veel moeilijker om een complex model te trainen. Voor bucketing abstracties of neurale netwerken bijvoorbeeld zijn er veel parameters nodig om complex gedrag te modelleren, maar een tiental spellen is niet voldoende informatie om zoveel parameters te trainen. Daarom is er nood aan een techniek die met zeer weinig informatie, zoals bijvoorbeeld een tiental spellen, toch een nuttig model te bouwen van de tegenstander. Aangezien er in dit kleine aantal spellen tegen de tegenstander zeer weinig toestanden voorkomen, en er hoogst waarschijnlijk hele klassen van toestanden zijn die helemaal niet voorkomen, moet de nieuwe techniek dus in staat zijn om de informatie die hij wel heeft te veralgemenen naar de toestanden die nog niet zijn voorgekomen. Om dit te kunnen doen moet de techniek dus kennis hebben over welke strategie¨en er vaak voorkomen en welke tendensen de tegenstanders vaak volgen. Er zijn twee bronnen waaruit de techniek zulke kennis kan halen:
58 1. Ingeprogrammeerde kennis van experten. Het is mogelijk om een pokerexpert regels te laten defini¨eren over welke tendensen pokerspelers vaak volgen. Een eenvoudig voorbeeld is dat men kan modelleren hoe “tight” een speler is. Een speler die zeer vaak foldt is “tight”, een speler die zeer gemakkelijk callt en raiset is “loose”. Als een speler gezien wordt als “tight” dan kan verwacht worden dat hij vlug zal vallen voor bluffs, maar dat wanneer hij niet foldt hij vaak een sterke hand heeft. Een ander voorbeeld is dat men kan modelleren hoe graag een speler gokt met handen die niet zeer sterk zijn maar een groot potentieel hebben om te verbeteren in de volgende ronden. Tegen dit soort speler moet voorzichtig gespeeld worden als de turn of de river een kaart bevat die zijn hand kan vervolledigen, zoals een derde kaart van ´e´en kleur of een kaart die een straight kan vervolledigen. In tegenstelling tot het vorige voorbeeld is dit echter iets moeilijker in code om te zetten. 2. Een hand history van andere spelers. Het zou ideaal zijn als dit soort kennis niet door een expert moet ingeprogrammeerd worden, maar als in plaats daarvan deze kennis automatisch berekend zou kunnen worden uit een hand history. Deze hand history bevat meestal geen spellen van de speler die gemodelleerd moet worden, maar toch kan deze hand history nuttig zijn om de algemene tendensen in de strategie¨en van spelers te modelleren. Voor het gebruik van kennis van experten gelden dezelfde nadelen als voor de regelgebaseerde systemen die besproken werden aan het begin van hoofdstuk 3: het is zeer moeilijk om een aantal regels te verzinnen die goed werken voor alle soorten situaties die in poker kunnen voorkomen, het is een zeer moeilijk te onderhouden systeem, en er is voor elke aanpassing aan het systeem een pokerexpert nodig. Daarom wordt er in deze thesis gekozen voor de tweede optie: het gebruiken van een hand history om de algemene tendensen van de strategie¨en die mensen gebruiken te modelleren. Hoe dit moet gebeuren is echter niet meteen duidelijk. Bij het berekenen van de gemiddelde strategie van een hand history konden de gespeelde spellen als datapunten aanzien worden. Als bijvoorbeeld in de hand history niet genoteerd zou staan welke speler welke spellen gespeeld heeft, dan kan men nog steeds een gemiddelde strategie berekenen, maar het berekenen van de tendensen in de strategie¨en is dan onmogelijk. In dit hoofdstuk zijn het dus in feite de spelers die als datapunten beschouwd worden, in plaats van enkel de spellen. Een eerste stap die in dit hoofdstuk dus moet gedaan worden is om te modelleren hoe de strategie¨en van spelers in een hand history verdeeld liggen in de ruimte van mogelijke
5.1 Bestaande unsupervised learning technieken
59
strategie¨en. Het doel is dus niet om iets te voorspellen maar om structuur te vinden in de hand history. Dit is dus een vorm van unsupervised learning. Daarom is het nuttig om enkele algoritmen te bekijken die voor andere unsupervised learning problemen vaak gebruikt worden.
5.1 5.1.1
Bestaande unsupervised learning technieken K-means clustering
´ en manier om structuur te vinden in een dataset is om de dataset onder te verdelen in E´ een bepaald aantal, stel k, clusters. De bedoeling is dat de clusters zo gekozen worden dat de gemiddelde afstand tussen datapunten en het centrum van de clusters waar ze toe behoren minimaal wordt. Deze afstand kan gemeten worden via de euclidische afstand of via een zelf-gedefini¨eerde afstandsmaat. Het doel van k-means clustering wordt wiskundig gedefini¨eerd als volgt. Stel dat de dataset n ongelabelde datapunten x1 tot xn bevat, en d(a, b) de afstandsmaat is tussen twee punten a en b. Dan is het doel om de dataset te partitioneren in k clusters Si met elk een centro¨ıde µi , zodanig dat de within-cluster sum of squares (WCSS) k X X
d(xj , µi )
i=1 xj ∈Si
minimaal wordt. Dit is een zeer moeilijk (NP-hard) probleem om exact op te lossen, wat betekent dat elk praktisch algoritme enkel een benaderde oplossing zal kunnen vinden. Er zijn vele varianten op het k-means algoritme, maar het meest gebruikte algoritme werkt als volgt: Er wordt vertrokken van een arbitraire partitionering van de dataset in k clusters Si . Daarna worden de volgende twee stappen iteratief herhaald: 1. De centro¨ıden µi van elke cluster worden berekend zodanig dat µi gemiddelde is van de datapunten in Si . Hoe dit gebeurt hangt af van de afstandsmaat, maar voor de euclidische afstand betekent dit: µi :=
1 X xj |Si | x ∈S j
i
60 2. De clusters worden nu herberekend zodanig dat elk datapunt toegekend wordt aan de cluster die overeenkomt met de dichtstbijzijnde centro¨ıde. In andere woorden: Si := {x : d(x, µi ) ≤ d(x, µj ) ∀ j ∈ [1, k]} Het algoritme stopt als na een iteratie de clusters niet veranderd zijn. Dit algoritme zou zeer nuttig zijn als we het zouden kunnen toepassen op een hand history. Dan zouden er immers k strategie¨en berekend worden die ongeveer overeenkomen met de k meest voorkomende soorten tegenstanders. Het is helaas zeer moeilijk om een nuttige afstandsmaat tussen spelers in een dataset te defini¨eren. In het k-means algoritme moeten de centro¨ıden ook van dezelfde aard zijn als de datapunten, waardoor stap 1, het berekenen van een gemiddelde speler uit een verzameling van spelers, moeilijk betekenis te geven is.
5.1.2
Mixture modellen en Expectation Maximization
Een andere veelgebruikte methode die in vele opzichten gelijkaardig is aan k-means is Expectation Maximization (EM). EM is een breed toepasbare techniek, maar de volgende bespreking van EM gaat voornamelijk over EM toegepast op het schatten van de parameters in een mixture model. Het doel van dit soort EM is ook om k clusters te berekenen, maar deze clustering moet geen partitie van de dataset zijn. In plaats daarvan worden de parameters van k mixture componenten berekend. Dit kan beschouwd worden als een “zachte” clustering. Een mixture model is een model waarbij verondersteld wordt dat elk van de datapunten komt uit ´e´en van de k mixture componenten. Met welke component elk datapunt xi overeenkomt is een verborgen variabele zi . Als zi = j dan defini¨eert component j de distributie P (xi | zi = j, θj ). Deze distributie wordt geparametriseerd door de parameters θj . Deze componenten zijn dikwijls gewone gaussiaanse distributies. Het gewicht van component j, P (zi = j) is een andere parameter van het model, voor elke j. Al deze parameters samen worden genoteerd als θ. Als de parameters θ van het mixture model gekend zijn, dan is het mogelijk om te berekenen hoe waarschijnlijk het is dat een datapunt xi bij component zi hoort: P (xi |zi , θ)P (zi , θ) P (zi |xi , θ) = P zj P (xi |zj , θ)P (zj , θ)
5.1 Bestaande unsupervised learning technieken
61
Dit worden de responsibilities genoemd. De clustering is dus geen “harde” clustering waarbij elk datapunt aan ´e´en enkele cluster wordt toegekend, maar een “zachte” cluster waarbij elk datapunt een bepaalde kans heeft om bij elk van de componenten te horen. EM wordt gebruikt om de parameters θ te schatten voor een dataset. Er wordt vertrokken van arbitraire parameters θ (0) , en dan worden net zoals in k-means twee stappen iteratief herhaald: 1. E-stap: Zoals hierboven vermeld kunnen met kennis van x en de huidige parameters θ (t) de responsibilities P (z | x, θ (t) ) berekend worden. Er kan nu over deze berekende distributies van z uitgemiddeld worden om de verwachte log likelihood van de data te berekenen met nieuwe parameters θ: Q(θ | θ (t) ) := Ez | x,θ(t) [log P (x, z | θ)] 2. M-stap: De parameters θ (t+1) voor de volgende iteratie worden nu gekozen als de parameters die de voorgaande verwachte log likelihood maximaliseren: θ (t+1) := argmax Q(θ | θ (t) ) θ
Het algoritme stopt na een aantal iteraties of als het verschil tussen Q(θ|θ (t) ) en Q(θ|θ (t+1) ) onder een bepaalde drempel valt. Het kan bewezen worden dat de likelihood van de data in elke iteratie stijgt, maar het EM algoritme kan wel vastlopen in lokale maxima en de maximum likelihood schatting niet bereiken. Het EM algoritme is zeer nuttig als het kiezen van de optimale θ in de M-stap analytisch kan uitgewerkt worden en zeer snel kan gebeuren. Dit is bijvoorbeeld het geval als er gaussiaanse mixtures gebruikt worden. Jammer genoeg is dit niet het geval als qua mixtures de modellen uit hoofdstuk 4 gebruikt worden. Het berekenen van de optimale parameters die likelihood van een model voor een hand history maximaliseren was immers het doel van hoofdstuk 4, en er is geen methode gevonden die deze parameters in 1 iteratie exact kan berekenen. In hoofdstuk 4 werd echter wel een methode voorgesteld die gebruik maakt van gradient descent om deze optimale parameters te benaderen. De M-stap zou kunnen ge¨ımplementeerd
62 worden met deze benaderende methode, maar dan valt de garantie dat de likelihood van de data in elke iteratie stijgt wel weg. Toch lijkt het waarschijnlijk dat dit aangepaste algoritme degelijke resultaten zou kunnen opleveren. Het EM algoritme is dus een goed vertrekpunt voor een algoritme dat structuur kan brengen in een hand history door k strategie¨en te berekenen die representatief zijn voor de hele hand history.
5.2
Berekeningsmethode
Er zijn twee vragen die eerst moeten beantwoord worden vooraleer het EM-algoritme toepasbaar is op hand histories: Hoe wordt de hand history ge¨encodeerd als een verzameling x van zichtbare en een verzameling z van verborgen variabelen? Wat moet er gebeuren in de M-stap? Het is niet mogelijk om de parameters die Q(θ | θ (t) ) maximaliseren exact te berekenen.
Deze twee vragen worden nu apart behandeld: Keuze van x en z Een eenvoudige keuze is om als xi hand i in een hand history te kiezen en als zi de mixture component waar het hand bij hoort. Zo wordt er een mixture van strategie¨en berekend. Merk echter op dat deze keuze van x en z geen informatie bevat over welke hand door welke speler gespeeld werd. De componenten die uit deze berekening zullen komen zullen gelijkaardige handen groeperen, niet gelijkaardige spelers. Er zal waarschijnlijk bijvoorbeeld een component zijn die voor de flop bijna altijd foldt, en andere componenten die bijna nooit folden voor de flop. Aangezien een gewogen gemiddelde van strategie¨en opnieuw gewoon een strategie is, zal het uiteindelijke resultaat niet echt nuttig zijn. Een manier om dit op te lossen is om als zi de component te kiezen waar niet hand i, maar waar speler i bij hoort. Alle handen in de hand history die door een speler i gespeeld werden worden dus verondersteld om door dezelfde mixture component zi gespeeld te zijn. De datapunten zijn dus nog steeds de spellen in de hand history, en de informatie over welke speler welke handen gespeeld heeft zit verwerkt in de structuur van zi .
5.2 Berekeningsmethode
63
Merk op dat doordat de datapunten nog steeds de handen zijn en niet de spelers, een speler met 1000 spellen in de hand history veel meer zal doorwegen dan een speler met 3 spellen. Dit is echter gewenst, aangezien er ook veel meer informatie is over die speler. De M-stap In de M-stap in het EM-algoritme worden er nieuwe parameters berekend die de verwachte log likelihood uit de E-stap te maximaliseren. Dit is echter zeer moeilijk voor de mixture componenten die we wensen te gebruiken, de modellen uit hoofdstuk 4. Zoals eerder vermeld is het wel mogelijk om deze parameters te benaderen, maar door enkel de parameters te benaderen valt de garantie dat in elke iteratie de likelihood van de data verbetert weg. Het uitvoeren van het volledige gradient descent algoritme tot convergentie voor elk van de k componenten zou ook enorm lang duren. Herinner uit sectie 4.1.2 dat voor elke actie in elk spel van de hand history tot 1326 keer de parti¨ele afgeleiden van de log likelihood naar elke parameter moeten berekend worden, ´e´en keer voor elke mogelijke hand van de ´ en iteratie van gradient descent duurt dus al lang, dus om dit k keer voldoende speler. E´ iteraties lang uit te voeren tot gradient descent convergeert zou betekenen dat de M-stap enorm lang duurt, en dat niet realistisch is om het volledige EM-algoritme uit te voeren tot convergentie. Daarom is er voor gekozen om in de M-stap niet het volledige gradient descent algoritme uit te voeren, dat vertrekt vanuit willekeurig gekozen parameters, maar om in de M-stap ´e´en iteratie van gradient descent uit te voeren waarbij vertrokken wordt van de parameters die het resultaat zijn van de vorige M-stap. Dit betekent dat er helemaal geen poging gedaan wordt om de parameters dicht bij de optimale parameters te krijgen, enkel dat er ´e´en stap ongeveer in de richting van de optimale parameters wordt gezet. Hiermee is er helemaal geen garantie dat de log likelihood van de data in elke iteratie van dit algoritme verbetert, of dat het algoritme uiteindelijk convergeert. Het zal dus empirisch moeten onderzocht worden of de mixture componenten die uit dit algoritme komen representatief zijn voor de dataset. Het is nuttig om na deze bespreking eens in woorden te herhalen en samen te vatten hoe het algoritme nu juist verloopt: 1. De k mixture componenten worden ge¨ınitialiseerd met willekeurige parameters, en de gewichten van elke component zijn initi¨eel gelijk.
64 2. De volgende twee stappen worden iteratief steeds herhaald: (a) E-stap: Voor elke speler i wordt berekend wat de likelihood is van de acties die hij in al zijn spellen gespeeld heeft als hij speelde volgens de strategie van component j, voor elke j. Na normalisatie zijn dit de responsibilities van component j voor speler i. (b) M-stap: Alle spellen in de hand history worden overlopen, en er wordt ´e´en iteratie van het gradient descent algoritme uitgevoerd op elk van de componenten. Het gewicht van een spel van speler i voor component j is de responsibility van component j voor speler i. 3. Dit algoritme wordt uitgevoerd voor een bepaald aantal iteraties, en eventueel een aantal keer herhaald om te vermijden dat het resultaat een lokaal optimum is.
Het algoritme in deze vorm duurt echter vrij lang om uit te voeren, zelfs voor relatief eenvoudige mixture componenten. Dit komt voornamelijk omdat het berekenen van de log likelihood en de gradient-descent iteratie telkens als de private kaarten van een speler niet gekend zijn al de mogelijke kaarten van die speler moet overlopen. Aangezien er 1326 mogelijke private kaarten zijn per speler duurt dit algoritme vele keren langer dan bijvoorbeeld een EM-algoritme met gaussiaanse mixtures. Daarom zijn er twee kleine aanpassingen die gemaakt werden aan het algoritme, met als doel om zonder de kwaliteit van het resultaat veel aan te passen het algoritme sneller te laten uitvoeren. Deze twee aanpassingen worden besproken in de volgende drie secties.
5.3
Harde assignatie tijdens trainen
In de M-stap wordt elke component getraind op elk spel in de hand history, waarbij de gewichten van elk spel komen uit de E-stap. Dit betekent dat deze M-stap ongeveer even lang duurt als k iteraties van gradient descent voor het trainen van 1 model op dezelfde data. Het gebeurt echter vaak voor een spel de responsibility van ´e´en van de componenten zeer dicht bij 1 ligt, terwijl de responsibilities van de andere componenten zeer klein zijn. Dit is meestal het geval als een speler vele spellen heeft in de hand history. De totale likelihood van een model voor een speler wordt immers berekend door de likelihood van elk van de
5.4 Stochastische assignatie
65
spellen van die speler met elkaar te vermenigvuldigen, en als een strategie consistent iets beter overeenkomt met de gespeelde spellen dan een andere, dan kan dit eindigen in enkele grootteordes verschil in likelihood. Hoe lang het duurt om de parti¨ele afgeleiden te berekenen in een iteratie van gradient descent hangt echter niet af van de gewichten waarmee deze parti¨ele afgeleiden later vermenigvuldigd worden. Het algoritme zal dus veel tijd spenderen aan het berekenen van parti¨ele afgeleiden die later met een zeer klein gewicht zullen vermenigvuldigd worden. Daarom is het nuttig om de gewichten in de M-stap te vervangen door een “harde assignatie” waarbij de mixture component die de grootste likelihood heeft voor een spel gewicht 1 krijgt en de andere componenten gewicht 0. Dit betekent dat men enkel voor deze component de parti¨ele afgeleiden moet berekenen, wat betekent dat de M-stap ongeveer k keer sneller uitgevoerd kan worden. Dit is echter geen pure optimalisatie in die zin dat het resultaat van het algoritme gegarandeerd onveranderd blijft. Het aanpassen van de gewichten verandert de parameters die als resultaat uit de M-stap komen. Het zorgt ervoor dat het algoritme zich iets meer zal gedragen als k-means. Een speler die net op de rand tussen twee componenten ligt in termen van likelihood liggen zal bijvoorbeeld enkel gebruikt worden om ´e´en van de twee componenten te trainen. Als dit een speler is met vrij veel spellen, dan kan dit een relatief grote invloed hebben op die component. Als de speler echter 1 actie anders gedaan had was het misschien mogelijk geweest dat hij aan de andere component werd toegekend, en had de speler die component be¨ınvloed. Deze harde assignatie is dus relatief ruisgevoelig.
5.4
Stochastische assignatie
Er is echter geen enkele reden dat bij een harde assignatie van de gewichten tijdens de M-stap alle spellen van dezelfde speler aan dezelfde component moeten toegekend worden. Als de responsibilities van een speler voor twee componenten ongeveer 1/2 zijn en de rest van de responsibilities van die speler zeer klein zijn, dan is het redelijk om de helft van de spellen van die speler toe te kennen aan de ene component en de helft aan de andere. Dit kan veralgemeend worden. Als de likelihoods van een speler niet gedomineerd worden door ´e´en van de componenten, dan kan de optimalisatie van harde assignatie toegepast
66 worden zonder dat alle spellen van die speler noodzakelijk toegekend worden aan de meest waarschijnlijke component. Elk spel van de speler kan willekeurig aan elk van de componenten worden toegekend, waarbij de kans dat het aan component i toegekend wordt overeenkomt met de responsibility van component i. Dit maakt de harde assignatie iets minder ruisgevoelig, en het gedrag van het algoritme zal iets dichter liggen bij het oorspronkelijke algoritme uit sectie 5.2. Het grootste voordeel van harde assignatie, namelijk dat de M-stap ongeveer k keer sneller uitgevoerd kan worden dan in het oorspronkelijke algoritme, blijft echter behouden.
5.5
Initialisatiefase
In de initialisatie van het algoritme worden de parameters van de mixture componenten willekeurig gekozen. Deze willekeurig gekozen parameters zullen echter geen strategie vormen die in het echt vaak voorkomt. De initi¨ele strategie¨en zullen immers niet consistent ´e´en “stijl” volgen, maar ongeveer willekeurig in sommige toestanden volgens ´e´en bepaalde stijl spelen en in andere toestanden volgens een andere. Dit is logisch, aangezien de consistente stijlen net zijn wat we willen leren met het algoritme. In de eerste iteraties zullen de responsibilities voor de componenten ook nog geen consistente stijl volgen. Het is dus niet nodig om veel rekenkracht te spenderen en de hele hand history te overlopen om nauwkeurig de responsibilities in de E-stap en de parti¨ele afgeleiden in de M-stap te berekenen. In de eerste paar iteraties zullen de responsibilities immers nog vrij veel veranderen tot het algoritme meer stabiliseert. Daarom is het mogelijk om in de eerste paar iteraties niet de volledige hand history te gebruiken, maar slechts een klein deel ervan. Dit zorgt ervoor dat de iteraties korter worden, waardoor er meer iteraties kunnen berekend worden in dezelfde tijdspanne. Het feit dat de responsibilities en de gradient descent iteraties minder nauwkeurig zijn is minder belangrijk, aangezien zowel de responsibilities als de parameters van de componenten nog veraf liggen van waar ze uiteindelijk zullen belanden. Het deel van de dataset dat gebruikt wordt in deze initialisatiefase is willekeurig en verandert elke iteratie. Het is echter wel belangrijk om op te merken dat de spellen van een speler niet uniform verdeeld liggen in een hand history. Een hand history is chronologisch, en de spellen van een speler zijn sterk gegroepeerd in de tijd. Daarom wordt er in de initialisatiefase steeds een aaneensluitend deel van de hand history gekozen, geen willekeurige
5.6 Gebruik van het mixture model
67
deelverzameling.
5.6
Gebruik van het mixture model
Het hierboven besproken algoritme is in staat om de parameters van een mixture model van strategie¨en te schatten die de likelihood van de gegeven hand history maximaliseren. Het mixture model dat er uit komt is in feite een gewogen gemiddelde van strategie¨en, wat op zich ook weer een strategie is. Deze gemiddelde strategie zal echter niet noodzakelijk een betere likelihood hebben van de hand history dan een “gewoon” model uit hoofdstuk 4 getraind via gradient descent, maar dat was ook niet de bedoeling. De bedoeling van dit hoofdstuk was om dit mixture model te gebruiken om nieuwe tegenstanders met zeer weinig informatie toch relatief accuraat te modelleren. Dit is nu relatief eenvoudig: Er wordt aangenomen dat de strategie van deze nieuwe speler gesampled werd uit het mixture model. Dit betekent dat er aangenomen wordt dat de strategie van de speler overeenkomt met de strategie van ´e´en van de componenten, namelijk z. De waarde van z is uiteraard onbekend, maar nadat men de tegenstander een aantal spellen x heeft zien spelen kan men wel de kans P (z | x, θ) dat de speler hoort bij elk van de componenten volgens het model berekenen. Deze kansen P (z | x, θ) zijn nu de kansen dat de strategie van de speler voortgebracht werd component z. Dit betekent in andere woorden dat het model van de strategie van de tegenstander een gewogen gemiddelde is van de strategie¨en van de componenten, waarbij component j gewicht P (z = j | x, θ) heeft. Het lijkt misschien raar dat hier dus een gewogen gemiddelde wordt gebruikt, en niet enkel de component met de beste responsibility. Dit kan echter intu¨ıtief begrepen worden via een eenvoudig voorbeeld: Stel dat het mixture model bestaat uit twee mixture componenten, ´e´en die 99% van de tijd foldt, en ´e´en die 99% van de tijd callt. Als met dit mixture model een speler geschat moet worden die ongeveer evenveel callt als foldt, dan zullen de responsibilities ongeveer gelijk zijn voor beide componenten. Met een gewogen gemiddelde zal de voorspelde strategie
68 dan ook ongeveer even vaak folden als callen, terwijl met een “harde assignatie” ´e´en van de twee componenten zal gekozen worden voor de voorspelling. Het is duidelijk dat het gewogen gemiddelde dan een betere log likelihood zal hebben. Fijner afstemmen van de parameters Merk op dat naarmate er meer en meer spellen zijn die men de tegenstander ziet spelen, de kansen P (z | x, θ) verder en verder uiteen zullen gaan. Na een aantal spellen zal de responsibility van ´e´en van de componenten dicht bij 1 liggen terwijl de rest dicht bij 0 ligt. Het algoritme zal dus convergeren naar ´e´en van de componenten. Dit betekent dat als men een groot aantal spellen speelt tegen dezelfde tegenstander, men niet zo veel meer zal bijleren over die tegenstander nadat men de meest waarschijnlijke component bepaald heeft. Wat men dan echter kan doen is de parameters van deze meest waarschijnlijke component nemen als vertrekpunt van gradient descent en deze parameters via gradient descent fijner afstemmen. Indien men meerdere iteraties doet zal men wel moeten opletten voor overfitting. Dynamische tegenstanders Wat men ook kan doen als men veel handen speelt tegen dezelfde tegenstander is de veronderstelling dat de tegenstander volgens een statische strategie speelt verzwakken. Men kan het gewicht dat men aan een spel geeft exponentieel laten afnemen met hoe lang het geleden is dat dat spel gespeeld is. Aangezien men niet zo veel data nodig heeft om te bepalen welk van de componenten het meest waarschijnlijk is kan men relatief snel opmerken dat de tegenstander van strategie veranderd is. Zo kan men dynamische tegenstanders modelleren. Dit wordt in deze thesis echter niet verder onderzocht.
5.7
Exploitatie
Hoewel deze thesis hoofdzakelijk gaat over het modelleren van de strategie¨en van tegenstanders, valt het toch op te merken dat het mixture model een groot voordeel heeft voor het exploiteren van het opgebouwde model. Het is immers mogelijk om na het trainen van het mixture model voor elke component een counter-strategie te berekenen. Dit kan door gebruik te maken van de RNR-techniek (RNR, zie sectie 3.6), die een -safe counterstrategie berekent tegen de gegeven strategie. Dit betekent dat de counterstrategie σ1 nooit meer kan ge¨exploiteerd worden dan . In
5.8 Conclusie
69
andere woorden: de utiliteit voor de counterstrategie is tegen elke andere strategie minstens de theoretische waarde van het spel voor speler 1, v1 , min : u1 (σ1 , σ2 ) ≥ v1 −
∀ σ2 ∈ Σ2
Als een -safe counterstrategie σ10 met dezelfde exploitabiliteit berekend wordt tegen een andere mixture component, dan geldt hetzelfde voor deze σ10 : u1 (σ10 , σ2 ) ≥ v1 −
∀ σ2 ∈ Σ2
Nu is de utiliteit van een gewogen gemiddelde van strategie¨en mixp (σ1 , σ2 ) steeds gelijk aan het gewogen gemiddelde van de utiliteit van de individuele strategie¨en [9, vergelijking 4]: u1 (mixp (σ1 , σ10 ), σ2 ) = pu1 (σ1 , σ2 ) + (1 − p)u1 (σ10 , σ2 ) Uit deze drie vergelijkingen kan geconcludeerd worden dat: u1 (mixp (σ1 , σ10 ), σ2 ) ≥ v1 −
∀ σ2 ∈ Σ2
In andere woorden, het gewogen gemiddelde van de twee -safe counterstrategie¨en zal ook nooit meer exploiteerbaar zijn dan . Het is echter niet gegarandeerd dat de gewogen gemiddelde strategie een -safe counter strategie is tegen het model van de tegenstander. Het is immers mogelijk dat er andere strategie¨en bestaan met exploitabiliteit die het model meer exploiteren. Zo’n -safe counterstrategie berekenen zal echter zeer moeilijk tijdens het spelen tegen een tegenstander in een aantal seconden te doen zijn. De RNR en DBR technieken doen er immers zeer lang over om een counterstrategie te benaderen. Het gewogen gemiddelde van strategie¨en zal in de meeste gevallen echter wel een redelijke benadering zijn van de -safe counterstrategie. Dit feit wordt nog versterkt doordat, zoals in de vorige sectie besproken werd, de responsibilities van de mixture componenten zullen convergeren naar een ´e´enheidsvector. Dit betekent dat dan het model zeer sterk overeenkomt met ´e´en van de mixture componenten, en dat de bijhorende counterstrategie bijna rechtstreeks kan gebruikt worden.
5.8
Conclusie
Hoofdstuk 4 besprak hoe men complexe modellen kon opbouwen van een tegenstander die men zeer veel spellen heeft zien spelen. Het feit dat men zo veel informatie heeft over de
70 tegenstander zorgt ervoor dat men zonder veel voorkennis van poker toch accurate modellen kan bouwen. Als men echter live een tegenstander wil modelleren en exploiteren, dan heeft men meestal die tegenstander slechts zeer weinig spellen zien spelen. Het accuraat modelleren van deze tegenstander vereist dan voorkennis over het algemeen gedrag van tegenstanders. In dit hoofdstuk werd een algoritme, gebaseerd op EM, voorgesteld dat in staat is om deze voorkennis te halen uit een hand history, onder de vorm van de parameters van een mixture model van strategie¨en. Dit mixture model kan men gebruiken om met weinig informatie de strategie van een nieuwe tegenstander relatief accuraat te modelleren.
EXPERIMENTELE RESULTATEN
71
Hoofdstuk 6 Experimentele Resultaten In dit hoofdstuk worden de methoden die in de vorige hoofdstukken werden voorgesteld experimenteel onderzocht en vergeleken met de bestaande opponent modeling technieken.
6.1
Datasets
De gradient descent techniek en het trainen van een mixture model vereisen een hand history van een groot aantal handen. Er zijn meerdere bronnen vanwaar deze hand histories bekomen kunnen worden. Enkele potenti¨ele bronnen worden in de volgende secties besproken.
6.1.1
HHExchange
Er bestaat een website, HHExchange.eu1 , waar mensen gratis hand histories die andere spelers ge¨ upload hebben kunnen downloaden, nadat ze zelf eerst een bepaald aantal handen ge¨ upload hebben van de spellen die ze zelf gespeeld hebben. Een hand history die het pokerprogramma van een speler gegenereerd heeft bevat doorgaans alle handen van die speler, ook als hij gefold heeft. Vele spelers zouden echter niet akkoord zijn om deze informatie zomaar door iedereen te laten downloaden, aangezien het hun strategie en manier van spelen volledig blootgeeft. Daarom filtert de HHExchange deze informatie weg uit de hand histories vooraleer het deze openbaar maakt. De hand histories die bijgevolg te downloaden zijn op HHExchange.eu bevatten dezelfde informatie als hand
1
http://www.hhexchange.eu/
72 histories die “gedatamined” werden door een programma dat niet deelnam aan de spellen, maar ze enkel observeerde. De HHExchange site lijkt dus een ideale bron van hand histories. Een nadeel is echter dat de site niet bijzonder populair is, en dat voornamelijk handen van de meest populaire pokervarianten ge¨ upload worden, zoals no-limit Hold’em met 6 of meer spelers. Heads-up limit Hold’em is minder populair, en er zijn in totaal slechts minder dan 1000 handen ge¨ upload van deze variant. Er zal dus nog een andere bron van hand histories moeten gebruikt worden.
6.1.2
Man-Machine Poker Championship
In 2007 werd door de Computer Poker Research Group van de universiteit van Alberta een Man-Machine Poker Championship toernooien gehouden [8]. In dit toernooi speelden twee van de beste pokerspelers in de wereld, Phil Laak en Ali Eslami, tegen een benaderd nash equilibrium berekend door de CFRM techniek (zie sectie 3.5). Er werden twee zogenaamde duplicate matches van 2000 handen gespeeld, voor een totaal van 4000 handen, waarbij Phil Laak de handen kreeg die de CFRM-bot kreeg in de match tegen Ali Eslami, en omgekeerd. Dit is een manier om de variantie van de spellen te reduceren. Het resultaat van dit toernooi was dat na de 4000 matches Laak en Eslami 39.5 small bets gewonnen hadden, minder dan 10 millibets per spel. Dit is echter een zeer klein aantal dat niet statistisch significant is om met zekerheid te zeggen dat ze beter gespeeld hebben. DIVAT-analyse (zie sectie 3.9) van de spellen duidt immers aan dat de bot iets beter gespeeld heeft en een positieve verwachte waarde heeft, maar ook dit is niet statistisch significant. De hand histories van dit toernooi zijn online te downloaden2 . Deze hand history kan zeer nuttig zijn aangezien alle handen van de spelers er in staan. De hand history bevat echter slechts 4000 handen, wat helaas iets te weinig is om complexe modellen op te trainen.
6.1.3
Datamining
De meest nuttige bron van grote hoeveelheden hand histories zijn echter hand histories die verzameld zijn door een programma dat vele pokerspellen van een online casino tegelijk 2
Op http://www.poker-academy.com/man-machine/downloads.php
6.1 Datasets
73
observeert. Deze manier om hand histories te verzamelen noemt men data mining. Er zijn online sites, zoals Poker Table Ratings3 , waar dergelijke gedataminede hand histo´ en miljoen spellen van heads-up limit Texas Hold’em ries te koop aangeboden worden. E´ met een big blind van 4 cent gespeeld op het iPoker netwerk bijvoorbeeld kost 16 USD. Deze aangekochte hand history vormt de dataset die gebruikt werd in dit hoofdstuk om de experimentele resultaten te bekomen. De handen erin zijn gespeeld tussen 14 juli 2012 en 10 februari 2013. Alle handen gespeeld in die periode voor deze variant van poker staan in de hand history. Er werd dus geen bias ge¨ıntroduceerd door de selectie van welke spellen er geobserveerd werden. Er is ook geen zogenaamd Hawthorne effect waarbij de spelers zich anders gedragen doordat ze weten dat ze geobserveerd worden, aangezien alle spellen geobserveerd worden en de spelers niet verwittigd worden van wie er het spel observeert. De strategie¨en in de hand history zijn dus effectief de strategie¨en die spelers gebruiken bij het spelen van een heads-up limit Texas Hold’em spel met big een blind van 4¢.
6.1.4
Gefabriceerde data
Naast het gebruik van realistische data, gespeeld door echte mensen en/of bots, is het ook nuttig om zelf hand histories te genereren door eenvoudige regelgebaseerde strategie¨en te laten spelen tegen elkaar. Het voordeel hiervan is dat men zowel steeds de handen kent die de spelers hadden, als de effectieve strategie van elk van de spelers. Een strategie die in dit hoofdstuk gebruikt wordt gebruikt enkel de Expected Hand Strength E[HS], als volgt: 1 sin(2π · (E[HS])) 2 1 P (call) ∼ 1 + sin(2π · (E[HS] − 2 1 P (raise) ∼ 1 + sin(2π · (E[HS] − 2 P (f old) ∼ 1 +
1 )) 3 2 )) 3
(6.1.1)
Deze probabiliteiten worden genormaliseerd door te delen door de som van de niet-genormaliseerde probabiliteiten op de mogelijke acties. Als alle drie de acties mogelijk zijn, dan betekent dit gewoon een deling door 3. De resulterende probabiliteitsdistributie wordt weergegeven in figuur 6.1. 3
http://www.pokertableratings.com/
74 1 P(fold) P(call) P(raise)
0.8 0.6 0.4 0.2 0
0
0.2
0.4 0.6 E[HS]
0.8
1
Figuur 6.1: Grafiek van de probabiliteiten van de voorbeeldstrategie gedefini¨eerd door vergelijking 6.1.1, als alle drie de acties mogelijk zijn. Deze strategie is uiteraard helemaal niet realistisch, maar is visueel wel herkenbaar als de probabiliteitstriples van een strategie in een grafiek uitgetekend worden in functie van E[HS]. De strategie is echter niet triviaal om te achterhalen uit een hand history, aangezien E[HS] geen publieke informatie is maar op een niet-triviale manier afhangt van de combinatie van private en publieke kaarten.
6.2 6.2.1
Generieke spelersmodellen Toy strategie
De bovenstaande “toy strategie” kan gebruikt worden om experimenteel te verifi¨eren dat de gradient descent methode uit hoofdstuk 4 de strategie die gebruikt werd om de hand history te genereren effectief kan benaderen. Het model dat gebruikt wordt om dit te verifi¨eren is een bucketing abstractie die ook gemakkelijk kan uitgetekend worden als grafiek van E[HS]. Er wordt gebruik gemaakt van 50 buckets. Bucket 1 komt overeen met de handen die een E[HS] hebben tussen 0 en 1/50, bucket 1 komt overeen met een E[HS] tussen 1/50 en 2/50, enzovoort. Dit kan men zien als een soort van histogram van de actiefrequenties van de speler in functie van E[HS]. Het is echter geen gewoon histogram van de actiefrequenties. Als men
6.2 Generieke spelersmodellen
75
immers een normaal histogram berekent van de frequentie van elke actie in elk interval (dit kan uiteraard enkel als de private kaarten en E[HS] altijd gekend zijn), dan bekomt men de grafiek uit figuur 6.2. De actiefrequenties in dit histogram komen helemaal niet overeen met de strategie uit figuur 6.1. Dit komt doordat figuur 6.1 de probabiliteit op fold, call en raise geeft als alle drie de acties mogelijk zijn. Het gebeurt echter vaak dat folden niet mogelijk is. Dan zal de strategie de kansen op fold op 0 stellen en de kans op call en raise uit vergelijking 6.1.1 normaliseren. De strategie zal dus vaker raisen en callen dan de frequenties in figuur 6.2, wat gereflecteerd wordt in de histogram in figuur 6.2. Dit is de reden waarom in bucketing abstractie modellen de buckets andere formules voor de probabiliteitstriples en parti¨ele afgeleiden gebruiken afhankelijk van welke acties er mogelijk zijn (zie sectie 4.1.4).
Figuur 6.2: Histogram van de geobserveerde actiefrequenties van de toy strategie in functie van E[HS]. Het valt nu te zien of de gradient descent methode wel in staat is om een accuraat model van de toy strategie te trainen. Het trainen gebeurt met stochastic gradient descent, met
76 mini-batches van 10 handen en een learning rate die doorheen de training lineair afneemt van 0.003 naar 0. Na een miljoen handen is het resultaat de strategie weergegeven in figuur 6.3. De probabiliteitstriples van elke bucket zijn in deze figuur weergegeven alsof alle drie de acties mogelijk zijn. Het is duidelijk dat dit zeer goed overeenkomt met de genererende strategie (figuur 6.1). Onderaan in figuur 6.2 wordt weergegeven exact hoe vaak elk E[HS]-interval voorkomt. Onderaan in figuur 6.3 wordt weergegeven hoe vaak de parti¨ele afgeleiden van elk van de buckets worden berekend, gewogen volgens de gewichten waarmee die parti¨ele afgeleiden later vermenigvuldigd worden. Merk op dat deze twee distributies over E[HS] zeer goed overeenkomen. Voor dit eenvoudige voorbeeld kunnen de strategie¨en visueel vergeleken worden om te zien dat de gradient descent methode convergeert naar de juiste strategie. Voor complexere modellen is dit echter niet meer mogelijk. Dan wordt gebruik gemaakt van de foutfunctie, de negatieve log likelihood, om aan te duiden hoe goed een strategie een hand history modelleert. De gemiddelde negatieve log likelihood van de toy strategie op een hand history van 100000 handen die de strategie zelf gegenereerd heeft is 6.55028, met een 95%-betrouwbaarheidsinterval van 0.018227. Elk model dat een gelijkaardige log likelihood heeft kan beschouwd worden als een goed model van de strategie. De gemiddelde negatieve log likelihood van het model op deze zelfde hand history bedraagt 6.55164 ± 0.018305. Deze hand history deelt geen handen met het miljoen handen gebruikt om het model te trainen. De log likelihood ligt dicht genoeg om te concluderen dat het getrainde model een goed model is van de strategie, wat overeenkomt met onze eerdere vaststellingen. Het is nuttig om te kijken hoe vlug het model de strategie benadert, door de log likelihood van de validatieset van het model na elke iteratie uit te zetten in functie van die iteratie. De resulterende grafiek is weergegeven in figuur 6.4. In deze grafiek werd een iteratie beschouwd als 20000 handen, maar in elke iteratie werden wel andere handen uit de trainingsset geselecteerd voor de stochastic gradient descent. Het is duidelijk dat het model na de eerste 20000 handen reeds een relatief goed model van de data is. Na 100000 handen is de log likelihood reeds dicht bij de log likelihood van de genererende strategie, en vanaf dat punt neemt de log likelihood geleidelijk aan af. Met meer iteraties of een iets grotere learning rate zou er nog een nauwkeuriger model kunnen
6.2 Generieke spelersmodellen
77
opgebouwd worden, maar dat was niet het doel van deze sectie. Het doel was enkel om te verifi¨eren dat gradient descent een model kan opbouwen aan de hand van een hand history van een strategie. Voor deze toy strategie is dit alvast duidelijk gelukt.
Figuur 6.3: Model van de toy strategie na trainen. Probabiliteitstriples zijn weergegeven alsof alle drie de acties mogelijk zijn.
6.2.2
Bucketing abstractie
In sectie 4.1.4 werd een manier voorgesteld om bij bucketing abstracties automatisch het aantal buckets te herordenen zodanig dat het aantal buckets waarin een verzameling toestanden wordt opgesplitst ongeveer proportioneel is met hoe vaak die verzameling toestanden ongeveer voorkomt. Dit gebeurt door een reeds getraind model te gebruiken om te schatten hoe veel spellen van de dataset er ongeveer de verzameling van toestanden zullen bereiken. Men zal de verzameling toestanden dan onderverdelen in een aantal buckets gelijk aan 1/k van dit geschatte aantal. Dan zullen er ongeveer k spellen per bucket beschikbaar zijn om de bucket te trainen. Er moet nog onderzocht worden welke waarde van k er best gebruikt wordt. Dit kan gebeuren door voor verschillende k het bijhorende bucketing abstractie model te trainen
78
Figuur 6.4: Negatieve log likelihood van de strategie na elke iteratie van het stochastic gradient descent algoritme, met 95%-betrouwbaarheidsintervallen. op de helft van de realistische iPoker hand history, en te kijken wat de log likelihood de andere helft van de hand history is voor elk van deze modellen. Door deze log likelihoods met elkaar te vergelijken kan gezien worden welke k er het beste model oplevert. In deze en de volgende secties wordt bij het berekenen van de de log likelihood de publieke kaarten niet meegerekend. Het verschil is slechts een constante die niet afhangt van de strategie¨en van de spelers. De absolute waarde van de gemiddelde log likelihood is minder belangrijk aangezien het sterk afhangt van de gebruikte hand history en de strategie¨en die de spelers in die hand history gebruikt hebben. Het verschil in gemiddelde log likelihoods tussen twee verschillende modellen is veel belangrijker. De log likelihood wordt gemeten in bits, wat betekent dat telkens de log steeds berekend wordt met grondtal 2. Het resultaat hiervan wordt weergegeven in figuur 6.5. Uit deze grafiek blijkt duidelijk dat als er minder dan tien handen gebruikt worden per bucket, dat dan de buckets veel te weinig data hebben om de correcte distributies aan te leren. Als een groot aantal handen gebruikt worden per bucket, dan is er voldoende data om de strategie¨en van de buckets nauwkeurig te berekenen, maar er zijn dan minder buckets, waardoor de strategie van de
6.2 Generieke spelersmodellen
79
Figuur 6.5: Gemiddelde negatieve log likelihood met 95%-betrouwbaarheidsintervallen voor bucketing abstracties met verschillende k. gemiddelde speler ook minder nauwkeurig kan worden gemodelleerd. De optimale waarde van k lijkt rond 60 te liggen. Deze waarde geeft het beste evenwicht tussen voldoende data te hebben per bucket en toch voldoende buckets te hebben in totaal.
6.2.3
Vergelijking van modellen
In hoofdstuk 4 werden twee verschillende klassen van modellen voorgesteld, bucketing abstracties en neurale netwerken, die in staat zijn om een generiek model van de gemiddelde speler in een hand history op te bouwen via de gradient descent methode. Het is nuttig om nu te kijken hoe goed deze voorgestelde technieken en hun varianten in staat zijn om een realistische hand history te modelleren. Deze modellen kunnen vergeleken worden met de verscheidene opponent modeling technieken die onderzocht werden in de literatuur, Alle modellen werden getraind op de helft van de hand history, waarna de gemiddelde negatieve log likelihood van de andere helft van de hand history berekend werd voor elk model. De resultaten zijn weergegeven in tabel 6.1.
80 Model Random ANN-Poki CT-Loki CT-Vexbot Regressieboom Bucketing Bucketing-R Bucketing-S Bucketing-RS ANN
- gem. log likelihood 9.431 6.302 6.965 6.19 6.158 6.124 5.838 6.052 5.748 5.566
Tabel 6.1: Gemiddelde negatieve log likelihood van de validatie hand history voor elke van de onderzochte modellen, gemeten in bits. Het model genoteerd als Random geeft aan elke mogelijke actie een gelijke kans. Dit is een model zonder parameters dat enkel dient om andere modellen mee te vergelijken. Het ANN-Poki model is een eigen implementatie van het neuraal netwerk dat gebruikt werd in de opponent modeling module in Poki. Alle inputs uit tabel 4.1 werden gebruikt, behalve 9 en 10 aangezien deze irrelevant zijn voor Heads-up poker, en 17 aangezien Poki aan geen enkele hand in de dataset meedoet. Het model genaamd CT-Loki is de context tree gebruikt in Loki (zie sectie 3.1), en het model genaamd CT-Vexbot is het actie-voorspellend deel van de opponent modeling module van Vexbot beschreven in sectie 3.4. Merk op dat deze CT-Vexbot dus niet alle opponent modeling techniek gebruikt in Vexbot gebruikt werden: in Vexbot wordt immers ook voor elke showdown een distributie van hand strengths voorspeld. Dit laatste kan echter niet omgezet worden in een strategie-model waarbij er distributies over acties worden voorspeld. Het is immers mogelijk dat de geleerde HS-histogrammen niet met een mogelijke strategie overeenkomen. Als de gemodelleerde speler bijvoorbeeld toevallig een aantal sterke handen op rij kreeg dan kunnen de HS-histogrammen voorspellen dat de speler vaker sterke handen heeft in een bepaalde situatie dan theoretisch mogelijk is. Het model genoteerd als Regressieboom is de regressieboom die in de MCTS-bot gebruikt werd om de volgende actie van de speler in een bepaalde toestand te voorspellen (zie sectie 3.8). Analoog met het vorige model omvat dit model niet alle opponent modeling gebruikt
6.3 Mixture model
81
in de MCTS-bot. In elke showdown wordt er immers in de MCTS-bot ook een distributie van de kaarten van de speler voorspeld, maar dit kan opnieuw niet vertaald worden naar een actie-voorspellende strategie, voor dezekfde redenen als hierboven. De features die statistieken van het gedrag van de speler in de vorige spellen encoderen, zoals de frequentie waarmee de speler tot nu toe heeft gefold, worden in deze sectie weggelaten. In sectie 6.3 worden ze wel gebruikt. De vier Bucketing-modellen zijn bucketing abstracties. Het model genaamd Bucketing is exact de bucketing abstractie besproken in sectie 4.1.4. Bucketing-R is dezelfde abstractie waarbij de buckets automatisch geherordend werden met een gemiddeld aantal datapunten per bucket k van 60. De structuur van de buckets van de Bucketing-S en Bucketing-RS modellen zijn dezelfde als in respectievelijk Bucketing en Bucketing-R, maar de buckets worden lineair ge¨ınterpoleerd volgens de methode besproken in sectie 4.1.6. Tenslotte is het ANN model het neuraal netwerk dat voorgesteld werd in sectie 4.1.5. Er wordt 1 verborgen laag met 10 neuronen gebruikt, die logistische activatiefuncties hebben. Resultaten Uit tabel 6.1 kan afgelezen worden dat voor de modellen uit de literatuur de recentere modellen beter werken dan hun voorgangers. De voorgestelde modellen, zowel de bucketing abstractie als het neurale netwerk, hebben echter een betere log likelihood dan al deze modellen en kunnen dus de acties in de hand history beter voorspellen. Voor de bucketing abstracties kan gezien worden dat de herordening van buckets een verbetering geeft in log likelihood van ongeveer 0.3 bits, en dat de lineaire interpolatie tussen buckets een verbetering geeft van ongeveer 0.1 bits. Het beste model in deze tabel is echter het neurale netwerk.
6.3
Mixture model
Het is ook nodig om voor het mixture model experimenteel te verifi¨eren dat de mixture modellen van een getraind mixture model overeenkomen met de meest voorkomende types van strategie¨en in de hand history. Dit kan opnieuw gebeuren door middel van toy strategie¨en. De sinuso¨ıdale strategie gedefini¨eerd in sectie 6.1.4 kan hier hergebruikt worden, maar met ´e´en strategie kan er
82 1
1 P(fold) P(call) P(raise)
0.8
1 P(fold) P(call) P(raise)
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0
0
0.2
0.4 0.6 E[HS]
0.8
1
0
0
0.2
0.4 0.6 E[HS]
0.8
P(fold) P(call) P(raise)
0.8
1
0
0
0.2
0.4 0.6 E[HS]
0.8
1
Figuur 6.6: Grafieken van de distributies over de mogelijke acties van de drie toy strategie¨en gebruikt om het mixture model te testen. De distributies zijn weergegeven alsof alle drie de acties mogelijk zijn. geen mixture model opgebouwd worden. Er zullen dus nog andere strategie¨en moeten gedefini¨eerd worden. Er worden twee toy strategie¨en toegevoegd, die beide zeer eenvoudig zijn. De eerste kijkt helemaal niet naar de toestand van het spel en zal steeds folden met kans 1/6, callen met kans 2/6 en raisen met kans 3/6. Als een actie niet mogelijk is dan worden de probabiliteiten op de overige twee acties gehernormaliseerd. De tweede toy strategie die wordt toegevoegd zal wel kijken naar E[HS], en zal de volgende distributie geven aan de mogelijke acties: P (f old) ∼ 1 + 2E[HS] P (call) ∼ 2 P (raise) ∼ 3 − 2E[HS]
(6.3.1)
Opnieuw worden deze probabiliteiten genormaliseerd door te delen door de som van de niet-genormaliseerde probabiliteiten van alle mogelijke acties. Als alle 3 de acties mogelijk zijn, dan wordt er gedeeld door 6. Deze toy strategie¨en worden weergegeven in figuur 6.6. Met deze toy strategie¨en wordt nu een hand history gegenereerd als volgt: de hand history bevat 1000 spelers die elk willekeurig ´e´en van de drie toy strategie¨en kiezen en deze strategie volgen. Deze spelers spelen nu tegen elkaar, en elke speler speelt een aantal handen, willekeurig gekozen tussen 1 en 1000.
6.3 Mixture model
83
1
1 P(fold) P(call) P(raise)
0.8
1 P(fold) P(call) P(raise)
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0
0
0.2
0.4 0.6 E[HS]
0.8
1
0
0
0.2
0.4 0.6 E[HS]
0.8
P(fold) P(call) P(raise)
0.8
1
0
0
0.2
0.4 0.6 E[HS]
0.8
1
Figuur 6.7: De strategie¨en van de drie mixture-componenten na het trainen op de dataset waarin spelers elk ´e´en van de drie toy-strategie¨en gebruiken. De probabiliteiten zijn weergegeven alsof alle drie de acties mogelijk zijn. Op de resulterende hand history kan een mixture model nu getraind worden. Er worden drie mixture-componenten gebruikt. De modellen gebruikt voor de mixture componenten zijn dezelfde als het “E[HS]-histogram” bucket abstractie model dat gebruikt werd om de gradient descent methode te testen. De getrainde mixture componenten van het resulterende mixture model worden weergegeven in figuur 6.7. Het is duidelijk dat de getrainde strategie¨en zeer nauw aansluiten bij de toy strategie¨en. In dit eenvoudige en onrealistische voorbeeld is het mixture model dus zeer goed in staat om de onderliggende “clusters” van strategie¨ n in de hand history te herkennen. Realistische hand history Dat de methode voor dit eenvoudig voorbeeld werkt impliceert echter niet dat er voor de realistische hand history ook een nuttig mixture model zal berekend worden. Er moet dus nagegaan worden wat de capaciteit is om een accuraat model op te bouwen van de strategie van een tegenstandre op basis van slechts een klein aantal, stel n, observaties over de tegenstander. Dit gebeurt als volgt: Een willekeurig spel wordt geselecteerd uit de hand history. Deze hand history mag uiteraard niet overlappen met de hand history die gebruikt werd om het mixture model te trainen. Uit dit spel wordt willekeurig ´e´en van de deelnemende spelers geselecteerd. Als deze speler minder dan n handen in de hand history heeft, dan begint men opnieuw. Anders worden de n vorige spellen van die speler geselecteerd uit de hand history. Het model moet nu op basis van deze n handen een zo accuraat mogelijk model bouwen van
84 de tegenstander. Men meet dan de log likelihood van het gekozen spel volgens het model. Hoe kleiner de gemiddelde negatieve log likelihood over meerdere samples, hoe beter het model in staat is om een gemiddelde tegenstander te modelleren met n observaties. Dit is een taak waarvoor het mixture model uitermate geschikt is. De n handen worden gebruikt om de responsibilities van de speler te berekenen, en het model van de tegenstander is dan een gewogen gemiddelde van de mixture componenten volgens deze responsibilities. De mixture componenten die hiervoor gebruikt worden zijn neurale netwerken, aangezien deze het beste bleken in staat te zijn om een generiek model van de hand history op te bouwen. Daarnaast worden ook bucket abstracties gebruikt als mixture componenten. In beide gevallen werden 10 mixture componenten gebruikt. Deze gemiddelde negatieve log-likelihoods van de modellen na het observeren van n handen worden weergegeven in functie van n in figuur 6.8. Ter vergelijking worden ook de actievoorspellende opponent modeling componenten van Vexbot (zie sectie 3.4) en de MCTS-bot (zie sectie 3.8) weergegeven in deze figuur. De Vexbot berekent voor de n geobserveerde spellen in verschillende context trees de histogrammen over de geobserveerde acties, en gebruikt in zijn voorspelling een gewogen gemiddelde van deze histogrammen. De MCTSbot meet in de n spellen een aantal statistieken, zoals de bet-frequentie van de speler, en gebruikt dit als features. Aangezien enkel de acties en kaarten van 1 van de spelers meegerekend worden, zijn de waarden in deze grafiek ongeveer de helft van deze uit de vorige secties, waar de log likelihood van de acties en kaarten van beide spelers worden berekend. Uit deze figuur blijkt duidelijk dat als er nog maar minder dan 100 handen gezien zijn van een bepaalde speler, dat dan het mixture model de acties van deze speler beter kan voorspellen dan zowel Vexbot als de MCTS-bot, zowel met de neurale netwerken als met de bucketing abstracties als mixture componenten. Daarnaast kan vastgesteld worden dat opnieuw de neurale netwerken deze hand history beter kunnen modelleren, voor elke waarde van n.
6.4
Conclusie
In dit hoofdstuk werden de technieken die in de vorige hoofdstukken werden voorgesteld experimenteel gecontroleerd. Er werd vastgesteld de gradient descent methode op een
6.4 Conclusie
85
Figuur 6.8: Gemiddelde negatieve log likelihood met 95%-betrouwbaarheidsintervallen na het observeren van de n vorige spellen van een speler voor verschillende modellen. Enkel de actie-voorspellende componenten van Vexbot en de MCTS-bot werden gebruikt.
86 hand history die voortgebracht werd door een eenvoudige strategie inderdaad convergeert naar een model dat deze genererende strategie zeer dicht benadert. Daarnaast werd ook vastgesteld dat als de spelers in een hand history elk ´e´en van drie mogelijke eenvoudige strategie¨en volgen, dat dan de mixture componenten in een mixture model met 3 componenten convergeren naar deze drie strategie¨en. Daarnaast werden voor realistische hand histories, gespeeld door menselijke pokerspelers op iPoker, de voorgestelde technieken vergeleken met de opponent modeling componenten van enkele bestaande bots, waaronder Loki, Vexbot en de MCTS-bot. Hieruit werd geconstateerd dat uit alle onderzochte modellen de neurale netwerken getraind met de gradient descent-methode het best in staat zijn om een generiek model van de tegenstanders in een hand history op te bouwen. Tenslotte werd ook vastgesteld dat uit alle onderzochte modellen het mixture model met neurale netwerken als mixture componenten het best in staat is om een tegenstander waarvan men slechts een klein aantal handen gezien heeft te modelleren.
BESLUIT EN MOGELIJK VERDER ONDERZOEK
87
Hoofdstuk 7 Besluit en mogelijk verder onderzoek Het modelleren van de strategie¨en van pokerspelers die men slechts een klein aantal spellen heeft zien spelen is een moeilijk maar interessant probleem. Het feit dat de kaarten die de speler had niet getoond worden als de speler gefold heeft zorgt ervoor dat vele machine learning technieken niet rechtstreeks toepasbaar zijn. In dit werk werd een nieuwe techniek voorgesteld die in staat is om een model van de strategie van een speler op te bouwen op basis van een hand history, een aantal spellen die men de speler heeft zien spelen. Deze methode is echter enkel toepasbaar op modellen met enkel continue re¨ele parameters waarvan de parti¨ele afgeleiden naar de parameters van de log likelihood kunnen berekend worden. Deze twee vereisten zorgen ervoor dat een grote klasse van modellen niet rechtstreeks toepasbaar zijn, zoals regressiebomen, Support Vector Machines, enzovoort. Het is niet duidelijk of het mogelijk is om de voorgestelde techniek aan te passen om dergelijke modellen te trainen. Dit kan mogelijk zijn door de parameterupdate met de gewogen som van parti¨ele afgeleiden te vervangen door meerdere parameterupdates, ´e´en per mogelijk hand van de speler, waarbij het grootte van de update de kans is dat het model geeft aan dat hand. Of deze techniek ondanks de discontinu¨ıteiten in de parameterruimte toch de strategie van de tegenstander zou kunnen schatten, zou nog moeten onderzocht worden in toekomstig onderzoek. Daarnaast wordt in de methode vaak verondersteld dat de private kaarten van de spelers onafhankelijk zijn van elkaar. Dit is in Texas Hold’em echter niet het geval, waardoor er een bias ontstaat op de trainingsmethode. Deze bias is waarschijnlijk zeer klein, en werd niet teruggevonden in de empirische resultaten, maar als er een manier gevonden zou worden
88 om die strategie¨en kan trainen zonder deze veronderstelling, en zonder dat het algoritme daardoor ongeveer 1000 keer trager loopt, dan zou dit een mogelijke verbetering zijn ten opzichte van de huidige techniek. Een tweede methode die werd voorgesteld in dit werk is in staat om een mixture model van strategie¨en op te bouwen. Dit mixture model is zeer nuttig als men wenst de strategie van een speler met zeer weinig informatie te modelleren. Het enige dat immers nog geschat moet worden is hoe veel de speler aansluit bij elk van de mixture componenten, niet de vele parameters van de complexe strategie¨en. De gradient descent methode is nuttig om de strategie van een speler te schatten als men de speler vele duizenden spellen heeft zien spelen. Het mixture model is vooral nuttig voor een speler te modelleren waarvan men minder dan 100 handen heeft gezien. Geen van de twee technieken zal echter uitstekend werken voor een speler waarvan men ongeveer duizend handen gezien heeft. Deze situatie komt in de praktijk weinig voor, maar toch kan het interessant zijn om een methode te ontwikkelen die op dit probleem uitblinkt. Een mixture model met zeer veel componenten zal een zeer grote hand history nodig hebben om op te trainen. En als de parameters van een mixture model als startpunt van de gradient descent methode gebruikt worden zal men moeten opletten voor overfitting. Een mogelijke manier om dit probleem aan te pakken zou kunnen zijn om een methode gebaseerd op principale-componentenanalyse toe te passen. In plaats van mixture componenten worden dan de voornaamste orthogonale “richtingen” berekend waarin de strategie¨en veranderen. Een voorbeeld van zo’n richting zou kunnen overeenkomen met of de speler tight of loose speelt. Tenslotte werd in het merendeel van deze thesis verondersteld dat de strategie van de tegenstander statisch is. Een mogelijke manier om het mixture model te gebruiken voor dynamische spelers te modelleren werd kort voorgesteld in sectie 5.6 maar niet verder onderzocht. Aangezien vele mensen geen statische strategie volgen, kan het zeer nuttig zijn om de dynamische aspecten van de manier waarop de mensen gemiddeld spelen te modelleren. Sommige mensen gaan bijvoorbeeld gemakkelijk “on tilt” en spelen zeer slecht nadat ze plotseling veel geld verliezen. Als er kan gemodelleerd worden wanneer een speler waarschijnlijk on tilt is, kan er meer geld gewonnen worden dan een statische opponent modelling zou kunnen. Er is dus nog zeer veel onderzoek mogelijk naar het modelleren van tegenstanders in poker. Met de voorgestelde technieken is het mogelijk om een nieuwe klasse van modellen op te
BESLUIT EN MOGELIJK VERDER ONDERZOEK
89
bouwen op een manier die voorheen niet mogelijk was, maar deze technieken formuleren geen finaal antwoord op hoe de strategie¨en van tegenstanders moeten gemodelleerd worden. Poker, en meer bepaald opponent modeling, blijft dus een zeer interessant en veelbelovend onderzoeksdomein.
90
LIJST VAN FIGUREN
Lijst van figuren 4.1 4.2
Voorbeeld van een neuraal netwerk . . . . . . . . . . . . . . . . . . . . . . Twee veelgebruikte activatiefuncties . . . . . . . . . . . . . . . . . . . . . .
6.1
Grafiek van de probabiliteiten van de voorbeeldstrategie gedefini¨eerd door vergelijking 6.1.1, als alle drie de acties mogelijk zijn. . . . . . . . . . . . . Histogram van de geobserveerde actiefrequenties van de toy strategie in functie van E[HS]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Model van de toy strategie na trainen. Probabiliteitstriples zijn weergegeven alsof alle drie de acties mogelijk zijn. . . . . . . . . . . . . . . . . . . . . . Negatieve log likelihood van de strategie na elke iteratie van het stochastic gradient descent algoritme, met 95%-betrouwbaarheidsintervallen. . . . . . Gemiddelde negatieve log likelihood met 95%-betrouwbaarheidsintervallen voor bucketing abstracties met verschillende k. . . . . . . . . . . . . . . . . Grafieken van de distributies over de mogelijke acties van de drie toy strategie¨en gebruikt om het mixture model te testen. De distributies zijn weergegeven alsof alle drie de acties mogelijk zijn. . . . . . . . . . . . . . . . . . . De strategie¨en van de drie mixture-componenten na het trainen op de dataset waarin spelers elk ´e´en van de drie toy-strategie¨en gebruiken. De probabiliteiten zijn weergegeven alsof alle drie de acties mogelijk zijn. . . . . . . Gemiddelde negatieve log likelihood met 95%-betrouwbaarheidsintervallen na het observeren van de n vorige spellen van een speler voor verschillende modellen. Enkel de actie-voorspellende componenten van Vexbot en de MCTS-bot werden gebruikt. . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 6.3 6.4 6.5 6.6
6.7
6.8
43 44
74 75 77 78 79
82
83
85
LIJST VAN TABELLEN
91
Lijst van tabellen 1.1
Rangschikking van handen in poker . . . . . . . . . . . . . . . . . . . . . .
4
4.1
Features gebruikt voor het neurale netwerk in Poki . . . . . . . . . . . . .
47
6.1
Gemiddelde negatieve log likelihood van de validatie hand history voor elke van de onderzochte modellen, gemeten in bits. . . . . . . . . . . . . . . . .
80
92
BIBLIOGRAFIE
Bibliografie [1] D. Billings, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron. Approximating game-theoretic optimal strategies for full-scale poker. In International Joint Conference on Artificial Intelligence, pages 661–668, 2003. [2] D. Billings, A. Davidson, T. Schauenberg, N. Burch, M. Bowling, R. Holte, J. Schaeffer, and D. Szafron. Game tree search with adaptation in stochastic imperfect information games. In In Computers and Games, pages 21–34. Springer-Verlag, 2004. [3] D. Billings and M. Kan. A tool for the direct assessment of poker decisions. The International Computer Games Association Journal, 29(3):119–142, Oct. 2006. [4] D. Billings, J. Schaeffer, and D. Szafron. Opponent modeling in poker. pages 493–499. AAAI Press, 1998. [5] M. Bowling, M. Johanson, N. Burch, and D. Szafron. Strategy evaluation in extensive games with importance sampling. In Proceedings of the 25th international conference on Machine learning, ICML ’08, pages 72–79, New York, NY, USA, 2008. ACM. [6] A. Davidson. Opponent modeling in poker: Learning and acting in a hostile and uncertain environment. Technical report, 2002. [7] A. Davidson, D. Billings, J. Schaeffer, and D. Szafron. Improved opponent modeling in poker. pages 493–499. AAAI Press, 2000. [8] M. Johanson. Robust strategies and counter-strategies: Building a champion level computer poker player. Master’s thesis, University of Alberta, 2007. [9] M. Johanson, M. Zinkevich, and M. Bowling. Computing robust counter-strategies. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2007.
BIBLIOGRAFIE
93
[10] L. Kocsis and C. Szepesv´ari. Bandit based monte-carlo planning. In ECML-06. Number 4212 in LNCS, pages 282–293. Springer, 2006. [11] H. W. Kuhn and A. W. Tucker. Contributions to the Theory of Games. Princeton University Press, 1950. [12] J. Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100(1):295– 320, 1928. [13] M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994. [14] D. R. Papp. Dealing with imperfect information in poker. Master’s thesis, University of Alberta, Edmonton, Alta., Canada, 1998. UML Order No. GAXMQ–34401. [15] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Neurocomputing: foundations of research. chapter Learning representations by back-propagating errors, pages 696–699. MIT Press, Cambridge, MA, USA, 1988. [16] J. Schaeffer, D. Billings, L. Pe˜ na, and D. Szafron. Learning to play strong poker. In Learning in Games, pages 225–242. Nova Science Publishers, 1999. [17] G. Van Den Broeck, K. Driessens, and J. Ramon. Monte-carlo tree search in poker using expected reward distributions. In Proceedings of the 17th European conference on Machine Learning, pages 289–293, 2006. [18] K. Waugh, D. Schnizlein, M. Bowling, and D. Szafron. Abstraction pathologies in extensive games. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS ’09, pages 781–788, Richland, SC, 2009. International Foundation for Autonomous Agents and Multiagent Systems. [19] K. Waugh, M. Zinkevich, M. Johanson, M. Kan, D. Schnizlein, and M. H. Bowling. A practical use of imperfect recall. In SARA, 2009. [20] M. Zinkevich, M. Bowling, N. Bard, M. Kan, and D. Billings. Optimal unbiased estimators for evaluating agent performance. In In American Association of Artificial Intelligence National Conference, AAAI, pages 573–578, 2006.
