Sometimes you create a problem so abstract that you don't recognise that it is long solved.
During a casual chat, I got the idea of building a machine which automatically takes in all Magic cards in my collection, indexes them, and stores them.
The idea also got a bit more technical but for this post only one thing is relevant: The cards are supposed to be moved via a 2 axis arm with a downward facing extensions with a suction cup at the end to grab the cards.
Now came the thing that got my thoughts going. How do I dispense a requested deck, in the correct order, the fastest? I felt like there must be an optimal, non-heuristic algorithm, to solve this issue. To test this I build a simplified abstract setup with the following specifications and assumptions:
- Cards are represented by the numbers 1 ... x
- Duplicate cards are not allowed
- There are always at least 100 cards in the system
- There are always at least 2 stacks in the system
- Before each run, all cards are distributed among the stacks in a round-robin fashion
- Each stack has a maximum capacity of
(number_of_cards / number_of_stacks) * 2 - Exactly 60 cards are selected before each run
- A specific order is chosen for these cards
- Each card movement counts as one step
- A run ends once all 60 cards have been dispensed in the correct order
- The distance the gripper has to travel and how deep it has to reach are assumed to be irrelevant
With these specifications in mind I build a simple setup in Python which replicates them, and used the typical stack of numpy,pandas,plotly
to build a small benchmark the algorithms could be thrown against under different conditions. (More/less Cards/Stacks)
And with hundreds of random seeds to exclude the possibility of creating an accidental bias. It also enabled me (python) to calculate the standard deviation for each condition.
So I began writing algorithms. Starting with the most simple approach.
- Look on which stack the next required card is
- Remove cards from the top and deposit them to the next not-full stack until the card has been reached.
- Repeat
Clearly visible is that the number of required steps is growing linearly with more cards, and falling exponentially as more stacks get added. This is roughly the same behaviour for all following algorithms so I won't use this graph again.
The next iteration was the same algorithm with the only tweak being that the unwanted cards get deposited into the stack which currently holds the least cards, distributing them more evenly.
This change resulted in consistently fewer steps taken compared to the previous iteration.
However both of these algorithms have the issue that they can bury later needed cards deep within the other stacks due to only searching for the one currently needed to progress.
So next I tried to address this issue. The new algorithm looked like this:
- Before starting to do anything
- look at all stacks and determine the stack containing the largest count of required cards (SLC)
- Remove the required cards from all stacks besides the SLC the same way the previous algorithm did
- While clearing the stacks, place all cards which are required but currently not the one in order to be output onto the SLC
- When discarding cards, prioritize stacks which have already been cleared of any required cards
- Once done, clear the SLC using the previous algorithm.
This should result in a longer time-to-first-card but also to a significant reduction in steps needed.
It however ... did not improve at all.
I had a few more ideas which I did try out, sometimes getting slightly better results, sometimes extremely promising results but with a standard deviation that made them glorified edge-cases.
I won't go into depth here anymore as the underlying result was always the same. More cards mean linear growth, more stacks an exponential reduction.
For the next days I left the problem sitting around on my laptop until I at some point during a stroll through the forest realized that my focus on the problem of getting the cards out, made me blind to the fact that I was describing a good old HDD (kinda).
While the parallels are not perfect, an HDD is also limited by the fact that it can only read one place at a time, having to collect data from all over the disk reduces the read speed, adding more HDDs (in our case) stacks increases read speed since relatively speaking each HDD needs to read less, which reduces, movements between points, which results in faster reads.
I know that this is not a perfect fit. However at the core, our Magic Card Dispenser has to master the exactly same challenges as the HDD.
And what is the answer to slow optimizing read speeds on HDDs? Defragmentation! Placing data (cards) which are often read together (often requested in the same decks) closer to each other physically so that the average read speed increases. Random access stays slow but even for that there can be occur consistent optimizations through pure luck.
So what is the conclusion for our maybe-never-to-be-realized project? Once the user is finished adding cards, which for the benefit of speed should happen basically at random, the machine should start optimizing the placement of these cards.
Even here there is no clear answer to how the defragmentation should happen:
- It could be fully heuristic; green to green, land on land, ...
- It could learn from user behaviour and even softly "prepare" decks the user has configured
- It could look at databases and calculate from hundreds-of-thousands of decks, which cards are most likely to be used together.
- ...
I do not have a real conclusion to this one. Maybe it is just a casual reminder that it is easy to get stuck optimizing the wrong thing. It is also easy to see your own projects as fully unique instead of thinking about similar applications that you can learn from, even if only through creative abstraction.
- Lilly