MCTS — UCB1을 트리에 적용하면
👋 PART 3의 클라이맥스
지난 두 챕터에서 만든 부품들 — rollout(무작위 끝까지)과 UCB1(탐험 vs 활용). 이걸 조합하면 마법이 일어남.
이 챕터에서 MCTS (Monte Carlo Tree Search) 완성. 2006년 이후 모든 강한 컴퓨터 바둑의 기반 알고리즘.
지난 챕터의 한계 — UCB1은 첫 수에만 적용되고, 그 후로는 무작위. 깊이를 못 봄.
해결책은 직관적: 두 번째 수, 세 번째 수에도 UCB1을 적용하자. 그러면 점진적으로 좋은 수순(line)을 발견할 수 있어.
📖 핵심 아이디어
- 처음에는 현재 보드 (루트 노드) 만 있는 트리로 시작
- 매 반복마다 트리를 한 노드씩 키워감
- 키울 노드의 선택은 UCB1 점수가 가장 높은 자식을 따라 내려감
- 새 노드에서 rollout 한 번으로 보상 측정
- 보상을 루트까지 거슬러 올라가며 누적
- N번 반복 후, 루트에서 가장 많이 방문된 자식이 최선의 수
이 한 사이클을 iteration이라고 부르고, 4단계로 분해돼:
🎯 MCTS의 4단계 (Iteration 한 번)
- ① Select (선택): 루트에서 시작해 UCB1로 자식 선택 반복 — 리프 노드까지
- ② Expand (확장): 리프 노드에 새 자식 하나 추가
- ③ Simulate (시뮬레이션): 새 자식에서 rollout 한 번 (무작위 끝까지)
- ④ Backup (역전파): 결과를 루트까지 거슬러 갱신 (각 노드의 visits++, wins+=결과)
이 4단계를 N번(1000~10000번) 반복하면, 트리가 좋은 수순 쪽으로 비대칭으로 자라남. 유망한 가지는 깊고, 별로인 가지는 얕음.
이 챕터에서 4단계를 하나씩 그림과 코드로 보고, 마지막에 통합 코드 완성.