How does software that calculates winning probability of a Texas Hold'em or Omaha hand against 8 random opponent hands work?

Question

So there are Texas Hold'em computer games where you play up to 8 opponents and supposedly some of these computer games tell you your probability of winning assuming your opponents hands are all random. In case someone doesn't know, in Hold'em each player is dealt 2 private cards and then eventually 5 community cards are dealt in the middle (first 3, then 1, then 1 more), and the winner is the player who can make the best 5 card poker hand they can using any combination of their 2 private cards and the 5 community cards. In Omaha, each player is dealt 4 private cards and there are still 5 community cards and the winner is the player who can make the best 5 card poker hand using 2 private cards and 3 community cards.

So, in Hold'em, for any given player's private hand, there are over 10^24 ways that 8 opponents' private hands and the 5 community cards could be dealt. So how do they calculate/estimate your probability of you winning in the beginning, assuming your 8 opponents' hands are random? In Omaha the situation is even worse although I've never seen an Omaha computer game that actually gives you your odds against 8 random opponents' hands. But anyway, are there any programming tricks that can get these winning probability calculations done (or say, correct within 3 or 4 decimal places), faster than brute force? I'm hoping someone can answer here who's written such a program before that runs fast enough, hence why I'm asking here. And I'm hoping the answer doesn't involve random sampling estimation, because there's always a small chance that could be way off.

Answer 1

I would use a pre-computed odds table instead of on-the-fly computation. Tables that list these are extremely easy to find, and have existed for quite some time so they are proven tools. It would be fairly simple to match your hole cards + community cards to the percentage listed in a pre-computed table, and return the value to you instantly, skipping on-the-fly computation time.

There are only 52 cards in a deck(classically), so if you simply find all the possible solutions ahead of time it is much faster to read from those instead of re-computing the odds for every hand on the fly.

Here's a link to an incomplete odds table: http://www.learn-texas-holdem.com/texas-holdem-odds-probabilities.htm

I'd think about it like password-cracking. Instead of brute-forcing every character individually, use a list of common password to decrease compute time. The difference in this case is you know every possible combination ahead of time.

Answer 2

As you identified the expected win rate is an intractably large summation and must be approximated. The standard approach is to use the Monte Carlo method which involves simulating various hands over and over and taking the empirical average: #wins/#games.

Interestingly, the (MSE) error of this approximation approach is independent of the dimensionality (number of combinations) specifically, letting X = 1 if you win, 0 if you lose, MSE = var(X)/N = p*(1-p)/N where p = Prob(X=1) (unknown), and N is the number of samples.

There are a whole host of different Monte Carlo techniques that can improve the variance of the vanilla sampling approach, such as importance sampling, common random numbers, Rao-Blackwellization, control variates, and stratified sampling to name only a few.

edit: just saw you are looking for a non-random approximation approach, I doubt you will have much luck with deterministic approximations approaches, I know that the current state of the art in compute poker research uses Monte Carlo methods to compute these probabilities, albeit with several variance-reduction tricks.

Regarding "because there's always a small chance that could be way off" you can always get a high probability bound on the error rate with Hoeffding's inequality.