[알고리즘]#10_MiniMax, 최적의 의사 결정

#1. 소개

1. 최대화 플레이어: 이익을 최대화하려는 플레이어
2. 최소화 플레이어: 최대화 플레이어의 이익을 최소화하려는 플레이어

최적의 의사 결정을 위한 재귀 알고리즘. 

 

---

 

#2. 구성

 

1. 게임 트리

게임 상태를 표현하는 트리

 

2. 기저 조건(종료 조건)

1. 게임 종료 함수: 어느 한 쪽이 이겼는지 판단하고, 그 결과를 반환하는 함수
2. 평가 함수: 게임 종료 상태의 수치화, 가장 간단한 형태는 승리/패배/무승부를 각각 +10/-10/0으로 표현

 

3. DFS(백트래킹)

최대? 최소? 누구의 턴인지 체크하고, 현재 상태에 대한 처리 이후 백트래킹 수행.
물론, 현재 최대화 플레이어의 턴이라면 재귀 호출 시 '최소화 플레이어'의 턴으로 설정하고 재귀 호출 진행.

 

4. alpha-beta 가지 치기, 최적화

alpha-beta 가지치기는 Minmax 알고리즘의 최적화 전략, 더 이상 살펴볼 필요가 없는 노드를 미리 제거함으로써 탐색 경로의 수를 줄인다. 최대화 플레이어는 이미 알려진 최소 보장 값(alpha) 보다 최소화 플레이어가 낮은 점수로 제한 가능하다면, 최대화 플레이어는 해당 경로를 절대 선택 하지 않는다. 또, 최소화 플레이어는 이미 알려진 최대 허용 값(beta) 보다 최대화 플레이어가 높은 점수를 얻을 수 있다면, 최소화 플레이 이는 이 경로를 절대 선택 안 한다.

1. alpha : 최대화 플레이어가 확보한 최소 점수 값, "적어도 이 점수는 얻을 수 있다"는 보장
2. beta : 최소화 플레이어가 확보 가능한 최대 점수 값, "이 점수보다 크게 허용하지 않겠다"는 상한

alpha는 매우 작은 값, beta는 매우 큰 값으로 초기화.

최대화 플레이어는 모든 자식 노드를 평가하고, 최대 점수 갱신 이후 alpha = max(alpha, 최대 점수) 업데이트 진행, 그리고 만약 beta <= alpha 라면, 현재 노드의 나머지 자식 노드는 검사할 필요가 없음.

반대로 최소화 플레이어는 모든 자식 노드를 평가하고, 최소 점수 갱신 이후 beta = min(beta, 최소 점수) 업데이트 진행, 그리고 만약 beta <= alpha 라면, 현재 노드의 나머지 자식 노드는 검사할 필요가 없음

 

---

 

#3. 코드

 

1. 3x3 틱택토

#pragma once

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

typedef pair<int,int> p;

//3x3 2차원 배열
int n = 3;
int m = 3;

//게임 트리
vector<vector<int>> board(n, vector<int>(m, 0));

//게임 종료 함수
int checkWinner()
{
    //가로
    for(int i=0; i<m; i++)
    {
        if(board[i][0] != 0 && board[i][0] == board[i][1] && board[i][1] == board[i][2])
            return board[i][0];
    }
    //세로
    for (int j = 0; j < 3; j++) {
        if (board[0][j] != 0 && board[0][j] == board[1][j] && board[1][j] == board[2][j]) {
            return board[0][j];
        }
    }
    //대각
    if (board[0][0] != 0 && board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
        return board[0][0];
    }
    if (board[0][2] != 0 && board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
        return board[0][2];
    }
    //무승부
    bool isFull = true;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 0) {
                isFull = false;
                break;
            }
        }
        if (!isFull) break;
    }

    return isFull ? 2 : 0; // 무승부면 2, 진행 중이면 0
}

vector<p> getAvailableMoves() {
    vector<pair<int, int>> moves;
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 0) {
                moves.push_back({i, j});
            }
        }
    }
    
    return moves;
}

//minimax
int miniMax(int depth, bool IsMaximizing, int alpha, int beta)
{
    //종료 함수
    int result = checkWinner();

    //기저 조건
    if(result == 1) return 10 - depth;
    if(result == -1) return depth - 10;
    if(result == 2) return 0;

    //백트래킹 
    //최대화 플레이어 턴
    if(IsMaximizing)
    {
        int bestScore = INT_MIN;

        //모든 가능한 이동 탐색
        vector<p> moves = getAvailableMoves();
        for(auto move : moves)
        {
            int ny = move.first;
            int nx = move.second;
            
            board[ny][nx] = 1;

            //DFS
            int score = miniMax(depth+1, false, alpha, beta);

            //백트래킹
            board[ny][nx] = 0;

            //최대값 업데이트
            bestScore = max(bestScore, score);

            //알파 값 업데이트
            alpha = max(alpha, bestScore);

            //알파-베타 가지치기, 최적화
            if(beta <= alpha)
                break;
        }
        return bestScore;
    }
    //최소화 플레이어 턴
    else
    {
        int bestScore = INT_MAX;

        //모든 가능한 이동 탐색
        vector<p> moves = getAvailableMoves();
        for(auto move : moves)
        {
            int ny = move.first;
            int nx = move.second;
            
            board[ny][nx] = -1;

            //DFS
            int score = miniMax(depth+1, true, alpha, beta);

            //백트래킹
            board[ny][nx] = 0;

            //최대값 업데이트
            bestScore = min(bestScore, score);

            //beta 값 업데이트
            beta = min(beta, bestScore);

            //알파-베타 가지치기, 최적화
            if(beta <= alpha)
                break;
        }
        return bestScore;
    }
}

 

2. 프로그래머스, 사라지는 발판

#include <string>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

typedef pair<int,int> p;

int n, m;
int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};

struct Result
{
    bool win;
    int moves;
    
    Result(bool _win, int _moves) : win(_win), moves(_moves) {}
};

vector<p> FindNextMoves(p cur, vector<vector<int>>& board)
{
    int cy = cur.first;
    int cx = cur.second;
    
    vector<p> moves;
    
    for(int i = 0; i < 4; ++i)
    {
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        
        if(ny < 0 || ny >= n || nx < 0 || nx >= m || board[ny][nx] == 0) continue;
        
        moves.push_back({ny, nx});
    }
    
    return moves;
}

Result minimax(vector<vector<int>>& board, p cur, p opo)
{
    // 현재 위치가 발판이 없으면 패배
    if(board[cur.first][cur.second] == 0) return Result(false, 0);
    
    // 이동할 곳이 없으면 패배
    vector<p> moves = FindNextMoves(cur, board);
    if(moves.empty()) return Result(false, 0); 
    
    bool canWin = false;
    int minWinMoves = INT_MAX;
    int maxLoseMoves = 0;
    
    for(auto move : moves)
    {
        int cy = cur.first, cx = cur.second;
        
        // 두 플레이어가 같은 위치에 있고, 현재 플레이어가 이동하면 상대방은 바로 패배
        if(opo.first == cy && opo.second == cx)
        {
            canWin = true;
            minWinMoves = min(minWinMoves, 1);
            continue;
        }
        
        // 현재 발판 제거
        board[cy][cx] = 0;
        
        // 상대방 차례 계산
        auto opoResult = minimax(board, opo, move);
        
        // 백트래킹
        board[cy][cx] = 1;
        
        if(!opoResult.win)
        {
            canWin = true;
            minWinMoves = min(minWinMoves, opoResult.moves + 1);
        }
        else
        {
            maxLoseMoves = max(maxLoseMoves, opoResult.moves + 1);
        }
    }
    
    if(canWin)
        return Result(true, minWinMoves);
    else
        return Result(false, maxLoseMoves);
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    n = board.size();
    m = board[0].size();
    
    p a = {aloc[0], aloc[1]};
    p b = {bloc[0], bloc[1]};
    
    auto res = minimax(board, a, b);
    
    return res.moves;
}

 

---