Open in app

Sign in

Write

Sign in

Cracking the Code: Algorithmic Approaches to Determine Best Grouping in Online Rummy

Anurag Garg
Gameskraft
Published in
8 min readApr 16, 2024

Written by Anurag Garg, Div Jain

In the previous post, we introduced the concept of Best Grouping and showed why it is an essential Skill in Online Rummy.

In this post, we delve deeper into the complexities of Optimal Card Grouping by examining 3 different algorithmic strategies for solving this problem:

1. Brute Force

2. Recursive

3. Dynamic Programming

We analyze the strengths and weaknesses of each approach, providing insights into the trade-offs in optimizing card grouping techniques.

The “Best Grouping” Problem:

Given a set of n cards (usually 13 or 14) and a declared joker card, return all best grouping(s) possible with the objective of (i) valid declaration (ii) and/or minimizing points.

Approach I: May the ‘Brute Force’ be with you

The naive solution to this problem is applying Brute Force. This would require considering all permutations of the cards by employing a backtracking algorithm. Such an algorithm:

  • recursively constructs permutations by selecting cards, one by one, and ensuring that no card is repeated within a permutation.
  • explores all possible choices at each step, backtracking when necessary, until all cards have been used.
  • For 3 cards represented as abc, this step would produce all permutations like (abc, acb, bac, bca, cab, cba).
  • Simply put, this step is equivalent to generating all possible permutations of a given string.

As a next step, within each such permutation, the algorithm further needs to look for all kinds of melds with different lengths (typically 3–5 for a sequence and 3–4 for a set) and group them in such a way that either minimizes the points or leads to valid declaration or both.

Fig. 1 shows how the Brute Force approach creates 13! (6,227,020,800) permutations of 13 cards

Pros:

  1. Simple to understand and implement.

Cons:

  1. The time complexity of the first step itself is O(n!).
  2. Memory intensive given the depth of the recursion tree for each permutation would be n.
  3. Not practical for use cases or applications that require responses in quick and real-time.

Given the above factors, this was just evaluated as one of the approaches but wasn’t given a try.

Approach II: Brute Force Reloaded — A Recursive Approach

The above approach builds even those permutations where no meld exists. Consider the hand below where no valid melds exist. It still generates all 13! = 6,227,020,800 permutations.

Based on the above observation, this solution tries to generate valid permutations or groupings of the melds as opposed to the cards themselves. It involves two steps: Meld Generation and Recursive Exploration with Backtracking.

Meld Generation

In this step, all possible valid melds (such as Pure Sequences, Sequences, and Sets) using the cards in the hand are identified first. Here’s how:

  • Iterate through each card and construct Sequences (both Pure and Impure) of varying lengths (typically 3–5) by finding cards with consecutive ranks but the same suit.
  • Similarly, Sets of different lengths (3–4) are formed by locating cards with the same rank but different suits.
  • In cases where a required card is unavailable for an Impure Sequence or a Set, any Joker cards present in the hand can be utilized.

This step lays the groundwork for subsequent permutation generation of melds.

Recursive Exploration with Backtracking

To generate groupings, this step also builds permutations recursively but of melds instead of cards as was in Approach I.

  • Initially, each meld is considered individually, deciding whether to include it in the current grouping or start a new grouping with it.
  • This branching decision tree continues for each meld, exploring all possible combinations.
  • A meld can be added to the current grouping only if the cards in the meld haven’t already been considered in the grouping.
  • Backtracking comes into play when a dead-end is reached (no more melds are left or 4 such melds (for 12–14 cards) have already been added to the grouping).
  • By exploring recursively and backtracking when necessary, the algorithm ensures that every valid grouping is considered, ultimately generating all possible groupings.

Whenever a dead-end is reached, the grouping is evaluated as a candidate for either valid declaration or for minimum points following the Rummy rules.

Performance:

For benchmarking, 1.5 Lakh hands were randomly selected. It took ~360ms per hand (on average) to compute valid groupings for those hands.

Pros:

  1. Relatively optimized and doesn’t generate permutations where no melds exist.
  2. It runs relatively faster than the Brute Force approach (Approach I) discussed earlier.

Cons:

  1. Generates the same groupings multiple times. For a grouping with 2 melds, it generates both [MeldA, MeldB] and [MeldB, MeldA] which are essentially the same.
  2. Still slower and memory intensive owing to no memorization.

Approach III: Using Dynamic Programming — The Savior

This approach differs from the above approach in the sense that after melds have been generated, it uses Dynamic Programming (DP) to build groupings as opposed to Backtracking.

  • The groupings are constructed following the Rummy rules. This means that melds are added to the groupings in order of significance of meld types (PS > IS > Set). If the recently added meld in the grouping is of type PS, then the next meld in the grouping can only be of type PS or IS. Set becomes an option too if there already exists 2 or more PS in the grouping. Similarly, for IS and Set, the next meld could be (an IS or a Set) and only Set respectively.
  • When adding a meld of a type similar to the previously added meld, only consider the subsequent melds. However, consider all melds if it is of a different meld type. e.g. if the 5th IS meld was previously added to a grouping, then either any IS melds starting from index 6 can be considered or all Set melds starting from index 1 can be considered. This ensures that no duplicate groupings are created with the same melds but in different order, as we had seen in Approach II.

Adhering to the guidelines above:

  • Initial groupings are constructed considering all PS melds.
  • In the second step, either the subsequent PS melds or all IS melds are added to the existing groupings, if possible.
  • Since at the 3rd level, the recently added meld could be of type PS or IS, all types of melds (PS, IS, Set) are considered here. This is true for the 4th level which is the final level as well (Considering 12–14 cards, there can be at max 4 melds).
  • Memoization: At each level, the groupings from the previous level are carried forward and are considered when creating the new groupings. This ensures a comprehensive exploration of potential groupings without the redundancy of reevaluating identical meld combinations.
  • Any grouping formed this way is a path from a root (Level 0) to a leaf node (Level 3) of the n-ary tree. For a hand with 12–14 cards and a minimum meld length of 3, the maximum height of this n-ary tree is 4.
  • As a final step, groupings are evaluated, one by one, for minimum points and valid declaration.
Fig. 2 — shows how card groupings are created in BFS manner as an n-ary tree efficiently using Dynamic Programming

Performance:

  1. The DP step is not needed at all if there are no PS melds.
  2. Since IS and Set melds are added on top of groupings that already have PS melds, the groupings that don’t have any PS meld won’t get generated. This, however, could not be achieved with the previous approaches.

Over the same 1.5 Lakh hands used in Approach II for benchmarking, this methodology took ~10ms per hand (on average) to compute all groupings. While this was a huge improvement over the previous approaches, it was still not enough to deploy this approach at the scale that our platforms or Data Science pipelines operate at.

Further optimizations:

To reduce the groupings further, the following rules were applied to limit the number of generated melds (Assumption: For sequence length between 3–5 and Set length between 3–4):

  1. An Impure Sequence would start with an actual card and not a joker.
  2. Any meld of length 3 but with 2 jokers in it will be generated as Impure Sequence and not Set.
  3. An Impure Sequence of length > 3 will only have 1 trailing joker.
  4. An Impure Sequence of length = 5 will always end with an actual card and not a joker.
  5. A Set will only have a maximum of 1 joker and be used only when building a meld of length 3.

Final Performance:

With the above optimizations, we were able to bring down the average time taken to ~1.5ms per hand to compute all groupings which was a huge win (Fig. 3).

Pros:

  1. No duplicate groupings and no re-evaluation of identical meld combinations.
  2. Extremely fast and highly efficient.

Cons:

  1. No such limitations except that the implementation of this approach requires an understanding of core data structures and programming paradigms.
Fig. 3 shows a performance comparison of different approaches discussed in this blog

As we conclude this journey through the nuances of Best Grouping of Cards, our focus shifts to another crucial skill: To Drop or not to Drop. In that upcoming blog, we will unveil the methodologies and various Data Science models developed for this skill, as well as the valuable insights that emerged from our research.

This post is part of a 9-part blog series delving into the art and science of skillful play and defining what Skill means in Online Rummy.

Algorithms
Dynamic Programming
Rummy Card Game
Skill Development
Recursion

--

--

Anurag Garg
Gameskraft

Written by Anurag Garg

10 Followers
Writer for

All things Tech, Engineering, Data Science, and Mountaineering

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams