[동적 계획법][미니맥스]NUMBERGAME 숫자 게임

1. 항상 최선을 다해 게임을 플레이한다.

 

이 문제는 자신의 차례일 때 항상 최선을 다한다.

 

다음 차례인 상대의 선택을 고려하면서

선택해야한다는 것이다.

 

어떻게 해야 최선일까?

 

자신의 선택한 점수 - 다음턴에 상대방이 선택한 점수

 

가 최대일때가 최선의 선택이 된다.

 

2. 재귀 함수

 

한번 위에 가정한것을 식으로 표현해보자.

 

i는 0~3까지이며 뭘 선택 할 것인지를 나타낸다

 

0: 맨 왼쪽 선택           => myTurn = board[lo]     dlo => +1, dhi => 0

1: 맨 오른쪽 선택        => myTurn = board[hi]     dlo => +0, dhi => -1

3: 맨 왼쪽 두개 삭제    => myTurn = 0               dlo => +2, dhi => 0

4. 맨 오른족 두개 삭제 => myTurn = 0               dlo => +0, dhi => -2

 

 

bestResult(lo, hi) = max( myTurn[i] - bestResult( lo + dlo[i], hi + dhi[i]))

 

 

이 함수는 바텀업 알고리즘을 따른다.

 

그러니까 일단 맨 마지막 노드를 보자

    마지막 선택은 이때까지 선택한것에의해

    남은 선택이 한가지가 될 경우와 선택할께 없는 경우이다.

    그 한가지는 이전턴에 상대방이 2개남은것중에서 다 날렸을 경우  0 과

    남은것 하나를 골랐을 때의 x 가 있다.

 

마지막 노드 이전을 봐보자

    이 노드에서는 0과 x 중에서 상대방의 선택을 강제 할 수 있는 단계이다.

    그러므로 이 단계에서 내가 무엇을 선택햇을경우 그 값과 

    상대방의 값을 뺀 값에서 오차가 큰 값을 선택하는게 최대 인 것이다.

 

그 다음노드도 마찬가지이다.

   자신의 선택다음에 상대방이 최대의 선택을 할때 

   그 최대의 선택이 나에게 제일 최선의 선택이되는 경우 를 선택하는 경우이다.

 

그 이후로도 마찬가지로

    우리는 주어진 상태에서 상대방을 고려한 최고의 선택을 할 수 있게 된다.

 

3. 미니맥스 알고리즘

 

위의 문제풀이는 뺄셈에의해 최대화 와 최소화가 번갈아가며 작동한다.

이와 같은 알고리즘은 미니맥스 알고리즘이라고 부르며 이는 인공지능쪽에서 다루는 알고리즘이다.

 

bestResult()함수를 어떤 플레이어 차례인지 전달하도록 정의를 변경해보자.

 

이 함수는 (A-B)를 리턴하며 A차례일때는 최대값을 찾고

B차례일때는 최소값을 찾도록 함수를 수정해야 할 것이다.

 

 

 

 

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
 
 
const int MIN = -1000000;
//-1000~1000
int board[50];
int cache[51][51];
int dlo[4] = {1, 0, 2, 0};
int dhi[4] = {0, -1, 0, -2}; 
 
int bestResult(int lo, int hi)
{
    if(hi == lo) return 0;
    int &ret = cache[lo][hi];
    if(ret != MIN) return ret;
    int myTurn[4] ={
        board[lo], board[hi-1], 0, 0
    };
 
    for(int i = 0; i < 4; i++)
    {
        if(i >= 2 && hi - lo < 2) break;
        ret = std::max(ret, myTurn[i] - bestResult(lo + dlo[i], hi + dhi[i]));
    }
    return ret;
}
 
int main()
{
    int testCase = 0;
    int boardN = 0;
    
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        std::fill_n(&cache[0][0],51*51, MIN );
        std::cin>>boardN;
        for(int j = 0; j <boardN; j++)
            std::cin>>board[j];
        std::cout<<bestResult(0, boardN)<<"\n";
    }
}

 

NUMBERGAME