Haven't played Slay the Spire? Here's the background - the rules, and why the game is hard to learn.
We finally had an agent that could beat the game. After a long time wading in the act 1 waters, combining search and dominance pruning for combats, the value model for card picks and behavioral cloning from bottled_ai for events and pathing created something that could play the game well enough to occasionally win. Why was I celebrating a 6% win-rate agent when bottled_ai already had 26% (and published 40% on A20)? Because my agent could, at least in theory, adapt. bottled_ai was forcing a specific strategy, and had its relic, potion and card evaluation tightly coupled to that. When I grafted a different card-picking engine onto it, it would pick cards it would then never play, turning them into curses. My agent was a lot weaker, but it could in theory bootstrap its way towards the goal (which was now matching my 100% win-rate when playing A0, the easiest difficulty of the game).
What remained was tuning. Even simple encounters in StS take a while to fully solve, and some encounters (such as the act 3 Darklings fight) can theoretically go on forever. So, limiting the search budget was a must, and the questions were "limit to what" and "how to best use it".
The scheme we started with took a page from chess engines. The way to limit their strength was historically to cap their thinking time per move. I wanted to ultimately apply more concepts from chess engines, such as caching searched positions and adaptively managing the time budget so more challenging situations got more thinking time. That was hard, so instead I decided every move in combat would get 1, 2 or 3 seconds of thinking time, and every move in a boss combat would be 3, 5 or 10 - the rationale being that bosses have a higher health pool, and thus take more turns to defeat, and thus search needs to go deeper which takes longer.
The second issue was also tricky. Imagine all possible "first moves", and then from each there's "potential subsequent moves" and keep going. You should end up with a mental image of a broadening network of moves. Even when accounting for the aforementioned dominance pruning, ruling out lines like "end turn early for no perceivable gain", the number of options is staggering.
With a limited time budget, you could do a "depth first" (up to a maximum depth) which is exploring a few options but for multiple turns, or "breadth first" which would consider more options but consider each less deeply. Finally, you can pick a couple of random options and go deep in each - which is my layman's view of "MCTS", the technique notably used in DeepMind's chess engine, AlphaZero.
A quick 30-episode eval showed no clear benefit to MCTS over BFS with a matched budget:
| Config | Avg floor | Wins | Time/ep |
|---|---|---|---|
| BFS 2s/5s | 28.0 | 1/30 | ~10.5 min |
| MCTS 2s/5s | 27.8 | 3/30 | ~13 min |
So I focused on BFS, which is what bottled_ai also did. Now it was time to calibrate the budget. The more time I'd give the agent, the slower it would play, so the slower it could self-improve. Conversely, the better it's going to play - up to a point. At some point, the marginal gain from adding another second is going to be low enough to not be worth the trouble. I checked what different budgets get me on five seeds:
| Budget | Avg floor |
|---|---|
| 3s/10s | 24.0 |
| 2s/5s | 28.6 |
| 1s/3s | 23.0 |
Sharp-eyed readers may notice the "returns" have indeed diminished considerably: longer thinking time translated to worse quality of play. This looked like a bug, so I wanted to reproduce it. Rerunning the 3s/10s to capture "lines of thought" to debug them got an average floor of 20.6.
Hmm.
I was willing to concede there would be some run to run variability when wall-clocks are involved - after all, I was using my computer while the agent was playing, so we were competing for CPU. However, even when adopting the practice of letting the agent run alone, variance became disruptive to experimentation. I wanted to add "batching": consolidating sequences of plays that end up being the same, such as playing a strike followed by defend and vice-versa. Move batching looked good, gaining 4.6 floors on a matched budget, but running the same set of seeds twice with it showed an average of 28.2 in one run and 20.6 in another. One seed regressed from reaching floor 50 to dying to the act 1 boss, showing that "average floor over 5 seeds" is a poor metric in general, in this case due to high run-to-run variance.
To properly root cause something random like that, we had to do two things: find a mechanism to explain it (it takes a lot to believe noise in the order of milliseconds could have an impact over something running for 200x longer than that) and show a causal relationship (e.g. when we neutralize the mechanism, the behavior disappears). The second one is often neglected, but it's critical, and here's why.
Without getting too technical, the JVM would cache and/or optimize the JITting of the game functions. That meant that after warming it up by running for a while, the game would become much faster, and you'd get a lot more bang for your buck - more moves searched for the same amount of seconds. That was a clean explanation, a lot more convincing than jitter. It was also wrong.
Despite the theory and supporting evidence (such as a certain seed losing over and over again then suddenly winning over and over again), when actually counting search calls the gap between "warm" and "cold" was negligible - 1864 versus 1857. A dedicated experiment compared how fast search ran from a given position on a cold versus warmed-up JVM, and the difference was within the noise margin. The first search took 5% longer than subsequent ones, a difference that evaporated within five seconds. Given that the regression happened after over 15 minutes, it's clear the VM temperature had little to do with it.
Wall-clock jitter definitely had an impact. Limiting the search budget based on number of iterations rather than wall-clock showed consistent performance - in fact, it yielded exactly identical games played by the agent. However, that caused another set of problems.
A noise-free, consistent iteration budget is not correlated to the real world. Concretely, I wanted to evaluate the impact of batching. When I was using wall-clock, batching sped up search by eliminating some options, so in a world without JVMs I could expect to see some benefit. Once we moved to an iteration budget, we ended up with simply searching different parts of the space. This isn't due to some deep algorithmic reason - the implementation of batching just changed the order in which nodes were traversed, so it was impossible to align the two. Indeed, I've just set batching to "on" reasoning it's better in theory without being able to practically validate it - not the first time I made an arbitrary call in this project, but the first time I did so knowingly.
Truth be told, I hated writing this post. At that stage in the project, there were many moving parts. The scale of the search algorithm was too large to manually verify and experimentation was slow. Looking back at the work I did five months ago, I detect clear signs of brain rot from over-reliance on Claude. For example, the experiment that ruled out the VM took an hour to design and run, and I only thought of it when researching for this post.
In my defense, learning how to use coding agents effectively was a part of the reason I was doing this to begin with, I just didn't expect any of the lessons to be "don't overuse them or your critical thinking will shut down due to overdose of lengthy, plausible and wrong explanations of phenomena". Luckily, I did manage to redeem myself in the search work. More on that next week.
Top comments (0)