I wrote a whole lot of logic since the last episode, and the game can now be played on the console, until you reach one of the special chapters. You can try the game (look at the end of this post). Decision flattening code is complete, and so is the combat code, even though it's really slow.

I tried several times describing the implementation in this post, but it's much too tedious to read, so it will focus only on a few key points.

The hidden optimization story

Many of the representation choices I'll take are motivated by the knowledge that solving the game book will involve some sort of memoization. As a result, it is crucial to make the game state as simple as possible :

• it should hold as little information as possible
• it should be possible to quickly turn this information into a "simple" data type, such as an integer type

The player character

All of what the player has to remember, when playing, is kept on the action chart. That's where all the game state resides, and it can be separated in two parts.

First of all, most of the data is constant during a play session, as it is rolled at the beginning of the story, or is imported from a previous book.

data CharacterConstant = CharacterConstant
      { _maxendurance :: Endurance
      , _combatSkill  :: CombatSkill
      , _discipline   :: [Discipline]
      } deriving (Generic, Eq, Show, Read)

Endurance represent how much damage a player can withstand, whereas the combat skill represents ... its skill in combat. The disciplines are many, and changing them can make each session unique! This data doesn't need to be particularly optimized for now, even though an obvious change would be to make the _discipline field a Set.

Then, there is the part that varies during the game, which needs to be optimized:

data CharacterVariable = CharacterVariable
      { _curendurance :: Endurance
      , _equipment    :: Inventory
      } deriving (Generic, Eq, Show, Read)

This is mainly the inventory, and the current health of the player.

A note on the inventory

A straightforward implementation of the inventory would be something like:

type Inventory = Map Item Int

This will however be much too inefficient for our future optimizations, so I decided to preemptively optimize it:

data Inventory = Inventory
     { _singleItems :: Word32
     , _gold        :: Word8
     , _meals       :: Word8
     } deriving (Generic, Eq, Show, Read)

I did not currently add the ! and {-# UNPACK #-} annotations, but inventory will most likely look like that up until the end. As can be seen, unique items are handled differently from meals and gold. This is an approximation, as the player can have a pair of identical weapons, but as it serves no purpose (except when selling weapons), I thought it was alright.

The singleItems field is a bitmap, where the first 25 bits each represent an unique item, just like it would be done in C.

Here is a function that works on the Inventory:

addItem :: Item -> Int -> Inventory -> Inventory
addItem i count inv
  | count < 0 = delItem i (negate count) inv
  | count == 0 = inv
  | otherwise = case i of
                  Gold -> inv & gold %~ \curgold -> min 50 (curgold + fromIntegral count)
                  Meal -> inv & meals +~ fromIntegral count
                  _    -> inv & singleItems %~ flip setBit (fromEnum i)

As can be seen, it treats gold and meals specifically, and sets bits in the singleItems field according to each item fromEnum. It ensures that the player can't own more than 50 gold coins, but is otherwise pretty brittle:

• adding more than one item that's not gold or a meal will only result in the item being owned once by the player
• it doesn't enforce the backpack rule of 8 items at most (including meals)
• it doesn't enforce the fact that the player can't own more than two weapons

All of this logic is handled in the part that handles player decisions, and that will be presented, if ever, in another episode (this logic lives in the LoneWolf.Choices module).

A possible future change would be to handle weapons differently, and have for example two slots reserved for them in the inventory. That would make a lot of the logic in the program a tad simpler, but I'll wait for the profiling data to decide.

The Probably type

Several outcomes involve an element of randomness, more specifically the Randomly and Fight ones. For this reason, the function that computes the updated game state from the ChapterOutcome has the following type:

data NextStep = NewChapter ChapterId CharacterVariable HadCombat
              | HasLost
              | HasWon CharacterVariable
              deriving (Show, Eq, Generic)

update :: CharacterConstant
       -> CharacterVariable
       -> ChapterOutcome
       -> Probably NextStep
update = ...

The Probably a type represents the probability distribution of events of type a happening. I went for this simple representation:

type Probably a = [(a, Proba)]
type Proba = Rational

So, for example, a six-sided dice roll will be:

d6 :: Probably Int
d6 = [ (n, 1/6) | n <- [1..6] ]

However, there are cases when transforming a distribution will require simplification. For example, if we make a game where we need to roll two six sided dices:

twod6 :: Probably Int
twod6 = do
  (roll1, p1) <- d6
  (roll2, p2) <- d6
  return (roll1 + roll2, p1 * p2)

This will return a list with 36 distinct elements:

[(2,1 % 36),(3,1 % 36),(4,1 % 36),(5,1 % 36),(6,1 % 36),(7,1 % 36),(3,1 % 36),(4,1 % 36)
,(5,1 % 36),(6,1 % 36),(7,1 % 36),(8,1 % 36),(4,1 % 36),(5,1 % 36),(6,1 % 36),(7,1 % 36)
,(8,1 % 36),(9,1 % 36),(5,1 % 36),(6,1 % 36),(7,1 % 36),(8,1 % 36),(9,1 % 36),(10,1 % 36)
,(6,1 % 36),(7,1 % 36),(8,1 % 36),(9,1 % 36),(10,1 % 36),(11,1 % 36),(7,1 % 36),(8,1 % 36)
,(9,1 % 36),(10,1 % 36),(11,1 % 36),(12,1 % 36)]

While this will technically work with all algorithms I will use to solve the game book, this will increase the work necessary to solve the game, as it will require exploring more game states. In the past, I used this maps to ensure the unicity of game states in the Probably type:

type Probably a = HashMap a Proba

twod6 :: Probably Int
twod6 = HM.fromListWith (+) $ do
  (roll1, p1) <- HM.toList d6
  (roll2, p2) <- HM.toList d6
  return (roll1 + roll2, p1 * p2)

But this time I decided to give discrimination a spin! I might benchmark it against other solutions in the next installments.

regroup :: D.Grouping a => Probably a -> Probably a
regroup = map (\( (a,s): as ) -> (a, s + sum (map snd as)) ) . D.groupWith fst

twod6 :: Probably Int
twod6 = regroup $ do
  (roll1, p1) <- d6
  (roll2, p2) <- d6
  return (roll1 + roll2, p1 * p2)

Playing the game

It's now possible to play the game, unless you arrive to either the cartwheel or portholes chapters. It's pretty ugly, but is there mainly to validate that things seem to work. If you want to try it, just clone the repo, and do:

$ stack build && .stack-work/install/x86_64-linux/lts-8.4/8.0.2/bin/gamebooksolver-consoleplay