 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;
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 SuprDewd

You’re catching up with me! This is the first problem that I didn’t solve before you posted a solution.

But nicely done. Kristian

Well I solve them linearly so at some point I had to run into a problem you hadn’t solved yet. And thanks 🙂 danei

line 25: CC3 is 33, not 34
It doesn’t matter actually… Kristian

You are right that it doesn’t matter for the problem as a such, but thanks for noticing anyway. I will change it now. kalhartt

I wanted to note that the three doubles -> jail rule isn’t so much of an issue for the Markov chain solution. Probabilities work backwards in time just as well as forward, so use the probability that the previous two were doubles. You can see my solution in python using a markov chain. Kristian

Thanks for sharing that solution, I probably need to study it a bit more before understanding it. But it seems interesting that you are indeed able to use markov chains. So you just model a certain probability that you rolled doubles in the last two rolls. Very clever. Marc-André Lafortune

To use markov chains, you can consider a state to be the pair formed by the position and how many successive doubles were rolled to get there. Instead of 40 possible states, you get 120.

I had fun coding a parametrizable monopoly game and used this technique to get the answer. In the standard Monopoly, I get 3.10 for Go, instead of 3.09 (actually something like 3.095…). Khaur

I went the simulation way as well. The issue IMO for Markov chains comes not from the three doubles condition (it’s still a third order MC – depending on only the last 3 states-, or you can fix it like Marc-André suggests), but from the Chance and CC cards.

For example, if you were just sent to jail by a CC card, your chances of ending up back there are lower until all the other CC cards have been drawn, at which point it raises significantly.

To be accurate, you need to model the current square, the number of previous doubles, the next Chance card, the next CC card, and you still have to deal with the initial shuffles.

However since it still works for some people without it, I guess being that accurate is not required here. Kristian

I see what you are saying. I hadn’t thought of it that way. And yes that would indeed increase the size of the chain significantly, if it can be modelled at all. Sergio

Hi

I believe there is a mistake in the problem enunciate. To calibrate the number of rolls needed to get a good statistic sample, I tried to replicate the results in the 6-face dices, and I was in 10,000,000 rolls and I was still not getting the 00 to be the third most visited square. I always get 19 square in that place.

Could you try to simulate the experiment with the 6 faces dices?

Thanks,

Sergio Kristian

Hi Sergio.

I will try this at some point, I just need to get to my own computer with the code on. Kristian

Hi Sergio

I just tested it with six sided dice, at at 1.000.000 simulations I get some variation, but often it comes out right. Some times it uses 19 or 25 instead. If I use 10.000.000 simulations I get the correct answer the 10 times in a row I tried. Jon

Late to the party, but:

Markov chains can handle doubles easily; as Lafortune suggests, you can encode the game state [latex]s = n + 40d[/latex], where [latex]n[latex] is the board position and [latex]d[/latex] is the number of doubles previously rolled, giving you a 120×120 transition matrix. At the end, just sum up the positions that correspond to the same board position. kalhartt looks to have a better solution, but as long as your matrix multiplication is fast enough it doesn’t much matter.

Khaur’s objection is actually a red herring, I think; you’re accounting for all configurations of both decks, and while I’d have to do more thinking to be sure the fixed cycle has no consequence, if there is any it’s of very small magnitude (I didn’t account for it at all, for either deck, and my top five squares had converged by [latex]m^15[/latex]).

Anyway, hopefully useful and of interest. Tom Dalton

I had exactly the same problem as Sergio had. I spent a bit of time trying to work out what I was doing wrong. I found the issue was that I was counting rolling a double as allowing you to continue your move (correctly), but not recording the ‘intermediate’ spaces landed on. I only recorded the final space the player landed on after they had finished throwing doubles (or they rolled the 3rd double and went to jail).

However, from the original problem statement:

“… That is, the probability of finishing at that square after a roll.”

So I changed my algorithm to record stats for the ‘intermediate’ squares the player ends up on in-between throwing doubles, and now I get the correct answer. Jean-Marie Hachey

Table 1 (Project Euler, Problem 84)

Variations of the most popular squares in Monopoly (OUTPUT)
as the size of the Digital Modal String (DMS) vary from 6, 6 to 1, 1.
Calculations done with Kristian’s code (1).

DMS OUTPUT t(ms)
6, 6 102400 79
5, 5 102425 77
4, 4 101524 79
3, 3 101415 78
2, 2 101316 78
1, 1 101214 47 Carl J Appellof

I ran it as a simulation too with 10,000,000 rolls
Thanks to the comments, I realized I had left out the rule about continuing your turn if you roll doubles (unless it’s the third roll of doubles). Until I included that rule, the 3rd most popular square sometimes switched from GO to D3 (Actually, I just got D3 as the 3rd most popular on my last try.)

BTW, the Project Euler statement of the problem doesn’t mention the “doubles, take another turn” rule, and it’s probably insignificant, since you’re going to roll again anyway.

While solving this, I discovered the good random number generators in the C++ std library: mt19937, and also discovered the std::shuffle algorithm, which made shuffling the card decks simple.