ChrisE
ChrisE
Joined: Apr 13, 2013
  • Threads: 2
  • Posts: 32
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
JB
Joined: Oct 14, 2009
  • Threads: 334
  • Posts: 2087
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
ChrisE
Joined: Apr 13, 2013
  • Threads: 2
  • Posts: 32
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
JB
Joined: Oct 14, 2009
  • Threads: 334
  • Posts: 2087
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
ChrisE
Joined: Apr 13, 2013
  • Threads: 2
  • Posts: 32
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
MangoJ
Joined: Mar 12, 2011
  • Threads: 10
  • Posts: 905
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
ChrisE
Joined: Apr 13, 2013
  • Threads: 2
  • Posts: 32
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
CrystalMath
Joined: May 10, 2011
  • Threads: 8
  • Posts: 1767
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:

royalstraight flush4 of a kindfull houseflushstraight3 of a kind2 pairjacks or betternothing
11007600924

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
ChrisE
Joined: Apr 13, 2013
  • Threads: 2
  • Posts: 32
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
ChrisE
Joined: Apr 13, 2013
  • Threads: 2
  • Posts: 32
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
--; }
}
}
}

  • Jump to: