   Poker hand evaluation
  Hi,I've found some very interesting code for evaluating poker hands fast (http://www.codingthewheel.com/archives/poker-hand-evaluator-roundup). I tried it (=The Two Plus Two Evaluator) and it can do millions of hands per second.That allows doing simulations of poker cards, which allows statistically calculating the chances of your poker hand compared with other players with unknown hands.BUT... That's not what this post is about.I was wondering, if it's possible to calculate the chances of winning with your hand, without using simulations, but instead purely symbolic, and faster due to not doing millions of evaluations? For Texas Hold'em.Given:Your hand cards: 2 cardsThe cards on the table: 3, 4 or 5 cardsOne other player has two unknown cards in his hand, and there are a few unknown cards left on the table (2, 1 or 0).What is the chance that you win?To perfectly simulate this, you need to calculate every possible combination of the two cards of the other player and values for the not-yet-flipped cards on the table. With the fast simulation of millions of games per second, this might get calculated in a reasonable time for some cases, but still pretty slow.So could this be done without the simulations but purely based on statistics?Or, alternatively, does there exist an algorithm that can give a rough estimate?I didn't find any when searching with Google, I only found those fast evaluators.Thanks!   
  Sure. First hit on Google.See other links under "texas hold'em odds".Of course, Poker being an interesting game probably keeps odds very close until final card. And most of the time, odds are just that - "given 1 million hands, who wins", while the winners are determined by playing 10 hands optimally.The chances of dying in car crash are well known, yet they can't help one prevent an accident.   ;  Hmm, this article seems to be written for a human, not for computer calculation :)A human sees quite fast based on his cards and what's on the table, what combination to calculate the outs for.But for a computer, I think it needs to try this for any possible combination of cards. Not just for a pair, but for all possible pairs with all possible kickers, and so on. Then it requires again millions of simulations...Unless I'm missing something :)EDIT: Most Poker Odds calculators found online also mention that they use millions of simulations. So I think that this problem is so difficult that indeed the simulations is the only viable solution.   ;Quote:Original post by LodeEDIT: Most Poker Odds calculators found online also mention that they use millions of simulations. So I think that this problem is so difficult that indeed the simulations is the only viable solution.Odds don't change.So the problem becomes a simple lookup table. Index is known state. For 1 known card, there are 52 distinct probabilities (less due to symmetry).Quote:Your hand cards: 2 cardsThe cards on the table: 3, 4 or 5 cardsThis makes 5..7 known cards. There are 52^7 different odds. This makes 1e12 different values. But due to lots of symmetry, this number is probably much smaller. This table can now be calculate in advance, and then used to look up probability of each individual hand.Quote:One other player has two unknown cards in his hand, and there are a few unknown cards left on the table (2, 1 or 0).The unknowns do not matter for calculation, since until they are revealed they are, well, unknown, and after they are revealed they cannot be changed.   ;  "This makes 5..7 known cards. There are 52^7 different odds. "This doesn't make sense. Poker hand strengths are based on conditional probabilities and the simple case of particular hands is done in terms of permutations where order don't matter - combinations. The reason monte carlo or simulations are used is cause  the conditional probabilities get too hard to do and do flexibly/generally. In terms of utility, nothing else makes sense really.   ;Quote:Original post by AntheusQuote:One other player has two unknown cards in his hand, and there are a few unknown cards left on the table (2, 1 or 0).The unknowns do not matter for calculation, since until they are revealed they are, well, unknown, and after they are revealed they cannot be changed.Maybe I didn't explain everything well enough, but the unknowns do matter here. Because, they're really unknown, which means, iterating through all possible combinations they can be.The chance you win can be calculated like this at the river:Iterate over all possible hand combinations of the opponent (this are 990 combinations: each card is one of 45 cards, the other 7 are in your hand and on the table). For each combinations, check if you or the opponent wins. Add 1 if you win. At the end, divide this through 990.At the flop, there are 4 unknowns, two player cards and two table cards. This requires 178365 iterations if I didn't make a mistake, and that goes very fast in fact.The code from the "2+2 forum" mentioned in my first post, uses a generated table that is 123MB in size, to evaluate the best 5-card combination formed by 7 cards.So I don't even need Monte Carlo for a single opponent, I can just check every possible combination. But if I want to extend this to multiple opponents I'll need to take random samples indeed.So I got a solution that works fast enough now. I'm still curious if there's an analytical way that doesn't involve brute-force iterating over all possibilities or Monte Carlo integration.   ;  I've wrote a bot to play online with real money and it used AI rules, not even statistical analysis. I was going to go that route until I stumbled on this little gem:You need to calculate what everyone might have, so it's not just your 2 hole cards and 5 on the board.For example, if the suit of a king turns someones low straight into a flush, and your best hand is a straight draw to king, then even if you get the king you still lose if its a heart to the other guys flush. You can't know who needs what, but you surely need to factor in these, "I just lost my house by getting the card I wanted" own goals.There's probably other shit going on as well that means you really must simulate for each player as well as yourself and then the combos get truly biblical.   ;Quote:Original post by LodeMaybe I didn't explain everything well enough, but the unknowns do matter here. Because, they're really unknown, which means, iterating through all possible combinations they can be.The probability of winning depends exclusively on the 7 known cards, as far as player is concerned - unknowns do not affect probability of winning, since the unknowns cannot be fed into the algorithm. This is why the table above is 123MB in size: 52 choose 7 = ~133 million. Unknown cards would matter if deck history had to be taken into consideration.Individual hands might need to be brute forced though, but that only needs to be done once. Same for multiple players.Quote:But if I want to extend this to multiple opponents I'll need to take random samples indeed.If more than 2 players are in a game - do you see more than 7 cards? If not - then the table will be different, but still only 52 choose 7 elements large. So just precompute for 3, 4, 5, 6, 7 players.All that can be calculated is defined by number of visible cards. Everything else boils into a single number and doesn't change once computed.   ;  Technically, you do have some information about the "unknown" hands of the other players - their betting patterns. However, that's well beyond the scope of an odds calculating algorithm.   ;  You may also want to find out how card counting works....The probability of a given hand is well known and documented. A simple look-up will tell you the relative value of a given hand. Eliminating possible hands based on known cards is also a viable method. To avoid the brute force method try working off the assumption each player recieved a best possible hand untill that possibility can be eliminated. For example if they have a diamond and a club then a flush is not possible. If they show 2 cards that are too far apart for a straight then that also can be eliminated.   