MCTS

개념

MCTS는 Monte Carlo Tree Search, 즉 몬테카를로 트리 탐색이다. 현재 상태에서 여러 번 시뮬레이션을 수행해 승률이나 평균 보상을 추정하고, 유망한 수를 찾는 알고리즘이다.

4단계

MCTS는 보통 다음 네 단계를 반복한다.

1. Selection: UCT 같은 기준으로 유망한 노드를 따라 내려간다.
2. Expansion: 아직 확장하지 않은 자식 노드를 만든다.
3. Rollout: 새 노드에서 게임이 끝날 때까지 빠르게 시뮬레이션한다.
4. Backpropagation: 결과를 경로를 따라 거꾸로 전달해 방문 수와 점수를 갱신한다.

미니맥스와 차이

미니맥스 알고리즘은 평가 함수를 잘 설계해야 한다. 반면 MCTS는 많은 롤아웃 결과를 통해 상태 가치를 추정한다. 그래서 평가 함수 설계가 어려운 게임에서 유용하다.

노드 $i$의 평균 가치는 누적 보상 $W_i$를 방문 횟수 $N_i$로 나누어 추정한다.

$$Q_i=\frac{W_i}{N_i}$$

실제 선택

시뮬레이션을 많이 반복한 뒤에는 루트의 자식 중 방문 수가 가장 많거나 가치가 높은 수를 실제 행동으로 선택한다.

$$a^{\ast }=\arg \underset{a}{\max }N(s_0,a)$$