"My methodology for video poker analysis" article question discussed in Math/Questions and Answers at Wizard of Vegas

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 13th, 2013 at 3:40:01 PM permalink

Hello!

This is my first post here, so I hope it's in the right spot.

I'm reading this article, and things were mostly making sense to me until I got to the end. There's a block of code, and I can't quite figure out what's happening in it.

r=combin_array[52][2]-combin_array[52-c1][2];

I have no idea what combin_array is. I feel like I'm missing something obvious. I tried doing a Google search for "combin_array" but that didn't help.

If anyone could help, I'd greatly appreciate it.

Here's the article on WoO (The code is at the bottom.)

Thanks!

JB
Administrator

Threads: 334
Posts: 2089

Joined: Oct 14, 2009

April 13th, 2013 at 4:05:02 PM permalink

Quote: ChrisE
I have no idea what combin_array is.

A 2-dimensional array with precomputed values of combin(n, k). For example, combin_array[52][2] holds the value for combin(52, 2) which is 1326.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 13th, 2013 at 8:20:57 PM permalink

Thanks! That clears things up a lot. I'm using C# which doesn't appear to have a predefined combination function, so I modified the ones found to this:


    private static long Factorial(long x) {
        if (x <= 1)
            return 1;
        else
            return x * Factorial(x - 1);
    }

    private static long Combination(long a, long b) {
        if (a <= 1)
            return 1;
        long numerator = 1;
        for (long i = a; i > a - b; i--)
        {
            numerator *= i;
        }
        return numerator / Factorial(b);
    }

I confirmed it works for the test case of [52][2] = 1326. Are there any flaws in this method? This is the original which seems like it's doing far too much extra work, unless I'm missing something:


private static long Factorial(long x)
        {
            if (x <= 1)
                return 1;
            else
                return x * Factorial(x - 1);
        }

        private static long Combination(long a, long b)
        {
            if (a <= 1)
                return 1;

            return Factorial(a) / (Factorial(b) * Factorial(a - b));
        }

JB
Administrator

Threads: 334
Posts: 2089

Joined: Oct 14, 2009

April 13th, 2013 at 9:18:31 PM permalink

Quote: ChrisE
Are there any flaws in this method?

It is slow and could easily overflow even though you're using a long. You should use Excel to compute a grid of values (replace cells that throw a #NUM! error with the value 0) and convert them to a hard-coded array.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 14th, 2013 at 12:28:48 AM permalink

Thanks for the warning, I didn't even consider overflow since I was using the long... I did a test of 100 cards with 5 draws and it's running in ~0.002 seconds for with no overflow exceptions. I'm only running it once on program start and cashing the results, so I think it should be okay.

My main concern is if the math correct though, in the first piece of code?

MangoJ

Threads: 10
Posts: 905

Joined: Mar 12, 2011

April 14th, 2013 at 2:54:06 AM permalink

Quote:
Factorial(a) / (Factorial(b) * Factorial(a - b))

First of all, your Factorial is a quite costly recursive function, you don't want to call it unless you have to.
Second, Factorial(52) is soemthing like 10^67, it won't certainly fit into a long, you would need a 256bit integer for that.
As it's been said, this is quite poor programming. If you cache the results the speed is okay, but still the results are inaccurate.

Third, most of the Factorial factors in combin(a,b) cancel, so why compute all those canceled factors in the first place?
If you check the formula, you see that Factorial(a) / Factorial(a-b) has in fact only b factors, that is a * (a-1) * ... * (a-b+1). Likewise, Factorial(b) has only b factors 1 * 2 * .. * b.

So why not use something like:


unsigned long combin(unsigned long a, unsigned long b) {
   if(a == b) {
      return 1;
   } else if(2*b > a) {
      b = a - b;
   }
   unsigned long nom = 1;
   unsigned long denom = 1;
   for(i=0; i<b; i++) {
      nom *= a - i;
      denom *= i + 1;
   }
   return nom / denom;
}

The first checks are for performance, since combin(a,a) = 1 and combin(a,b) = combin(a,a-b).
The loop just multiplies all significant b factors. Note that the division at the end is an integer division, but as combin(a,b) is always an integer there is no implicit rounding.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 17th, 2013 at 1:25:46 PM permalink

Okay, new question. I'm starting to feel a bit stupid at this point, but the following is throwing me for a loop:

Quote:
To determine the value of holding any four cards, translate the four cards to an index number, and look up the possible outcomes on the draw in the corresponding element of array1. This, however, will include getting the card you discarded on the deal. So you should subtract one from the element in the array associated with the poker value of holding all five cards. For example, if you hold J♣, Q♣, K♣, A♣ and discard 2♥ there will be 1 way to get a royal, 8 ways to get a flush, 3 ways to get a straight, 12 ways to get a pair of jacks or better, and 23 ways to get a losing hand. However, array1 will say there are 24 ways to get a losing hand, including getting the 2♥ on the draw. So you need to subtract the outcome of holding everything from the possible outcomes of the 5 ways of holding 4 cards.

I'm usually pretty good at this sort of thing, I've been making games for about two years now... but I don't really understand what "subtract the outcome of holding everything" means exactly.

CrystalMath

Threads: 8
Posts: 1911

Joined: May 10, 2011

April 18th, 2013 at 8:15:48 AM permalink

Chris,

Let's say that you have the hand AH KH QH JH TH. The outcome from holding everything is a royal.

When evaluating the pay for holding 4 cards, should have an array which gives all the possible outcomes for holding any 4 of the cards.

One of these is -- KH QH JH TH, and the array will include all of the possible wins from this specific hold:

royal	straight flush	4 of a kind	full house	flush	straight	3 of a kind	2 pair	jacks or better	nothing
1	1	0	0	7	6	0	0	9	24

You see here that it includes the possibility for the royal, but we know that it is not possible because the AH was thrown away. So, we must "subtract the outcome of holding everything," which is the royal that we cannot get.

I heart Crystal Math.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 18th, 2013 at 1:38:21 PM permalink

The logic of it makes sense... but I can't figure out how to do it in code.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 24th, 2013 at 10:29:42 AM permalink

I think I may have finally wrapped my head around it, but I'm still not sure. Can anyone tell me if this looks like the right way to do this for array0 and array1? If so I think I can do it for the rest as well.


    //drawPayouts is where the results are stored.  drawArray is where all condenced hands, plus their weight are stored.
    void LoopCondencedHands() {
        for (int i = 0; i < drawPayouts.Length; i++)
        {
            //Five cards
            drawPayouts[array0[HandIndex5(drawArray)]]++;

            //Four Cards
            //Use array1[0] because all lengths are the same.
            for (int j = 0; j < array1[0].Length; j++)
            {
                //Check all five ways of playing four cards.
                //Use "* drawArray[5]" to count the weight.
                drawPayouts += (array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5]);
                drawPayouts += array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[4])] * drawArray[5];
                drawPayouts += array1[HandIndex4(drawArray[4], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts += array1[HandIndex4(drawArray[0], drawArray[4], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts += array1[HandIndex4(drawArray[0], drawArray[1], drawArray[4], drawArray[3])] * drawArray[5];
                //If this is the value of holding all five cards, subtract one.
                if (array0[HandIndex5(drawArray)] == j)
                    { drawPayouts--; }
            }
        }
    }

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 24th, 2013 at 10:30:50 AM permalink

This came out a bit hard to read. Here's the code on pastebin with syntax highlighting:
http://pastebin.com/UQ8w8KLQ

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 24th, 2013 at 10:58:08 AM permalink

New version with the next set of loops, things are looking a little crazy. I'm fairly certain I'm not doing this right!

http://pastebin.com/PAuz94gr

It says to add array2, subtract array1 where it overlaps, then add back in array0. Is this how you do that?

Array2:


for (int j = 0; j < array2[0].Length; j++)
            {
                drawPayouts += array2[HandIndex3(drawArray[0], drawArray[1], drawArray[2])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[4])] * drawArray[5];

                drawPayouts += array2[HandIndex3(drawArray[0], drawArray[1], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[4], drawArray[3])] * drawArray[5];

                drawPayouts += array2[HandIndex3(drawArray[0], drawArray[1], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[4], drawArray[3])] * drawArray[5];

                drawPayouts += array2[HandIndex3(drawArray[3], drawArray[1], drawArray[2])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[4], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                
                drawPayouts += array2[HandIndex3(drawArray[4], drawArray[1], drawArray[2])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[4], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                
                drawPayouts += array2[HandIndex3(drawArray[0], drawArray[3], drawArray[2])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[4], drawArray[2], drawArray[3])] * drawArray[5];
                
                drawPayouts += array2[HandIndex3(drawArray[0], drawArray[4], drawArray[2])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[2], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[4], drawArray[2], drawArray[3])] * drawArray[5];
                
                drawPayouts += array2[HandIndex3(drawArray[0], drawArray[3], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[4], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[4], drawArray[3])] * drawArray[5];
               
                drawPayouts += array2[HandIndex3(drawArray[3], drawArray[1], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[4], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[1], drawArray[4], drawArray[3])] * drawArray[5];
                
                drawPayouts += array2[HandIndex3(drawArray[2], drawArray[3], drawArray[4])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[4], drawArray[1], drawArray[2], drawArray[3])] * drawArray[5];
                drawPayouts -= array1[HandIndex4(drawArray[0], drawArray[4], drawArray[2], drawArray[3])] * drawArray[5];
                
                if (array0[HandIndex5(drawArray)] == j)
                    { drawPayouts++; }
            }

JB
Administrator

Threads: 334
Posts: 2089

Joined: Oct 14, 2009

April 24th, 2013 at 11:05:27 AM permalink

It's hard to say whether or not it's correct.

What you should do is treat each hold as a 5-binary-digit number ranging from 00000 to 11111 binary, with a 0 indicating that the card in that position is discarded and a 1 indicating that the card is held. Make sure the five card numbers are sorted from lowest to highest (or highest to lowest - whichever you prefer; I do lowest to highest). Then convert each 5-binary-digit number to decimal, 0 to 31, and use the bits in the binary representation of the number to determine which totals to add or subtract to compute the counts on the draw. See here for more info.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 24th, 2013 at 11:47:29 AM permalink

Maybe I just need to take a while to think about it, but I'm not really understanding that. This project is starting to make me question myself!

JB
Administrator

Threads: 334
Posts: 2089

Joined: Oct 14, 2009

April 24th, 2013 at 12:30:37 PM permalink

First, loop through every single hand (not just the simplified 134,459 hands). Score the hand and update the global totals for each n-card combination (from the hand) for the outcome the hand represents. For example, if the hand is 2♣ 3♠ 4♥ J♦ J♣, the outcome is Jacks or Better (outcome[1]), so you would increase the total number of Jacks or Better outcomes for each possible n-card combination for this hand.

Then use the global totals to calculate the number of outcomes on the draw for each of the 134,459 unique hands, according to the 32 formulas shown in the Sierpinski Triangle in the above link, and weighting the results appropriately to determine the totals for the game as a whole.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 24th, 2013 at 12:49:50 PM permalink

Okay, I'll have to try that, because that craziness I was trying is up to 45 seconds run time!

Thank you.

JB
Administrator

Threads: 334
Posts: 2089

Joined: Oct 14, 2009

April 24th, 2013 at 2:43:02 PM permalink

Quote: ChrisE
Okay, I'll have to try that, because that craziness I was trying is up to 45 seconds run time!

Thank you.

Don't expect lightning-fast analysis without making even more optimizations. The code in the video poker calculator has several layers of optimizations which make the code very ugly for humans to read and understand, but extremely fast for computers to execute, since execution speed was a higher priority than code readability. I wouldn't be able to explain the end result without explaining all of the optimizations made along the way. I might put together a more detailed explanation of it sometime in the near future.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 24th, 2013 at 10:31:49 PM permalink

Well, when all was said and done the run time is ~1 minute, which isn't terrible but it's far from good. That doesn't matter much because clearly something I'm doing is wrong, because it says full pay JoB has a 0.6786964 return! Something is clearly very wrong. ;) Thanks for the help so far... I'll let you know if I get it working.

CrystalMath

Threads: 8
Posts: 1911

Joined: May 10, 2011

April 25th, 2013 at 6:33:57 AM permalink

Quote: ChrisE
Well, when all was said and done the run time is ~1 minute, which isn't terrible but it's far from good. That doesn't matter much because clearly something I'm doing is wrong, because it says full pay JoB has a 0.6786964 return! Something is clearly very wrong. ;) Thanks for the help so far... I'll let you know if I get it working.

I run under a minute without simplifying the deck, so I know you can do far better. Other than that, my method is nearly identical to JBs.

I heart Crystal Math.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 26th, 2013 at 6:05:25 PM permalink

I think I've found where the error may be coming from, but I'm not sure why.


        Debug.Log(array1[HandIndex4(0, 1, 2, 3)][STRAIGHT]);
        Debug.Log(array1[HandIndex4(0, 2, 3, 1)][STRAIGHT]);
        Debug.Log(array1[HandIndex4(0, 1, 3, 2)][STRAIGHT]);

So that's looking in array1 for how many straights there are. It should be the same for each because they are all suited 2, 3, 4, 5 just listed in a different order. Sadly, they're giving me the index numbers: 0, 20821, and 47 with the results of the debugs being:


6
0
8

This makes zero sense to me, and I have no clue what's going on at this point. Any ideas?

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 26th, 2013 at 6:10:57 PM permalink

Also, just to make sure I even understand the point of array1... this should have all the ways of making a straight, including the starting hand... meaning it *should* return 8 (four aces, four sixes)

#edit:

No, the correct answer is six, because this is a possible straight flush. That means there's only 6 flushes + 2 straight flushes. So they need to be ordered low to high.

CrystalMath

Threads: 8
Posts: 1911

Joined: May 10, 2011

April 26th, 2013 at 7:02:26 PM permalink

Quote: ChrisE
I think I've found where the error may be coming from, but I'm not sure why.
        Debug.Log(array1[HandIndex4(0, 1, 2, 3)][STRAIGHT]);
        Debug.Log(array1[HandIndex4(0, 2, 3, 1)][STRAIGHT]);
        Debug.Log(array1[HandIndex4(0, 1, 3, 2)][STRAIGHT]);
So that's looking in array1 for how many straights there are. It should be the same for each because they are all suited 2, 3, 4, 5 just listed in a different order. Sadly, they're giving me the index numbers: 0, 20821, and 47 with the results of the debugs being:
6
0
8
This makes zero sense to me, and I have no clue what's going on at this point. Any ideas?

The method for finding a hand index relies on the hand being pre-sorted, so only the first one will point to the hand you are looking for, which is good because it contains the correct number of flushes.

I heart Crystal Math.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 26th, 2013 at 8:03:22 PM permalink

My hands are not sorted at all. This appears to be my issue. :(

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

April 26th, 2013 at 10:26:45 PM permalink

Okay, hands all sorted... onto the next issue.

Once you have an array with the best possible outcome after taking all weights into consideration... how do you turn that into the payout percentage?

cherrnp

Threads: 0
Posts: 4

Joined: May 7, 2013

May 7th, 2013 at 11:40:54 PM permalink

I'm working on writing a VP expected value code. I'm not sure about these steps. What should say array1 be? It is for holding 1 card. So we want to loop over 4 of the 5 cards something like this...

int HandIndex4(int c1, int c2, int c3, int c4)
{
int r;
r=combin_array[52][4]-combin_array[52-c1][4];
r+=combin_array[51-c1][3]-combin_array[52-c2][3];
r+=combin_array[51-c2][2]-combin_array[52-c3][2];
r+=combin_array[51-c3][1]-combin_array[52-c4][1];
return r;
}

for(int i=0;i<52;i++)
{
for(int j=i+i;j<52;j++)
{
for(int k=j+1;k<52;k++)
{
for(int l=k+1;l<52;l++)
{
//Calculate the index for these four cards

array1[HandIndex(i,j,k,l)][handscore]++;
// How do I get handscore??
// What do I put for the 5th card to fill out the hand

}}}}

Obviously I'm missing something with these arrays. How do I calculate the hand score?

Do I loop over all possible 5th cards? That would lead to looping over 2,598,960 hands to fill the array?

Thanks for any assistance you can provide.

/// from the wizard's page....
For each of the 5 ways to choose 4 out of 5 cards on the deal, translate the four cards into an index number from 0 to 270,724 (I'll explain how to do that later), and increment element [index number][hand score] of array1 by 1.

For each of the 10 ways to choose 3 out of 5 cards on the deal, translate the three cards into an index number from 0 to 22,099, and increment element [index number][hand score] of array2 by 1.

For each of the 10 ways to choose 2 out of 5 cards on the deal, translate the two cards into an index number from 0 to 1,325, and increment element [index number][hand score] of array3 by 1.

For each of the 5 ways to choose 1 out of 5 cards on the deal, translate the card into an index number from 0 to 51, and increment element [index number][hand score] of array4 by 1.

Increment element [hand score] of array5 by 1.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

May 7th, 2013 at 11:49:08 PM permalink

I'm still not getting this all, but I think this is what you're supposed to do for array1:
You're going through all hands. Each hand will be 5 cards. You want handIndex4 for each of the 5 ways you can organize those cards.

So you deal all cards as hand[ a ], hand[ b ], hand[ c ], hand[ d ], hand [ e ] (I'm going to write these as a, b, c, d, e for shorthand, but that should be hand[a], hand[e], etc.)

Then you do:

HandIndex4(a, b, c, d);
HandIndex4(a, b, c, e);
HandIndex4(a, b, d, e);
HandIndex4(a, c, d, e);
HandIndex4(b, c, d, e);

This is all five ways to choose 4 out of the 5 cards.

Remember, these have to be ordered to get it correct!

cherrnp

Threads: 0
Posts: 4

Joined: May 7, 2013

May 8th, 2013 at 12:14:45 AM permalink

Thats fine for the HandIndex, but what about the hand value? That's the part I don't follow. And then again if you loop over all of them and then do it in the various orders it seems to be redundant. I thought that was the point of the weighting?

Looking at the vpgenius page it looks like you may do it the way you are talking about for the indexing then then use the handscore that you have in the main loop for all 5 cards. Not sure though.

//// from vpgenius
For each of the 5 individual cards, update the total number of hands of type H which include that card (Array #2).

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

May 8th, 2013 at 12:20:15 AM permalink

The hand value is the value of all five cards. What you're saying is that if you look up a, b, c, d... then a, b, c, d, e is one of the many possibilities of what you can draw (hence you increase a, b, c, d by one to represent drawing a, b, c, d, e.)

You don't do it for the various orders. You always order from smallest to largest.

cherrnp

Threads: 0
Posts: 4

Joined: May 7, 2013

May 8th, 2013 at 12:32:28 AM permalink

Giving it a try...will see how it goes. Thanks.

ChrisE

Threads: 2
Posts: 32

Joined: Apr 13, 2013

May 8th, 2013 at 12:33:49 AM permalink

Nevermind. :D

cherrnp

Threads: 0
Posts: 4

Joined: May 7, 2013

May 14th, 2013 at 11:54:43 AM permalink

Retried the setup and it worked for 1 of the 10 3 card discards.

Jump to: