Haven't played Slay the Spire? Here's the background - the rules, and why the game is hard to learn.
Our agent had peaked. We suspected the exploration trap, but another issue emerged from my conversations with Claude. Since the methods it suggested to root-cause problems led us nowhere, I began telling it how I play and asking it to translate it to data science terms. The discussion of the act 1 Gremlin Gang encounter led it to conclude our approach was inherently flawed.
The encounter includes 4 enemies drawn from a pool of 5, with up to 2 repeats allowed. Every enemy type poses a certain challenge: The poorly-named Sneaky Gremlin simply hits you every turn. Mad Gremlin doesn't hit as hard, but gets stronger the more often you hit it. The Shield Gremlin doesn't deal any damage unless it's the last one standing, but it shields one of the other gremlins at random. Fat Gremlin doesn't hit very hard but it weakens you, making it more difficult to eliminate gremlins. Finally, the Gremlin Wizard doesn't do anything for two turns, then hits you very hard on the third.
When encountering the gang, a human evaluates based on its composition. If a Wizard is in the mix, you plan to kill it within 3 turns. That often means you target enemies that get in the way of that: the Fat and Shield gremlins. This, in turn, dictates letting a Sneaky one hit you once or twice, since that would minimize overall damage. If there's no Wizard, you'd be in no rush and usually prioritize the Sneaky one first, since it's easy to block Fat and Mad gremlins while building up your strength.
In data science terms, the Gremlin Gang encounter requires multi-turn planning. To make things more complex, the plan can also depend on your deck. You might have access to powerful damage-mitigating cards or relics, which would mean you ignore the Wizard. Self play, by a network that looks at the game state and the draw pile and chooses card plays one by one, will not uncover these, due to the credit assignment problem. The way to play this encounter well would be to look ahead several turns, applying different lines of play, and calculating which plan gives the best expected outcome. In other words, we needed to rely on search.
Fortunately, we had one ready. AlphaStS, designed to serve as a foundation to AlphaZero-style solvers for StS, included what we needed: cloning a game state, simulating ahead and rolling back, and supported all Silent cards and StS enemies and encounters.
The question was how to use it. If you can simulate a fight all the way to the end multiple times, using search is pretty easy: just take the line that has the best average outcome, or the one where the worst case is the least bad. However, due to draw RNG, it's not really feasible to look ahead enough turns in most fights. That meant we needed a source of truth that takes a game state (resulting from "playing" current combat a couple of turns ahead) and assigns it a numerical score. Thus was born the state-evaluation heuristic.
The heuristic tried to lump everything together to explain how good a situation was. Winning is great, so +1000. HP is good, better add that. Let's also add poison and enemy debuffs while we're at it, but take away points for Nob having strength, that's bad for us, as is waking Lagavulin up prematurely. To make everything more scientific, scale block by 1.5x and assume we deal 12 damage per turn regardless of deck composition. This hodge-podge of rules, constants and weights was meant to be a placeholder that will be refined later in training.
The architecture became "look ahead until you hit your budget. If you find a no-HP-loss win, go for it. Otherwise, pick the line which leads to the best heuristic score, then re-evaluate next turn". It seemed pretty smart to me, despite the placeholder heuristic, which is why it was so disappointing that it did poorly.
Our basis for comparison was a port of bottled_ai into our environment. bottled_ai uses a simple BFS search capped at 11,000 states, and uses a hand-crafted heuristic to rank between states: being alive is better than being dead, killing an enemy is better than damaging another enemy, and so on. The decision is hierarchical: there are 50 rules, if the first one doesn't apply (e.g. you're alive in both lines) you move to the next. We capped our own search to 10,000 states1 to make the comparison fair.
Bottled_ai reached an average floor of 34.0 and beat the game 26% of the time. Our search never won and reached an average floor of 18.4.
Looking into the gap in performance, our search seemed hell-bent on attacking. Since by this point I had PTSD from the block bug, it triggered another fidelity effort, to ensure our headless game and AlphaStS behave the same. The class of bugs was different now: AlphaStS was oriented at ascension 20, the hardest difficulty of the game. This made the simulation environment the agent saw much more dangerous than the game they played, so the lines it chose performed worse in the easier game. Overall, we spent another two weeks and 150 commits aligning the two.
It helped to some degree, but not enough:
| Pre-fix | Post-fix | Expert BFS | |
|---|---|---|---|
| Avg floor | 18.4 | 19.3 | 34.0 |
| Wins | 0% | 0% | 26% |
| Speed | 237 steps/s | 215 steps/s | 15 steps/s |
We had to go deeper. The problem could be with the search: it could be reaching worse states than you get by using BFS. It could be the heuristic: it ranks the states it reaches wrong and picks bad ones. Claude kept claiming the reason was architectural in nature: bottled_ai commits to full-turn plans whereas our search picked a single card play then re-evaluated. I held my ground that the latter dominates the former, strategically. However, it meant we couldn't graft our heuristics onto bottled_ai, so instead we compared bottled_ai against our search with different heuristics. Specifically, the heuristic I built, one that was trained on bottled_ai's to mimic it, and lifting bottled_ai's heuristic completely and just using it despite how slow it was.
The results were useful, but dishearteningly so:
| Config | Avg floor | Wins | Speed |
|---|---|---|---|
| Expert BFS (bottled_ai) | 34.0 | 26% | 15 steps/s |
| AlphaStS + bottled_ai comparator | 17.1 | 1% | 27 steps/s |
| AlphaStS + handcrafted evaluator | 18.4 | 0% | 237 steps/s |
| AlphaStS + learned evaluator | 16.8 | 0% | 147 steps/s |
To me, this strongly suggested the core problem was the search. Peeking inside AlphaStS revealed the disappointing answer: at some point, to speed the work up, Claude injected a 512 state-cap on search breadth. That re-introduced the exploration problem, since the search could cover only a tiny subset of the space, a subset it was locked into by heuristics that had no chance to get refined.
I was, of course, right to push back against the cap I hadn't realized got added. However, it got added for a reason: search was unrealistically slow without it. This surprised me, because when I play a fight, I really only consider 2-3 lines at a time, so how can the agent even find 10,000 different plays to consider?
Trying to answer that question led to the next big unblock: dominance pruning.
The reason I only consider a few plays is that some plays are just inherently idiotic: if I have spare energy and am being attacked, I block2. I don't evaluate "what would happen if I took this damage? Would this fight be better or worse?" because I know it's worse. In game-theory terms, "blocking the damage" dominates "taking the damage" all other things being equal. However, I do consider "do I spend my last energy pushing more damage or avoiding chip damage" - those two lines don't have clear dominance.
Dominance pruning was extracting a large vector representing a game state, and defining rules allowing classification of one as strictly inferior. In practice, it eliminated 90-94% of the game states that were being considered earlier: a 10x speedup just by helping the model not consider silly plays.
This led to another idea to reflect how I play. Instead of using a heuristic to translate "game state" into a number and focus on game states with high numbers, focus on states that have a high number of surviving descendants. With pruning, these translate into "more options", which intuitively felt right.
I also added a much simpler heuristic, just for tie-breaking between states that have been equally-ranked.
raw = (player_hp / max_hp)
- (total_enemy_hp / total_enemy_max_hp)
+ (total_poison / total_enemy_max_hp)
+ min(block, incoming_dmg) / max_hp
This one still considers the big four: my HP, my effective block, enemy HP, and poison.
| Config | Avg floor | Wins | Budget per decision |
|---|---|---|---|
| Handcrafted evaluator | 19.3 | 0% | 500ms |
| Handcrafted evaluator, bigger budget | 24.0 | 0% | 5s hallway / 20s boss |
| Dominance-pruned direct search | 28.7 | 2/30 (6.7%) | 5s hallway / 20s boss |
Looking back, I wish I'd decomposed the different ideas - it seems reasonable to say that just dominance pruning is akin to giving a 10x time budget, so let's compare dominance pruning that uses the existing heuristic at 0.5 s with the old search at 5s. However, at the time I hadn't planned to write a retrospective and was more enamored with finally moving the needle than I was concerned about being able to do credit attribution myself.
Instead, now that I was reasonably convinced search sees enough diverse game states and enough combat outcomes, we trained a heuristic. All previous heuristics were either hand-crafted, or attempted to distill a 50-deep hierarchical decision heuristic. We played 30 games, resulting in a 89K sample training set, and trained a series of MLPs (638->256->128->1) to evaluate game score.
The results were amazing. Testing on 5 seeds with a 3s/10s budget reached an average floor of 31.2 - nearly as good as bottled_ai, but running much faster to allow further improvement by self-play, and better than our best heuristic at 28.7 despite using a smaller search budget.
Unfortunately, when testing 30 games at 5s/20s, our advantage disappeared. We averaged 27.2 while the heuristic was stable at 28.8. What we really got was just a faster way to reach the same result, and we'd been misled by a small sample size. Good thing THAT was going to be the only time this happened on this project.
1 - re-reading this now, I have no idea why 10,000 instead of 11,000
2 - like many "StS" considerations I mention, this one is also simplified. In reality I could have Meat on the Bone or expecting to fight Hexaghost, which in both cases might make me take damage intentionally to manipulate my HP. StS really is a fascinating game.
Top comments (0)