Identification and collection of key data
I explored various algorithms to optimize and reduce the search space for all possible combos. However, the fact that each card can appear twice increased the number of potential combinations, making it difficult to track and validate each one. While competing in Codeforces, I ran into a problem that reminded me of the 'island problem,' which gave me new insight into how to approach the hand evaluation system.
We can represent the hand as a 2D grid of size 4×13, where each column represents the ranks 1 to 13 and each row corresponds to the 4 suits. Each cell in this grid contains the card count in the hand, in our case 1, 2 or 0. This allows us to divide the hand into “islands”, which are defined as groups of connected land cells with counts of 1 or 2 depending on the following connectivity rules:
1. Two cells are considered connected if they share a side (left, right, up, or down) on the grid.
2. All cells within the same column are also connected if they both contain at least ones, even if they are not adjacent (above or below).
'Hand A' EXP: 11C 3H 4H 11D 3D 5H 9D 2H 6H 3C 4H 3D 4D 5H 12D 3C
Our first task is to identify and label all the different islands. Since each island is independent of the others, we can make our lives easier by assigning each island to a class type, let's call it _cardGraph. This class will be responsible for that island in terms of extraction, modification or removal operations.
For clarity, we will isolate one island and work on it in the next sections, so that it will be easier for you to follow. If it helps, you can think of each island as a connected graph, as shown in the following figure:
Now, if you take several island examples and try to extract the possible combinations, you will notice that some cards have unique functions by branching out into potential combinations. We will call these types of cards checkpoints either Cpts In short, since they play a fundamental role in significantly reducing the search space as you will see in the following steps.
Cpts: For a card to be considered Cpts, it must be in a position where we have to choose which combination (run or set) to add it to. If a card can naturally fit into multiple combos without forcing a choice (for example, a duplicate card with two combo options, each card will be added to a combo), it will not be considered Cpts.
In the case of our island example, the 3 of hearts is identified as cpts. Below are all the combinations that the 3 of Hearts could join, one at a time.
Our next step is to mark each card that qualifies as Cpts. To do this, we will create a 4×13 table (in byte type), let's call it _flagMap. Now, to improve memory efficiency, you can make this a shared table; every manually created _cardGraph instance can reference and use it. In this table, each card in an island will be assigned a bitstream at the corresponding index in _flagMap, this byte will represent their potential locations in different runs or sets. If a card qualifies as Cpts, it will be stored in a stack (we'll need it later), which we'll call _cptsStack. Here's a breakdown of the byte structure: the first bit indicates whether the card belongs to a run, the second bit indicates its location in an additional run, the third bit represents whether it belongs to a set, and the fourth bit specifies whether it belongs to multiple sets.
Here is an example of a bitstream: 00000111 Here we have:
• The first bit (1) means that the card can belong to an execution.
• The second bit (1) means that the card may belong to a second print run.
• The third bit (1) means that the card belongs to a set.
• The fourth bit (0) means that the card does not belong to a second set.
We could be in the case that the configuration is 00000101 for a card (no copy), which means that the card belongs to a run or a set. Or another setting could be 00000011, which means the card belongs to two different runs.
To identify a cpt, simply count the '1's' in its bit representation. If this count exceeds the total number of that card in hand, it is considered cpts. For example, if a card appears twice (that is, has two copies) and its bit representation is 00000101, it is not a cpt. However, if the bit representation is 00000111 as in the example, then it qualifies as cpts.
In our island example, this is what the _flagMap table would look like:
Once we have populated the _flagMap and identified the cpts, the next task is to decompose the island into horizontal and vertical lines. But why? Splitting the card graph along these lines simplifies the process of identifying runs and sets by allowing us to focus on contiguous sequences of cards that can be processed more efficiently. As you can guess, the vertical lines will represent the sets, while the horizontal lines will represent the races.
We will store each horizontal line in a tuple-type list, where the first element represents the starting index of the line and the last element represents the ending index (inclusive). For vertical lines, simply store the column index in a list.
Advice: We can perform 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 have identified the checkpoints (CPT) and stored them in _cptsStack. We also decomposed the island into vertical and horizontal lines, and populated the _flagMap with card bit representation.
With our data ready, what remains is to use it to generate all the possible valid combos on the island. But how do we do that? Here is a simplified approach:
1. Assign Valid Locations for Control Points (Cpts):
We take the bit representation of a cpt from _flagMap, which indicates all possible locations for that cpt. Next, we look at the number of copies of the cpts in _cardGraph and adjust their bit representation to a current valid configuration. For example, if cpts has a bit representation of 00001111 and 2 copies, we can generate all valid locations for it, which is C(4,2)=6C(4,2) = 6C(4,2)=6. The possible combinations would be 0011, 0101, 1100, 1010, 1001 and 0110.
2. Using DFS to configure all possible combinations for each Cpt:
We will use a depth-first search (DFS) to iterate over the valid locations for each cpt as shown in step 1. Each node in the DFS tree represents a possible location for a given cpt, so each unique DFS path represents a path valid. combined configuration. For each “leaf” node (end of the DFS path), we proceed to the next step.
3. Generating Combos:
In this step, we iterate over the horizontal and vertical lines of the island to identify runs, sets, and a list of dumps. This is done in two passes for each line, as follows:
- Pass 1: For a horizontal line, for example, we continually add cards from (from the beginning to the end of the line) in a list to form a series. We stop adding if ( card_bit_representation | 00000001 == 0 ). If the length of the run is greater than or equal to 3, we add it to the run combo; otherwise each card goes to the dump list and we continue trying to form another series until we reach the end of the line.
- Pass 2: Repeat the process, this time searching for cards that match a different bit pattern with the operation u (00000010). This allows us to identify possible second executions.
The same approach applies to set extraction, but we use bit operations with 00000100 and 00001000.
4. Register the valid combo and proceed to the next DFS configuration:
After completing all runs, sets and dumps for the current combo, we save the combo and then move on to the next DFS setup to repeat the process. In this way, we systematically explore all potential setups for valid combos.
If you coded everything correctly and fed it with our island example: “2H3H4H5H4H5H6H3C3C3D3D4D”, it should break down as shown below. Note that I added some calculations to each generated combo so we can get an idea of how the ai will act.
In the next article, I'll delve into the rest of the system, focusing on dynamic hand modification and ai strategy. If you've followed this far, it won't be difficult to see how we can optimize the addition and removal of cards, as well as incorporate the two rules we left out at the beginning. Stay tuned and see you next time! “hopefully ”.
Unless otherwise noted, all images are created by the author using Lucidchart, Gimp and Python.
