PUCT — 알파고의 핵심 알고리즘
👋 이 챕터에서 다룰 것
알파고의 모든 부품을 통합. MCTS + 세 신경망 = PUCT (Polynomial UCT) 알고리즘. 우리가 만들 7x7 미니 알파고의 핵심.
📖 무엇이 바뀌나? — UCB1 → PUCT
PART 3에서 본 UCB1 공식:
UCB1 = w/n + c · √(ln(N)/n)
알파고의 PUCT 공식:
PUCT = Q(s,a) + c · P(s,a) · √(N) / (1 + n)
주요 차이:
- Q(s,a): 활용 항. UCB1의 w/n과 동일 (평균 보상)
- P(s,a): 탐험 항에 policy network 확률 곱하기
- √(N) / (1+n): 시도 횟수가 적을수록 큼
P(s,a)가 핵심 — policy network이 추천하는 수에 탐험 우선순위 자동 부여.
🎯 직관 — UCB1 vs PUCT
- UCB1: "모든 자식을 동등하게 탐험" + "성과 좋은 자식 활용"
- PUCT: "Policy가 좋다고 한 자식을 더 탐험" + "성과 좋은 자식 활용"
예: 49 자리 중 policy network이 "(3,3) 33%, (3,15) 15%, ..." 추천. PUCT는 (3,3)에 가장 많이 시뮬레이션 배분. 명백히 약한 자리(가장자리)는 거의 안 가봄.
💡 왜 이게 강한가
UCB1은 모든 자식을 한 번씩은 가봐야 함 (visits=0이면 ∞). 49 자리면 49 시뮬레이션 낭비.
PUCT는 P(s,a)가 0에 가까운 자리는 거의 안 가봄. "명백히 약한 자리는 시도조차 안 함" → 시간 효율 100배.
이게 알파고가 "1수당 5만 시뮬레이션"으로 사람을 이긴 비결. UCB1만 쓰면 5만 시뮬레이션도 부족.
이 챕터:
- PUCT 공식 자세히
- 새 MCTS 알고리즘 — Value도 통합
- 알파고의 시간 사용 (1수에 ~50,000 시뮬레이션)
- 모든 부품이 합쳐진 그림