Tour · 5 of 11 · Section 4.6

The exact solver

Where does the optimum come from, and why was the published one wrong?

To know how good an episode is, each floor needs its optimum. The solver turns the grid into a graph: every monster and door is a node, neighbouring items are merged, and chains with nothing attached are merged too. It then searches over the sets of nodes the hero has cleared, keeping for each set the state with the most HP.

The solver published with the test maps keeps the first state it reaches for each set instead of the best. On the simple floor both give 13 HP. On the complex floor the published search reports 22 HP and the exact search 68, so every early claim of an "optimal" complex-floor win was an artefact (Appendix E, incident 12).

Search graph
node 0: start (5,0) (cleared in this state)node 1: Red Gem (+1 ATK) (1,0) +1node 1: Red Gem (+1 ATK) (1,0) +1node 2: yellow door (7,0) +2node 2: yellow door (7,0) +224node 2: yellow door (7,0) +2 Green Slime: HP 50 ATK 7 DEF 3 gold 0 costs 24 HP to kill now114node 3: Slime Lord (2,1) +1 Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill now114node 3: Slime Lord (2,1) +1 Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill nownode 4: Yellow Key (5,1)node 5: Red Gem (+1 ATK) (9,1) +2node 5: Red Gem (+1 ATK) (9,1) +2node 5: Red Gem (+1 ATK) (9,1) +2node 6: Red Gem (+1 ATK) (1,3) +2node 6: Red Gem (+1 ATK) (1,3) +2node 6: Red Gem (+1 ATK) (1,3) +256node 7: Red Slime (5,3) Red Slime: HP 70 ATK 11 DEF 1 gold 0 costs 56 HP to kill now55node 8: Black Slime (6,4) Black Slime: HP 45 ATK 5 DEF 5 gold 0 costs 55 HP to kill nownode 9: Blue Gem (+1 DEF) (10,4) +1node 9: Blue Gem (+1 DEF) (10,4) +1182node 10: Bat (3,5) Bat: HP 100 ATK 17 DEF 2 gold 0 costs 182 HP to kill nownode 11: yellow door (7,5)55node 12: Black Slime (9,5) Black Slime: HP 45 ATK 5 DEF 5 gold 0 costs 55 HP to kill now24node 13: Green Slime (5,6) Green Slime: HP 50 ATK 7 DEF 3 gold 0 costs 24 HP to kill nownode 14: Blue Gem (+1 DEF) (0,7) +1node 14: Blue Gem (+1 DEF) (0,7) +155node 15: Black Slime (3,7) +1 Black Slime: HP 45 ATK 5 DEF 5 gold 0 costs 55 HP to kill nownode 15: Black Slime (3,7) +1node 16: Red Potion (+75 HP) (7,7)56node 17: Red Slime (10,7) +1 Red Slime: HP 70 ATK 11 DEF 1 gold 0 costs 56 HP to kill now114node 17: Red Slime (10,7) +1 Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill nownode 18: Yellow Key (2,8) +2node 18: Yellow Key (2,8) +2node 18: Yellow Key (2,8) +2114node 19: Slime Lord (1,9) Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill now182node 20: Bat (5,9) Bat: HP 100 ATK 17 DEF 2 gold 0 costs 182 HP to kill now!node 21: Boss (5,10) Boss: HP 50 ATK 20 DEF 12 gold 0 cannot be beaten at the hero's ATKnode 22: Red Gem (+1 ATK) (7,10) +1node 22: Red Gem (+1 ATK) (7,10) +1

One frame per node over the game's tiles: monsters red (boss purple), doors in their colour, items green, the start gold; cleared nodes are filled and their tiles emptied. Items next to each other are merged into one node (dashed lines), as are chains of monsters and doors with nothing else attached. Lines join nodes the hero can walk between. Numbers give the order of the decisions in the state shown (the hero marks the start; items picked up on the way are not numbered): the state just taken from the queue, and once the search ends the best state. Gold ring: the nodes it can take next. The number on a monster is the HP it costs to kill at the hero's current stats (green: affordable, red: not, !: cannot be beaten). Hover a tile for its node and monster stats.

HP470start 470
ATK / DEF9 / 4
Keys0 / 0 / 0yellow / blue / red
Expanded00 taken from the queue
Queue10 queued in total
Skipped0set already expanded with ≥ HP
Best so far–optimum 13
What the search did (newest first)

Press step to take the first state from the queue.

Exact search. States are taken in order of decisions (breadth first), most HP first. A set of cleared monsters and doors is expanded again only if a later state reaches it with more HP, so no better route is thrown away.

Published search. The solver released with the test maps keeps the first state it takes for each set. On this floor both find 13 HP; on the complex floor the published search reports 22 HP and the exact search 68.

More floors, including all generated floors, are on the solver page. The searches of the complex floor and hand03 take minutes, so their routes are precomputed on their floor pages.