몬테카를로 트리 탐색
IT 위키
- MCTS; Monte Carlo Tree Search; 몬테카를로 트리 탐색
- 무작위 시뮬레이션으로 각 수의 가치를 추정하면서 탐색 트리를 점진적으로 넓혀 가는 의사결정 알고리즘
바둑처럼 경우의 수가 너무 많아 완전 탐색이 불가능하고, 좋은 평가 함수를 만들기도 어려운 문제에 쓴다. 알파고의 핵심 구성요소였다.
한 번의 반복(iteration)은 다음 네 단계로 이루어지고, 시간이 허락하는 만큼 반복한다.
| 순서 | 단계 | 내용 |
|---|---|---|
| 1 | 선택(Selection) | 루트에서 시작해 UCT 값이 가장 큰 자식을 따라 내려간다. 아직 다 펼치지 않은 노드에 닿으면 멈춘다 |
| 2 | 확장(Expansion) | 그 노드에 자식 노드를 하나(또는 여럿) 새로 만든다 |
| 3 | 시뮬레이션(Simulation / Playout) | 새 노드에서 게임이 끝날 때까지 무작위로 수를 두어 승패를 얻는다 |
| 4 | 역전파(Backpropagation) | 그 결과를 지나온 경로의 모든 노드에 반영해 방문 횟수와 승률을 갱신한다 |
선택 단계에서 탐험과 활용의 균형을 잡는 식이다.
- UCT = w/n + C·√(ln N / n)
- w : 그 노드에서의 승리 횟수, n : 방문 횟수, N : 부모의 방문 횟수
- 앞 항은 활용(지금까지 좋았던 수), 뒤 항은 탐험(덜 가 본 수)을 뜻한다
- C 가 커지면 탐험 쪽으로 기운다
- 평가 함수가 필요 없다. 승패만 알면 되므로 도메인 지식이 적어도 쓸 수 있다
- 언제든 멈출 수 있다(Anytime). 반복을 더 할수록 좋아진다
- 유망한 가지에 계산을 집중하므로 비대칭 트리가 만들어진다
- 무작위 시뮬레이션의 편차가 커서 반복 횟수가 적으면 불안정하다
알파고는 무작위 시뮬레이션 대신 정책망으로 유망한 수를 좁히고 가치망으로 승률을 추정해 MCTS 의 약점을 보완했다. 알파제로는 자가 대국으로 이 두 망을 학습시켜 사람의 기보 없이 같은 구조를 완성했다.
