Solving a gamebook : revenge of the Haskell solver
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
Last time I rewrote the Haskell solver in Rust, and it was so much faster that it became possible to solve the second book from zero. That was very satisfying, but I had misgivings.
First, the Haskell version was better tested, and supported more features (such as the hunting discipline). Secondly, for Haskell I used a standard memoizer, whereas in Rust I wrote my own memoization system. I decided to do the same with the Haskell version, and it turned out it runs sufficiently fast to be usable! It is also much more confortable to add features in such a high level language.
I also tweaked the book description a bit to remove graph loops (unfortunately, this is currently a manual process), and introduced a topological sort approach to state exploration that prevents exploration loops.
To cut things short, here are updated numbers, that have been checked more toroughly than in the previous post, and should be much more accurate. In particular, a lot of bugs have been found in the chapters descriptions, and the combat escape mechanism did not work. This means that win probabilities are now much better, as fights can actually be avoided!
Starting conditions
In the following examples, the starting conditions are:
- a short sword (yes, even when having other weapon disciplines)
- the Seal of Hammerdal
- a shield
- 15 gold coins
In the previous instalments, I chose the pair of meals over the shield, but the shield is in fact the most effective item to choose at the beginning of the story. All other items would be quickly lost, but for some reason the shield can be kept.
It would be better to choose a weapon that matches selected weapon specialties, but this will be for another episode :)
Number of states
First of all, what is interesting is how many game states need to be traversed in order to find the solution, depending on the starting disciplines. The time it takes to compute a solution is generally proportional to the amount of states that must be searched. Here is a quick chart that should be illustrative:
Tracking | Spear | ShortSword | Healing | MindBlast | MindShield | AnimalKinship | Camouflage | MindOverMatter | SixthSense | Hunting | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Tracking | 2985557 | 2625361 | 2711710 | 2902417 | 2985249 | 3099854 | 3150696 | 3204877 | 3198669 | 3198145 | 9314661 |
| Spear | 2625361 | 5236316 | 5819251 | 5060427 | 5230867 | 5323102 | 5519090 | 5512594 | 6073541 | 6171112 | 12612684 |
| ShortSword | 2711710 | 5819251 | 5297698 | 5123241 | 5293613 | 5420292 | 5561858 | 5567158 | 5860453 | 5942910 | 13092512 |
| Healing | 2902417 | 5060427 | 5123241 | 5514335 | 5510899 | 5705421 | 5812238 | 5861880 | 5862985 | 5917761 | 14926638 |
| MindBlast | 2985249 | 5230867 | 5293613 | 5510899 | 5654395 | 5845481 | 5957920 | 5983669 | 6102573 | 6174766 | 15263336 |
| MindShield | 3099854 | 5323102 | 5420292 | 5705421 | 5845481 | 5847823 | 6142386 | 6188875 | 6303044 | 6456377 | 15507739 |
| AnimalKinship | 3150696 | 5519090 | 5561858 | 5812238 | 5957920 | 6142386 | 5954460 | 6300863 | 6405337 | 6438119 | 15776351 |
| Camouflage | 3204877 | 5512594 | 5567158 | 5861880 | 5983669 | 6188875 | 6300863 | 5986011 | 6460004 | 6530189 | 16144572 |
| MindOverMatter | 3198669 | 6073541 | 5860453 | 5862985 | 6102573 | 6303044 | 6405337 | 6460004 | 6105302 | 6177566 | 15883371 |
| SixthSense | 3198145 | 6171112 | 5942910 | 5917761 | 6174766 | 6456377 | 6438119 | 6530189 | 6177566 | 6177567 | 15826247 |
| Hunting | 9314661 | 12612684 | 13092512 | 14926638 | 15263336 | 15507739 | 15776351 | 16144572 | 15883371 | 15826247 | 15129259 |
It turns out hunting makes the number of states explode. I believe it is because it allows you to keep more meals, creating more decisions when the character does not have to hunt.
On the other hand, tracking does reduce the amount of states generated. The reason is that at chapter 231, you get to choose between two huge branches, but tracking forces you into a given path.
Success probability
Strong character
A strong character starts with maxed out endurance and combat skill (respectively 29 and 19).
AnimalKinship | MindShield | Hunting | Spear | Healing | MindBlast | ShortSword | Camouflage | MindOverMatter | SixthSense | Tracking | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| AnimalKinship | 89.29% | 89.29% | 89.55% | 89.49% | 89.56% | 89.54% | 89.54% | 89.29% | 89.29% | 84.83% | 89.29% |
| MindShield | 89.29% | 50.24% | 78.73% | 67.31% | 64.28% | 52.69% | 52.20% | 50.24% | 50.24% | 47.96% | 49.34% |
| Hunting | 89.55% | 78.73% | 42.43% | 63.95% | 55.95% | 46.79% | 44.86% | 42.43% | 42.43% | 40.31% | 42.43% |
| Spear | 89.49% | 67.31% | 63.95% | 29.24% | 43.05% | 31.47% | 31.37% | 29.24% | 29.24% | 27.89% | 28.51% |
| Healing | 89.56% | 64.28% | 55.95% | 43.05% | 24.54% | 24.54% | 24.34% | 24.54% | 24.54% | 23.52% | 24.18% |
| MindBlast | 89.54% | 52.69% | 46.79% | 31.47% | 24.54% | 17.26% | 17.91% | 17.26% | 17.26% | 16.42% | 15.62% |
| ShortSword | 89.54% | 52.20% | 44.86% | 31.37% | 24.34% | 17.91% | 16.79% | 16.79% | 16.79% | 16.00% | 15.62% |
| Camouflage | 89.29% | 50.24% | 42.43% | 29.24% | 24.54% | 17.26% | 16.79% | 15.89% | 15.89% | 15.11% | 14.10% |
| MindOverMatter | 89.29% | 50.24% | 42.43% | 29.24% | 24.54% | 17.26% | 16.79% | 15.89% | 15.89% | 15.11% | 14.10% |
| SixthSense | 84.83% | 47.96% | 40.31% | 27.89% | 23.52% | 16.42% | 16.00% | 15.11% | 15.11% | 15.11% | 13.40% |
| Tracking | 89.29% | 49.34% | 42.43% | 28.51% | 24.18% | 15.62% | 15.62% | 14.10% | 14.10% | 13.40% | 14.10% |
Average character
A strong character starts with everage endurance and combat skill (respectively 25 and 15).
AnimalKinship | MindShield | Hunting | Spear | Healing | MindBlast | ShortSword | Camouflage | MindOverMatter | Tracking | SixthSense | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| AnimalKinship | 84.92% | 84.92% | 85.38% | 84.78% | 85.22% | 87.09% | 86.94% | 84.92% | 84.92% | 84.53% | 80.73% |
| MindShield | 84.92% | 6.91% | 22.92% | 16.40% | 13.77% | 7.42% | 7.40% | 6.91% | 6.91% | 6.91% | 6.56% |
| Hunting | 85.38% | 22.92% | 3.96% | 11.10% | 7.82% | 4.25% | 4.24% | 3.96% | 3.96% | 3.96% | 3.76% |
| Spear | 84.78% | 16.40% | 11.10% | 2.41% | 5.28% | 2.61% | 2.56% | 2.41% | 2.41% | 2.29% | 2.29% |
| Healing | 85.22% | 13.77% | 7.82% | 5.28% | 1.66% | 1.70% | 1.70% | 1.66% | 1.66% | 1.66% | 1.57% |
| MindBlast | 87.09% | 7.42% | 4.25% | 2.61% | 1.70% | 0.73% | 0.85% | 0.73% | 0.73% | 0.73% | 0.69% |
| ShortSword | 86.94% | 7.40% | 4.24% | 2.56% | 1.70% | 0.85% | 0.73% | 0.73% | 0.73% | 0.73% | 0.69% |
| Camouflage | 84.92% | 6.91% | 3.96% | 2.41% | 1.66% | 0.73% | 0.73% | 0.67% | 0.67% | 0.67% | 0.64% |
| MindOverMatter | 84.92% | 6.91% | 3.96% | 2.41% | 1.66% | 0.73% | 0.73% | 0.67% | 0.67% | 0.67% | 0.64% |
| Tracking | 84.53% | 6.91% | 3.96% | 2.29% | 1.66% | 0.73% | 0.73% | 0.67% | 0.67% | 0.67% | 0.64% |
| SixthSense | 80.73% | 6.56% | 3.76% | 2.29% | 1.57% | 0.69% | 0.69% | 0.64% | 0.64% | 0.64% | 0.64% |
Effect of skill and endurance on outcome
This table displays the effect of starting skill and endurance on the winning probability, for the animal kinship and mindblast choice of disciplines.
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 20 | 68.63% | 71.42% | 77.10% | 78.11% | 80.31% | 81.80% | 85.20% | 85.65% | 86.88% | 87.04% |
| 21 | 70.60% | 73.48% | 79.06% | 80.04% | 82.11% | 83.46% | 86.36% | 86.70% | 87.69% | 87.82% |
| 22 | 72.35% | 75.27% | 80.69% | 81.61% | 83.53% | 84.73% | 87.14% | 87.39% | 88.26% | 88.34% |
| 23 | 73.96% | 76.87% | 82.09% | 82.93% | 84.67% | 85.72% | 87.69% | 87.87% | 88.67% | 88.72% |
| 24 | 75.42% | 78.26% | 83.25% | 84.01% | 85.59% | 86.47% | 88.10% | 88.21% | 88.97% | 89.01% |
| 25 | 76.80% | 79.53% | 84.25% | 84.92% | 86.35% | 87.09% | 88.42% | 88.49% | 89.18% | 89.21% |
| 26 | 78.10% | 80.69% | 85.10% | 85.68% | 86.99% | 87.59% | 88.69% | 88.74% | 89.34% | 89.35% |
| 27 | 79.33% | 81.76% | 85.81% | 86.31% | 87.53% | 88.01% | 88.92% | 88.96% | 89.43% | 89.45% |
| 28 | 80.46% | 82.71% | 86.40% | 86.82% | 87.99% | 88.36% | 89.12% | 89.14% | 89.49% | 89.50% |
| 29 | 81.51% | 83.57% | 86.90% | 87.25% | 88.37% | 88.66% | 89.27% | 89.29% | 89.53% | 89.54% |
Discussion
As always, fair bit of warning : all those statistics might be completely wrong. They sure were previously, and while I reviewed the chapter descriptions toroughly, there still might be mistakes, especially in the decision heuristics.
As was well known, the animal kinship discipline is almost obligatory if one wishes to survive this book. If you do not have this discipline, you are forced through a route that involves acquiring the magic spear, which is a very dangerous fight. A descent substitute is the hunting and mindshield combination, but only for strong characters.
One huge surprise was that some disciplines decreases your probability of winning.
The first is sixth sense. This discipline is useful for a human, as it gives hints throughout the adventure, but not to a solver that already knowns the optimal path. Its drawback is observed in chapter 254 where it forces you thought a path that leads to chapter 183, where you have a 10% chance of instadeath.
The other low tier discipline is tracking, which is used in four chapters in order to give you a hint about where you should go next, and only opens a new path in chapter 334, but this chapter is not on the optimal solution path anyway. As previously discussed, it also forces you into a bad path, at chapter 231.
Chapter 200, and the choice of assassin
In chapter 200, you get to choose who you will attack. As noted in other walkthough, attacking Halvorc the merchant seems preferable as it is the easier fight. However, it also has a weak reward, so I wondered if it might make sense, sometimes, to have a harder fight in exchange for a better reward.
It turns out that this is indeed that case, but in a completely counter-intuitive way. It is sometimes better to attack the priest Parsion. I did a tiny bit of correlation, and it turns out that it is inversely correlated to the amount of meals one have (except for characters with the hunting discipline), and to the probability of actually winning that fight!
I suppose that the stronger characters do not need that reward to survive the rest of the adventure, which makes the harder fight only interesting for weaker characters.
For those interested, here are the raw correlation results between all tracked variables for average character with mindblast and animal kinship. Win chances and expected endurance are computed for the priest fight.
chapter allmeals winchance expectedendurance Laumspur Meal
chapter 1.000000 -0.226461 -0.413484 -0.259957 -0.195328 -0.141111
allmeals -0.226461 1.000000 -0.014969 -0.059701 0.640212 0.797655
winchance -0.413484 -0.014969 1.000000 0.858334 -0.139976 0.090432
expectedendurance -0.259957 -0.059701 0.858334 1.000000 -0.183343 0.066315
Laumspur -0.195328 0.640212 -0.139976 -0.183343 1.000000 0.047357
Meal -0.141111 0.797655 0.090432 0.066315 0.047357 1.000000Conclusion
I am much more confident in the current version numbers, but I will need to audit the choice heuristics to make sure nothing is wrong. The current software has a solution explorer, that let you run through the adventure and tells you your probability of winning at each choice, but it is still very crude. A browser version would be much nicer, but I can't really reuse all the Haskell machinery, as this project is GHC 9+ and GHCJs doesn't seem to be supported for this version :(
- 2021-12-07 : fixed a bug in the way combat escapes were handled. Should work properly now!