Decision Generalisation from Game Logs in No Limit Texas Hold'em

1 Introduction

In 2008 the Second Man-Machine Poker Competition was won by a computer poker robot named Polaris [Bowling et al., 2009]. Polaris challenged a group of professional human players to the game of limit Texas Hold'em, beating its competitors by a statistically significant margin. The success of Polaris can (at least in part) be attributed to the increasing popularity of Texas Hold'em poker as a research domain and advances in game theoretic equilibrium finding algorithms [Sandholm, Winter 2010; Rubin and Watson, April 2011]. Polaris's victory occurred in the game of limit Texas Hold'em, where the amount able to be wagered is restricted by pre-determined bet sizes. Today, the most popular variation of the game is no limit Texas Hold'em, where players' bet sizes are no longer restricted. This allows a player to wager any amount they wish (up to the total amount of chips they possess). This simple rule change has a profound effect on the nature of the game, as well as on the development of computerised agents that wish to handle the no limit betting structure. While the Polaris system was able to beat world-class human opposition in the game of limit Hold'em, nothing like Polaris's victory has been achieved in the more complicated domain of no limit Hold'em. In fact, it is only relatively recently that many researchers have shifted their attention to the more complicated domain of no limit Texas Hold'em [Schnizlein et al., 2009; Van den Broeck et al., 2009; Gilpin et al., 2008].

∗The paper on which this extended abstract is based was the recipient of the best application paper award of the 2011 International Conference on Case Based Reasoning [Rubin and Watson, 2011].

Our previous research has focused on the techniques of expert imitation to achieve strong performance in the domain of limit Texas Hold'em [Rubin and Watson, 2010]. In this current work, we apply the same principles of expert imitation and decision generalisation to the more complicated domain of no limit Texas Hold'em. For automated no limit poker agents, a non-trivial translation phase is required to map quantitative bet amounts into discrete betting categories. Furthermore, our approach requires the construction of metrics to determine similarity between complicated no limit betting sequences (without which no generalisation would be able to take place). Our approach allows the successful imitation of any designated expert player (artificial or human), given a large enough set of training data. We present results from the 2012 Annual Computer Poker Competition (ACPC), where our entry to the competition, SartreNL, achieved a 5th place finish in the no limit equilibrium run-off event 1 .

2 Background

In [Rubin and Watson, 2010] we focused on expert imitation via a case-based approach within the domain of limit Texas Hold'em. Expert decisions recorded from a set of training data were encoded into cases and playing decisions were made at runtime by searching a case-base. While we employ a similar framework for our current work, the transition to a no limit domain results in unique challenges that are not encountered in a limit poker environment. First, there is the issue of establishing a set of abstract betting actions that all real actions will be mapped into during game play. This is referred to as action abstraction and it allows the vast, continuous domain of no limit Hold'em to be approximated by a much smaller abstract state space. Second, given an established set of abstract actions, a translation process is required that determines how best to map real actions into their appropriate abstract counterparts, as well as a reverse translation that maps abstract actions back into appropriate real-world betting decisions.

1 http://www.computerpokercompetition.org

Both action abstraction and state translation are issues that are also required to be addressed in the construction of no limit ϵ-Nash equilibrium strategies via algorithmic game theory. A pair of strategies are said to be an ϵ-Nash equilibrium if either player cannot gain more than ϵ by deviating their strategy. An early attempt to construct a no limit Hold'em agent via game theoretic methods is described by Andersson [Andersson, 2006]. Andersson extended the procedures used to construct ϵ-Nash equilibrium-based limit poker agents [Billings et al., 2003] to the no limit domain.

Another no limit poker agent produced via game theoretic algorithms is Tartanian [Gilpin et al., 2008]. Tartanian was able to build models for much larger starting chip stacks than the work presented by [Andersson, 2006].

While our current work is required to deal with many of the same issues and challenges faced by ϵ-Nash Equilibrium strategies, the focus of our approach is more to do with expert imitation and investigating the generalisation of playing decisions from game traces.

3 Overview

Given a set of (artificial or real-world) training data, our agent SartreNL, is able to generalise the decisions recorded within the data by constructing and storing a collection of cases. Each case attempts to capture important game state information that is likely to have an impact on the final betting decision. Table 1 depicts a collection of attribute-value pairs that, when taken together, captures a particular game scenario. All attributes were selected by the authors, given their importance in determining a final betting decision.

Each case also records a solution. A solution is made up of two n-tuples, one which specifies action probabilities and another which specifies the average outcome of taking the observed action in the past. The entries within each tuple correspond to a particular betting decision. The entries within the action tuple must sum to one.

During game play values are assigned to each attribute and the previously stored collection of cases are searched for attributes with similar values. The case with the highest global similarity is assumed to be most similar to the current situation. Once a similar case has been retrieved a betting decision is made by re-using the tuples within that case's solution.

Each attribute-value pair is described in more detail below:

Hand Strength Bucket This is given by rolling out all possible combinations of community cards and determining the proportion of the time the player's hand wins against the set of all possible opponent holdings. Values are mapped into a discrete set of buckets that contain hands of similar strength.

Betting Sequence The betting sequence attribute is given by a string of characters where each character is an observed game action. As any betting value can be observed in the real game, a discrete set of abstract actions are chosen to represent real betting actions.

Stack Commitment The proportion of chips committed by a player, compared to the player's stack size. The stack commitment feature maps this value into one of N categories, where N is a specified granularity.

Board Texture The board texture attribute maps a collection of community cards to one of nine categories that highlight important information such as whether a straight or flush is possible.

4 Action Abstraction

Recall that abstraction is a concept used by game theoretic poker agents that derive ϵ-Nash equilibrium strategies for the game of Texas Hold'em. As the actual Hold'em game tree is much too large to represent and solve explicitly, it becomes necessary to impose certain abstractions that help restrict the size of the original game. For Texas Hold'em, there are two main types of abstraction:

1. Chance abstraction - which reduces the number of chance events that are required to be dealt with. This is typically achieved by grouping strategically similar hands into a restricted set of buckets.
2. Action abstraction - which restricts the number of actions a player is allowed to perform.

A typical abstraction such as: fcpa, restricts the allowed actions to: f - fold, c - call, p - bet the size of the pot a - allin (i.e. the player bets all their remaining chips). Given this abstraction, all actions are interpreted by assigning the actual actions into one of their abstract counterparts.

While SartreNL does not attempt to derive an ϵ-Nash equilibrium solution for no limit Hold'em, it is still required to define an action abstraction in order to restrict the number of actions allowed in the game and hence reduce the state space. SartreNL uses the following action abstraction: fcqhipdvta, where each entry refers to different discrete betting categories as follows: fold (f ), call (c), raise quarter pot (q), raise half pot (h), raise three quarter pot (i), raise pot (p), raise double pot (d), raise five times pot (v), raise ten times pot (t), all-in (a).

5 Translation

Given that all bets need to be mapped into abstract actions, a translation process is required to define the appropriate mapping. [Schnizlein et al., 2009] formalise two types of translation: hard translation and soft translation.

• Hard Translation: is a many-to-one mapping that maps an unabstracted betting value into an abstract action based on a chosen distance metric. Given a unique unabstracted betting value, hard translation will always map this value into the same abstract action. A disadvantage of hard translation is that an opponent can exploit this mapping simply by selecting particular betting values.
• Soft Translation: is a probabilistic state translation that uses normalised weights as similarity measures to map an unabstracted betting value into an abstract action. The use of a probabilistic mapping ensures that soft translation cannot be exploited like hard translation can.

SartreNL uses both hard and soft translation. The type of translation that takes place differs depending on where translation occurs within the system. The exact details of the translation used within the different areas of the system are now presented.

Define A = {q, h, i, p, d, v, t, a} to be the set of abstract betting actions. Note that the actions f and c are omitted as these require no mapping.

1. During case-base construction, where hand history logs from previously played hands are encoded into cases, SartreNL uses the hard translation function Th : ℜ → A, as follows:

where b ∈ ℜ is the proportion of the total pot that has been bet in the actual game and a, c ∈ A are abstract actions that map to actual pot proportions in the real game and a <= b < c. The fact that hard translation has the capability to be exploited is not a concern during casebase construction. Hard translation is used during this stage to ensure that re-training the system with the same hand history data will result in the same case-base.

1. During actual game play SartreNL is required to map opponent betting actions (as well as its own actions) to abstract categories. Observant opponents have the capability to exploit deterministic mappings during game play, hence SartreNL uses a soft translation function for this stage, Ts : ℜ → A, given by the following probabilistic equations:

where once again, b ∈ ℜ is the proportion of the total pot that has been bet in the actual game and a, c ∈ A are abstract actions that map to actual pot proportions in the real game and a <= b < c. Note that when b = a, P(a) = 1 and P(c) = 0 and when b = c, P(a) = 0 and P(c) = 1. Hence, a betting action that maps directly to an abstract action in A does not need to be probabilistically selected. On the other hand, when b ̸= a and b ̸= c, abstract actions are chosen probabilistically. Also, notice that in Equations (2) and (3), P(x) + P(y) ̸= 1 and hence a final abstract action is probabilistically chosen by first normalising these values.

1. The final place that translation is required is when SartreNL has determined an appropriate abstract action to play. A reverse mapping is then required to map the abstract action into an appropriate real betting value, given the current game conditions. SartreNL uses the following function to perform reverse translation, Tr : A→ℜ:

where a ∈ A and a′ ∈ ℜ is the real value corresponding to abstract action a and ∆a′ is some random proportion of the bet amount that is used to ensure SartreNL does not always map abstract actions to their exact real world counterparts. For example, when a′ = 100 and ∆ = 0.3, SartreNL could bet any amount between 70 - 130 chips.

6 Similarity

In order to generalise no limit betting decisions, it is first required to locate similar scenarios for which solutions have been recorded in the past. Given a target case, t, that describes the immediate game environment, a source case, s ∈ S, where S is the entire collection of previously recorded cases and a set of features, F , global similarity is computed by summing each feature's local similarity contribution, simf , and dividing by the total number of features:

We now present the local similarity metrics (simf ) required in order to generalise betting decisions from a collection of data.

6.1 Hand Strength Bucket

The following metric is used to determine similarity between two hand strength buckets (f1, f2).

Here, T refers to the total number of buckets that have been defined, where f1, f2 ∈ [1, T] and k is a scalar parameter used to adjust the rate at which similarity should decrease. SartreNL uses values of T = 50 and k = 2.

6.2 Stack Commitment

The stack commitment metric uses an exponentially decreasing function.

where, f1, f2 ∈ [1, N] and N refers to the granularity used for the stack commitment attribute. This function was chosen as small differences between two stack commitment attributes (f1, f2) should result in large drops in similarity. SartreNL uses a granularity of N = 4.

6.3 Betting Sequence

For two betting sequences to be considered similar each sequence must contain the same number of elements and any calls (c) or all-in bets (a) that occur within sequence S1 must also occur at the same location in sequence S2. Exactly how dissimilar two individual bets are to each other can be quantified by how far away from each other they occur within the bet discretisation string: qhipdvt, e.g. δ(h, i) = 1 and δ(q, t) = 6.

For two betting sequences S1, S2 overall similarity is determined by (8):

where the notation S1,i, S2,i refers to the ith character in the betting sequences S1 and S2, respectively and α is some constant rate of decay.

6.4 Board Texture

To determine similarity between board texture categories a similarity matrix of hand picked values was derived by the authors.

7 Results

A version of the system described above was submitted to the 2012 Annual Computer Poker Competition. Our entry to the competition was trained on data from the best no limit agent of the 2011 competition. The ACPC is the premier computer poker event and has been held each year at either AAAI or IJCAI conferences since 2006. Entrance into the competition is open to anyone and the agents submitted typically represent the current state-of-the-art in computer poker.

Table 2 presents a cross-table of results between competitors at the 2012 heads-up no limit competition. A green cell indicates a win for the row player and a red cell indicates a loss for that player. Cells with a lighter background represent matches that were not statistically significant. The figures presented in Table 2 are in milli big blinds per hand (mb/h), where the total number of big blinds won are divided by the number of hands played, and the result is multiplied by 1000.

Table 2 presents the final results of the instant run-off competition. The instant run-off competition uses a recursive winner determination algorithm that repeatedly removes the agents that performed the worst against a current pool of players.

8 Conclusion

Our results support the idea that generalising decisions via expert imitation has the ability to produce strong, sophisticated strategies in complex, imperfect information environments. Table 2 shows that these strategies can lead to successful performance compared with alternative approaches. In particular, the SartreNL system produced by the framework achieved a 5th place finish out of 11 competitors at the 2012 ACPC no limit, instant run-off competition.