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 FightModifiers:

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 Sommerswerd.
• MindblastImmune: the opponent is not affected by the MindBlast ability 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 ChapterId is provided as the destination if he loses the fight. This happens in chapter 276.
• EnemyMindblast: the enemy has the MindBlast ability!
• PlayerInvulnerable the 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
fight cconstant cvariable fdetails = regroup $ do

It starts by computing the result of a single combat round.

  ((hpLW, hpOpponent), p) <- fightRound cconstant cvariable fdetails

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
                          ndetails = fdetails & fendurance .~ hpOpponent
                                              & 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 Endurance:

• 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.

Let's memoize!

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:

• The Timed modifier, 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 Timed effect 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 CombatSkill or Endurance modifications that are constant for the fight (player having WeaponSkill or Mindblast, combat modifiers such as MindblastImmune, CombatBonus, BareHanded, or Undead and DoubleDamage which both can be modelled as if the opponent had half the life).
• The only remaining special case is EnemyMindblast!

The resulting code is a pair of functions, with their memoized equivalents:

fightVanillaM :: CombatSkill -> Endurance -> Endurance -> Probably (Endurance, Endurance)
fightVanillaM = Memo.memo3 Memo.integral Memo.integral Memo.integral fightVanilla

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
      (odmg, pdmg) <- hits ratio
      fmap (/10) <$> fightVanillaM ratio (php - pdmg) (ohp - odmg)

fightMindBlastedM :: CombatSkill -> Endurance -> Endurance -> Probably (Endurance, Endurance)
fightMindBlastedM = Memo.memo3 Memo.integral Memo.integral Memo.integral fightMindBlasted

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
      (odmg, pdmg) <- hits ratio
      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.

What's left?

From the roadmap, I skipped the part about solving the special chapters, so that will be the next stop.