CH 25 강화학습 · Part 4 엔트로피 · 모델 · 데이터
MCTS와 AlphaZero — 탐색이 정책을 가르친다
23·24장에서는 모델을 배워야 했고, 그래서 모델 오차가 계획을 오염시켰다. 보드게임은 사정이 다르다. 규칙이 곧 완벽한 모델이므로 상상할 필요 없이 진짜 탐색을 할 수 있다. 문제는 크기다. 체스의 분기계수 35로 6수만 읽어도 356 = 1,838,265,625 개의 국면이 생긴다. 몬테카를로 트리 탐색은 전수 탐색을 포기하고 유망한 가지만 깊게 읽는데, 그 선택 규칙이 2장의 UCB 다. AlphaZero 는 여기에 고리 하나를 더 건다 — 탐색 결과를 신경망의 정답으로 되먹이는 것. 탐색은 정책을 평가하는 도구가 아니라 정책향상 연산자다.
- 01 직관
- 02 수식 읽는 법
- 03 손으로 풀기
- 04 코드
- 05 시각화
약어 및 기호 정의
- MCTS
- Monte Carlo tree search. 무작위 표본 탐색으로 트리를 비대칭으로 키우는 계획 알고리즘
- UCT
- UCB applied to trees. 트리의 각 노드에서 2장의 UCB1 을 돌리는 선택 규칙
- PUCT
- predictor + UCT. 신경망 사전확률 P(s,a) 로 탐험항을 배분하는 AlphaZero 의 선택 규칙
- N(s,a)
- 간선 방문횟수. 루트에서 내려오며 행동 a 를 고른 횟수
- W(s,a)
- 누적 가치합. Q(s,a) = W(s,a)/N(s,a)
- 분기계수 b
- branching factor. 한 국면의 평균 합법 수. 체스 약 35, 바둑 약 250
- 네가맥스 negamax
- 2인 제로섬 게임에서 값의 부호를 한 수마다 뒤집어 한 가지 관점으로 통일하는 규약
- 온도 T
- temperature. 방문횟수를 정책으로 바꿀 때의 첨예함. π ∝ N1/T
- 디리클레 잡음 Dirichlet noise
- 루트의 사전확률에 섞는 잡음. 자기대국에서 같은 수순만 반복되는 것을 막는다
- z
- 대국 결과. 현재 수를 둘 쪽 관점으로 +1(승) · 0(무) · −1(패)
직관: 모델이 정확하면 상상이 아니라 탐색이다
23장 Dyna 와 24장 세계모델은 같은 약점을 공유했다. 모델을 데이터에서 배우기 때문에, 모델이 틀린 곳에서 계획이 자신만만하게 틀린다. 그런데 어떤 문제에서는 모델이 이미 완벽하다. 체스의 규칙, 바둑의 착수 금지점, 님 게임의 돌 개수 — 전이함수 p(s′|s,a) 와 보상함수가 오차 없이 주어져 있다. 이때 모델 기반 강화학습의 어려움 절반이 사라지고, 남는 어려움은 하나뿐이다.
남는 어려움
모델은 정확하지만 전부 펼칠 수는 없다. 4장의 가치반복은 상태를 전부 훑었고, 그건 상태가 수십 개일 때만 가능한 일이다. 체스의 국면 수에 대해 섀넌이 내놓은 고전적 추정은 10120 규모이고, 분기계수 35로 80수를 펼치면 3580 ≈ 10123.5 이다. 우주의 원자 수를 한참 넘는다.
깊이를 6수로 줄여 보자. 356 = 1,838,265,625 개다. 초당 1백만 국면을 평가하는 기계라면 30.6분이 걸린다. 한 수를 두려고 30분을 쓴다는 뜻이고, 8수는 26일, 10수는 87.4년이다. 깊이 2수마다 시간이 352 = 1225 배 든다. 전수 탐색은 여기서 끝난다.
사람은 이렇게 두지 않는다. 명백히 나쁜 수는 한 수 이상 읽지 않고, 유력한 후보 두세 개만 열 수·스무 수 깊이 읽는다. 트리가 비대칭으로 자란다. MCTS 는 이 비대칭을 통계로 만든다 — 표본을 한 번 내려보낼 때마다 방문횟수와 승률을 기록하고, 다음 표본은 그 기록을 보고 더 유망한 쪽으로 내려간다.
그리고 "유망한 쪽으로 내려가되 덜 본 쪽도 봐야 한다"는 문장은 우리가 2장에서 이미 푼 문제다. 루트에서 행동을 고르는 일은 팔이 b 개인 밴딧이고, 그 아래 각 노드도 다시 밴딧이다. MCTS 는 트리의 모든 노드에서 밴딧을 하나씩 돌리는 알고리즘이며, 그 밴딧 정책이 UCB1 일 때 이름이 UCT 다.
한 문장으로 줄이면 트리 안에서는 통계로 고르고, 트리 밖에서는 한 번 추정하고, 그 결과를 통계에 더한다. 그 "한 번 추정"을 무작위 롤아웃(rollout)으로 하는 것이 고전 MCTS, 신경망 가치함수로 하는 것이 AlphaZero 다.
그리고 고리가 하나 더 있다
AlphaZero 의 진짜 기여는 탐색 자체가 아니다. 탐색이 신경망보다 낫다는 사실을 학습에 쓴 것이다.
신경망 정책 pθ(a|s) 가 어떤 국면에서 수를 내놓는다. 그 국면에서 MCTS 를 800번 돌려 얻은 방문횟수 분포 N(s,a) 는 거의 항상 pθ 보다 좋다 — 탐색이 신경망의 평가를 실제 수순으로 검증했기 때문이다. 그러면 그 분포를 정답으로 삼아 pθ 를 학습시키면 된다. 신경망이 좋아지면 다음 탐색이 좋아지고, 좋아진 탐색이 다시 더 나은 정답을 만든다.
이 구조는 5장의 정책반복(policy iteration)과 같은 모양이다. 5장의 정책개선 단계는 π′(s) = argmaxa Qπ(s,a) 였고, 정책개선 정리가 π′ 가 π 보다 나쁘지 않음을 보장했다. AlphaZero 에서 그 argmax 자리에 들어온 것이 MCTS 다. 탐색은 평가기가 아니라 향상 연산자다 — 이 장에서 가장 중요한 한 줄이다.
수식 읽는 법: UCT · PUCT · 그리고 되먹임 손실
네 단계의 식
트리의 각 간선 (s,a) 는 방문횟수 N(s,a) 와 누적 가치합 W(s,a) 를 들고 있고, 노드의 방문횟수는 N(s) = Σa N(s,a) 다. ① 선택에 쓰는 규칙이 UCT 다.
2장의 UCB1 을 다시 적어 보자.
같은 식이다. 달라진 것은 기호의 해석뿐이다. 밴딧의 t 가 그 노드를 지나간 횟수 N(s), Nt(a) 가 그 간선을 고른 횟수 N(s,a), 팔의 평균 보상 Qt(a) 가 그 수를 둔 뒤 이어진 대국들의 평균 결과가 되었다. 2장에서 "UCB 는 같은 노드를 수천 번 방문하는 상황에 잘 맞는다"고 적었던 이유가 이것이다.
한 가지 차이는 있다. 밴딧의 팔은 고정된 분포에서 보상을 뽑지만, 트리의 간선은 그 아래 부분트리가 자라는 동안 값이 변한다. UCT 가 푸는 것은 비정상 밴딧(non-stationary bandit)이다. 그래서 반복수를 무한히 늘리면 루트의 선택이 미니맥스 최적 수로 수렴한다는 것은 증명되어 있어도, 수렴 속도 보장은 UCB1 의 후회 상한만큼 깨끗하지 않다.
평가와 역전파
③ 평가는 새로 붙인 노드 sL 의 가치를 한 번 추정한다 — 고전 MCTS 는 롤아웃으로, AlphaZero 는 가치망으로.
④ 역전파는 내려온 경로를 거슬러 갱신한다. 2인 제로섬 게임에서는 한 수마다 두는 쪽이 바뀌므로 부호를 뒤집어야 한다.
AlphaZero 의 PUCT
UCT 의 약점은 미방문 자식의 점수가 ∞ 라는 것이다. 모든 자식을 적어도 한 번은 봐야 한다. 분기계수 250의 바둑에서는 루트에서 깊이 들어가기도 전에 250번을 쓴다. AlphaZero 는 사전확률 P(s,a) = pθ(a|s) 를 탐험항에 곱해 이 문제를 없앤다.
식 (25.1)과 (25.4)를 나란히 놓고 세 가지를 읽어야 한다.
탐색 결과를 정답으로 쓴다
탐색이 끝나면 루트의 방문횟수 N(s0,a) 가 남는다. 이것을 정책으로 바꾼다.
한 판이 끝나면 승부 z ∈ {+1, 0, −1} 이 정해진다. 그 판의 모든 국면에 대해 (st, πt, zt) 를 학습 표본으로 저장하는데, zt 는 st 에서 수를 둘 쪽 관점의 결과다. 신경망 (pθ, vθ) 는 다음 손실을 줄인다.
둘째 항 −πT log pθ = −Σa π(a|s) log pθ(a|s) 는 16장의 정책경사가 아니라 지도학습의 교차엔트로피다. 정답 레이블이 사람이 아니라 방금 돌린 탐색에서 나왔다는 점만 다르다. AlphaZero 의 학습은 사실상 "탐색이 선생, 신경망이 학생"인 지도학습이고, 강화학습의 고분산 문제가 여기서 크게 완화된다.
탐색은 정책향상 연산자다
5장에서 정책반복은 두 단계를 번갈았다. 평가: π 에 대해 Qπ 를 구한다. 향상: π′(s) = argmaxa Qπ(s,a). 정책개선 정리는 Vπ′(s) ≥ Vπ(s) 를 모든 s 에서 보장했다.
AlphaZero 의 대응은 이렇다. 평가: 신경망 vθ, pθ 가 근사 평가를 제공한다. 향상: 그 평가를 쓴 MCTS 가 식 (25.5)의 π 를 내놓는다. π 가 pθ 보다 나은 이유는 탐색이 실제 수순을 펼쳐 검증했기 때문이며, 4장의 벨만 최적 백업을 깊이 d 까지 근사 적용한 셈이다.
차이는 보장의 강도뿐이다. 5장의 향상은 표 위에서 엄격하게 성립했고, MCTS 의 향상은 표본이 유한하고 가치망에 편향이 있어 확률적·근사적이다. 방향은 같다 — 탐색은 연산으로 정책을 끌어올린다. 신경망 파라미터를 건드리지 않고도 추론 시간에 정책이 개선된다는 뜻이고, 이것이 AlphaZero 계열이 "생각할 시간을 주면 더 잘 두는" 이유다.
루트에 잡음을 더하는 이유
자기대국(self-play)에는 고유한 함정이 있다. 신경망과 탐색이 모두 결정적이면 같은 시작 국면에서 언제나 똑같은 수순이 나온다. 데이터가 한 줄로 수렴하고 보지 않은 수는 영원히 사전확률이 낮은 채 남는다 — 1장의 "갇히면 갇혔다는 사실조차 모른다"가 자기대국 규모로 재현된다.
세 가지를 읽어야 한다. (a) 잡음은 루트에만 더한다 — 트리 내부에 더하면 탐색이 망가진다. (b) α < 1 인 디리클레는 한 성분이 거의 1인 희소한 표본을 내므로, 매 판 "한 수만 강하게 띄우는" 방식으로 다양성을 만든다. (c) 혼합이라 원래 사전확률이 완전히 지워지지 않는다.
여기에 더해 자기대국 초반 일정 수까지는 식 (25.5)의 T=1 로 수를 표본하고 그 뒤에는 T → 0 으로 최선을 둔다 — 탐험은 초반, 정확성은 종반이다.
손으로 풀기
계산 1 — 전수 탐색은 왜 불가능한가
분기계수 b = 35(체스의 대략적인 평균 합법 수), 깊이 d 의 잎 노드 수는 bd 다. 초당 106 개를 평가하는 기계를 가정한다.
| 깊이 d | 잎 노드 수 35d | 소요 시간 (초) | 사람이 읽는 단위 |
|---|---|---|---|
| 4 | 1,500,625 | 1.5006 | 1.5초 |
| 6 | 1,838,265,625 | 1,838.27 | 30.64분 |
| 8 | 2,251,875,390,625 | 2,251,875.4 | 26.06일 |
| 10 | 2,758,547,353,515,625 | 2,758,547,353.5 | 87.41년 |
검산: 356 = 353 × 353 = 42875 × 42875 = 1,838,265,625. 시간은 이것을 106 으로 나눈 1838.265625 초 = 30.6378 분이다. 깊이를 2 늘릴 때마다 352 = 1225 배가 곱해진다 — 30.6분 × 1225 = 26.06일, 다시 ×1225 = 87.41년.
한 판이 80수쯤 간다고 보면 log10(3580) = 80 × 1.544068 = 123.53, 즉 ≈ 10123.5 이다. 섀넌의 고전적 추정 10120 과 같은 자리다. 모델이 완벽하다는 사실은 탐색 공간을 줄여 주지 않는다.
계산 2 — UCT 를 손으로 12회
루트에 행동 세 개 A, B, C 가 있다. 단순화를 위해 각 행동의 평가 결과를 결정적으로 둔다 — A 를 고르면 항상 0.8, B 는 0.4, C 는 0.1 이 돌아온다. 그러면 Q 는 첫 방문 이후 변하지 않고, 방문이 어떻게 몰리는지만 보인다. c = 1.4.
점수는 Q(a) + 1.4√(ln N(s) / N(a)) 이고 N(a)=0 이면 ∞ 다. 미방문이 여럿이면 A → B → C 순으로 깬다.
| 반복 | N(s) | 점수 A | 점수 B | 점수 C | 선택 | 갱신 후 N |
|---|---|---|---|---|---|---|
| 1 | 0 | ∞ | ∞ | ∞ | A | (1, 0, 0) |
| 2 | 1 | 0.800000 | ∞ | ∞ | B | (1, 1, 0) |
| 3 | 2 | 1.965576 | 1.565576 | ∞ | C | (1, 1, 1) |
| 4 | 3 | 2.267406 | 1.867406 | 1.567406 | A | (2, 1, 1) |
| 5 | 4 | 1.965576 | 2.048374 | 1.748374 | B | (2, 2, 1) |
| 6 | 5 | 2.055886 | 1.655886 | 1.876091 | A | (3, 2, 1) |
| 7 | 6 | 1.881950 | 1.725113 | 1.973993 | C | (3, 2, 2) |
| 8 | 7 | 1.927532 | 1.780939 | 1.480939 | A | (4, 2, 2) |
| 9 | 8 | 1.809419 | 1.827534 | 1.527534 | B | (4, 3, 2) |
| 10 | 9 | 1.837613 | 1.598132 | 1.567406 | A | (5, 3, 2) |
| 11 | 10 | 1.750060 | 1.626522 | 1.602176 | A | (6, 3, 2) |
| 12 | 11 | 1.685049 | 1.651649 | 1.632951 | A | (7, 3, 2) |
두 줄만 검산하자. 반복 4: 모든 N(a)=1 이므로 보너스가 세 행동 모두 1.4√(1.098612/1) = 1.467406 이고, 점수는 2.267406 / 1.867406 / 1.567406 으로 A 가 이긴다. 반복 8: ln 7 = 1.945910 에서 A 의 보너스 1.4√(1.945910/3) = 1.127532, C 의 보너스 1.4√(1.945910/2) = 1.380939 다. C 는 직전 반복에서 방문을 받아 보너스가 줄어 점수가 1.480939 로 떨어졌다.
선택 순서: A B C A B A C A B A A A. 두 구간으로 갈린다.
계산 3 — 같은 상황에 PUCT
신경망이 사전확률 P = (0.7, 0.2, 0.1) 을 준다고 하자. c = 1.5, 참 가치는 그대로, 미방문 간선의 Q 는 0이다. 탐험항은 U(a) = 1.5 × P(a) × √N(s) / (1 + N(a)) 다.
| 반복 | N(s) | Q (A,B,C) | U(A) | U(B) | U(C) | 점수 A | 점수 B | 점수 C | 선택 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0, 0, 0 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | A |
| 2 | 1 | 0.8, 0, 0 | 0.525000 | 0.300000 | 0.150000 | 1.325000 | 0.300000 | 0.150000 | A |
| 3 | 2 | 0.8, 0, 0 | 0.494975 | 0.424264 | 0.212132 | 1.294975 | 0.424264 | 0.212132 | A |
| 4 | 3 | 0.8, 0, 0 | 0.454663 | 0.519615 | 0.259808 | 1.254663 | 0.519615 | 0.259808 | A |
반복 1은 N(s)=0 이라 모든 점수가 0이고 동점이므로 사전확률이 큰 A 를 깬다. 반복 2의 U(A) = 1.5 × 0.7 × 1/(1+1) = 0.525, U(B) = 1.5 × 0.2 × 1/(1+0) = 0.3 이다.
UCT 와 PUCT 의 선택 순서 비교
UCT: A B C A B A C A B A A A — 첫 세 번에 모든 자식을 강제로 본다.
PUCT: A A A A A A A A A A A A — 첫 12번이 전부 A 다. 계속 돌리면 B 의 첫 방문은 반복 14, C 의 첫 방문은 반복 43 에 온다.
이유는 간단하다. B 가 뽑히려면 0.3√N(s) > 0.8 + 1.5 × 0.7 × √N(s)/(1+N(A)) 여야 하고, 반복 14에서 √13 = 3.605551 일 때 U(B) = 1.081665 가 점수 A = 1.070416 을 처음 넘어선다.
400회 시점은 UCT N=(349, 35, 16), PUCT N=(384, 13, 3) 이다. PUCT 가 훨씬 날카롭다. 이것이 바둑에서 250개 자식을 전부 펼치지 않고도 깊이 들어가는 이유이며, 동시에 신경망이 틀렸을 때의 위험이다 — 참 최적수에 P=0.001 을 준 신경망은 탐색이 그 수를 찾을 기회를 거의 없앤다. 식 (25.7)의 루트 잡음이 이 위험을 부분적으로 막는다.
계산 4 — 방문횟수를 정책으로: 온도의 효과
탐색이 끝나고 루트에 N = (60, 30, 10) 이 남았다고 하자. 식 (25.5)로 정책을 만든다. π ∝ N1/T 다.
| T | 1/T | N1/T | π(A) | π(B) | π(C) |
|---|---|---|---|---|---|
| 1 | 1 | (60, 30, 10) | 0.600000000 | 0.300000000 | 0.100000000 |
| 0.5 | 2 | (3600, 900, 100) | 0.782608696 | 0.195652174 | 0.021739130 |
| 0.1 | 10 | (6.0466×1017, 5.9049×1014, 1010) | 0.999024374 | 0.000975610 | 0.000000017 |
T=1 은 방문 비율 그대로다. T=0.5 는 제곱이므로 3600+900+100 = 4600 으로 나눈다 — 0.782609, 0.195652, 0.021739 이고 합은 1.000000 이다.
T=0.1 은 10제곱이다. 비율은 610 : 310 : 1 = 60466176 : 59049 : 1, 합이 60525226 이므로 π(A) = 60466176/60525226 = 0.999024374 다. 방문 비율 6:3:1 이 확률 999:1:0 이 되었다. 온도는 손잡이가 아니라 거의 스위치다. 그래서 자기대국은 초반 일정 수까지만 T=1 로 표본하고 그 뒤에는 T 를 떨어뜨려 최다 방문 수를 둔다.
계산 5 — 역전파의 부호 뒤집기
2인 게임에서 가장 자주 틀리는 곳이다. 규약은 하나다 — 모든 노드의 W/Q 는 그 노드에서 수를 둘 쪽의 관점으로 저장한다. 부모와 자식은 관점이 반대이므로 부모가 자식을 평가할 때도 부호를 뒤집어야 한다.
님 게임(돌 11개, 한 번에 1~3개, 마지막 돌을 가져가면 승)의 루트를 보자. s0 은 돌 11개, X 가 둔다. 세 자식은 각각 돌 10·9·8 개이고 모두 O 가 둘 국면이다.
| 반복 | 확장 노드 | 롤아웃 결과 (그 노드 기준) | 자식 갱신 | 루트 갱신 (부호 반전) | 루트 이후 상태 |
|---|---|---|---|---|---|
| 1 | s(10), O 차례 | v = +1 (O 가 이김) | N=1, W=+1 | W(s0) += −1 | N=1, W=−1 |
| 2 | s(9), O 차례 | v = −1 (O 가 짐) | N=1, W=−1 | W(s0) += +1 | N=2, W=0 |
| 3 | s(8), O 차례 | v = −1 (O 가 짐) | N=1, W=−1 | W(s0) += +1 | N=3, W=+1 |
반복 4에서 루트는 세 자식이 모두 펼쳐졌으므로 UCT 를 쓴다. 주의할 점은 점수에 들어가는 Q 가 −Q자식 라는 것이다. 자식의 Q 는 O 의 관점이고, 루트에서 고르는 쪽은 X 다.
| 자식 | Q자식 (O 관점) | −Q자식 (X 관점) | 보너스 1.4√(ln3/1) | UCT 점수 |
|---|---|---|---|---|
| s(10) | +1 | −1 | 1.467406 | 0.467406 |
| s(9) | −1 | +1 | 1.467406 | 2.467406 |
| s(8) | −1 | +1 | 1.467406 | 2.467406 |
s(9) 와 s(8) 이 동점이고 s(10) 은 이미 밀려났다. 부호를 뒤집지 않고 +Q자식 를 썼다면 루트는 s(10) 을 골랐을 것이다 — 상대가 이기는 수를 자기 최선으로 착각한다. 이 부호 하나를 빼먹으면 탐색 반복을 늘릴수록 성능이 떨어진다. MCTS 구현 버그의 1번이다.
계산 6 — 디리클레 잡음이 사전확률을 얼마나 흔드는가
P = (0.7, 0.2, 0.1), ε = 0.25, η ~ Dir(0.3, 0.3, 0.3) 로 식 (25.7)을 표본해 보자(시드 3). 첫 표본은 η = (0.000528, 0.998748, 0.000724) 로 거의 전부 2번 성분에 몰려 있고, 혼합하면 P′ = (0.525132, 0.399687, 0.075181) 이다 — B 의 사전확률이 0.2 → 0.40 으로 두 배가 되었고, 그 판에서는 탐색이 B 를 훨씬 일찍 들여다본다. 다음 표본은 η = (0.960528, 0.039472, 0) 이라 P′ = (0.765132, 0.159868, 0.075000) 으로 오히려 1등을 더 띄운다. α = 0.3 < 1 인 디리클레는 거의 한 성분에 몰린 벡터를 뱉으므로, 잡음은 방향을 지정하지 않고 매 판 다른 가지를 한 번씩 밀어 준다.
경계도 확인된다. P′ 의 어떤 성분도 (1−ε)P = 0.75 × 0.1 = 0.075 아래로 내려가지 않고(둘째 표본에서 정확히 0.075), A 는 0.75×0.7+0.25 = 0.775 를 넘지 않는다. 혼합이므로 잡음이 신경망의 판단을 지우지는 못한다.
코드: 님 게임과 순수 MCTS
신경망 없이 롤아웃만 쓰는 고전 MCTS 를 님 게임에 붙인다. 님을 고른 이유는 최적 수를 이론으로 정확히 알기 때문이다. 돌 n 개에서 1~3개를 가져가고 마지막 돌을 가져간 쪽이 이기는 규칙에서는 n 이 4의 배수인 국면이 수를 둘 쪽의 패배다. 따라서 n = 11 의 유일한 최적수는 3개를 가져가 8을 남기는 것 — 적중률을 셀 수 있는 정답이 있다.
import numpy as np, math
MOVES = (1, 2, 3) # 님: 1~3개, 마지막 돌 가져가면 승
def legal(n): return [m for m in MOVES if m <= n]
def rollout(n, rng): # n 에서 둘 쪽 관점 (+1 승 / −1 패)
if n == 0: return -1.0 # 가져갈 돌이 없다 = 직전 수가 마지막 돌 = 패
turn = 1
while True:
n -= int(rng.choice(legal(n)))
if n == 0: return float(turn)
turn = -turn
class Node:
__slots__ = ('n', 'kids', 'N', 'W', 'untried')
def __init__(s, n): s.n = n; s.kids = {}; s.N = 0; s.W = 0.0; s.untried = legal(n)[:]
def mcts(root_n, iters, rng, c=1.4):
root = Node(root_n)
for _ in range(iters):
path, node = [root], root
while True: # (1) 선택
if node.n == 0: val = -1.0; break # 종료 노드
if node.untried: # (2) 확장
m = node.untried.pop(int(rng.integers(len(node.untried))))
ch = Node(node.n - m); node.kids[m] = ch; path.append(ch)
val = rollout(ch.n, rng); break # (3) 평가 = 롤아웃
lnN = math.log(node.N) # UCT — 부호를 뒤집어 상대 관점으로
m = max(node.kids, key=lambda k: -node.kids[k].W / node.kids[k].N
+ c * math.sqrt(lnN / node.kids[k].N))
node = node.kids[m]; path.append(node)
for nd in reversed(path): # (4) 역전파 — 단계마다 부호 반전
nd.N += 1; nd.W += val; val = -val
return root
for H, iter_list in [(11, [10, 100, 1000]), (15, [1000, 5000])]:
best = H % 4 # 4의 배수를 남기는 수가 최적
for iters in iter_list:
hit, T, cnt = 0, 200, {1: 0, 2: 0, 3: 0}
for t in range(T): # 시드 200개로 적중률 측정
r = mcts(H, iters, np.random.default_rng(10007 * iters + t))
m = max(r.kids, key=lambda k: r.kids[k].N) # 최다 방문 수를 둔다
cnt[m] += 1; hit += (m == best)
print(f"heap={H:2d} (최적수={best}) iters={iters:5d} 적중 {hit:3d}/{T} = {hit/T*100:5.1f}% 루트 선택분포 {cnt}")
r = mcts(11, 1000, np.random.default_rng(7))
print("heap=11, iters=1000 한 판의 루트 통계: " +
" ".join(f"m={m}: N={r.kids[m].N:4d} Q={-r.kids[m].W/r.kids[m].N:+.4f}" for m in sorted(r.kids)))heap=11 (최적수=3) iters= 100 적중 91/200 = 45.5% 루트 선택분포 {1: 39, 2: 70, 3: 91}
heap=11 (최적수=3) iters= 1000 적중 200/200 = 100.0% 루트 선택분포 {1: 0, 2: 0, 3: 200}
heap=15 (최적수=3) iters= 1000 적중 73/200 = 36.5% 루트 선택분포 {1: 60, 2: 67, 3: 73}
heap=15 (최적수=3) iters= 5000 적중 200/200 = 100.0% 루트 선택분포 {1: 0, 2: 0, 3: 200}
heap=11, iters=1000 한 판의 루트 통계: m=1: N= 45 Q=-0.0222 m=2: N= 100 Q=+0.1400 m=3: N= 855 Q=+0.8713
읽을 것이 네 가지다.
손계산 재현
계산 2·3·4 를 그대로 돌리는 코드다. 앞의 표가 임의로 만든 숫자가 아니라는 확인이다.
import numpy as np, math
v = np.array([0.8, 0.4, 0.1]) # 세 행동의 참 가치 (결정적)
P = np.array([0.7, 0.2, 0.1])
def run(rule, iters, c, show):
N = np.zeros(3); W = np.zeros(3); first = {}
for it in range(1, iters + 1):
Ns = N.sum(); Q = np.where(N > 0, W / np.maximum(N, 1), 0.0)
if rule == 'uct':
U = np.array([c * math.sqrt(math.log(Ns) / N[i]) if N[i] > 0 else math.inf
for i in range(3)])
else: # PUCT — 사전확률 P 가 탐험항을 배분한다
U = c * P * math.sqrt(Ns) / (1 + N)
s = Q + U; a = int(np.argmax(s)); first.setdefault('ABC'[a], it)
if it <= show:
print(f" it{it:2d} N(s)={int(Ns):2d} U={np.round(U,6)} score={np.round(s,6)} → {'ABC'[a]}")
N[a] += 1; W[a] += v[a]
return N, first
for rule, c, show in [('uct', 1.4, 6), ('puct', 1.5, 4)]:
N, first = run(rule, 12, c, show)
print(f" {rule.upper()} c={c} 12회 후 N = {N.astype(int)}")
N4, first = run(rule, 400, c, 0)
print(f" {rule.upper()} c={c} 각 행동의 첫 선택 반복 = {first}, 400회 후 N = {N4.astype(int)}\n")
for T in (1.0, 0.5, 0.1): # 방문횟수 → 정책 목표 (온도 T)
x = np.array([60.0, 30.0, 10.0]) ** (1.0 / T); p = x / x.sum()
print(f" T={T:<4} pi = ({p[0]:.9f}, {p[1]:.9f}, {p[2]:.12f})")it 2 N(s)= 1 U=[ 0. inf inf] score=[0.8 inf inf] → B
it 3 N(s)= 2 U=[1.165576 1.165576 inf] score=[1.965576 1.565576 inf] → C
it 4 N(s)= 3 U=[1.467406 1.467406 1.467406] score=[2.267406 1.867406 1.567406] → A
it 5 N(s)= 4 U=[1.165576 1.648374 1.648374] score=[1.965576 2.048374 1.748374] → B
it 6 N(s)= 5 U=[1.255886 1.255886 1.776091] score=[2.055886 1.655886 1.876091] → A
UCT c=1.4 12회 후 N = [7 3 2]
UCT c=1.4 각 행동의 첫 선택 반복 = {'A': 1, 'B': 2, 'C': 3}, 400회 후 N = [349 35 16]
it 1 N(s)= 0 U=[0. 0. 0.] score=[0. 0. 0.] → A
it 2 N(s)= 1 U=[0.525 0.3 0.15 ] score=[1.325 0.3 0.15 ] → A
it 3 N(s)= 2 U=[0.494975 0.424264 0.212132] score=[1.294975 0.424264 0.212132] → A
it 4 N(s)= 3 U=[0.454663 0.519615 0.259808] score=[1.254663 0.519615 0.259808] → A
PUCT c=1.5 12회 후 N = [12 0 0]
PUCT c=1.5 각 행동의 첫 선택 반복 = {'A': 1, 'B': 14, 'C': 43}, 400회 후 N = [384 13 3]
T=1.0 pi = (0.600000000, 0.300000000, 0.100000000000)
T=0.5 pi = (0.782608696, 0.195652174, 0.021739130435)
T=0.1 pi = (0.999024374, 0.000975610, 0.000000016522)
표와 한 자리도 다르지 않다. 그리고 마지막 줄들에 이 장의 요지가 그대로 있다 — 12회 후 UCT 는 N=(7,3,2), PUCT 는 N=(12,0,0) 이고, 400회 후에도 (349,35,16) 대 (384,13,3) 이다. 사전확률이 정확하면 이 집중이 기력이 되고, 틀리면 치명적인 편향이 된다.
AlphaZero 가 보고한 것
직접 돌릴 수 없는 규모의 결과는 논문 보고값으로만 인용한다. AlphaGo Zero 논문은 사람의 기보 없이 자기대국만으로 학습한 신경망이 이세돌과 대국한 버전(AlphaGo Lee)을 100대 0 으로 이겼다고 보고한다. AlphaZero 논문은 같은 알고리즘을 체스·쇼기·바둑에 그대로 적용했고 착수당 탐색 시뮬레이션을 800회 로 썼다고 밝힌다. 이 숫자가 중요한 것은 800회라는 얕은 탐색으로도 향상 연산자가 작동한다는 뜻이기 때문이다. 초당 수천만 국면을 보던 고전 엔진과의 차이를 메운 것이 가치망과 PUCT 의 가지치기다.
시각화
이 장이 앞뒤와 닿는 곳
2장과의 연결은 식 (25.1)이 식 (2.7)과 같은 식이라는 사실로 끝난다. 밴딧은 장난감이 아니라 트리의 모든 노드에 들어가는 부품이었다. 5장과의 연결은 더 깊다 — 정책반복의 향상 단계에 무엇을 끼워 넣을 수 있는지에 대한 답이 MCTS 다. 16~19장의 정책경사가 파라미터를 미분으로 밀어 정책을 올린다면, MCTS 는 추론 시간의 연산으로 올린다. AlphaZero 는 후자의 결과를 전자의 목표로 쓴다.
23·24장과의 대비는 전제에 있다. 이 장은 모델이 정확하다고 가정했다. 규칙이 주어지는 게임 밖에서는 이 전제가 깨지고, 배운 모델 위에서 탐색하면 모델 오차가 깊이에 따라 증폭된다는 24장의 경고가 그대로 따라붙는다. 다음 장은 반대쪽 극단이다 — 환경도 모델도 없고 로그만 있을 때. 이 장의 탐색이 자유로웠던 것은 환경을 마음대로 불러볼 수 있었기 때문인데, 26장에서는 그 권리가 사라진다.
이것만 기억하자
- MCTS 는 트리의 모든 노드에서 밴딧을 하나씩 돌리는 알고리즘이다. UCT 식 (25.1)은 2장 UCB1 식 (2.7)과 같은 식이고, t → N(s), Nt(a) → N(s,a) 로 기호만 바뀐다.
- PUCT 는 사전확률 P 를 탐험항에 곱해 미방문 간선의 점수를 유한하게 만든다. 그래서 분기계수 250에서도 모든 자식을 펼치지 않는다 — 손계산에서 UCT 는 3회에 세 자식을 다 봤지만 PUCT 는 12회를 전부 1등에 썼다.
- AlphaZero 의 핵심은 탐색이 아니라 되먹임이다. 탐색 분포 π ∝ N1/T 를 교차엔트로피 목표로, 대국 결과 z 를 회귀 목표로 써서 식 (25.6)을 줄인다. 탐색은 5장 정책개선의 자리에 들어가는 향상 연산자다.
흔한 오해
- "MCTS 는 모델을 배우는 알고리즘이다" — 아니다. MCTS 는 모델을 전제하는 계획 알고리즘이고 학습이 하나도 없어도 돌아간다. 4단의 님 코드에 학습 파라미터는 한 개도 없는데 1000회 반복으로 200/200 최적수를 찾았다. 학습이 들어오는 곳은 평가 함수와 사전확률이다.
- "반복수를 늘리면 언제나 좋아진다" — 부호 규약이 맞을 때만이다. 자식의 Q 를 뒤집지 않으면 탐색은 자기 패배를 향해 깊어진다. 또 돌 15개에서는 같은 1000회가 36.5% 로 떨어진다 — 반복수는 깊이에 대해 읽어야 하는 양이다.
- "학습 목표로 Q 를 쓰는 게 더 직접적이다" — 적게 방문한 간선의 Q 는 표본 1~2개로 계산된 값이라 믿을 수 없고, N 은 탐색이 그 수를 얼마나 진지하게 검토했는지를 담은 신뢰도 가중량이다. 한 판 출력에서도 Q = (−0.0222, +0.1400, +0.8713) 보다 N = (45, 100, 855) 가 또렷했다.
- "디리클레 잡음은 사소한 구현 디테일이다" — 자기대국의 탐험 전부를 이 잡음 하나가 담당한다. 잡음이 없으면 모든 판이 동일해져 데이터가 한 줄로 붕괴한다. 계산 6에서 α=0.3 의 잡음은 2등 수의 사전확률을 0.2 → 0.40 으로 올리면서도 신경망의 판단을 (1−ε) 만큼은 반드시 남겼다.
'강화학습' 카테고리의 다른 글
| [강화학습 27] 모방학습과 역강화학습 (0) | 2026.09.15 |
|---|---|
| [강화학습 26] 오프라인 RL — 환경 없이 로그만 있을 때 (0) | 2026.09.15 |
| [강화학습 24] 세계모델 — 잠재공간에서 꿈꾸기 (0) | 2026.09.15 |
| [강화학습 23] 모델기반 RL — Dyna와 상상 속 경험 (0) | 2026.09.15 |
| [강화학습 22] TD3 — 과대추정, 세 번째 이야기 (0) | 2026.09.15 |
댓글