몬테카를로 트리 탐색

컴퓨터 과학에서 몬테카를로 트리 탐색(Monte Carlo tree search, MCTS)은 모종의 의사결정을 위한 체험적 탐색 알고리즘으로, 특히 게임을 할 때에 주로 적용된다. 선두적 예로 컴퓨터 바둑 프로그램이 있으나, 다른 보드 게임, 실시간 비디오 게임, 포커와 같은 비결정적 게임에도 사용되어 왔다.

운용 원리

몬테카를로 트리 탐색은 어떻게 움직이는 것이 가장 유망한 것인가를 분석하면서 검색 공간에서 무작위 추출에 기초한 탐색 트리를 확장하는 데 중점을 둔다. 몬테카를로 트리 탐색을 게임에 적용하는 것은 많은 '플레이아웃'(playout)에 기초한다. 각각의 플레이아웃에서 무작위 선택을 통해 게임을 끝까지 마치게 된다. 각 플레이아웃의 최종 게임 결과로 노드에 가중치를 두어 장래의 플레이아웃에서 선택할 가능성을 높인다.

플레이아웃을 사용하는 가장 기초적인 방법은 참가자가 규칙에 맞게 둔 각각의 후에 동일한 수(움직임)의 플레이아웃을 적용하고, 가장 많은 수의 승리를 이끈 움직임을 선택하는 것이다. '순수 몬테카를로 게임 탐색'(Pure Monte Carlo Game Search)이라 불리는 이 방법은 종종 시간이 진행되면서 예전의 플레이아웃에서 참가자를 승리로 이끌었던 움직임에 더 많은 플레이아웃이 부과되면서 효율성이 높아진다.

몬테카를로 트리 탐색의 매 회는 다음과 같은 네 단계로 구성된다.

• 선택 (Selection): 루트 R에서 시작하여 연속적인 자식 노드를 선택해 내려가 마디 L에 이른다. 몬테카를로 트리 탐색의 본질인, 게임 트리를 가장 승산 있는 수로 확장시킬 자식 노드를 선택하는 방법은 아래 난을 참고한다.
• 확장 (Expansion): 노드 L에서 승패를 내지 못하고 게임이 종료되면, 하나 또는 그 이상의 자식 노드를 생성하고 그 중 하나의 노드 C를 선택한다.
• 시뮬레이션 (Simulation): 노드C로부터 무작위의 플레이아웃을 실행한다.
• 역전달 (Backpropagation): 플레이아웃의 결과로 C에서 R까지의 경로에 있는 노드들의 정보를 갱신한다.

아래 그림은 한 차례에서의 단계의 예이다. 각 트리 노드는 플레이아웃의 '승수/실행 경기 수'를

몬테카를로 트리 순회의 각 단계의 예: 선택, 확장, 시뮬레이션, 역전달