Graphics Programming

게임 이론 본문

Season 1/Problem solving

게임 이론

minseoklee 2016. 10. 24. 19:57

문제: https://www.hackerrank.com/challenges/game-of-stones-1


다이나믹 프로그래밍을 시도해보자. dp[i]를 다음과 같이 정의한다.


dp[i] = 돌이 i개 남았고 플레이어 1의 차례다. 플레이어 1이 이길 수 있는가?


dp[n] == true이면 플레이어 1이 이기고, 아니면 플레이어 2가 이긴다. 하지만 이 정의는 플레이어 2를 고려하지 않는다. 식을 하나 더 만들어보자.


dp2[i] = 돌이 i개 남았고 플레이어 2의 차례다. 플레이어 2이 이길 수 있는가?


한 번에 돌을 2개, 3개, 또는 5개 가져갈 수 있으므로 돌이 1~5개 남은 상황에 대해 생각한다.


dp[1] = false (플레이어 1이 선택 불가)

dp[2] = true (2개를 가져가면 0개가 남아서 플레이어 2는 선택 불가)

dp[3] = true (3개를 가져가면 0개가 남아서 플레이어 2는 선택 불가)

dp[4] = true (3개를 가져가면 1개가 남아서 플레이어 2는 선택 불가)

dp[5] = true (5개를 가져가면 0개가 남아서 플레이어 2는 선택 불가)


같은 논리로 dp2[1]에서 dp2[5]까지는 dp[1]에서 dp[5]까지와 값이 같다.


이제 dp[i] (i >= 6)에 대해 생각해보자. 플레이어 1이 돌을 가져가면 남는 돌의 개수는 i-2, i-3, i-5개 중 하나다. 만약 dp2[i-2], dp2[i-3], dp2[i-5] 중 하나라도 false이면 플레이어 1이 이기는 전략이 있다. 플레이어 1은 바로 이 전략을 선택할 것이다.


dp[i] = !dp2[i-2] || !dp2[i-3] || !dp2[i-5]

dp2[i] = !dp[i-2] || !dp[i-3] || !dp[i-5]


따라서 각각의 테스트 케이스를 다음과 같이 해결할 수 있다.


bool dp[101], dp2[101];


void solve() {

    int n;

    cin >> n;


    dp[1] = dp2[1] = false;

    dp[2] = dp2[2] = true;

    dp[3] = dp2[3] = true;

    dp[4] = dp2[4] = true;

    dp[5] = dp2[5] = true;


    for(int i=6; i<=n; i++){

        dp[i] = !dp2[i-2] || !dp2[i-3] || !dp2[i-5];

        dp2[i] = !dp[i-2] || !dp[i-3] || !dp[i-5];

    }


    cout << (dp[n] ? "First" : "Second") << endl;

}


그런데 dp와 dp2의 형태가 완전히 똑같다. 즉 dp[i] = dp2[i]인 것이다. 그러면 dp2를 그냥 dp로 치환할 수 있다.


bool dp[101];


void solve() {

    int n;

    cin >> n;


    dp[1] = false;

    dp[2] = true;

    dp[3] = true;

    dp[4] = true;

    dp[5] = true;


    for(int i=6; i<=n; i++){

        dp[i] = !dp[i-2] || !dp[i-3] || !dp[i-5];

    }


    cout << (dp[n] ? "First" : "Second") << endl;

}


기계적인 변환으로 메모리와 계산량을 반절으로 줄였다. dp[i]의 실제 의미는 다음과 같이 재정의된다.


dp[i] = 돌이 i개 남았을 때, 선택권이 우선인 플레이어가 이길 수 있는가? (여기선 플레이어 1)


위 알고리즘을 바탕으로 실제 게임을 만들어보자. selection[i]를 돌이 i개 남았을 때 이기기 위한 선택의 집합이라 하자. 가령 돌이 i개 남았는데 돌을 2개 또는 5개 선택하면 이길 수 있다면 selection[i] = {2, 5}가 된다.


selection[i]는 위 코드를 응용해 간단히 구할 수 있다.


bool dp[101];

vector<int> selection[101];


void solve() {

    int n;

    cin >> n;


    dp[1] = false;

    dp[2] = true;

    dp[3] = true;

    dp[4] = true;

    dp[5] = true;


    selection[2].push_back(2)

    selection[3].push_back(3)

    selection[4].push_back(3)

    selection[5].push_back(5)


    for(int i=6; i<=n; i++){

        dp[i] = !dp[i-2] || !dp[i-3] || !dp[i-5];

        if(!dp[i-2]) selection[i].push_back(2)

        if(!dp[i-3]) selection[i].push_back(3)

        if(!dp[i-5]) selection[i].push_back(5)

    }


    cout << (dp[n] ? "First" : "Second") << endl;

}


이제 플레이어와 AI가 번갈아 돌을 가져가는 상황을 가정한다. AI의 차례에 돌이 i개 남아있다면 AI는 selection[i]를 본다. selection[i]가 공집합이라면 AI에겐 가망이 없다. 플레이어가 최적의 선택을 안하길 바라며 2, 3, 5개 중 아무거나 가져간다. selection[i]가 공집합이 아니라면 이제 AI에게 필승 전략이 존재한다. selection[i]의 아무 원소나 선택한다.


Game of stones - wonderfl build flash online


Comments