Problem 84 : Monopoly odds (35%)

Description

original

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.

간략해석

모노폴리를 위 그림 판에서 실행된다. CC또는 CH는 도착하면 위의 목록에 있는 카드들이 실행되는데, 각 종류별 카드는 16개이고 이동에 관련된 카드는 각각 2개와 10개이다.

G2J는 Go to Jail로 방문하는 순간 Jail로 간다. 또한 주사위 두개가 같은 수가 나오는 것을 더블이라하는데, 더블을 3번하면 JAIL로 간다.

4면체 주사위 2개로 모노폴리를 실행할때, 가장 많이 가는 3개의 칸을 구하여라. 답의 경우에는 출발지부터 순서를 매겨 각 칸이 나타내는 2자리수를 연결하여 6자리 수를 제출하면된다.

Idea & Algorithm

naive idea

각 칸에서 다음칸으로 갈 확률을 DP또는 BFS로 구해볼까 하였지만 구현하기 귀찮았다. 그래서 실제로 주사위를 1000만번 이상 던진다고 가정하고, 방문하는 칸을 체크하여 시뮬레이션으로 정답을 구했다.

advanced idea

rand함수를 적절히 이용하여 주사위를 던지는 시뮬레이션과 각 카드별 확률을 설정하였다.

그리고 마지막에 구조체 정렬을 이용하여 가장 확률 높은 3 파트를 구했다. 소스 코드 구현시간이 3초내로 돌아가기 때문에 여러번 실험해보았는데 모두 똑같은 결과값이 나왔다.

source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int SZ = 40;
const int RTIME = 10000000;

int mono[SZ], cnt[SZ];
int CC[3] = {2,17,33}, CH[3] = {7,22,36};

int CC_RAND(int n){
    int seed = rand()%16;
    if(seed==0) return 0;
    if(seed==1) return 10;
    return n;
}

int CH_RAND(int n){
    int seed = rand()%16;
    int way[6] = {0,10,11,24,39,5};
    if(seed<6) return way[seed];
    if(seed<8){
        if(seed == 7) return 15;
        if(seed == 22) return 25;
        if(seed == 36) return 5;
        return n;
    }
    if(seed==8){
        if(n==22) return 28;
        else return 12;
    }
    if(seed==9) return n-3;
    return n;
}

void init(){
    for(int i = 0 ; i < 3 ; i++){
        mono[CC[i]] = 1;
        mono[CH[i]] = 2;
    }
}

void game(){
    int pos = 0;
    int db = 0;
    for(int i = 0 ; i < RTIME ; i++){
        int d1 = rand()%4 + 1, d2 = rand()%4 + 1;
        pos = (pos+d1+d2) % SZ;
        if(d1==d2) db++;
        else db = 0;
        if(db==3){
            pos = 10; db = 0;
        }
        if(mono[pos]==1) pos = CC_RAND(pos);
        else if(mono[pos]==2) pos = CH_RAND(pos);
        else if(pos==30) pos = 10;
        cnt[pos]++;
    }
}

int main(){
    srand(time(NULL));
    init(); game();
    vector<pii> v;
    for(int i = 0 ; i < SZ ; i++){
        v.push_back({cnt[i],i});
    }
    sort(v.begin(),v.end(),greater<pii>());
    for(int i = 0 ; i < 3 ; i++){
        cout << v[i].second << ' ';
    }
}

Problem 084