Monte Carlo Tree Search (MCTS): 게임 AI의 혁신을 이해하다
확률과 탐색의 만남, 알파고를 만든 핵심 알고리즘
바둑에서 인간을 이긴 알파고, 체스에서 무적을 자랑하는 AI들의 비밀은 무엇일까요? 그 핵심에는 Monte Carlo Tree Search (MCTS, 몬테카를로 트리 탐색)라는 혁신적인 알고리즘이 있습니다. 카지노 도시의 이름을 딴 이 알고리즘이 어떻게 게임 AI의 판도를 바꿨는지 알아보겠습니다.
MCTS란 무엇인가?
Monte Carlo Tree Search는 게임 인공지능에서 의사결정을 내릴 때 사용되는 탐색 알고리즘입니다. 핵심 아이디어는 간단합니다: "많이 시뮬레이션할수록 좋은 수를 찾는다"
모든 경우를 다 계산하는 완전 탐색 대신, 확률적 시뮬레이션(몬테카를로 방법)을 사용해 유망한 수를 점점 더 깊이 탐색하는 방식입니다.
"Monte Carlo"의 어원
Monte Carlo는 모나코 공국의 유명한 카지노 도시 이름입니다. 연구자들이 확률적 시뮬레이션 방법을 설명하면서 "마치 카지노에서 무작위로 공을 돌리는 것과 같다"는 비유로 이름을 붙였습니다. 즉, 난수를 이용한 확률적 계산 방법을 의미합니다.
MCTS의 4단계 핵심 알고리즘
MCTS는 다음 4단계를 반복적으로 수행합니다:
1. Selection (선택)
현재까지 구축된 탐색 트리에서 루트부터 시작하여, UCT(Upper Confidence Bound for Trees) 공식을 사용해 자식 노드를 선택합니다.
UCT 공식:
UCT = (승리횟수/방문횟수) + c × √(ln(부모방문횟수)/방문횟수)이 공식은 "탐험(exploration)"과 "활용(exploitation)"의 균형을 맞춥니다:
- 앞부분: 승률이 높은 수를 선호 (활용)
- 뒷부분: 아직 충분히 시도하지 않은 수에 보너스 (탐험)
2. Expansion (확장)
선택된 노드에서 아직 시도되지 않은 새로운 자식 노드(새로운 상태)를 트리에 추가합니다.
3. Simulation (시뮬레이션, 롤아웃)
새로 추가된 상태에서 무작위 플레이 또는 정책을 사용하여 게임을 끝까지 진행하고, 결과(승패, 점수)를 기록합니다.
4. Backpropagation (역전파)
시뮬레이션 결과를 선택 경로에 있는 모든 노드에 반영합니다. 승리 시 해당 경로 노드들의 승리 횟수와 방문 횟수를 업데이트합니다.
직관적 예시: 틱택토에서의 MCTS
간단한 틱택토(삼목게임)로 MCTS 동작을 살펴보겠습니다.
현재 상황 (O 차례):
X | O |
---------
| X |
---------
| | 시뮬레이션 과정
- Selection: UCT 공식으로 탐색할 칸을 선택 (예: 왼쪽 아래)
- Expansion: 새로운 보드 상태를 트리에 추가
- Simulation: 그 상태에서 무작위로 게임 끝까지 진행
- Backpropagation: 결과를 상위 노드들에 반영
UCT 점수 계산 예시
수천 번의 시뮬레이션 후:
| 위치 | 방문 횟수 | 승리 횟수 | 승률 | UCT 점수 |
|---|---|---|---|---|
| 왼쪽 아래 | 10 | 7 | 0.7 | 1.16 |
| 가운데 아래 | 10 | 2 | 0.2 | 0.66 |
| 오른쪽 아래 | 10 | 1 | 0.1 | 0.56 |
→ 왼쪽 아래가 최고 점수로 선택됩니다.
MCTS의 장점과 한계
장점
- 대규모 상태 공간: 바둑처럼 완전 탐색이 불가능한 경우에 효과적
- 점진적 개선: 시간이 많을수록 더 정확한 결과
- 평가 함수 불필요: 순수 시뮬레이션만으로도 강력한 성능
- 범용성: 다양한 게임과 의사결정 문제에 적용 가능
한계
- 시뮬레이션 품질 의존성: 무작위가 너무 단순하면 성능 저하
- 수렴 속도: 매우 깊거나 확률적 요소가 큰 게임에서는 느릴 수 있음
- 메모리 사용량: 트리 확장에 따른 메모리 요구량 증가
MCTS와 대형 언어 모델 (LLM)
최근에는 MCTS를 텍스트 생성과 추론에도 적용하려는 시도들이 있었습니다.
기본 아이디어
- 상태: 현재까지 생성된 텍스트
- 행동: 다음 토큰 또는 추론 단계
- 액터 모델: 다음 행동을 제안하는 정책
- 밸류 모델: 현재 상태의 가치를 평가하는 심판
왜 어려운가?
- 분기 폭 폭증: 한 토큰당 수십-수백 개의 후보, 문장 길이만큼 기하급수적 증가
- 가치 평가의 어려움: "좋은 중간 추론 과정"에 대한 객관적 평가 기준 부재
- 계산 복잡도: 매번 MCTS 실행으로 인한 높은 리소스 비용
제한적 성공
추론 단계에서 이미 훈련된 가치 모델을 활용한 후보 재랭킹이나 제한적 탐색은 어느 정도 효과를 보였지만, 대규모 자기-탐색 학습 파이프라인으로는 효율 대비 이득이 작았습니다.
알파고에서 배우는 MCTS의 핵심
액터-크리틱 구조
- 액터 모델: "무엇을 할지" 결정하는 정책 네트워크
- 밸류 모델: "현재 상태가 얼마나 좋은지" 평가하는 가치 네트워크
성공 요인
- 명확한 보상: 바둑에서는 승패가 분명
- 적절한 분기 수: 한 턴당 합리적인 후보 수
- 안정적인 평가: 게임 상태를 비교적 정확히 평가 가능
현대적 활용 분야
- 게임 AI: 체스, 쇼기, 포커 등 복잡한 게임
- 강화학습: 플래닝과 탐색이 필요한 환경
- 의사결정 시스템: 불확실성이 높은 선택 상황
- 최적화 문제: 전역 최적해 탐색이 어려운 경우
결론: 확률과 지능의 만남
MCTS는 "무작위로 여러 번 시뮬레이션하여 최선의 선택을 찾는" 단순한 아이디어에서 시작되었지만, 알파고의 성공으로 그 가능성을 증명했습니다.
완벽한 해답을 구할 수 없는 복잡한 문제에서 확률적 탐색과 점진적 학습을 통해 근사 최적해를 찾는 MCTS는, 인공지능이 불확실성 하에서 지능적 판단을 내리는 핵심 메커니즘 중 하나입니다.
비록 자연어 처리 분야에서는 여전히 한계가 있지만, 게임 AI와 의사결정 시스템에서는 이미 검증된 강력한 도구로 자리잡았습니다. MCTS의 진화는 계속되고 있으며, 새로운 응용 분야에서의 혁신을 기대해볼 수 있습니다.
