I’ve just requested sourceforge space for my latest mini-project: Poker Analysis. I’ve been a big fan of poker for years, and am pleased to see everyone is catching up with me finally with the boom of Internet poker. I’ve started playing a little online, and it set me thinking about the algorithmic aspects of analysing the game. Obviously, the real skills of poker are about predicting people’s actions, but before you can do that you need to be able to see what hand you’ve got and what possibilities are out there, and that stuff is entirely deterministic.
I like small, self-contained challenges, so I set about writing a program to play every two-person game of Texas Hold ‘Em poker that could ever happen, and ranks the two-card hands you can have in order of how many games they win. Obviously most people have a pretty good idea of which hands are good or bad, but I bet there would be some interesting results to see the full ranking.
Of course, I’m sure lots of people have done this before, but I want to do it too! Also, of course, it doesn’t matter how good your hand is in the grand scheme of things, just whether it beats the other hands out there, but bear with me: I’m interested in the results.
The major challenge is getting it to run fast enough, and that is what I’m finding interesting. I’ve already changed my algorithm several times and made huge improvements in execution time, but to run through all the trillion or so (I think) hands would still take several years to execute on my home machine, so I’ve got some work still to do.
There are 2 major parts to the algorithm: enumerating all the hands you could get, which sounds easy but is in fact slightly tricky, and difficult to do perfectly if you want to avoid repeating redundant analyses, and finding out what hand you have (e.g. pair, flush). I’m pretty happy with my current implementation of the second, but I’ve got quite a lot of work to do on the first.
To analyse what hand you’ve got I’m taking an approach where all the real work is done when you sort the hand, and then looking for pairs or straights is easy since the cards are already next to each other. I then re-sort the cards so that the same suits are next to each other, and that makes it easy to find flushes. The part I’m really happy with is that the way I choose hands to analyse means they are already sorted, and when I transform them into the sorted-by-suit instead of by number order, I have very little work to do the way I’ve done it. (Some slight extra complication is added by the need for aces to be either high or low in straights.) This means that deciding what hand you’ve got is pretty quick, and I am able to enumerate and analyse every 5-card poker hand (2.6 million hands) in 4 seconds on my home machine.
I believe I might be able to speed up the analysis a little by changing my encoding of cards which at the moment is just consecutive integers (e.g. 0=2c, 1=3c, 2=4c, …, 12=Ac, 13=2d, …) but might be better to have each suit starting at a power of two to allow the use of the shift operator instead of %13 or something, but I’m happy for the moment. Where I need to improve is in writing the code that enumerates all the hands. As I have it at the moment, it plays every 2-card hand against every other 2-card hand for every 5-card set of community cards (but obviously preventing repeats of the same card) but this is hugely redundant (something like 24x?) since the suits are symmetrical. Exactly how much redundancy I can squeeze out of it is what I am thinking about now.
Anyway, hopefully soon the code will be in sourceforge CVS, and when I’ve achieved my goal of examining all games I’ll make a release. Hopefully in the future I’ll make it accept as arguments the current situation in a game and output the probabilities of each player winning.
Share on Mastodon