몬테카를로 트리 탐색
컴퓨터 과학에서 몬테카를로 트리 탐색(Monte Carlo tree search, MCTS)은 모종의 의사결정을 위한 체험적 탐색 알고리즘으로, 특히 게임을 할 때에 주로 적용된다. 선두적 예로 컴퓨터 바둑 프로그램이 있으나, 다른 보드 게임, 실시간 비디오 게임, 포커와 같은 비결정적 게임에도 사용되어 왔다.
운용 원리
[편집]몬테카를로 트리 탐색은 어떻게 움직이는 것이 가장 유망한 것인가를 분석하면서 검색 공간에서 무작위 추출에 기초한 탐색 트리를 확장하는 데 중점을 둔다. 몬테카를로 트리 탐색을 게임에 적용하는 것은 많은 '플레이아웃'(playout)에 기초한다. 각각의 플레이아웃에서 무작위 선택을 통해 게임을 끝까지 마치게 된다. 각 플레이아웃의 최종 게임 결과로 노드에 가중치를 두어 장래의 플레이아웃에서 선택할 가능성을 높인다.
플레이아웃을 사용하는 가장 기초적인 방법은 참가자가 규칙에 맞게 둔 각각의 후에 동일한 수(움직임)의 플레이아웃을 적용하고, 가장 많은 수의 승리를 이끈 움직임을 선택하는 것이다.[1] '순수 몬테카를로 게임 탐색'(Pure Monte Carlo Game Search)이라 불리는 이 방법은 종종 시간이 진행되면서 예전의 플레이아웃에서 참가자를 승리로 이끌었던 움직임에 더 많은 플레이아웃이 부과되면서 효율성이 높아진다.
몬테카를로 트리 탐색의 매 회는 다음과 같은 네 단계로 구성된다.[2]
- 선택 (Selection): 루트 R에서 시작하여 연속적인 자식 노드를 선택해 내려가 마디 L에 이른다. 몬테카를로 트리 탐색의 본질인, 게임 트리를 가장 승산 있는 수로 확장시킬 자식 노드를 선택하는 방법은 아래 난을 참고한다.
- 확장 (Expansion): 노드 L에서 승패를 내지 못하고 게임이 종료되면, 하나 또는 그 이상의 자식 노드를 생성하고 그 중 하나의 노드 C를 선택한다.
- 시뮬레이션 (Simulation): 노드C로부터 무작위의 플레이아웃을 실행한다.
- 역전달 (Backpropagation): 플레이아웃의 결과로 C에서 R까지의 경로에 있는 노드들의 정보를 갱신한다.
아래 그림은 한 차례에서의 단계의 예이다. 각 트리 노드는 플레이아웃의 '승수/실행 경기 수'를
_-_Updated_2017-11-19.svg)
같이 보기
[편집]각주
[편집]- ↑ Bernd Brügmann (1993). 《Monte Carlo Go》 (PDF). Technical report, Department of Physics, Syracuse University.
- ↑ G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, B. Bouzy (2008). “Progressive Strategies for Monte-Carlo Tree Search” (PDF). 《New Mathematics and Natural Computation》 4 (3): 343~359. doi:10.1142/s1793005708001094.