Cracking the Code: Algorithmic Approaches to Determine Best Grouping in Online Rummy
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.
Pros:
- Simple to understand and implement.
Cons:
- The time complexity of the first step itself is O(n!).
- Memory intensive given the depth of the recursion tree for each permutation would be n.
- 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:
- Relatively optimized and doesn’t generate permutations where no melds exist.
- It runs relatively faster than the Brute Force approach (Approach I) discussed earlier.
Cons:
- 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.
- 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.
Performance:
- The DP step is not needed at all if there are no PS melds.
- 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):
- An Impure Sequence would start with an actual card and not a joker.
- Any meld of length 3 but with 2 jokers in it will be generated as Impure Sequence and not Set.
- An Impure Sequence of length > 3 will only have 1 trailing joker.
- An Impure Sequence of length = 5 will always end with an actual card and not a joker.
- 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:
- No duplicate groupings and no re-evaluation of identical meld combinations.
- Extremely fast and highly efficient.
Cons:
- No such limitations except that the implementation of this approach requires an understanding of core data structures and programming paradigms.
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.
- Part 1 — Introduction to Best Grouping Cards in Online Rummy
- Part 2 — Cracking the Code: Algorithmic Approaches to Determine Best Grouping in Online Rummy
- Part 3 — Decision Science in Action: To Drop or Not to Drop in Online Rummy
- Part 4 — Data-Driven Insights: Picking from the Open Deck in Online Rummy — Coming Soon
- Part 5 — Analyzing Patterns: Optimal Discard Strategies in Online Rummy — Coming Soon
- Part 6 — Leveling up: Mastering Best Grouping Techniques in Online Rummy — Coming Soon
- Part 7 — Empowering Players: Enhancing Hand Dropping Skills in Online Rummy — Coming Soon
- Part 8 — Elevating Gameplay: Mastering the Art of Picking from the Open Deck in Online Rummy — Coming Soon
- Part 9 — Refining Strategy: Improving Optimal Discarding in Online Rummy — Coming Soon