Monte Carlo Tree Search 알고리즘(MCTS)

Monte Carlo Tree Search 알고리즘(MCTS)

1. 개요

MCTS는 주로 게임 AI에서 사용되는 알고리즘이다. 이 알고리즘은 최근에 알파고에 사용되었다. 

현재 이 MCTS 알고리즘은 바둑, 체스, 오셀로 등의 모든 보드 게임 알고리즘에서 사용되고 있다. 

MCTS는 시뮬레이션을 통해 가장 승률이 좋은 행동을 하도록 하는 알고리즘이다.

MCTS는 각 상태에서 움직일 수 있는 곳이 정해져 있어야 한다. MCTS는 이름이 말해주듯이 

"game tree" 안에서 작동한다. 알고리즘의 시작은 이 트리의 루트노드로 부터 시작되며 

자식노드는 새로운 게임 상태에 대한 정보를 나타낸다.

2. MCTS의 조건

MCTS는 다음 3가지 조건을 만족할 때 사용가능하다.

1) 최대, 최소 값이 존재

2) 게임 규칙의 존재

3) 게임 길이 제한

3. MCTS 알고리즘

MCTS의 알고리즘은 다음 아래 그림과 같은 4 Step을 거친다.

1) Selection

현재 노드에서 어떠한 자식노드로 가야할지 결정하기위해서 각 노드에서 selection function을 사용한다.

selection function은 UTC라고 불리는데 다음과 같은 수식이다.

- Wi : i번 움직인 후의 승리 횟수

- ni : i번 움직인 후의 시뮬레이션 횟수

- c : exploration parameter이다. sqrt(2)가 처음 추측 값으로 적당한 역할을 한다고 한다. 

      그러나 이 값은 실험을 통해서 조정되어야 한다.

- t : 시뮬에이션의 전체 횟수이다. 즉 모든 ni의 합이 라고 할 수 있다. 이 값은 결국 부모 노드의 ni값이다.

다음 그림을 보면 더 이해하기 쉽다.

결국, 가장 높은 selection value를 가진 자식노드를 선택하여 이동하면된다.

2) Expansion

selection 할 때, 다음에 이동해서 멈출 노드의 확률을 생성한다. 

한 노드의 방문 횟 수가 threshold에 도달하면 

대부분의 수행은 한 노드의 모든 자식노드의 확장을 하도록한다.

3) Simulation

expansion 과정에서 만들어진 노드로 부터 게임을 실행한다. 기본적으로 게임이 끝날 때까지 실행하며

random하게 선택하여 움직인다. 최종적으로, 어던 플레이어가 이겻는지 track을 유지하여

backpropagation 과정으로 움직인다.

4) Backpropagation

트리의 root로 다시 올라가는 과정이다. 

각 확률 노드에 대해, "visit" count를 증가시킨다. 

또한 현재 player가 승리한 부모노드에 대해 "win" count를 증가시킨다.

이 4개의 과정을 결정한 만큼이나 시간이 되는 데까지 반복한다.

최종적으로 자식노드 중 win/visit count 비율이 가장 높은 쪽으로 움직이면 된다.

5. 참고자료

https://spin.atomicobject.com/2015/12/12/monte-carlo-tree-search-algorithm-game-ai/