Eureka!! My first successful analysis (Mississippi Stud)
Mississippi Stud is a good first game to analyze because, at ~156M outcomes, it’s relatively small. All in all, it took me about 3 1/2 days to code and test (2 days a while back and 1.5 days just now), a far cry from the longer stretches I’ve put into BJ, VP, and general poker code (though the general poker code is used here). My final runtime was around 5 minutes, compared to a 23 second benchmark that Jopke offered for his code. I used a memoization + mutual recursion technique that I’d worked on with my BJ code which allowed me to easily take out much of the repetition found in the game tree. Unfortunately, this means I can’t get quite as much information back out at the end, for instance, I can’t distinguish between between a hand that followed a 1-1-3 betting pattern and an otherwise similar one that followed a 1-3-1 pattern. But in return, I think the problem is a bit easier to express, at least once you understand the method used. But I could be wrong, and may just be doing things the hard way.
Other than the suffe style deck and corrosponding hand evaluator (translated to clojure), I took a few lines from my BJ code:
(defmacro defn-memo [name & body] `(def ~name (memoize (fn ~body)))) ;found on internet, simplifies memoization slightly
(defn average-over-vec [the-vec] (/ (reduce + the-vec) (count the-vec)))
(defn doseqfor [combineby deck digwith]
(do (doseq [val deck] (digwith val))
(let [vallist (vec (for [val deck] (digwith val)))]
(combineby vallist))))
and then there’s the program,
(def payouts [-1 0 1 2 3 4 6 10 40 100 500])
(defn-memo fold [[hand bet :as gm]] ["fld" (- bet)])
(defn-memo bet1 [[hand bet :as gm]]
(let [b-deck (apply disj s-deck1 hand)]
["bt1"
(doseqfor average-over-vec b-deck
#(let [nHand (conj hand %) nBet (inc bet)]
(if (= 5 (count nHand))
(* nBet (payouts (handtype (eval (vec nHand)))))
((dispatch [nHand nBet]) 1))))]))
(defn-memo bet3 [[hand bet :as gm]]
(let [b-deck (apply disj s-deck1 hand)]
["bt3"
(doseqfor average-over-vec b-deck
#(let [nHand (conj hand %) nBet (+ 3 bet)]
(if (= 5 (count nHand))
(* nBet (payouts (handtype (eval (vec nHand)))))
((dispatch [nHand nBet]) 1))))]))
(def ops [fold bet1 bet3])
(defn-memo dispatch [gm]
(doseq [op ops] (op gm))
(last (sort-by second (for [op ops] (op gm)))))
(/ (reduce + (vec (for [e (combinations s-deck1 2)] (dispatch [(into #{} e) 1]))))) 1326)I'm trying to decide where to next. I'm tempted to make an attempt at Double Draw Poker since that sort of brought me here.
-John
Quote: tringlomaneGood Job!
Thanks :)
Quote: socksThanks :)
WTG, socks! You're well ahead of me on learning to do that.
Three Card Poker might be a good next one. It is simple also and has the added twist of a dealer vs player hand.
A standard challenge is a video poker analyzer.
Quote: WizardCongratulations! I think you would find a Double Draw program would take years to cycle through all the combinations.
A standard challenge is a video poker analyzer.
Have you looked at the DD thread? By reducing the number of hands via suit compression and spreading the work out over a bunch of AWS nodes, I can go through all combinations in a few hours. Unfortunately, my numbers don't exactly match what has been published for DD.
Quote: jopkeHave you looked at the DD thread? By reducing the number of hands via suit compression and spreading the work out over a bunch of AWS nodes, I can go through all combinations in a few hours. Unfortunately, my numbers don't exactly match what has been published for DD.
Yes, iirc, the transposition tables being built here, with my MS program, and with clojure's easy memoization, get me down to about 650k internal nodes on my tree, while covering the 156M leaf game. The data structures are a bit memory hungry, so I'm not sure I can memoize the full 5 card hand + 3 card discard, but if so, I believe the gains should be significantly larger.
Idk, maybe The Wizard has an intuitive (or explicit) sense for how much this sort of technique saves, but I'm not convinced. Until his response, I was just half heartedly considering it, but now, I think I have to give it go now, or at least run a test to see how big of a split hand/discard tree I can cram into memory without doing anything too fancy.
Quote: WizardCongratulations! I think you would find a Double Draw program would take years to cycle through all the combinations.
A standard challenge is a video poker analyzer.
Yes, thanks. I think I'm going give it a try, so I guess we'll see.
I did spend a few weeks on VP before, but I hit a dead end with that fancy trick on your programming tips page, and I had to take a break. I'll definitely revisit it in the future.
Quote: RSWhat language is that?
Clojure. It' a modern Lisp that's built for performance and runs on the JVM.
Quote: DeMangoAny idea what the ev would be if you muck face-low cards?
face-low? JJ's and QQ's? Or face cards and low cards? I guess I'm not sure what you're asking.
Quote: DeMangoSay King, deuce. Know someone that plays that way, just wondering how much worse the ev is.
Oh, gotcha. I'm getting -9.17%, but that's just a quick look. I'm not sure how much faith you should put in that #.
Quote: socksOh, gotcha. I'm getting -9.17%, but that's just a quick look. I'm not sure how much faith you should put in that #.
I'm getting -8.16%
| Hand | 1X ev | Combinations | Probability | Cost Per Hand | Overall Cost |
|---|---|---|---|---|---|
| Unsuited | -0.901429 | 192 | 0.1447963801 | 0.098571 | 0.01427272398 |
| Suited No A | -0.633265 | 48 | 0.03619909502 | 0.366735 | 0.01327547511 |
| Suited A | -0.591327 | 16 | 0.01206636501 | 0.408673 | 0.004931197587 |
| Total | -0.831766875 | 256 | 0.1930618401 | 0.168233125 | 0.03247939668 |
So it costs 3.25% and a base house edge of 4.91%
Quote: richbailey86I read this thread. My response: http://gublecraft.com/gc/halp/files/stacks_image_2.png
LOL!
Quote: mipletI'm getting -8.16%
Yes, I see my mistake. Thanks for pointing that out.
Quote: socksYes, thanks. I think I'm going give it a try, so I guess we'll see.
I did spend a few weeks on VP before, but I hit a dead end with that fancy trick on your programming tips page, and I had to take a break. I'll definitely revisit it in the future.
Ok Wizard, I'm that convinced double draw is hard, and I can't do what I thought I could :(
I'm going to try Three Card Poker as a stepping stone instead.
I also cut the run time on MStud down from 4min to 30sec.
Funny about 3CP. That game is trivial compared to coding MS. But congrats, keep up the good work! There is a lot of room for more analysts in the industry, and you are doing exactly what we all do, figure it out ourselves from scratch.Quote: socksI don't know that anyone cares, but I finally got a correct result for a second game, Three Card Poker. I'm slowly getting better at putting various optimizations into practice and the code runs in about 6 seconds, w/ a couple more seconds for setting things up.
I also cut the run time on MStud down from 4min to 30sec.
I'm going to run my MS code and see the run time for a cycle, hang on ... 8 seconds. Maybe it's that I wrote it in C++, compiled in using g++ -Ofast, and run it on a pretty new Ubuntu quad core box. I use a fast poker library. Glad to send you my code if you want it, just email me.
Quote: socksI don't know that anyone cares, but I finally got a correct result for a second game, Three Card Poker. I'm slowly getting better at putting various optimizations into practice and the code runs in about 6 seconds, w/ a couple more seconds for setting things up.
I also cut the run time on MStud down from 4min to 30sec.
I think that's pretty great, Socks, and I would also encourage you to keep working on it, and let us know where you are on it. Well done.
Quote: teliotFunny about 3CP. That game is trivial compared to coding MS. But congrats, keep up the good work! There is a lot of room for more analysts in the industry, and you are doing exactly what we all do, figure it out ourselves from scratch.
I'm going to run my MS code and see the run time for a cycle, hang on ... 8 seconds. Maybe it's that I wrote it in C++, compiled in using g++ -Ofast, and run it on a pretty new Ubuntu quad core box. I use a fast poker library. Glad to send you my code if you want it, just email me.
Thanks for the encouragement. It's really appreciated.
3CP didn't seem any easier to me. I'm guessing my approach (mutually recursive and memoized) made MS a bit easier to express than it would've been otherwise, especially since I'd explored that technique with an earlier attempt (at BJ). I also took the time to make a really sparse lookup table using a prime #'d deck for 3CP.
I see a way to make both games run faster. Not sure how much, but I'm guessing I can get a good multiple improvement on MS. I just have to figure out how to use mutable arrays w/ multiple cores, instead of the immutable data structures I'm using now.
Quote: beachbumbabsI think that's pretty great, Socks, and I would also encourage you to keep working on it, and let us know where you are on it. Well done.
Thank you. I will keep you updated :)
Okay, I went back and looked at my code. You are right, it was harder than I remembered. I started by scoring all the three-card hands into an array score[52][52][52]. Overall, the program takes about 2 seconds to run.Quote: socks3CP didn't seem any easier to me.
Quote: teliotscore[52][52][52]
Ugh. All of a sudden, my sparse array seems really gimmicky... it seemed clever at the time.
I used all sorts of gimmicks before I discovered that I could increase memory to an array score[52][52][52][52][52] that stores the exact rank of each poker hand (I use ulimit -s 1048576 in Ubuntu). I do a lot of hashing and scoring now for big programs. I'm just waiting until the memory in my box is large enough to store the score all seven-card hands, then we're rocking!Quote: socksQuote: teliotscore[52][52][52]
Ugh. All of a sudden, my sparse array seems really gimmicky... it seemed clever at the time.
Quote: teliotI used all sorts of gimmicks before I discovered that I could increase memory to an array score[52][52][52][52][52] that stores the exact rank of each poker hand (I use ulimit -s 1048576 in Ubuntu). I do a lot of hashing and scoring now for big programs. I'm just waiting until the memory in my box is large enough to store the score all seven-card hands, then we're rocking!
A trillion values? Memory is not your only problem.
My dogs, cat and wife agree with you.Quote: AxiomOfChoiceMemory is not your only problem.
Quote: teliotMy dogs, cat and wife agree with you.
Ha!
Seriously, though, even if you precompute everything, you are not loading 32T of data into memory in no time.
You should just build a datacenter.
Quote: teliotI used all sorts of gimmicks before I discovered that I could increase memory to an array score[52][52][52][52][52] that stores the exact rank of each poker hand (I use ulimit -s 1048576 in Ubuntu). I do a lot of hashing and scoring now for big programs. I'm just waiting until the memory in my box is large enough to store the score all seven-card hands, then we're rocking!Quote: socksQuote: teliotscore[52][52][52]
Ugh. All of a sudden, my sparse array seems really gimmicky... it seemed clever at the time.
Actually, I think I was going the other way. I used an oversized(109MB), but very sparse, array and prime numbered cards, so I could just multiply individual cards to get an index w/o hasing or even keeping hands sorted. I knew I could use lots of memory, and this was the first usage that came to mind. I guess I had prime numbers on the mind.
3cp: 1.6s + 2.2s for setup (the distinction is only important if you want to do multiple runs.)
MStud: 12.2s
Quote: CrystalMathI was just curious about my run time on 3CP, and it averages 250ms. I haven't done a MS analyzer, though.
Nice. A few minor refinements got me down to 1.3s. There are a few more rough edges, but much of what's left is likely my choice in language. Clojure is going to be slower than c/c++.
Quote: teliotQuote: teliotscore[52][52][52]
I'm just waiting until the memory in my box is large enough to store the score all seven-card hands, then we're rocking!
If you use a single-dimensional array for the exact number of combinations, such as score[22100] or score[2598960] or score[133784560], you can do it using the bare minimum amount of memory. PM me if interested.
I don't do PM's. Another way?Quote: JBIf you use a single-dimensional array for the exact number of combinations, such as score[22100] or score[2598960] or score[133784560], you can do it using the bare minimum amount of memory. PM me if interested.
Are you saying that you can get a min-sized array without that constant factor?
Quote: AxiomOfChoiceI thought that the whole point of this was do to lookups as quickly as possible. With a min sized array or hash table you can get constant-time lookups and minimal memory usage, but there is a significant multiplicative constant factor to calculate the hash or the array offset or whatever you choose to do.
Are you saying that you can get a min-sized array without that constant factor?
If you use multi-dimensional arrays, there is a behind-the-scenes overhead of calculating the offset into it, which is fastest if the dimensions are all powers of 2 since the compiler can use bit-shifting to compute the offset. If you use a single-dimensional array and calculate the offset yourself, the net effect is about the same (in my opinion). A benchmark would be necessary to compare, but I would hazard a guess that with larger arrays, using the combination approach is faster. Especially if you are just iterating through every possible 5-card hand, then all you do is increment an index by 1 each iteration, which is about as fast as you can get.
Quote: JBIf you use multi-dimensional arrays, there is a behind-the-scenes overhead of calculating the offset into it, which is fastest if the dimensions are all powers of 2 since the compiler can use bit-shifting to compute the offset. If you use a single-dimensional array and calculate the offset yourself, the net effect is about the same (in my opinion).
Yes, it seems like walking the 2+2 graph is faster than letting the computer do the indexing using a 7 dim array, but it seems like it would choke on memory accesses for random lookups. But if you manage the larger 52^7 array yourself, you can get the best of both worlds (once memory is available)
edit: I meant, "is faster for continuous blocks of hands"
http://specialk-coding.blogspot.com/2010/04/texas-holdem-7-card-evaluator_23.html
First, you need some precomputed arrays to hold the results of combin(n,k) where n <= 52 (or a larger deck size if applicable) and k >= 2 and k <= 5 (or a larger number of cards in the hand).
At design time, the value of k is always known, so I use separate single-dimensional arrays for k = 2 to 5. I call them Choose2[], Choose3[], Choose4[], Choose5[]. These should be populated with combin(n,k) values so that, for example, Choose5[52] = combin(52,5) = 2598960. "Invalid" possibilities such as Choose5[4] = combin(4,5) must have a zero value. Excel throws an error for these cases, but we need a zero, which is more accurate in my opinion, since there are zero ways to choose 5 items from 4 anyway.
int[] Choose2 = { 0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171,
190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595,
630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225,
1275, 1326 };
int[] Choose3 = { 0, 0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816,
969, 1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654, 4060, 4495,
4960, 5456, 5984, 6545, 7140, 7770, 8436, 9139, 9880, 10660, 11480, 12341,
13244, 14190, 15180, 16215, 17296, 18424, 19600, 20825, 22100 };
int[] Choose4 = { 0, 0, 0, 0, 1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380,
3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751,
27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390,
101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876,
230300, 249900, 270725 };
int[] Choose5 = { 0, 0, 0, 0, 0, 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188,
8568, 11628, 15504, 20349, 26334, 33649, 42504, 53130, 65780, 80730, 98280,
118755, 142506, 169911, 201376, 237336, 278256, 324632, 376992, 435897,
501942, 575757, 658008, 749398, 850668, 962598, 1086008, 1221759, 1370754,
1533939, 1712304, 1906884, 2118760, 2349060, 2598960 };Now, to score every possible 5-card hand, start with an index at zero and loop through the cards as follows:
int i = 0;
for (int c5 = 4; c5 < 52; c5++) {
for (int c4 = 3; c4 < c5; c4++) {
for (int c3 = 2; c3 < c4; c3++) {
for (int c2 = 1; c2 < c3; c2++) {
for (int c1 = 0; c1 < c2; c1++) {
score[i++] = ScoreHand(c1, c2, c3, c4, c5);
} } } } }where ScoreHand() is your hand-scoring function.
----
If you have five card variables (c1, c2, c3, c4, c5) all ranging from 0 to 51 with no duplicates, you can calculate the offset into the score[] array as follows:
1) Sort the variables such that c5 is the highest and c1 is the lowest. I use the following code to sort them using XOR swaps:
if (c1 > c2) { c1 ^= c2; c2 ^= c1; c1 ^= c2; }
if (c1 > c3) { c1 ^= c3; c3 ^= c1; c1 ^= c3; }
if (c1 > c4) { c1 ^= c4; c4 ^= c1; c1 ^= c4; }
if (c1 > c5) { c1 ^= c5; c5 ^= c1; c1 ^= c5; }
if (c2 > c3) { c2 ^= c3; c3 ^= c2; c2 ^= c3; }
if (c2 > c4) { c2 ^= c4; c4 ^= c2; c2 ^= c4; }
if (c2 > c5) { c2 ^= c5; c5 ^= c2; c2 ^= c5; }
if (c3 > c4) { c3 ^= c4; c4 ^= c3; c3 ^= c4; }
if (c3 > c5) { c3 ^= c5; c5 ^= c3; c3 ^= c5; }
if (c4 > c5) { c4 ^= c5; c5 ^= c4; c4 ^= c5; }2) Calculate the array offset as follows:
Choose5[c5] + Choose4[c4] + Choose3[c3] + Choose2[c2] + c1-----
If you have a combination number (0 to 2598959) and need to decode the cards, here's a way to accomplish this:
int c1, c2, c3, c4, c5;
c1 = combination_number; // the combination number being decoded (0 to 2598959)
for (c5 = 51; Choose5[c5] > c1; c5--); c1 -= Choose5[c5];
for (c4 = c5 - 1; Choose4[c4] > c1; c4--); c1 -= Choose4[c4];
for (c3 = c4 - 1; Choose3[c3] > c1; c3--); c1 -= Choose3[c3];
for (c2 = c3 - 1; Choose2[c2] > c1; c2--); c1 -= Choose2[c2];
// c1, c2, c3, c4, c5 now contain the five card numbers corresponding to this combinationQuote: JBIf you use multi-dimensional arrays, there is a behind-the-scenes overhead of calculating the offset into it, which is fastest if the dimensions are all powers of 2 since the compiler can use bit-shifting to compute the offset. If you use a single-dimensional array and calculate the offset yourself, the net effect is about the same (in my opinion). A benchmark would be necessary to compare, but I would hazard a guess that with larger arrays, using the combination approach is faster. Especially if you are just iterating through every possible 5-card hand, then all you do is increment an index by 1 each iteration, which is about as fast as you can get.
Oh, I thought we were talking about random access, not sequential.
For something like MS Stud, it seems like, not only will you not be able to iterate through all 5-card hands in order, but your hand will be unsorted when you analyze it. It seems like sorting the hand and then calculating the offset would be a lot slower then teliot's method (although, you make a good point; he could probably increase performance even more by making his dimension sized 64 rather than 52)
Am I missing something here?
Quote: socksHas anyone looked over the specialk eval? I always thought it looked interesting but it seems to get overlooked. In part 2, the author claims to get 250M evals/sec on his 2010 macbook pro.
http://specialk-coding.blogspot.com/2010/04/texas-holdem-7-card-evaluator_23.html
That approach has a lot of fat that could be trimmed.
Quote: AxiomOfChoiceOh, I thought we were talking about random access, not sequential.
For something like MS Stud, it seems like, not only will you not be able to iterate through all 5-card hands in order, but your hand will be unsorted when you analyze it. It seems like sorting the hand and then calculating the offset would be a lot slower then teliot's method (although, you make a good point; he could probably increase performance even more by making his dimension sized 64 rather than 52)
Am I missing something here?
Correct, there's a big difference between sorted and unsorted hands for random lookups. That's one benefit of directed acyclic graph approaches like moritz and 2+2, you keep memory requirements small while also doing away with the sorted requirement.
Quote: AxiomOfChoiceAm I missing something here?
I'm going to take a half step back. It's always hard to predict how things operate in the real world. JB's sorting network probably has everything in the L1 cache, and the arrays being used are all small and will stay in the Lvl2 cache. IIRC, the lvl1 cache has a latency of 1ms, Lvl2 has a latency of 7ms, and RAM is... 100ms? So, yeah... just benchmark it. Sometimes I get carried away drooling over theoretical gains when I shouldn't
Quote: socksI'm going to take a half step back. It's always hard to predict how things operate in the real world. JB's sorting network probably has everything in the L1 cache, and the arrays being used are all small and will stay in the Lvl2 cache. IIRC, the lvl1 cache has a latency of 1ms, Lvl2 has a latency of 7ms, and RAM is... 100ms? So, yeah... just benchmark it. Sometimes I get carried away drooling over theoretical gains when I shouldn't
Well, yeah. If we are talking about an analysis running in 2s or 5s it really doesn't matter -- it's not like you can't wait 5s. Of course for games with more cards the difference might be a lot larger.
