Gary Kjos
garykjos at gmail.com
Thu Jan 22 14:55:24 CST 2015
Forwarding this message to the list for Alan Lawhon..... ---------------------------------------------------------------------------------------------- Caveat Emptor!! Don't tackle this challenge unless you have some spare time ... (If you have a very high IQ and/or great programming aptitude, this is your opportunity to shine.) This is a tough programming problem which will require really good thinking. It will be helpful if you have knowledge of the game of poker, although this is not a strict requirement. (Rudimentary poker knowledge will aid your understanding of the problem.) This is not a test of your coding skills per se. Knowledge of a particular programming language - or the tricks and nuances of a particular programming dialect - is not necessary. This challenge is more a test of your logical thinking skills and your ability to write an elegant algorithm that solves a very specific problem. Full Disclosure: I don't know the solution to this challenge as I just thought of this and I have not looked on Wikipedia (or anywhere else) to see if there is a posted solution. (The algorithm probably is posted on some programming site or poker site somewhere, but the point of this challenge is to see just how good you are at solving a "real world" programming problem.) OK, all the caveats are over, so let's get to the challenge! The game is Omaha high/low split poker or "Omaha/8" for short. The challenge is to write an algorithm which correctly identifies the winner (or winners) of the pot and correctly distributes the proper share of the pot to each winner. (Sounds simple, doesn't it ...) First, a review of Omaha/8 rules and how the game is played are in order. https://en.wikipedia.org/wiki/Omaha_hold_%27em#Omaha_hi-low_split-8_or_better The rules are fairly straightforward. In a typical (full table) ring game, up to ten players will be dealt cards. Each player is dealt four "hole cards" face down. In fixed-limit Omaha/8, there are four rounds of betting. The first round, (i.e. pre-flop), occurs before the first three board cards (the flop) are placed (face up) on the table. The second round of betting occurs after the flop. The third round of betting occurs after the fourth board card (i.e. "the turn") has been dealt. The fourth (and final) round of betting occurs after the fifth board card, (i.e. the "river"), is placed on the felt. (All five of the board cards are dealt face up.) After all the betting has concluded, players who have not folded their hands turn their hole cards face up so that the dealer can determine the winner(s). This is the proverbial showdown. Omaha/8 is similar to Texas Hold 'Em in that five community cards are dealt face up on the table, (i.e. the "board"), but that's where the similarities end. The general rule in poker is that the best "five card hand" wins the pot. However, in split pot poker variants, (such as Omaha/8), you can have two winners - the winner of the "high" hand who gets half of the pot - and the winner of the "low" hand - who gets the other half. The winner of the high hand is determined by the rules of straight poker: Two pair beats a pair, three of a kind beats two pair, a straight (any five cards in sequence) beats three of a kind, and a flush (any five cards of the same suit) beats a straight. A full house, (three of a kind plus a pair), beats any flush - with the notable exception of a straight flush which is five cards all of the same suit and all in sequence. (The best possible straight flush is a Royal Flush which is the Ace, King, Queen, Jack, and Ten all of the same suit.) Four-of-a-kind beats a full house. The trick (and the catch) in Omaha/8 (as opposed to Texas Hold 'Em) is that you must use two (and only two) of your four hole cards - combined with any three of the five board cards - to form your best five card poker hand. (This varies from hold 'em in that you may use any combination of your two hole cards and the five board cards to form your best five card poker hand.) So, in a typical showdown, the best "high" five card poker hand wins (at least) half of the pot. So what about the other half of the pot? That's where the "low" comes in ... For a low to exist in Omaha/8, you must combine any two of your four hole cards (from an 8 on down to an Ace) with any three of the five board cards that are also 8 or lower. (In Omaha/8 the Ace counts as both a high and a low card. You can use it either way.) Example: If three of the five board cards are 8, 5, and 3; then a low is possible. If the three [low] board cards are 8, 5, and 5 - and there are no other low cards on the board - then a low is not possible. There must be [at least] three "different" low cards (eight or lower) on the board for a low to be possible. In addition, if only one (or none) of a player's four hole cards are 8 or lower, that player cannot have a low. If there is no qualifying low at showdown, the high hand wins the entire pot. (This is referred to as a "scoop" or scooping the pot.) A player who scoops receives the entire pot. The best possible low hand is 5-4-3-2-A - which is called a wheel. The worst possible qualifying low hand is 8-7-6-5-4 - which I call cr*p. I have never seen an 8-7-6-5-4 low hand win the low half of a pot. Although theoretically possible, (if enough players fold their hands prior to the showdown), an 8-7-6-5-4 hand has probably never won the "low" in Omaha/8. (It's theoretically possible, but I've never seen it in a full ring game.) Obviously, an 8-7-6-5-4 low is the worst possible low hand in Omaha/8. The best possible low hand is a wheel. All the other possible lows are somewhere in between. If you have a hand which wins both the high and the low - say the 5-4-3-2-A all of diamonds - then your straight flush has won the high half of the pot and your wheel has won (or at least tied) the low half of the pot. When you have a hand such as 5-4-3-2-A (all of the same suit) that wins both the high and the low, you say "Nut, nut!!" as you triumphantly turn over your cards at showdown. (In poker, the "nuts" is defined as the winning hand at showdown.) Nut-nut is a scoop and that is the object of Omaha/8 - you want to scoop the pot, (i.e. win all of the chips), by winning in both directions - high and low. What tends to happen more frequently in Omaha/8 is that one (and occasionally two players) will win the high half of the pot and two or more players will win the low half of the pot. (Split pots between a high and a low hand are common in Omaha/8.) In a nutshell, the programming challenge is to write an algorithm which will determine (at showdown) the player (or players) with the best "high" hand, (and the best "low" hand if a qualifying low exists), and award the winning player, (or players in the event of a split), the correct proportion of the pot. Sounds simple, right? I practice Omaha/8 against a software simulation program. Occasionally I have found myself confused as to just who has the best low hand - even when the software is telling me the best low! It seems, at first glance, that this is a trivial challenge, but consider this: Your algorithm will have to account for times when there is a 2-way, a 3-way - and sometimes even a 4-way split for the low! (This occurs when a single player takes the "high" half of the pot, but two players have the same low. This is called "getting quartered," so the two tied hands (for low) each get half-of-half of the pot - or one-quarter of the pot. A simple example illustrates this quirk of Omaha/8. At the final showdown the pot is $800.00. Three players go all the way to the showdown. One player has the A-K-10-9-4 of hearts for the nut flush. (He has the A-K of hearts among his four hole cards and the 10-9-4 of hearts are on the board.) He wins the high half of the pot for $400.00. The other two players each have a "wheel" - 5-4-3-2-A - (suits don't matter) - for the best possible low. The two low hands are tied for the "nut" low, so they split the low half of the pot. They each get $200.00. (This is why this variant of poker is called Omaha "high/low" split. The pot is divided between the player (or players) who have the best high hand and the player (or players) who have the best low hand.) A few pointers before you rush off to demonstrate your superior programming skills ... There is (almost never) a chop for the high hand as there is usually only one hand that can be the winner for high. (You can't have two players on the same hand both claiming a win because they both have four-of-a-kind as one of the hands will be of a higher rank than the other - four Aces beats four Kings. Also, it's impossible for two (or more) players to both have a straight flush for high. (This is due to the fact that they must use exactly two cards from their four hole cards and any three - but only three - of the five board cards to form their best five-card [high] poker hand. You can't have three clubs and three spades on the board as the board cards are limited to five, so it's impossible to have two players both with a straight flush.) It is extremely rare in Omaha/8, but it is possible for two (or more) players to split the high if they both have the same straight - any five cards all in sequence such as 9-8-7-6-5 - since suits don't matter with a straight. However, if one player's "straight" just happens to be five cards all of the same suit - such as the 9-8-7-6-5 of hearts - then he has a "straight flush" and a flush (i.e. any five cards of the same suit) beats any straight. In Omaha/8, you'll play 1,000 hands and (maybe) see three or four hands where there is a tie for the high involving two players with the same straight. (You'll also occasionally have a hand where two players both have the same full house and thus split the high half of the pot.) Here's where determining the low can get real hairy ... How do you split the pot when three players all stay in to the showdown and all three have the same qualifying low? If three players all have the same low, then the player who wins the high hand gets one-half plus one-sixth of the pot. The other two players get one-sixth of the pot each. Got that? This is rare, but there have been showdowns in Omaha/8 where four players all have the same low. (An example of this would be four players who all have A-2 among their four hole cards with 9-9-5-4-3 on the board. All four players have a wheel for the nut low! This is rare in Omaha/8 - it happens maybe once every 500 hands. Your algorithm has to correctly determine how many players (at showdown) have the nut low and, based on that determination, award the correct amount of the pot to each of the "low" winners. (Generally, in Omaha/8, you want to avoid getting quartered - or worse - since you can win fewer chips than what you put in the pot. This is how you go broke playing Omaha/8 ...) One other factor to take into account when determining the low ... the possibility of a low hand getting counterfeited. (This is mentioned in the Wikipedia article above.) Your algorithm will have to recognize (and reject) low hands that have been counterfeited. Occasionally a player with a counterfeited low will go to showdown anyway, hoping that his [technical] low is the nut low. (I bet some of you thought this would be easy ...) So the challenge is to write a "simple" (Ha! Ha!) algorithm that determines both the winning high and the winning low hands (when there is a qualifying low hand) and correctly awards the pot. Your algorithm must also be able to determine when no low is possible and thus the entire pot is awarded to the winning high hand. Up to the challenge? I've got some ideas on how to generate a solution, but I don't have it all fleshed out. (It was hard enough just figuring out all the information I should include in this post!) While I think and cogitate, and work a 2,000-piece picture puzzle with my mother, those of you who are up to the challenge can show your true programming skills. (The ultimate embarrassment will be if I figure this out first. Ha! Ha!) If any of you have any questions or need clarification on any of this - especially questions concerning Omaha/8 rules - don't hesitate to post your questions. I'll get to them ASAP. If any of you produce a truly elegant (well thought out) solution that I cannot crack, I will be truly impressed. Time to shine. Good luck! Alan C. Lawhon -- Gary Kjos garykjos at gmail.com