몬테카를로 트리 탐색 (Monte Carlo Tree Search)
몬테카를로 트리 검색 (Monte Carlo Tree Search:MCTS)는 게임 같은 영역에서 주로 사용되는 트리 검색 이론이다.
선택이 연속적이고 선택지가 매우 많은 사용 사례에서 주로 사용되고, 가장 대표적인 사용사례가 바둑이나 체스 같은 게임이다. 그 외에 로봇 경로 탐색 같은 경우에도 쓰이기도 한다.
개념 자체는 2006년에 나왔다.
기본 논리
MCTS의 핵심 논리는 반복적인 시뮬이션을 통해 통계를 쌓고, 이를 통해 최선의 선택지를 도출하는 것이다. 어떻게 보면 요즘 ML 모델들의 학습과도 비슷해보이기도 한다.
바둑만 해도 모든 경우의 수를 고려해서 뭔가를 하는 것이 사실상 불가능하다. 매 선택마다 100개가 넘는 선택지가 있는데, 그러면 3번만 진행해도 1NN^3의 경우의 수가 존재하는 것이다.
이렇듯 모든 경로의 조합, 경우의 수를 처리하는 것이 불가능하기 때문에, 특정 경로를 위주로만 학습을 돌린 다음에, 그걸 통해 최적의 선택지를 도출해내는 것이다.
게임 인공지능의 가장 대표적인 형태라고 할 수 있다.
상세 논리
총 4개의 스텝으로 구성된다.
https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
- Selection (선택) - 현재 통계를 기반으로 노드(선택지) 선택
- Expansion (확장) - 선택된 최상위 노드에서 아직 보지 않은 노드가 있다면 추가하고 내려가기
- Simulation (실행) - 결과가 나올때까지 타고 들어가기 (승패상관없이)
- Backpropagation (역전파) - 결과가 나오면 해당 결과를 통계에 기록 (거쳐온 모든 노드에 대해)
Selection->Expansion으로 트리 타고 내려가면서 재귀적으로 계속 돌다가, 다 끝나면 역전파로 통계 정보를 기록하는 것이다.
반복은 원하는 만큼 돌리면 되는데, 당연히 반복의 횟수만큼 좋은 품질이 나온다.
통계가 충분히 쌓인다면, 해당 통계 정보를 기반으로 "승률이 높은" 선택지를 합리적으로 선택할 수 있다.
응용과 현재
MCTS는 게임 AI를 만들때도 많이 사용했지만, 이 자체로 머신러닝의 토대가 되기도 했다.
한때 유명했던 AlphaGo 같은 경우에도 신경망과 MCTS를 결합한 하이브리드 방식으로 뛰어난 게임 성능을 구현했다. 이걸 Neural MCTS라고도 부르는데, 요즘 나오는 고성능 게임 AI들은 대부분 이 방식을 차용한다.