How I Built a Working Online Poker Bot, Part 8: Poker Hand Recognition, Comparison, Enumeration, and Evaluation

Thursday, August 21, 2008

Introduction

Thirty hands an hour.

When you're dealing a real-money game of No Limit Texas Hold'em, that's what you're shooting for. Thirty hands an hour, or roughly one hand every two minutes, like clockwork. Two minutes to wash, shuffle, cut the cards, deal them out in two concentric rings. Two minutes to gently coax a table of beer-drinking adults through four rounds of betting, keeping your sanity in the midst of two and three-way all-ins, split pots and side pots, pot bets and string bets, kills, half-kills, straddles, and other inventions of bored-out-of-their-mind poker players.

"Run it twice, dealer."

After a while, it becomes automatic. You get to where you can eyeball a stack of chips and tell it's one chip short of twenty. You get to where you can cut three, five, eight chips from a stack in one clean motion. Your dealing improves, as your hands learn the curt yet unhurried, almost lazy rhythm of high-throughput dealing. Wash, shuffle, shuffle, shuffle, cut, don't forget the deck guard, go. Two months before you were sending cards flying over the table rails in curlicues, now you're tossing them with pinpoint accuracy.

Like shuriken.

The rituals of the poker table are a kind of language, and as a fluent speaker of this language, you don't stop and think about what the individual words mean, or whether the grammar is correct. The words and the meaning they convey are one and the same. To hear the words is to understand them, but at the poker table, your "words" are bets, actions, the casual tossing of two useless cards into the muck, the spill of meaningful color we call the flop, the turn, the river, whatever. Symbols. Grammar. Inflection. Punctuation.

Language.

Think of a Texas Hold'em hand as a seven-letter word built from a 52-card alphabet. Consonants and vowels. In combination, they have meaning. One of your jobs as a poker dealer is to figure out when one person's "word" is better than another person's, and push the pot accordingly. As a poker player, you have to take things a step further. You have to understand the word. Not just its specific meaning, its denotation; but its connotations, associations, nuance, history. And you have to do all of this in the blink of an eye, automatically, without thinking.

It's almost robotic.

Hand vs. hand range computation

Speaking of robots, this is the kind of stuff at which poker robots excel:

Hand Recognition
Hand Comparison
Hand Enumeration
Hand Evaluation

These terms are often used interchangeably, but I like to give them specific meanings.

Hand Recognition. Figuring out what a poker hand "is": what hand category it belongs to, the number of outs it has, it's equivalence class, and so forth.
Hand Comparison. Taking two or more poker hands and determining the winner.
Hand Enumeration. Enumerating all possibly combinations of cards, whether the cards in a player's hand, or the cards on the board, or both.
Hand Evaluation. Computing the win/loss percentage or pot equity for two or more hands or hand ranges.

And of course, it goes without saying that robust hand evaluation is the stepping-stone to a mature poker A.I. If your poker bot can't do this...

PokerStove

...it's fighting with one arm tied behind its back.

That, by the way, is a screenshot of Andrew Prock's PokerStove, a poker calculator capable of performing hand vs. hand-range analysis across multiple opponents, using exhaustive exploration or Monte Carlo simulation. There are many such tools out there, but PokerStove is the most popular, and probably the most functional, of the lot. PokerStove is free, so if you haven't already done so, I suggest downloading it and getting familiar with how it works.

Because we're going to teach our poker bots and related tools how to do what PokerStove does.

Subjective All-In Equity (SAIE)

Notice I said hand vs. hand-range analysis. The "range" part is crucial, because in poker, rarely are we able to put our opponents on specific hands. Instead, we assign them a range of hands, and narrow that range as the hand progresses. In order to compute our equity, we have to figure out how well our known hand fares not against another known hand, but against the range of hands we believe our opponent has. This is what's referred to as subjective all-in equity or SAIE.

I like Michael Maurer's definition:

SAIE is a player's pot equity given particular beliefs about the possible hands of the opponent(s) and assuming no further betting.

Provided we follow it with Andrew Prock's note in the PokerStove FAQ:

This is not the chance that a hand will win the pot. Rather it is the fraction of the pot that a hand will win on average over many repeated trials, including split pots. The equity for a hand is calculated by dividing the number of "pots" that the hand won by the number outcomes considered. Because two players can split a pot, a player can win fractional pots. Thus, it is possible for a hand to have non-zero equity despite the fact that it cannot win.

For example, in the above screen shot of PokerStove, we can see that the equity of pocket Jacks versus two opponents is around 36%, if we assign each of those opponents a range of [any pair; any AQ or better]. If you took this situation and played it out a million times, you'd find that on average, you'd win 36% of the pot (assuming no further betting, and assuming nobody folds).

This is a useful number to have.

It takes into account the fact that, if one of your opponent has Aces, and the other has Kings, you're equity is lower—only 15%. It takes into account the fact that, if one opponent has AK (any AK) and the other has AQ (any AQ), your equity is higher—about 44%. SAIE provides a sort of weighted average of how your hand fares against each of the hands in your opponents' range, taking into account the likelihood of each specific opponent holding. You see, it's quite a bit easier for an opponent to have AK (12 combinations) than it is for him to have AA (only 6 combinations). And the mathematics need to allow for that.

Once again: this is not the same thing as your chance of winning the pot! Another example should make this clear.

PokerStove

Here, Player 0's chance of winning the pot is only 11%, but his equity is around 57%. This is because most of the time—whenever a 4 or higher falls on the river—the hand is going to be tied. But when a 3 or 2 falls on the river, Player 0 wins with Four Aces and a Four kicker, which beats Player 1's Four Aces and a Three Kicker.

And although Player 1's pot equity is 44%, he has zero chance of winning the pot outright.

That's a contrived situation, but an illustrative one. By thinking in terms of pot equity, rather than chance of winning the pot, we neatly fold all those messy tie-game situations into our mathematics.

The Need For Speed

Believe it or not, calculating SAIE is easy. Calculating it efficiently may not be.

It all hinges on hand comparison: the ability to compare two or more poker hands and determine the winner. If you can do that, all you have to do is programmatically deal out large numbers of hands and start tallying wins, losses, and ties. When it comes to dealing those hands out programmatically, you have two options:

Exhaustive Exploration. Enumerate all possible outcomes: all the combinations of cards fitting your opponents' range times all the possibly combinations of board cards. Keep a tally of how many hands each player wins, loses, and draws. Afterwards, when you've enumerated every possibly combination, express these as a percentage.
Monte Carlo Simulation. Randomly generate hands fitting your opponents' ranges and board cards, keeping a tally of wins, losses, and draws for each player. Over many trials (hands or games), your results will start to converge.

Typically in the game of Hold'em, we use Monte Carlo simulation for preflop matchups, and exhaustive exploration for matchups on the flop or later. You'll notice PokerStove has a radio button allowing you to specify which technique to use although, as Andrew Prock notes:

Monte Carlo simulations work very well for most practical problems, and enumeration driven software is only going to be of interest to the true poker geeks who must have all of their i's dotted and t's crossed. Of course, I'm one of those geeks :)

Whether you're a geek or not, you're going to need throughput: the ability to evaluate large numbers of hands quickly. If you're going to be randomly generating, or consecutively enumerating, millions of hands, you can't afford to do four bubble sorts, nine redundant array copies, a Google search, and send off 3 emails every time you evaluate one of those millions of hands.

You've got to optimize.

(Remember, this is something poker bots and other tools need to do in real time, at multiple tables, on various and sundry hardware.)

So it's got to be fast.

I don't mean 2,000 hands per second fast. That's not fast, that's slow. I mean fast like a bat out of hell. Fast like the wind. Fast like the Flash. Speedy Gonzales. Run Forest Run! fast. Or even—dare I say it—as fast as that paragon of speed and grace, the Roadrunner.

The Roadrunner

MEEP-MEEP!

And the best part?

This is not a wheel you have to reinvent. Highly-optimized hand evaluation code is already written, and is publically available in multiple languages (C, C++, C#, Java, and Python, among others) with support for multiple poker variants (Hold'em, Omaha, Stud) provided you know where to look.

A Small Army of Poker Hand Evaluators

Some people collect butterflies, leaves, flowers; others collect coins, marbles and shot-glasses.

Me? I collect open-source poker code.

If it's code, and if it's about the game of poker, and if it's freely available, I want a copy. Even if the code is written in a language I'll never use. Even if it's slower, messier, or buggier than my existing code. A lot of clever people have devoted a lot of time and energy to building robust poker hand evaluators, you see, and I want to leverage their hard work.

So every time I stumble across a new specimen, I collect it. I haul it out to the garage, open my toolbox, and start hammering away. I clean up the code, throw it into a Visual Studio project or who knows, I might even crack open my Eclipse IDE and do some Java work. Whatever.

There is no "one size fits all" poker hand evaluator, so I want a hand evaluation library which incorporates multiple evaluators within it, all of them written by other people.

Here are just a few (all of which we'll be covering in detail):

So instead of thinking of your poker hand evaluator as a single tool, think in terms of building a poker hand evaluation toolset; a collection of code which can be applied to the specific problems you're facing. Even within the relatively narrow context of an online poker bot, there's a lot of wiggle room. Are you building a multi-table online Texas Hold'em poker bot? If so, you need a fast 7-card evaluator. Are you building something which needs to support Hold'em as well as Omaha and 7-Card Stud. You need a good generic evaluator. And so forth.

If you think of poker hand evaluation as a smorgasbord, rather than a single component, you'll be doing yourself a favor.

Conclusion

Now, I know what you're thinking: where's the code? Where are the algorithms?

Well, it turns out that poker hand recognition, comparison, enumeration, and evaluation are such complex topics, it's impossible to fit them all into a single post, and at the same time, provide and explain the source code for a dozen different pre-existing evaluators. So I've broken these off into a set of background articles, to be published shortly:

Poker Hand Analysis, Part 1: Theory
Poker Hand Analysis, Part 2: 3rd-Party Evaluators and the XPokerEval library
Poker Hand Analysis, Part 3: Hand Ranges and Multiple Opponents

Today, I just wanted to introduce the subject, and tell you how you can make some money by writing hand evaluation code.

Coding the Wheel, in conjunction with a site to be named shortly, will be presenting an award of X dollars (we're not quite sure what X will be yet, but it will be hundreds of dollars, rather than thousands or tens) to the person or persons who can produce a substantial improvement to the hand evaluation code we'll be presenting.

In addition, that person's solution will be highlighted, with full credit, or anonymously if preferred, in a dedicated post on Coding the Wheel and possibly some other sites as well.

There are only a few requirements:

The solution must be unpublished
The solution must evaluate 7-card poker hands
The solution must be fast (noticeably faster than current evaluator implementations)

Full rules to follow. Stay tuned!

Tags: probability, poker hand evaluation, poker bot, online poker, poker

122 comment(s)

First!

The Poker Chesney on Friday, August 22, 2008

Nice intro James, this article is worth it just for the links to 3rd-party hand evaluators. I'd seen a few of those but not all of them. Looking fwd to the contest...

Anonymous on Friday, August 22, 2008

In addition to exhaustive exploration and Monte Carlo-style simulation, you can use precomputed lookups for diff situations (as you probably know) but I think PokerStove uses preflop lookup tables, for certain matchups anyway.

CodifyTheChad on Friday, August 22, 2008

Nice to see you back - you know, these postings will make a great book!

Also - the link http://www.codingthewheel.com/how-i-built-a-working-poker-bot doesn't work...

Terry Smith on Friday, August 22, 2008

I'm definitely gonna have a go at the hand evaluator "competition", you gotta love algorithms. :D

ehsanul on Friday, August 22, 2008

I guess your latest few articles didn't get enough juice so you had to pump out another poker one. anyone that has taken your first ones to heart and have started making a bot will benefit zilch from this article.

it sounds like you have a half-working bot and you want to pay someone to come up with your algorithms for you. try rentacoder

Bismark on Friday, August 22, 2008

Sorry Bismark, it ain't so. The reading public will have a very hard time suprassing the mentioned algorithms. Some of them are completely awesome.

Terry Smith on Friday, August 22, 2008

Bismark, go troll elsewhere please. If you've read any of the articles you would see how much one could gain by implementing this into their homebrew poker bot.

Adam on Friday, August 22, 2008

Do you have an arbitrary environment to test it in?

Jordan on Friday, August 22, 2008

James I agree with Jordan's question. How will you test the solutions? Will you run them on a dedicated machine? Enumerating all hands, generating random hands, both?

I suggest using the 2+2 method. Test the evaluator by enumerating all hands, then test it again by spawning 1 million random hands. Run each evaluator three times. Take the best result.

Anonymous on Friday, August 22, 2008

I AM ALL OVER THIS CONTEST. YOU GUYS MIGHT AS WELL JUST PAY ME THE MONEY NOW ;)

Anonymous on Friday, August 22, 2008

Given a test environment that I can build, I might be able to tweak my program a little bit more.

Jordan on Saturday, August 23, 2008

While AI/algorithms are really cool and I couldn't wait to dive into them, I can't help but feel we left the input/output section a bit too early. I still am unable to get the hole cards or all the table state from the current hand on pokerstars. My poor bot is still blind.

Anonymous on Saturday, August 23, 2008

yeah, I haven't started on that (yet). I haven't finished reading Windows via C/C++ by Richter. So I'm reading the book, and programming the calculators. That way I don't get too bored on one task. There's top down, and bottom up... but for some reason I'm doing both. Just gotta make sure it meets in the middle.

I already win at poker, so I think I can make a decent AI later on. This project will definitely strengthen both poker and programming skills, and you can never get too much of either.

Does anyone know how they catch WoW bots these days? I was thinking that might be even more fun. I just wish there was a guide to the history of the cat-and-mouse regarding WoW.

Jordan on Saturday, August 23, 2008

This is a hand evaluator contest that we ran. All java sources are up for download and prepared with the same example so easy to get them running (and no half working stuff). I don't think anyone can beat RayW 7-card evaluator, in any language or by any approach, so the topic is pretty much closed. http://pokerai.org/pf3/viewtopic.php?f=3&t=16

Indiana on Saturday, August 23, 2008

hi james,

¿Because create your own detoured.dll, because we do not use that comes with Detours ?
¿Detourcreatewithdll have to be in a dll.?

alex on Saturday, August 23, 2008

Hi guys, thanks, and a few things.

We still have a ton of botting-mechanics stuff to do. So we're not leaving this topic (DLL injection, hooking, scraping, stealth, etc.) by any means. We'll be doing some contests here as well.
Indiana is right: Very hard to beat the RayW evaluator. But prior to the RayW evaluator, people were saying the same thing wrt the poker-eval evaluator. And how well is RayW optimized for multi-core?
More importantly, most of the evaluators don't support SAIE computation and so far as I know this has never been benchmarked, at least not making use of very fast core reference evaluators.
Bismarck, the point you're missing is that the RayW and poker-eval evaluators are all we need. We don't need to get any faster. We can use those evaluators as-is and we can use them for the next 10 years. So this is really more of a "for-fun" thing, and a way of paying our respects to some clever work.
And with regard to testing... typical deal: known, isolated hardware, single and multi-core, using multiple testing strategies, and the full source code for all tests and reference evaluators will be provided ahead of time for anybody that cares to take this on.

James Devlin on Saturday, August 23, 2008

"And how well is RayW optimized for multi-core?" -- RayW code is just a table lookup, you can't go any faster than that. It runs for 146,000,000 evaluatons per second. On a multi-core, for full evaluation purposes, you can lookup in several threads, and that's pretty much all you have to do. This isn't available as coding, but is a possible extension that one can easily do.

For a single hand evaluation there is no way to speed this up, as it's really mostly a table lookup, and this is pretty much a "single instruction operation".

P.S. By the way, there is another contest we run since some time with 1k$ reward, for preflop SAIE: http://www.pokerai.org/pf3/viewtopic.php?f=3&t=869

Indiana on Saturday, August 23, 2008

I'm guessing as usual (never have time to lookup/check my statements) But a shouldn't a algorithm running in L1 cache should be faster than a lookup table?!

Nyx on Saturday, August 23, 2008

The porting to C actually achieved 450m+ evaluatons per second. This means that it took less than half of a second to run ALL possible 7-card evaluations.

Indiana on Saturday, August 23, 2008

[i]>P.S. By the way, there is another contest we run since some time with 1k$ reward, for preflop SAIE[/i]

Looks like a good contest! But it's for known matchups correct? (i.e., N players with known hole cards)

The more common situation in play is SAIE vs. multiple opponents with multiple [b]hand ranges[/b]. For example, try running a PokerStove simulation with Ah Ad vs. 9 random hands and watch it bog down.

Is the deadline for your contest still Sept. 15th?

[i]>RayW code is just a table lookup, you can't go any faster than that[/i]

I agree it's tough. Here's the typical usage:

int p = HR[53 + *pCards++];
p = HR[p + *pCards++];
p = HR[p + *pCards++];
p = HR[p + *pCards++];
p = HR[p + *pCards++];
p = HR[p + *pCards++];
return HR[p + *pCards++];

That's an increment, deref, add, array lookup, and store. Then the final bit-shift or mask to extract the hand category or its rank within the category. Not "single operation" but pretty darn fast.

James Devlin on Saturday, August 23, 2008

i've looked at all (okay, almost all) of these evaluators and one thing i never seen any benchmarks for is p. senzee's 7-card evaluator (see link) with the 52c7 table etc. anybody have stats on this?

and I agree with nyx. l1 cache should (might) be the fastest way to go..and other working set optimizations.

Anonymous on Saturday, August 23, 2008

oh and also, cactus kev talks about being approached by one of the major poker software co's and asked for his algorithm, and whether it could be ported to 7-card. whatever became of that?

Anonymous on Saturday, August 23, 2008

All seems very complex. Putting people on a range of hands is hard at the best of times let alone getting a robot that can always do the correct +EV move.

Poker is Rigged | Forums on Saturday, August 23, 2008

Hey James, can you tell how many tables u use to play when playing 30 Hands a hour? c u popo.

popo on Saturday, August 23, 2008

Angry, I don't think Senzee's 7-card evaluator is faster than the 2+2's lookup. I read that entire thread and lol. Can 1 programmer do any better? But I would like to see some hand vs. hand-range benchmarks which use that evaluator..

Angry on Saturday, August 23, 2008

I understand you're just doing an intro here but I really hope the next two parts are hard-hitting like parts 4-7 were. I would say the best posts of the series are 1, 4, 5, 6, and 7. So far.

Anonymous on Saturday, August 23, 2008

To win at poker, you don't have to make +EV decisions all the time. All you have to do is make less theoretical mistakes than your opponents make.