YOLO 라이선스 받기
Ultralytics 용어집으로 돌아가기

Monte Carlo Tree Search (MCTS)

몬테카를로 트리 탐색(MCTS)은 시뮬레이션 플레이아웃으로 탐색 트리를 확장하고 유망한 수에 집중해 행동을 선택합니다. AlphaGo와 로봇에 사용됩니다.

몬테카를로 트리 탐색(MCTS)은 여러 시뮬레이션 플레이아웃을 통해 가능한 미래의 트리를 확장하고, 가장 유망해 보이는 수에 더 많은 탐색 예산을 투입해 다음 행동을 선택하는 계획 알고리즘입니다. 게임 규칙이나 시뮬레이터처럼 합법적인 수와 결과를 생성하는 방법만 필요하며, 사람이 직접 작성한 평가 함수는 필요하지 않습니다. 또한 언제든지 실행을 중단해도 그때까지 찾은 최선의 수를 반환하는 애니타임 알고리즘입니다. 더 오래 실행할수록 더 나은 답을 얻습니다. Rémi Coulom은 2006년에 이 방법의 이름을 붙였고, 같은 해 Levente Kocsis와 Csaba Szepesvári는 이 방법의 표준 형태가 된 선택 규칙 UCT를 발표했습니다. MCTS는 몇 년 만에 컴퓨터 바둑의 수준을 크게 끌어올렸고, 이후 AlphaGo와 AlphaZero를 구동했으며, 현재는 로봇과 차량의 동작 계획 및 추론 단계를 탐색하는 데도 대규모 언어 모델(LLM)에서 사용됩니다.

MCTS 작동 방식#

탐색은 현재 상태를 루트로 하는 트리를 유지하며, 각 노드에는 방문 횟수와 방문 중 승리로 이어진 횟수가 저장됩니다. 각 반복은 네 단계로 이루어집니다.

  1. 선택: 루트에서 시작해 완전히 탐색된 노드를 내려가며 UCT 점수가 가장 높은 자식 노드를 선택합니다. UCT 점수는 높은 승률과 거의 시도되지 않은 수 사이의 균형을 맞춥니다.
  2. 확장: 시도하지 않은 수가 있는 첫 노드에서 해당 수를 새 자식 노드로 추가합니다.
  3. 시뮬레이션: 새 자식 노드부터 게임이 끝날 때까지 진행합니다. 전통적으로 무작위 수를 두어 결과를 얻습니다.
  4. 역전파: 경로를 따라 위로 올라가며 결과를 반영해 각 노드의 방문 횟수와 승리 합계를 업데이트합니다.

탐색 예산이 소진되면 알고리즘은 루트에서 가장 많이 방문된 자식 노드를 선택합니다. 이는 평균 점수가 가장 높은 노드보다 안정적인 선택입니다.

탐색과 활용의 균형#

UCT는 각 노드의 선택을 멀티암드 밴딧 문제로 보고 UCB1 공식을 적용합니다. 자식 노드의 점수는 승률 w/n에 c·√(ln N / n)을 더한 값입니다. 여기서 n은 자식 노드의 방문 횟수, N은 부모 노드의 방문 횟수, c는 이론상 √2이며 실제로는 조정되는 탐색 상수입니다. 두 번째 항은 수를 더 자주 시도할수록 줄어듭니다. 따라서 몇 번의 운 좋은 승리를 거둔 수가 다른 수를 밀어내지 못하며, 한동안 선택되지 않은 수도 결국 다시 검토됩니다.

다음 Python 예제는 작은 게임에서 MCTS를 실행합니다. 플레이어는 10개 돌 더미에서 한 번에 돌 1~3개를 가져가며, 마지막 돌을 가져가는 플레이어가 승리합니다.

import math
import random

# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {}  # visits and wins per node; a node is the sequence of pile sizes from the root


def rollout(stones):
    """Play random moves to the end and return 1 if the player to move wins."""
    turn = 0
    while stones:
        stones -= random.randint(1, min(3, stones))
        turn ^= 1
    return turn


def search(node):
    """Run one MCTS iteration below a node and return 1 if the player to move there wins."""
    if node[-1] == 0:
        return 0  # the opponent took the last stone
    children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
    unvisited = [c for c in children if c not in N]
    if unvisited:  # expansion, then simulation
        child = random.choice(unvisited)
        N[child], W[child] = 0, 0
        result = 1 - rollout(child[-1])
    else:  # selection by UCT, balancing win rate against how rarely a child was tried
        child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
        result = 1 - search(child)
    N[child] += 1  # backpropagation, with wins counted for the player who moved into the child
    W[child] += result
    return result


for _ in range(2000):
    search((10,))
    N[(10,)] += 1
for take in (1, 2, 3):
    child = (10, 10 - take)
    print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")

돌 두 개를 가져가는 수는 방문 2,000회 중 1,889회를 차지하고 시뮬레이션의 91%에서 승리합니다. 한 개를 가져가는 수는 68회, 세 개를 가져가는 수는 43회 방문되었습니다. 이는 승리로 이어지는 수입니다. 돌 8개를 남기면 4의 배수가 되므로, 첫 번째 플레이어는 상대의 모든 응수에 대해 4의 배수를 복원하다가 더미가 빌 때까지 진행할 수 있습니다. 탐색은 전략을 코드로 작성하지 않고 무작위 플레이아웃과 방문 통계만으로 이 수를 찾아냈습니다.

AlphaGo에서 AlphaZero와 MuZero까지#

바둑의 합법적 수는 평균 약 250개로, 체스의 약 35개보다 많아 완전 탐색이 불가능했습니다. 2000년대 후반부터 컴퓨터 바둑의 실력이 도약한 데에는 MCTS가 핵심 역할을 했습니다. DeepMind의 AlphaGo는 유력한 수를 제안하는 정책 네트워크와 가치 네트워크 및 빠른 롤아웃을 사용한 상태 평가로 MCTS를 안내했으며, 2016년 3월 이세돌을 4대 1로 이겼습니다. AlphaZero와 MuZero는 이를 한 단계 더 발전시켰습니다. AlphaZero는 롤아웃을 완전히 제거하고 가치 네트워크로 리프 상태를 평가했으며, 스스로 대국한 게임으로 네트워크를 학습했습니다. 각 탐색에서 얻은 방문 횟수를 정책 네트워크의 타깃으로 사용해 MCTS를 강화 학습 내부의 정책 개선 단계로 만들었습니다. MuZero는 학습된 환경 모델 안에서 같은 탐색을 수행하므로 규칙을 제공받지 않고도 바둑, 체스, 쇼기, 아타리 게임을 할 수 있었습니다.

계획 및 추론을 위한 MCTS#

로봇과 자율주행 차량은 교통에 합류하는 것과 같은 불확실한 상황에서 계획을 세우기 위해 MCTS를 사용합니다. POMCP와 같은 변형은 숨겨진 상태에 대한 신념 분포를 추적해 부분 관측 마르코프 결정 과정으로 MCTS를 확장합니다. 카메라 입력에서 계획하는 탐색에는 루트 상태가 필요합니다. 예를 들어 체스를 두는 로봇 팔은 보드 이미지로 학습된 Ultralytics YOLO26 모델을 사용해 모든 말을 찾고, 복원된 위치를 탐색의 루트로 삼을 수 있습니다.

LLM 추론에서 각 노드는 부분 해답이고 각 간선은 추론 단계이며, 프로세스 보상 모델이나 답 검증기가 각 분기에 점수를 부여합니다. Microsoft의 rStar-Math는 프로세스 선호도 모델과 함께 MCTS를 사용해 MATH 벤치마크의 Qwen2.5-Math-7B 점수를 58.8%에서 90.0%로 높였습니다. 사고 트리는 대신 너비 우선 탐색이나 깊이 우선 탐색으로 추론 단계를 탐색합니다. 학습 중에는 MCTS를 사용하기가 더 까다로웠습니다. DeepSeek은 DeepSeek-R1을 개발하며 MCTS를 실패한 시도 중 하나로 언급했습니다. 토큰 시퀀스 공간이 보드게임보다 훨씬 크고 탐색을 안내하는 가치 모델을 학습하기 어렵기 때문입니다. 대신 검증 가능한 보상을 통한 강화 학습으로 R1을 학습했습니다.

솔루션 살펴보기

스포츠 분야의 컴퓨터 비전

스포츠 분야의 컴퓨터 비전

Ultralytics YOLO가 선수 및 공 추적, 경기력 분석, 코칭 인사이트, 선수 재활을 통해 스포츠 비전을 구현하는 방법을 알아보세요.
자세히 알아보기
항공 이미지 컴퓨터 비전

항공 이미지 컴퓨터 비전

Ultralytics YOLO를 활용해 드론 및 항공 이미지를 농업, 양식업, 보전, 지리 공간 분석을 위한 실시간 인사이트로 전환하세요.
자세히 알아보기
항공우주 분야의 컴퓨터 비전

항공우주 분야의 컴퓨터 비전

Ultralytics YOLO를 활용해 항공기 검사, 활주로 FOD 감지, 공항 지상 운영, 복합재 결함 감지 등 항공우주 분야에 컴퓨터 비전을 적용하세요.
자세히 알아보기
보안 분야의 컴퓨터 비전

보안 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 모든 시설을 보호하세요. Vision AI는 경계 모니터링, 위협 감지, 번호판 인식, 작업장 안전을 지원합니다.
자세히 알아보기
로보틱스 분야의 컴퓨터 비전

로보틱스 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 더 스마트한 머신을 구현하세요. 로보틱스 분야의 Vision AI는 자율 주행, 인식, 객체 추적, 실시간 제어를 지원합니다.
자세히 알아보기
물류 분야의 컴퓨터 비전

물류 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 물류를 간소화하세요. 비전 AI는 화물 검사, 분류, 차량 추적, 실시간 창고 안전 모니터링을 지원합니다.
자세히 알아보기
리테일 분야의 컴퓨터 비전

리테일 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 리테일의 새로운 가능성을 열어 보세요. 비전 AI는 재고 추적, 선반 모니터링, 대기열 관리, 더욱 심층적인 고객 인사이트를 지원합니다.
자세히 알아보기
의료 분야의 컴퓨터 비전

의료 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 의료 솔루션을 구축하세요. 의료 분야의 비전 AI는 의료 영상 판독을 가속화하고, 진단을 개선하며, 환자 모니터링을 지원합니다.
자세히 알아보기
제조 분야의 컴퓨터 비전

제조 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 제조 공정을 최적화하세요. 비전 AI는 품질 관리, 결함 탐지, PPE 규정 준수, 조립 라인 자동화를 지원합니다.
자세히 알아보기
자동차 분야의 컴퓨터 비전

자동차 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 자동차 분야에 컴퓨터 비전을 적용하세요. 비전 AI는 도로 안전, 운전자 지원, 차량 자동화를 개선해 더 스마트한 도로를 구현합니다.
자세히 알아보기
농업 분야의 컴퓨터 비전

농업 분야의 컴퓨터 비전

Ultralytics YOLO 모델로 스마트 농업에 비전 AI를 도입하세요. 작물 모니터링, 가축 추적, 정밀 농업을 지원하여 더 높은 수확량과 더 스마트한 농업을 실현합니다.
자세히 알아보기

함께 AI의 미래를 만들어 가세요!

머신러닝의 미래와 함께 여정을 시작하세요