Simulation

Project Euler 84: In the game, Monopoly, find the three most popular squares when using two 4-sided dice

Project Euler 84: In the game, Monopoly, find the three most popular squares when using two 4-sided dice

Problem 84 of Project Euler is either difficult or boring based on the number of people who has solved it. At the time of writing it was only solved by 3669. However, I think it was a lot of fun to solve. The problem reads

In the game, Monopoly, the standard board is set up in the following way:

GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL
H2 C1
T2 U1
H1 C2
CH3 C3
R4 R2
G3 D1
CC3 CC2
G2 D2
G1 D3
G2J F3 U2 F2 F1 R3 E3 E2 CH2 E1 FP

A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.

In addition to G2J, and one card from each of CC and CH, that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.

At the beginning of the game, the CC and CH cards are shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.

  • Community Chest (2/16 cards):
    1. Advance to GO
    2. Go to JAIL
  • Chance (10/16 cards):
    1. Advance to GO
    2. Go to JAIL
    3. Go to C1
    4. Go to E3
    5. Go to H2
    6. Go to R1
    7. Go to next R (railway company)
    8. Go to next R
    9. Go to next U (utility company)
    10. Go back 3 squares.

The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing on it is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes at on each roll that we are interested in. We shall make no distinction between “Just Visiting” and being sent to JAIL, and we shall also ignore the rule about requiring a double to “get out of jail”, assuming that they pay to get out on their next turn.

By starting at GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.

Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.

If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.

A rather long problem description of the game of monopoly. I first considered solving this problem using Markov chains, something I am only vaguely familiar with, but I thought I would get a chance to study more. It involves a finite number of states (the squares) and a probability of moving between these squares (The dice rolls along with the additional rules). Since there are only 40 squares I thought it would be a reasonable approach.

However, one of the basic properties of Markov chains is that they are memory less, meaning that the probability to move from one square to another is not dependent on how we got to that square. However the rule of moving to jail after three consecutive doubles busts that property. Based on these (1 and 2) sources I think it could be done but they also seem to avoid the three consecutive doubles so I decided to take another approach – Simulation.

What I did was basically implementing all the rules given in the problem statement as you can see in the coded further down in the post. After that I decided to make 1.000.000 rolls with the dice and then see how many times we visited each square. Pretty simple approach,  I know. But lets try.

The main C# code looks like

int[] board = new int[40];
int samples = 1000000;
random = new Random();
int doubles = 0;

for (int i = 0; i < samples; i++) {  //roll the dices  int dice1 = random.Next(4) + 1;  int dice2 = random.Next(4) + 1;   //Check doubles  doubles = (dice1 == dice2) ? doubles + 1 : 0;  if (doubles > 2) {
        cPos = 10;
        doubles = 0;
    } else {
        //Move to the square
        cPos = (cPos + dice1 + dice2) % 40;

         //Handle chance
         //Important first, as you can go CH3->CC3
         if (cPos == 7 || cPos == 22 || cPos == 36) chance();
         //Handle CH
         if (cPos == 2 || cPos == 17 || cPos == 33) CC();
         //Handle G2J
         if (cPos == 30) cPos = 10;
    }
    board[cPos]++;
}
int[] index = board
              .Select((item, indx) => new { Item = item, Index = indx })
              .OrderByDescending(x => x.Item)
              .Select(x => x.Index)
              .ToArray();

string modalstring = "";
for (int i = 0; i < 3; i++) {
    if (index[i] < 10) modalstring += "0";
    modalstring += index[i].ToString();
}

Then I have the two helper functions for the cards

private void CC() {
    int[] cc = { 0, 10 };
    ccPos = ++ccPos % 16;

    if (ccPos < 2) {
        cPos = cc[ccPos];
    }
    return;
}

 

private void chance() {
    int[] chance = { 0, 10, 11, 24, 39, 5 };

    chancePos = ++chancePos % 16;

    if (chancePos < 6) {
        cPos = chance[chancePos];
    }

    if (chancePos == 6 || chancePos == 7) {
        if (cPos == 7) cPos = 15;
        if (cPos == 22) cPos = 25;
        if (cPos == 36) cPos = 5;
    }

    if (chancePos == 8 ) {
        cPos = (cPos == 22) ? 28 : 12;
    }

    if (chancePos == 9) cPos -= 3;
    return;
}

as well as the class variables

Random random;
int cPos = 0;
int ccPos = 0;
int chancePos = 0;

As you can see I haven’t modeled that the doubles are reset if move to jail, as I think the real game would imply, but that should be rather easy to include if you decide to. It wont change the result for this problem though.

The simulation gives us

the six-digit modal string is 101524
Solution took 68,2296 ms

There is no guarantees that this will give us the exact probabilities, but it gets us close enough to get the right ordering.

Wrapping up

Being someone who played a lot of monopoly as a kid or at least the Danish version of it, this problem was a lot of fun to solve. In order to get good at it, I guess the next thing to do is to correlate it with the payoff of buying the properties. I haven’t done that though.

You can find the complete source code here. Next thing I guess is to play the game again. So see you all later.

Oh yeah, one last question, how did you solve this problem?

The blog image is from a giant monopoly at the children’s museum Guadalupe river park and taken by Anna Fox who shared it under the Creative Commons license.

Posted by Kristian in Project Euler, 16 comments