몬테카를로 트리 탐색(MCTS)은 결정 과정, 특히 보드 게임을 실행하는 소프트웨어에서 사용되는 휴리스틱 트리 탐색 알고리즘이다. 이 알고리즘은 가장 유망한 수에 집중하여 탐색 공간의 무작위 표본 추출을 기반으로 탐색 트리를 확장함으로써 게임 트리를 해결한다. MCTS는 2016년에 신경망과 결합되었으며, 이후 체스, 쇼기, 체커, 주사위 놀이, 콘트랙트 브리지, 바둑, 스크래블, 클로버와 같은 게임뿐만 아니라 턴제 전략 비디오 게임 및 기타 영역에도 적용되었다.
이 알고리즘은 반복적인 플레이아웃(또는 롤아웃)을 통해 작동하며, 여기서 게임은 무작위 수로 끝까지 시뮬레이션된다. 이러한 플레이아웃의 결과는 게임 트리의 노드에 가중치를 부여하는 데 사용되어, 이후 선택 과정에서 더 유망한 수로 안내한다. MCTS의 각 라운드는 선택, 확장, 시뮬레이션, 역전파의 네 단계로 구성된다.
역사
결정적 문제에 무작위 표본 추출을 사용하는 몬테카를로 방법은 1940년대로 거슬러 올라간다. 1987년, 브루스 에이브럼슨은 무작위 게임 플레이아웃에 기반한 기대 결과 모델과 미니맥스 탐색을 결합하여 틱택토 및 기타 게임에서 그 효과를 입증했다. 1989년, W. 에르텔, J. 슈만, C. 주트너는 자동 정리 증명에 유사한 방법을 적용하여 탐색 시간을 개선했다. 1992년, B. 브뤼그만은 바둑 프로그램에서 이 접근 방식을 사용했다. 2002년, 창 등은 몬테카를로 트리에서 UCB 기반 탐색과 활용을 도입한 적응형 다단계 표본 추출(AMS)을 제안하여 UCT의 기초를 마련했다.
2006년, 레미 쿨롬은 몬테카를로 트리 탐색이라는 용어를 만들었고, L. 코치시와 Cs. 세페슈바리는 UCT(트리에 적용된 상한 신뢰 경계) 알고리즘을 개발했다. S. 겔리 등은 프로그램 MoGo에 UCT를 구현했으며, 2008년까지 9x9 바둑에서 단 수준에 도달했다. 2012년, Zen 프로그램은 19x19 바둑판에서 아마추어 2단 기사와의 대국에서 승리했다. Google DeepMind의 AlphaGo는 신경망과 결합된 MCTS를 사용하여 2015년에 프로 바둑 기사를 이긴 최초의 프로그램이 되었고, 2016년에는 이세돌을 꺾었다.
작동 원리
MCTS의 초점은 탐색 공간의 무작위 표본 추출을 기반으로 탐색 트리를 확장하여 가장 유망한 수를 분석하는 것이다. 각 플레이아웃은 게임을 끝까지 시뮬레이션하며, 그 결과는 더 좋은 수가 더 자주 선택되도록 노드에 가중치를 부여한다. 기본 순수 몬테카를로 게임 탐색은 각 합법적인 수에 동일한 플레이아웃을 적용하고 가장 많은 승리를 거둔 수를 선택한다.
MCTS의 각 라운드는 네 단계를 포함한다:
- 선택: 루트에서 시작하여 리프 노드에 도달할 때까지 연속적인 자식 노드를 선택한다.
- 확장: 게임이 결정되지 않은 경우, 리프에서 하나 이상의 자식 노드를 생성한다.
- 시뮬레이션: 새 노드에서 무작위 플레이아웃을 완료한다.
- 역전파: 새 노드에서 루트까지의 경로를 따라 노드 통계를 업데이트한다.
UCT 알고리즘
UCT 알고리즘은 상한 신뢰 경계 공식을 사용하여 탐색과 활용의 균형을 맞춘다. 이 알고리즘은 자식 노드의 평균 승률과 덜 방문된 노드에 대한 보너스를 기반으로 자식 노드를 선택하여, 대안을 계속 탐색하면서도 유망한 수 쪽으로 트리를 확장할 수 있게 한다. 이 접근 방식은 MCTS 효율성의 핵심이다.
응용 분야
MCTS는 헥스, 하바나, 아마존 게임, 아리마와 같은 보드 게임 프로그램뿐만 아니라 Ms. Pac-Man 및 Fable Legends와 같은 실시간 비디오 게임에도 사용되었다. 또한 스카트, 포커, 매직: 더 개더링, 카탄의 개척자와 같은 비결정적 게임에도 적용된다. 게임 외에도 MCTS는 계획 및 최적화 문제에서 탐구되었다.
의의
AlphaGo에서와 같이 MCTS와 심층 신경망의 결합은 Artificial intelligence 및 Machine learning 분야의 이정표가 되었다. 이는 휴리스틱 탐색이 Deep learning 방법과 통합되어 복잡한 영역에서 초인적 성능을 달성할 수 있음을 보여주었으며, 이후 Generative AI 및 기타 분야의 연구에 영향을 미쳤다.