[C/C++] 프로젝트 오일러 #84 모노폴리 확률(몬테카를로)

이 문제를 2015년 10월에 풀었네요.  지금 소스를 보니까, 몬테카를로(Monte Carlo) 기법을 이용해서 풀었네요.  문제가 요구하는대로 구현하고, 결과는 굉장히 많은 수로 무작위 연산을 한 것이죠.  그래도 여전히 결과가 잘 나오는 것으로 보아서는 몬테카를로 기법이 그렇게 나쁘지는 않은 기법이라고 봅니다.

 

monopoly game

https://projecteuler.net/problem=84

 

모노폴리는 널리 알려진 게임입니다.  우리나라에서는 블루마블이라는 게임으로 소개되었습니다.

 

문제를 번역해보았습니다.  (chatGPT로 번역)

게임 "모노폴리"에서 표준 보드는 다음과 같은 방식으로 구성됩니다:

플레이어는 GO 스퀘어에서 시작하며, 6면 주사위의 두 번의 결과를 합산하여 시계 방향으로 진행하는 스퀘어 수를 결정합니다. 다른 규칙이 없을 경우, 각 스퀘어를 방문할 확률은 동일하게 예상됩니다: 2.5%입니다. 그러나 G2J (Go To Jail), CC (공동체 상자), CH (찬스)에 도착하는 것은 이 분포를 변경시킵니다.

G2J뿐만 아니라 CC와 CH 각각 하나의 카드도 직접적으로 감옥으로 이동하라고 지시하면, 플레이어가 연속해서 세 번의 더블을 굴린 경우에는 세 번째 던진 결과로 진행하지 않습니다. 대신 직접 감옥으로 이동합니다.

게임 시작 시 CC와 CH 카드는 섞입니다. 플레이어가 CC나 CH에 도착하면 해당 카드를 각각의 더미 맨 위에서 가져오고, 지침에 따라 행동한 후에는 카드를 더미 맨 아래로 되돌립니다. 각 더미에는 16장의 카드가 있지만, 이 문제에서는 이동에 관련된 카드만 고려하며, 이동과 관련되지 않는 지침은 무시하고 플레이어는 CC/CH 스퀘어에 그대로 머무릅니다.

공동체 상자 (2/16 카드):
GO로 이동
JAIL로 이동
찬스 (10/16 카드):
GO로 이동
JAIL로 이동
C1로 이동
E3로 이동
H2로 이동
R1로 이동
다음 R로 이동 (철도 회사)
다음 R로 이동
다음 U로 이동 (유틸리티 회사)
3개의 스퀘어 뒤로 이동
이 문제의 핵심은 특정 스퀘어를 방문할 확률입니다. 즉, 주사위를 굴린 후 해당 스퀘어에서 게임을 마칠 확률입니다. 이러한 이유로, G2J를 제외하면 G2J에 도달하여 게임을 마칠 확률은 0이며, CH 스퀘어의 확률이 가장 낮을 것입니다. 이는 8개 중 5개가 다른 스퀘어로 이동을 요청하기 때문입니다. 우리는 각 롤마다 플레이어가 최종적으로 도달하는 스퀘어에만 관심을 두겠습니다. "Just Visiting"과 JAIL로 보내는 것에는 차이를 두지 않으며, "감옥에서 나오려면 더블을 굴려야 한다"는 규칙도 무시하고 다음 턴에 돈을 지불하여 감옥에서 나온다고 가정합니다.

GO에서 시작하여 스퀘어를 00부터 39까지 순차적으로 번호를 매기고, 이 두 자리 숫자를 연결하여 해당 스퀘어와 일치하는 문자열을 생성할 수 있습니다.

통계적으로 증명되었듯이, 순서대로 가장 인기 있는 세 개의 스퀘어는 JAIL (6.24%) = 스퀘어 10, E3 (3.18%) = 스퀘어 24, GO (3.09%) = 스퀘어 00입니다. 따라서 이 세 가장 인기 있는 스퀘어는 6자리 모달 문자열 "102400"로 나열할 수 있습니다.

만약 6면이 아닌 4면 주사위를 사용한다면, 6자리 모달 문자열은 어떻게 될까요?

 

사실 정상적으로 풀려면, 모든 경우의 수를 계산해서 가장 확률이 높은 세개의 스퀘어를 골라서 표시해야 합니다.  그러기 위해서는 동적 계획법을 이용해야 합니다.  동적 계획법은 문제를 추상화하고, 분석 가능해야 합니다.  그래서 구현할 수 있는 문제가 제한적입니다.  몬테카를로 기법은 문제를 구현할 수 있다면, 추상화 과정이 필요하지 않습니다.  대신 결과는 일정부분의 오차를 보이게 됩니다.  몬테카를로 기법은 적은수의 시도와 많은수의 시도와 결과가 비슷하다는 장점이 있습니다.

몬테카를로 기법은 문제의 복잡성과 상관없이 비슷한 결과를 도출할 수 있다는 점때문에 인공지능 분야 중 강화학습에 많이 사용되었습니다.  알파고를 비롯하여 많은 강화학습이 몬테카를로 기법을 적용하고 있습니다.

 

제가 몬테카를로 기법을 이용해서 네개의 눈을 가진 주사위를 이용해서 모노폴리를 시뮬레이션한 프로그램입니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>

#define    DICESIDE    4
#define    TRYNUM        1000000000

int dice()
{
    static int doublecount = 0;
    int a = rand()%DICESIDE+1, b = rand()%DICESIDE+1;
    if( a == b ) doublecount++; else doublecount = 0;
    if( doublecount >= 3 ) { doublecount = 0; return 0; }
    return a+b;
}

void solve1()
{
    static int board[40];
    int pos = 0, chance = 0, chest = 0;

    srand(time(0));

    for( int i = 0 ; i < TRYNUM ; i++ )
    {
        int d = dice();
        if( d == 0 ) pos = 10; else pos = (pos+d)%40;
        if( pos == 30 ) pos = 10;
        else if( pos == 2 || pos == 17 || pos == 33 )
        {
            if( chest == 0 ) pos = 0;
            else if( chest == 1 ) pos = 10;
            chest = (chest+1)%16;
        }
        else if( pos == 7 || pos == 22 || pos == 36 )
        {
            if( chance == 0 ) pos = 0;
            else if( chance == 1 ) pos = 10;
            else if( chance == 2 ) pos = 11;
            else if( chance == 3 ) pos = 24;
            else if( chance == 4 ) pos = 39;
            else if( chance == 5 ) pos = 5;
            else if( chance == 6 || chance == 7 ) pos = (pos==7)?15:(pos==22)?25:5;
            else if( chance == 8 ) pos = (pos==22)?28:12;
            else if( chance == 9 ) pos = (pos+37)%40;
            chance = (chance+1)%16;
        }
        board[pos]++;
    }

    int max[4] = { 0 }, last = 1;
    for( int i = 1 ; i < 40 ; i++ )
    {
        int k = last;
        while( k > 0 && board[max[k-1]] < board[i] )
        {
            max[k] = max[k-1];
            k--;
        }
        max[k] = i;
        if( last < 3 ) last++;
    }

    printf("Ans = %02d%02d%02d(%.2f%%, %.2f%%, %.2f%%)\n", 
        max[0], max[1], max[2], 
        (float)board[max[0]]*100/TRYNUM, 
        (float)board[max[1]]*100/TRYNUM, 
        (float)board[max[2]]*100/TRYNUM);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}