Algorithmic Modelling – Achievement Hunting (Slay the Spire, Part 2)

Many modern video games feature an achievements system. Achievements are typically awarded for completing specific tasks; typically achieving all of these requires doing substantially more than just what is required to finish the game. In many cases, it’s not even possible to complete all of the achievements on one playthrough.

In a previous post, I wrote about Slay the Spire, an RPG where combat is driven by a deckbuilding mechanic. The game also features an achievements system. I finished getting 100% completion on these achievements this week – this took quite a long time. If I wanted to start from the beginning and accomplish these as quickly as possible, I would need to plan carefully. The main issue here is that achievements are not independent. For example, there are chains of achievements where the final achievement subsumes all previous ones (e.g. “have 99 block, have 999 block” or “unlock ascension mode, finish ascension 10, finish ascension 20”). Furthermore, some achievements can be achieved using the same strategy (e.g. “play 25 cards in a single turn” and “defeat a boss before it takes a turn”, which can both be achieved by building an infinite combo). Other achievements can often be significant handicaps (e.g. “beat the game with a deck that has no uncommons or rares”, “beat the game with only 1 relic”) and I thus think it’s a lot harder to combine these with other achievements.

The game is played in distinct runs, and a majority of the achievements involve performing specific feats on individual runs. We can model this by identifying strategies that unlock one or more achievements. If we try to use the fewest number of distinct approaches, this becomes what’s called a set cover problem. There are achievements and strategies with each being non-empty and a subset of . We also require that , otherwise not all achievements are achievable. The goal is to identify some set of strategies we need to deploy such that . Trivially, picking everything is possible, but it’s very unlikely that that’s going to be minimal.

This problem is known to be NP-hard; the decision version (does there exist a solution using strategies or fewer?) is NP-complete. Clearly, we can obtain a solution that is worst-case exponential in by iterating through each possible subset of , checking if it satisfies the criteria and remembering the best solution we’ve seen so far. There’s a little dynamic programming trick we can do to memoise partial achievement states (e.g. I can get to the state where I have the first 8 achievements and no others using two runs with one strategy but three with another; I’ll always pick the first). This achieves a solution exponential in but linear in , which is an improvement. We can also try to pre-process the input for and a little, by eliminating any achievements that are subsumed by harder achievements, and by eliminating any strategies that are strictly dominated by others.

If this is unacceptable, we can either try to use approximation algorithms (for example, a standard ‘greedy algorithm’ which picks the subset with the most outstanding items doesn’t always fare too poorly). We can also attempt to leverage constraint solving systems; these don’t deal with the exponentiality of the problem directly, but they often have good heuristics to deal with this.

That said, this isn’t a very good model, as some strategies are riskier to implement than others. For example, it may be theoretically possible to combine “beat the game with one relic” and “beat the game without uncommon or rare cards”, but that seems unlikely. For example, if each of these individually has a 1% chance of being completed but attempting them together has just a 0.1% chance, doing the achievements separately will take an expected 200 runs while the combined approach has an expectation of 1000.

A natural extension to this is to consider the weighted version of the problem. We change the formulation slightly, so each strategy has a weight and we seek to minimise the total weight of the strategies we pick. If we assign a strategy a given probability of success , since runs are (mostly) independent, the expected number of runs it takes to attain a successful outcome would be following standard geometric distribution results. The dynamic programming based algorithm still works if we keep track of weights instead of number of sets.

This is better, but there are still a few issues with the model. Firstly, partial successes haven’t been considered in this model; we might try a risky strategy for three achievements and fail, but still complete two of them. We could try to account for these by figuring out some kind of state transition between achievement states – it wouldn’t be a set cover problem any more. We would be building some kind of a discrete-time Markov chain on-the-fly.

Modelling this as a set cover problem also seems to imply that our algorithm is offline; that is, it formulates a strategy and then executes it. However, Slay the Spire has a significant luck element, especially if one is trying for specific achievements, and thus an offline algorithm doesn’t work so well. For example, one achievement requires “play 10 shivs on a single turn” and another “have an enemy reach 99 poison”; the cards and relics that support these are quite different, and depending on what cards are offered as the game progresses, one achievement or the other could become easy or nigh-impossible. If both achievements remain to be unlocked, it seems suboptimal to commit early on.