Solving a gamebook : roadmap

I will try to achieve the following goals during this serie:

  • Model the book in the most accurate way. This part is already done, and is kind of failed already, as I removed several elements from the original story : the warm blanket that can be bought/grabbed but serves no actual purpose, and all references to a star pendant that is given to the player in the previous book. This will be detailed in the next post, and in my experience is one of the hardest part to get right, because of how tedious and error-prone it is.
  • Model the rules in the most accurate way, and provide a console interpreter of the game.
  • Write a generic solver for single player games, and try to run it on reduced versions of the game.
  • Optimize and memoize the combat solver. This part is quite tricky, and I found it hard to get the rules right and optimize for efficient memoization at the same time.
  • Solve the “special chapters” (such as the cartwheel game). They provide a way for the player to gain some money, which is required in later parts of the adventure. Solving this part will require careful analysis of the game structure in order to determine the proper “win conditions” for these games.
  • Manually alter the book description to get rid of loops, and to reduce the complexity of the player state.
  • Improve the efficiency of the solver. This part includes writing heuristics about player choice, using checkpoints, or other approximations. I will try to find a good balance between computability and precision.
  • Solve the game!
  • ???
  • Generate pretty graphs and provide analysis.

The linked picture comes from a previous try at solving this story. The redder the node, the most likely the player is to traverse it, if he plays optimally. White nodes are “checkpoints”, which means the solver would try to solve subsets of the game that lie between two consecutive checkpoints, which greatly helps with the performance. It can however destroy the accuracy of the analysis, as some paths are more risky, but provide the player with items that could make the game easier after the next checkpoint … The combat solver would also not take into account timed effects (more on that in the next episode!), and some other parts were too approximate.

I hope this serie of posts will prove to be a fun read, and force me to create an accurate solver!