MCTS, UCB1, 몬테카를로 시뮬레이션, AlphaGo

출제 빈도: ★★★★★ | 기출: ★131회, ★135회

답안.

Ⅰ. 개요

몬테카를로 시뮬레이션: 확률적 샘플링을 반복하여 복잡한 문제의 해를 추정하는 수치 기법. MCTS(Monte Carlo Tree Search): 게임/결정 트리 탐색에서 몬테카를로 방법을 적용한 휴리스틱 탐색 알고리즘. AlphaGo의 핵심.

Ⅱ. 핵심 구성요소

I. 몬테카를로 시뮬레이션 기초
   - 무작위 샘플링 반복 → 통계적 추정
   - 예시: π 추정 (원 안에 랜덤 점 → π/4 비율)
   - 복잡한 확률 공간 탐색에 효과적

II. MCTS 동작 원리
   
   [MCTS 루프]
   루트 노드 (현재 게임 상태)
      ↓ ① Selection: UCB1 = win/n + C√(ln N/n)
   유망 노드 선택
      ↓ ② Expansion: 미탐색 자녀 노드 생성
   새 노드 추가
      ↓ ③ Simulation (Rollout): 랜덤 플레이아웃
   게임 결과 (승/패)
      ↓ ④ Backpropagation: 결과 역전파
   경로 상 모든 노드 win/n 업데이트
      ↓ 반복 (시간 허용 시까지)
   최다 방문 노드 선택 → 최적 행동
   
   UCB1 (Upper Confidence Bound):
   UCB1 = (W/N) + C × √(ln(N_parent)/N)
   - W/N: 승률 (탐욕)
   - √(ln N_parent/N): 미탐색 보너스 (탐험)
   - C: 탐험-탐욕 균형 파라미터

III. 기존 탐색 vs MCTS 비교
   | 방법      | 깊이     | 평가함수  | 도메인 |
   |----------|---------|---------|------|


해당 키워드의 기술적 구성요소와 동작 원리를 서술한다.

### Ⅲ. 특징 및 비교

핵심 기술의 장단점과 유사 기술과의 차이를 분석한다.

### Ⅳ. 적용 사례

실무 환경에서의 적용 사례와 기대효과를 제시한다.

### Ⅴ. 전망

최신 기술 동향과 향후 발전 방향을 서술한다.