Designing challenges for Top Drives can be challenging! Here’s one of our engineers to explain how we approached one important element - calculating how many hands win against an opponent.

The Requirements

Challenges consist of multiple rounds. In each round you compete against a bot opponent, racing a car of your choice against an opponent’s car in 5 different races (tracks). The bigger the margin of win, for example in the time difference, the larger the score in the race.

A Top Drives game designer is responsible for designing each round by selecting the opponent cars and the track they will race on. During this design phase our designers need to know how many hands (permutations with 5 cars) can beat a certain opponent hand and by how much. They can use this as an indicator of how difficult a challenge is and design challenges that not only are possible to complete but also have rounds with varying degrees of difficulty.

A typical challenge can easily have more than 30 different opponents, and while designing it, we need to calculate the winning hands for every one of them. So we need a fast solution that can also accommodate short iterations where the designers are tweaking the cars in each opponent hand.

The Meditation Of Dr. Strange

Top Drives currently contains a few thousand cars and each car can be in one of around one thousand so-called “upgrade states”. This results in more than 10^30 different permutations of 5 cars, which is more than the number of atoms in the human body. So calculating all the winning hands is not computationally feasible.

One factor that limits the possible hands we need to consider, is the fact that each car has a value called an RQ and each round has a Max RQ limit. Valid hands are only those hands whose Hand RQ (sum of the RQ values of the 5 cars) does not exceed the Max RQ. But this still does not reduce the complexity of the problem in a useful way.

So we need to reduce the number of possible hands. To do that, we have to abandon a perfect solution and go for an approximate one. This is how we chose to approximate the solution:

• We reduced the number of considered “upgrade states”

• We assigned a score to each car based on how many cars it can beat in a specific race. Let’s call this the Victory Score. Note that this is a generic indicator of how a car performs in the race, not an exact score against each of the other cars.

• We redefined the problem as trying to maximize the total Victory Score of a hand while not letting the Hand RQ exceed the Max RQ. We still want to get the maximum Hand RQ possible.

So now the problem has become a maximization one. We are not interested in the number of winning hands anymore or in enumerating those hands. We are only interested in a single hand.

This problem resembles the 0-1 Knapsack Problem. So as hard problems come, it might be a relatively easier one to tackle in practice. However, one key difference is that we need a permutation of cars and the cars have different scores (what is called a “value” in the definition of the Knapsack Problem) for each race.

Thor’s Hammer

“When in doubt, use brute force.”

• Ken Thompson

We could iterate through all the cars in each of the 5 races and calculate the total Victory Score of each hand. Given that we still have many thousands of candidate cars for each race, that would produce a number of hands that is larger than the age of the universe in seconds, making the running time of the algorithm prohibitive. So we need to reduce the number of possible hands even further.

One key observation we can make is that since we are looking to maximize the Hand RQ, we can group cars by their RQ and iterate through RQ values instead of through individual cars. This makes a big difference in the number of possible hands if we combine it with a second observation: since we are looking to also maximize the total Victory Score, for each RQ value, we only need to consider the car that has the highest Victory Score.

These two observations allow us to reduce the number of candidate cars for each race to 91, as we have that many different RQ values. Add on top of that a couple of ordering heuristics that come from insights into the search space of our problem, and we have an algorithm that can be used to find our approximate winning hands in a matter of minutes, for all practical purposes.

A Faster Way To Win

Waiting several minutes to calculate a winning hand is still not good enough for our design processes. Due to the specific conditions of our problem (race scores and car RQs can change, there are hundreds of different tracks and Max RQ limits, etc.), it is not feasible to pre-compute the winning hands. We need a solution that is fast enough on the fly.

In an approach inspired by bidirectional search and memoization, we can do two smaller exhaustive searches. Since we have 5 ordered slots (races) for cars, we can do a separate brute-force search for some of the slots and combine the results.

To better visualise this assume two directions, from slot 1 towards slot 5 and from slot 5 towards slot 1. For example, we can first do an exhaustive search for slots 3, 4 and 5, so a permutation of 3 cars, and store (cache) the results by total RQ. We can follow this with an exhaustive search for slots 1 and 2, so a permutation of 2 cars. When we have the 2 cars, we can use the remaining total RQ to look up the best remaining 3 cars, and either prune this permutation of 5 cars or add it to the candidate solution.

Using this approach we were able to reduce the running time of our solution from a few minutes down to a few dozen milliseconds. This is fast enough to allow the algorithm to be used on the fly when designing challenges.

Next Steps

Our tool currently calculates the best of the winning hands. These hands often contain highly upgraded cars and also repeat (duplicate) cars. This is something that is unlikely to happen in reality, particularly for the higher rarity cars that are more difficult to collect and upgrade.

This means that at the moment a winning hand can be unrealistic. So we need to also calculate a different kind of winning hand, one that would be more common among the majority of our player base. In the next iteration of this tool, we could also calculate the worst winning hand, one that would contain cars with lowest rarity and upgrades.

Having both hands available would allow our game designers to better infer the difficulty of a challenge round.

Look out for more Tech blog posts coming soon!

And if you're an Engineer looking to start a new chapter in your career, check out our current vacancies here: hutch.io/careers. We'd love to hear from you!

References:

1. Dake, “Knapsack.” Illustration of the knapsack problem, 9 July 2007, https://en.wikipedia.org/wiki/Knapsack_problem. Accessed 14 July 2021.

2. “Bidirectional Search.” Search Techniques, Judea Pearl and Richard E. Korf, Annual Review of Computer Science 1987 2:1, 451-467****

3. “Memoization”, https://en.wikipedia.org/wiki/Memoization, Accessed 14 July 2021.