Python으로 몬테카를로 트리 탐색(MCTS) 구현하기

반응형

소개: MCTS란 무엇이고, 왜 중요한가?

몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)은 복잡한 문제에서 최적의 선택을 찾기 위해 사용되는 알고리즘입니다. 이름에서 알 수 있듯이, 이 알고리즘은 몬테카를로 시뮬레이션 이라는 기법을 활용합니다. 몬테카를로 시뮬레이션이란, 무작위로 많은 경우의 수를 시도해보고 그 결과를 분석하는 방법을 말해요. 마치 주사위를 던지거나 랜덤 숫자를 생성하는 것처럼, 확률적으로 결과를 예측하는 방식이죠.

MCTS는 특히 게임 AI 나 복잡한 의사결정 문제 에서 매우 유용합니다. 예를 들어:

• 바둑이나 체스 같은 보드게임에서 다음 수를 결정할 때.
• 로봇이 어떤 경로로 이동할지 계산할 때.
• 심지어 주식 투자나 비즈니스 전략에서도 활용될 수 있어요.

그렇다면 MCTS는 어떻게 동작할까요? 핵심은 4단계 프로세스 에 있습니다:

1. Selection (선택):
   현재 상태에서 가장 유망한 선택지를 찾습니다. 이를 위해 이미 탐색된 노드들 중에서 "UCB1"이라는 공식을 사용해 최적의 노드를 선택합니다. (이 공식은 나중에 코드에서 다룰게요!)
2. Expansion (확장):
   새로운 가능성을 추가합니다. 즉, 아직 탐색하지 않은 행동(예: 게임에서 아직 시도하지 않은 수)을 트리에 추가해 탐색 공간을 넓힙니다.
3. Simulation (시뮬레이션):
   새로운 노드에서 랜덤하게 행동을 시도하며 결과를 확인합니다. 이 과정은 실제 게임을 끝까지 플레이하거나 문제를 해결할 때까지 계속됩니다.
4. Backpropagation (역전파):
   시뮬레이션 결과를 트리에 반영합니다. 예를 들어, 좋은 결과가 나왔다면 해당 경로의 점수를 올려줍니다. 이렇게 하면 다음 번에는 더 좋은 선택지를 찾을 가능성이 높아집니다.

---

왜 MCTS를 배워야 할까요?

MCTS는 단순히 "랜덤하게 시도해보는" 방법이 아니라, 데이터를 기반으로 점진적으로 학습 하는 알고리즘입니다. 이 덕분에 아래와 같은 장점이 있어요:

1. 직관적이다:
   MCTS는 인간이 문제를 해결하는 방식과 비슷합니다. 우리는 모든 경우의 수를 다 고려하지 않고, 경험을 통해 가장 유망한 선택지를 찾아가죠. MCTS도 똑같은 방식으로 동작합니다.
2. 유연하다:
   규칙만 정해져 있다면, 거의 모든 문제에 적용할 수 있습니다. 게임뿐만 아니라 경로 탐색, 스케줄링 등 다양한 분야에서 활용할 수 있어요.
3. 강화학습과 결합 가능:
   AlphaGo나 AlphaZero 같은 현대적인 AI 시스템은 MCTS와 딥러닝을 결합해 더욱 강력한 성능을 발휘합니다. 지금 당장은 신경망이 어렵더라도, MCTS만으로도 충분히 재미있는 결과를 얻을 수 있습니다.

---

이 글에서는 무엇을 배우게 될까요?

이 글에서는 Python을 사용해 MCTS를 직접 구현해볼 거예요. 단순히 개념만 설명하는 것이 아니라, 실제로 코드를 작성하고 실행하면서 MCTS의 동작 원리를 체험할 수 있습니다. 초보자도 쉽게 따라 할 수 있도록 단계별로 설명할 테니, 걱정하지 마세요!

---

본문: Python 코드로 MCTS 구현하기

이제 본격적으로 Python으로 MCTS를 구현해보겠습니다. 각 단계를 차근차근 설명하면서 코드를 작성할 테니, 초보자도 쉽게 따라 할 수 있을 거예요. 먼저, 우리가 만드는 예제는 "숫자 맞추기 게임"입니다. 컴퓨터가 1부터 10 사이의 숫자 중 하나를 찾아내는 것이 목표입니다.

---

1. 기본 클래스 정의

MCTS를 구현하려면, 상태(State)와 노드(Node)라는 두 가지 핵심 개념을 정의해야 합니다.

• State(상태): 현재 상황을 나타냅니다. 예를 들어, 어떤 숫자를 추측했는지, 목표 숫자에 도달했는지 등을 저장합니다.
• Node(노드): 트리 구조의 한 요소입니다. 각 노드는 특정 상태를 가리키며, 방문 횟수와 누적 보상을 기록합니다.

아래는 Node와 State 클래스를 정의한 코드입니다. 각 부분의 역할을 주석으로 자세히 설명했으니 천천히 읽어보세요!

import random
import math

class Node:
    def __init__(self, state, parent=None):
        self.state = state  # 현재 상태
        self.parent = parent  # 부모 노드
        self.children = []  # 자식 노드들
        self.visits = 0  # 방문 횟수
        self.value = 0  # 누적 보상 값

    def is_fully_expanded(self):
        # 모든 가능한 행동을 탐색했는지 확인
        return len(self.children) == len(self.state.get_possible_actions())

    def select_child(self):
        # UCB1 공식을 사용해 최적의 자식 노드 선택
        return max(self.children, key=lambda child: child.ucb1())

    def ucb1(self):
        # UCB1 공식 계산: 탐험과 활용의 균형을 맞춤
        if self.visits == 0:
            return float('inf')  # 아직 방문하지 않은 노드는 우선 선택
        return (self.value / self.visits) + math.sqrt(2 * math.log(self.parent.visits) / self.visits)

class State:
    def __init__(self, target_number):
        self.target_number = target_number  # 목표 숫자
        self.current_guess = None  # 현재 추측값

    def get_possible_actions(self):
        # 가능한 행동(숫자 후보) 반환
        return list(range(1, 11))  # 1부터 10까지의 숫자

    def is_terminal(self):
        # 종료 상태인지 확인
        return self.current_guess == self.target_number

    def simulate(self):
        # 랜덤 시뮬레이션을 통해 결과 반환
        return random.choice(self.get_possible_actions()) == self.target_number

코드 설명:

• Node 클래스는 트리의 각 노드를 나타냅니다. 방문 횟수(visits)와 누적 보상(value)을 기록하며, 자식 노드들을 관리합니다.
• State 클래스는 현재 상태를 관리합니다. 가능한 행동(get_possible_actions)과 종료 조건(is_terminal)을 정의하며, 시뮬레이션 결과를 반환합니다.

 

2. Selection (선택) 단계

Selection 단계에서는 현재 트리 내에서 가장 유망한 노드를 선택합니다. 이를 위해 UCB1 공식 을 사용합니다. 이 공식은 "탐험(Exploration)"과 "활용(Exploitation)"의 균형을 맞추는 데 도움을 줍니다.

def selection(node):
    while not node.state.is_terminal():
        if not node.is_fully_expanded():
            return expansion(node)
        else:
            node = node.select_child()
    return node

코드 설명:

• selection 함수는 현재 노드가 종료 상태가 아닐 때까지 실행됩니다.
• 만약 모든 가능한 행동을 탐색하지 않았다면, expansion 함수를 호출해 새로운 노드를 추가합니다.
• 그렇지 않으면, UCB1 공식을 사용해 가장 유망한 자식 노드를 선택합니다.

3. Expansion (확장) 단계

Expansion 단계에서는 새로운 노드를 추가하여 탐색 공간을 확장합니다. 즉, 아직 시도하지 않은 행동을 트리에 추가합니다.

def expansion(node):
    possible_actions = node.state.get_possible_actions()
    for action in possible_actions:
        if action not in [child.state.current_guess for child in node.children]:
            new_state = State(node.state.target_number)
            new_state.current_guess = action
            new_node = Node(new_state, parent=node)
            node.children.append(new_node)
            return new_node

코드 설명:

• expansion 함수는 가능한 행동 중 아직 탐색되지 않은 것을 찾아 새로운 노드를 생성합니다.
• 새로운 노드는 현재 상태에서 특정 행동을 선택한 결과를 나타냅니다.

4. Simulation (시뮬레이션) 단계

Simulation 단계에서는 랜덤하게 행동을 선택하며 결과를 시뮬레이션합니다. 이 단계는 실제 문제를 해결하지 않고, 대략적인 성공 가능성을 평가합니다.

 

def simulation(node):
    temp_state = State(node.state.target_number)
    temp_state.current_guess = node.state.current_guess
    while not temp_state.is_terminal():
        temp_state.current_guess = random.choice(temp_state.get_possible_actions())
    return temp_state.simulate()

코드 설명:

• simulation 함수는 현재 상태에서 무작위로 행동을 선택하며, 목표 숫자에 도달할 때까지 반복합니다.
• 시뮬레이션이 끝나면, 결과를 반환합니다(True 또는 False).

5. Backpropagation (역전파) 단계

Backpropagation 단계에서는 시뮬레이션 결과를 트리에 반영합니다. 이를 통해 좋은 결과를 낸 경로의 점수가 올라가고, 다음 번에는 더 유망한 선택지를 찾을 가능성이 높아집니다.

def backpropagation(node, result):
    while node is not None:
        node.visits += 1
        node.value += result
        node = node.parent

코드 설명:

• backpropagation 함수는 현재 노드부터 루트 노드까지 거슬러 올라가며 방문 횟수와 누적 보상을 업데이트합니다.
• 이렇게 하면 트리 전체가 시뮬레이션 결과를 반영하게 됩니다.

---

6. MCTS 메인 함수

위의 4단계를 결합하여 MCTS 알고리즘을 완성합니다. 아래는 최종적으로 MCTS를 실행하는 코드입니다.

 

def mcts(root_state, iterations=1000):
    root_node = Node(root_state)

    for _ in range(iterations):
        # 1. Selection
        selected_node = selection(root_node)

        # 2. Expansion
        if not selected_node.state.is_terminal():
            selected_node = expansion(selected_node)

        # 3. Simulation
        simulation_result = simulation(selected_node)

        # 4. Backpropagation
        backpropagation(selected_node, simulation_result)

    # 최종적으로 가장 많이 방문된 노드 선택
    best_child = max(root_node.children, key=lambda child: child.visits)
    return best_child.state.current_guess

코드 설명:

• mcts 함수는 설정된 반복 횟수만큼 MCTS 과정을 반복합니다.
• 각 반복마다 Selection, Expansion, Simulation, Backpropagation 단계를 거칩니다.
• 마지막에는 가장 많이 방문된 노드를 선택하여 최종 추측값을 반환합니다.

---

7. 실행 예제

이제 위의 코드를 실행해 "숫자 맞추기 게임"을 풀어봅시다.

 

if __name__ == "__main__":
    target_number = 7  # 목표 숫자
    initial_state = State(target_number)
    result = mcts(initial_state, iterations=1000)
    print(f"추측 결과: {result}")

코드 설명:

• target_number는 컴퓨터가 찾아야 할 숫자입니다.
• mcts 함수를 호출하면, 1000번의 반복을 통해 최적의 추측값을 찾아냅니다.
• 결과는 목표 숫자(7)에 가까운 값을 출력합니다.

결론: MCTS를 어디에 쓸 수 있을까?

MCTS는 복잡한 문제에서 최적의 선택을 찾기 위해 사용되는 강력한 도구입니다. 이제 막 배우기 시작했다면, 아래와 같이 간단한 상황부터 적용해보세요:

1. 게임 AI 만들기:
   바둑, 체스 같은 보드게임이나 숫자 맞추기처럼 규칙이 있는 게임에서 AI를 만들어보세요. MCTS는 사람이 직접 모든 경우의 수를 계산하지 않아도, 컴퓨터가 스스로 최선의 수를 찾아줍니다.
2. 복잡한 의사결정 문제 해결:
   예를 들어, 주식 투자나 경로 탐색처럼 다양한 선택지 중 하나를 골라야 하는 문제에도 MCTS를 적용할 수 있습니다. 처음에는 단순한 문제부터 시도해보고, 점차 복잡한 문제로 확장해보세요.
3. 강화학습과 결합하기:
   MCTS는 자체적으로도 유용하지만, AlphaZero처럼 신경망과 결합하면 더 놀라운 성능을 발휘합니다. 아직 신경망은 어렵다면, 먼저 MCTS만으로도 충분히 재미있는 결과를 얻을 수 있습니다.

---

다음 단계: 실전에서 연습하기

위에서 작성한 코드를 실행하면서 몇 가지 실험을 해보세요:

• target_number를 바꿔가며 다른 숫자를 맞춰보세요.
• iterations 값을 늘리거나 줄여보면서 알고리즘의 성능이 어떻게 변하는지 확인하세요.
• 가능하다면, 자신만의 새로운 게임(예: 가위바위보)을 만들어 MCTS를 적용해보세요.

---

궁금한 점이 있다면?

처음 배울 때는 낯설 수 있지만, 반복해서 코드를 수정하고 실험하다 보면 금방 익숙해질 거예요. 혹시 이해가 안 되는 부분이나 궁금한 점이 있다면 댓글로 남겨주세요! 추가 설명이나 예제를 드릴게요. 😊

---

결론: MCTS의 한계와 개선 방향

MCTS는 강력하지만 몇 가지 한계점이 있습니다:

1. 시간 소모: 많은 시뮬레이션이 필요하므로 계산 비용이 높습니다.
2. 탐색 공간 크기: 상태 공간이 크면 효율성이 떨어질 수 있습니다.

이러한 한계를 극복하기 위해 다음과 같은 개선 방법이 연구되고 있습니다:

• 뉴럴 네트워크 결합: AlphaZero와 같이 신경망을 활용해 시뮬레이션 효율성을 높입니다.
• 병렬 처리: 여러 CPU/GPU를 사용해 시뮬레이션을 동시에 실행합니다.

추가 학습 자료:

• Monte Carlo Tree Search - Wikipedia
• AlphaZero Paper