Solving a gamebook : implementing the combat system, and first optimizations
This post is part of the "Gamebook solver" serie:
- Solving a gamebook : introduction
- Solving a gamebook : roadmap
- Solving a gamebook : chapters
- Solving a gamebook : game state and probability
- Solving a gamebook : implementing the combat system, and first optimizations
- Solving a gamebook : solving the cartwheel game
- Solving a gamebook : a smarter solver
- Solving a gamebook : a simple solver
- Solving a gamebook : the Rust rewrite, teaser
- Solving a gamebook : revenge of the Haskell solver
- Solving a gamebook : can we solve five books at once? The 2022 update.
- Solving a gamebook : Lone Wolf book 05, Shadow on the Sand mega solution (edit)
- Solving a gamebook : Lone Wolf book 04, The Chasm of Doom
The combat system of the Lone Wolf series is pretty simple in the absence of special rules. The problem is, there are quite a few special rules, that are modelized as
data FightModifier = Undead | MindblastImmune | Timed Rounds FightModifier | CombatBonus CombatSkill | BareHanded | EnemyMindblast | PlayerInvulnerable | DoubleDamage | FakeFight ChapterId | Evaded Rounds ChapterId
Here is a brief description of these modifiers:
Undead: undead creatures take double damage from the
MindblastImmune: the opponent is not affected by the
MindBlastability of the player.
CombatBonus: the player receives a combat bonus for this fight.
BareHanded: the player is forced to fight bare handed, reducing his combat skill by 4 points.
FakeFight: this isn't a real fight, and the player will have his endurance restored at the end of the fight. The
ChapterIdis provided as the destination if he loses the fight. This happens in chapter 276.
EnemyMindblast: the enemy has the
PlayerInvulnerablethe player cannot be harmed.
DoubleDamage: happens in chapter 306, where the player inflicts double damage.
Timed: the effect only lasts a given number of rounds.
Evaded: the player will evade the fight after this round.
Player abilities also interact with the combat rules, resulting in an annoyingly complex function that I hope I got right for resolving a single round of combat, and another one that is just as annoying for computing the combat ratio.
In the end, the top level function takes all player data, the combat specific data, and returns a distribution of the player's
Endurance statistic after the fight:
fight :: CharacterConstant -> CharacterVariable -> FightDetails -> Probably Endurance = regroup $ dofight cconstant cvariable fdetails
It starts by computing the result of a single combat round.
<- fightRound cconstant cvariable fdetails ((hpLW, hpOpponent), p)
Then checks if the combat is over.
let evaded = fdetails ^? fightMod . traverse . _Evaded . _1 == Just 0 outcome| hpLW <= 0 = return (-1, p) -- player is dead | hpOpponent <= 0 || evaded = return (hpLW, p) -- player escaped
Otherwise, the endurance of each opponent is updated, timed effects counters are decremented, and another round is started:
| otherwise = let nvariable = cvariable & curendurance .~ hpLW = fdetails & fendurance .~ hpOpponent ndetails & fightMod %~ mapMaybe decrementTimed in fmap (*p) <$> fight cconstant nvariable ndetails outcome
But it is so slow!
The sample fight that's in the tests makes the tests complete in about 3.4s. That is a lot of time, and is a showstopper, as many, many fights will be evaluated in order to solve the game.
The reason it's so slow is that each round produce ten possible outcomes, resulting in an exponential increase in the number of evaluated possibilities with the number of rounds. Hopefully, thanks to the way the combat system works, one of the fighters always receives damage, which means that the fight always finishes in a finite amount of time.
Unfortunately, as it is implemented, most nodes are traversed, and evaluated, several times, as can be seen in the following picture:
The cause is easy to understand: several distinct fighting situations can produce the same result. For example, the two following situations result in the player having 15
- The player has 17
Endurance, and receives two points of damage ;
- the player has 16
Endurance, and receives one point of damage.
In both cases, the algorithm, as it is written right now, will keep on computing starting from the same state, effectively computing twice the exact same expression. If it was possible to compute each expression exactly once, the situation would be like that:
There are several strategies for reducing the complexity of this problem, which would fall under the name "dynamic programming". The simplest way to do that in Haskell is memoization, for which I have often successfully used the data-memocombinators package.
Memoizing is about mapping the results of a function to a persistent structure. There must be a relationship between the arguments of the function and the position the result is stored in the structure. That way, in order to evaluate the result of a function, one only has to traverse the structure to the proper place, and read the stored value. But do not worry, data-memocombinators takes care of everything!
However, there is a major drawback to memoization: the structure that stores the results must be persistent, and will never be garbage collected. It is crucial to memoize functions with the smallest set of inputs as possible, in order to minimize the memory footprint (this is an approximation, as it depends on the properties of the lazy data structure, but it is a good rule of thumb).
Let's go back to the original function, that has type:
fight :: CharacterConstant -> CharacterVariable -> FightDetails -> Probably Endurance
This is far from ideal, as all three arguments are complex data structures, containing a lot of information irrelevant to the fighting situation. After a bit of research about compressing the input space of the memoized combat function, I made the following observations:
Timedmodifier, which models effects that only last for certain duration, keeps effects working for at most 2 rounds after the fight has started. As the effects do not last long, I decided to keep the original (slow) combat logic as long as a
Timedeffect was present in the list of
CombatModifier. This decision simplifies the handling of
PlayerInvulnerable, which only ever happens to be timed.
- Almost all other modifiers / disciplines can be reduced to
Endurancemodifications that are constant for the fight (player having
Mindblast, combat modifiers such as
DoubleDamagewhich both can be modelled as if the opponent had half the life).
- The only remaining special case is
The resulting code is a pair of functions, with their memoized equivalents:
fightVanillaM :: CombatSkill -> Endurance -> Endurance -> Probably (Endurance, Endurance) = Memo.memo3 Memo.integral Memo.integral Memo.integral fightVanilla fightVanillaM fightVanilla :: CombatSkill -> Endurance -> Endurance -> Probably (Endurance, Endurance) fightVanilla ratio php ohp| php <= 0 || ohp <= 0 = certain (max 0 php, max 0 ohp) | otherwise = regroup $ do <- hits ratio (odmg, pdmg) fmap (/10) <$> fightVanillaM ratio (php - pdmg) (ohp - odmg) fightMindBlastedM :: CombatSkill -> Endurance -> Endurance -> Probably (Endurance, Endurance) = Memo.memo3 Memo.integral Memo.integral Memo.integral fightMindBlasted fightMindBlastedM fightMindBlasted :: CombatSkill -> Endurance -> Endurance -> Probably (Endurance, Endurance) fightMindBlasted ratio php ohp| php <= 0 || ohp <= 0 = certain (max 0 php, max 0 ohp) | otherwise = regroup $ do <- hits ratio (odmg, pdmg) fmap (/10) <$> fightVanillaM ratio (php - pdmg - 2) (ohp - odmg)
As can be seen, using
data-memocombinators is really straightforward for simple types. The result is a performance gain of 100x to 200x, depending on the fight complexity. The test suite now runs in less than 0.1s, which is fast enough to keep on working! I will try factoring the two functions into one, as they share so much code, but only after there is enough code written for having meaningful performance data.
From the roadmap, I skipped the part about solving the special chapters, so that will be the next stop.