Project Euler/227

Problem Statement

Game with 2 dice, even number of players

Players sit around a table, game begins with 2 opposite players, 1 die each.

On each turn, the two players with the die roll it.

If the player rolls 1, they pass the die to their left neighbor

If the player rolls 6, they pass sthe die to their right neighbor

Otherwise, they keep the die for the next turn

The game ends when one player has both dice after they have been rolled and passed. That player loses.

In a game with 100 players, what is expected number of turns the game lasts?

Analysis

Since this is a large-numbered PE problem, we can start with a brute force solution and explore a small part of the problem space, and then get an estimate for whether we are even in the neighborhood of possibility to do the calculation.

The Chase Simulator

I started by writing a simple script to simulate the game. I used two pointers, and in each round of the game, incremented or decremented the pointers based on the outcome of two random integers (the dice).

The game is essentially a Markov simulator, as the state of the game on any given round only depends on the state of the game in the prior round. No histeresis.

Estimating Brute Force Solution Time

Based on the fact that each simulation is independent, there is a linear relationship between number of simulations and computational cost. If I want 4 decimal places of accuracy, it will cost at least 1000 simulations. To get to 10 decimal places of accuracy, we will need to run billions of simulations.

The relationship bettween number of players and computational cost is more complicated. Based on running the numbers with 5, 10, 15, 20, and 25 players, the relationship looks to be quadratic, meaning the computational cost increases with the number of players squared.

The execution time in terms of the number of players N and number of simulations S is therefore

$ T(N, S) = c \times S \times N^2 $

If I use the simple Python program to measure computational cost for smaller N and S, and extrapolate to 100 players and 9 billion simulations, I esimated a solution time of 7 x 10^6 seconds, or 80+ days.

Hmmm.

We should expect PE solutions to complete in a reasonable amount of time - say 100 seconds. That means the code needs to get 10,000x faster for a brute force solution to be feasible.

Switching to a compiled language like Java should help, as should implementing multi-threading. But because the game is so simple - just modular arithmetic with pointers - it doesn't seem like there is a whole lot of places to look for other optimizations.

Markov Insights

Denote the Markov state as $ (i, j) $, where $ i, j \in \{0, 1, 2, 3\} $

Starting state would be (0, 2)

Absorbing states are (0, 0), (1, 1), (2, 2), (3, 3)

Transition probabilities are 1/6 probability to pass to the left, 1/6 probability to pass to the right, 4/6 probability to keep the die

Transition probability from state $ (i, j) $ to $ (i^{\prime}, j^{\prime}) $ is the product of the transition probabilities of each die

Let E(i,j) be expected number of additional rounds starting from state (i,j) until a player loses (absorbing state)

We can think about E(i,j) as a recursive expression.

The base case are the absorbing states, where the expected number of additional rounds is 0

$ E[i,j] = 0 $

The recursive case are the non-absorbing states, where the expected number of additional rounds is

$ E[i,j] = 1 + \sum_{i', j'} P((i,j) \rightarrow (i',j')) \times E[i',j'] $

Explanation:

• We know there will be at least 1 more round (b/c this is a non-absorbing state), hence the 1
• We are also summing over each potential next state (i',j'). We multiply the transition probability for that state by E(i,j) for that state.

Unfortunately, this approach gets complicated fast.

Suppose we have 4 players. Then the expression for E[0, 2] would be

E[0,2] = 1 + (2/3)(2/3)E[0,2] + (2/3)(1/6)E[0,1]
         + (2/3)(1/6)E[0,3] + (1/6)(2/3)E[3,2] + (1/6)(1/6)E[3,1]
         + (1/6)(1/6)E[3,3] + (1/6)(2/3)E[1,2] + (1/6)(1/6)E[1,1]
         + (1/6)(1/6)E[1,3]