3
$\begingroup$

$2$ people (C and D) decide to play a computer assisted game. The computer is programmed to quickly play as many fair hands (using the equivalent of a fair $52$ card deck), until someone wins the hand so the win will appear instantly when they press a button on the keyboard and then it waits for the next keypress for the next game. The computer is necessary because of how infrequent wins are, thus a real deck of cards would take way too long between wins.

The rules are player C can win if he gets $3$ "gapped" $3$ card straights dealt in order. An A (ace) will be considered the highest rank for both C and D so $A23~567~9TJ$ (T = ten rank) would NOT be a win for C but $234~QKA~789$ would be. There has to be at least a gap of $1$ rank between the $3$ card straights but can be wider as shown in the 2nd example. Note that the individual straights of length $3$ have to be dealt in order but the actual $3$ length $3$ straights don't need to be in relative order (as shown by $234QKA789$). That is still a win for C and need not be $234789QKA$ (although that would also be a win for C). The simplest example of a win for C would be something like $234678TJQ$. This is also the lowest ranked win for C. The highest rank win for C would be $45689TQKA$. Remember permutations are allowed such as $89TQKA456$ is also a win but $243678TJQ$ is not. If you think of each gapped $3$ card straight as a letter. Such as with $234678TJQ$, X=$234$, Y=$678$, Z=$TJQ$, then valid permutations are XYZ, XZY, YXZ, YZX, ZXY, and ZYX.

For player D to win, $2$ pattern classes are allowed. Either any $6$ card straight (such as $345678$) or this pattern: $223344$, $334455$, $556677$... $QQKKAA$.

The computer will keep dealing community (shared) cards until either there is a winner of the hand (not likely) or all $52$ cards are depleted (very likely). The cards are reshuffled after each win and after each nonwin (all $52$ cards are depleted). Permutations are NOT allowed. The straights and patterns MUST be dealt in order. For example, $345678$ is a win for D but $357468$ is not, even though they could be the same exact cards. Suits are irrelevant for the straights and other winning patterns. Any suits are allowed.

So it is a rainy day and they play many hundreds of winning hands to see who gets more wins. The question is who has the mathematical advantage and by how much? A hand that ties can be ignored as they will not count that hand and will continue play. Neither player has any knowledge of the expected probability and both just play on a "hunch" based on the observed patterns to win which they are told about.

The $300$ bounty ends Monday night (Aug 22nd) around 11:59PM (Eastern time) already including the $24$ hour grace period. Other simulations are encouraged but also math solutions or partial math solutions (like how to set it up properly).

Sample data of $3$ million random shuffles can be downloaded here for test purposes and/or analysis for mathematical solutions.:

https://drive.google.com/file/d/0BweDAVsuCEM1amhsNmFITnEwd2s/view

Format is $52$ bytes of data per line and $2$ more bytes for the end of line so $54$ bytes total per line, $3$ million lines. "$2$" = rank $2$, "$3$" = rank $3$... "T" = rank $10$.... All cards are represented by this set of ranks: "$23456789TJQKA$". There are $4$ of each rank in each shuffle (suits are irrelevant in this card game).

Where are the mathematical attempts at solving the probabilities of this card game? How about even some partial solutions like take the winning D patterns and compute the probability of a D win if D was the only player, subtracting out the overcounting cases where $2$ (or more) of those patterns can appear in the same shuffled deck. For example, if we get something like $234567223344$

$\endgroup$
  • 3
    $\begingroup$ As a general rule, games with complicated win/loss rules tend to be easier to analyze by simulation. Program the game and let the machine play out a few million rounds. In this case, it might not be that hard to count the winners for each. $\endgroup$ – lulu Aug 4 '16 at 21:01
  • 1
    $\begingroup$ In Blackjack, for example, the probabilities change dramatically if you play with a depleted deck. In some cases, the advantage actually moves to the player (away from the House, that is). That's why serious blackjack games either reshuffle each round or play with many decks (and still reshuffle more quickly than you might expect). $\endgroup$ – lulu Aug 4 '16 at 21:06
  • 1
    $\begingroup$ there are no general short cuts. As I say, in this case...if you held a gun to my head I'd prefer to play as $D$. It seems to me that as $C$ is building a winner, it will look a lot like a winner for $D$. If, say, $C$ has $234\;67$ then a $5$ wins for $D$ while $C$ still has a long way to go. So, my guess is the game strongly favors $D$. But, like I said, intuition is often wrong...that's why there are casinos. I'd trust a simulation more than my intuition. $\endgroup$ – lulu Aug 4 '16 at 23:34
  • 4
    $\begingroup$ Like I say, the rules are not clear to me. That's why I wouldn't try to simulate it myself. if I were you, I wouldn't trust any one else's simulation for that reason...very high probability of a misinterpretation of the rules. $\endgroup$ – lulu Aug 4 '16 at 23:40
  • 1
    $\begingroup$ this is extremely unclear $\endgroup$ – mercio Aug 15 '16 at 13:48
2
$\begingroup$

Since the winning hands are so rare, I thought about generating them directly, separately for player C and D.

The chances of player D

For a fixed set of six adjacent positions, we already know the odds: the probability of seeing D's winning pattern 1 is $$ P_{D_1}=8\prod_{i=0}^5\frac{4}{52-i},$$ for pattern 2 it is $$ P_{D_2}=11\prod_{i=0}^2\frac{4\cdot 3}{(52-2i)(52-2i-1)}, $$ and the probability for any winning pattern for D at these positions is $$ P_D=P_{D_1}+P_{D_2}. $$

To create a representative winning hand, we first select between winning patterns 1 and 2, respecting the ratio $P_{D_1}:P_{D_2}=512:297$. Next we choose between the 8 or 11 possible ways to assign cards according to the selected pattern at the positions considered, they all have the same probability. Then, we randomly distribute the remaining cards.

Since we don't want to only create winning hands which show a winning pattern at fixed positions, we also want to randomly select these positions. Up to now, nothing depended on that selection, so we can defer determining these positions to this moment. We shuffle the remaing cards together with a special marker that after shuffling is replaced by the cards forming the selected winning pattern. This way we create each pair of a winning hand and six adjacent positions that show a winning pattern in that hand with the same probability. If we forget about the selected winning positions, we are overcounting the winning hands that show $n>1$ winning patterns. To compensate, we could weight these hands with $1/n$. Alternatively, we can reject a winning hand that has a winning pattern before the selected one. This avoids having to use rationals or floating point numbers. I found that I can keep more than 95% of the generated winning hands, so I did that. Now we can generate representative candidate wins for D, next we can test if it is a win for C after all and also reject in this case (after counting it as an interesting outcome).

So what can we do with a stream of representative winning D hands? One thing is to determine the average number of cards needed until it is a win for D. I get 28.963 (after $10^{11}$ experiments, where an experiment consists of finding a winning hand that may then be rejected).

It is also possible to count how often a particular number of cards was needed and compare that to the numbers expected from a uniform distribution:

distribution of number of cards needed for a D win

But there is more! We can use the observed ratio of all D's wins to the wins after the first six cards as an experimentally justified multiplier for $P_D$ (which is the exact probability for D winning after six cards), replacing the rough estimated multiplier 47 that came from the assumption of a nearly uniform distribution. We get a multiplier of 44.66 and D's winning chances as 0.0158%.

The chances of player C

We can use essentially the same idea for player C. The probability of seeing a winning pattern at three triples of adjacent positions is already known to be $$ P_C=3!\cdot 10\prod_{i=0}^8 \frac{4}{52-i} $$ (that calculation only needs that each pattern demands nine different particular cards at each of nine chosen positions).

We select one of the ten patterns and shuffle the remainig cards together with three special marks. Rejecting hands to avoid overcounting is slightly more difficult, because it is not enough to compare the last position needed to see that C is winning, because we might still use different straight first and second triples. However, we can just use whatever triples our algorithm finds as representative for one hand, and check if this agrees with the positions we used to create the winning hand. This time, we have to reject more hands, but we still can keep more than 85%. The following results are again after $10^{11}$ experiments.

The average number of cards needed to see a winning pattern is 41.10, the distribution is very different:

distribution of number of cards needed for a C win

It is a problem that the first value is so relatively close to zero, because it makes the computation of the multiplier less stable. (By comparing $P_D$ and $P_C$, we could have known that before.) After $10^5$ experiments (I didn't look at smaller values), the estimated multiplier for the player D case already had two good digits, while the estimate for the player C case was 50% off. That is no surprise, given that only four occurences of wins after 9 nine cards have been observed. After the $10^{11}$ experiments, 6581830 such wins were observed. The estimated multiplier is 13000 (with three plausible digits), giving a winning chance for C of 0.0153%.

More results

While we create 63.288% of the D wins as pattern 1 wins, only 61.565% percents of the surviving D win hands belong to pattern 1. The ratio of real ties to candidate ties (which can be determined from both simulations) is about 1:31.

Using the observed ratio of real ties and wins at the first possible position, we can again use $P_D$ resp. $P_C$ as "leverage", this time to get the expected frequency of real ties. The D winning data predict one real tie in 43974812 hands, the C winning data predict one in 43961799 hands. The result from the D wins is again more relyable, but seeing both estimates are so close is reassuring.

The program

The program to perform the experiments is written in C++11, compilable with g++ from both Debian stable and oldstable with the option -std=c++11. It is too long to post it here, but if anyone is interested in it (or the detailed results) I will find a way to transfer it. Performing $10^{11}$ experiments took about 32 hours.


Getting better results faster

I found a better way to use my method of getting representative winning hands. If we multiply $P_D$ by 47, we get the sum of the probability of getting a deck that has a winning pattern in the first possible position, and the propability of getting one that has it in the second position, and so on. These events are not disjoint, we are overcounting the decks that satisfy the winning condition in more than one way: we count them twice if they have two winning patterns, three times if they have three etc.

We can estimate the factor by which we are overcounting by looking closely at the randomly created (candidate) winning decks. For all the created winning decks, we sum the number of ways in which it is winning, and divide that by the number of decks we have created. Dividing $47P_D$ by this factor gives D's single player winning chance. If we want to know his chance in the two player version, we have to correct by a factor that we can also estimate: the number of real wins divided by the number of candidate wins. (The candidate wins cancel.) This method is better because we don't depend on an estimate for the number of wins in the first possible position of which there are almost two orders of magnitude less than the number of experiments we have performed. We already get three significant digits after $10^5$ experiments. As single player winning probability we get 0.015787%, for the two player variant we get 0.015776%.

We can do the same for player C with an even better improvement in accuracy, but first we have to find the equivalent of the factor 47. It is the number of ways in wich we can find three disjoint triples of adjacent positions of the 52 cards in the deck. This number is 15180. (We could get this by stars and bars, but I already had a list of them for another experiment: If you take all these possibilities and count how often each position appears as last selected position, the result looks very much like the distribution of the number of cards needed for a C win shown above.) So $15180P_C$ is morally as good an estimate for C's chances as $47P_D$ is for D's, however it is less accurate, it is almost 17% off. Estimating the correction factor again gives three significant digits after only $10^5$ experiments. Eventually, we get 0.015332% as C's single player winning chance and 0.015271% for the two player variant.

(I missed a simpler way to estimate the overcounting factor. We just need to divide the number of experiments by the number of winning decks that we keep as representative. This avoids having to find the number of ways in which a deck is winning, which is slightly tricky for C. However, being able to do it will be useful in the next section.)

Strict bounds for the single player variants

(I'll add this part later. It's nice, but not enough to really prove that D's chances are better.)

$\endgroup$
  • $\begingroup$ Very nice. Can you run your program on the 3 million deck test data to help confirm you are getting the same results? I guess I had the right idea trying to approximately solve this mathematically for D. That is, to figure out out what are the chances of getting a D win in the first 6 cards is, then multiplying that by 47 to account for a win in any deck position after that, pretty much randomly distributed I would think.. $\endgroup$ – David Aug 22 '16 at 3:25
  • $\begingroup$ I already checked your data and reported the result when I mentioned that after fixing the problem with cases like 2223344 I got your results. - Of course it is randomly distributed, but not uniform. There had to be a slight bias to lower numbers, but the peak at 6 surprised me. I guess it's not clearly visible with stats from your ~1.6*10^5 D wins, but after 10^6 wins it begins to show. Simply using 47 as multiplier was a bold decision that worked amazingly well, but not good enough since the odds for C and D are so close. $\endgroup$ – Christian Sievers Aug 22 '16 at 9:28
  • $\begingroup$ How can winning hands be rare? There are about 3/1000 chance of winning, so multiply with 10^50 we get a gigantic number. $\endgroup$ – user202729 Aug 22 '16 at 11:31
  • $\begingroup$ Also this still depends on stimulation. How can you be sure this it's better than plain simulation? $\endgroup$ – user202729 Aug 22 '16 at 11:39
  • $\begingroup$ @user202729 Oh, the wonders of multiplication! Now I see how to win at lotto! :-) $\endgroup$ – Christian Sievers Aug 22 '16 at 11:43
3
$\begingroup$

My simulation program works by first shuffling the entire $52$ card deck and then searching the entire deck for candidate wins for each player, then simply selecting the candidate win with the lowest drawn card position. Normally there is only $1$ candidate win per winning hand as can be seen by only $769$ candidate ties. A candidate tie is when the program detects a possible win for both players, which are normally at different final drawn card positions, but very rarely will be the same. In $22$ cases they were the same, thus resulting in a tie. It was easier for me to let the program search the entire $52$ card deck then to just draw $1$ card at a time looking for winners after each card (after the $6$th card is drawn which is the minimum # of cards needed for a player D win).

I have some results from a simulation program. Also it is interesting that since the game is so close to $50/50$, as the simulation runs, the partial results show C sometimes winning. This is why $1$ million hands is not enough.

$1,000,000,000$ : simulated hands.
$24$ hours : approx runtime using interpreted language.
$11,500$ : approx # of hands played per second.
$3.06$ Ghz dual core Intel : CPU speed but only $50$% used by simulation.
$152,981$ : wins for player C.
$157,822$ : wins for player D.
$49.22$% : $50.78$% ... approx ratio of C wins to D wins.
$99.9689$% : approx percentage of nonwinning hands (deck exhausted without a winner).
$41.1453$ : approx # of average cards drawn for C win (only counting when C actually wins).
$28.9136$ : approx # of average cards drawn for D win (only counting when D actually wins).
$769$ : candidate ties (both players have possible win in entire shuffled deck).
$22$ : actual ties.
$35:1$ approx candidate tie to actual tie ratio.
$6537$ : approx average hands per C win.
$6336$ : approx average hands per D win.
$3217$ : approx average hands for any win (or tie).
$45,454,545$ : approx average hands for a tie.

I am hoping someone else can do some analysis too to help confirm these numbers. Perhaps some mathematical calculations to help show that player D has a slight advantage. Also if someone would like some other stats tracked in the simulation program just let me know in the comment section and I can try to put it in and then post those results.

Here are the patterns we need to check for a possible C win. Note each length $3$ straight can appear in any order so for example, $234678TJQ$ and $678234TJQ$ are equally good winners for player C. Those are just $2$ of the $6$ possible permutations of each of these $10$ main patterns. So there are $ 60$ actual patterns including permutations. The comma indicates any number of cards (including $0$ cards) may appear as long as the pattern continues. For example, in pattern $1$, if the drawn cards are $K234J7ATJQ2495678$, that is a winner for player C cuz it follows (a permutation of) a winning pattern.

$~~1)~234,678,TJQ$
$~~2)~234,678,JQK$
$~~3)~234,678,QKA$
$~~4)~234,789,JQK$
$~~5)~234,789,QKA$
$~~6)~234,89T,QKA$
$~~7)~345,789,JQK$
$~~8)~345,789,QKA$
$~~9)~345,89T,QKA$
$10)~456,89T,QKA$

The winning patterns for D are (no permutations are allowed):

$~~1)~234567$
$~~2)~345678$
$~~3)~456789$
$~~4)~56789T$
$~~5)~6789TJ$
$~~6)~789TJQ$
$~~7)~89TJQK$
$~~8)~9TJQKA$
$~~9)~223344$
$10)~334455$
$11)~445566$
$12)~556677$
$13)~667788$
$14)~778899$
$15)~8899TT$
$16)~99TTJJ$
$17)~TTJJQQ$
$18)~JJQQKK$
$19)~QQKKAA$

Note that for player D, NO permutations of these $19$ patterns are allowed. They must appear EXACTLY as shown here. For example, $QQJJKK$ is NOT a win for player D. This is a clarification not a rule change.

It is somewhat amazing to me that wins are rare for both C and D (based on the average number of hands between wins), but they are almost equally as rare, making it almost $50/50~$ like a fair coin toss.

In case anyone is interested, I had the program display the cards for all $22$ ties. It displays the entire deck in the shuffled order for that hand so you can just trace where the tie occurred. For example, in the first tie, the relevant cards are $,345,89T,9TJQKA$. Here is a cropped partial screenshot for the simulation output for the ties: (T= ten).

enter image description here

I will now attempt to solve this mathematically but in a very simple way.

Looking at player's D's ways to win, there are only $2$ patterns. Pattern $1$ which is a $6$ card straight has probability $32/52 * 4/51 * 4/50 * 4/49 * 4/48 * 4/47$ but this is the probability of getting the $6$ card straight on the first $6$ cards drawn so we multiply that by $47$, assuming the straight can appear equally likely anywhere in the deck. So far that is about $1 / 9518$.

Next we have player D's 2nd pattern such as ($223344,334455, ... ,QQKKAA$) so that is $44/52 * 3/51 * 4/50 * 3/49 * 4/48 * 3/47$ but again we have to multiply that by $47$ since that $6$ card pattern can appear anywhere in the deck so we get $1/16407$. Adding the 2 probabilities we get $1/6024$ which is fairly close to the probability reported by the simulation program which was $1/6336$. The slight difference could be a combination of interaction with C's wins, ties, and the patterns not being uniformly distributed in all $47$ positions, but considering the simplicity of the calculations, it is quite a good approximation, only roughly $5$% off. For example, imagine we get $234567$ very late in the deck. It is quite possible that $234$, $345$, or $456$ can give C the win instead, or $567$ can give C and D a tie. Thus we would expect D's win chances to be lower than $1/6024$ which means the denominator has to be larger, more like $1/6336$. Also we must consider cases where multiple $6$ card straights appear. For example, it maybe possible that $234567$ appears early in the deck but something like $6789TJ$ appears much later (towards the end of the deck). Using my simple math, I would overcount these. I think worst case there could be $8$ straights of length $6$ in the same deck but that would be an astronomically rare event. Perhaps something like $234567,~234567,~234567,~234567,~89TJQK,~89TJQK,~89TJQK,~9TJQKA$. In my simulation program, I could count up how many times a straight of length $6$ appears multiple times in the same shuffled deck and add that to the table of results.

So I have done some of the work for you. I just need someone to somehow compute the interactions and account for those in the final probability. I will attempt to calculate C's win probability, also using simple math if possible.

Now let's look at C's win pattern. Let's take $234,678,TJQ$ as an example. Any one of those $3$ card patterns can appear first. Let's suppose the $234$ appeared first. The first part of this pattern MUST appear by card draw $46$ to allow ample time for the other part of the pattern to appear. To get $234$ on the first $3$ card draw we have probability $4/52 * 4/51 * 4/50$ = $1/2072$. From here it gets more complicated. Placing the three $3$ card straights might be one of those stars and bars type problems. Just find the probability of getting the $234,678,TJQ$ in order (without completing a $6$ card straight) and then multiply by $6$ to account for the possible permutations of them. Then multiply by $10$ to account for the $9$ other similar win patterns for C. This should be a rough approximation. Treat the $234$ as one entity and just place it anywhere in the $52$ card deck and do the same for the $678$ and $TJQ$. That is stars and bars. I think one way to solve this is to use stars and bars with a gap space of at least $2$ (such as $2,3,4,i,j,6,7,8$ so we are guaranteed not to have a $6$ card straight, then handle the cases where the gap space is $1$ separately so that we can make sure we only place cards there that will not complete the $6$ card straight. Also if anyone needs a certain count of some pattern that will help them to use math to solve this just let me know and I can try to create a bucket for it in my sim prog. I would love to get an exact answer to this problem but based on the lack and answers here (even with a $150$ bounty), I am assuming it is not easy.

$\endgroup$
  • $\begingroup$ I don't quite understand what you mean by equi-probable cards. You mean having a deck where the drawn cards are replaced? As far as treating each pattern (rule) separately, I see your point. For example, for D, $334455$ and $445566$ are related in that they both share $4455$. So imagine if $33445566$ appears in the shuffled deck. That is a win based on $334455$ but not on the $445566$, which, if cards were drawn $1$ at a time, we would never get to. Because I shuffle the deck each time, I can "see" all the cards and will see patterns like $33445566$. Good point. $\endgroup$ – David Aug 8 '16 at 15:59
  • $\begingroup$ @igael, okay thanks and yes I agree it is interesting in that there is no way to "cheat" to get the correct answer. A computer can give a good approximation. Also, as you get more reputation points you get more privileges. Good luck I hope you can solve it. A good solution will show for certain who has the advantage and will explain why. I simulated 1 billion hands but that doesn't prove D has an advantage for certain. What if I did 1 trillion hands might it reverse to C favored? I doubt it but it is possible, so technically I did not prove D has the advantage for certain. $\endgroup$ – David Aug 8 '16 at 16:18
  • $\begingroup$ Another interesting example would be something like $K234J67826789TJQ$. Here we have the first good $3$ card straight at cards $234$, the 2nd at $678$, but then we get the $6$ card straight before we get the 3rd gapped $3$ card straight. So the winning card sequence is $6789TJ$ for player D. Player C needed TJQ for the 3rd gapped $3$ card straight but player D already won $1$ card previous to that. $\endgroup$ – David Aug 9 '16 at 2:36
  • $\begingroup$ An example that illustrates a C win more clearly would be $234234234234678TJQ$ Here only the first $234$ is relevant to the win cuz the other ones are not gapped. $678$ IS gapped and so is $TJQ$ so when we get the Q card it is a win for player C. My sim prog will simply search that string for the first occurrence of $234$ (which ends at card position $3$), then it will immediately search for the next good $3$ card straight which is $678$ and then to do the same for $TJQ$ and then it will report a win for C. Very simple algorithm only searching for $3$ card straights that are good for a win. $\endgroup$ – David Aug 9 '16 at 14:59
  • $\begingroup$ The difference between your estimate and observed number of D wins can not be explained by C wins. These cases would appear as candidate ties in your simulation, and these are much rarer than the 5% difference. The difference (which unfortunately is big compared to the difference of chances of C and D) comes nearly completely from the simplifications in the estimate. $\endgroup$ – Christian Sievers Aug 9 '16 at 19:56
2
+300
$\begingroup$

I also simulate a version, using C++ mt19937 generator and Fisher–Yates shuffle (perhaps that is why this is slow). Result:

nowin: 19993847, cwin: 2993, dwin: 3160, tie: 0

My code:

#include <iostream>
#include <random>
std::mt19937 mt(123456789); // mersenne twister generator using a seed

enum card {c2, c3, c4, c5, c6, c7, c8, c9, cT, cJ, cQ, cK, cA};

enum type {straight, alternate};

card deck [52] {
    c2, c3, c4, c5, c6, c7, c8, c9, cT, cJ, cQ, cK, cA,
    c2, c3, c4, c5, c6, c7, c8, c9, cT, cJ, cQ, cK, cA,
    c2, c3, c4, c5, c6, c7, c8, c9, cT, cJ, cQ, cK, cA,
    c2, c3, c4, c5, c6, c7, c8, c9, cT, cJ, cQ, cK, cA,
};

void shuffle() {
    card temp; int pos;
    for (int i = 52; i > 1;) {
        pos = mt() % i; // generate random int in [0, i)
        i--;
        temp = deck[i];
        deck[i] = deck[pos];
        deck[pos] = temp;
    }
}

short prevtrans[256][13]; /* prevtrans[prev][card] = newprev.
prev: (total 8 bit)
    first bit: 0 is straight, 1 is alternate - type.
    4 next bit: from 0 to 12, indicate *FIRST* card - p1card.
    3 last bit: from 0 to 5, indicate length minus 1 - len1. (if length = 6 then D win instantly)
    There are a lot of redundancies.
*/
bool cwinp[2048]; /* cwinp[cwinpart] is true if cwinpart gives an instant win for C.
    cwinpart consists of 11 bits <QKA, JQK, ..., 456, 345, 234>.
    There are a lot of redundancies. For example, 567 and 9TJ are always 0.
*/
short cwinbuild[256]; /* The value to be ORed to cwin given prev to build a better cwin. */

void init() { // init those three tables.
    for (int prev = 0; prev < 256; prev++) {
        int type = prev >> 7, p1card = (prev >> 3) & 15, len1 = prev & 7; // bit extract
        int pcard = p1card + (type == alternate ? len1 >> 1 : len1);
        for (int ncard = 0; ncard < 13; ncard++) {
            if (pcard >= 13 || len1 >= 6) continue; // as I said, there are a lot of redundancies
            if (pcard == ncard) {
                if (type == alternate && (len1 & 1) == 0)
                    prevtrans[prev][ncard] = (prev & 0b11111000) | (len1 + 1); // build next alternate
                else // either bad alternate or straight
                    prevtrans[prev][ncard] = (alternate << 7) | (ncard << 3) | 1; // reset to alternate, length = 2 -> len1 = 1
            } else if (pcard + 1 == ncard) { // straight at least 2
                if (type == alternate) {
                    if ((len1 & 1) == 1) // good alternate
                        prevtrans[prev][ncard] = (prev & 0b11111000) | (len1 + 1); // build next alternate
                    else if (len1 != 0) // (likely) bad alternate, form straight 3 (len1 = 2)
                        prevtrans[prev][ncard] = (straight << 7) | ((pcard - 1) << 3) | 2;
                    else // (unlikely) short alternate, form straight 2 (len1 = 1)
                        prevtrans[prev][ncard] = (straight << 7) | (pcard << 3) | 1;
                }
                else /*if (type == straight)*/ {
                    prevtrans[prev][ncard] = (prev & 0b11111000) | (len1 + 1); // build next straight
                }
            } else { // ncard do not form a pattern with pcard, straight 1 (len1 == 0)
                prevtrans[prev][ncard] = /*(straight << 7) | */(ncard << 3)/* | 0*/;
            }
            //std::cout << "prevtrans[" << prbin(prev, 8) << "][" << ncard << "] = " << prbin(prevtrans[prev][ncard], 8) << "\n";
        }
        cwinbuild[prev] = (type == straight && len1 >= 2 ? // so length >= 3
        1 << (p1card + len1 - 2) : 0);
    }
    for (short cwinpart = 0; cwinpart < 2048; cwinpart++) {
        const short cwindone[10] = {
            0b00100010001, // 234, 678, TJQ
            0b01000010001, // 234, 678, JQK
            0b10000010001, // 234, 678, QKA
            0b01000100001, // 234, 789, JQK
            0b10000100001, // 234, 789, QKA
            0b10001000001, // 234, 89T, QKA
            0b01000100010, // 345, 789, JQK
            0b10000100010, // 345, 789, QKA
            0b10001000010, // 345, 89T, QKA
            0b10001000100, // 456, 89T, QKA
        };
        cwinp[cwinpart] = false;
        for (int i = 0; i < 10; i++)
            if ( // cwinpart is a superset of cwindone[i]
                (cwindone[i] &~ cwinpart) == 0) {
                    cwinp[cwinpart] = true;
                    break;
                }
    }
}

int main() {
    init();
    short prev, cwinpart;
    int cwin = 0, dwin = 0, tie = 0, nowin = 0, i;
    for (int cnt = 0; cnt < 20000000; cnt++) { // 100 millions. Consider switch to long long if necessary
        shuffle();
        prev = 0b01100000; // straight A length=1. Cannot benefit for C or D.
        cwinpart = 0b00000000000; // not got anything for C.
        for (i = 0; i < 52; i++) {
            prev = prevtrans[prev][deck[i]];
            cwinpart |= cwinbuild[prev];    
            if ((prev & 7) == 5) {// len1 == 5 <=> length = 6. D win instantly.
                if (cwinp[cwinpart])
                    tie++;
                else
                    dwin++;
                break;
            } else if (cwinp[cwinpart]) {
                cwin++;
                break;
            }
        }
        if (i == 52)
            nowin++;
    }
    std::cout << "nowin: " << nowin << ", cwin: " << cwin << ", dwin: " << dwin << ", tie: " << tie;
    std::string s;
    std::cin >> s;
}

I have an idea to completely solve the problem with computer-assisted (perhaps in a few days), but the memory take is several TBs. The basic idea is, given a deck (not count permutation, so there is 5^13 decks, or "submultiset" of the original deck), previous some cards (count permutation) (prev in my code), and partial winning data for C (cwinpart in my code), you can calculate the probability by the probability of other decks with less card, so you can use Dynamic Programming can be useful here.

Edit: To solve the problem exactly you can use the following code:

void calcp(long long board, // board: 3 bits for each number, AKQJT98765432 -> 39 bits
    short prev, short cwinpart, double& cwin, double& dwin, double& tie
) {
    // < Check for base cases: board == 0LL >
    cwin = dwin = tie = 0.;
    int ncard = 0, sumcard = 0;
    short nprev;
    double cwin1, dwin1, tie1;
    for (int i = 0; i < 13; i++) {
        ncard = (board >> (3 * i)) & 07;
        if (ncard != 0) {
            sumcard += ncard;
            nprev = prevtrans[prev][i];
            calcp(board - (1 << (3 * i)), nprev, cwinpart | cwinbuild[nprev],
                    cwin1, dwin1, tie1);
            cwin += cwin1 * ncard;
            dwin += dwin1 * ncard;
            tie += tie1 * ncard;
        }
    }
    cwin /= sumcard;
    dwin /= sumcard;
    tie /= sumcard;
}

int main() {
    init();
    double cwin = 0., dwin = 0., tie = 0.; // probability
    calcp(04444444444444LL, 0b01100000, 0b00000000000, cwin, dwin, tie);
    std::cout << cwin << " " << dwin << " " << tie << "\n";
}

There are some notes:

  1. The code use tables, enums, functions from the previous my code part.
  2. You should add memoization to the function (wisely, because there are about $2\times 10^{13}$ different inputs) to decrease the time. The code is easy to understand providing you know C++11.

Edit: Result from your test: count: 3000000 nowin: 2999046, cwin: 470, dwin: 484, tie: 0

I have made a fault in my code (see revision). Now our result accept.

$\endgroup$
  • $\begingroup$ I have my sample data of $3$ million random shuffles here. Try running your program on my sample data and we can compare results and figure out where the discrepancy (if any) is occuring. drive.google.com/file/d/0BweDAVsuCEM1amhsNmFITnEwd2s/…. Format is one $52$ byte shuffle per line with $2$ bytes for end of line so $54$ bytes per line total. $3$ million records/shuffles/lines. File is zipped so you will have to unzip (extract) the raw data which should be $162,000,000$ bytes $\endgroup$ – David Aug 14 '16 at 16:17
  • 1
    $\begingroup$ @David 1. I edited my answer. 2. Use a generator and a engine is better. That's why I seeded 123456789 and generator mt19937. You should read my code and learn C++11. $\endgroup$ – user202729 Aug 15 '16 at 13:26
  • 1
    $\begingroup$ Remember that this is not a programming site. But you don't want to learn C++, and still want to check in that way, then download mediafire.com/download/yu2o8951854by7n/fcardgame.exe , put your file to C:\input.txt, then run the program. You should try with small input first to see how the program output. $\endgroup$ – user202729 Aug 16 '16 at 7:59
  • 1
    $\begingroup$ @David I think you are the only person who need that exe. New version: mediafire.com/download/wluy9f33ud3vlpk/fscanf_cardgame.exe . If you make huge input, then I won't run it. $\endgroup$ – user202729 Aug 17 '16 at 14:06
  • 1
    $\begingroup$ @David Do you know the cube20 problem and the 4-coloring theorem? They are all solved by supercomputer. And this problem is also quite hard, similar to them. Given several TB of memory I can solve it. $\endgroup$ – user202729 Aug 17 '16 at 14:10
0
$\begingroup$

This is a 2nd answer for those of you that are considering using computer simulation or a combination of that and math. If you use a computer language that has good string functions like I did, a simple algorithm is to put the patterns "$234$", "$345$", "$456$"... "$QKA$" in an array. I indexed them from $2$ to $12$ to keep is simple cuz the index matches the lowest ranked card in the $3$ card straight. Then just run $3$ nested loops, call them i, j and k. The outermost loop index i goes from $2$ to $4$ since one of those patterns MUST appear for a C win. That is, either $234$, $345$, or $456$ MUST appear for C to win. The middle loop (j) iterates from (i+$4$) to $8$. Notice this middle loop never goes higher than $8$ cuz we need room for the gap and then the final $3$ card straight. The innermost loop (k) iterates from (j+$4$) to $12$. If a $3$ card straight is found from each of the $3$ groups (thus indicating they are all gapped by at least $1$ rank), then that is a win for player C unless a $6$ card straight is also found in the deck, in which case I just compare final card positions of both to determine who really won the hand. Most of the time this is not necessary cuz there is only $1$ candidate winner which is the actual winner.

D wins are also put in an array and the entire shuffled deck is scanned for them. Examples would be DW[$1$] = "$234567$" DW[$2$] = "$345678$".... Of course since multiple D winning patterns may appear in the same shuffled deck, I ultimately choose the one with the lowest finishing card position. For example, $345678A234567$ is a "double" candidate win for D but the winning sequence is $345678$ and NOT $234567$ although my simulation is programmed to search for $234567$ first.

So to be clear, using strings is a very good way to simulate this card game cuz many languages have good fast string searching functions built in and it makes the coding much simpler in my opinion as an "old school" programmer.

Just to be clear, my sim prog shuffles and scans the entire deck but when a candidate win is found, if it is a solo candidate win (such as player C only), then the win is awarded and the card position is recorded for averaging later. An interesting scenario happens when there are $2$ candidate wins in the same $52$ card deck. A very simple example would be $234678TJQ234567...$ Here, my program will detect possible (candidate) wins for both C and D but will see that the C win happened first and award the win only to C. Reason I scan the entire deck is cuz it is simpler and it also allows me to track additional interesting info like dual candidate winners in the same hand which is rare, and of those few, some ties appear which are even more rare.

Someone asked about my shuffle routine so I will describe it here. I start with the deck initialized to rank order. The array (call it A here) is such that A[$1$] = '$2$', A[$2$] = '$2$', A[$3$] = '$2$', A[$4$] = '$2$', A[$5$] = $3$... A[$52$] = 'A'.

The goal is to choose a random card from the deck and place it at the "tail end" of the deck. This is a variation of the Fisher-Yates shuffle. So 1st iteration of shuffle will grab a random number from $1$ to $52$ (inclusive). That number will be the position of the card in array A we want to place at the "end" of the deck. So for example, if the random number is $5$, we already know that A[$5$] = '$3$' (a rank 3 card is there) so we do the swap. Next we only concentrate on the first $51$ cards in the deck so we grab a random number from $1$ to $51$ and do another swap, but this time with the 2nd to last card in the deck which is our new "tail end" of the deck. This process continues until the deck size we are concentrating on is only size $1$. In that case we can just exit the shuffle cuz now all $52$ cards will have had an equal opportunity to be in any of the $52$ card positions. The Rand() function I call is a library function so I have little control over it but I have been using it in many card and dice simulation programs and it has agreed with others results so it seems very reliable, accurate, and fast. I am not sure how it works internally but it seems to work very well, showing no bias.

$\endgroup$
  • 1
    $\begingroup$ Your description doesn't explain that one can't stop after finding the first triple $(i,j,k)$. Test case: do you recognize 234678JQK234567TJQ as win for C? You might not if you stopped after finding TJQ as third run of 3 straight cards and ignored the earlier run JQK of higher ranked cards. (Such a thing could also happen with the first or second run.) $\endgroup$ – Christian Sievers Aug 10 '16 at 13:55
  • $\begingroup$ @Christian Sievers - you are exactly right! I typed in your example deal and it incorrectly reported a win for D. However, since this case is extremely rare, it wont upset the numbers significantly. That is cuz this is a candidate tie condition and those are very rare. Even if I corrected the code, the percentage would not change significantly but you are exactly right this is a flaw in my nested loop logic. It is telling me a candidate tie but with C win position at card $18$ and D win card position at $15$ so it gives D the win but C actually should have won at card position $9$. $\endgroup$ – David Aug 10 '16 at 14:20
  • 1
    $\begingroup$ I agree that it will not change the winning percentages much. I guess it will have a bigger influence to the average number of cards drawn before C wins (here not only candidate ties are affected). $\endgroup$ – Christian Sievers Aug 10 '16 at 14:33
  • 1
    $\begingroup$ I guess you jumped out of the inner loop? Can't you just take the highest used index (as before), compare with a possible earlier result, and continue the loop? Then there is no difference if C doesn't have a "candidate win". $\endgroup$ – Christian Sievers Aug 10 '16 at 14:45
  • 1
    $\begingroup$ BTW, there is potentially a similar problem with D's winning patterns. Given 3456789JQK234567, one better not stops after finding 234567 as D's winning pattern. $\endgroup$ – Christian Sievers Aug 10 '16 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.