Mapping Out Every Line in a Slay the Spire Fight
Recently inspired by poetry_in_shm (reddit, blog) and Caleb Gannon (video), I made a solver for Slay the Spire 2 which shows the value and optimal action for every single state in an early fight (if you’ve played the game, it’s the A10 Nibbit fight, with the Ironclad starting deck). Below I explain details, but if you have all the background feel free to just play with the solver or look at the optimal policy flowchart below. See the reddit post for an overview.
Slay the Spire 2 is a single-player card game I like a lot, and it came out in March this year. Between Spire 1 and 2 I’ve played a few hundred hours, and have always wanted to do a project on it. Hopefully this is the first of many posts :)
If you’re reading this but haven’t played Slay the Spire, I’m not sure how much of this post will make sense or be interesting, but thanks for supporting me! I hope some of the ideas about solvers or search at least will be interesting to read about.
Click for a primer on Slay the Spire mechanics!
In case you haven't played before, in short, the goal is to defeat enemies as you climb the spire. After each fight you can add 1 of 3 random cards to your deck, but at the start, you always have the same deck. Within a fight, we want to kill the enemies as fast as possible while minimizing damage taken.Here is what a fight looks like:
Each turn you draw 5 cards into your hand, which have effects like dealing damage or blocking. Cards cost energy to play, and you have 3 energy to spend per turn. After your turn, you discard any unused cards in hand and the enemy will take their turn; repeat until either side is dead. If you run out of cards to draw, you shuffle all your discarded cards back into the draw pile.
Solving Via Expectimax (Exhaustive Search)
In principle, any singleplayer game can be solved by constructing a tree of all possible outcomes. From the starting state, you consider all possible actions and chance outcomes, which produces a set of resulting states. You do this for each of the resulting states to get the next layer in the tree, and so on until the game ends in every branch. You can recursively compute the best action starting from the bottom layer of the tree and thus get the optimal action at every state. In singleplayer games this exhaustive search is called “Expectimax” since we compute the expected value at chance events and take the max value action whenever we need to take an action.
Image from Berkeley's CS 188 course notes.
The tree size is exponential in the length of the game, so for more complex games it’s computationally intractable to solve with exhaustive search/Expectimax. Fortunately as poetry_in_shm discovered, with a few optimizations this is tractable for the Nibbit fight with the starter deck; my implementation takes 1-2s. Poetry_in_shm computes the exact Expectimax solution, yielding ~8 damage taken on average. He also samples 10k-1M fights to get the distribution of outcomes. I’ve reproduced the Expectimax solver, and folded in the damage distribution computation into the expectimax solver, which gives a slightly more precise distribution and is a lot cheaper computationally.
Insights from the Solver
Click for the link to the solver. There’s an analysis tab on the right (computer) or bottom (mobile) side that you can use. Click here for a video demo of the solver.
Recently I watched a video by Jorbs discussing a key heuristic in Spire 1 which is that you really need to pick enough non-premium damage cards (e.g. perfected strike or iron wave) in act 1 in order to quickly improve your deck’s damage, even though you don’t want them in your deck later. While this seems like a fundamental principle of Spire, this is unintuitively not as important in Spire 2, and this is ultimately related to the exact way that act 1 boss/elite and lategame enemy design differs between the two games. I thought this was fascinating and I hope solvers can help with the process of finding similarly interesting insights. This post talks about combat ideas, but even combat solvers can also be used to get ideas about card picks/upgrades, relics, potions, etc. (by looking at how they affect average damage taken). This is something poetry_in_shm has started to do with card replacements and additions.
Furthermore, like chess and poker, memorizing specific lines or spots is tedious and low value. Instead, we should use the solver to try to distill general patterns about what to do, and then think more about why those patterns are good. Below I have a flowchart which describes the entire optimal policy assuming you follow it at every step, but I don’t recommend you memorize it, aside from the major ideas. We don’t really care about taking 0.6 less average damage against Nibbit with the starting Ironclad deck, we care about understanding a wide variety of fights, with more cards and a modified deck, and with relics and potions. This analysis is a step towards building intuitions for those generalized cases.
Besides the flowchart, I wanted to highlight a few main play patterns I saw from the solver, but feel free to look more yourself. The Nibbit fight is reasonably easy to play, but it’s interesting to see the analysis for the exact optimal lines. Note in many cases the choices are equivalent (e.g. when deciding bash vs. two strikes) and I pick the choice that makes the rule cleaner.
Tree Depth
The solver assumes you spend all 3 energy and play lethal whenever available. Also, that you don’t waste energy on defends after full blocking. Given this, you only have to make decisions up to turn 7. This is a major reason why it’s computationally tractable to use Expectimax to solve this fight (a few other reasons are that Nibbit has a deterministic move order, you can’t draw cards during your turn, deciding the play order of cards is easy for this deck, and we can filter out all 0-2 energy lines).
Always Full Or Efficient Block
This is inspired by Caleb Gannon’s video on fight analysis and solvers.
Other than playing lethal when available, it’s surprisingly always optimal to full block or efficient block (block as much as possible without overblocking).
Furthermore, on the heavy attack turns, i.e. turns 1, 4, and 7, you should always full block if you don’t have lethal. On turns where the enemy buffs, you trivially full block since the enemy doesn’t attack. Lastly, on turn 5 (10 damage incoming), full block is the same as efficient block. This means you actually want to full block every turn except turn 2, where you need to decide whether you should full or efficient block.
Bash Or No?
Assuming you know how many defends to play based on the above section, and the optimal number of defends is 0 or 1, then you may have a choice between bash or two strikes with your remaining energy. Which is better?
Turn 5 and later, always choose bash. Turn 4, choosing bash is almost always correct. Turns 1-3, bash is often correct, but there are still some cases where you should play two strikes instead.
Unintuitively, there are cases where you play 3 strikes instead of bash strike, i.e. you want 1 damage instead of vulnerable next turn! Letting B = bash, S = strike, D = defend, X = ascender’s bane, then SSS > BS against a 47 HP nibbit when you draw BSSSS on turn 1. There are two cases for the turn 2 draw, if DDDDX (no strike), then 29 vs. 30 enemy HP matters. If you draw strike (SDDDX or SDDDD), then afterwards the enemy is 23 HP (SSS line on turn 1) vs. 21 HP (BS line on turn 1), which has the same value.
If anyone can find simpler patterns or give explanations for why we play bash vs. 2 strikes, or decide full vs. efficient block on T2, I’d be curious to hear. I think these are the only decisions you need to make in the Nibbit fight given the starting deck.
On LLM-Generated Code
I use LLMs here to do the coding (implementation but not ideation), though I believe I could reimplement everything myself (significantly more slowly). LLM coding agents are extremely fast and decently capable implementers, but there's often a tradeoff between human supervision and correctness. It's good practice to describe how much supervision was given and the extent of the supervisor's domain knowledge. You should already be careful about lightly-vetted human code, and even more so for lightly-vetted LLM code.- Solver: Typically I like to read and understand all the generated code, but here, I read only small pieces of generated code, relying mainly on output logs of computed state values, node counts, etc. to verify the code's correctness. After many rounds of iteration/debugging, the EV and damage distribution matches poetry_in_shm's prior work and my understanding of the nibbit fight and expectimax, so it's reasonably likely the code is either correct or contains only minor errors.
- Visualizations (distribution, flowchart, solver visualization): the style is visibly LLM-like, unfortunately. However, I took care to iterate on the actual presented data, the style, and the descriptions.
- Writing: I didn't use LLMs at any point and strongly prefer writing completely without LLMs (problems with style, emphasis, and correctness).
In the Future
Solvers (superhuman but not perfect) have been built for chess, go, poker, etc. I’d like to make progress on a strong solver for Spire. We’re currently very far away, though there have been few public, long-term projects for Spire solvers.
This starting deck Nibbit solver is just a small taste of what we can achieve. Building good solvers for complex fights with bigger decks, relics, and potions demands scalable techniques like MCTS and AlphaZero instead of Expectimax. I’ve also been working on a learning/data-based policy for playing full runs, though it’s currently very bad and I’ll need to pair it with a proper combat solver. I hope to write about both of these when I’ve made more progress. See you soon :)