Computer Poker: Agents and Approaches – Project topics materials

Get Complete Project Material File(s) Now! »

Abstractions

The combination of game tree abstractions and the use of linear programming methods has resulted in the construction of strong poker programs that approximate equilibrium solutions [18, 39, 6]. Each of these programs requires the use of a combination of abstractions to reduce the size of the game tree.
In general, there are two categories of abstraction, those that respect the original strategic complexity of the game (lossless abstractions) and those that compromise it (lossy abstractions). The following example will highlight the differences between the two. Consider the preflop stage of the game where each player is dealt two cards that only they can see. Out of a deck of 52 cards the first player is dealt 2 cards at random resulting in a total of 1,624,350 possible combinations (see Figure 2.5). Imagine for one of these combinations that player one is dealt the two cards A~K~ and player two is dealt T|J. Now, during the preflop stage of the game there is no strategic difference between the hands A~K~, AK, A|K|or A}K}.
The only difference between these hands are the suits and at present the suit information has no bearing on the quality of the hand. All that matters is whether the hand is of the same suit or not. Hence, an abstraction can be used where the hands A~K~, AK, A|K| and A}K} could all be represented as the single hand AKs (where s stands for suited). The same holds for player two who was dealt T|J, this player could have equivalently been dealt T~J, T}J|, T~J} etc. the only difference is that the two cards are not of the same suit, so they could all be represented as TJo (where o stands for off-suit). In total there are 169 equivalence classes of this formfor all two card combinations. Using this abstraction technique can drastically reduce the number of preflop card combinations in the game tree from 1,624,350 to 28,561. The important point is that no strategic information has been lost to achieve this reduction. The game tree has been reduced in size simply by reclassifying hands in a more concise manner.
Unfortunately, lossless abstractions alone do not always provide the reduction in size required to solve large scale games. This results in the need for lossy abstractions that will affect the original strategic integrity of the game to some degree. Furthermore, the example presented above only works for one stage of the poker game tree, i.e. the preflop. Once play transitions to the next stage (the flop) suit information is required and this information has now been lost. A better abstraction would be one that is able to be used throughout the entire game tree. Bucketing (also known as binning) is a powerful abstraction that has been used within many poker agents [109, 18, 39, 6]. Bucketing is a lossy abstraction that groups categories of hands into equivalence classes. One possible method of bucketing groups hands based on the probability of winning at showdown against a random hand. This is given by enumerating all possible combinations of community cards and determining the proportion of the time the hand wins.
This is referred to as roll-out hand strength or expected hand strength (E[HS]). Hands can then be grouped by assigning them into a particular bucket which holds hands with the same E[HS]. For example, the use of five buckets would create the following categories:
[0.0 – 0.2] [0.2 – 0.4] [0.4 – 0.6] [0.6 – 0.8] [0.8 – 1.0] and group all hands with the same winning probabilities into the same bucket. The abstract game model is nowconstructed using buckets rather than cards. To complete the abstract game model, the final requirement of bucketing is to determine the probability of transitioning between different buckets during each stage of play.
Abstraction via bucketing can either be performed manually, by the system designer, or the process can be automated. Creating a manual abstraction allows the designer control over bucket types and boundaries, but may be costly when re-creating an abstraction. On the other hand, automated abstraction, groups similar hands into buckets that are determined by the algorithm itself. Automated abstraction typically allows the specification of some granularity to determine how fine (or coarse) to make a particular abstraction. Finer abstractions lead to larger models that are required to be solved.

READ Social networking sites

Expectation-Based Abstraction

An abstraction that is derived by bucketing hands based on expected hand strength is referred to as an expectation-based abstraction. Johanson [55] points out that squaring the expected hand strength (E[HS2]) typically gives better results, as this assigns higher hand strength values to hands with greater potential. A hand’s potential refers to its ability to improve in strength, given future community cards. Typically in poker, hands with similar strength values, but differences in potential, are required to be played in strategically different ways [111].
The example above presented one standard procedure for automatically grouping hands by placing them into buckets, based on a predefined partition of winning probabilities. One problem with this approach is that some buckets will contain many hands, while others may contain very few. Further bucketing procedures attempt to improve upon the standard bucketing approach presented above. Nested bucketing attempts to further accommodate for the effects of hand potential. Nested bucketing begins like standard bucketing, by combining hands into buckets that have similar E[HS2] values, however after the first bucketing stage a second bucketing stage splits each of the first buckets based on standard E[HS]. This is done in order to better distinguish between hands with high hand strength and hands with high potential.
Percentile bucketing is an automated bucketing technique that creates buckets that hold roughly the same amount of hands. Percentile bucketing modifies the hand strength boundaries used for each bucket, such that each bucket contains the same percentage of hands. For example, given 5 buckets for a betting round, the bottom 20% of hands would be assigned into the first bucket, the next 20% of hands assigned into the next bucket, and so on. The top 20% of hands would be assigned into the last bucket. History bucketing is a manual bucketing technique that allows finer control over bucket boundaries In history bucketing child buckets are individually determined for each parent bucket in the previous round. History bucketing makes use of the fact that some buckets have a greater probability of transitioning to particular buckets in the next round. For example, it is more likely that a bucket that represents high hand strength in one round, will transition to a high hand strength bucket in the next round. Correspondingly, it is likely that a low hand strength bucket will remain in a low hand strength bucket between rounds, rather than transitioning into a very high hand strength bucket. By modifying bucket boundaries, history bucketing allows finer control over how many hands can be mapped into a child bucket for each parent, resulting in an improved quality of abstraction, without increasing the number of buckets.

Potential-Aware Automated Abstraction

A separate automated abstraction method is potential-aware automated abstraction, developed by Gilpin and Sandholm at Carnegie Mellon University [45]. Expectation-based abstractions require information about hand potential to be encapsulated within a one-dimensional hand strength value, whereas potential-aware abstractions make use of multi-dimensional histograms to assign similar hands into buckets.

1 Introduction
1.1. Texas Hold’e
1.2. PerformanceMetrics & Evaluation
1.2.1. Types of Strategies
1.2.2. Performance Evaluators
1.3. Variance Reductio
1.4. Thesis Objectives
1.5. Thesis Contributions
1.6. Thesis Outline
2 Computer Poker: Agents and Approaches
2.1. Knowledge-Based Systems
2.1.1. Rule-Based Expert Systems
2.1.2. Formula-Based Strategies
2.1.3. Knowledge-Based Poker Agents
2.2. Monte-Carlo and Enhanced Simulation
2.2.1. Introduction
2.2.2. Simulation Example
2.2.3. Simulation-Based Poker Agents
2.3. Game Theoretic Equilibrium Solutions
2.3.1. Game Theory Preliminaries
2.3.2. Rock-Paper-Scissors Example
2.3.4. Abstractions
2.3.5. Near-Equilibrium Poker Agents
2.3.6. Iterative Algorithms for finding -Nash Equilibria
2.4. Exploitive Counter-Strategies
2.4.1. Imperfect Information Game Tree Search
2.4.2. Game-Theoretic Counter-Strategies
2.5. Alternative Approaches .
2.5.1. Evolutionary Algorithms and Neural Networks
2.5.2. Bayesian Poker
2.6. Summary
3 Case-Based Strategies in Computer Poker
3.1. Introduction
3.2. Case-Based ReasoningMotivation
3.3. Two-Player, Limit Texas Hold’em
3.3.1. Overview .
3.3.2. Architecture Evolution
3.3.4. Two-Player, Limit Texas Hold’em Experimental Results
3.4. Two-Player, No-Limit Texas Hold’em
3.5. Multi-Player, Limit Texas Hold’em
3.6. Concluding Remarks
4 Implicit OpponentModelling via Dynamic Case-Base Selection
4.1. Multiple Case-Bases
4.2. Expert Imitators
4.3. Combining Decisions
4.4. Methodology
4.5. Experimental Results
4.6. Concluding Remarks
5 Explicit OpponentModelling via Opponent Type Solution Adaptation
6 Strategy Switching via Case-Based Transfer Learning
7 Conclusions and FutureWork
Appendices