Overview

On this put up, I’ll checklist a collaborative effort that proved that unwinnable Kill the Spire seeds exist. This project is joint work with gamerpuppy and ForgottenArbiter and is in conserving with the different attempts which had been made to prove unwinnability for seeds in Kill the Spire.

Previous growth

In a weblog put up on unwinnable seeds in Kill the Spire, ForgottenArbiter outlined an intensive intention to the self-discipline of discovering an unwinnable and shared a branch of SeedSearch which appears for these seeds. We steal unwinnable to checklist any hotfoot of Kill the Spire that can now not be won by any sequence of decisions allowed by the scandalous recreation (ignoring system defects). Since the random quantity period of Spire is determined uniquely by the hotfoot seed, the player can replay a seed, alter their card play utter (and thus the halt outcomes of later deck shuffles), and compose unintuitive decisions, to maximize health and different sources for the length of the hotfoot.

By analyzing optimal cases of card blueprint and deck shuffling, Arbiter proved that Restful’s starting deck loses in opposition to Lagavulin on Ascension (18+). The argument completely ignores trouble dealt to the player and focuses entirely on the lose condition: after (3) of Lagavulin’s debuff turns ((-2) dexterity and (-2) energy), the player can now now not deal trouble. If the player reaches a fight in opposition to Lagavulin without suddenly or ultimately improving the difficulty of their starter deck, they lose the hotfoot. With this in thoughts, he formulated the following criteria when searching to search out unwinnable seeds.

1. Play as Restful on Ascension (18) or elevated.
2. Compelled Lagavulin elite fight on ground (6), with out a retail outlets or relaxation sites on the first five floors.
3. No Neow bonuses, potion drops, or card rewards which succor the player deal trouble to Lagavulin.

The “most unwinnable” seed that resulted from this search is 3LWVGX7BL which has the following properties:

1. Neow Alternatives: make stronger a card, (100)g, take dangle of (2) playing cards (steal (15) trouble), swap for Cursed Key
2. Card and potions earlier than ground (6):
   • {Bane, Outmaneuver, Deflect}
   • {Outmaneuver, Accuracy, Footwork} and Essence of Metal
   • {Deflect, Outmaneuver, Setup} and Fruit Juice
   • {Dodge and Roll, Accuracy, Tactician}
3. Lagavulin is the first elite.
4. Compelled burning elite (with the metallicizing buff) on ground (6) with out a retail outlets or relaxation sites beforehand.
5. ?-nodes are pointless rather than for a presumably priceless card rework (Adrenaline, and loads others).

It’s a ways likely that this seed is unwinnable. Nonetheless, it goes to now not be dominated out as winnable without detailed knowledge about the bound RNG of the fight in opposition to Lagavulin. In Kill the Spire, the random quantity generator which controls bound is instantiated at the begin of every fight, and it is dependent most efficient on the seed and the bottom quantity. By taking half in playing cards in a agreeable utter on the first cycle by the deck, the player can manipulate the utter wherein playing cards are drawn on later cycles.

As an illustration, it is attainable to achieve Lagavulin on this seed with a deck which pulls as follows:

• Strike+, Bane+, Protect, Strike, Survivor, Protect, Protect,
• Footwork, Neutralize, Ascender’s Bane, Protect, Strike,
• Protect, Strike, Strike, Outmaneuver, bound…

By taking half in playing cards in a agreeable utter, the player controls the utter of playing cards of their blueprint pile, and thus can manipulate how they’re shuffled in the next deck cycle. ForgottenArbiter has confirmed that with this deck and ideally agreeable shuffling on future turns, the player is able to deal precisely (113) trouble to Lagavulin (which starts with (112) HP) earlier than the debuffs prick all trouble to (0). Whether this bound might maybe well well moreover merely also be realized by the recreation’s RNG has now not been sure. With entry to mid-turn deck shuffling from Adrenaline as properly, this becomes a ways more sophisticated to analyze.

The hunt for an abomination: 18ISL35FYK4

The aim of my search modified into as soon as to search out a seed so irascible that the proof of unwinnability can match on an index card (e.g., it requires no fight simulation).

As an integer, this seed is (3,431,382,150,268,629) or (sim 3.4) quadrillion, but we compose no claim that this is the first seed (as a undeniable integer) which is unwinnable. This seed has the following properties:

1. Neow most efficient presents (1) removal, gold, or a swap into Cursed Key.
2. The scheme forces a burning elite fight (max HP Lagavulin) on ground (6) with out a retail outlets or relaxation sites beforehand.
3. The player encounters (2) or (3) combats and the ?-nodes are basically unhelpful.
4. The playing cards offered attain now ultimately add any trouble and are blueprint-neutral.

For now, we can make clear the computational effort that led to its discovery. Scroll down extra to perceive the proof of unwinnability.

BCE (Forward of CUDA Era)

I first bought fascinated about this search in early January 2022 now not lengthy after discovering and routing an Ascension 20 Coronary heart snipe seed. I had accomplished (with system defects and some very careful RNG manipulation) the first turn-(1) Coronary heart abolish for the explanation that boot worm exploited here by ForgottenArbiter modified into as soon as patched. For it, I worn gamerpuppy’s sts_seed_search, which emulates important seed hunting functions at a low level in C++. With this library, I am ready to specify which RNG calculations I are searching to compose, and the intention in which seeds are filtered. For speedrun-linked searches in the past, I even respect predominantly worn ForgottenArbiter’s SeedSearch mod, which runs by the backend of the scandalous recreation and comes with a straightforward to spend list of seed criteria.

I filtered in conserving with the bottom (0) rewards from Neow, rewards of (5) (or generally (4)) combats, and most efficient filtered for maps with a forced ground (6) elite and no retail outlets or relaxation sites beforehand. The filter utter has a massive affect on the rate at which seeds are examined.
Bid now we respect two filters (mathcal{F},mathcal{G}) which could be fair in a suitable probabilistic sense. If (s,t) are correct estimates for the cases expend checking out a seed in opposition to (mathcal{F},mathcal{G}), and (p,q) are the potentialities of a seed passing the filters, respectively, then the anticipated time to look at a seed in opposition to (mathcal{F}), after which (mathcal{G}) is

(mathbb{E}[
text{time spend testing a seed} |
text{ testing } mathcal{F}
text{ then } mathcal{G}
]
=s + pt.)

Reversing the filter utter exchanges (s,t) and (p,q) in this expression. In utter to in the prick worth of the frequent time spent checking out every seed, the optimal filter utter might maybe well well moreover merely also be came upon by the following commentary:

These fractional expressions might maybe well well moreover merely also be regarded as measures of the efficiency of the filters (mathcal{F}) and (mathcal{G}), below a minor concentration hypothesis. When (p) is puny, the denominator term is arbitrarily end to (1) (as is the case with scheme filtering), and most efficient the time spent on the filter issues. Following some experiments, we advance at the following utter on the filters:

1. (mathcal{N}:) the bottom (0) rewards from Neow are “unhelpful”.
2. (mathcal{C}(5):) the first (5) card rewards attain now not adequately augment Restful’s trouble output.
3. (mathcal{P}(5):) the potions offered from the first (5) combats also attain now not augment trouble output.
4. (mathcal{E}:) Lagavulin is the first elite fought.
5. (mathcal{M}:) no retail outlets or relaxation sites seem earlier than ground (6), and ground (6) most efficient has elite fights.

For loads of concerns equivalent to ?-nodes outcomes and boss relic swaps, we print out some knowledge on every seed that passes filters (1) by (5), and test the whole lot else manually, or with Arbiter’s SeedSearch. Adjusting parameters repeatedly, the toughest seed I came upon with this intention modified into as soon as 37UKXMQJQ which meets the above properties. More precisely:

1. (mathcal{N}): (1) removal, (100)g, and (250)g for some max HP, or swap into Dusky Superstar.
2. (mathcal{C}(5)):
   • {Deflect, Ready, Outmaneuver},
   • {Outmaneuver, Dodge and Roll, Blur},
   • {Backflip, Listen, Dodge and Roll},
   • {Listen, Burst, Backflip}, and
   • {Piercing Yowl, Gash, Blade Dance}.
3. (mathcal{P}(5)): (1) skill potion from the (5)-th fight (continuously {Calculated Gamble, Tactician, Setup}).
4. (mathcal{E}) and (mathcal{M}) are met, and one in all the bottom (6) elites is the “burning” elite.
5. ?-nodes: Winged Statue ((-7) HP for (1) removal), Scrap Ooze ((5) or (6) hits for Tea Keep of residing), Wheel Gremlin (continuously presents (1) removal), and fight.

Whereas I am optimistic that this seed is unwinnable, proving it can require fully simulating loads of combats.

It turned sure to me that in utter to search out a correct seed, one which does now not require brute force calculations and loads more and loads casework, I’d respect to also force the player to fight a buffed Lagavulin on ground (6), as is the case with Arbiter’s seed. In the initiating, the scheme constraint (mathcal{M}) permits most efficient (1) in (sim 15,000) seeds by. For a forced burning elite with out a retail outlets or relaxation sites beforehand (name this filter (mathcal{B})), most efficient (1) in every (sim 225,000) seeds passes by. This search ran by the first (10) trillions seeds in one to 2 weeks of frequent breaks and adjustments to seem parameters,. It modified into as soon as time for a brand fresh intention.

the GPU seed farm

After loads of priceless conversations with gamerpuppy, they despatched me a model of the CUDA code worn for discovering unbelievable Pandora’s Box boss swaps. In temporary, CUDA presents the programmer voice entry to the GPU’s digital instruction swear and parallel computational functionality, bearing in mind simultaneous computation with tens of thousands of threads, if ran on a swear of the art GPU.

To optimize performance, we feed in the finest constraints into CUDA: (mathcal{N}) and (mathcal{C}(5)) and steal particular care to in the prick worth of slowdown caused by branching. Any seeds that hurry these filters rating written to a textual vow file which will later be fed by the C++ program for extra diagnosis.

To tag the energy of the card reward filter, steal into legend the following swear of Restful playing cards:

Other than for Distraction, that might maybe well give a poison or shiv-generating card, these playing cards can now not be worn to deal voice trouble to Lagavulin or to be sure blueprint. For simplicity, we can approximate the likelihood that a card reward lies in this swear as (1/100). With (5) card rewards potentially attainable earlier than ground (6), roughly (1) in every (10) billion seeds can respect (5) consecutive spoiled card rewards. Even with loads of optimizations, the rate at which seeds handed (mathcal{N}) and (mathcal{C}(5)) modified into as soon as insufficient to search out sufficient seeds passing the last filters (mathcal{P}(5)), (mathcal{E}), and most importantly, (mathcal{B}).

A final tradeoff

As a running hypothesis, I had been planning for the worst case self-discipline where the player has entry the maximum series of combats. Having viewed a whole bunch of (mathcal{B}) maps, I knew that an attractive series of them had most efficient (4)-fight paths. If we would relax the constraint on card rewards, many more seeds would be printed to file from the CUDA code, and likely sufficient of those seeds would then hurry the last (3) filters.

Checking the first (100) billion seeds, I made a discovery. As many as a Third of all (mathcal{B})-maps did now not respect (5)-fight paths, and strikingly, (~2%) of all (mathcal{B}) maps had most efficient (3) combats earlier than the burning elite! Altogether, this fresh constraint, name it (mathcal{B}(3)), is glad by (1) in every (~9.17) million seeds, in accordance to the pattern. Whereas this might maybe well well moreover merely now not seem respect loads, changing the persona of the filters in this intention successfully swaps two (1)-in-(100) filters for a single (1)-in-(50) filter. It also reduces a massive deal of branching in the CUDA code by reducing down the scope of the first loop in the card reward filter.

After stress-free the card constraints from (5) rewards to (3) (that is, replace (mathcal{C}(5)) with (mathcal{C}(3))), the CUDA code returned a batch of about (234) million seeds between (1) quadrillion and (6.6) quadrillion seeds, after most efficient (16) hours of runtime on a most modern GPU. Four seeds MC81APL0TK, UL8LMGQV64, 1778H44QQQP, 18ISL35FYK4 emerged after being examined in opposition to properties (mathcal{N}, mathcal{C}(3), mathcal{P}(3), mathcal{E},) and (mathcal{B}(3)), with most efficient the closing one having a suitably unhelpul boss relic swap and match pool.

At closing, we’re prepared to prove this seed is unwinnable.

Proof of unwinnability

Let (mathcal{BS} :=3,431,382,150,268,629) (also identified as 18ISL35FYK4}. We list some priceless info about this seed.

Fact A. As Restful on Ascension (18) or elevated with, a typical hotfoot with seed (mathcal{BS}) manually entered has the following properties.

1. Neow presents (1) card removal, gold, or a boss swap into Cursed Key.
2. Forward of ground (6), the finest ?-node outcomes are World of Goop, Golden Idol, and The Cleric, in this utter.
3. The first (3) combats rewards earlier than Lagavulin are:
   • {Ready, Dodge and Roll, Escape Notion}, gold, and no potion.
   • {Escape Notion, Outmaneuver, Ready}, gold, and no potion.
   • {Ready, Dodge and Roll, Footwork}, gold, and a Block Potion.
4. Each course to ground (6) encounters both (2) combats and (3) ?-nodes, or (3) combats and (2) ?-nodes.
5. The most efficient scheme node on ground (6) is an elite fight aganist Lagavulin with (144) HP.

The following argument modified into as soon as suggested to me by Arbiter. To prove that (mathcal{BS}) is unwinnable, we divide the fight in accordance to the cases at which a deck bound happens. In between shuffles, the player can play at most (5) Strikes and at most (1) Neutralize, with trouble optimized by taking half in the Strikes as early as attainable. On this argument, we ignore the player’s health, the energy price of the player’s playing cards, and the block on Lagavulin earlier than it is woke up.

For consolation, let (okay) be the mixed series of copies of Escape Notion and Ready in the player’s deck. We swear and prove the following claims about fight on ground (6).

Boom B.0. The first deck bound happens at the begin of turn (1) and the next deck bound happens, at the earliest, at the begin of turn (2).

Since Restful’s deck begins with (12) total playing cards and Ascender’s Bane, and by ground (6), most efficient (2) card removals are attainable, the player’s deck has at the least (11+okay) playing cards. Moreover, noting the relics accessible, at most (7+okay) playing cards are drawn on turn (1). So no different bound happens for the length of turn (1), finishing up the proof.

Boom B.1. If the player shuffles the deck at the begin of turn (t) where (t geq 2), then the next deck bound happens, at the earliest, at the begin of turn (t+2).

Noting that by ground (6), at most (2) removals are attainable, and since Ascender’s Bane might maybe well well moreover merely also be exhausted, it follows that mixed series of playing cards in the player’s hand, discard pile, and blueprint pile is continuously least (10 + okay). Since (t geq 2), turn (t) begins with the player drawing (5) playing cards. Moreover, this ability that of the miniature card pool and relics, and the accessible potions, no playing cards might maybe well well moreover merely also be carried out to amplify the series of playing cards in-hand. It follows that the player has at most (5) playing cards in-hand factual earlier than the bound at time (t).

Since the player has at most (5) playing cards in-hand at the begin of turn (t), there are at the least (5+okay) playing cards in the blueprint pile. On turns (t) and (t+1), at most (okay) blueprint playing cards (Escape Notion and Ready) might maybe well well moreover merely also be carried out. It follows that the player can now not bound the deck again for the length of turns (t) and (t+1).

Boom B.2. If the player shuffles the deck for the length of turn (t) where (t geq 2) by taking half in playing cards, then the next deck bound happens, at the earliest, for the length of turn (t+2).

As earlier than, prove that the mixed series of playing cards in the player’s hand, discard pile, and blueprint pile is continuously least (10 + okay). Demonstrate also that the player has at most (5) playing cards in-hand factual earlier than this bound, and at the least one in all those playing cards is a blueprint card. It follows that turn (t) ends with one blueprint card and at most (5) non-blueprint playing cards in the discard pile. This implies that the blueprint pile contains at the least (10-5=5) non-blueprint playing cards at the halt of turn (t). So no different bound happens for the length of turns (t) and (t+1), as desired.

Boom C. Bid the player shuffles the deck on turn (t). Within the time after this bound, but earlier than the next bound, the player’s trouble output is bounded above by the difficulty handled the following sequence of card performs:

• play (5) Strikes and (1) Neutralize on turn (t) if (t=1), and
• play (5) Strikes on turn (t) and (1) Neutralize on turn (t+1).

Indeed, for the length of this time, every trouble card (at most (5) Strikes and (1) Neutralize) enters the player’s hand, and thus might maybe well well moreover merely also be carried out, at most as soon as. Ranging from turn (2) or elevated, at most (5) of those playing cards might maybe well well moreover merely also be carried out on a given turn, and taking half in the Strikes on the earliest attainable turn deals more trouble.

To whole the proof, steal into legend the sequence (1=t(1)leq t(2)leq cdots) of turns on which a bound happens. By Claims B.0, B.1, and B.2, it follows that (t(2)geq 2) and (t(i) geq t(i-1) + 2) for all (i geq 3) such that (t(i)) is printed. By Boom C, the maximum trouble dealt to Lagavulin earlier than the Third debuff is bounded above by the difficulty dealt by (1) taking half in (5) Strikes and (1) Neutralize on the “wake-up” turn, and (2) alternatingly on future turns taking half in (5) Strikes on even turns and (1) Neutralize on atypical turns. So the difficulty dealt to Lagavulin earlier than the (3)-rd debuff is utilized is

.

Since Lagavulin’s total HP equals (144), (mathcal{BS}) is unwinnable as Restful on Ascension (18) or elevated.

Future work

With more extremely efficient seedsearching tools at our disposal, we return to some questions draw to be by Arbiter in his weblog on unwinnable seeds, and some different complications. Within the event you can well maybe be drawn to joining the hunt, steal a watch at the CUDA code besides to sts_seed_search.

What if the player will get Neow’s Lament?

As a running assumption for the length of this project, we assumed that the unwinnable seed had to be manually entered. A manually entered seed continuously presents the player (4) choices from Neow on ground (0). If as a change the player had been encountered our unwinnable seed 18ISL35FYK4 by accident while not having reached the Act I boss on their earlier hotfoot, they would be offered Neow’s Lament (or some extra max HP). Our seed 18ISL35FYK4 would unquestionably be winnable since the burning elite might maybe well well presumably be killing the spend of the (3)-rd stack of Neow’s Lament.

To work around this, we would hotfoot the inquire of a protracted time to search out many seeds equivalent to 18ISL35FYK4, and get dangle of out one which can now not defend a ways from (3) combats earlier than the fight with Lagavulin (whether this is this ability that of the seeded RNG of ?-node outcomes or the scheme structure. As an illustration, we would get dangle of the sort of seed for which the ?-node outcomes are match, match, fight, fight. Likely this search would now not steal more than a week on a swear of the art Nvidia GPU (for compatibility with CUDA).

What about different characters?

As Arbiter argued, it is probably going that unwinnable seeds for Ironclad and Defect exist. Nonetheless, it is also likely that a proof of unwinnability would involve the bound RNG of fights, and likely a full fight simulation to look at sequences of mid-fight decisions for survivability. Other characters’ starter decks can deal trouble to Lagavulin after the (3)-rd turn of debuffing, and exhaustively simulating more than (10) turns is probably going impractical. I imagine that the following search criteria tend to yield an unwinnable Ironclad seed:

1. (mathcal{N}): rework (1) (receive an unhelpful card), (100)g, (250)g for any downside, and a depraved or neutral boss relic swap (Dusky Superstar, Sacred Bark, and loads others)
2. (mathcal{C}(3)): most efficient offered blueprint-neutral skill playing cards and unhelpful powers
3. (mathcal{P}(3)): no potions
4. (mathcal{E}): first elite is Gremlin Nob
5. (mathcal{B}(3)): no retail outlets or relaxation sites earlier than a ground (6) burning elite

In contrast to Lagavulin, Gremlin Nob…

• deals more trouble in a (3)-turn cycle,
• begins dealing trouble on turn (2) no topic the player’s decisions,
• penalizes taking half in skill playing cards and severely limits deck manipulation and blocking,
• aloof has at the least (106) HP if given the max HP buff.

Additionally, fights in opposition to Gremlin Nob on the whole closing fewer turns than each and each Lagavulin and Three Sentries and are thus more uncomplicated to simulate.

If the player draws Bash too unhurried for the length of the first deck bound and has an spoiled reshuffle with their Strike playing cards, they’re likely unable to dwell to train the story Gremlin Nob’s attack for too many turns, even in the event that they’re ready to enter the fight with full HP ((80)). Unmitigated, Gremlin Nob deals now not lower than (88) trouble in the first (6) turns.

For a identical motive, the Defect might maybe well well moreover merely also be unable to dwell to train the story an spoiled fight in opposition to a buffed Gremlin Nob.

What about Watcher?

Watcher is extremely draw to be the strongest of the (4) characters in Kill the Spire. With her starting deck on my own, the player can deal (123) trouble for the length of the first (2) cycles by the deck. This exceeds the maximum scandalous HP of Gremlin Nob and Lagavulin, and generally can abolish all (3) Sentries.

On different hand, if the player is unable to play (2) Strikes for the length of this time, this amount is diminished to (99), which is lower than the minimum HP of a HP-buffed Gremlin Nob. Last in wrath stance also poses a important constraint on the player. If the player is in wrath for the length of a (3)-attack cycle, then, unmitigated, Gremlin Nob’s attacks for the length of this time total a minimum (112) trouble, which eclipses Watcher’s starting HP of (61) (Ascension (14+)), and the lesser of those two attacks totals (64) trouble.

What number of of Watcher’s skill and vitality playing cards are priceless in this particular fight? Whereas the acknowledge might maybe well well maybe be “many”, I attain now not imagine it is “all”. I am optimistic that even an unwinnable Watcher seed might maybe well well presumably be came upon in a couple of days of hunting, and confirmed, with the abet of a moderately optimized, RNG-factual fight simulator.

Are there unwinnable runs with system defects?

Within the event you watched Kill the Spire at AGDQ 2022 or respect in any other case viewed some Kill the Spire speedrunning, you presumably know that this recreation has masses of system defects. Using a differ of different node entry manipulation system defects, the player can:

1. (double node) enter (2) or more scheme nodes on the same ground,
2. (node dupe) enter the same scheme node twice,
3. (node reroll) commerce the fight in a duplicated fight node, and
4. (node ladder) climb the scheme on a couple of paths staunch now.

By node system defects on my own, the player critically will increase their likelihood of accessing trouble-dealing playing cards, deck manipulation, potions, card removals, card upgrades, and retail outlets from ?-nodes. Whereas it goes to be attainable to contrive instances for unwinnable glitched runs, they’re necessarily more scarce by loads of orders of magnitude. As an illustration, by duplicating combats, the player can turn a (3)-fight course into one with (5) or even (6) combats earlier than the burning elite. By visiting extra scheme nodes, the player also adjustments the bottom quantity for the length of the burning elite fight, and might maybe well well make stronger their deck manipulation in this model.

I doubt the sort of seed exists. If one does, it is unclear how one would get dangle of it, now not to enlighten prove it is unwinnable.

That it has taken (3) years for the explanation that recreation’s main initiating (and over (4) years because it modified into as soon as released for early entry) to search out and prove seed unwinnability is a testament to the energy of Kill the Spire’s balance and dangle. How noteworthy extra will we hurry? I attain now not know, but I invite any programmer to identify out the C++ and CUDA code. Don’t be unnerved to rating in contact (inquire of main weblog internet page for contact knowledge) and join the fun.