PUCT 공식 상세

이전 글에서 MCTS와 신경망의 결합을 개괄했습니다. 이제 MCTS 선택 단계의 핵심인 PUCT 공식을 깊이 탐구해 보겠습니다.

이 공식은 단순해 보이지만 AlphaGo 성공의 핵심 중 하나입니다. '알려진 좋은 수를 활용'하는 것과 '더 나을 수 있는 수를 탐색'하는 것, 이 두 가지 상충되어 보이는 목표를 우아하게 균형 잡습니다.

---

PUCT 공식

공식 정의

AlphaGo가 사용하는 PUCT(Predictor Upper Confidence Trees) 공식:

$a^* = \arg\max_a \left[ Q(s,a) + U(s,a) \right]$

여기서:

$U(s,a) = c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$

완전히 전개하면:

$a^* = \arg\max_a \left[ Q(s,a) + c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)} \right]$

기호 설명

기호	의미	출처
$Q(s,a)$	행동 $a$의 평균 가치	MCTS 통계
$P(s,a)$	행동 $a$의 사전 확률	Policy Network
$N(s)$	부모 노드의 방문 횟수	MCTS 통계
$N(s,a)$	자식 노드의 방문 횟수	MCTS 통계
$c_{\text{puct}}$	탐색 상수	하이퍼파라미터

직관적 이해

PUCT 공식은 두 부분으로 나눌 수 있습니다:

총 점수 = Q(s,a)        + U(s,a)
         ↓              ↓
       활용 항          탐색 항
     "이 수가 얼마나 좋은가?"   "이 수를 더 탐색할 가치가 있는가?"

활용 항 Q(s,a):

• 이 수의 과거 평균 성적
• 방문이 많을수록 추정이 더 정확
• '이미 좋다고 알려진' 수를 선택하도록 유도

탐색 항 U(s,a):

• 이 수에 아직 얼마나 탐색 가치가 있는지
• 방문이 적을수록 탐색 보상이 높음
• '좋을 수 있는' 수를 시도하도록 유도

---

각 항의 의미

Q(s,a): 평균 가치

$Q(s,a)$는 노드 $(s,a)$에서 출발한 모든 시뮬레이션의 평균 결과입니다:

$Q(s,a) = \frac{W(s,a)}{N(s,a)} = \frac{\sum_i z_i}{N(s,a)}$

여기서 $z_i \in \{-1, +1\}$는 $i$번째 시뮬레이션의 결과입니다.

특성:

• 범위: $[-1, +1]$
• 초기값: 정의되지 않음(최소 한 번의 방문 필요)
• 방문 횟수가 증가함에 따라 안정화됨

해석:

• $Q = 0.6$: 이 수의 승률은 약 80% (왜냐하면 $Q = 2 \times \text{승률} - 1$)
• $Q = 0$: 승패 반반
• $Q = -0.3$: 이 수의 승률은 약 35%

P(s,a): 사전 확률

$P(s,a)$는 Policy Network의 출력에서 옵니다:

$P(s,a) = \pi_\theta(a|s)$

특성:

• 범위: $[0, 1]$이며, $\sum_a P(s,a) = 1$
• 노드가 처음 확장될 때 계산됨
• '이 수가 얼마나 좋은지'에 대한 신경망의 판단을 반영

역할:

• 높은 확률의 행동이 우선 탐색됨
• 방문 횟수가 0이어도 탐색 동기가 있음
• 탐색이 '합리적으로 보이는' 수에 집중하도록 유도

N(s) 와 N(s,a): 방문 횟수

$N(s)$는 부모 노드의 총 방문 횟수입니다:

$N(s) = \sum_a N(s,a)$

탐색 항에서의 역할:

$\frac{\sqrt{N(s)}}{1 + N(s,a)}$

이 점수의 행동:

• $N(s,a) = 0$일 때, 점수 = $\sqrt{N(s)}$(최대 탐색 동기)
• $N(s,a)$가 증가함에 따라 점수 감소
• $N(s,a) \gg \sqrt{N(s)}$일 때, 점수는 0에 가까워짐

이것이 보장하는 것:

1. 모든 행동이 최소 한 번은 탐색됨($P(s,a) > 0$인 경우)
2. 탐색 동기가 방문에 따라 감소
3. 최종 선택은 $Q$ 값에 의해 지배됨

c_puct: 탐색 상수

$c_{\text{puct}}$는 탐색과 활용의 균형을 제어합니다:

$c_{\text{puct}}$ 값	효과
작음(예: 0.5)	활용에 더 치우침, 좋은 수에 빠르게 집중
적당함(예: 1-2)	탐색과 활용의 균형
큼(예: 5)	탐색에 더 치우침, 더 많은 가능성 시도

AlphaGo Zero 논문(Nature 2017)은 $c_{\text{puct}}$를 "탐색 수준을 결정하는 상수"로만 적었고 값은 공개하지 않았습니다. 아래 수치는 오픈소스 프로젝트와 이 문서 예시에서 흔히 쓰는 값입니다.

---

UCB1과의 관계

UCB1 공식 복습

전통적 MCTS가 사용하는 UCB1 공식:

$\text{UCB1}(s,a) = \bar{X}_{s,a} + c \sqrt{\frac{\ln N(s)}{N(s,a)}}$

여기서 $\bar{X}_{s,a}$는 평균 보상입니다.

비교

측면	UCB1	PUCT
활용 항	$\bar{X}_{s,a}$(평균 보상)	$Q(s,a)$(평균 가치)
탐색 항	$\sqrt{\frac{\ln N}{n}}$(신뢰 구간)	$P \cdot \frac{\sqrt{N}}{1+n}$(사전 유도)
사전 정보	없음	Policy Network 사용
탐색 감소	로그 감소	선형 감소

PUCT의 장점

1. 사전 지식 활용: Policy Network가 제공하는 $P(s,a)$로 탐색이 처음부터 합리적인 수에 집중

2. 더 빠른 수렴: 선형 감소($1/(1+n)$)가 로그 감소($1/\sqrt{\ln N / n}$)보다 탐색을 더 빨리 집중시킴

3. 조절 가능한 탐색: $P(s,a)$와 $c_{\text{puct}}$가 탐색을 조절하는 더 많은 수단 제공

이론적 배경

UCB1은 엄격한 이론적 보장(regret bound)이 있지만, 다음을 가정합니다:

• 각 팔(행동)이 독립적
• 사전 정보 없음

바둑에서는 강력한 사전 정보(Policy Network)가 있으므로, PUCT가 이 정보를 더 잘 활용할 수 있습니다.

---

수학적 유도

다중 슬롯머신에서 시작

PUCT의 영감은 다중 슬롯머신(Multi-Armed Bandit) 문제에서 왔습니다.

$K$대의 슬롯머신이 앞에 있고, 각 머신의 당첨 확률이 다르지만 알려지지 않았다고 상상해 보세요. 목표는 총 당첨 횟수를 최대화하는 것입니다. 전략은:

• 활용: 가장 좋아 보이는 머신을 당김
• 탐색: 다른 머신을 시도하여 더 좋은 것을 발견할 수 있음

UCB1은 이 문제의 고전적 해결책이고, PUCT는 그 변형입니다.

UCB의 이론적 기초

확률 변수 $X$에 대해 Hoeffding 부등식에 의해:

$P(|\bar{X}_n - \mu| \geq \epsilon) \leq 2 \exp(-2n\epsilon^2)$

$1/t^4$의 확률로 오류를 범하려면:

$\epsilon = \sqrt{\frac{2 \ln t}{n}}$

이것이 UCB1 탐색 항의 유래입니다.

PUCT의 수정

PUCT는 고전적 UCB에 몇 가지 수정을 가했습니다:

1. 사전 확률 추가

$U(s,a) \propto P(s,a) \cdot (\text{탐색 항})$

이로써 탐색이 높은 확률의 행동에 집중됩니다.

2. 탐색 항 형태 변경

$\sqrt{\frac{\ln N}{n}}$에서 $\frac{\sqrt{N}}{1+n}$으로

이것이 수렴을 가속화합니다:

비교(N = 1000, n = 10 가정):

UCB1:  sqrt(ln(1000) / 10) = sqrt(0.69) ≈ 0.83
PUCT:  sqrt(1000) / 11 ≈ 2.87

PUCT는 더 많은 탐색 보상을 주지만 감소가 더 빠름

3. 학습 가능한 사전

$P(s,a)$는 신경망에서 오며, 훈련에 따라 개선됩니다. 이로써 MCTS와 신경망이 긍정적인 순환을 형성합니다.

왜 이 형태가 효과적인가?

직관적 설명:

$U(s,a) = c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$

1. $P(s,a)$: "전문가가 이 수가 얼마나 좋다고 말하는가"
2. $\sqrt{N(s)}$: "이 국면에 대해 얼마나 알고 있는가"
3. $1/(1 + N(s,a))$: "이 수에 대해 얼마나 알고 있는가"

조합하면: 국면에 대해 많이 알지만 특정 수에 대해 적게 알고, 전문가가 그 수가 괜찮다고 생각할 때, 탐색해야 함.

---

시각적 이해

탐색 항의 변화

탐색 항이 방문 횟수에 따라 어떻게 변하는지 시각화해 보겠습니다:

U(s,a) = c_puct × P(s,a) × √N(s) / (1 + N(s,a))

가정: P(s,a) = 0.1, c_puct = 1.5, N(s) = 1600

N(s,a)  |  U(s,a)
--------|----------
   0    |  6.00      ← 미방문, 최대 탐색 보상
   1    |  3.00
   5    |  1.00
  10    |  0.55
  50    |  0.12
 100    |  0.06
 400    |  0.015     ← 많이 방문 후, 탐색 보상 매우 작음

다른 사전 확률의 영향

가정: c_puct = 1.5, N(s) = 1600, N(s,a) = 0

P(s,a)  |  U(s,a)
--------|----------
  0.30  |  18.00     ← 높은 확률 행동이 더 많은 탐색 동기
  0.10  |   6.00
  0.03  |   1.80
  0.01  |   0.60
  0.001 |   0.06     ← 낮은 확률 행동은 거의 탐색되지 않음

인터랙티브 탐색

아래의 $c_{\text{puct}}$ 매개변수를 조정하여 MCTS의 선택에 어떻게 영향을 미치는지 관찰해 보세요:

載入中...

---

AlphaGo에서의 구체적 구현

AlphaGo Fan/Lee의 구현

원본 AlphaGo는 약간 다른 공식을 사용합니다:

$U(s,a) = c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{\sum_b N(s,b)}}{1 + N(s,a)}$

그리고 $Q(s,a)$의 계산은 가상 손실을 고려합니다:

def get_ucb_score(node, action, c_puct=1.5):
    Q = node.W[action] / (node.N[action] + 1)  # 0으로 나누기 방지
    P = node.prior[action]
    N_parent = sum(node.N.values())
    N_child = node.N[action]

    U = c_puct * P * math.sqrt(N_parent) / (1 + N_child)

    return Q + U

AlphaGo Zero의 구현

AlphaGo Zero는 더 간결한 구현을 사용합니다:

def select_action(node, c_puct=1.5):
    """PUCT 점수가 가장 높은 행동 선택"""
    N_parent = sum(node.visit_count.values())

    def puct_score(action):
        Q = node.value_sum[action] / (node.visit_count[action] + 1)
        P = node.prior[action]
        U = c_puct * P * math.sqrt(N_parent) / (1 + node.visit_count[action])
        return Q + U

    return max(node.legal_actions, key=puct_score)

미방문 노드 처리

$N(s,a) = 0$일 때 $Q(s,a)$는 정의되지 않습니다. 일반적인 처리 방식:

방법 1: 부모 노드 가치 사용

Q = parent_value if N[action] == 0 else W[action] / N[action]

방법 2: 초기값 사용

Q = 0 if N[action] == 0 else W[action] / N[action]

방법 3: FPU(First Play Urgency) 사용

# 미방문 노드는 더 낮은 Q 값 사용
fpu_value = parent_Q - fpu_reduction
Q = fpu_value if N[action] == 0 else W[action] / N[action]

AlphaGo Zero는 FPU를 사용하여 탐색이 방문한 노드를 먼저 시도하도록 합니다.

---

실제 튜닝 경험

c_puct 선택

$c_{\text{puct}}$는 가장 중요한 하이퍼파라미터입니다. 실무 지침:

1. 네트워크 품질과 관련

• 네트워크가 강함(높은 정확도): 작은 $c_{\text{puct}}$ 사용 가능
• 네트워크가 약함: 오류 수정을 위해 큰 $c_{\text{puct}}$ 필요

2. 탐색 예산과 관련

• 시뮬레이션 횟수 많음: 큰 $c_{\text{puct}}$ 사용 가능(탐색할 시간 충분)
• 시뮬레이션 횟수 적음: 작은 $c_{\text{puct}}$ 사용(빠르게 집중)

3. 게임 특성과 관련

• 전술성이 강한 게임: 더 많은 탐색 필요할 수 있음
• 전략성이 강한 게임: 사전을 더 신뢰할 수 있음

일반적인 값

프로젝트	$c_{\text{puct}}$
AlphaGo / AlphaGo Zero	논문에서 미공개
AlphaZero	1.25
KataGo	0.5 - 1.0(동적 조정)
Leela Zero	1.5 - 2.0

동적 조정

일부 고급 구현은 동적 $c_{\text{puct}}$를 사용합니다:

def dynamic_cpuct(visit_count):
    """방문 횟수에 따라 탐색 상수 조정"""
    base = 1.0
    init = 1.5
    log_base = 19652  # 조정 매개변수

    return math.log((visit_count + log_base + 1) / log_base) + init

이로써 탐색이 초기에는 탐색에 치우치고 후기에는 활용에 치우칩니다.

민감도 분석

$c_{\text{puct}}$가 기력에 미치는 영향:

실험(다른 조건 고정, c_puct 변화):

c_puct | 상대 Elo
-------|----------
  0.5  |   -50     ← 과도한 활용, 좋은 수 놓침
  1.0  |   +20
  1.5  |    0      ← 기준
  2.0  |   -10
  3.0  |   -30     ← 과도한 탐색, 탐색 낭비
  5.0  |   -80

최적값은 보통 1.0-2.0 사이이지만, 네트워크 품질과 탐색 예산에 따라 다릅니다.

---

고급 변형

PUCT의 변형

1. Polynomial PUCT (P-UCT)

$U(s,a) = c \cdot P(s,a) \cdot \frac{N(s)^\alpha}{1 + N(s,a)}$

여기서 $\alpha$는 조절 가능한 매개변수(보통 $\alpha = 0.5$).

2. 노이즈가 있는 PUCT

루트 노드에 Dirichlet 노이즈 추가:

$P'(s,a) = (1-\varepsilon) P(s,a) + \varepsilon \cdot \eta_a$

여기서 $\eta \sim \text{Dir}(\alpha)$. 이것이 탐색의 다양성을 증가시킵니다.

3. UCT-like PUCT

$U(s,a) = c \cdot P(s,a) \cdot \sqrt{\frac{\ln(1 + N(s) + c_{\text{base}})}{1 + N(s,a)}}$

UCT의 로그 형태와 PUCT의 사전 유도를 결합합니다.

KataGo의 개선

KataGo는 PUCT에 여러 개선을 가했습니다:

1. 동적 $c_{\text{puct}}$ 국면 복잡도와 탐색 진행에 따라 조정.

2. 가치 예측의 불확실성 Value Network의 예측 신뢰도 고려.

3. 정책 목표 학습 정책 헤드 출력뿐 아니라 MCTS 방문 분포를 직접 학습.

다른 선택 공식

PUCT 외에도 다른 선택 공식이 있습니다:

RAVE(Rapid Action Value Estimation)

$Q_{\text{RAVE}}(s,a) = (1-\beta) Q(s,a) + \beta Q_{\text{AMAF}}(s,a)$

"All Moves As First" 통계를 사용하여 학습 가속.

GRAVE(Generalized RAVE)

RAVE의 변형으로, 조상 노드의 통계 정보 사용.

---

이론적 분석

수렴성

PUCT가 최적해로의 수렴을 보장하는가?

엄격하게는: UCB1과 같은 이론적 보장은 없습니다.

실제로는: 충분한 시뮬레이션 후 PUCT는 고품질 해로 수렴합니다. 왜냐하면:

1. 탐색 항이 결국 0에 가까워짐
2. 모든 행동이 결국 방문됨
3. $Q$ 값이 실제 가치로 수렴

복잡도 분석

시간 복잡도(시뮬레이션당):

• Selection: $O(\log N)$(트리의 깊이)
• Expansion: $O(A)$(합법적 행동 수, 신경망 추론 필요)
• Evaluation: $O(1)$(Value Network) 또는 $O(T)$(Rollout, $T$는 게임 길이)
• Backpropagation: $O(\log N)$

공간 복잡도:

• 노드당: $O(A)$(사전과 방문 통계 저장)
• 전체 트리: $O(N \cdot A)$($N$은 노드 수)

Minimax와의 관계

$c_{\text{puct}} \to 0$이고 시뮬레이션 횟수 $\to \infty$일 때, MCTS + PUCT는 Minimax 탐색에 근접합니다.

하지만 유한한 예산에서 PUCT는 보통 Minimax + Alpha-Beta보다 효율적입니다. 사전 지식을 더 잘 활용하기 때문입니다.

---

자주 묻는 질문

Q: Policy Network의 출력을 직접 선택으로 사용하지 않는 이유는?

A: Policy Network는 실수할 수 있습니다. MCTS의 탐색은:

1. 신경망의 판단을 검증
2. 신경망이 놓친 좋은 수 발견
3. 신경망의 체계적 편향 수정

실험에 따르면 신경망이 강해도 탐색 추가가 기력을 크게 향상시킵니다.

Q: PUCT가 성능이 좋지 않은 경우는?

1. 사전 확률이 완전히 틀림: Policy Network가 좋은 수를 낮은 확률로 평가하면, PUCT는 수정에 많은 시뮬레이션 필요

2. 장기 전술: PUCT는 정확한 계산이 필요한 긴 시퀀스 전술 발견이 어려울 수 있음

3. 상대 모델 부재: PUCT는 상대도 최적 전략을 사용한다고 가정, 비합리적 상대에게는 최적이 아닐 수 있음

Q: 매우 큰 행동 공간을 어떻게 처리하는가?

몇 가지 기법:

1. Policy Network 필터링: $P(s,a) > \epsilon$인 행동만 고려
2. 점진적 확장: 처음에는 소수의 행동만 확장, 필요시 확대
3. 동적 가지치기: 명백히 나쁜 행동 제거

---

애니메이션 대응

이 글에서 다루는 핵심 개념과 애니메이션 번호:

번호	개념	물리/수학 대응
E4	탐색과 활용	다중 슬롯머신
C3	PUCT 선택	신뢰 구간

---

요약

PUCT 공식은 AlphaGo MCTS의 핵심입니다. 우리가 배운 것:

1. 공식 구조: $Q + U$, 활용 항 더하기 탐색 항
2. 각 항의 의미: $Q$는 경험적 가치, $P$는 사전 확률, $N$은 탐색 감소 제어
3. UCB1과의 관계: PUCT는 사전을 추가하고 다른 탐색 항 형태 사용
4. 수학적 유도: 다중 슬롯머신에서 MCTS 선택까지
5. 실제 튜닝: $c_{\text{puct}}$의 선택과 영향
6. 고급 변형: 동적 조정, 노이즈, KataGo 개선

PUCT의 우아함은 단순하면서도 효과적이라는 점입니다—하나의 공식으로 탐색과 활용의 균형을 맞추고, 신경망의 사전 지식을 우아하게 통합합니다.

---

더 읽을거리

• 다음 글: AlphaGo Zero 개요 — 처음부터 시작하는 돌파구
• 이전 글: MCTS와 신경망의 결합 — 전체 아키텍처
• 관련: 전통적 방법의 한계 — 왜 새로운 방법이 필요한가

---

참고 자료

1. Rosin, C. D. (2011). "Multi-armed bandits with episode context." Annals of Mathematics and Artificial Intelligence, 61(3), 203-230.
2. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489.
3. Silver, D., et al. (2017). "Mastering the game of Go without human knowledge." Nature, 550, 354-359.
4. Kocsis, L., & Szepesvari, C. (2006). "Bandit based Monte-Carlo Planning." ECML.
5. Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). "Finite-time analysis of the multiarmed bandit problem." Machine Learning, 47(2), 235-256.
6. Wu, D., et al. (2019). "Accelerating Self-Play Learning in Go." arXiv preprint (KataGo 기술 보고서).

---

부록: 완전한 구현 예제

import math
import numpy as np
from typing import Dict, List, Optional

class MCTSNode:
    """MCTS 노드"""
    def __init__(self, prior: float = 0.0):
        self.prior = prior          # P(s,a)
        self.visit_count = 0        # N(s,a)
        self.value_sum = 0.0        # W(s,a)
        self.children: Dict[int, 'MCTSNode'] = {}

    @property
    def q_value(self) -> float:
        """Q(s,a) 계산"""
        if self.visit_count == 0:
            return 0.0
        return self.value_sum / self.visit_count


class MCTS:
    """MCTS 탐색기, PUCT 사용"""

    def __init__(
        self,
        policy_network,
        value_network,
        c_puct: float = 1.5,
        num_simulations: int = 800
    ):
        self.policy_network = policy_network
        self.value_network = value_network
        self.c_puct = c_puct
        self.num_simulations = num_simulations

    def search(self, root_state) -> Dict[int, float]:
        """MCTS 탐색 실행, 행동의 방문 분포 반환"""
        root = MCTSNode()

        # 루트 노드 확장
        policy = self.policy_network(root_state)
        for action, prob in enumerate(policy):
            if is_legal(root_state, action):
                root.children[action] = MCTSNode(prior=prob)

        # 시뮬레이션 실행
        for _ in range(self.num_simulations):
            self._simulate(root, root_state)

        # 방문 분포 반환
        total_visits = sum(
            child.visit_count for child in root.children.values()
        )
        return {
            action: child.visit_count / total_visits
            for action, child in root.children.items()
        }

    def _simulate(self, node: MCTSNode, state) -> float:
        """단일 시뮬레이션 실행"""

        # 종료 상태인 경우
        if is_terminal(state):
            return get_result(state)

        # 리프 노드인 경우, 확장 및 평가
        if not node.children:
            policy = self.policy_network(state)
            value = self.value_network(state)

            for action, prob in enumerate(policy):
                if is_legal(state, action):
                    node.children[action] = MCTSNode(prior=prob)

            return value

        # Selection: PUCT 점수가 가장 높은 행동 선택
        action = self._select_action(node)
        child = node.children[action]
        next_state = apply_action(state, action)

        # 재귀적 시뮬레이션
        value = -self._simulate(child, next_state)

        # Backpropagation: 통계 업데이트
        child.visit_count += 1
        child.value_sum += value

        return value

    def _select_action(self, node: MCTSNode) -> int:
        """PUCT 공식으로 행동 선택"""
        total_visits = sum(
            child.visit_count for child in node.children.values()
        )

        def puct_score(action: int, child: MCTSNode) -> float:
            # Q(s,a): 평균 가치
            q = child.q_value

            # U(s,a): 탐색 보너스
            u = (
                self.c_puct
                * child.prior
                * math.sqrt(total_visits)
                / (1 + child.visit_count)
            )

            return q + u

        return max(
            node.children.keys(),
            key=lambda a: puct_score(a, node.children[a])
        )


# 사용 예제
def play_game():
    policy_net = PolicyNetwork()
    value_net = ValueNetwork()

    mcts = MCTS(
        policy_network=policy_net,
        value_network=value_net,
        c_puct=1.5,
        num_simulations=1600
    )

    state = initial_state()

    while not is_terminal(state):
        # MCTS 탐색 실행
        visit_distribution = mcts.search(state)

        # 방문 횟수가 가장 많은 행동 선택
        action = max(visit_distribution.keys(),
                     key=lambda a: visit_distribution[a])

        # 행동 실행
        state = apply_action(state, action)
        print(f"Selected action {action} with visit ratio "
              f"{visit_distribution[action]:.2%}")

    print(f"Game result: {get_result(state)}")

이 구현은 MCTS에서 PUCT 공식의 핵심 역할을 보여줍니다. 실제 AlphaGo 구현은 추가로 포함합니다:

• 병렬 탐색(가상 손실)
• 배치 신경망 평가
• 트리 재사용
• 디리클레 노이즈
• 온도 제어 등 기능