Monday, September 8, 2008

The Fraternal Order of Delta Hand

"So, you're dealt a hand, right?" "No, I'm Alpha Omicron Pi."

Explanation: Recently, I've been pondering a probability issue in poker. I attempted to explain it to my wife last night, resulting in the above conversation. Now, to her credit, she was joking, and it was so funny I left the room to go write it down. That pretty much ended our conversation, though. Things like this happen when you marry someone who was in a sorority.

Now Down To The Nitty-Gritty: My problem is this: In Texas Hold'Em, what is the probability that my starting hand will win against n other starting hands. For example, if you are dealt pocket aces and are playing heads up, you have about an 85% chance of beating a random hand.

It's easy to design an algorithm for this. For a given starting hand, iterate through all other possible starting hands (or combinations thereof) and generate all possible combinations of community cards for those starting hands, keeping track of the total wins for your starting hand and the total number of permutations considered. On my home machine, given the best algorithm I've come up with so far, I think I can perform this computation for n=1 for all possible starting hands in under a day. Last time I did this was a while ago, so I don't remember exactly how long it took, but I've done it before in a reasonable amount of time.

Using the same algorithm for n=2, however, increases the complexity to the point where it can take days to consider a single starting hand. There are 169 possible starting hands, so the computation for all possible starting hands cannot be completed in a reasonable amount of time. I need a better algorithm, and that's what I've been working on.

Special Blog Bonus: This problem mocks me, as the snake mocks the snake charmer* in this Far Side:

*Yeah, my segue is a stretch. So what? You try connecting a snake in Groucho glasses to a complex combinatorics problem.