2
\$\begingroup\$

Related to Poker Hand Evaluator. This it not the same. This is take best from all combinations of 7. The other is all combinations of 5.

Poker is 52 cards - 4 suits and 13 ranks:

  • Texas holdem
  • Hand is exactly 5 cards
  • Order of hands
    • Straight-flush
      all same suite and in order
      ace high is royal straight flush
    • Quad four of same rank
    • Boat three of one rank and two of another rank
    • Flush all the same suit
    • Straight e.g. 56789
      ace 0 counts as both low and high 01234 and 9,10,11,12,0
    • Two pair
    • One pair
    • High card

There are 23,294,460 distinct 7 card combinations in a deck of 52. I am not interested in a random sampling (Monte Carlo). Will add the as on option later but need the option to run all and have the correct answer from wiki.

This program makes the best 5 cards hand from every combination of 7 and tallies. That is how a poker game works. You have 2 hole cards and then 5 cards on the board. You make the best 5 cards card had from you hole cards plus the board.

Combination of 7 is harder in there are a lot more combination. Cannot assume if you have a straight and a flush you have a straight-flush as they may not be the same 5 cards. This separates a royal straight flush from a straight flush but they can be combined into just straight flush if that is faster.

Not interested in parallel processing. Have a pattern for doing that. For this question just optimize the raw code.

This code gives the correct answers to poker hand probability. It runs in about 200 seconds.

How to optimize this code to run faster? Or make it cleaner and not run any slower.

    public void Deal7c()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int counter = 0;
        int counterFlush = 0;
        int counterStraight = 0;
        int counterStraightFlush = 0;
        int counterStraightAndFlush = 0;
        int counterRoyalFlush = 0;
        int counterQuad = 0;
        int counterBoat = 0;
        int counterTrips = 0;
        int counterPairTwo = 0;
        int counterPairOne = 0;
        int counterHigh = 0;
        Card[] CardArray = new Card[7];   // hand plus board 
        bool haveStraight;
        bool haveQuad;
        bool haveBoat;
        bool haveFlush;
        int flushSuite;
        bool haveStraightFlush;
        bool haveRoyalFlush;
        int flushCount;
        int straightCount;
        int straightCount2;
        bool haveAce;
        int? lastRank;
        int firstCard;
        //byte* rankArray = stackalloc byte[13];
        //byte* rankCount = stackalloc byte[5];
        int[] rankArray = new int[13];
        int[] rankCount = new int[5];
        Debug.WriteLine("");
        for (int i = 51; i >= 6; i--)
        {
            Debug.WriteLine("Deal7a i = " + i + "  milliseconds " + sw.ElapsedMilliseconds.ToString("N0"));
            CardArray[0] = new Card(i % 13, i / 13);
            for (int j = i - 1; j >= 5; j--)
            {
                CardArray[1] = new Card(j % 13, j / 13);
                for (int k = j - 1; k >= 4; k--)
                {
                    CardArray[2] = new Card(k % 13, k / 13);
                    for (int l = k - 1; l >= 3; l--)
                    {
                        CardArray[3] = new Card(l % 13, l / 13);
                        for (int m = l - 1; m >= 2; m--)
                        {
                            CardArray[4] = new Card(m % 13, m / 13);
                            for (int n = m - 1; n >= 1; n--)
                            {
                                CardArray[5] = new Card(n % 13, n / 13);
                                for (int p = n - 1; p >= 0; p--)
                                {
                                    CardArray[6] = new Card(p % 13, p / 13);

                                    counter++;
                                    //if (rand.Next(4) != 0)
                                    //     continue;
                                    haveStraight = false;
                                    haveFlush = false;
                                    haveStraightFlush = false;
                                    haveRoyalFlush = false;
                                    haveBoat = false;
                                    haveQuad = false;

                                    for (int q = 0; q <= 12; q++)
                                        rankArray[q] = 0;

                                    for (int c = 0; c < 7; c++)
                                        rankArray[CardArray[c].Rank]++;

                                    // this will build up the rank count 
                                    rankCount[0] = 0;  // none   - not used but it needs to be here to make this work
                                    rankCount[1] = 0;  // single - not used but it needs to be here to make this work
                                    rankCount[2] = 0;  // pair
                                    rankCount[3] = 0;  // trips
                                    rankCount[4] = 0;  // quad
                                    for (int c = 0; c <= 12; c++)
                                        rankCount[rankArray[c]]++;

                                    if (rankCount[4] == 1)
                                        haveQuad = true;
                                    else if (rankCount[3] == 2)  // with 7 could have two trips
                                        haveBoat = true;
                                    else if (rankCount[3] == 1 && rankCount[2] > 0)
                                        haveBoat = true;

                                    if (!haveQuad && !haveBoat && rankCount[2] != 3)  // cannot make a straight or flush with a quad or boat
                                    {
                                        // flush
                                        flushSuite = -1;
                                        for (int f = 0; f <= 3; f++)
                                        {   // can only have one flush in 7 cards 
                                            flushCount = 0;
                                            for (int c = 0; c < 7; c++)
                                            {
                                                if (CardArray[c].Suit == f)
                                                    flushCount++;
                                            }
                                            if (flushCount >= 5)
                                            {
                                                haveFlush = true;
                                                flushSuite = f;
                                                break;
                                            }
                                        }

                                        //straight
                                        //first ace high
                                        haveStraight = rankArray[0] > 0 &&
                                                       rankArray[12] > 0 &&
                                                       rankArray[11] > 0 &&
                                                       rankArray[10] > 0 &&
                                                       rankArray[9] > 0;
                                        if (!haveStraight)
                                        {
                                            for (int s = 12; s >= 4; s--)
                                            {
                                                haveStraight = rankArray[s] > 0 &&
                                                               rankArray[s - 1] > 0 &&
                                                               rankArray[s - 2] > 0 &&
                                                               rankArray[s - 3] > 0 &&
                                                               rankArray[s - 4] > 0;
                                                if (haveStraight)
                                                    break;
                                            }
                                        }

                                        if (haveStraight && haveFlush)
                                        {   // now for the difficult task of straightFlush 
                                            // this is kind of expensive but at least it does hot happen a lot
                                            // note in 7 you could have gap and still have a straight xyxxxxx
                                            counterStraightAndFlush++;
                                            straightCount = 0;
                                            haveAce = false;
                                            for (int c = 0; c < 7; c++)
                                            {
                                                if (CardArray[c].Suit == flushSuite)
                                                {
                                                    straightCount++;
                                                    if (CardArray[c].Rank == 0)
                                                        haveAce = true;
                                                }
                                            }
                                            if (straightCount >= 5)
                                            {   
                                                straightCount2 = 0;
                                                lastRank = null;
                                                firstCard = 0;
                                                foreach (Card c in CardArray.Where(x => x.Suit == flushSuite).OrderByDescending(x => x.Rank))
                                                {
                                                    //Debug.WriteLine(c.Rank + " " + c.Suit);
                                                    if (lastRank == null)
                                                    {
                                                        firstCard = c.Rank;
                                                    }
                                                    else
                                                    {
                                                        if (c.Rank == lastRank - 1)
                                                        {
                                                            straightCount2++;
                                                            if (haveAce && straightCount2 == 3 && firstCard == 12)
                                                            {
                                                                haveRoyalFlush = true;
                                                                haveFlush = false;
                                                                haveStraight = false;
                                                                break;
                                                            }
                                                            else if (straightCount2 == 4)  //the first card is not in the straightCount
                                                            {
                                                                haveStraightFlush = true;
                                                                haveFlush = false;
                                                                haveStraight = false;
                                                                break;
                                                            }
                                                        }
                                                        else
                                                        {
                                                            if (straightCount < 6)  
                                                                break;
                                                            straightCount2 = 0; // this is the 
                                                            firstCard = c.Rank;
                                                        }
                                                    }
                                                    lastRank = c.Rank;
                                                }
                                            }
                                        }
                                    }

                                    // hands in order
                                    if (haveRoyalFlush)
                                        counterRoyalFlush++;
                                    else if (haveStraightFlush)
                                        counterStraightFlush++;
                                    else if (haveQuad)
                                        counterQuad++;
                                    else if (haveBoat)  // with 7 could have two trips
                                        counterBoat++;
                                    else if (haveFlush)
                                        counterFlush++;
                                    else if (haveStraight)
                                        counterStraight++;
                                    else if (rankCount[3] == 1)
                                        counterTrips++;
                                    else if (rankCount[2] >= 2)  // with 7 could have 3 trips
                                        counterPairTwo++;
                                    else if (rankCount[2] == 1)
                                        counterPairOne++;
                                    else
                                        counterHigh++;
                                }
                            }
                        }
                    }
                }
            }
        }
        sw.Stop();
        Debug.WriteLine("");
        Debug.WriteLine("Deal7a");
        Debug.WriteLine("stopwatch millisec    " + sw.ElapsedMilliseconds.ToString("N0"));;
        Debug.WriteLine("hand count            " + counter.ToString("N0"));
        int sum = counterHigh + counterPairOne + counterPairTwo + counterTrips + counterStraight
                + counterFlush + counterBoat + counterQuad + counterStraightFlush + counterRoyalFlush;
        Debug.WriteLine("royalFlush counter    " + counterRoyalFlush.ToString("N0") + "       " + (100m * counterRoyalFlush / sum).ToString("N4"));
        Debug.WriteLine("straightFlush counter " + counterStraightFlush.ToString("N0") + "      " + (100m * counterStraightFlush / sum).ToString("N4"));
        Debug.WriteLine("quad count            " + counterQuad.ToString("N0") + "     " + (100m * counterQuad / sum).ToString("N4"));
        Debug.WriteLine("boat count            " + counterBoat.ToString("N0") + "   " + (100m * counterBoat / sum).ToString("N3"));
        Debug.WriteLine("flush counter         " + counterFlush.ToString("N0") + "   " + (100m * counterFlush / sum).ToString("N3"));
        Debug.WriteLine("straight counter      " + counterStraight.ToString("N0") + "   " + (100m * counterStraight / sum).ToString("N3"));
        Debug.WriteLine("trips count           " + counterTrips.ToString("N0") + "   " + (100m * counterTrips / sum).ToString("N3"));
        Debug.WriteLine("two pair count        " + counterPairTwo.ToString("N0") + "  " + (100m * counterPairTwo / sum).ToString("N2"));
        Debug.WriteLine("one pair counter      " + counterPairOne.ToString("N0") + "  " + (100m * counterPairOne / sum).ToString("N2"));
        Debug.WriteLine("high card counter     " + counterHigh.ToString("N0") + "  " + (100m * counterHigh / sum).ToString("N2"));
        Debug.WriteLine("sum                   " + sum.ToString("N0"));
        Debug.WriteLine("");
    }

    struct Card
    {
        public Card(int Rank, int Suit)
        {
            rank = Rank;
            suit = Suit;
        }
        Int32 rank;
        Int32 suit;
        public int Rank { get { return rank; } }
        public int Suit { get { return suit; } }
    }
\$\endgroup\$
  • \$\begingroup\$ @StewieGriffin It is a zero based array so 12 is king. \$\endgroup\$ – paparazzo Jul 25 '16 at 13:23
  • \$\begingroup\$ What about a regular flush (in the description). I see you have it in the code... \$\endgroup\$ – Stewie Griffin Jul 25 '16 at 13:26
  • 1
    \$\begingroup\$ It's missing isn't it? \$\endgroup\$ – Stewie Griffin Jul 25 '16 at 13:28
  • 1
    \$\begingroup\$ this is texas holdem, just one (popular) poker variant. Also the word is suit not suite \$\endgroup\$ – pm100 Jul 25 '16 at 16:36
  • \$\begingroup\$ @pm100 This isn't just Texas Holdem. There are many games that force you to pick the best 5 of 7 cards. I'd say the next most popular is 7 card stud, but more obscure ones like pineapple and anaconda come to mind. \$\endgroup\$ – corsiKa Jul 25 '16 at 21:27
4
\$\begingroup\$

When checking for a flush, instead of looping through the cards 4 times, you could have an array of length 4 where each position represents a suit. Then loop over the 7 cards one time and use a switch statement to increment the element that corresponds to the suit. Then loop over the array and check if any of the elements is 5 or more.

If you want to get really down in the bit twiddling, consider changing your && conditionals to & non-short circuiting conditions where it makes sense. Your haveStraight section where you are doing 4 conditional ANDs on simple conditions seems like a strong candidate, for example. The reason is that the compiler will likely be able optimize the code much better if you get rid of the conditional branching. Usually this won't make a big enough difference to matter but since you are doing this many millions of times, it could be substantial.

Another bit-twiddling approach that might be faster is to take the rank array and write the results into a short where each bit represents whether the corresponding element was greater than 0 (set the 13th and 0th bit for the aces.) Then you can bitwise AND the value with 31 (binary 11111) and see if it equals 31. Right shift 1 and compare again. Do this 9 times or until you find a match.

Lastly, you could take advantage of the fact that in your inner most loop, only one card is changing. You would have to restructure your code substantially but you could avoid all the recalculations of the other 6 cards each time by adjusting for that one card. You can keep doing this recursively up the tree for the loops but the return on that will be progressive less for each level you move up.

Here's an example of using a single pass loop to evaluate the straight:

int contig = rankArray[0] > 0 ? 1 : 0;

for (int r = 12; r >= 0; r--) {
  contig = rankArray[r] > 0 ? contig + 1 : 0;

  if (contig > 4) {
    haveStraight = true;
    break;
  } else if (contig + r < 4) {
    /* not sure this if this helps or hurts */
    break;
  }
}

Does that align with what you did?

\$\endgroup\$
  • \$\begingroup\$ On the flush would not even need a switch - just++ the array position. And I would think short circuiting is good for speed. Will check out your other suggestions also. \$\endgroup\$ – paparazzo Jul 25 '16 at 16:52
  • \$\begingroup\$ @Paparazzi Sorry, I could be missing something but the point of the switch was to select which array position to increment. Switches tend to be very fast versus if-else chain but that all depends on the compiler/VM optimizations. \$\endgroup\$ – JimmyJames Jul 25 '16 at 16:55
  • \$\begingroup\$ Else if? Array position. Same way I load up other arrays. \$\endgroup\$ – paparazzo Jul 25 '16 at 16:57
  • \$\begingroup\$ I see, you already associate a int value to each suit. Yeah, you can just use that. \$\endgroup\$ – JimmyJames Jul 25 '16 at 17:02
  • 2
    \$\begingroup\$ FYI the C# compiler will already realize && as & if it knows that (1) there is no possible semantic difference, and (2) high likelihood of smaller code and faster execution. It doesn't do a perfect job, but it does have some heuristics in this area. \$\endgroup\$ – Eric Lippert Jul 26 '16 at 17:28
3
\$\begingroup\$

I believe you can use formulas to calculate your answer, which will be much faster than brute force. However, it is a good idea to code a brute force solution first, as you have, so that you can test against it. The biggest improvement you can make readability-wise is on how you generate all of the card combinations. Right now there is so much nesting that most of your logic starts in the middle of the screen. There are some nice solutions out there for generating "n choose k" type collections. Here is one in C#:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

It is elegant, but I'm not sure how fast it is. You can use it like this:

foreach(var combination in Enumerable.Range(0, 52).Combinations(7))
{
    Card[] hand = combination.Select(x => new Card(x % 13, x / 13)).ToArray();
    // ...
\$\endgroup\$
  • \$\begingroup\$ This is almost guaranteed to be much slower. But only tests will tell. \$\endgroup\$ – 404 Jul 25 '16 at 15:35
  • \$\begingroup\$ @eurotrash perhaps but it's doubtful that it would make a big difference as the rest of the code is surely much more expensive. A simple recursive function to fill the arrays would clean this up in any event. I focused purely on performance in my answer. There's a lot of stuff here that should be broken out in separate methods. \$\endgroup\$ – JimmyJames Jul 25 '16 at 16:00
  • \$\begingroup\$ Cool syntax on the combinations but it will not work when I take this to the next level. A user can pick two cards and runs the boards so I need to check for either card and skip at every level. \$\endgroup\$ – paparazzo Jul 25 '16 at 17:13

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.