Solving a gamebook : solving the cartwheel game

The “Cartwheel” game is described in chapter 238, and is a gambling game that is unline any real world gambling game. It goes like this:

  • The player decides on an (integral) amount of money he would like to bet.
  • The players chooses a number between 0 and 9.
  • A random number between 0 and 9 is rolled, with the following outcomes:
  • If the player guessed what the rolled number was, he wins 8 times his wager.
  • If the player chose a number that is just before or after (0 and 9 are adjacent for this purpose) the rolled number, he wins 5 times his wager.
  • Otherwise, he loses his wager.

The game is very much biased for the player, as the expected win for a wager of w is 8w/10 + 2 × 5w/10 = 1.8w! So, unless it is a money laundering scheme, the gambling house that is described will soon go out out business.

The reason this game is placed here is that the player will soon after need at least 20 gold coins in order to buy a ticket, and some extra change depending on the circumstances. In order to convince yourself, you might want to take a look at the following picture, and search for chapter 238:

Click to see the whole picture

From here, one can see the only way to get a ticket (TKT) is to buy one for 20 coins at chapter 136. Then, depending on random rolls, one could be forced to leave another coin at chapters 195 or 339. If the player arrives at chapter 39 without tickets, he will be sent to his death. Same thing if he doesn’t have an extra coin in the next chapter (346).

So the player needs at least 22 coins before buying a ticket in order to make sure he makes it. But then, he might want to have extra money lining up his pocket for the rest of the adventure!

Optimal strategy, and model

I asked for help solving this problem, but did not get a good answer yet. Fortunately, one of the answers confirmed my intuition that the optimal strategy would be to bet as little as possible, so one coin for each round.

That makes it possible to model the game, for a target of t coins:

  • if the player owns t or more coins, the game ends
  • if the player owns 0 coins, the game ends too!
  • otherwise, the next step is:
    • the player loses 1 coin, with a probability of 7/10
    • the player gains 4 coin, with a probability of 2/10
    • the player gains 7 coin, with a probability of 1/10

That makes it possible to write a transition matrix, mapping the three cases:

transition :: Fractional a => Int -> Matrix a
transition n = foldl' ins (emptyMatrix n) (transitions ++ zero ++ fixedWon)
  where
     ins :: IM.IntMap (IM.IntMap a) -> (Int, Int, a) -> IM.IntMap (IM.IntMap a)
     ins mtx (x,y,r) = mtx & ix y . ix x .~ r
     zero = [(0,0,1)]
     fixedWon = do
        x <- [n .. n + 8]
        return (x,x,1)
     transitions = do
         x <- [1 .. n - 1]
         [ (x, max 0 (x - 1), 7 / 10), (x, x + 7, 1 / 10), (x, x + 4, 2 / 10) ]

For example, if the target is 10 coins (which is a bad idea, as the player will lose later):

1.0 0.7
0.7
0.7
0.7
0.7
0.2 0.7
0.2 0.7
0.2 0.7
0.1 0.2 0.7
0.1 0.2
0.1 0.2 1.0
0.1 0.2 1.0
0.1 0.2 1.0
0.1 0.2 1.0
0.1 1.0
0.1 1.0
0.1 1.0

So, the probability of a single step, if one start with 5 coins is:

LoneWolf.Cartwheel> transition  10 !* IM.singleton 5 (1 :: Double) & IM.filter (/= 0)
fromList [(4,0.7),(9,0.2),(12,0.1)]

Solving

In order to solve this problem, one would need to compute, for a transition matrix M, the value of limx → ∞Mx. In order to do that, one would need to diagonalize the M matrix. I don’t know how to do that symbolically on large matrices (for our purpose, the smallest will be 28×28), and sage doesn’t seem to either, so I will go for a numerical approximation. In all cases, I suppose the eigenvalues have irrational factors, so even with the exact symbolic formula the end result would have been approximated anyway, because all my probabilities are Rationals.

Instead of doing all the linear algebra, I just opted for squaring the matrix 20 times, using Doubles, and then converting it back to Rational.

The result, for the same target of 10 coins, looks like:

1.0 0.75 0.56 0.41 0.30 0.22 0.15 0.11 0.07 0.05
0.04 0.10 0.21 0.17 0.14 0.30 0.21 0.14 0.10 1.0
0.05 0.07 0.11 0.21 0.18 0.12 0.28 0.20 0.14 1.0
0.07 0.10 0.09 0.12 0.22 0.15 0.10 0.27 0.19 1.0
0.02 0.08 0.08 0.07 0.10 0.17 0.12 0.08 0.25 1.0
0.01 0.02 0.04 0.04 0.04 0.03 0.12 0.08 0.05 1.0
0.02 0.02 0.02 0.04 0.04 0.03 0.02 0.11 0.08 1.0
0.00 0.02 0.01 0.01 0.03 0.02 0.01 0.01 0.10 1.0

And the probability of a potentially infinite amount of steps, if one start with 5 coins is:

LoneWolf.Cartwheel> approx  10 !* IM.singleton 5 (1 :: Double) & IM.filter (/= 0)
fromList [(0,0.22607400081196705)
         ,(10,0.14606094132925695)
         ,(11,0.18229417264972955)
         ,(12,0.22275693955176407)
         ,(13,0.10310731161277857)
         ,(14,4.406795246148139e-2)
         ,(15,4.4122564256762906e-2)
         ,(16,3.151611732625923e-2)]

And interesting observation is that it makes little difference to aim for 22 or 50 coins if you start from a low amount, if you look at the relative distribution!

What about the other special chapter

The other special chapter, the portholes chapter, is completely random, and biased against the player (the two-zeros win is decided for the opponents before the player plays). It makes no sense to play this game, and it should be avoided. This means the only ratio

Next stop

There is now an implementation of the approximation code, along with code that was used to produce the charts and table in this article. There is also an implementation of the special chapter! The player gets to choose the amount of money he is aiming for, which is much better than the previous solutions I had (which only tried to get 22 gold, with a worse approximation).

The next stop is writing a solver, and trying to solve the first few chapters of the game. Then, it will be time to optimize the heck of it.