Select 단계 — PUCT 공식의 재해석
이제 한 단계씩 자세히 본다. 첫째 — Select.
PUCT(a) = Q(s,a) + c · P(s,a) · √N(s) / (1 + N(s,a))
"이 행동이 얼마나 좋은가 + 얼마나 덜 가봐서 더 시도할 만한가"
📖 변수 정리
- Q(s, a): 행동 a의 지금까지 평균 가치 — 즉 자식 노드의 평균 가치
- P(s, a): 정책 신경망이 준 사전 확률 — "이 수가 얼마나 그럴듯해 보이나"
- N(s): 부모 노드의 방문 횟수
- N(s, a): 자식 노드의 방문 횟수
- c: 탐험 강도 상수 (보통 1.0 ~ 2.5; MuZero 논문은 약 1.25)
🎯 첫 항 — Q(s, a): "활용(exploitation)"
지금까지 가본 결과, 이 행동의 평균 결과는 얼마나 좋았나.
- 방문 횟수가 늘수록 안정된 추정치가 됨
- "이미 검증된 좋은 행동을 더 시도"하는 방향으로 끌어당김
🎯 둘째 항 — c·P·√N/(1+n): "탐험(exploration)"
덜 가본 행동, 사전 확률이 높은 행동에 가산점을 준다.
P(s,a): 정책 신경망이 "이 수 그럴듯하다"고 본 행동에 가중치√N(s): 부모를 많이 방문할수록 자식 탐험에도 더 투자1/(1+N(s,a)): 자식을 많이 방문할수록 이 보너스는 줄어듦 (이미 충분히 시도해본 곳은 덜 끌어당김)
💡 직관 — 식당 고르기 비유
새 동네에서 점심 먹을 식당 고른다고 해보자.
- Q: 몇 번 가봐서 평가가 좋은 식당 → 다시 가고 싶음
- P: 외관/메뉴판이 좋아 보이는 식당 → 가보고 싶음
- √N/(1+n): 한참 동네를 돌아다녀봤는데(N 큼) 아직 한 번도 안 가본 식당(n 작음) → 한 번은 가볼 만함
PUCT는 이 세 요소를 합쳐서 "다음에 어디 갈지"를 결정한다.
📖 Select 알고리즘 (의사코드)
node = root
path = [node]
while node.expanded():
best_a = argmax over a of PUCT(node, a)
node = node.children[best_a]
path.append(node)
return path # 끝까지 내려온 경로매우 단순하다 — "트리를 더 이상 못 갈 때까지 PUCT 따라 내려간다."