> [!abstract] Introduction > 체스나 바둑처럼 경우의 수가 폭발적으로 많은 게임에서, 모든 수를 전부 계산하는 것은 현실적으로 불가능합니다. 그렇다면 AI는 어떻게 "좋은 수"를 찾아낼 수 있을까요? 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)은 **무작위 시뮬레이션의 통계적 힘**과 **트리 탐색의 구조적 체계**를 결합하여 이 문제에 답하는 알고리즘입니다. 도메인 지식 없이도 작동할 수 있고, AlphaGo가 인간 세계 챔피언을 꺾은 핵심 엔진이기도 합니다. 이 글에서는 MCTS가 무엇이고, 어떤 단계로 작동하며, 왜 강력한지를 차근차근 살펴봅니다. # 미니맥스 알고리즘의 한계 어떤 게임을 수행하는 컴퓨터 유저를 설계할 때, 기존의 핵심 알고리즘은 [[Minimax Algorithm|미니맥스 알고리즘]]이었다. 미니맥스 알고리즘에서는 상대방이 항상 최선의 수를 둔다고 가정하고 게임 트리를 끝까지 탐색하여 최적의 수를 계산하며, [[Minimax Algorithm#Alpha-Beta Pruning|Alpha-Beta Pruning]]을 적용하면 탐색해야 할 노드 수를 상당히 줄일 수도 있다. 하지만 이 접근법은 두 가지 근본적인 한계를 가지고 있다. 1. **게임의 어떤 상태를 표현하는 상태 공간이 지수적으로 폭발하는 도메인에서는 사실상 작동하지 않는다.** 체스의 게임 트리 복잡도는 약 $10^{123}$이고, 바둑은 약 $10^{360}$에 달하기 때문에 아무리 가지치기를 해도 이 규모의 트리를 전수 조사하는 것은 무리다. 2. **좋은 평가 함수(Evaluation Function)를 설계하기 어려운 도메인이 존재한다.** 미니맥스는 탐색 깊이에 한계가 있으므로 중간 상태의 가치를 수치로 매기는 평가 함수가 필수적인데, 바둑처럼 형세 판단이 극도로 복잡한 게임에서는 평가함수를 설계하기 매우 어렵다. MCTS는 이 두 가지 한계를 우회하는데, 평가 함수 대신 **무작위 시뮬레이션의 결과**를 활용하고, 전체 트리를 균등하게 탐색하는 대신 **유망한 경로에 계산 자원을 집중한다.** # MCTS의 역사: 몬테카를로 방법에서 UCT까지 MCTS는 하루아침에 만들어진 것이 아닌 수십 년에 걸친 연구의 융합 결과다. ## 몬테카를로 방법 MCTS의 출발점은 1940년대의 [[몬테카를로 방법|몬테카를로 방법(Monte Carlo Method)]]이다. 해석적으로 풀기 어려운 문제에 무작위 샘플링으로 근사해를 구하는 이 접근법은, 게임의 끝까지 무작위로 플레이한 결과를 모아 상태의 가치를 추정하는 기대 결과 모델*Expected-Outcome Model*을 탄생시켰다. ### 기대 결과 어떤 게임 상태의 가치를 **그 상태에서 양측이 무작위로 끝까지 두었을 때, 최종적으로 승리할 확률**로 정의하는 것이 바로 기대 결과다. 기대 결과는 크게 두가지 방법으로 정의되는데, 게임이 끝날 때까지 완전히 무작위로 수를 이어가는 과정을 수천 번 반복해 전체 시뮬레이션 횟수 중 승리한 횟수의 비율을 구하는 방식이 있고, 지도 학습*Supervised Learning* 접근법을 도입해 미리 데이터를 생성하고 선형회귀로 데이터를 학습시킨 다음 실제 게임을 할 때는 학습된 평가 함수를 사용하는 방식이 있다. 하지만 양 플레이어가 무작위로 수를 둔다는 가정에 기반하기 때문에 이 방식이 항상 최적의 수를 대변하지는 못한다는 한계 또한 존재했다. ### 2006 결정적 전환점은 **2006년**에 찾아왔다. 레미 쿨롬(Rémi Coulom)이 몬테카를로 시뮬레이션과 트리 탐색을 체계적으로 결합한 기법에 "Monte Carlo Tree Search"라는 이름을 붙이고, 레벤테 코치스(Levente Kocsis)와 차파 셰페스바리(Csaba Szepesvári)는 다중 슬롯 머신*Multi-Armed Bandit* 문제의 해법인 UCB(Upper Confidence Bound)를 트리 탐색에 적용한 **UCT(Upper Confidence Bounds for Trees)** 알고리즘을 발표했다. # MCTS의 4단계 프로세스 MCTS의 핵심은 선택*Selection* → 확장*Expansion* → 시뮬레이션*Simulation* → 역전파*Backpropagation*라는 네가지 단계로 이루어지는 과정의 반복이다. 이 루프를 시간이 허용하는 한 최대한 반복 수행하고, 가장 많이 방문된 자식 노드에 해당하는 수를 최종적으로 선택하게 된다. ![[MCTSProcess.png]] ## 선택(Selection) 처음에는 루트 노드에서 출발해 이미 확장된 자식 노드 중 하나를 골라 아래로 내려가는 과정을 리프 노드에 도달할 때까지 반복한다. 이때 어떤 자식을 고를지가 중요한데, 여기에는 탐험*Exploration*과 활용*Exploitation*이라는 두 가지 상충되는 목표가 있다. 활용은 지금까지 승률이 높았던 노드를 다시 선택하는 것이고, 탐험은 아직 충분히 살펴보지 않은 노드를 선택하는 것이다. 승률만 쫓으면 더 좋은 수를 놓칠 수 있고, 탐험만 하면 이미 발견한 좋은 수를 깊이 파고들지 못한다. ![[MCTSSelection.png]] ### 보상을 최대화하는 방법은? #### Greedy Algorithm 그래서 탐색과 활용 사이에서 균형을 잘 잡아 보상을 최대화하는 접근법이 필요하다. 첫번째로 생각할 수 있는 접근법으로는 그리디 알고리즘이 있다. 당장 가장 큰 보상을 주는 선택지를 고르는 방법인데, 어떤 시점에서 어떤 선택지를 골랐을 때 얻을 기대 보상을 실제로 파악할 방법이 없으니 일단 시뮬레이션을 돌린 뒤 어떤 선택지를 골랐을 때의 보상을 모아 평균을 계산한 다음, 그 값을 실제 기대 보상이라고 가정하고 그 값을 최대로 만드는 선택지를 고르는 방법이다. #### $\epsilon$ - Greedy Algorithm 하지만 그리디 알고리즘은 너무 적은 시도로 확신해버린다. 이제 여기에 변수를 하나 더 추가해보자. 기본 아이디어는 전체 시행 중 ε 만큼의 비율은 아무 선택지나 무작위로 선택하는 것이다. 이러한 탐색 시행도 모든 시행에서 무작위로 (ε이라는 확률로) 선택되므로, 활용 시행과 완전히 섞여 진행되며 나머지 (1 − ε) 비율의 시행에서는 지금까지 평균 보상이 가장 좋은 선택지를 고르게 된다. 이 접근법을 $\epsilon$ - 그리디 알고리즘이라 부른다. 이 방법에서는 잘못된 선택지에 영원히 갇히지 않는다는 것이 보장되며, 또한 활용 단계가 일찍 시작되기 때문에 대부분의 시간 동안 최선의 전략을 사용할 가능성이 높다. 약간의 변칙을 주기는 하지만 그래도 이렇게 무작위로 하는 방법이 똑똑한 방법 같지는 않다. ### UCT 알고리즘 이 딜레마를 수학적으로 해결한 것이 **UCT(Upper Confidence Bounds for Trees)** 알고리즘이다. 부모 노드 $s$에서 자식 노드 $i$를 선택할 때의 점수는 다음과 같다. $UCT_i = \underbrace{\frac{w_i}{n_i}}_{\text{활용(Exploitation)}} + \underbrace{C \sqrt{\frac{\ln N_p}{n_i}}}_{\text{탐험(Exploration)}}$ 각 기호의 의미는 다음과 같다. - $w_i$ : 자식 노드 $i$의 누적 보상 (예: 승리 횟수) - $n_i$ : 자식 노드 $i$의 방문 횟수 - $N_p$ : 부모 노드의 총 방문 횟수 - $C$ : 탐험 상수. 이론적 기본값은 $\sqrt{2}$이며, 도메인에 따라 조정한다. **활용 항** $w_i / n_i$는 해당 노드의 평균 승률이며, 승률이 높을수록 점수가 올라간다. **탐험 항**은 방문 횟수가 적은 노드일수록 커지는데, 부모는 계속 방문되는데($N_p$ 증가) 특정 자식의 방문 횟수($n_i$)가 정체되면 분모는 작고 분자는 커지므로 탐험 점수가 상승하여 결국 그 노드가 선택되는 원리다. 이런 메커니즘 덕분에 MCTS는 지엽적인 최적해에 빠지지 않고 탐색 공간을 점진적으로 커버하게 되는 것이다. 또한 UCT 기반 탐색이 충분한 시간이 주어지면 [[Minimax Algorithm|미니맥스]] 값으로 수렴함이 이론적으로 증명되어 있기 때문에 이 방법은 미니맥스와 똑같은 결과값을 내면서 훨씬 효율적인 방법이 되는 셈이다. ### 확장 (Expansion) ![[MCTSExpansion.png]] 선택 단계에서 도달한 리프 노드가 게임의 종료 상태가 아니라면, 그 노드에서 가능한 선택지 중 하나에 해당하는 새로운 자식 노드를 트리에 추가해 트리를 확장시킨다. 메모리 효율성을 위해 반복할 때마다 자식 노드를 하나만 생성하는 것이 일반적이며, 일부 구현에서는 방문 횟수가 특정 임계값을 넘은 노드에서만 확장을 수행하여 트리의 폭발적 성장을 억제하기도 한다. ### 시뮬레이션 (Simulation) 이제 새로 추가된 노드에서 게임이 끝날 때까지 가상의 대국을 진행한다. 이를 롤아웃(Rollout) 또는 플레이아웃(Playout)이라고 부른다. ![[MCTSSimulation.png]] 가장 단순한 형태는 양측이 완전히 무작위로 수를 두는 것이다. 도메인 지식이 전혀 필요 없다는 것이 큰 장점이지만, 게임의 실제 양상을 반영하지 못하는 한계가 있다. 이를 보완하기 위해 간단한 패턴 인식이나 즉각적 위협 회피 같은 가벼운 휴리스틱을 적용하는 가벼운 정책(Light Policy)을 쓰기도 한다. 다만, 시뮬레이션 정책이 지나치게 정교하면 편향을 초래하거나 연산 속도가 떨어질 수 있으므로 속도와 품질 사이의 균형을 찾는 것이 중요하다. ### 역전파 (Backpropagation) ![[MCTSBackpropagation.png]] 시뮬레이션이 끝나면 그 결과(승리, 패배, 무승부 등)를 확정하고, **리프 노드에서 루트 노드까지 경로를 거슬러 올라가며 모든 노드의 통계를 갱신**한다. 구체적으로는, 경로 상의 각 노드 $i$에 대해 새로운 값을 대입한다. $n_i \leftarrow n_i + 1, \quad w_i \leftarrow w_i + \Delta$ 여기서 $\Delta$는 시뮬레이션 결과값이다. 2인 제로섬 게임에서는 트리의 레벨마다 플레이어가 바뀌므로, 보상의 부호를 반전시키거나 각 플레이어 관점에서 승패를 기록해야 한다. 이러한 반복을 통해 각 노드의 평균 가치 $Q_i = w_i / n_i$는 해당 상태의 기대 가치에 점차 수렴하게 한다. MCTS는 이 네가지 단계를 계속 반복하며 전체 플레이아웃 중에서 가장 많이 선택된 선택지를 다음 행동으로 결정한다. ### 의사코드 MCTS의 의사코드는 아래와 같다. $ \begin{array}{l} \textbf{function } \text{Monte-Carlo-Tree-Search}(state) \textbf{ returns } \textit{an action} \\ \quad tree \leftarrow \text{Node}(state) \\ \quad \textbf{while } \text{Is-Time-Remaining}() \textbf{ do} \\ \quad\quad leaf \leftarrow \text{Select}(tree) \\ \quad\quad child \leftarrow \text{Expand}(leaf) \\ \quad\quad result \leftarrow \text{Simulate}(child) \\ \quad\quad \text{Back-Propagate}(result, child) \\ \quad \textbf{return } \text{the move in Actions}(state) \text{ whose node has highest number of playouts} \end{array} $ # MCTS 응용편 기본적인 MCTS는 복잡한 실제 문제에서 수렴이 느리거나 메모리 효율이 떨어질 수 있기 때문에, 이를 보완하는 몇 가지 대표적인 기법이 존재한다. ## RAVE (Rapid Action Value Estimation) ![[RapidActionValueEstimationExample.png]] MCTS 초기에는 각 노드의 방문 횟수가 적어 UCT 값의 신뢰도가 떨어지지만, RAVE는 AMAF(All-Moves-As-First) 휴리스틱을 활용하여 이 문제를 해결한다. 핵심은 특정 상태에서 좋은 수는 나중에 두더라도 여전히 좋을 가능성이 높다는 전제 하에 어떤 서브 트리 $\tau(s)$에서 행동 $a$가 가지는 가치가 비슷할 것이라고 가정하는 것이다. 이 가정을 전제로 RAVE에서는 $s$에서 시작하는 모든 시뮬레이션에서 시점과 관계없이 $a$의 가치를 집계한다. 그림에서 파란색 영역이 바로 $a$의 가치가 집계되는 영역이다. 각 노드는 일반 MC 값[^mc] 외에 AMAF 값을 별도로 유지하며, 이 둘의 적절히 배합해 RAVE 가치를 산출한다. $V_{RAVE} = (1 - \beta) \cdot V_{MC} + \beta \cdot V_{AMAF}$ $\beta$가 두 값의 혼합 비율을 결정하며, 방문 횟수가 적을 때는 1에 가까워 AMAF 정보에 의존하다가 방문 횟수가 늘면 0으로 수렴하여 정밀한 MC 정보를 신뢰하게 된다. 이를 통해 학습 초기의 수렴 속도를 크게 높일 수 있다. ## FPU (First Play Urgency) UCT 알고리즘은 미방문 노드의 값을 무한대로 취급하므로 모든 자식을 최소 1회 방문하게 만든다. 바둑처럼 분기 계수가 수백에 달하는 경우 이것만으로도 막대한 횟수의 시뮬레이션이 이루어져야 하기 때문에, FPU는 미방문 노드에 무한대 대신 **고정된 기본값**(예를 들어, 부모 노드의 가치에서 일정량을 뺀 값)을 부여해 가망이 없는 수에 대한 불필요한 초기 탐색을 줄인다. ## 병렬화 전략 MCTS의 성능은 단위 시간당 시뮬레이션 횟수에 비례하기 때문에 멀티코어 환경에서의 병렬화는 필수적이며, 대표적으로 세 가지 방식이 있다. | 방식 | 핵심 아이디어 | 특징 | | ------------------------ | -------------------------- | --------------------------- | | **Leaf Parallelization** | 리프 노드에서 여러 스레드가 동시에 롤아웃 수행 | 구현이 간단하지만 트리 탐색 경로의 다양성은 부족 | | **Root Parallelization** | 독립된 트리를 각각 생성 후 통계 병합 | 스레드 간 통신 오버헤드가 적지만 중복 탐색 가능 | | **Tree Parallelization** | 하나의 공유 트리를 동시 탐색 | 정보 공유가 즉각적이나 동시 접근 제어가 필요 | Tree Parallelization에서는 가상 손실*Virtual Loss* 기법이 주로 사용되는데, 이는 한 스레드가 노드를 선택해 내려갈 때 즉시 가상의 패배를 기록해 다른 스레드가 같은 경로를 중복 선택하는 것을 방지하는 기법이다. ## 심층 신경망과의 결합 MCTS는 딥러닝과 결합되면서 진정한 도약을 이루어냈다. ### AlphaGo 2016년 이세돌 9단을 꺾은 알파고는 두 가지 신경망을 MCTS에 통합했다. 정책 네트워크*Policy Network*는 유망한 수의 확률 분포를 출력하여 선택 단계에서 탐색의 폭을 줄이는 역할을 했고, 가치 네트워크*Value Network*는 현재 상태의 승률을 직접 예측하여 롤아웃을 끝까지 하지 않아도 노드의 가치를 평가할 수 있게 했다. ### AlphaZero 알파고의 발전된 모델인 알파제로는 한 발 더 나아가 설계를 극도로 단순화했는데, 정책과 가치를 하나의 통합 신경망에서 동시에 출력하도록 하고 무작위 롤아웃 단계를 완전히 제거해 신경망의 가치 예측이 롤아웃을 대체하도록 했다. 롤아웃을 없앤 대신, 선택 단계에서는 UCT 대신 변형된 PUCT*Predictor + UCT* 공식을 사용한다. $PUCT(s, a) = Q(s, a) + C_{puct} \cdot P(s, a) \frac{\sqrt{\sum_b N(s, b)}}{1 + N(s, a)}$ 여기서 $P(s, a)$는 신경망이 예측한 사전 확률이다. 탐색 초기에는 신경망의 직관($P$)을 따르고, 시뮬레이션이 쌓이면 실제 탐색 결과($Q$)를 신뢰하도록 자연스럽게 전환된다. 인간이 학습에 끼어드는 일 없이 스스로 학습하면서도 초인적 성능을 달성했다는 점에서, AlphaZero는 MCTS가 범용적인 정책 개선 연산자로 기능할 수 있음을 보여준 사례다. ## MCTS vs Minimax | 비교 항목 | MCTS | [[Minimax Algorithm\|Minimax(Alpha-Beta)]] | | ---------- | --------------------- | ------------------------------------------ | | **핵심 원리** | 확률적 시뮬레이션 및 통계적 추정 | 전수 조사 및 가지치기 | | **평가 함수** | 불필요 (시뮬레이션 결과를 활용) | 필수 (도메인 특화 설계 필요) | | **탐색 형태** | 비대칭적 (유망한 경로에 집중) | 대칭적 (깊이 제한 내 균등 탐색) | | **적합 도메인** | 분기 계수가 크고 평가가 어려운 도메인 | 분기 계수가 작고 전술적 수읽기가 중요한 도메인 | | **대표 사례** | 바둑, 로봇 제어, 범용 게임 플레이 | 체스, 체커 | | **약점** | 탐색 사각지대 | 상태 공간 폭발 | MCTS의 대표적인 약점은 **탐색 사각지대**다. 확률적 평균값에 의존하기 때문에, 99번 이기더라도 1번의 치명적인 함정(즉시 패배하는 경로)을 "평균적으로 좋은 수"로 오판할 수 있다. 미니맥스는 모든 경우를 검토하므로 이런 함정을 완벽히 감지하지만, MCTS는 샘플링되지 않은 경로를 놓칠 위험이 있다. 이를 극복하기 위해 롤아웃이나 확장 단계에서 얕은 깊이의 미니맥스 탐색을 수행하는 **하이브리드 기법**이 연구되고 있다.[^hybrid] --- ## 출처 - Russell, S.J. and Norvig, P. (2021) *Artificial intelligence: a modern approach*. 4th edn. Harlow: Pearson. (Chapter 5: Adversarial Search and Games) - Browne, C.B. *et al.* (2012) 'A survey of Monte Carlo tree search methods', *IEEE Transactions on Computational Intelligence and AI in Games*, 4(1), pp. 1–43. - Kocsis, L. and Szepesvári, C. (2006) 'Bandit based Monte-Carlo planning', in *Machine Learning: ECML 2006*. Berlin: Springer, pp. 282–293. - Coulom, R. (2007) 'Efficient selectivity and backup operators in Monte-Carlo tree search', in *Computers and Games*. Berlin: Springer, pp. 72–83. - Silver, D. *et al.* (2016) 'Mastering the game of Go with deep neural networks and tree search', *Nature*, 529(7587), pp. 484–489. - Silver, D. *et al.* (2017) 'Mastering the game of Go without human knowledge', *Nature*, 550(7676), pp. 354–359. - Silver, D. *et al.* (2018) 'A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play', *Science*, 362(6419), pp. 1140–1144. - [[추천시스템] 2. Multi-Armed Bandit (MAB)](https://m.blog.naver.com/nilsine11202/221912267111) - [Monte-Carlo Tree Search - Mastering Reinforcement Learning](https://gibberblot.github.io/rl-notes/single-agent/mcts.html) - Baier, H. and Winands, M.H.M. (2015) ‘MCTS-Minimax Hybrids’, _IEEE Transactions on Computational Intelligence and AI in Games_, 7(2), pp. 167–179. [^mc]: 몬테카를로 시뮬레이션을 통해 트리의 각 노드를 평가한 값이다. [^hybrid]: Baier, H. and Winands, M.H.M. (2015) ‘MCTS-Minimax Hybrids’, _IEEE Transactions on Computational Intelligence and AI in Games_, 7(2), pp. 167–179. 에서 하이브리드 기법에 대한 연구를 확인할 수 있다.