Minimax

[https://school.programmers.co.kr/learn/courses/30/lessons/92345]

쉬운 문제라고 생각했다가 엄청 애를 먹은 문제여서 복기 차원에서 포스팅하려고 합니다.

전제 조건

• 나와 상대 모두 모르는 요소가 일절 없음
  • 체스, 오목처럼 서로의 정보가 모두 공개되면 O, 포커같이 비공개 요소가 있으면 X
• 턴제형 게임
• 제로섬 게임 (누군가 이익을 얻으면 다른 누군가는 반드시 그만큼의 손해를 보게 되는 구조로, 승자와 패자의 구분이 명확한 경쟁 상황)
• 나와 상대가 모두 최선을 다해야 하는 상황 (가장 중요)

위 4가지가 모두 충족한다면 사용을 고려해야 합니다.

이름처럼 최솟값과 최대값을 모두 선택하는 알고리즘인데, 예시는 다음과 같습니다.

나 (MAX 플레이어): 어떻게든 나의 점수를 최대화 하는 선택

상대방 (MIN 플레이어): 어떻게든 나의 이익을 최소화하는 선택 (상대방 입장에서는 자신의 이익을 최대화하는 것이지만, 내 기준에서는 내 점수가 깎이는 것이기 때문)

구현 방법

1. 상태 트리 만들기

미래의 모든 경우의 수를 그려보고, 끝에서부터 거꾸로 올라와야 하기 때문에 DFS를 활용. 게임 종료 상태까지 탐색 지점을 이동시키여야 합니다.

2. 바닥(리프)에서 승패 점수 매기기

더 이상 돌을 둘 수 없거나 게임이 끝난 상태에 도달하면 점수를 매깁니다.

해당 문제의 경우에는 최장/최단 턴을 활용했고, 점수가 +-로 나오는 경우도 존재합니다.

3. 밑에서부터 위로 끌어올리기

평소에 DFS를 활용할 때, Token을 증가시키는 것 처럼 밑에서부터 한 칸씩 거슬러 올라오면서 최선의 선택을 결정합니다.

나의 턴(MAX): 아래쪽 경우의 수 중 나에게 가장 유리한(점수가 가장 높은) 값을 골라서 위로 올립니다. (이 문제에서는 승리한 경우의 최소 턴)

상대방의 턴(MIN): 아래쪽 경우의 수 중 나(MAX)에게 가장 불리한 값을 골라서 리턴 (상대방은 바보가 아니므로 당연히 나에게 최악인 수를 둘 것이다”라고 가정)

4. 현재 턴의 최종 결정

이 과정을 반복하여 현재 시점(루트 노드)까지 값이 올라오면, 나는 가장 높은 점수를 보장하는 경로를 선택하면 됩니다.

해당 문제에서는 승리하는 경우의 수가 단 하나라도 존재하면 그 경로만 계속 선택하면 되기 때문에 승리한 값을 선택하고 나머지는 버리면 됩니다. (플레이어는 항상 최선을 다 할테니까요)

이 외에도 최소/최대값을 1번이라도 찾았을 때, 그 값보다 안좋은 방향으로 흘러가는 경우의 수는 미리 가지치기를 하면 최적화 할 수 있습니다.

구현

#include <string>
#include <vector>

using namespace std;

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
vector<pair<int ,int>> pos;
int w, h;

pair<bool, int> dfs(int round, vector<vector<int>>& board)
{
    int turn = round % 2;
    int next = (round + 1) % 2;
    auto [cy, cx] = pos[turn];
    auto [oy, ox] = pos[next];
    
    int defeat = 0;
    if(board[cy][cx] == 0) defeat = 4;
    
    bool isWin = false;
    int winBest = 987654321;
    int loseBest = 0;
    if(defeat < 4)
    {
        pair<bool, int> p;
        for(int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            bool bBlock = false;

            if(nx < 0 || ny < 0 || nx >= w || ny >= h) bBlock = true;
            if(!bBlock && !board[ny][nx]) bBlock = true;
            if(bBlock)
            {
                ++defeat;
                continue;
            }
            
            board[cy][cx] = 0;
            pos[turn] = {ny, nx};
            p = dfs(round + 1, board);
            board[cy][cx] = 1;
            pos[turn] = {cy, cx};
            
            if(!p.first)
            {
                isWin = true;
                winBest = min(winBest, p.second);
            }
            else
            {
                loseBest = max(loseBest, p.second);
            }
        }
    }
    
    if(defeat >= 4) return {false, round};
    if(isWin) return {true, winBest};
    return {false, loseBest};
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) 
{
    w = board[0].size();
    h = board.size();
    pos = { {aloc[0], aloc[1]}, {bloc[0], bloc[1]} };
    return dfs(0, board).second;
}

구현할 때 중요 포인트는 승리/패배 플래그를 정해놓고, 승패가 번갈아가면서 돌아가도록 해야 한다는 것입니다.

A, B 플레이어가 존재할 때, A 플레이어가 (round) 번째 턴이라고 가정하겠습니다.

B(round + 1)가 패배하여 false를 반환하면 A(round)가 승리한 판정이 됩니다. 즉, A는 다시 true를 반환하고 B(round - 1)는 패배한 상태를 리턴 받게 되겠죠.

그리고 또 다시 B(round - 1)는 패배 판정이기 때문에, false를 반환하고 A(round - 2)는 다시 승리 판정이 됩니다. 이 과정이 계속 반복되는 것입니다.

이때, 승/패 여부만 리턴 하는게 아니라, pair<bool, int>로 승/패 여부 + best 값 까지 같이 리턴해야 합니다. 그렇지 않으면 같은 분기 상에 상대가 실수하는 경우같은 잘못된 값이 덮어 씌워져서 저 처럼 애를 먹게되기 때문입니다.