Part 8: 99 Moves and Hitting a Sentry Ain't One

Haven't played Slay the Spire? Here's the background - the rules, and why the game is hard to learn.

I still felt search was the way to go. I just needed to get better at debugging it. My go-to until then was an infrastructure for tracing agent play on a given seed. I could then review the logs (or even watch it being replayed in the full game with the GUI) and try to generalize from the errors I'd identified. That doesn't apply to search, which evaluates tens of thousands of positions involving different card play orders, target selection and draw-order estimates.

To debug search, I'd have to learn to ask questions about aggregates. This was illustrated nicely with a failed attempt for subtree dominance pruning. The idea was to save a lot of "leaf" comparisons. Let's say I'm trying to look three turns ahead, evaluating play A. If I can make play A on turn 3, but with better moves leading to it, I need not consider play A at all. More generally, the idea was that if on a certain turn I have a bad play and a better play, every branch from "bad play" should be strictly dominated by an equivalent branch followed by "good play", so I could save potentially hundreds of evaluations.

That made sense to me, but ran into the problem of draw order. Batching already collapsed single-turn plans, so the value for this would need to come from multi-turn. However, when looking ahead multiple turns, one needs to simulate the draw order. We started with "strict" dominance, meaning every line in a branch needed a same-draw line in another branch. It never fired since the draws diverged immediately. Even in the rare case where they didn't diverge, ordinary leaf pruning had already thrown the loser away.
If you loosened it you'd get something that fired a lot more but degraded play quality, since it ended up picking the candidates for which a small number of simulated draws drew better cards.

That was scrapped in favor of fixed-turn lookahead. Instead of going really deep on some promising (according to the "frontier heuristic" - four ratios that tried to express how good the agent was doing in this game state) states and starve others, let's expand for a fixed number from each, since even the most meticulous human experts I've seen don't try to think ahead more than 3 turns at a time during combat. That one showed very modest return (+1.33 on average, improving 7 seeds and degrading another 7), and my gut feeling was there was a big unlock waiting for me to stumble upon it.

So, I asked Claude to actually profile search, to understand where time was being spent (I'd accepted the jitter and the cold-start issues since the finished product would have to speak in human terms, e.g. "how long are you willing to stare at your screen waiting for me to play a card"). It came back with the most boring conclusion available: the super-slow calls that cost a lot of the budget looked exactly like the fast ones, they just had more work to do. We were reasonably optimal when generating what to look at and at evaluating it, so if you had plenty of candidates to evaluate, it just took longer.

While looking at it, Claude pointed out 75% of the search calls "hit the cap". Evaluating a line of play stops when it hits a "terminal state" - either the agent won the fight or it died. In either case, there are no more plays to make. Or, it hits a leaf cap - the same 10,000 put in there, to avoid over-emphasizing some states at the expense of others. Peeking inside the data showed that "terminal states" don't really add much - the overwhelming majority of them was just dying. So, search would normally run until it hit the cap. The problem was that the cap limited us unevenly: "interesting" states with many branches got shallow searched for each branch, whereas states with less potential continuations were explored deeply.

But 10,000 states is a lot, and I was quite surprised simple hallway fights run into it. Digging deeper, it turned out we would first search until hitting our cap, then perform deduplication: fusing together states that were the same. Innocently asking Claude "shouldn't it be the opposite? First of all see if you already saw that state, and only count unique states in your budget?" made it happy and reduced our "cap exit" rate from 75% to 0.37%, meaning the majority of time search now could exhaustively find an answer.

This was doubtless the lever I was looking for. Wary of small-seed variance, we evaluated the optimized search on 30 seeds:

	After the whole arc (30 eps)	Before it (20 eps)
Avg floor	28.1	28.4
Median floor	28	24
Wins	0/30	3/20 (15%)

The reason for the difference in seed-set size and identity is that those 20 seed numbers simply weren't logged anywhere. Going forward Claude was instructed to log seed sets and re-use them, but for now we had to make do with the shape of the result, since I wasn't going to spend 6 more hours just for the sake of rigor. The table shows that we've indeed optimized what we set out to do: search was covering a lot more unique states now in the same amount of allotted time, and performance hasn't moved at all: the confidence interval was about 3 floors, so roughly the magnitude of the difference.

I wanted to see if I can recover the wins and doubled the boss time budget:

	Boss 10s	Boss 5s	Δ
Avg floor	26.6	28.1	−1.43
Median floor	22	28	−6
Wins	1/30	0/30	+1
Wall time	~7.4h	~6h	+24%
Per-decision time	2.14s	1.66s	+29%

This time this is on the same set of 30 seeds. We can see search indeed could and did use more time on average per decision with the bigger budget, and even won once. So why median-floor regression? Is this another tedious "a functional bug invalidated the whole thing" post?

Tied:      21/30
Improved:   4/30  — +5, +18, +3, +10      (mean +9.0)
Regressed:  5/30  — −1, −34, −5, −34, −5  (mean −15.8)

What are -34s? That's dying on floor 16 instead of 50. Which would mean we did worse against the act-1 boss when we had more time to consider our plays. The conclusion, at the time, was something called The Optimizer's Curse. Searching more options is only better if you evaluate your options correctly. Otherwise, you just get more chances to get things wrong. Our simple four-number heuristic was used to break ties between situations evaluated the same. It might be that it's best to just not find those situations so as not to have to call it.

However. Those conclusions were based on a time budget, which we already know to be pretty noisy. So, we took the time and re-evaluated using the deterministic lever we had, which was a leaf budget - how many different ending states search may look at before committing to a play. We derived the number (12,400) from the median amount of leaves encountered when limited to 2s/5s. Then ran the same seeds, once using 12400 and once with 24800. Consistent with time-budget results, we got very similar overall performance (1 win out of 30 and a 0.5 better average floor). Drilling down:

Paired outcome	Seeds
Tied	21
Improved	5
Regressed	4
Sign test on the 9 movers	5/4, two-sided p = 1.000

In simple words, doubling the search budget helped as often as it harmed - pointing to search quality so low that draw RNG dominates it. Looking into one particular regression, where less time did better, showed that on the first divergent floor, more budget did better: the bigger budget allowed it to find a winning line shallow search didn't uncover, resulting in 3 HP more at the end of the fight. This was in vain though as later playing versus Lagavulin the shallower search lucked into a line that eked a win after taking 50 damage rather than dying like the deeper search.

The delta between "good play" and what we had can also be illustrated with some numbers. Since starting this project, I've played almost 150 games of silent A0 (the reason for which will be explained next week). An average run takes me about an hour. The agent took 67 minutes to make six decisions in the triple sentries fight, which is in act 1. A neuron can fire every 1-2 ms, so the human brain runs at about 500 Hz. The agent runs on silicon whose clock is measured in GHz. That means that there are still large benefits to be had, and that improving search efficiency or breadth is not the place to look, at least until we improve how we evaluate those potential lines.

I'd set out to understand the mind of an agent that considers 12,000 lines before making a single move, which meant training myself to stop looking at individual plays. The conclusion was that we need something that doesn't consider all those lines before deciding to shiv the outer sentry with lower HP. In other words, for the agent to improve, we'd need to find a way to make it think slightly more like a human.