몬테카를로 트리 탐색

몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)은 “가능한 모든 수를 다 읽지 않고, 무작위 시뮬레이션을 여러 번 돌려 승률이 좋아 보이는 수만 깊게 파고드는 게임 트리 탐색 알고리즘입니다.wikipedia+1

기본 아이디어

• 체스·바둑처럼 경우의 수가 폭발적으로 많은 게임에서, 전수 탐색 대신 일부 수만 샘플링해 그중 유망한 수를 선택하는 방법입니다.gusals1620.tistory+1
• 각 수(노드)에 대해 “이 수를 뒀을 때의 승률”을 반복 시뮬레이션으로 추정하고, 승률이 높아 보이는 가지를 점점 더 자주 탐색합니다.hi-guten-tag.tistory+1

네 단계 절차

MCTS는 보통 다음 네 단계를 한 번의 반복으로 보고, 이 반복을 수천·수만 번 실행합니다.jidum+2

1. 선택(Selection)
   • 루트(현재 국면)에서 시작해, 이미 펼쳐진 트리 안에서 “가장 유망한 자식 노드”를 선택하며 아래로 내려갑니다.thebook+1
   • 이때 탐색(아직 잘 모르는 수를 더 보려는 것)과 활용(이미 승률이 좋은 수를 더 파는 것)을 균형 있게 섞기 위해 UCB1 같은 수식을 쓰는 것이 일반적입니다.thebook+1
2. 확장(Expansion)
   • 선택을 계속하다가 아직 탐색되지 않았거나 덜 펼쳐진 노드에 도달하면, 거기서 새로운 자식 노드(새 수)를 하나 이상 추가해 트리를 확장합니다.wikipedia+1
3. 시뮬레이션(Simulation, Playout)
   • 방금 확장한 노드에서부터 게임이 끝날 때까지, 보통 비교적 단순한 정책(무작위 혹은 간단한 휴리스틱)으로 착수를 반복해 승패를 결정합니다.naver+1
   • 이 과정을 여러 번 반복할수록 그 노드에서의 “기대 승률” 추정이 점점 정확해집니다.news.hada+1
4. 역전파(Backpropagation)
   • 시뮬레이션 결과(승·패·무)를 해당 노드에서 루트까지 거슬러 올라가며 방문 횟수와 승리 횟수를 갱신해, 각 노드의 통계적 가치 추정을 업데이트합니다.velog+2

특징과 장점

• 탐색 자원을 “유망한 수”에 집중하기 때문에, 같은 연산량으로도 단순 미니맥스+알파베타 탐색보다 실전 성능이 좋은 경우가 많습니다.naver+1
• 규칙만 있으면 평가 함수를 명시적으로 설계하지 않고도 적용할 수 있어, 바둑처럼 정량적 형세 판단이 어려운 게임에서 특히 효과적입니다.gusals1620.tistory+1

알파고에서의 활용 (간단히)

• 알파고는 MCTS에 정책 신경망(어떤 수가 좋을지 사전 확률 제시)과 가치 신경망(현재 국면의 승률 평가)을 결합해, “확장·시뮬레이션 단계”의 품질을 크게 높인 구조였습니다.jidum+2