MCTS (Monte Carlo Tree Search)

거대한 탐색 트리에서 모든 경로를 다 펼치지 않고, 무작위 시뮬레이션(Monte Carlo rollout)으로 각 행동의 가치를 추정하면서 유망한 가지에 탐색 자원을 집중하는 의사결정 알고리즘.
바둑/체스 같은 거대한 상태공간의 게임에서 다음 수를 고르는 데 쓰이며, RL과 결합해 AlphaGo의 핵심 엔진이 되었다.

왜 필요한가

바둑의 상태공간은 약 $1 0^{170}$ . Minimax처럼 전체 트리를 깊이까지 전부 펼치는 brute-force 탐색은 불가능하다.
핵심 아이디어: 트리를 균일하게 키우지 말고, 좋아 보이는 곳을 더 깊이 파자. 그리고 “좋은지”의 판단은 끝까지 빠르게 시뮬레이션(rollout)한 평균 결과로 근사한다 → 이름 그대로 Monte Carlo.

네 단계 사이클

한 번의 “탐색(iteration)“은 다음 4단계를 반복한다. 시간/연산 예산이 허락하는 만큼 수천~수십만 번 돌린다.

1. Selection (선택)

루트에서 시작해 이미 만들어진 트리 안에서 자식 노드를 골라 내려간다. 이때 단순히 평균 승률이 높은 노드만 고르면(greedy) 잘못 저평가된 가지를 영영 못 살핀다. 그래서 exploration vs. exploitation 균형을 맞추는 UCT 점수로 고른다.

2. Expansion (확장)

더 내려갈 자식이 없는 leaf에 도달하면, 아직 시도하지 않은 행동 하나(또는 여럿)에 대한 새 자식 노드를 트리에 추가한다.

3. Simulation / Rollout (시뮬레이션)

새로 추가한 노드에서부터 게임 끝(terminal)까지 빠르게 플레이아웃한다. 전통적으로는 무작위(random policy) 또는 가벼운 휴리스틱 정책으로 진행. 결과(승/패, 또는 보상 $z$ )를 얻는다.

4. Backpropagation (역전파)

시뮬레이션 결과를 방문 경로를 따라 루트까지 거슬러 올라가며 각 노드의 통계( 방문 횟수 $N$ , 누적 가치 $W$ )에 반영한다.
주의: 신경망 backprop과는 다른 의미 — 여기선 트리 경로를 따라 통계를 갱신하는 것.

사이클이 끝나면, 루트에서 가장 많이 방문된(또는 가치가 가장 높은) 자식을 실제 수로 선택한다. (방문 횟수가 강건한 추정치라 보통 이쪽을 쓴다.)

        [Root]
       /  |   \      ← 1. Selection: UCT로 내려감
     ...  ...  ●     ← 2. Expansion: 새 노드 ● 추가
                |
                ┊    ← 3. Simulation: terminal까지 rollout
              (z=+1)
                ↑
        ← 4. Backprop: 경로의 N, W 갱신

UCT(Upper Confidence bound for Trees)

Selection 단계의 핵심 공식. Multi-Armed Bandit의 UCB1을 트리에 적용한 것.

각 노드(행동) $a$ 에 대해 다음 점수가 가장 큰 자식을 고른다:

U CT (a) = exploitation \frac{W _{a}}{N _{a}} + exploration c \frac{ln N _{p a re n t}}{N _{a}}

$\frac{W _{a}}{N _{a}}$ : 그 노드의 평균 가치(승률) → 좋은 곳을 더 가자(exploitation).
$c \frac{l n N _{p a re n t}}{N _{a}}$ : 덜 방문한 노드일수록 커지는 보너스 → 안 가본 곳도 가보자(exploration). $c$ 는 둘의 균형을 조절하는 상수( $\approx 2$ 가 이론적 기본값).
부모 방문 $N_{p a re n t}$ 가 늘수록 보너스는 천천히 커지고, 자식 방문 $N_{a}$ 가 늘수록 빠르게 줄어든다 → 자연스럽게 유망 가지로 수렴.

Multi-Armed Bandit과의 연결

UCT의 뿌리는 Multi-Armed Bandit 문제(여러 슬롯머신 중 어느 것을 당길까)다. MCTS의 각 노드에서 “어느 자식으로 갈까”를 매번 작은 bandit 문제로 보고, 후회(regret)를 최소화하는 UCB1 전략을 재귀적으로 적용한 것이 UCT. 그래서 MCTS는 **이론적으로 최적 행동으로 수렴(asymptotic convergence)**한다는 보장이 있다.

AlphaGo / AlphaZero에서의 발전 (PUCT)

순수 MCTS의 약점: 무작위 rollout은 분산이 크고, 깊은 게임에선 신뢰도가 낮다. AlphaGo 계열은 두 가지로 이를 대체·보강했다.

Policy network $p (a ∣ s)$ : 어느 수가 유망한지 사전 확률을 줘서 Selection을 가이드 → 탐색 폭을 줄임.
Value network $v (s)$ : 끝까지 rollout하는 대신 상태의 가치를 직접 예측 → 시뮬레이션을 신경망 평가로 대체(분산↓).

Selection 공식도 PUCT로 바뀐다:

P U CT (a) = Q (a) + c \cdot p (a ∣ s) \cdot \frac{\sum _{b} N _{b}}{1 + N _{a}}

exploration 항에 policy prior $p (a ∣ s)$ 가 곱해져, 신경망이 추천한 수를 우선 탐색.
AlphaZero는 사람 기보 없이 self-play + MCTS만으로 policy/value를 학습 → MCTS가 “탐색 기반 정책 개선 연산자(policy improvement operator)” 역할.

정리: 장점과 한계

장점	한계
도메인 지식 없이도 동작(random rollout)	분기 계수(branching factor)가 매우 크면 비효율
언제든 멈춰도 그때까지 최선의 답(anytime)	rollout 분산이 크면 수렴 느림
트리를 비대칭적으로(유망한 쪽만) 키움	메모리에 트리를 저장해야 함
신경망(policy/value)과 자연스럽게 결합	결정론적·완전관측 게임에 가장 잘 맞음

Multi-Armed Bandit — UCT의 이론적 뿌리(UCB1).
Basic RL — MCTS는 plan/search 기반 RL의 대표 사례.
Importance Sampling — off-policy rollout 가치 보정, 분산 감소에 쓰이는 짝꿍 개념.
Playing Atari with Deep Reinforcement Learning

Monte Carlo Tree Search(MCTS)

왜 필요한가

네 단계 사이클

UCT(Upper Confidence bound for Trees)

Multi-Armed Bandit과의 연결

AlphaGo / AlphaZero에서의 발전 (PUCT)

정리: 장점과 한계

Related