Opponent Modeling in Poker

From PRLT
Jump to: navigation, search
PokerPRLT.png

This project aims at introducing opponent modeling techniques into reinforcement learning algorithms for Texas Hold'em Poker.

Introduction

In this years, Artificial Intelligence research has shifted its attention from fully observable environments such as Chess to more challenging partially observable ones such as Poker.

Up to this moment research in this kind of environments, which can be formalized as Partially Observable Stochastic Games, has been more from a game theoretic point of view, thus focusing on the pursue of optimality and equilibrium, with no attention to payoff maximization, which may be more interesting in many real-world contexts.

On the other hand Reinforcement Learning techniques demonstrated to be successful in solving both fully observable problems, single and multi-agent, and single-agent partially observable ones, while lacking application to the partially observable multi-agent framework.

This research aims at studying the solution of Partially Observable Stochastic Games, analyzing the possibility to combine the Opponent Modeling concept with the well proven Reinforcement Learning solution techniques to solve problems in this framework, adopting Poker as testbed.

POSG Framework

A Partially Observable Stochastic Games can be formally described as a tuple

<math>\mathcal{}</math>

where:

  • <math>\mathcal{I}</math> is a set of agents indexed 1, <math>\ldots</math>, n
  • <math>\mathcal{S}</math> is a set of states of the world
  • <math>\mathcal{\textbf{A}} = \times_{i \in I} \mathcal{A}_{i}</math> is the set of joint actions, where <math>\mathcal{A}_{i}</math> is the set of actions of the agent i and <math>\textbf{a}_{i} = <a_1, \ldots , a_n></math> is a joint action
  • <math>\mathcal{T:\textbf{A} \times S \rightarrow} \Pi\mathcal{(S)}</math> is the state-transition function, which returns a probability distribution over world states, where <math>\mathcal{T}</math>(s,<math>\textbf{a}</math>,s') <math>= P(S_{t+1} = </math>s' <math>\mid S_{t} = </math>s,<math>\textbf{A}_{t} = \textbf{a})</math> is the probability of ending in the state s, starting from the state s and given the joint action <math>\textbf{a}</math>
  • <math>\mathcal{R}_{i}\mathcal{:S \times \textbf{A} \rightarrow} \mathbb{R}</math> is the reward function for the agent <math>i</math>, which returns the immediate reward <math>R_{t}^{i}=</math>r gained by the <math>i</math>-th agent when joint action <math>\textbf{A}_{t-1}=\textbf{a}</math> is performed in the state <math>S_{t-1}=</math>s at time <math>t</math>
  • <math>\mathbf{\Omega} = \times_{i \in I} \Omega_{i}</math> is the set of joint observation, where <math>\Omega_{i}</math> is the set of observations the agent <math>i</math> can experience of the world
  • <math>\mathcal{\textbf{O}:S \times \textbf{A}}\times \mathbf{\Omega} \rightarrow [0,1]</math> is the observation function, which returns a probability over joint observations, where <math>\mathcal{O}_{i} (s',\textbf{a},o_{i}) = P(\Omega_{t}^{i} = o_{i} \mid S_{t} = </math>s',<math>\textbf{A}_{t-1} = \textbf{a})</math> is the probability for the i-th agent of experiencing the observation <math>o_{i}</math>, given the performed joint action

Poker: A Formal Representation

Poker, in particular its Texas Hold’em variant, is a card game that proceeds in stages. In each stage, active players are dealt cards (some of which, called common cards, are dealt face up for all players to see, while others are dealt face down to each player to keep private). Players then wager against each other that their hand of cards is the best (or will be the best at the end of the game). As each player knows only her cards and common ones, with no information over opponents’ ones, poker is an example of an imperfect information domain. In addition, as players have no control over which cards are dealt, poker is also an example of a stochastic domain.

To remain active in the game, and therefore to proceed through the stages of play, a player must match the amount of money wagered by each of her opponents. If one player makes a wager that no opponent matches, then the game ends immediately with that player winning all the wagered money (the pot) regardless of her cards. Otherwise, play continues until there are no stages left in the game, and at that point all the active players enter into a showdown. During the showdown, all active players reveal their hidden cards and the player with the highest ranked poker hand wins the pot (equally ranked hands split the pot).

Let’s see a sample Texas Hold’em play to understand game mechanics.

Compulsory bets : Player A is the dealer. Player B, to A's left, posts a small blind of $1, and player C posts a big blind of $2.

Pre-flop :A deals two hole cards face down to each player, beginning with B and ending with herself. Player D must act first because she is the first player after the big blind. She cannot check, since the $2 big blind plays as a bet, therefore she folds. A calls the $2. B adds an additional $1 to her $1 small blind to call the $2 total. C's blind is "live", therefore she has the option to raise here, but she checks instead, ending the first betting round. The pot now contains $6, $2 from each of three players.

Flop : A now deals the flop of three face-up community cards, 9<math>\clubsuit</math> K<math>\clubsuit</math> 3<math>\heartsuit</math>. On this round, as on all subsequent rounds, the player on the dealer's left begins the betting. In this case it is B who checks. C opens for $2, D has already folded and A raises another $2 (puts in $4, $2 to match C and $2 to raise), making the total bet now facing B $4. She calls (puts in $4, $2 to match C's initial bet and $2 to match A's raise). C calls as well, putting in her $2. The pot now contains $18, $6 from the last round and $12 from three players this round.

Turn : A now deals the turn card face up. It is the 5<math>\spadesuit</math>. B checks, C checks, and A checks; the turn has been checked around. The pot still contains $18.

River : A deals the final river card, the 9<math>\diamondsuit</math>, making the final board 9<math>\clubsuit</math> K<math>\clubsuit</math> 3<math>\heartsuit</math> 5<math>\spadesuit</math> 9<math>\diamondsuit</math>. B bets $4, C calls, and A folds (A's holding was A<math>\clubsuit</math> 7<math>\clubsuit</math>; she was hoping the river card would be a club to make her hand a flush).

Showdown : B shows her hand of Q<math>\spadesuit</math> 9<math>\heartsuit</math>, so the best five-card hand she can make is 9<math>\clubsuit</math> 9<math>\diamondsuit</math> 9<math>\heartsuit</math> K<math>\clubsuit</math> Q<math>\spadesuit</math>, for three nines, with a king-queen kicker. C shows her cards of K<math>\spadesuit</math> J<math>\heartsuit</math>, making her final hand K<math>\clubsuit</math> K<math>\spadesuit</math> 9<math>\clubsuit</math> 9<math>\diamondsuit</math> J<math>\heartsuit</math> for two pairs, kings and nines, with a jack kicker. B wins the showdown and the $26 pot.

Poker as a POSG

It is possible to describe poker as a POSG, where the state of the world is given by the cards given to each player, by the community cards, the pot, the current stage and the raises history of each player in each stage.

Each player have usually at least three actions available at each step. They can leave the game by folding, losing all they have bet up to this moment, they can agree to another player bet by calling, or they can increase the amount of money bet by betting/raising. In some poker variant it is also possible to change some cards, but we focus our attention on Texas Hold’em variant, where no card changing is possible.

When there is only a player left in game, she wins the pot, so her payoff will be positive and it will be the sum of all the money bet in the game, while other players will have a negative payoff equal to the amount of money they invested in that play. When more than a player is left at the end of the game, their cards are ranked and those handling the best hand split the pot.

The observations for each player are built from her private cards, community cards, pot, turn and raises histories. No information is available about other players’ cards.

Experimental Framework Description

For our experiments we have carried out several millions Texas Hold'em heads-up game simulation.

In all this experiments, the state variables available to each agent are:

  • Stage: The current stage of the game, which can assume four values
    • pre-flop: each agent receives her private cards and no public cards have been drawn
    • flop: the first tree public cards are drawn
    • turn: the fourth public card is drawn
    • river: the fifth public card is drawn
  • Raise Left: The number of raises left in the current stage, which can assume a value between 0 and 4. During the pre-flop its maximal value is limited to 3. This is obviously a variable applicable only to limit games
  • Seat: The position of the agent in the table
  • Hand Strength: A value representing the agent hand strength, which is the conditional probability that her hand would be the strongest one at showdown and thus win or tie, given her private cards and the public ones, calculated considering a tie as half a victory:<math>HS=\frac{\#Wins}{\#\textit{Possible Hands}} + 1/2*\frac{\#Tie}{\#\textit{Possible Hands}}</math>
  • Average Opponent Hand Ranking: A value between 1 and 7462 representing the average opponent hand rank, being the hand rank a value that identifies the relative strength of a 5 cards hand. Even thought there are <math>{52 \choose 5}=\frac{52!}{5!(52-5)!} = 2598960</math> unique 5 hand which can be drawn from a 52 cards deck, they can be collapsed to only 7462 equivalent hands. For example there are 24 different ways to create an Aces over Kings Full House hand, but they have all the same strength
  • Opponent Bets: The number of bets done by the opponent during the current game. Its value can range from 0 to 8 in a limit game, while being virtually unbounded in a no-limit game
  • Opponent Stage Bets: The number of bets done by the opponent during each stage of the game
  • Opponent Start Check: Whether the opponent had started the current game with a check
  • Opponent Stage Start Check: For each stage, whether the opponent had started it with a check
  • Opponent Pot: The amount of money invested by the opponent in the game
  • Opponent Last Action: Last action performed by the opponent

While each agents can perform three possible actions each turn:

  • Fold: An agent may choose to abandon the game, losing all the money she has invested up to this moment
  • Call: An agent may choose to stay in game, paying the bets that have been done by the opponent preceding her if any was done
  • Raise: Bet more money in the game. This is possible only if there are raises left for the current stage of the game in limit games or if the player hasn't already gone all-in in a no-limit game. In no-limit an agent can raise whatever amount of money he wants.

Ongoing work

Resources

Temporary_Bots

People involved

  • Andrea Bonarini, Full Professor
  • Alessandro Lazaric, PhD Student
  • Marcello Restelli, PhD
  • Mario Lozza, Master Student
  • Mario Quaresimale, Master Student

== Publications ==