몬테카를로 트리 탐색 (Monte Carlo Tree Search)

바둑처럼 경우의 수가 너무 많아 끝까지 다 계산할 수 없는 게임에서, 컴퓨터는 어떻게 좋은 수를 찾을까? MCTS는 유망해 보이는 수를 위주로 수천 번 무작위로 끝까지 둬 보고(랜덤 플레이아웃), 이긴 비율이 높은 가지를 더 깊이 파고든다. 알파고의 핵심 뼈대가 바로 이 알고리즘이다.

1 · 선택 Selection 2 · 확장 Expansion 3 · 시뮬레이션 Simulation 4 · 역전파 Backpropagation

🎮 틱택토 — 당신(X) vs MCTS(O)

빈 칸을 클릭해 두세요. 당신이 선공입니다.

반복 횟수 2000

탐험 상수 C 1.41

반복 횟수가 많을수록 MCTS는 거의 완벽하게 둡니다(틱택토는 완전 게임이라 최선이면 무승부). C를 0 으로 내리면 탐험을 멈춰 근시안적으로, 너무 높이면 아무 데나 헤맵니다.

🌳 루트에서 뻗은 후보 수 (마지막 탐색 결과)

막대 = 방문 횟수(그 수를 얼마나 깊이 탐색했나) · 숫자 = 승률 Q/N. MCTS는 이 중 가장 많이 방문한 수를 최종 선택합니다.

아직 탐색하지 않았습니다.

// 탐색 로그 — "한 번의 반복 보기"를 누르면 4단계가 여기 찍힙니다

🔄 한 번의 반복 = 4단계

선택(Selection) — 루트에서 시작해, 각 자식의 UCB1 점수가 가장 높은 쪽으로 이미 만들어진 트리를 따라 내려간다. 아직 확장 안 된 노드가 나올 때까지.
확장(Expansion) — 도착한 노드에서 아직 안 둬 본 수 하나를 골라 새 자식 노드를 트리에 붙인다.
시뮬레이션(Simulation / rollout) — 그 자식 상태에서 양쪽 다 완전 무작위로 게임 끝까지 둔다. 승·무·패 결과 하나를 얻는다.
역전파(Backpropagation) — 결과를 방금 지나온 경로의 모든 노드에 되돌려 N += 1, Q += 결과 로 누적한다.

이 4단계를 수천 번 반복하면, 좋은 수 아래에 통계가 두껍게 쌓인다.

⚖️ UCB1 — 활용 vs 탐험

UCB1 = Qᵢ / Nᵢ + C · √( ln N_부모 / Nᵢ )

앞 항(활용): 지금까지 승률이 높은 수를 밀어준다.

뒤 항(탐험): 덜 가 본 수(Nᵢ 작음)일수록 커진다 — 운 나쁘게 초반에 저평가된 수에 기회를 다시 준다.

한 번도 안 가 본 자식은 Nᵢ = 0 → 점수 ∞ 로 취급해 먼저 방문. 이 공식은 "멀티 암드 밴딧" 문제의 후회(regret) 를 이론적으로 최소화한다. MCTS에 이를 쓴 것이 UCT 알고리즘(2006).

🐍 핵심 루프

def mcts(root, n_iter, C): for _ in range(n_iter): node = root # 1) 선택: 완전히 확장된 노드는 # UCB1 최대 자식으로 하강 while node.untried == [] and node.kids: node = max(node.kids, key=lambda k: ucb1(k, C)) # 2) 확장 if node.untried: node = node.expand() # 3) 시뮬레이션 (무작위 플레이아웃) result = rollout(node.state) # 4) 역전파 while node: node.N += 1 node.Q += reward(result, node) node = node.parent # 최종: 가장 많이 방문한 수 return max(root.kids, key=lambda k: k.N).move

💡 왜 미니맥스 대신 MCTS인가?

미니맥스 / 알파–베타의 한계

미니맥스는 트리를 일정 깊이까지 전부 펼치고, 잎 노드를 평가 함수로 채점한다. 바둑은 한 수에 갈래가 ~250개라 몇 수만 내려가도 폭발하고, "이 판이 얼마나 유리한가"를 점수로 매기는 좋은 평가 함수를 만들기가 극도로 어렵다.

MCTS의 세 가지 강점

평가 함수가 필요 없다 — 무작위로 끝까지 둬서 나온 승/패 자체가 평가다.
비대칭 트리 — 유망한 가지에만 계산을 몰아준다. 나쁜 수는 몇 번 방문하고 버린다.
언제든 멈출 수 있다(anytime) — 반복을 많이 돌수록 좋아지지만, 중간에 끊어도 그때까지의 최선을 답으로 낸다.

알파고에서는?

무작위 롤아웃 대신 정책망(policy network) 으로 그럴듯한 수만 시도하고, 롤아웃 승패 대신 가치망(value network) 으로 판을 평가해 MCTS를 안내했다. 뼈대는 그대로 이 4단계다.