비대칭으로 자라는 트리
MCTS의 가장 멋진 특성은 "트리가 비대칭으로 자란다"는 것.
minimax는 모든 가지를 같은 깊이로 탐색. b^d 노드 폭발.
MCTS는 UCB1로 유망한 가지에 더 많은 시뮬레이션 → 그 가지의 자식들도 생김 → 더 깊이 들어감 → 정밀해짐.
🌳 트리 모양 비교
Minimax 트리 (대칭):
● (루트, 깊이 0)
/ | \
● ● ● (깊이 1, 모두 봄)
/|\ /|\ /|\
● ● ● ● ● ● ● ● ● (깊이 2, 모두 봄)
... 모든 가지 같은 깊이
MCTS 트리 (비대칭):
● (루트)
/ | \
● ● ● (자식들 — 일부만 자세히 봄)
/|\
● ● ● (왼쪽 가지가 유망하면 더 깊이)
/|\
● ● ● (그 안의 또 유망한 가지)
|
● (계속 깊이 → 핵심 수순 발견)
💡 비대칭의 의미
좋은 가지로 가는 수순을 깊이 봐서 진짜 그게 좋은지 확인. 명백히 나쁜 가지는 얕게 두고 시간 낭비 안 함.
같은 시간 예산에서 minimax는 깊이 4를 모든 가지에 골고루 쓰는데, MCTS는 핵심 가지에 깊이 15~20을 가능. "필요한 곳에만 깊이".
📊 어떻게 비대칭이 만들어지나
- 초기에는 모든 자식이 visits=0 → UCB1 ∞ → 한 번씩 시도
- 몇 번 후, 좋은 자식은 wins/visits가 높음 → UCB1 점수 높음 → 또 선택됨
- 좋은 자식이 다시 선택되면 그 안에서 또 UCB1로 자식 선택 → 깊이 들어감
- 유망한 가지는 visits가 늘면서 그 안에 더 많은 자식이 생김 → 트리 깊이 + 폭 증가
- 안 좋은 가지는 visits가 적게 머물면서 그 안에 자식도 적음
이게 "안건 더 깊게, 안 본 건 그대로"의 자기 조직화.
이 챕터의 마지막 페이지로 정리하자.