Game Theory in Practice

HEM red line

2011-10-27T02:09:00.005-04:00

So it seems like almost everyone has a fundamental misunderstanding about how the HEM red line works and what it does/doesn't do (and to be honest, I didn't really understand it myself until recently).

Common statements seen regularly on the 2+2 forums include:
"The red line is wrong because it is based on ICM, and ICM isn't correct."
"The red line is wrong because it doesn't take into account coolers or other forms of luck."
"The red line is wrong in merge sngs because it uses 65/35 payoffs while actual payoffs are 70/30."

This post will be pretty informal, but hopefully will convince you why all of these statements are essentially wrong. I say "essentially" because I will be ignoring card removal in the analysis; but card removal plays a pretty minor role in general, and it seems reasonable to ignore it.

Now, when assessing an EV-estimating function like the HEM red line, it will be useful to use two metrics:
1) Bias. An unbiased estimator of actual EV would have the same expectation as actual profits, and would equal actual profits in the limit.
2) Variance. A lower variance estimator will generally have smaller swings, and will make it easier to assess our performance with fewer samples.

Obviously we would like an estimator that is unbiased and low variance (there would be no point in using the red line if it didn't have lower variance than the green line/actual profits).

Now let's recall how the red line works in sngs. For each hand in which two players are all-in, an "EV diff" is computed. The hand EV diff equals the difference between the expected ICM payoff over the allin outcomes, and the ICM payoff of the outcome that actually occurs (so it will be negative when you are "lucky" and positive when you are "unlucky" with respect to ICM). If no two players are allin in a given hand, the hand EV diff is 0.

Here is an example: suppose 1000 starting stacks, $100 pre-rake buyin, 6max superturbo sng, 65/35 payouts, blinds at 50/100.
Initially the ICM value is $100 to everyone.
Suppose you get in a 60-40 in the first hand and win (SB vs BB).
The ICM value of a win is $186, while that of a loss is $0.
So your expected ICM payoff is 0.6*$186 + 0.4*$0 = $111.60
The ICM payoff the actual outcome (you winning) is $186.
So the hand EV diff will be $111.60 - $186 = -$74.4

Let EV-diff-total equal the sum of all the individual hand EV diffs. The total red line EV of the tournament will equal EV-diff-total plus your actual profit (i.e., the green line). So if your EV diff total is -$50 and you get a payout of $150 in the tournament, your red line will go up by $100 and green line will go up by $150 (minus the buyin + rake, for both lines).

So to recap, we have:
Red line EV = EV-diff-total + Green line EV

Let's call the green line EV our "WINNINGS," the red line our "SKILL" and the negative of the EV-diff-total our "LUCK."
So we have
WINNINGS = SKILL + LUCK
It should also be pretty obvious that E[LUCK] = 0, since it is solely due to the chance outcome of the allin (ignoring the card removal effect of other players who have folded). So we have E[WINNINGS] = E[SKILL]; i.e., the red line is an unbiased estimator of the green line. Interestingly, this doesn't really depend on whether ICM is "correct" or not; we would have E[LUCK] = 0 for any mapping, even really naive ones.

Let's consider the same 60-40 example from above, but assume we use an arbitrary value mapping that gives payoff P of winning the allin (and $0 for losing it). Then our expected payoff will be 0.6P. With probability 0.6, we will win the allin, and the EV hand diff will be 0.6P - P = -0.4P. With probability 0.4 we will lose the allin, and the EV hand diff will be 0.6P - 0 = 0.6P. So the expected value of the hand diff equals 0.6 * (-0.4P) + 0.4*(0.6P) = 0, and therefore E[LUCK] will equal 0. This is just one example, but the same reasoning will apply in general to arbitrary value mappings.

A really dumb value mapping however could produce a very high variance, which might make the red line less useful than the green line. However, any value mapping would produce an unbiased estimator of our actual EV; so for example, using 65/35 ICM payoffs when actual payoffs are 70/30 still produces an unbiased red line, which almost definitely has significantly lower variance than the green line. A better value mapping would just decrease variance, not bias.

So in conclusion, the current HEM red line algorithm (using ICM) is unbiased (ignoring card removal), but not necessarily minimal variance. Nonetheless, it has significantly lower variance than actual EV (the green line), and so is generally a very useful tool for evaluating performance.

Thanks to Prof. Mike Bowling at Alberta, and jukofyork from the 2+2 forums for helping me understand this better.

Work vs. play

2011-03-29T01:40:00.008-04:00

In my office at school I often go back and forth between playing poker and doing research; my friends sometimes joke around about how they are basically the same thing. I usually correct them; while much of my research applies to poker, there is a big difference between when I am playing poker and when I am actually doing research (i.e., working on projects that will lead to papers). It turns out that this is only sort of true and that my friends are kind of right; my poker playing has actually had a substantial and unique impact on my research.

My first main research project in grad school was on an algorithm for computing an approximate Nash equilibrium in 3-player poker endgames. It ended up resulting in two papers so far, and hopefully a journal paper if I can find time to write it up. I got the idea to work on this after playing thousands of poker tournaments; I think it's fair to say that there is a 0% chance I would have come up with this project idea if I didn't play poker myself.

My interest in poker also got me to browse the 2+2 poker forums, which among other things led me to this great book on poker theory. As it turned out, my next main research project involved significantly generalizing the main algorithm used throughout the book. Here is the conference version of that paper, and here is an extended tech report. This project is still in progress, and I've made some significant improvements since those versions.

For both projects I described above, my interest in poker led to the choice of topic; however, the actual research had very little to do with my poker playing. For one of my recent projects, the algorithm I came up with was actually based roughly on the strategy I use when playing. The main idea is to start with a strong, approximate-equilibrium strategy, and deviate from it to take advantage of specific observed weaknesses of opponents. I came up with an algorithm for two-player limit Texas Hold'em based on this reasoning which ended up exploiting weaker players significantly more than the equilibrium strategy did. This seems to be the first real work combing game-theoretic reasoning and opponent modeling in real time. Here is the conference version of the paper.

What is the lesson to take from all of this? Maybe in addition to grades, GRE scores, and recommendations, grad schools should also require applicants to submit relevant game-playing experience:) Seriously though, I do think that people with "nontraditional" backgrounds and experiences can sometimes bring a fresh new perspective to academic problems that people with traditional backgrounds can't. My favorite example is Persi Diaconis, a statistician at Stanford who dropped out of high school at age 14 to become a professional magician.

How much would you pay ...

2011-03-23T20:52:00.007-04:00

to play the following game? Suppose there is initially $1 in a pot, and at each time step I flip a coin; if it is heads, the amount in the pot doubles, and if it is tails then the game is over and you get to keep what is in the middle. The question is, what is the maximum amount you would pay to be able to play this game. Let's assume that there is no limit to how big the pot can get.

One obvious observation is that the value of the game is infinite. It is equal to
1/2 * $1 + 1/4 * $2 + 1/8 * $4 + ... = 1/2 + 1/2 + 1/2 + ... = infinity
So theoretically you will expect to win an infinite amount of money playing the game; this means you should be willing to pay a lot of money to play it right?

Let's assume your bankroll is B, and suppose you risked your entire bankroll on the game. Since the game has infinite value to you, your expected profits are still infinite and this would be a very +EV bet. On the other hand, 50% of the time you are left with $1 and lose your entire bankroll (minus 1). An additional 25% of the time you lose B-2. And so on. So even though this bet is very (infinitely) profitable, you lose a very large % of your bankroll most of the time.

Fortunately, investment theory provides a solution to this problem: you should take the bet that maximizes the expected utility of the outcome, where utility is logarithmic in wealth. What really matters is the rate of growth of your wealth, which must account for such possibilities as going broke; on the other hand, just looking at expected profits as we did above might lead to a significant probability of going broke and will not maximize your long-term wealth.

Now let's assume you are considering paying k to play the game. Using our new formulation, your expected utility would be

1/2 * log(B-k+1) + 1/4 * log(B-k+2) + 1/8 * log(B-k + 4) + ...
= sum_i=1^infinity [1/2^i * log(B - k + 2^(i-1))]

We should be willing to play the game for k if the value of this infinite sum exceeds log(B) -- our expected utility of not playing the game.

I did a simulation assuming a bankroll B = $100000, and determined that the maximum (integral) amount we would be willing to pay is $9. So interestingly, we are only willing to invest 0.009% of our bankroll to play this game despite the fact that it is worth infinity to us.

Coaching Principles and Strategies of Basketball

2011-03-01T23:25:00.004-05:00

I finally got around to reading Freakonomics recently, and just finished a section describing how the No Child Left Behind law incentivized teachers to cheat. Following this law, several cities enacted rules stipulating that schools with low performance on standardized tests were put on probation/shut down and teachers fired. Conversely, schools with good performances were given rewards, and specific teachers whose classes performed well were given bonuses. Not surprisingly, this system incentivized teachers to cheat in order to obtain better test performances for their class (e.g., by giving extra time to their students, giving away answers, or even changing students' answers after the test).

They then went on to describe a particularly humorous incident of teacher cheating at UGA:

"You might think that the sophistication of teachers who cheat would increase along with the level of schooling. But an exam given at the University of Georgia in the fall of 2001 disputes that idea. The course was called Coaching Principles and Strategies of Basketball, and the final grade was based on a single exam that had twenty questions. Among the questions:

How many halves are in a college basketball game?
a. 1
b. 2
c. 3
d. 4

How many points does a 3-pt. field goal account for in a basketball game?
a. 1
b. 2
c. 3
d. 4

What is the name of the exam which all high school seniors in the state of Georgia must pass?
a. Eye Exam
b. How Do the Grits Taste Exam
c. Bug Control Exam
d. Georgia Exit Exam

In your opinion, who is the best Division I assistant coach in the country?
a. Ron Jirsa
b. John Pelphrey
c. Jim Harrick Jr.
d. Steve Wojciechowski

If you are stumped by the final question, it might help to know that Coaching Principles was taught by Jim Harrick Jr., an assistant coach with the university's basketball team. It might also help to know that his father, Jim Harrick Sr., was the head basketball coach. Not surprisingly, Coaching Principles was a favorite course among players on the Harricks' team. Every student in the class received an A. Not long afterward, both Harricks were relieved of their coaching duties."

Whew

2011-01-07T17:03:00.001-05:00

So lately I've been playing some hyper-turbo satellite tournaments on Pokerstars. These tournaments have six players with entry fee $177.45+$3.55. Everyone starts with 10 BBs, and blinds double every 3 minutes (there are antes too). The top two finishers get a seat in a tournament worth $530, while the third place finisher gets $4.70: so basically just the top 2 finishers get paid, since the third place payoff is so tiny compared to the top two. This is a pretty significant change from how these tournaments ran last year, where the third place finisher got his entry fee back (minus the rake). I think the average duration of these tournaments is around 7-8 minutes.

Anyway, I was registered in one of these tournaments today when my computer went nuts and displayed a scary blue error screen -- something like this. This has happened before, and is basically just like my computer crashing: sometimes rebooting fixes it and sometimes the blue screen reappears. This happens pretty infrequently, but it's really annoying especially since it's a new laptop.

Fortunately I prepared in advance for this kind of thing, or so I thought. A few months ago I bought a backup laptop to use in case my computer crapped out during a session (which I previously blogged about here). So I excitedly whipped out my 2nd laptop ready to jump into the tournament.

Of course, it ended up taking longer to boot up than I expected, and then it required a passcode to connect to the internet which I couldn't locate (I just moved to a new apartment and guess I forgot to set up the wireless on my backup computer).

I also rebooted my original computer while I was doing this, and fortunately was able to get back to my game on that before I was blinded out. However, when I returned there were only 3 people left and I had 1.75 BBs; not a very good situation in a tournament in which only the top two pay. The stacks were 175, 1865, and 960 with blinds at 50/100 and ante 20.

Surely I'd have to double up 3 or even 4 times to come back right? Orrrr I could just triple up in my first hand back, then win without going to showdown again. Weeee.

I won't post all the hands, but this was my first hand back where I tripled up:

PokerStars Game #55524894186: Tournament #350235896, $177.45+$3.55 USD Hold'em No Limit - Level II (50/100) - 2011/01/07 14:35:42 ET
Table '350235896 1' 6-max Seat #3 is the button
Seat 3: beserious (175 in chips)
Seat 4: Bring 1t!!! (1865 in chips)
Seat 5: RynCzechLion (960 in chips)
beserious: posts the ante 20
Bring 1t!!!: posts the ante 20
RynCzechLion: posts the ante 20
Bring 1t!!!: posts small blind 50
RynCzechLion: posts big blind 100
*** HOLE CARDS ***
Dealt to beserious [Qc Jc]
beserious: raises 55 to 155 and is all-in
Bring 1t!!!: calls 105
RynCzechLion: calls 55
*** FLOP *** [4d Jd Kc]
Bring 1t!!!: checks
RynCzechLion: checks
*** TURN *** [4d Jd Kc] [Ad]
Bring 1t!!!: checks
RynCzechLion: checks
*** RIVER *** [4d Jd Kc Ad] [Qh]
Bring 1t!!!: checks
RynCzechLion: checks
*** SHOW DOWN ***
Bring 1t!!!: shows [Qs 7d] (a pair of Queens)
RynCzechLion: mucks hand
beserious: shows [Qc Jc] (two pair, Queens and Jacks)
beserious collected 525 from pot
*** SUMMARY ***
Total pot 525 | Rake 0
Board [4d Jd Kc Ad Qh]
Seat 3: beserious (button) showed [Qc Jc] and won (525) with two pair, Queens and Jacks
Seat 4: Bring 1t!!! (small blind) showed [Qs 7d] and lost with a pair of Queens
Seat 5: RynCzechLion (big blind) mucked [8s 3h]

Lessons from this:
1) Keep my backup computer on so I don't have to wait for it to boot up.
2) Make sure my internet (and backup internet) is installed on my backup computer.
3) When your comp craps out, Pokerstars just sits you out and doesn't give you extra time for being "disconnected."

Funny hand

2010-11-27T01:03:00.001-05:00

This hand was from the bubble of a $235 6max. LePlein, a very good regular player, accidentally types JJ in the chat during the hand -- I guess he was typing to a friend on aim or something and got the wrong chatbox. This made the hand pretty easy for me to play. I wonder if shipping turn is his best play though given the chat, knowing I'll call if I can beat JJ and fold if I can't.

PokerStars Game #52825618985: Tournament #332399516, $220+$15 USD Hold'em No Limit - Level IV (50/100) - 2010/11/17 3:16:09 ET
Table '332399516 1' 6-max Seat #4 is the button
Seat 2: LePlein (4980 in chips)
Seat 4: beserious (2450 in chips)
Seat 6: bballwiz (1570 in chips)
bballwiz: posts small blind 50
LePlein: posts big blind 100
*** HOLE CARDS ***
Dealt to beserious [Qd Kd]
beserious: raises 133 to 233
bballwiz: folds
LePlein: raises 267 to 500
beserious: calls 267
*** FLOP *** [2d 6d 6s]
LePlein said, "JJ"
LePlein: bets 300
beserious: calls 300
*** TURN *** [2d 6d 6s] [Qc]
LePlein: bets 4180 and is all-in
beserious: calls 1650 and is all-in
Uncalled bet (2530) returned to LePlein
*** RIVER *** [2d 6d 6s Qc] [9s]
*** SHOW DOWN ***
LePlein: shows [Jc Jd] (two pair, Jacks and Sixes)
beserious: shows [Qd Kd] (two pair, Queens and Sixes)
LePlein said, "ok"
beserious collected 4950 from pot
*** SUMMARY ***
Total pot 4950 | Rake 0
Board [2d 6d 6s Qc 9s]
Seat 2: LePlein (big blind) showed [Jc Jd] and lost with two pair, Jacks and Sixes
Seat 4: beserious (button) showed [Qd Kd] and won (4950) with two pair, Queens and Sixes
Seat 6: bballwiz (small blind) folded before Flop

Crazy day

2010-11-01T01:32:00.002-04:00

Pretty crazy day today at the tables. I couldn't win a tournament for my life at the beginning of my session, and was somehow down over $9k after 90 games or so (which I think would've been my worst day ever). But I battled back to end up in the black for the day (+$63). The green line shows actual profits, and the red line shows "luck-adjusted" profits (i.e., approximately how I would've done ignoring luck on all-ins).

Sick comeback

2010-10-16T01:25:00.001-04:00

I was playing a $1060+$50 6max sng tonight (top 2 get paid 65/35) and had a pretty ridiculous comeback heads-up. After losing a big allin, I was down to 100 chips (while he had 8900). Through a combination of luckboxing and him being too passive, I was able to pull off a pretty insane comeback. Here's how it went down:

PokerStars Game #51168420945: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level VIII (200/400) - 2010/10/16 0:07:28 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (8900 in chips)
Seat 2: beserious (100 in chips)
Joe Nice Guy: posts the ante 25
beserious: posts the ante 25
Joe Nice Guy: posts small blind 200
beserious: posts big blind 75 and is all-in
*** HOLE CARDS ***
Dealt to beserious [6d 4h]
Uncalled bet (125) returned to Joe Nice Guy
*** FLOP *** [8s Qh Js]
*** TURN *** [8s Qh Js] [Qd]
*** RIVER *** [8s Qh Js Qd] [6h]
*** SHOW DOWN ***
beserious: shows [6d 4h] (two pair, Queens and Sixes)
Joe Nice Guy: shows [Th 2h] (a pair of Queens)
beserious collected 200 from pot
*** SUMMARY ***
Total pot 200 | Rake 0
Board [8s Qh Js Qd 6h]
Seat 1: Joe Nice Guy (button) (small blind) showed [Th 2h] and lost with a pair of Queens
Seat 2: beserious (big blind) showed [6d 4h] and won (200) with two pair, Queens and Sixes

PokerStars Game #51168427727: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level VIII (200/400) - 2010/10/16 0:07:42 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (8800 in chips)
Seat 2: beserious (200 in chips)
Joe Nice Guy: posts the ante 25
beserious: posts the ante 25
beserious: posts small blind 175 and is all-in
Joe Nice Guy: posts big blind 400
*** HOLE CARDS ***
Dealt to beserious [8d Js]
Uncalled bet (225) returned to Joe Nice Guy
*** FLOP *** [7d Ks Qc]
*** TURN *** [7d Ks Qc] [5s]
*** RIVER *** [7d Ks Qc 5s] [Qd]
*** SHOW DOWN ***
Joe Nice Guy: shows [2h Jh] (a pair of Queens)
beserious: shows [8d Js] (a pair of Queens - King+Jack+Eight kicker)
beserious collected 400 from pot
*** SUMMARY ***
Total pot 400 | Rake 0
Board [7d Ks Qc 5s Qd]
Seat 1: Joe Nice Guy (big blind) showed [2h Jh] and lost with a pair of Queens
Seat 2: beserious (button) (small blind) showed [8d Js] and won (400) with a pair of Queens

PokerStars Game #51168434417: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level VIII (200/400) - 2010/10/16 0:07:57 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (8600 in chips)
Seat 2: beserious (400 in chips)
Joe Nice Guy: posts the ante 25
beserious: posts the ante 25
Joe Nice Guy: posts small blind 200
beserious: posts big blind 375 and is all-in
*** HOLE CARDS ***
Dealt to beserious [As Ks]
Joe Nice Guy: calls 175
*** FLOP *** [5s 7c 3s]
*** TURN *** [5s 7c 3s] [2s]
*** RIVER *** [5s 7c 3s 2s] [Jd]
*** SHOW DOWN ***
beserious: shows [As Ks] (a flush, Ace high)
Joe Nice Guy: shows [8h 5d] (a pair of Fives)
beserious collected 800 from pot
*** SUMMARY ***
Total pot 800 | Rake 0
Board [5s 7c 3s 2s Jd]
Seat 1: Joe Nice Guy (button) (small blind) showed [8h 5d] and lost with a pair of Fives
Seat 2: beserious (big blind) showed [As Ks] and won (800) with a flush, Ace high

PokerStars Game #51168442928: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level VIII (200/400) - 2010/10/16 0:08:15 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (8200 in chips)
Seat 2: beserious (800 in chips)
Joe Nice Guy: posts the ante 25
beserious: posts the ante 25
beserious: posts small blind 200
Joe Nice Guy: posts big blind 400
*** HOLE CARDS ***
Dealt to beserious [Ks Js]
beserious: raises 375 to 775 and is all-in
Joe Nice Guy: calls 375
*** FLOP *** [6d Ah Kd]
*** TURN *** [6d Ah Kd] [4d]
*** RIVER *** [6d Ah Kd 4d] [9s]
*** SHOW DOWN ***
Joe Nice Guy: shows [9h Th] (a pair of Nines)
beserious: shows [Ks Js] (a pair of Kings)
beserious collected 1600 from pot
*** SUMMARY ***
Total pot 1600 | Rake 0
Board [6d Ah Kd 4d 9s]
Seat 1: Joe Nice Guy (big blind) showed [9h Th] and lost with a pair of Nines
Seat 2: beserious (button) (small blind) showed [Ks Js] and won (1600) with a pair of Kings

PokerStars Game #51168453493: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:08:39 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (7400 in chips)
Seat 2: beserious (1600 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Qd Kd]
Joe Nice Guy: folds
Uncalled bet (300) returned to beserious
beserious collected 700 from pot
*** SUMMARY ***
Total pot 700 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) folded before Flop
Seat 2: beserious (big blind) collected (700)

PokerStars Game #51168457720: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:08:48 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (7050 in chips)
Seat 2: beserious (1950 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [4s As]
beserious: raises 1300 to 1900 and is all-in
Joe Nice Guy: folds
Uncalled bet (1300) returned to beserious
beserious collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (big blind) folded before Flop
Seat 2: beserious (button) (small blind) collected (1300)

PokerStars Game #51168461416: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:08:56 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (6400 in chips)
Seat 2: beserious (2600 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Tc 9h]
Joe Nice Guy: raises 5750 to 6350 and is all-in
beserious: calls 1950 and is all-in
Uncalled bet (3800) returned to Joe Nice Guy
*** FLOP *** [3h Ts Ac]
*** TURN *** [3h Ts Ac] [3s]
*** RIVER *** [3h Ts Ac 3s] [Td]
*** SHOW DOWN ***
beserious: shows [Tc 9h] (a full house, Tens full of Threes)
Joe Nice Guy: shows [4c Kc] (two pair, Tens and Threes)
beserious collected 5200 from pot
*** SUMMARY ***
Total pot 5200 | Rake 0
Board [3h Ts Ac 3s Td]
Seat 1: Joe Nice Guy (button) (small blind) showed [4c Kc] and lost with two pair, Tens and Threes
Seat 2: beserious (big blind) showed [Tc 9h] and won (5200) with a full house, Tens full of Threes

PokerStars Game #51168471514: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:09:19 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (3800 in chips)
Seat 2: beserious (5200 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [4c Th]
beserious: folds
Uncalled bet (300) returned to Joe Nice Guy
Joe Nice Guy collected 700 from pot
*** SUMMARY ***
Total pot 700 | Rake 0
Seat 1: Joe Nice Guy (big blind) collected (700)
Seat 2: beserious (button) (small blind) folded before Flop

PokerStars Game #51168476719: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:09:30 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (4150 in chips)
Seat 2: beserious (4850 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Kd Td]
Joe Nice Guy: calls 300
beserious: raises 4200 to 4800 and is all-in
Joe Nice Guy: folds
Uncalled bet (4200) returned to beserious
beserious collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) folded before Flop
Seat 2: beserious (big blind) collected (1300)

PokerStars Game #51168483703: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:09:46 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (3500 in chips)
Seat 2: beserious (5500 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Th As]
beserious: raises 4850 to 5450 and is all-in
Joe Nice Guy: folds
Uncalled bet (4850) returned to beserious
beserious collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (big blind) folded before Flop
Seat 2: beserious (button) (small blind) collected (1300)

PokerStars Game #51168491746: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:10:04 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (2850 in chips)
Seat 2: beserious (6150 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [5c Kh]
Joe Nice Guy: folds
Uncalled bet (300) returned to beserious
beserious collected 700 from pot
*** SUMMARY ***
Total pot 700 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) folded before Flop
Seat 2: beserious (big blind) collected (700)

PokerStars Game #51168495614: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:10:12 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (2500 in chips)
Seat 2: beserious (6500 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Qc Jh]
beserious: raises 5850 to 6450 and is all-in
Joe Nice Guy: calls 1850 and is all-in
Uncalled bet (4000) returned to beserious
*** FLOP *** [Kh Jc Td]
*** TURN *** [Kh Jc Td] [6h]
*** RIVER *** [Kh Jc Td 6h] [9s]
*** SHOW DOWN ***
Joe Nice Guy: shows [9d Qd] (a straight, Nine to King)
beserious: shows [Qc Jh] (a straight, Nine to King)
Joe Nice Guy collected 2500 from pot
beserious collected 2500 from pot
*** SUMMARY ***
Total pot 5000 | Rake 0
Board [Kh Jc Td 6h 9s]
Seat 1: Joe Nice Guy (big blind) showed [9d Qd] and won (2500) with a straight, Nine to King
Seat 2: beserious (button) (small blind) showed [Qc Jh] and won (2500) with a straight, Nine to King

PokerStars Game #51168504434: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:10:32 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (2500 in chips)
Seat 2: beserious (6500 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [5d Qh]
Joe Nice Guy: raises 1850 to 2450 and is all-in
beserious: calls 1850
*** FLOP *** [4d 3s Jd]
*** TURN *** [4d 3s Jd] [Ts]
*** RIVER *** [4d 3s Jd Ts] [9s]
*** SHOW DOWN ***
beserious: shows [5d Qh] (high card Queen)
Joe Nice Guy: shows [Ac 9c] (a pair of Nines)
Joe Nice Guy collected 5000 from pot
*** SUMMARY ***
Total pot 5000 | Rake 0
Board [4d 3s Jd Ts 9s]
Seat 1: Joe Nice Guy (button) (small blind) showed [Ac 9c] and won (5000) with a pair of Nines
Seat 2: beserious (big blind) showed [5d Qh] and lost with high card Queen

PokerStars Game #51168516315: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:10:59 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (5000 in chips)
Seat 2: beserious (4000 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [6h Qs]
beserious: raises 3350 to 3950 and is all-in
Joe Nice Guy: folds
Uncalled bet (3350) returned to beserious
beserious collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (big blind) folded before Flop
Seat 2: beserious (button) (small blind) collected (1300)

PokerStars Game #51168520370: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:11:08 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (4350 in chips)
Seat 2: beserious (4650 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Td Ad]
Joe Nice Guy: raises 600 to 1200
beserious: raises 3400 to 4600 and is all-in
Joe Nice Guy: folds
Uncalled bet (3400) returned to beserious
beserious collected 2500 from pot
*** SUMMARY ***
Total pot 2500 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) folded before Flop
Seat 2: beserious (big blind) collected (2500)

PokerStars Game #51168535462: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:11:41 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (3100 in chips)
Seat 2: beserious (5900 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Ac 7s]
beserious: raises 5250 to 5850 and is all-in
Joe Nice Guy: folds
Uncalled bet (5250) returned to beserious
beserious collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (big blind) folded before Flop
Seat 2: beserious (button) (small blind) collected (1300)

PokerStars Game #51168540142: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:11:52 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (2450 in chips)
Seat 2: beserious (6550 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Th 3d]
Joe Nice Guy: raises 1800 to 2400 and is all-in
beserious: folds
Uncalled bet (1800) returned to Joe Nice Guy
Joe Nice Guy collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) collected (1300)
Seat 2: beserious (big blind) folded before Flop

PokerStars Game #51168548819: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:12:11 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (3100 in chips)
Seat 2: beserious (5900 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Ts 5s]
beserious: raises 5250 to 5850 and is all-in
Joe Nice Guy: calls 2450 and is all-in
Uncalled bet (2800) returned to beserious
*** FLOP *** [2d Qs 5h]
*** TURN *** [2d Qs 5h] [Jh]
*** RIVER *** [2d Qs 5h Jh] [9h]
*** SHOW DOWN ***
Joe Nice Guy: shows [As 9c] (a pair of Nines)
beserious: shows [Ts 5s] (a pair of Fives)
Joe Nice Guy collected 6200 from pot
*** SUMMARY ***
Total pot 6200 | Rake 0
Board [2d Qs 5h Jh 9h]
Seat 1: Joe Nice Guy (big blind) showed [As 9c] and won (6200) with a pair of Nines
Seat 2: beserious (button) (small blind) showed [Ts 5s] and lost with a pair of Fives

PokerStars Game #51168557165: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:12:30 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (6200 in chips)
Seat 2: beserious (2800 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [9s 2s]
Joe Nice Guy: folds
Uncalled bet (300) returned to beserious
beserious collected 700 from pot
*** SUMMARY ***
Total pot 700 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) folded before Flop
Seat 2: beserious (big blind) collected (700)

PokerStars Game #51168560821: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:12:38 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (5850 in chips)
Seat 2: beserious (3150 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [Qc 2h]
beserious: raises 2500 to 3100 and is all-in
Joe Nice Guy: folds
Uncalled bet (2500) returned to beserious
beserious collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (big blind) folded before Flop
Seat 2: beserious (button) (small blind) collected (1300)

PokerStars Game #51168565869: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:12:49 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (5200 in chips)
Seat 2: beserious (3800 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [9d 8h]
Joe Nice Guy: raises 4550 to 5150 and is all-in
beserious: folds
Uncalled bet (4550) returned to Joe Nice Guy
Joe Nice Guy collected 1300 from pot
*** SUMMARY ***
Total pot 1300 | Rake 0
Seat 1: Joe Nice Guy (button) (small blind) collected (1300)
Seat 2: beserious (big blind) folded before Flop

PokerStars Game #51168572389: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:13:04 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (5850 in chips)
Seat 2: beserious (3150 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
Joe Nice Guy: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [8s 3c]
beserious: folds
Uncalled bet (300) returned to Joe Nice Guy
Joe Nice Guy collected 700 from pot
*** SUMMARY ***
Total pot 700 | Rake 0
Seat 1: Joe Nice Guy (big blind) collected (700)
Seat 2: beserious (button) (small blind) folded before Flop

PokerStars Game #51168575010: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level IX (300/600) - 2010/10/16 0:13:10 ET
Table '321445815 1' 6-max Seat #1 is the button
Seat 1: Joe Nice Guy (6200 in chips)
Seat 2: beserious (2800 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
Joe Nice Guy: posts small blind 300
beserious: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [6c 6d]
Joe Nice Guy: raises 5550 to 6150 and is all-in
beserious: calls 2150 and is all-in
Uncalled bet (3400) returned to Joe Nice Guy
*** FLOP *** [Ah 5d 6s]
*** TURN *** [Ah 5d 6s] [7s]
*** RIVER *** [Ah 5d 6s 7s] [2h]
*** SHOW DOWN ***
beserious: shows [6c 6d] (three of a kind, Sixes)
Joe Nice Guy: shows [4d Kh] (high card Ace)
beserious collected 5600 from pot
*** SUMMARY ***
Total pot 5600 | Rake 0
Board [Ah 5d 6s 7s 2h]
Seat 1: Joe Nice Guy (button) (small blind) showed [4d Kh] and lost with high card Ace
Seat 2: beserious (big blind) showed [6c 6d] and won (5600) with three of a kind, Sixes

PokerStars Game #51168587353: Tournament #321445815, $1060+$50 USD Hold'em No Limit - Level X (400/800) - 2010/10/16 0:13:38 ET
Table '321445815 1' 6-max Seat #2 is the button
Seat 1: Joe Nice Guy (3400 in chips)
Seat 2: beserious (5600 in chips)
Joe Nice Guy: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 400
Joe Nice Guy: posts big blind 800
*** HOLE CARDS ***
Dealt to beserious [Ac Qs]
beserious: raises 4750 to 5550 and is all-in
Joe Nice Guy: calls 2550 and is all-in
Uncalled bet (2200) returned to beserious
*** FLOP *** [7h Jd 7s]
*** TURN *** [7h Jd 7s] [7d]
*** RIVER *** [7h Jd 7s 7d] [2h]
*** SHOW DOWN ***
Joe Nice Guy: shows [Ts 9c] (three of a kind, Sevens)
beserious: shows [Ac Qs] (three of a kind, Sevens - Ace kicker)
beserious collected 6800 from pot
Joe Nice Guy finished the tournament in 2nd place and received $2226.00.
beserious wins the tournament and receives $4134.00 - congratulations!
*** SUMMARY ***
Total pot 6800 | Rake 0
Board [7h Jd 7s 7d 2h]
Seat 1: Joe Nice Guy (big blind) showed [Ts 9c] and lost with three of a kind, Sevens
Seat 2: beserious (button) (small blind) showed [Ac Qs] and won (6800) with three of a kind, Sevens

Interesting step 6 hand

2010-08-17T01:36:00.002-04:00

I was randomly observing a step 6 tournament today when the following hand came up. There were 4 players left, with the top 3 finishers all getting seats to the WCOOP main event (worth $5200), and the 4th place finisher getting $1200. So essentially the payoff structure at this point is (4000, 4000, 4000, 0), which is strategically equivalent to (1,1,1,0).

PokerStars Game #48260597443: Tournament #301619265, $2000+$100 USD Hold'em No Limit - Level VIII (200/400) - 2010/08/16 21:38:52 ET
Table '301619265 1' 9-max Seat #7 is the button
Seat 2: Octavian_C (8320 in chips)
Seat 4: Al K. Holick (7695 in chips)
Seat 6: heißtercamp (6275 in chips)
Seat 7: Leycrow (4710 in chips)
Octavian_C: posts the ante 25
Al K. Holick: posts the ante 25
heißtercamp: posts the ante 25
Leycrow: posts the ante 25
Octavian_C: posts small blind 200
Al K. Holick: posts big blind 400
*** HOLE CARDS ***
heißtercamp: raises 5850 to 6250 and is all-in
Leycrow: folds
Octavian_C: calls 6050
Al K. Holick: folds
*** FLOP *** [Ah 9d 3c]
*** TURN *** [Ah 9d 3c] [6c]
*** RIVER *** [Ah 9d 3c 6c] [Jc]
*** SHOW DOWN ***
Octavian_C: shows [Ad Qc] (a pair of Aces)
heißtercamp: shows [8d As] (a pair of Aces - lower kicker)
Leycrow said, "gg"
Octavian_C collected 13000 from pot
heißtercamp finished the tournament in 4th place and received $1200.00.
Octavian_C finished the tournament in 1st place
Octavian_C wins an entry to tournament #2010090062
Al K. Holick finished the tournament in 1st place
Al K. Holick wins an entry to tournament #2010090062
Leycrow finished the tournament in 1st place
Leycrow wins an entry to tournament #2010090062
*** SUMMARY ***
Total pot 13000 | Rake 0
Board [Ah 9d 3c 6c Jc]
Seat 2: Octavian_C (small blind) showed [Ad Qc] and won (13000) with a pair of Aces
Seat 4: Al K. Holick (big blind) folded before Flop
Seat 6: heißtercamp showed [8d As] and lost with a pair of Aces
Seat 7: Leycrow (button) folded before Flop (didn't bet)

I was really curious what the equilibrium jam/fold strategy was in this spot, so I ran it in holdemresources (which uses fictitious play and assumes ICM to compute an "approximate"-equilibrium). Holdemresources also assumes that once there is an all-in, a call, and overcall, all remaining players must fold. Here was the output:

CO shove: 51.0%, JJ+ Qx+ J2s+ J7o+ 97s+ 86s+ 75s+ 64s+ 53s+
BU call CO: 1.8%, JJ+
SB overcall vs CO/BU: TT+
BB overcall vs CO/BU: 2.3%, TT+
SB call CO: 1.8%, JJ+
BB overcall vs CO/SB: 0.5%, AA
BB call CO: 1.8%, JJ+
BU shove: 36.3%, 22+ Ax+ K2s+ K9o+ Q3s+ Q9o+ J8s+ J9o+ T8s+ 98s
SB call BU: 4.2%, 99+ AQs+ AKo
BB overcall vs BU/SB: 0.9%, KK+
BB call BU: 7.1%, 88+ ATs+ AJo+
SB shove: 100.0%, Any two
BB call SB: 1.4%, QQ+

Here is a link to the holdemresources output, with better indentation.

The equilibrium strategies seemed very counter-intuitive at first glance. Here are a few specific observations.

1) Cutoff shoves 51% of hands, and his range includes J2s and 53s, while he open-folds 99 and TT! The reason for this is that he is getting called with JJ+ from everyone else. So having any overcard to a J is more useful than having an underpair, and having a J helps by card-removal since it makes it less likely a remaining player will have JJ and can call him. Interestingly, underpairs like 88 and 99 do worse against the range JJ+ than some suited connector hands like 97s, 64s, etc.

2) Button calls CO with JJ+, but SB overcalls with TT+. Why does SB overcall with TT when he KNOWS button has JJ+? I ended up getting into a debate with my officemate about this. At first we both thought it was just a mistake in the calculation, but then I realized that it might actually make some sense. If SB folds and button beats CO (which will usually happen), then the CO will still be in with around 4 BB's, and the tournament will not be over. However, if SB calls and button beats both SB and CO (which will usually happen), but SB beats CO, then the tournament will be over (even though the button short-stack triples up). Our first initial calculation showed that it would still be silly to call here assuming TT is only about 70% vs CO's range. However, it doesn't really matter how good TT is vs. CO's range a priori: all that matters is how TT does vs CO's range GIVEN THAT BUTTON BEAT CUTOFF, since if CO beat BU then the tournament will be over and SB will win anyway. But if button beat CO, then it means that button's big pair (JJ-AA) held, and it is extremely unlikely that CO had a pair above jacks. Therefore, it's also extremely unlikely he can beat TT given he lost to button. So TT is probably at least a 90% favorite vs. this new conditional range of CO. Anyway, we didn't work out all the details, but I am now convinced that overcalling with TT in the SB here might actually be correct vs. those ranges.

3) While SB overcalls with TT+, he only calls with JJ+ if CO shoves and button folds. Again this is very counterintuitive at first glance. Why does he call TT if BU calls CO, but fold TT if BU folds? Let's look at the different scenarios. In both cases if SB calls with TT and the worst-case event happens, he will be left with about 5 BB's. In the overcall case, the cutoff will be left with 7-8 BB's if the all-in goes BU > CO > SB. In the non-overcall case, the 2nd shortest stack will be button, who will have almost 12 BB's. In the latter case, SB will have less than half of the 3rd place stack, and will still be in last place even if he doubles up. He is in much better shape when the 3rd place stack only has 7.5 BB's. So he is happier calling TT in the overcall case, since the stack setup will be more favorable to him in the event that the worst-case outcome occurs and the tournament continues.

Computer Poker Competition

2010-07-31T19:10:00.002-04:00

The Annual Computer Poker Competition took place a few weeks ago at AAAI, the main AI conference. It looks like there were about 30 bots submitted, both from academics and recreational programmers from around the world. There were 6 different competitions overall: three different variations of poker (two-player limit, two-player no-limit, and three-player limit, all Texas Hold'em), and for each variation two different scoring metrics (total bankroll (tbr), and bankroll instant runoff (iro)).

For each metric, each pair/threesome of bots played several matches, each consisting of 3000 duplicate hands. Duplicate hands work by dealing out a hand, then dealing out the same hand with the bots and positions reversed. The memories of the programs are erased between the duplications, so they can't remember the first play of the hand. This is a well-known technique for reducing variance, so that fewer hands are needed to obtain a desired level of statistical significance. Several of these 3000-duplicate-hand matches are played between each set of bots until a desired level of significance is obtained.

The tbr metric works by playing all the entrants against each other, and ranking the bots by their total profits. The iro metric is a bit more complicated. First, all entrants play against each other, and the bot with the worst head-to-head record is eliminated. Then, the records of all remaining bots are recomputed, and the remaining bot with the worst record is eliminated. This is continued until only one bot remains. (These descriptions were for the two-player competitions, and the three-player competition was pretty similar).

The different scoring rules are designed to encourage different types of algorithmic innovations. In particular, the iro encourages equilibrium or approximate-equilibrium bots. If a bot actually played an equilibrium, it would beat or break even against every other bot in expectation, and would win the iro competition in theory if enough matches were played. On the other hand, an equilibrium bot might not exploit weaker opponents as much as exploitative bots that use learning/opponent modeling. So this competition really encourages both game-theoretically "optimal" strategies, as well as exploitative strategies that do very well against weak opponents. I think both of these problems -- playing optimally and exploiting weak opponents -- are very important problems in AI.

While the competition is really great for the field, and provides a rigorous experimental testbed for these important problems, it is not without significant issues in my opinion.

My main criticism is with respect to a selection bias that prevents the tbr metric from being very meaningful. In particular, almost all of the bots submitted to the competitions (especially the two-player limit competition, which has received the most attention over the years and is the most competitive), are approximate-equilibrium bots and are quite good. The reason for this is pretty simple; if a good university spends a lot of time on a program for the competition, it will probably be very good (especially since most of the strong programs publish papers detailing the approach used). And if for some reason a team produces a bot that isn't very good, the team can just choose to not submit the bot and avoid the embarrassment of a poor finish. It is not hard to assess how good/bad your bot is too, since bots from previous competitions are made available for testing. So in short, it is very unlikely a team will submit a weak bot.

In addition, if only one or two weak bots are submitted, these bots will totally skew the results, and essentially determine the winner, since the winrates against the weak bot(s) will be significantly larger than the profits/losses against the stronger bots. So the results are not robust at all against the addition of a weak bot. Ideally we'd like to be able to make more general conclusions from the competition than just that the winning bot was especially good at exploiting one specific bot.

To put this in perspective, recall Axelrod's experiments described in The Evolution of Cooperation. To summarize briefly, he ran a competition for the repeated prisoners' dilemma game, which drew tons of entries from people in many different fields (e.g., econ, math, cs, psych, sociology). The submissions contained a very wide variety of strategies, and the winner ended up being Tit for Tat (TFT) -- a strategy that works by first cooperating, then playing whatever its opponent did the previous round. This was very significant, as it suggested that not only can cooperation emerge in this game (while game-theoretic analysis would suggest otherwise), but one of the most cooperative strategies actually has the highest performance against a wide variety of "reasonable" strategies.

Now imagine what would happen if all of the entries submitted were "rational." In fact, for the finitely-repeated prisoner's dilemma (Axelrod's experiments were repeated 200 times with each opponent pair), always defecting is the unique Nash equilibrium, and is also the only strategy surviving iterative dominance. So game theory would clearly suggest playing always defect. If everyone did this, then everyone would break even (and get a very low payoff). In fact, against a field of people playing Always Defect, TFT would actually come in last, since it would lose the first round before getting the (D,D) payoff for all later rounds. If this had happened, then it is unlikely TFT would have received all of the attention it did, and we might have greatly different views towards the possibility of cooperation in this setting.

I feel like a similar phenomenon is happening in the poker bankroll competitions. The current set of submitted bots just doesn't provide a good mechanism for identifying strong exploitative bots in a meaningful or robust way. This is definitely not a fault of the organizers of the competition in any way. But I think it is definitely an issue that needs to be addressed.

One idea to address this would be to reuse old versions of bots, which presumably are well behind the state of the art. But this can be problematic. First, the authors of those bots might have graduated and the code/jar files might not be available. Also, this might give an unfair advantage to the teams that wrote these bots, since they have access to the code and can determine how to better exploit them. Finally, these bots also might not demonstrate the same kinds of mistakes that many humans make.

One further idea would be to try to somehow learn some models of average human play from actual hand histories. I imagine this would involve getting access to tons of data, and again I'm not sure if the personal benefits would outweigh the time (though it would benefit all of the other competition entrants too). Also, this could potentially lead to a pretty cool paper if new algorithmic techniques were developed, i.e., "Learning human play in poker." On the other hand, it could also lead to a terrible paper, i.e., "The development of an extremely mediocre poker bot by standard techniques." In any case, right now this seems like the most promising solution to me, especially with the availability of large databases of human play from online poker.

Anyway, I should probably say that I'm not just being results-oriented and venting because we did poorly in the competition. In fact, CMU's team came in first in the no-limit bankroll competition, though we did worse than I hoped in the limit bankroll competition. Results aside, I think there are some major theoretical shortcomings of the current competition mechanism that should be addressed, though overall it is a great success.

Main event

2010-07-08T04:16:00.001-04:00

Ugh, busted with about 10 minutes left at the end of the day. Basically it seemed like nothing went right -- when I made plays people played back at me, when I had monsters people folded, and when I had decent hands people had slightly better ones. I do think I misplayed a few hands, but think overall I just ran like crap. My table was also very tough, with only one real fish. The only huge pot was KT vs K9 on a K98TK board (I wasn't in the hand).

Here are some of the hands I played.

Hand 1) Blinds 100/200 I raised to 500 from hijack with 77, SB who is aggro/good 3bets to 1900, I call in position. I was planning to call a barrel on most flops, and then reevaluate on the turn/river and possibly call more. But flop was 844 and he surprisingly checked, which threw me a little off guard. I figured he bets his big pairs, so I decided to bet to charge him to stay in with AK or whatever he had, but he raised to 7500 and I folded. I immediately regretted my decision to bet, and wish I checked back since I turned a hand w/decent value into essentially a bluff since I'm folding to a raise and he's rarely just check/calling flop. I was just kind of thrown off by his surprising check, and I think I definitely misplayed this one.

Hand 2) I raised QQ in EP (utg+1 i think), tight player calls in MP, fish calls in LP. Flop is 966 2 hearts, I cbet, both players call. Turn is blank (4 of clubs or something). I check, tight player makes a big bet, fish calls, I fold. River was a low heart, tight player bets, fish calls. Tight player had 99 (for flopped full house), fish had 2 low hearts for a flush. I got away pretty cheaply here fortunately.

Hand 3) I started hand with about 18k at 150/300. I raised CO with KQo to 750, button (who was pretty good) reraised me to around 2k. I decided to make a light 4bet here to 4700 b/c I didn't really want to flat, and KQ has blockers for KK/QQ/AK/AQ so seemed like a decent hand to 4bet/fold. He shipped pretty quickly, and I folded.

Hand 4) I think it was a hand or 2 after hand 3. I opened AQs (diamonds) in MP, player from hand 1 calls from button or cutoff. Flop was 3 diamonds, and I cbet. He raises me, and I think I had his raise covered by around 8k. I decided to ship, and he folded. I feel like flat-calling his raise screams monster, and I might be shipping Ad or some draws, so thought he might look me up. Not sure if flatting him is better, but I think I played this one fine.

Hand 5) I have around 16k at 150/300. Aggro guy opens in EP, fish calls in EP. I'm in EP with QQ. It was sort of a weird spot given my image -- I hadn't really been 3-betting much, so I thought they'd put me on a monster if I did and I wouldn't really get much value from QQ (i.e., they'd raise with better and not give me much action with worse). So I decided to just call, which I guess is debatable. Anyway, flop is JJ8 with 2 diamonds. Aggro guy cbets, fish calls, I call. Turn is blank, both check and I bet around 1/2 pot. Aggro guy calls, fish folds. At this point I think he probably has AA or KK -- he probably fires the turn again with a J or better, and I doubt he calls my bet with much worse, though TT/99 are still possible. River is a blank, and he makes a small bet of 3800 into 16k+. I felt like I couldn't really beat much at all, but I was getting such a great price I ended up calling, and he showed KK. If I had a few more chips, I could probably have shipped the river as a bluff and gotten him to fold, since my line looked really strong. But I think I only had around 6kish more and didn't think I had much fold equity there. Guess I could fold river, but I think it has to be pretty close. Also, I'm pretty sure I'm supposed to be raising preflop and getting it in, and balancing my range by 3betting air over EP opens enough so that I can get value from QQ.

Hand 6) Cutoff opened to 1000 at 200/400 50 ante. I had around 9k on the button with 88, and I shipped. Cutoff tanked and tanked for several minutes, asked me if I wanted him to call, etc. At that point I was almost positive I had the best hand, and actually did want him to call (though I didn't respond to his question). I put him on something like AT or 55. Anyway, he ended up calling me with TT (which should have been a really easy call), and I lost. Really standard shove by me I think, and just a cooler in that spot.

Also, I had KK once, two people limped in EP, I raised to 5x, and everyone folded. I had AA once and 3bet when an aggro guy opened, and he insta-folded. Later I 3bet the same guy with junk, and he 4bet me.

$1k day 2

2010-07-04T17:20:00.000-04:00

Busted out in 143rd last night (3844 entrants) for a cash of $3182. Most of the hands I was involved in weren't very interesting, but I'll summarize the main ones.

Early on I won a nice pot when utg+1 raised, I reraised with aces from utg+2, utg+1 shipped 15 bbs with 88, and my aces held. A few hands later, I raised in EP with AQo (Q of hearts), BB flatted, flop was 3 low hearts, he checked, I bet, he called. Turn was K of hearts, we both checked, river was blank and he led out 1/2-2/3 pot and I just called. He showed 73hh, so he flopped the flush, but I turned a higher one. I guess I played it pretty passively and might have been able to get another bet from him at some point -- maybe with a little raise on the river. Not sure what I do if he ships though.

Then I got moved to a pretty aggressive table with a few good players. I lost a decent pot when I opened 44 from CO at 600/1200 (100 ante), button shipped around 13k with A2s, I called and he hit an ace. I lost a bigger pot a little later when an aggro player on button shipped 15 bbs with T8o, I called BB with A8o, and he hit a flush. At this point I was down to < 10 bbs, but fortunately I ran well and won AJ > JJ and K8s > 77 allin preflop to get up over 30 bbs.

Finally, at 1500/3000 400 ante hijack who started the hand with 53k opened to 10k (an unusually large open, since standard is usually around 2-2.5x). I had 55k in the small blind and shipped with QQ, and he snap-called me with KJs. Unfortunately he turned a flush, and I was basically eliminated. His line was a little weird -- raising to 3.3x and calling a shove here -- but it probably wasn't so bad, since KJs is a big hand in an MTT with < 20 bbs.

A few more amusing things from the day didn't involve hands I played. At my first table, before the money bubble broke, this one guy (Player A) couldn't stop blabbing on about all his big laydowns and how he was trying to sneak into the money. We were about 100 ppl from the money bubble and he was pretty short, and he was bragging about his laydowns with 66/AJs/etc. One hand he opened button with like 12 bbs, BB shipped then he tanked and folded claiming he had AQo, and BB showed A8o. Then around the bubble he kept stalling by asking everyone at the table for their chip counts, etc. Finally someone called a clock on him (player B), causing player A to flip, saying he had made tons of huge laydowns and had a right to think them over. Player B (who I totally agree with) told him he was being really unreasonable, taking 3 minutes for every decision, and making it impossible for anyone else at the table to have a chance to win the tourney. Player A said to player B "Well, you have no chance of winning the tournament anyway, because you have bad karma!" Lol. Anyway, Player A's strategy "worked" I suppose, as he ended up making the money with literally 1/2 a BB left.

Finally after I busted, I had to wait in this huge line to receive my payout. Next to me was this guy in his 50's or 60's with some sort of southern accent. For some reason, he was trying to convince me that AA was only a 52% favorite vs. a random hand. I asked him if he meant allin preflop or something else, and he blabbered on about something incoherent. I told him it was at least a 76% favorite vs. any hand allin preflop, and he told me that I could really learn a lot by checking out Andy Bloch and Chris Ferguson's "computer modeling" that proved otherwise. He said some other stuff, like how 32 offsuit is only a 3-2 underdog vs aces or something, and how Andy Bloch was an MIT graduate so I could really learn a lot from his work! I thought about mentioning my background and my research, but decided it wasn't worth it with this nutcase so I just said "Very interesting, I'll have to check it out!"

$1k day 1 update

2010-07-02T21:26:00.001-04:00

Finished day 1a yesterday with 18250 chips (started with 3000). It's a little confusing b/c day 1b is still going on today, but it looks like around 330 people survived day 1a out of around 2500 total, and there were 1400 more entrants on day 1b. I was in 162nd out of 331 after day 1a, and am playing day 2 starting tomorrow.

My tables were all really weak yesterday until my final table, which had 3 aggro players to my left. Here were a few interesting hands:

Hand 1) Blinds were 100/200 and the hijack (2 before button) moved all-in for around 1300. It folded to the small blind who quietly said "I call, but I'm not very happy about it ..." It was pretty obvious to me that she was being sincere and probably didn't even realize I was still in the hand. I'm pretty sure she didn't have it in her to be deceptive. Anyway, I looked down at A5o -- not a great hand, but I thought it was a little ahead of the shover's range since he was pretty short. I was positive the SB had me beat -- I thought she had something like 66 or AT. But I was also pretty sure she'd fold if I reraised, since she was already not very happy about calling the first raise. So I reraised, she quickly folded (claiming she had AQ afterwards, which I believe). So I ended up getting over 2-1 against the hijack when I was ahead of his range, which is a great situation. Fortunately he had A4s and I hit my 5 to win a nice pot.

Hand 2) This was a little earlier, at 75/150. I was button with 25-30 bbs, and CO also had 25-30 bbs. He opened to 400, and I looked down at T4 of clubs -- obviously not a great hand. But I had position, and had a feeling if I 3bet this he wasn't going to go broke without a premium hand (based on my read of the player). So it seemed like a good spot to make a play, and I reraised to around 900. Surprisingly, he called my reraise (I expected him to fold or go all-in). But fortunately, the flop had 3 clubs, so I hit my flush. He checked, I made a smallish bet, he went all-in and I called. He had AQ with 1 club, so he still had a draw to a better flush, but fortunately I held.

Plane teasers

2010-07-01T02:12:00.001-04:00

The magazine on my flight to Vegas had a brain teaser section with the instructions "See if you can solve these problems in five minutes or less!"

Here was the first problem:
"Twelve balls are identical in all ways except one has a different weight than the others, which all have the same weight. Three weighings on a balance scale will not only identify the odd ball, but also tell whether it is heavier or lighter. How many balls must be put on the scale in the first weighing?"

It seemed pretty obvious that you need to put four balls on each side (the correct answer), but when I tried a few obvious algorithms for identifying the odd ball (and telling if it's lighter or heavier), none of them worked. For example, you can try weighing the first four balls against the next four: if they are equal then you can weigh 2 of the remaining balls against each other. But you can't solve the problem in one more weighing ... It quickly became clear that either the solution was pretty complicated, or more than 3 weighings were needed.

It turns out that you can actually solve the problem with three weighings. Obviously I would've solved it if I weren't so busy :), but a little googling gave me the following solution:

"I have lifted this practically verbatim from the book "Games for the Super-
intelligent" by the late Jim Fixx. (I would never have figured this out.)
Number the balls 1 to 12. Weigh 1, 2, 3, and 4 against 5, 6, 7, and 8.
If (1, 2, 3, 4) and (5, 6, 7, 8) balance:
Weigh 9 and 10 against 11 and 8 (we know 8 is not the odd ball).
If (9, 10) and (11, 8) balance: then 12 is the odd one.

Weigh 12 against any other to find out if it is heavy or light.

If (9, 10) and (11, 8) do not balance: suppose 11 and 8 are heavier,
than 9 and 10; then either 11 is heavy, or 9 is light, or 10 is light.

Weigh 9 against 10; if they balance, 11 is heavy; if they do not,
the lighter of 9 and 10 is the odd ball.

(Similar argument if 11 and 8 are lighter than 9 and 10).

If (1, 2, 3, 4) and (5, 6, 7, 8) do not balance:
Suppose 5, 6, 7, and 8 are heavier than 1, 2, 3, & 4. Then: one of
(1, 2, 3, or 4) is light, or else one of (5, 6, 7, or 8) is heavy.
Weigh 1, 2, and 5 against 3, 6, and 9.
If they balance: then either 7 is heavy, or 8 is heavy, or 4 is light.
Weigh 7 against 8; if they balance, 4 is the odd ball, otherwise the
heavier of 7 and 8 is the odd ball.

If (1, 2, 5) and (3, 6, 9) do not balance: suppose 1, 2, and 5 are lighter
than 3, 6, and 9; then either 6 is heavy, or 1 is light, or 2 is light.
Weigh 1 against 2 to find out which one of the three choices is true.
Otherwise, suppose 1, 2, and 5 are heavier than 3, 6, and 9; then either 3
is light, or 5 is heavy.

Weigh 3 against (say) 2 to find out which of the two choices is true.

(Similar argument if 1, 2, and 5 are lighter than 3, 6, and 9)."

I found it kind of funny that this problem was actually pretty tough, given how silly the other two problems were:

2) Is it possible for a man in St. Louis to marry his widow's sister?

3) Out of 3 females and 3 males, 3 people at random enter an empty room. What is the probability that there are two males and one female in the room now?

MTT score

2010-06-25T14:23:00.001-04:00

Wee, got 2nd in the $320 tourney on stars two nights ago for $34k. Hopefully my running good continues into WSOP. I'm heading out to Vegas in a few days, and I'll try to post more regularly once I get out there and start playing. Also, just set up a twitter account. I'll be texting quick stack updates to twitter while I'm playing.

Computer poker class

2010-06-08T22:36:00.002-04:00

Abe's post on what material he thought should be taught in undergrad AI motivated me to post some of my ideas about classes. In this post, I'll talk about a new course I'd like to design if I become a professor.

The class would be called "Computer Poker," and basically introduce a lot of concepts from game theory, AI, and related areas using poker as a motivating problem. I recall discussing the possibility of such a course with Mike Bowling at a conference a few years ago, and he said something along the lines of "nearly every section from Russel/Norvig's classic AI textbook has shown up in the course of poker research in the last few years." Not that I really need to defend poker research to the people reading this blog, but the following two links present some good summaries of its contributions: Annual Computer Competition website and AAAI Computer Poker Competition description. Here's a nice summary quote from the AAAI link: "In recent years, poker has emerged as an important, visible challenge problem for the field of AI."

Unlike most courses which present lots of different topics without really tying them all together or going into much depth in any particular topic, this course would present relatively fewer topics, but would tie them all back to the motivating problem of creating a strong poker program. I think a course like this could be really popular, since most people enjoy playing poker (or similar games) and would be naturally motivated already.

I guess the class would be designed at 3rd or 4th-year undergrads who had already taken some math and programming courses. I think it would need to end with a final project that was some sort of competition in which everyone submitted a full poker bot for some variant of poker. But this would be kind of tricky, because on the one hand it takes months (or even years) to develop strong Texas Hold'em bots, but if we picked a variant that was too small, it could probably be solved exactly making the problem not very interesting (although if people expected some entrants wouldn't play an equilibrium, they might not want to either, which might make it interesting). One reasonable idea might be to use a simplified 3-player game, so that even if an equilibrium could be computed, it might not necessarily be a good idea to play it. Maybe we could even give away an equilibrium in advance, so everyone is on the same page.

This idea is obviously still in very early stages, but I think it has potential ...

WSOP Staking

2010-05-28T00:40:00.001-04:00

I decided to try my luck in Vegas again this year ... right now I'm planning to play the $10k main event, and a $1k no-limit hold'em event. You can check out my report from last year in case you missed it: http://samsvegastrip.blogspot.com/.

Like last year, I'm looking to get staked for a decent percentage of my buy-ins to cut down on variance. After talking to some people, I decided that I'll be doing 1.1-1 markup like last year -- so e.g., you would put up $110 if you want 1% of my main event payoff.

If you're interested in buying a piece, please send me an email at beseriouspoker@gmail.com with "WSOP STAKING" as the title. Please let me know what % you are interested in of the $1k event or $10k main event (or both). Right now I'm not imposing a minimum (or maximum) share size, so feel free to propose whatever you want.

Also, please let me know how you want to pay -- transfer on Pokerstars would be the easiest, though transfer on FTP or sending a check work too (screen name is 'beserious' on both sites). Also let me know how you want to get paid after the events are done. I'll send you an email back confirming the agreement and the method of payment.

Even if you don't really play or follow poker, this is a good chance to make a +EV investment, and hopefully it will be exciting following my progress. Like last year, I'll be blogging regularly during the events. I'll also be setting up a twitter account so I can text shorter updates during the day.

Running it twice

2010-05-22T01:01:00.001-04:00

Sometimes when two people get all-in during a hand, they choose to "run it twice." Normally when two people are all-in, the remaining community cards are dealt, and the winner wins the entire pot. When players run it twice, the remaining community cards are dealt twice, and a player wins the pot only if he wins both times (and the pot is split if each player wins once). For example, suppose the players are all-in preflop with AA against KK and decide to run it twice. If the first set of community cards is 2389J, and second set is 3489K, then the players chop the pot because the AA player won the first hand and the KK player won the second hand (assume no one hit a flush).

Players seem to choose to run it twice fairly often for big pots on televised high stakes cash games (I guess the casino allows it). Pokerstars doesn't have the option to run it twice, but I think Full Tilt or another major site has the option if both players agree. I've even seen players run it three times once on tv.

Why would players choose to run it twice? To reduce variance. Suppose both players are all-in in a 50/50. For this example suppose that the community cards are dealt with replacement (though in reality they are dealt without replacement). If they just ran it once, then each player would win the pot P with probability 1/2, and win 0 with probability 1/2. So the expected payoff is
(1/2) P + (1/2) 0 = P/2
and the variance is (P/2)^2 = P^2/4.
If they ran it twice, then both players win the pot with probability 1/4, and with probability 1/2 they chop. So the expected payoff is still P/2, but the variance is now (1/2)*(P/2)^2 = P^2/8. So the variance has halved, while the expected payoff remains the same. Thus if both players are risk-averse, they should choose to run it twice in this setting.

Risk-averse players would actually prefer to run it 3 times than to run it twice, assuming replacement. In fact, the optimal way to allocate the pot would be to not even run it at all, and just give each player his expected payoff. For example, if player 1 wins with probability q and there is no replacement, then you should just give him q*P and give player 2 (1-q)*P, and not even deal out the cards. This would give both players their expected payouts with zero variance, which is clearly desirable for risk-averse players. This would also help make games run faster, since no more cards need to be dealt once people are all-in. But I have a feeling that casinos won't be using this rule anytime soon ...

The previous analysis holds for cash games; however, in big tournaments there are actually benefits of taking a high-variance strategy if the payoff structure is very top-heavy. I'm pretty sure no sites or casinos allow players to run it twice in tournaments though.

In the previous examples we assumed the cards were dealt with replacement; but in reality they are not. Does this change anything? It isn't obvious at all, but it turns out that your expected payoff is the same in both settings.

Let P be the size of the pot.
Let p be the probability P1 wins the first hand.
Let w be the probability P1 wins the second hand given he wins the first hand.
Let L be the probability P1 wins the second hand given he loses the first hand.

P1's expected payoff running it once is p*P
P1's expected payoff running it twice (without replacement) is
pwP + p(1-w)P/2 + (1-p)LP/2
= (P/2)(pw + p + L - pL)

Now, note that the probability that P1 wins the second hand is the same as the probability that he wins the first hand. This is because for community card sequences c1 and c2, the probability c1 is the first sequence and c2 is the second sequence is the same as the probability that c2 is the first sequence and c1 is the second sequence.

So Prob(P1 wins 2nd hand) = p.
But we know (Prob P1 wins 2nd hand) = Prob(P1 wins 2nd hand | P1 wins 1st hand) * Prob (P1 wins 1st hand) + Prob(P1 wins 2nd hand | P1 loses 1st hand) * Prob(P1 loses 1st hand) = wp + L(1-p)

So we have p = wp + L(1-p)
So substitution into the expression above yields:
P1's expected payoff running it twice (without replacement) is
(P/2)(2p) = p*P

So P1's expected payoff is the same running it once and twice.

Another interesting collusion case

2010-04-30T01:53:00.002-04:00

Another interesting collusion case has received some attention on the 2+2 forums. This case involved two high-volume limit hold'em players, with usernames furbean and fua9999. Apparently these players had been softplaying each other and sharing hole cards for several years. What is interesting is that they claimed they didn't realize what they were doing was wrong. This is the strategy they were using, as described by furbean:

"1. If one of us has entered the pot pre-flop with a raise, the other would raise with AA regardless. The chance for this to happen is less than 20% /221 x 2 = 0.001% , assuming we raise 20% of time pre-flop, which neither of us do.

2. For the situation when one of us has entered the pot pre-flop with a raise, the other holds KK, a phone call will be made to ensure that the other does not have AA; if one does hold AA, the other would fold KK to simplify the game. The chance of this situation to happen is same as with AA, which is less than 0.001%. We admit that what we did here is wrong and this is against the T&C, as we did share the hole card.

3. If one of us has entered the pot pre-flop with a raise, the other would fold all hands except the above mentioned. What this means is, the other would fold hands like QQ, JJ, AK without knowing the raiser's holdings. This happens 99.998% of time at least."

More complete information on this case, including all of the emails exchanged between pokerstars and furbean/fua9999, are available on furbean's blog. Emails #4 and #5 in particular are total gems, and you should all read them.

Collusion in online poker

2010-04-11T22:55:00.001-04:00

One of the trickier aspects of the online poker industry is the possibility of various types of cheating. In particular, colluding is one prominent form of cheating in which two players work together unethically to gain an advantage at the expense of other players.

Here is wikipedia's description of collusion in poker:

"Collusion is two or more players acting with a secret, common strategy. Some common forms of collusion are: soft play, that is, failing to bet or raise in a situation that would normally merit it, because you don't want to cost your partner money; whipsawing, where partners raise and reraise each other to trap players in between; dumping, where a cheater will deliberately lose to a partner; and signalling, or trading information between partners via signals of some sort, like arranging their chips in a certain manner.

Simple collusion in online poker is relatively easy and much more difficult to immediately spot if executed well. Cheaters can engage in telephone calls or instant messaging, discussing their cards, since nobody can see them. Sometimes one person may be using two or more computers to play multiple hands at the same table under different aliases (since many broadband plans offer customers multiple IP addresses, this can conveniently and cheaply be done without the likelihood of immediate detection). Such tactics can give cheaters an advantage that is difficult to work against. However, online poker cardrooms keep records of every hand played, and collusion can often be detected by finding any of several detectable patterns (such as folding good hands to a small bet, as it is known that another player has a better hand). Users who frequently sit at the same tables will be flagged by poker rooms and their play will be closely monitored. Often, such users will be warned they have been flagged, in an effort to deter collusion."

Some forms of collusion can be relatively easy to detect -- for example, if two accounts are registered under the same human user, or two accounts are playing in the same tournament from the same IP address. However, other more subtle forms of collusion can be very difficult to detect -- for example, two players might appear to be "soft-playing" each other and not betting as aggressively as they would against other players. But proving that this is the case with any level of rigor seems very difficult.

Interestingly, I just came upon a story in which a comprehensive publicly-available database of poker hands (pokertableratings) was used to show with statistical significance that several pairs of accounts had been soft-playing each other. Here is the full write-up of the findings of this case: CollusionAnalysis.pdf.

To summarize the results, the investigator compared how the suspected colluders' frequencies of various betting sequences compared to the frequencies of those betting sequences against all other opponents. In particular, the suspected colluders were both cash game short-stackers -- which means they buy in for about 20 big blinds, and employ a strategy that consists almost exclusively of going all-in preflop over a raise (3-betting), or raising preflop and then shoving the flop.

In particular, the 3-betting probabilities were given for the suspected colluders against each other, as well as against a wide variety of other opponents, which relevant sample sizes and confidence intervals given. The investigator was able to demonstrate with statistical significance that the players in question were in fact colluding. For example, on page 44 of the report listed above, the 3-betting percentages of the player LittleZen are plotted when 50 common opponents open with a raise (with relevant confidence intervals given). The graph contains a clear outlier of a 2% 3-bet range against the player knockstiff, the suspected colluder (while 3-bet %'s vs. all other common opponents exceed 4%). This represents a 3-bet percentage of less than KK+, AK over a significant sample of hands, which seems like a pretty clear sign of collusion.

In any case, it clearly remains a very tricky task of statistically "proving" the existence of collusion. But this seems to have been done very successfully in this case, and I am very interested to see how the future of collusion detection in online poker plays out, and whether these brute-force statistical datamining investigations will become mainstream.

Class projects

2010-03-21T13:49:00.001-04:00

Recently some people have been requesting a class project of mine that I wrote several years ago and had up on my webpage at one point. I'm a little unsure whether I should post class projects on my webpage for a few reasons. First, they could easily lead to papers in the future, and if I post them on my page in an unpublished form they could be scooped. Second, they generally aren't very "complete" or polished, and for this project in particular I came up with an entirely better approach I should have used in hindsight (though the results are still pretty interesting). Third, I guess it's kind of weak and not very professional to post class projects/drafts, since it implies they aren't really good enough to get published (which is probably the case in their actual form, though I could probably publish them eventually if I put in a bunch of more work which I don't have time for now). I guess this issue applies more to projects that are more expository or just applying a known technique; however, all of my projects are pretty novel and interesting in my opinion.

On the positive side, I think most of the results from my projects are pretty interesting and some people could definitely benefit from my posting them. So what do you guys think, should I post them? I guess I could make them tech reports first if I wanted to avoid being scooped.

GFY verizon

2010-02-23T01:07:00.001-05:00

So several months ago I received a call on my cell phone (yeah she called me, not the other way around) from someone at Verizon. She first talked to me about my wireless usage, and suggested switching from the $60/month to $40/month plan (which actually made sense, since I just use it for backup internet and occasionally for travel, and I hadn't been using it very much). Then she told me I could receive a free upgrade of my device, though after some followup questions I realized it wasn't free: they charged me for it (I think it was $60), and ALL i had to do was send back the rebate form and they would refund it.

So I got the new upgrade, and of course it was less convenient to use than the original device -- it was awkwardly shaped and required a USB cord, while my old device just had a single component and went right into my computer. I called verizon and found out that in fact the new "upgrade" didn't actually have any benefits over the older version. So I decided to stick with my older version, and the upgrade was basically useless.

Anyway, the upgrade came with instructions for sending the "rebate" form in. These instructions were obviously pretty simple, right? Wrong. They involved cutting off various pieces of cardboard from an oddly shaped box, and sending various bar codes and receipts via mail. Since I wasn't sure which code was which, I put every single receipt/bar code that came with the upgrade in an oversized envelope and shipped it back.

Well tonight I got home to see the following:
"Dear Customer:
Thank you for participating in this promotion. Unfortunately we oculd not honor your request due to the following reason(s):
- Missing Proof of Purchase (UPC) Bar Code
- Missing ESN / MEID
To resubmit for this offer you must return this card and any validating information to the address shown above by: 05/08/2010"

Sweet. Too bad I can't return any if these items because I fucking sent them to you already. Nice going verizon, good way to sneak a few $'s from your valued customers.

Backup laptop

2010-02-22T13:09:00.002-05:00

All serious mid/high stakes poker players I know have backup internet of some sort (I have Comcast and a Verizon wireless card). This is pretty much a no-brainer for me, because I usually have around $2k in play at a time (and sometimes significantly more), and losing internet for even 5 minutes could be disastrous if the blinds are high at some tables. My backup internet costs $40 a month, so this means if I lost internet once every 50 months, it would be profitable. Not to mention that it is useful when I travel and don't have another source of internet access.

Occasionally, even backup internet isn't enough. For example, there is a small chance that I will lose both Comcast and Verizon internet access at the same time. There is also a chance I will lose power (though my battery should be able to last long enough to finish the session). Also, my backup internet can fail for some reason -- one time I lost internet, and for some reason I couldn't launch my backup internet because of some driver issue (I had to reboot, which takes several minutes). And lastly, sometimes my computer might just totally crap out. This has happened to me before on both of my past laptops -- sometimes this crazy blue error screen pops up and I need to reboot, and sometimes the screen totally dies and I can't see anything. It's also possible the computer will totally die too.

In case something like this happens, I also have phone numbers of a few of my poker friends whom I could call to log into my account and take over for me (this is allowed in emergency situations like this, though generally it's not allowed for someone else to play under your account). I think I've only had to resort to this once or twice and it worked out ok. Though obviously it's possible that I can't reach any of the people on my list, or they aren't at their computer, etc. Also, if my computer craps out while I'm logged in to Pokerstars, it's not clear that Pokerstars will log me off so my friend can log in.

One final option to deal with these extreme situations is to actually buy a backup laptop (I know at least one of my friends has done this). While it seemed obvious financially to pay for backup internet, it's much less obvious whether it's worth it to pay for a second computer: it's much more expensive, and it would only help in extremely rare situations. I think calling a friend (who is presumably good at the games I play) is an acceptable solution, and the probability of my computer crapping out and not being able to reach any of my friends is extremely low. So I doubt it's worth it to buy a second laptop just to use in these extreme situations.

Am I overlooking any other important factors here? I know at least one person who has a backup laptop, so maybe there is more merit to getting one than I'm seeing.

Grocery Store BS

2010-02-14T19:31:00.001-05:00

The following situation happens to me all the time. I'll go to the market, and end up stuck behind 6-7 people in line to pay because they are only using 2 lanes or so. Eventually I'll move up a few slots, so maybe I'll be 3rd or 4th in line. Then all of a sudden, totally unannounced, a new lane will open up several lanes over. One would think that I should get priority in the new lane and be one of the first to go, since I've been in line the longest; but that would be incorrect. Usually it's the people from the back of the current lines -- or people who weren't even in line at all -- that somehow end up getting to go first in this magical new lane. Pretty fair system imo.

A similar situation happens on the road as well. I'll be driving along, then all of a sudden the car in front of me will turn on his blinker to make a left turn with lots of traffic coming the other way. Naturally, one would think I should be the first one to switch over to the other lane to pass this car; but no. Somehow the cars behind me in the left lane think they have some special right to switch lanes before the cars ahead of them do, and I get stuck waiting for all these cars who were behind me to drive by before I can switch.

So what can we do about these situations? Clearly people are super-selfish and will do everything they can to eek out a slight advantage or to shorten their commute. So there is a need for well-defined rules/laws to control these situations to achieve the just outcome.

Here is what I propose. In the grocery store, there should be a central queue: people take a number when they are ready to check out, and each lane picks the person with the next number to serve next (you can still have separate lanes for <= 10 items, etc. that aren't included in this system). One issue with this proposal is the transition time, since a person might be waiting by lane 1 and then his number appears at lane 15. With the old system, the 2nd person in line can already start emptying his groceries on the conveyor belt, so clearly the queue system will suffer a loss due to transition time.

Rather than having a single queue, I propose the following. Each lane has 3 "slots," and whenever a person leaves, the next number in the central queue takes the 3rd slot in that lane. This would leave someone enough time to walk from lane 1 to lane 15, since there are still 2 other customers at lane 15. This kind of system probably has a name in the queuing theory literature, but I'm not sure what it is.

For the driving example, there should be a law that says that the car in front has priority in the situation described above -- i.e., it is illegal to switch lanes and pass a car in front of you who is also trying to switch lanes due to a car waiting to turn left. Maybe tricky to enforce, but so are many laws (like talking on your cell phone while driving, etc.), so that shouldn't be a deterrent.

Sng Brainteaser

2010-02-12T19:21:00.001-05:00

I was talking with a friend on aim and he proposed the following problem: does there exist a stack/blind scenario in a sit-and-go tournament such that if it is folded to the small blind (and both the small blind and big blind have >= 5 BBs), there exist two hands h1, h2 and two calling ranges r1, r2 for the big blind such that if the big blind calls with r1, then the small blind should shove h1 but fold h2, but if the big blind calls with r2, then the small blind should shove h2 but fold h1? Let's assume we are talking about 9-player tournaments with a 50/30/20 payoff structure.

I was able to come up with the following solution pretty quickly. Suppose the blinds are 50/100 and the stacks are (from UTG to BB): (1500,500,1500,1500,1500,1500,1500,2000,2000). If the big blind calls with 100% of hands, the best response of the small blind is to shove the following range: 44+,A3o+,A2s+,K8o+,K5s+,QTo+,Q8s+,J9s+ (29.1%). If the big blind calls with the best 20% of hands (according to Karlson-Sklansky rankings), then the best response of the small blind is to shove the following range: 22+,AKo,AQo,AJo,ATo,A9o,A8o,A7o,A5o,A2s+,KJo+,KTs+ (19.5%).

So interestingly, the SB shoves almost 10% more of the time against a BB who calls 100% than against a BB who calls 20% (this is pretty surprising, because usually you tighten up your shoving range when people call wider).

The small blind shoves 22 and 33 against the 20% calling range, but folds them against the 100% range. He also shoves lots of hands against the 100% range that he folds against the 20% range (A6o,A4o,A3o,K8o-KTo,K5s-K9s,QTo+,Q8s+,J9s+).

AAMAS paper

2010-02-11T15:34:00.001-05:00

Just finished the final version of my AAMAS paper -- here's the link: http://www.cs.cmu.edu/~sganzfri/AAMAS2010.pdf.

In my unbiased opinion it's a pretty interesting paper. Here is the abstract:

"We present a new procedure for solving large games of imperfect information. Our approach involve -- somewhat counterintuitively -- solving an infinite approximation of the original game, then mapping the equilibrium to a strategy profile in the original game. Our main algorithm exploits some qualitative model of equilibrium structure as an additional input to find an equilibrium in continuous games. We prove that our approach is correct even if given a set of qualitative models (satisfying a technical property) of which only some are accurate. We compute equilibria in several classes of games for which no prior algorithms have been developed. In the course of our analysis, we also develop the first mixed-integer programming formulations for computing an epsilon-equilibrium in general multiplayer normal and extensive-form games based on the extension of our initial algorithm to the multiplayer setting, which may be of independent interest. Experiments suggest that our approach can outperform the prior state of the art, abstraction-based approaches. In addition, we demonstrate the effectiveness of our main algorithm on a subgame of limit Texas hold’em -- the most studied imperfect-information game in computer science."

Staking

2010-01-14T16:44:00.001-05:00

Often in poker, players expect to be very profitable in games that they are not bankrolled for. For example, a good mid-stake mtt player (e.g., $50-$100 mtts online) would probably be very +EV in the main event at the wsop, which attracts alot of weak players. However, the buyin of this tournament is $10k, which is almost definitely too expensive for a mid-stakes player who practices proper bankroll management.

To allow these +EV players who are under-bankrolled to play these higher-buyin games, sometimes players with more money "stake" them. For tournaments, staking is relatively straightforward: usually the staker puts up fraction p of the entry fee, and then gets back fraction q of the payout of the stakee (often p = q or p = 1.1q, depending on the ability of the stakee/terms of the agreement). For simplicity, let's model the tournament as a random event that the player wins with probability x, and loses with probability 1-x (i.e., a biased coin). If p = q and the stakee were "breakeven" in the tournament (post-rake), then the staker's expected profit is [0.5*0 + 0.5*p*(2T)] - pT = 0 (where T is the entry fee). So the staker expects to break even in this case, and clearly if the stakee is +EV, the staker will expect to turn a profit.

Now for cash games, staking becomes more complicated. There's no single event that the staker is paying for, and the stakee's profits will fluctuate over time. Let's consider the following simple model. Suppose the staker gives the stakee some amount of money n. And suppose at each time step, the stakee takes a binary gamble as above s.t. he wins 1 with probability p, and loses 1 with probability 1-p. Suppose the stakee repeats this process for n time steps. At the end of the n time steps, if the stakee has < n left of the money the staker gave him, he pays it back to the staker (and the staker takes a loss). If the stakee has > n, then he gives 1/2 of the profits to the staker, and keeps the rest.

At first glance, this type of agreement seems pretty bad for the staker. If the stakee loses x, the staker loses x; and if the stakee wins x, the staker wins x/2. So clearly if the stakee is breakeven post-rake, this will be -EV for the staker (unlike the tournament example above). So the question is, how profitable does the stakee have to be to make this agreement profitable for the staker?

I was curious about this yesterday, and decided to run some calculations to figure this out (thanks to my officemate Kevin for helping with this). Using n = 200, it turns out that the stakee only needs to win with probability p somewhere between 0.509 and 0.51 for this agreement to be profitable for the staker. So I guess if the stake agreement lasts long enough, the stakee only needs to be slightly profitable for the agreement to be +EV for the staker.

Idea for google

2009-11-17T11:28:00.001-05:00

So I've had this song/melody stuck in my head all morning. But I have absolutely no idea what it's from, or it's even from a song or if I just made it up on my own. If only there were a search engine you could sing/hum into that would tell you what song it was! Oh well, I guess I'll take credit for the song myself then ...

Awesome comic

2009-11-13T03:56:00.001-05:00

http://abstrusegoose.com/strips/computer_science_major.PNG.

Tennis puzzle

2009-10-04T03:42:00.002-04:00

Suppose you (a tennis novice) get to play a tennis match against Roger Federer for $1,000,000. It is a normal best out of 5 set match, except there is one catch: you get to choose the score that the match is started at. For example, you could choose to start at 1 set all, you are up 3-2 in the third set, you are up 40-15 in the game. What score would you choose to start at?

I think this question is relatively well-known, so don't answer right away if you already know the answer.

AI + music

2009-10-03T22:26:00.002-04:00

I was just randomly thinking that it would be really cool if there were an algorithm that could take as inputs a list of songs that I like and automatically generate a new song that I also like (that doesn't just copy/paste together parts of the songs I input). I think we should be able to come up with such an algorithm, though I have no idea how to model the problem, and what features to use for learning algorithms, etc. It looks like my undergrad thesis advisor actually taught a class on AI and music a few years ago, though I didn't take it: http://www.eecs.harvard.edu/~avi/CS281r/F03/. Maybe I'll check out some of the papers from the class if I have time.

Football strategy

2009-10-01T04:25:00.002-04:00

A few weeks ago Hines Ward on the Steelers made a crucial 4th quarter fumble that could have thrown away an almost guaranteed win. The score was 10-10 with about a minute left in the 4th quarter, when Hines caught a pass inside the 20 yard line of the other team. Instead of just downing himself and taking the almost sure field goal from 35 yards away, he decided to keep running even though it seemed pretty unlikely he'd be able to get a touchdown.

Here is the clip:
http://www.youtube.com/watch?v=3QgaJ17GrLo.

At first I thought he made an idiotic decision and should have just downed himself. So I decided to make a model and analyze the decision more closely.

Let's assume the following:
f is probability he fumbles
t is probability he scores a touchdown
g is probability the kicker will make a field goal from inside 35 yards (we'll assume he's equally likely to kick a field goal from any distance inside 35 yards)
If the Steelers score, they will win the game (i.e., the other team won't be able to come back).

Then the probability of winning the game if he downs himself is g.
The probability of winning if he goes for the touchdown is
(1-f)(t+(1-t)g) = t + g - gt - ft - fg + ftg.

So he should keep running iff
t - gt - ft - fg + ftg >= 0.
<-> t >= fg/(1-g-f+fg)

I spoke with a former professional sports-bettor, and here are the values he came up with:

t = 0.1
f = 0.02
g = 0.93

Using these values, the probability of winning if he downs himself is 0.93, while the probability of winning if he keeps running is
t + g - gt - ft - fg + ftg = 0.91826.

So this suggests that he should down himself in this model. If you add the fact that they can run out the clock before kicking the field goal if he downs himself, while if he scores a touchdown the other team will have a chance to score with > 40 seconds left, this makes it even more clear that he should down himself.

Good to see my intuition confirmed.

Locksmiths = good or bad?

2009-09-26T04:43:00.001-04:00

This story happened to me several months ago, and just randomly came across my mind. I came back to my apartment around 2am and put my key into the lock of my front door, but for some reason the lock was jammed and wouldn't open. I tried it several more times with no luck. Finally after about 10-15 minutes, I ended up getting the number of a locksmith. He was there within an hour, and unlocked the door in about two minutes (without asking me for an ID or any form of verification that it actually was my house). It turned out that some maintenance people from my rental agency had been in my apartment earlier that day to fix the balcony, and I guess somehow jammed the lock when they left. There are some other details I'll leave out for now -- but basically the rental agency claimed it was my fault and didn't reimburse me.

But anyway, the main moral of the story is that the locksmith system is totally buggy. Anyone can call a locksmith claiming to be locked out from a house and then break into and rob the house with relative ease. All he would have to do is ensure the people who live in the house will be away for about an hour window (which shouldn't be too hard during typical work hours), and possibly forge an ID for the locksmith (though he didn't even check mine). Also, anyone looking to become a burglar can get trained as a locksmith, and then go rob houses at will. Yes, locksmiths can provide a valuable service to people who get locked out; but does this outweigh the security risk? I think at the least there should be better measures to verify the identity of the person trying to get into the house, and possibly some police involvement.

Superusers

2009-09-15T23:57:00.001-04:00

A few years ago, there was a pretty big scandal on Absolute Poker in which certain players were able to see the hole cards of the other players at the table, and could therefore gain an unfair advantage (more information is available here:http://www.absolutepokerscandal.com/). It turns out that former employees of Absolute Poker had hacked into the system and were cheating.

This got me thinking about how to detect superusers, and how to optimally superuse (if you just try to win every hand, it will become obvious pretty quickly and you will get caught). I decided to come up with a small toy game that captures some interesting aspects of this situation.

The game has two players. Player 1 -- the superuser -- is playing a series of 1000 games of matching pennies (http://en.wikipedia.org/wiki/Matching_pennies) against a player who plays optimally and randomizes 50/50 between heads and tails. Each round player 1 wins, he gets $1, and each round he loses he loses $1. The superuser can see what action the opponent has selected before he makes his decision, and therefore can end up with any (even) payoff between $0 and $1000 depending on how much he chooses to take advantage of his opponent.

Player 2 is the detector who is trying to catch the superuser cheating. He has 3 options: to set k equal to 0.01, 0.05, or 0.1. He chooses k in private before the game starts. After all 1000 games of matching pennies are over, he compares player 1's payoff P to the quantity Q_k = sqrt(2000 ln(1/k)). If P >= Q_k, then he concludes that player 1 is a superuser, since the probability player 1 would have obtained such a payoff if he played randomly is less than k (the formula for Q_k was obtained using a Chernoff bound -- http://en.wikipedia.org/wiki/Chernoff_bound). This is basically like running a hypothesis test with k denoting the level of statistical significance.

If P >= Q_k, then player 1 gets payoff 0 (since he was caught), and player 2 gets payoff log(1/k) (player 2 would prefer to catch player 1 cheating with a higher degree of statistical significance). If P < Q_k, then player 1 gets payoff P and player 2 gets payoff 0 (since he didn't catch the cheater). What are the Nash equilibria of this game? It turns out that this game actually has a unique equilibrium which can actually be found by iterated removal of dominated strategies (http://en.wikipedia.org/wiki/Iterated_deletion). In the equilibrium, player 1 chooses to win in 533 rounds and lose in 467 rounds for a payoff of $66, while player 2 sets k = 0.1 and ends up with payoff 0.

I was pretty surprised that the game had a pure strategy equilibrium -- I'd think that both players would want to randomize. I'm pretty sure even if you let player 2 select from a larger set of possible k-values, the game still has a unique equilbrium where player 2 picks the largest possible k value, and player 1 chooses the maximum payoff that avoids detection.

Bankroll optimism

2009-09-08T03:30:00.001-04:00

Many poker players play stakes far higher than they should because they overestimate their winrates and don't understand and/or practice proper bankroll management. Another more subtle mistake that poker players (and presumably other gamblers) make is overestimating the size of their effective bankroll. For example, someone might see he has $200k in his account, and after setting aside some amount for necessities think his effective bankroll is around $150k and then base his bankroll management system based on that. However, if he goes on a $50k "downswing," he might make a drastic jump down in stakes, or even quit playing altogether. If this is the case, then he should really have viewed his effective bankroll from the beginning as being $50k instead of $150k, which would presumably have had a large effect on what stakes he started off playing. I think a lot of poker players need to be more honest with themselves about how much money they are really willing to lose (as well as their projected winrates at various buyins), and manage their bankrolls accordingly.

Music strategy

2009-09-08T03:17:00.001-04:00

Random observation I can't believe I've never made before -- artists should really make it super-obvious what the title (and/or artist) of a song is in the song (e.g., by repeating it over and over). Lots of times I'll hear a song I like, but can't obviously tell the title or artist from hearing it. If the artist just made it a little more obvious, I might have downloaded the song (in the past maybe bought a CD) and would recommend it to my friends. I feel like the title/artist of a random song is only obvious < 50% of the time though, which is pretty dumb in such a competitive industry.

Split Or Steal

2009-08-21T01:26:00.001-04:00

I came across this youtube video a few weeks ago: http://www.youtube.com/watch?v=p3Uos2fzIJ0.

The clip is from a British game show in which two contestants play a game similar to the Prisoner's Dilemma for 100,000 pounds. Each contestant can choose to Split or Steal. If both players Split, then each one gets 50,000 pounds. If one player Splits and the other Steals, the person who Split gets 100,000 and the other person gets 0. And if both people Steal, then they both get 0. Before making their decisions, the contestants get a few minutes to talk to each other and presumably convince the other person that they plan to Split.

I tried to base a homework problem for the class I TA'd last semester off this situation (but had to change it a little) -- http://www.cs.cmu.edu/~ggordon/780/hws/PS5.pdf (Problem 1). This problem also looks at what happens when the players repeat the game more than once.

Anyway, it seems pretty clear that if you are playing against a total stranger, you should definitely choose Steal (after of course convincing them that you are going to Split). This is because no matter what the other player does, you do at least as well by Stealing than by Splitting (i.e., Steal weakly dominates Split).

On the other hand, if you are playing against a relative/close friend whom you trust, you should probably choose Split since that relationship is probably more important than the amount of money.

But what if you were playing against an acquaintance, distant friend, business associate, or someone you have a connection to but aren't that close with? Convincing him that you are going to Split, then choosing Steal could get pretty ugly ..

Face the Ace

2009-08-17T22:09:00.001-04:00

A new poker show called "Face the Ace" just started up on nbc (http://www.face-the-ace.net/). The show works as follows. A contestant is selected (who is presumably an amateur poker player) who then plays a match against one of the "aces" -- a poker pro who is affiliated with fulltilt (e.g., Phil Ivey, Howard Lederer, Chris Ferguson). If the ace wins, then the contestant goes home with nothing. If the contestant wins, then he gets a choice of $40k or playing another match against a different ace. If the contestant wins the second match, then he gets a choice of $200k or another match. If he wins the third match, then he wins $1,000,000. If the contestant loses any of the matches he gets nothing (I'm pretty sure money is donated to a charity in that case).

Each match is a heads-up sit-and-go tournament. It's hard to tell the exact structure from the tv footage, but it looks like both players start about 100 BB's deep and blinds go up super-fast. Due to the fast blind structure, the aces shouldn't really have a huge edge if the contestant is at all competent, since once the blinds are high luck becomes very important.

Clearly the contestant will always play the first match, since he gets nothing if he doesn't play and gets either $0 or $40k if he plays. If he were risk-neutral, then he should play each of the other two matches if he thinks his chance of winning is above 20%. His expected winnings will be p^3 * 1,000,000 if his winrate is p.

However, there are two major reasons a contestant might choose to take the money instead of play even if he thinks his winrate is significantly larger than 20%.

1) Risk aversion. The contestants' utility functions might not be perfectly linear in wealth, and in reality most utility functions are probably concave (e.g., logarithmic) in wealth. For example, if you have no money then an extra dollar is most likely significantly more valuable than if you are a millionaire.

2) Kelly criterion. The Kelly criterion is a formula that specifies the optimal percentage of your bankroll to risk in a series of bets (http://en.wikipedia.org/wiki/Kelly_criterion). While the situation in "Face the Ace" only consists of up to 3 bets (and not a long series as in the Kelly model), we can view the contestant's lifetime as consisting of a long series of investment opportunities of which this is just one. On the other hand, the Kelly model assumes that the investor gets to choose any amount to bet at each round, while in this situation the amount is fixed and the contestant only chooses whether or not to take the bet. So the models aren't identical, but it is still probably a bad idea to make a bet for a larger percentage of your wealth than Kelly recommends. It is often recommended to be far more conservative than Kelly suggests and to bet some fraction of the Kelly amount (e.g., 1/2 or 1/4). The wikipedia page has a section on why you should bet less than the Kelly amount.

According to the Kelly criterion, the contestant should bet fraction f = (5p-1)/4 of his bankroll if he were given the choice. So for example, suppose the contestant is deciding whether to play the 3rd game for $1,000,000 and expects to win with probability p = 0.3. Then according to Kelly he should be willing to bet up to 1/8 of his wealth. If W is his pre-show wealth, he should only take the bet if
200k <= 1/8(W + 200k) <---> W >= $1,400,000.

In the episodes I've seen so far, one person lost the first match, and another person won two matches before losing the third (he turned down the money twice). It will be interesting to see what the contestants choose to do in the upcoming episodes.

Interesting sng hand

2009-08-11T17:24:00.001-04:00

This hand came up earlier in the week and I thought it was pretty interesting. This was in a sit-and-go (sng) tournament that started with 9 players, with the prize pool going to the top three finishers according to a 50/30/20 ratio (i.e., winner gets 50% of the prize pool, 2nd place gets 30%, 3rd place gets 20%).

Level IX (300/600) - 2009/08/09 18:03:16 ET
Table '185918082 1' 9-max Seat #7 is the button
Seat 1: arnebever (7311 in chips)
Seat 7: paulrob23 (2843 in chips)
Seat 9: beserious (3346 in chips)
arnebever: posts the ante 50
paulrob23: posts the ante 50
beserious: posts the ante 50
beserious: posts small blind 300
arnebever: posts big blind 600
*** HOLE CARDS ***
Dealt to beserious [2c Ac]
paulrob23: raises 1200 to 1800
beserious: calls 1500
arnebever: raises 3600 to 5400
paulrob23: folds
beserious: folds
Uncalled bet (3600) returned to arnebever
arnebever collected 5550 from pot
arnebever: doesn't show hand
*** SUMMARY ***
Total pot 5550 Rake 0
Seat 1: arnebever (big blind) collected (5550)
Seat 7: paulrob23 (button) folded before Flop
Seat 9: beserious (small blind) folded before Flop

My stats on both players said they were pretty loose, and I didn't recognize either of them so they were probably losing players.

Before I present my analysis of the hand, I'll discuss the strategies that the ICM Nash calculator (http://www.holdemresources.net/hr/sngs/icmcalculator.html) prescribes. That site takes as inputs the stack sizes, payout structure, blinds, and antes, and outputs a Nash equilibrium when all players are restricted to going all-in or folding preflop, assuming that the Independent Chip Model (ICM) holds. The Independent Chip Model gives a way of mapping a vector of stacks to a vector of monetary payoffs. According to ICM, a player's probability of coming in 1st is equal to the fraction of the chips in play that he has, a player's probability of coming in 2nd is equal to the weighted sum over other players of their probability of winning times the fraction of remaining chips he has, etc. For more information on the Independent Chip Model and a formal definition you can check out my AAMAS 2008 paper here: http://www.cs.cmu.edu/~sganzfri/AAMAS2008.pdf (especially Section 4). In any case, ICM is just a heuristic that has been developed in the poker community and is reasonably accurate for most stack vectors, though way off in other spots. Maybe I'll devote a post in the future to describing some of the shortcomings of ICM.

Here are the ICM Nash strategies:

Button shove: 22+ Ax+ K7s+ K9o+ Q9s+ QTo+ J9s+ T9s
SB shove after button shoves: 33+ A6s+ A8o+ KJs+ KQo
BB call after button shoves and SB shoves: 44+ A9s+ ATo+ KTs+ KQo QTs+ JTs
BB call after button shoves and SB folds: 22+ Ax+ K5s+ K9o+ Q9s+ QTo+ J8s+ JTo T8s+ 98s 87s
SB shove after button folds: 22+ Kx+ Q2s+ Q7o+ J5s+ J8o+ T6s+ T9o 96s+ 98o 86s+ 75s+ 65s
BB call after button folds and SB shoves: 22+ Ax+ K2s+ K4o+ Q4s+ Q8o+ J7s+ J9o+ T8s+ T9o 98s

Here are the strategies output by our newer algorithm PI-FP presented at IJCAI 2009: http://www.cs.cmu.edu/~sganzfri/IJCAI2009.pdf. Unlike the Nash ICM algorithm, our algorithm doesn't assume the Independent Chip Model and computes an equilibrium in the actual (and potentially infinite) tournament endgame with three-players left and 300-600 blinds (so it ignores antes). Thus, our algorithm will take into factors such as having to post the big blind next hand, a future advantage of having a big stack etc., which ICM does not account for.

Here are the corresponding strategies output by PI-FP:

Button shove: 22+ Ax+ K4s+ K9o+ Q8s+ QTo+ J8s+ JTo T7s+ 97s+ 87s
SB shove after button shoves: 44+ A4s+ A8o+ KTs+ KJo
BB call after button shoves and SB shoves: 33+ A8s+ ATo+ KTs+ KQo Q9s+ J9s+ T9s
BB call after button shoves and SB folds: 22+ Ax+ K8s+ KTo+ QTs+ QJo JTs
SB shove after button folds: 22+ Kx+ Q2s+ Q8o+ J3s+ J8o+ T4s+ T8o+ 95s+ 97o+ 85s+ 87o 74s+ 76o 64s+ 53s+
BB call after button folds and SB shoves: 22+ Ax+ K3s+ K7o+ Q8s+ Q9o+ J9s+ JTo

It's worth noting a few major differences between the ICM Nash and PI-FP strategies. PI-FP has button shoving wider, presumably because he will have to post the big blind next hand. Consequently, PI-FP has SB calling wider if button shoves and BB calling wider if both players go-allin in front of him. PI-FP also has the SB shoving wider if the button folds, but surprisingly the BB calling narrower if either button or SB shoves (and the other player folds). This is probably explained by the fact that the BB, who is the big stack at the table, is more likely to get more profitable situations in the future from bullying with his big stack and thus should be less likely to call a shove with a marginal hand.

In any case, pretty much everyone in button's spot is shoving significantly wider than both Nash ICM and PI-FP suggest, probably because they overestimate the effect of having to post the BB next hand and underestimate the gain in EV of folding and letting SB shove and BB call (which will happen over 20% of the time). Many players shove much much wider than the algorithms suggest, including hands like K2o, 54s, etc. Given my read that button is loose, I assume he is raising significantly wider than the PI-FP range. Thus, while A2s is a fold according to PI-FP (it requires A4s+), it is a pretty clear call against my perceived range of this (and most) opponents.

So now given that I think I am sufficiently ahead of button's range to warrant playing the hand, my decision is between calling and raising. If I raise (i.e., go all-in), then if BB wakes up with a big hand behind and calls, button can fold and I will be all-in against the BB with his range crushing my A2s. On the other hand, if I just call and BB wakes up with a hand and goes all-in, then if button calls I can call behind him, in which case button will need to beat both me and BB to avoid coming in 3rd (because I had more chips than him at the start of the hand). Also if BB shoves and button folds, I can fold as well because I still have button covered and he will essentially be forced all-in in the big blind next hand.

Now let's examine my decision after button raises, I call, BB shoves, and button folds more carefully. If I call and lose, then I will finish in 3rd and end up with 20% of the prize pool (let's normalize the payoffs so they are $50/$30/$20). If I call and win, then the stacks will be (8542, 3965, 993), which is worth $42.750 to me according to the PI-FP algorithm (while it's worth $42.412 according to ICM). Big blind's range most likely consists of mid to high pocket pairs and big aces, that all have me dominated. Playing around with an odds calculator (http://www.cardplayer.com/poker-tools/odds-calculator/texas-holdem) reveals that A2s wins about 32% of the time against most of the hands in BB's range.

So my expected profit from calling at this point is approximately
0.32 * 42.750 + 0.68 * 20 = 27.280.

On the other hand, if I fold then the stacks will be (1496, 11011, 993) which is worth $28.749 to me according to PI-FP ($28.552 according to ICM).

So folding is more profitable than calling by 1.469% of the prize pool, which is actually very significant. So it is a clear fold for me.

Now let's analyze button's decision after he raises, I call, and BB shoves. Let's assume he has some junky hand like K5o, which wins about 22% of the time against a representative hand for BB like 99 (it is pretty hard to estimate button and BB's exact ranges since I don't know them very well). Let's assume that button will win 22% of the time if he calls and I call behind, which seems pretty reasonable.

If he calls, I call behind, and he wins, then with probability around 0.68 BB will beat me for the sidepot and button will be heads-up with the chip lead, while with probability around 0.32 I will win the sidepot, and the stacks will be (1006, 3965, 8529). The first scenario is worth $42.636 to him, while the second is worth $42.573 to him.

So his expected profit from calling is:
0.22*(0.68*42.636 + 0.32*42.573) + 0.78*20 = $24.975.

If he folds, I will fold behind as described above and the stacks will be (1496, 11011, 993) with him having to post the BB next hand, which gives him an expected payoff of $24.631 according to PI-FP.

Thus, calling is worth about 0.344% of the prize pool more than folding for him. This is still fairly significant, and suggests that it is a pretty clear call for him even with a bad hand like K5o. So his fold was probably a mistake, and there is a good chance he should have folded initially as well, though I don't know what hand he had.

Online site for pokerbots

2009-08-08T11:36:00.001-04:00

It seems that it is unanimous among online poker sites to have strict anti-bot rules. As far as I know, all sites prohibit bots and will ban and seize the funds from any account suspected to be using a bot (without even having to present any proof). The reason for this appears to be that sites fear people would no longer want to play if they thought they were playing against bots, who presumably would use "advanced mathematical techniques" to take their money. In the competitive industry of online poker, this is a reasonable fear since people can easily switch over to another site if they suspect they are playing against bots on one site. The abundance of threads on the 2+2 forum of the form "Omg is player x on site y a bot???" (e.g., http://forumserver.twoplustwo.com/28/internet-poker/possible-sitngo-bot-518594/) makes it clear that many people are strongly anti-bot. This fear is not unfounded, as bots are getting better and better every year, and can already beat some of the best humans in some forms of poker (e.g., two-player limit Texas hold'em).

On the other hand, there are many potential upsides of allowing bots to play on sites. For one thing, they could play many more tables at a time than humans, bringing in much more money to the site because they will have to pay rake on each table. While humans can't really play more than 20 or 30 tables at a time, bots can play hundreds or even thousands (depending on how much cpu they have). Additionally, bots could play 24/7 while humans obviously need to take breaks to eat, sleep, etc. Many people (including myself) might even enjoy playing against bots, especially if they thought they could exploit obvious weaknesses in them.

My proposal is not to have the major sites suddenly allow bots, since I'm sure many people would be against that and probably move to another site. However, I do think either adding "bot-optional" tables, or starting a new bot-friendly site could be a great idea. I suppose the latter might make more sense, because if a site has bot-optional tables, people might still (irrationally) think "omg site x has bots!" and switch sites. On the other hand, I don't see how anyone could really have a problem with a new site that allows bots. The site could label all the players as a bot or human, so people know whom they are playing against. I'm honestly shocked that no bot-friendly site has arisen (at least not to my knowledge). In 1971 the NASDAQ was developed as the first electronic stock exchange (e.g., trades were all made by computer agents or "bots"). Now it is the largest electronic stock market in terms of both dollar value and share volume. I really think the same thing could happen in the online poker industry.

One other issue worth noting is that computers are only competitive with people in one form of poker which isn't even very popular (two player limit Texas hold'em). If this were the only form of poker played, then allowing bots might not be a great idea since eventually all the bots would be near-optimal and no one would want to play them. On the other hand, in most popular variants -- like no limit Texas hold'em, tournaments, multiplayer cash games, Omaha, etc. -- computers are no where near as good as the top humans, or even many low stakes recreational players. Thus, having a large-scale bot-friendly site could actually be a great resource for researchers in artificial intelligence to obtain large amounts of experimental data for these challenging open problems.

New blog

2009-08-08T03:45:00.000-04:00

So I think I'm going to continue blogging for a while and see how it goes. I previously blogged about my trip to Vegas earlier in the summer for the WSOP, which you can check out here: http://samsvegastrip.blogspot.com/. That blog focused mostly on analyzing poker hands I played. This blog will probably cover a wider range of topics such as poker and gambling theory, computer science, and game theory. I'll try to make at least one fairly substantial post every week, hopefully leading to interesting feedback and comments from you guys. More to come ...