몬테카를로 트리 탐색(MCTS)은 컴퓨터 과학의 일부 결정 과정, 특히 게임 플레이에서 사용되는 휴리스틱 탐색 알고리즘이다. 2016년에 구글 딥마인드가 개발한 알파고와 같은 프로그램에서 두각을 나타냈으며, 이후 체스, 쇼기, 바둑과 같은 보드 게임과 비디오 게임, 비게임 응용 분야에도 적용되었다.
이 알고리즘은 무작위 표본 추출을 기반으로 탐색 트리를 확장하여 가장 유망한 움직임에 집중한다. 각 라운드는 선택, 확장, 시뮬레이션, 역전파의 네 단계로 구성된다.
- 선택: 루트 노드에서 시작하여 자식 노드를 선택해 나간다. 이때 선택은 유망한 움직임에 치우치도록 설계되며, 이는 종종 UCT(신뢰 상한 적용 트리)를 사용한다.
- 확장: 리프 노드에 도달하면 하나 이상의 자식 노드를 생성하여 트리를 확장한다.
- 시뮬레이션: 확장된 노드에서 시작하여 게임이 끝날 때까지 무작위 플레이아웃을 완료한다.
- 역전파: 시뮬레이션 결과를 사용하여 선택된 경로의 노드들을 업데이트하고, 승리 횟수와 방문 횟수를 적절히 증가시킨다.
이 과정은 게임이 끝날 때까지 반복되며, 각 플레이어는 자신의 승리 확률을 최대화하는 움직임을 선택한다.
UCT 알고리즘
UCT 알고리즘은 2006년에 소개되었으며, 탐색 트리의 균형 잡힌 탐색과 활용을 위해 신뢰 상한을 적용한다. 이는 무작위 표본 추출을 기반으로 하여 가장 유망한 움직임을 선택하면서도 아직 덜 탐색된 노드에 대한 탐험을 장려한다. UCT는 MoGo와 같은 프로그램에서 MCTS 구현의 표준이 되었다.
응용 분야
MCTS는 Hex, Havannah, Game of the Amazons, Arimaa와 같은 보드 게임과 Ms. Pac-Man, Fable Legends와 같은 실시간 비디오 게임에 사용되어 왔다. 또한 Skat, 포커, 매직: 더 개더링, 카탄의 개척자와 같은 비결정적 게임도 처리한다. 턴제 전략 게임인 토탈 워: 로마 II는 캠페인 AI에 MCTS를 사용한다. 게임 외에도 계획 및 최적화 문제에 응용되고 있다.
MCTS와 신경망의 결합은 알파고에서 입증된 것처럼 특히 효과적이다. 이 하이브리드 접근 방식은 신경망을 사용하여 선택을 안내하고 위치를 평가함으로써 광범위한 무작위 플레이아웃의 필요성을 줄인다. 알파제로와 같은 후속 프로그램은 이를 체스와 쇼기에 적용하여 초인적인 성능을 달성했다.