Leveraging Dynamic Programming to Improve Player Performance in Rummy

Written by Shubham Sharma

“Are data structures and algorithms even useful in a software engineering job?”

Over the past few years, there has been a drift towards people assuming that algorithms and data structures are useless and are asked by tech companies just as a thoughtless practice.
Even the likes of Max Howell, the founder of Homebrew and Brian Acton, the co-founder of Whatsapp supported this sentiment after posting about their interviews in today’s big tech companies.

While the chances of encountering a use-case involving the inversion of a binary tree, in reality, are very thin but as an engineer, you directly or indirectly come across different problems which require writing code and making decisions based on your understanding of many algorithmic concepts. In a nutshell, knowing how intricate algorithms or exotic data structures work is not something you need to know but identifying what an algorithm is and being able to devise simpler algorithms on your own is ample.

Here’s one such problem that we solved in multiple iterations that required us to understand fundamental data structures and algorithmic concepts.

Background

Our gaming division JEET-11, recently released the beta version of a popular card game in India, Rummy.

Rummy is a turn-based card game in which you try to improve the hand that you’re originally dealt. You can do this whenever it’s your turn to play, either by drawing cards from a pile (or stock) or by picking up the card thrown away by your opponent and then discarding a card from your hand.

To educate our players, we wanted to give them the ability to generate the best combination of cards that they could have arranged for each declaration. This would let the players know various combination strategies helping them to make better decisions in the game.

Before jumping to the problem, if you have never played Rummy, here’s a quick overview of the rummy vocabulary that you might want to know. Terminology Used

The Problem

Given a set of 13 cards, divide these cards into multiple melds of 3 or more cards, such that these melds form the most optimal declaration.
In Rummy, for a declaration, a player can arrange his cards into sets and sequences, and cards that are not a part of any set or sequence form the deadwood. The goal of our algorithm is to find the most optimal melding for a given group of 13 cards provided it’s a valid declaration, which minimises the sum of the values of all cards belonging to the deadwood.

For the given set of 13 cards,

The initial set of cards

the optimal melding is

If any input has multiple solutions, any of them works.

The Solutions

Following are the solutions in order from the least optimal to the most optimal solutions we could come up with.

Before moving to the solutions mentioned below, we encourage you to take a step back and think of the problem and how you would go about solving it.

1. Et Tu, brute force?

On observing you would notice that the problem is like the “set-cover” problem which is an NP-Complete problem. To recall, for an NP-Complete problem, the correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions. And that’s what this solution does.

When constructing the most optimal melding, for every card selection the algorithm has to try all the leftover cards, enabling us to cover all the permutations. For every card selection when already n cards are selected, we have 13-n possibilities. Initially, for 13 cards, we have in total 13! = 6227020800 possibilities.

We didn’t continue with this approach as this solution is already very infeasible in terms of time and space required and wouldn’t suffice our response time expectations.
Besides, we also want to ensure we split our selected cards into multiple melds at each selection and keep track of the total pure sequences and sequences constructed, which will require even more operations and memory, making this solution even slower.

Pros
1. Yields the correct result.
2. Simple implementation.

Cons
1. Too slow, time complexity would be O(13!) even when we don’t consider the melding part.
2. Would consume a lot of stack memory to keep track of already chosen melds.

2. The better brute force

In the previous solution, you can observe that we would generate a lot of melds that are neither a set nor a sequence. For instance, melds like [ 1♦, 5♠, 3♣ ] are fundamentally deadwood as they don’t have the same suit or the same values.
This solution uses this observation and tries to compute only those sets or sequences which are a potential candidate in the optimal melding.

The solution has two steps, pre-computation + backtracking.

Precompute
This step involves the generation of all the possible sets, sequences and pure sequences from the given cards. In addition, we also want to precompute for each valid-meld, it’s all other mutually inclusive valid-melds ie. two melds are mutually inclusive if they have at least 1 common card.

Backtrack
This step involves the generation of our final result. At each step, we choose one of the precomputed valid-melds and add it to our solution. Once a meld is a part of the solution we remove all its mutually inclusive melds from the subsequent selections. Among all such solutions, we choose the one in which the sum of all the melds chosen is maximum. More precisely put, we perform the following

1. At each step, choose one of the available valid melds (precomputed)
2. Once a meld is chosen, limit the choices for the next selection by removing mutually inclusive melds with the chosen meld
3. Repeat steps 1 and 2 till no meld is available for selection

The 2nd step ensures that we don’t select 2 melds having the same card.

Performing the above steps will generate an n-ary tree structure like this

In the above tree, the final combination would be the path from the root to the leaf with the maximum sum of all melds on the path.

To ensure that we fulfil the pure-sequence and sequence requirements of a valid declaration, we allow only pure-sequences to be available for level 0 of the tree and a sequence to be selected at level 1.

This tree would have a maximum depth of 4, as all cards would be exhausted after choosing at-max 4 valid melds.

The branching factor at each level depends on the melds at the previous levels and is hard to quantify, but over a diverse set of card combinations the average branching factor comes out to be ≈15.

Pros
1. Huge improvement over the previous brute force, search space reduced exponentially.
2. Able to achieve effective response times, produces results under 100ms on a light Golang server.

Cons
1. Keeping track of all available melds at each level is memory heavy.
2. Susceptible to memory leaks with more concurrent requests.

3. BITMASKS!

In our previous solutions, there are many overlapping subproblems in the search space that are re-computed each time.
The idea here is to simply store the results of subproblems effectively so that we do not have to re-compute them when needed later. The solution is based on dynamic-programming optimization.
However, currently, our subproblems are a function of the remaining cards, which programmatically will be an array/list. So it’s fairly complicated to store these results.

Enter, Bitmasks

By definition, Bitmask also known as a mask is a sequence of N -bits that encode the subset of our collection. The element of the mask can be either set or not set (i.e. 0 or 1). This denotes the availability of the chosen element in the bitmask.

In our case, any combination/subset from the given N cards can be represented by a binary string having no more than N bits. The ith bit is set if the card is present in the subset else unset. E.g. from the binary string 1000100010001, it can be inferred that the 1st, 5th, 9th and 13th cards from the left are present in the combination represented by this binary string. This binary string in its decimal form is an integer less than 2¹³= 8192, making it fairly easy to store results for each subset of cards.

Let F(mask, requirementState) represent the minimum score achievable using the cards represented by mask considering we have already full-filled the conditions represented by the integer requirementState.

The requirementState takes values from 0 to 2 and represents the following.

1. requirementState = 0, represents that till now, no pure-sequence or sequence has been formed
2. requirementState = 1, represents that till now, 1 pure sequence and no other sequence has been formed
3. requirementState = 2, represents that till now, 1 pure sequence and at least one another sequence has been formed. This state is mandatory for a combination to be valid

Then the solution to F(mask, requirementState) would be dependent on its substates, conditions to prune the substates:

1. At each state, consider transitioning to a substate for each subset of mask which forms a valid meld. Let’s say if the chosen valid meld is represented by a submask, then the substate would be F(mask^submask, newRequirementState).
   The newRequirementState depends on the value of requirementState and on the meldType of submask, i.e. pure-sequence, sequence or a set. Consider the path which returns the lowest sum of cards as the optimal path.
2. Considering melds of the length of 3,4 and 5 will always produce the optimal results. Melds of length greater than 5, can be split into two or more melds of length ≥ 3. Hence only consider submasks with 3 ≤ total_set_bits ≤ 5.

The solution to our problem then would be F((2¹³ — 1), 2), which can be solved recursively by solving all its substates. The base case for the recursion would be the sum of all cards left at the end. Storing the result of each state in a 2D auxiliary space ensures that we don’t compute one state repeatedly.

Example subproblem with 7 cards, each card is represented by 1 set bit

Here’s a visualisation of how the bits get flipped for this subproblem with the given 7 cards with each card represented as one set bit.

Recursion tree for the given 7 cards, yielding best score of 1

The maximum number of states for which we compute the result for using this approach are 2¹³ * 3 = 24576, that’s approximately 2.5 Million lesser compute operations from our factorial order solution, this approach would require only 99Kb of auxiliary memory assuming int_32 taking 4 bytes.

Pros
1. Very fast compared to previous solutions, constantly produces results under 10ms on a light Golang server.
2. Extra memory required is well within limits, not prone to frequent memory leaks.

Cons
1. Not any con we could think of, however, the implementation might be a bit trickier than the other solutions, but this doesn’t affect the performance or functionality of the solution.

Deployment

Our game servers run Node.js containers in a K8s cluster. Before this feature, the game had no CPU bound tasks. Node.js runs a single-threaded event loop to concurrently perform many tasks, for example, serving multiple incoming HTTP requests.
A typical healthy Node.js server application is I/O bound. That is what Node.js does best, instead of having to ‘wait’ for an I/O operation to complete (and essentially waste CPU cycles sitting idle), Node.js can use the time to execute other tasks. However, things change when the operations are CPU bound, CPU bound tasks are performed synchronously on the main event-loop potentially blocking the execution of other incoming requests.

There are many workarounds to perform CPU bound tasks on Node.js like
1. Native C/C++ Add ons
2. Offload tasks to worker threads
3. Splitting of a CPU bound task using the built-in setImmediate() function
4. Polyglot setup with a sidecar

We’ll be writing about running CPU bound tasks on Nodejs, and benchmarking different solutions we explored. Do look out for the upcoming blogs at Tech@ShareChat.

Terminology used

• Card: A card from a standard 52-card deck and 2 joker cards.
• Meld: a meld is a set of cards, typically three or more, that earn player points and/or allow them to deplete their hand.
• Joker card: A joker can be used as a substitute for any other card when composing a sequence or a group or when adding to an already existing meld. There are 2 joker cards in addition to the standard 52 cards
• Wild-card joker: At the beginning of the game, a random card is selected as a wildcard joker. All the suits of that value are also the wildcard joker. For example, if 7♣ is the selected card, then 7 of ♦, ♠, and ♥ are all wildcard jokers for that game.
• Pure sequence: A pure sequence is a group of three or more cards of the same suit, placed in consecutive order. To form a pure sequence in Rummy, a player cannot use any Joker or wild card. E.g. 6♥ 7♥ 8♥ (Pure sequence with three cards)
• Impure Sequence: An impure sequence is a group of three or more cards of the same suit with one or more Joker / Wild-card joker used. E.g. 6♦ 7♦ 🃏 9♦ (Here the joker card 🃏, is used in place of 8♦ to create a sequence)
• Set: A set is a group of three or more cards of the same value but of different suits. When you are forming sets, you can use wild cards and Jokers. E.g. A♥ A♣ A♦.
• Valid Declaration: Declaring in rummy means that you have to lay down your arranged cards on the table for the other players to see. A valid declaration requires 2 sequences, out of which one needs to be a pure sequence i.e. sequence without a joker and the other can be a pure or impure sequence. E.g. Consider this declaration, 2♥ 3♥ 4♥ | 5♣ 6♣ 🃏 | 8♦ 8♠ 5♣ | 2♦ 2♣ | K♠ Q♠ The first 2 groupings have 1 pure sequence and 1 impure sequence making this declaration valid.
• Deadwood: Any remaining cards from your hand which are not part of a valid combination ( set or sequence ) are called deadwood. From the previous example, the last three melds i.e. 8♦ 8♠ 5♣ | 2♦ 2♣ | K♠ Q♠ will form the deadwood.

Cover illustration by Ritesh Waingankar