몬테카를로 트리 탐색

게임 개발 통계 마지막 수정: 2026-07-23 05:19:48

1. 개요[편집]

다 계산할 수 없으면, 주사위를 굴려 유망해 보이는 쪽에 힘을 몰아준다.

몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)은 게임 트리를 무작위 시뮬레이션으로 표본조사하면서, 통계적으로 유망한 수(move)에 탐색을 집중해 나가는 결정 알고리즘이다. 완전 탐색이 불가능할 만큼 경우의 수가 폭발하는 문제에서, 트리 전체를 다 펼치는 대신 유망한 가지만 골라 깊게 파는 것이 핵심이다.

전통적 미니맥스 알고리즘은 트리의 모든 노드를 평가하려 들고, 그래서 상태가 좋은지 나쁜지를 알려주는 평가 함수(heuristic)를 사람이 손수 설계해 넣어야 했다. 바둑처럼 판세를 숫자로 매기기가 악명 높게 어려운 게임에서 이 접근은 오랫동안 벽에 부딪혔다. MCTS는 발상을 뒤집었다. 판세를 사람이 평가하지 말고, 그 자리에서 게임을 끝까지 무작위로 여러 번 둬 보고 이기는 비율로 대신 평가하자는 것.¹ 이 단순한 아이디어가 컴퓨터 바둑을 인간 프로 수준까지 끌어올렸다.

2. 네 단계 순환[편집]

MCTS는 정해진 시간(또는 반복 횟수) 동안 다음 네 단계를 쉬지 않고 돌린다. 매 반복마다 트리가 조금씩 자라고 통계가 조금씩 쌓인다.

선택(Selection). 루트에서 출발해, 이미 만들어진 트리를 따라 자식 노드를 골라 내려간다. 아직 안 가본 수가 남은 노드에 닿을 때까지. 이때 어느 자식을 고를지가 알고리즘의 두뇌인데, 여기서 UCT(Upper Confidence bound for Trees) 공식이 쓰인다.
확장(Expansion). 도달한 노드에서 아직 시도 안 한 수 하나를 골라 새 자식 노드를 트리에 붙인다. 트리가 딱 한 마디 자라는 순간이다.
시뮬레이션(Simulation). 새로 붙인 노드에서부터 게임이 끝날 때까지 무작위로(또는 가벼운 정책으로) 둬 본다. 이 무작위 대국을 롤아웃(rollout) 또는 플레이아웃이라 부른다. 승패라는 결과 하나가 튀어나온다.
역전파(Backpropagation). 그 승패 결과를 방금 지나온 경로의 모든 노드에 거슬러 올라가며 반영한다. 각 노드의 방문 횟수와 승리 횟수가 갱신되고, 다음 반복의 선택 단계가 이 통계를 참고한다.

정해진 예산이 다 소진되면, 루트에서 가장 많이 방문된(또는 승률이 가장 높은) 수를 실제 착수로 내놓는다.²

3. UCT: 탐색과 활용의 저울[편집]

MCTS의 심장은 선택 단계의 UCT 공식이다. 노드 $i$ 의 점수를 다음으로 매긴다.

\text{UCT}_i = \underbrace{\frac{w_i}{n_i}}_{\text{활용}} + c \, \underbrace{\sqrt{\frac{\ln N}{n_i}}}_{\text{탐색}}

$w_i$ 는 노드 $i$ 를 거친 롤아웃의 승리 수, $n_i$ 는 그 방문 수, $N$ 은 부모의 총 방문 수, $c$ 는 탐색 강도를 조절하는 상수다. 앞 항은 “지금까지 승률이 좋은 수를 더 밀어주자”는 활용(exploitation), 뒤 항은 “덜 가본 수도 한 번쯤 확인해 보자”는 탐색(exploration)이다. 이 둘의 줄다리기는 멀티암드 밴딧(multi-armed bandit) 문제의 고전적 해법에서 곧장 빌려온 것으로, MCTS를 이론적으로 떠받치는 뼈대다. $c$ 를 키우면 넓게 훑고, 줄이면 유망한 가지에 집착한다.

4. 시뮬레이션 단계의 본질[편집]

MCTS라는 이름에서 “몬테카를로”가 붙은 이유는 3단계, 즉 무작위 롤아웃 때문이다. 판세를 정교하게 평가하는 대신, 그 자리에서 무작위로 게임을 끝까지 여러 번 굴려 승률로 근사하는 것 — 이것이 몬테카를로 방법의 정신 그 자체다.

분기 인수 2, 깊이 D의 결정 트리에서 UCT로 선택-확장-롤아웃-역전파를 반복한다. 잎마다 숨겨진 승률이 있고, 정답 수순과 앞부분이 길게 일치할수록 승률이 높게 배치돼 있다. 원 크기는 방문 수 N, 색은 평균 가치 Q, 흰 경로는 이번 반복이 고른 경로다. 탐색이 진행되면 트리는 고르게 자라지 않고 유망한 가지 쪽으로만 비대칭적으로 깊어진다. 탐험 상수 c 슬라이더를 움직이면 같은 게임을 새 c로 다시 탐색하는데, c가 크면 넓고 얕게, 작으면 좁고 깊게 자란다. 노드 수가 상한을 넘으면 방문 수 상위 노드만 그린다.

위 시뮬레이션에서 UCT 점수의 두 항 — 경험 평균(이용)과 방문 부족 보너스(탐험) — 이 겨루면서 방문이 점점 최선의 가지로 쏠린다. 트리가 모든 수를 균등하게 펼치는 대신 승률이 높아 보이는 쪽만 깊게 파고드는 모습이 곧 MCTS가 거대한 게임 트리를 감당하는 방식이다. 표본이 적으면 추정이 요동치고, 표본이 쌓이면 안정된다는 몬테카를로의 큰 그림 위에, “어디에 표본을 쓸 것인가”를 밴딧 문제로 푸는 장치가 얹힌 것. 즉 MCTS는 “똑똑하게 편향된 몬테카를로”인 셈이다.

5. 알파고와 그 이후[편집]

MCTS가 대중의 뇌리에 박힌 결정적 사건은 2016년 알파고(AlphaGo)가 이세돌을 꺾은 대국이다. 알파고는 순수 무작위 롤아웃 대신, 딥러닝으로 학습한 정책망(policy network)으로 선택·확장을 안내하고 가치망(value network)으로 롤아웃을 대체하거나 보강했다.³ MCTS의 골격에 신경망이라는 근육을 붙인 것. 후속작 알파제로(AlphaZero)는 사람의 기보조차 버리고, 자기 자신과의 대국만으로 바둑·장기·체스를 모두 정복했다.

MCTS의 매력은 범용성이다.

완벽정보 보드게임. 바둑, 헥스, 체스 등. 원래의 주 무대.
일반 게임 플레이(GGP)와 실시간 전략. 규칙만 주면 게임별 평가 함수 없이도 그럭저럭 둔다.
계획과 스케줄링. 경우의 수가 폭발하는 조합 최적화, 로봇 경로 계획.
화학·설계 탐색. 합성 경로 탐색처럼 거대한 결정 트리를 뒤지는 문제.

한계도 분명하다. 롤아웃이 무거운 게임에서는 반복당 비용이 크고, 함정 수(한 수만 잘못 둬도 지는 상황)를 무작위 시뮬레이션이 놓치기 쉽다. 그래서 순수 MCTS보다 신경망이나 도메인 지식으로 롤아웃과 선택을 안내하는 하이브리드가 현대의 표준이다. 그럼에도 “다 못 세겠으면 표본으로 근사하고, 유망한 쪽에 예산을 몰아준다”는 MCTS의 철학은, 미니맥스 알고리즘이 60년간 지배하던 게임 AI의 판을 통째로 갈아엎었다.

6. 관련 문서[편집]

처음 이 발상이 나왔을 때 바둑 고수들의 반응은 “무작위로 둬서 나온 승률을 어떻게 믿냐”였다. 그런데 무작위 대국을 수만 판 돌리면 그 평균이 놀랍게도 판세를 꽤 정직하게 반영한다. 개별 롤아웃은 엉망이지만 평균은 현명하다는, 몬테카를로의 오래된 마법. ↩
최종 착수로 “승률 최고”가 아니라 “방문 최다”를 고르는 게 보통이다. 방문이 적은 노드의 높은 승률은 표본이 적어 운일 수 있기 때문. 많이 가본 수가 곧 신뢰할 수 있는 수라는 통계적 겸손이다. ↩
알파고는 롤아웃을 완전히 버리진 않았고, 빠른 롤아웃 정책과 가치망을 섞어 썼다. 알파제로에 와서야 롤아웃을 아예 없애고 가치망 하나로 노드를 평가하는 방식으로 단순해졌다. ↩