Identifying and Collecting key Data
I explored several algorithms to optimize and reduce the search space for all possible combos. Nevertheless, the indisputable fact that each card can appear twice increased the variety of potential combos, making it difficult to trace and validate every one. While competing on Codeforces, I encountered an issue that jogged my memory of the ‘island problem,’ which gave me recent insight into approaching the hand evaluator system.
We are able to represent the hand as a 2D grid of size 4×13, where each column represents ranks from 1 to 13 and every row corresponds to the 4 suits. Each cell on this grid comprises the count of cards within the hand in our case either 1, 2, or 0 . This permits us to divide the hand into ‘islands,’ that are defined as groups of connected land cells with counts of 1 or 2 based on the next connectivity rules:
1. Two cells are considered connected in the event that they share a side (left, right, above, or below) within the grid.
2. All cells throughout the same column are also connected in the event that they each contain not less than 1s, even in the event that they aren’t adjoining (above or below).
EXP of ‘ hand A’ : 11C 3H 4H 11D 3D 5H 9D 2H 6H 3C 4H 3D 4D 5H 12D 3C
Our first task is to discover and label all distinct islands. Since each island is independent of the others, we will make our life easier by mapping each island to a category type let’s name it _cardGraph. This class can be answerable for that island by way of extracting, modifying, or deleting operations.
For clarity, let’s isolate one island and work on it within the upcoming sections, so it’s easier so that you can follow. If it helps, you may consider each island as a connected graph, as Shown within the figure below:
Now If you happen to take multiple island examples and check out to extract the possible combos, you’ll notice that some cards have unique roles in branching out to a possible combos. We’ll call these form of cards a control points or Cpts for brief, as they play a necessary role by reducing the search space significantly as you will note in the next steps.
Cpts: For a card to be considered a Cpts, it have to be ready where we’ve to select on which meld (run or set) to append it to. If a card can naturally fit into multiple melds without forcing a alternative (for instance, a reproduction card with two options for melds each card will append to a meld), it won’t be considered a Cpts.
Within the case of our island example the three of heart is identified as a cpts. Below are all of the melds that the three of Hearts could attach to, one after the other.
Our next step is to mark each card that qualifies as a Cpts. To do that, we’ll create a 4×13 (in byte type) table lets call it _flagMap . Now for memory efficiency, you may make this a shared table each _cardGraph instance created from the hand can reference it and use it . On this table, each card in an island can be assigned a bitstream on the corresponding index in _flagMap, this byte will represents its potential placements in numerous runs or sets. If a card qualifies as a Cpts, it would be stored in a stack (we are going to need later), which we’ll call _cptsStack. Here’s a breakdown of the byte structure: the primary bit indicates whether the cardboard belongs to a run, the second bit indicates its placement in a further run, the third bit represents whether it belongs to a set, and the fourth bit specifies if it belongs to multiple sets.
Here’s an example of a bitstream: 00000111 In here we’ve:
• The primary bit (1) means the cardboard can belong to a run.
• The second bit (1) means the cardboard can belong to a second run.
• The third bit (1) means the cardboard belongs to a set.
• The fourth bit (0) means the cardboard doesn’t belong to a second set.
We could be in case where the configuration is 00000101 for one card (no copy), meaning the cardboard belongs to a run or a set. Or one other configuration might be 00000011, meaning the cardboard belongs to 2 different runs.
To discover a cpts, simply count the ‘1’s in its bit representation. If this count exceeds the entire variety of that card within the hand, it’s considered a cpts. As an example, if a card appears twice (i.e., has two copies) and its bit representation is 00000101, it’s not a cpts. Nevertheless, if the bit representation is 00000111 like the instance , then it qualifies as a cpts.
In our island example, here’s how the _flagMap table would look :
Once we’ve populated the _flagMap and identified the cpts, the subsequent task is to decompose the island into horizontal and vertical lines. But why? Breaking down the cardboard graph into these lines simplifies the technique of identifying runs and sets, because it allows us to give attention to contiguous sequences of cards that may be processed more efficiently. As you may guess, the vertical lines will represent the sets, while the horizontal lines will represent the runs.
We’ll store each horizontal line in an inventory of a tuple type, where the primary item represents the starting index of the road and the last item represents the tip index (inclusive). For the vertical lines, it’s sufficient to easily store the column index in an inventory.
Tip: We are able to accomplish this task together with the bit representation step in a single loop, achieving O(n) complexity.
Generate Combos
Now, let’s take a break and recap: we’ve identified the control points (CPTs) and stored them within the _cptsStack. We also decomposed the island into vertical and horizontal lines, and populated the _flagMap with card bit representation.
With our data in place, what stays is to make use of it to generate all possible valid combos of the island. But how can we do this? Here’s a simplified approach:
1. Assign Valid Placements for the Control Points (Cpts):
We take the bit representation of a cpts from _flagMap, which indicates all possible placements for that cpts. Then, we take a look at the variety of copies of the cpts within the _cardGraph and adjust its bit representation to a current valid configuration. For instance, if the cpts has a bit representation of 00001111 and a couple of copies, we will generate all valid placements for it, which is C(4,2)=6C(4,2) = 6C(4,2)=6. Possible combos could be 0011, 0101, 1100, 1010, 1001, and 0110.
2. Using DFS to Configure All Possible Combos for Each Cpts:
We’ll use a depth-first search (DFS) to iterate over the valid placements for every cpts as shown in step 1. Each node within the DFS tree represents a possible placement for a given cpts, so each unique DFS path represents a sound combo configuration. For every “leaf” node (end of the DFS path), we proceed to the subsequent step.
3. Generating Combos:
On this step, we iterate over the horizontal and vertical lines within the island to discover runs, sets, and a dump list. This is finished in two passes for every line, as follows:
- Pass 1: For a horizontal line, for instance, we repeatedly append cards from [line start to line end] into an inventory to form a run. We stop adding if ( card_bit_representation | 00000001 == 0 ). If the length of the run is larger than or equal to three, we add it to the run combo; otherwise, each card goes into the dump list, and we proceed attempting to form one other run until we reach the road end.
- Pass 2: Repeat the method, this time on the lookout for cards that match a special bit pattern with or operation ( 00000010). This permits us to discover possible second runs.
The identical approach applies to extracting sets, but we use bit operations with 00000100 and 00001000.
4. Register the Valid Combo and Move to the Next DFS Configuration:
After completing all runs, sets, and dumps for the present combo, we save the combo after which move on to the subsequent DFS configuration to repeat the method. This manner, we systematically explore all potential configurations for valid combos.
in the event you coded the whole lot accurately and feed it our island example : ”2H3H4H5H4H5H6H3C3C3D3D4D”, it ought to be decomposed as shown bellow. Notice that I’ve added some calculation to every generated combo in order that we will get a way of how the AI will act.
In the subsequent article, I’ll dive into the remaining of the system, specializing in the dynamic modification of the hand and the AI strategy. If you happen to’ve followed along thus far, it won’t be hard to see how we will optimize adding and removing cards, in addition to incorporate the 2 rules we put aside firstly. Stay tuned, and see you next time! “hopefully 😉”.
Unless otherwise noted, all images are created by the writer using Lucidchart ,Gimp and Python
