몬테카를로 트리 탐색

2024년 9월 4일 · 태그: ai, python · 원문 · 한국어 번역(원문에서 변경됨)

몬테카를로 트리 탐색은 게임 플레이와 강화 학습에서 의사 결정에 사용되는 강력한 알고리즘입니다. 이는 트리 탐색과 몬테카를로 시뮬레이션의 장점을 결합한 휴리스틱 탐색 알고리즘입니다. MCTS는 신경기호(neurosymbolic) 시스템이나 강화 학습처럼 크고 복잡한 탐색 공간을 다룰 때 특히 유용합니다.

오늘은 Python으로 MCTS를 구현해 봅시다. 먼저 상태를 표현하는 데 사용할 Node 클래스를 정의해야 합니다.

rom dataclasses import dataclass, field
from collections import defaultdict
import math
from typing import Dict, Set, List, Optional
from abc import ABC, abstractmethod
import random


class Node(ABC):
    """Abstract base class for game state nodes."""

    @abstractmethod
    def find_children(self) -> Set["Node"]:
        """Return all possible child nodes."""

    @abstractmethod
    def get_random_child(self) -> Optional["Node"]:
        """Return a random child node."""

    @abstractmethod
    def is_terminal(self) -> bool:
        """Check if the node is a terminal state."""

    @abstractmethod
    def reward(self) -> float:
        """Return the reward value for a terminal node."""

    @abstractmethod
    def __hash__(self) -> int:
        """Define a hash function for the node."""

    @abstractmethod
    def __eq__(self, other: object) -> bool:
        """Define equality comparison for nodes."""

이제 탐색 상태를 보관하고 트리 탐색을 수행할 MCTS 클래스를 정의하겠습니다.

@dataclass
class MCTS:
    """Monte Carlo Tree Search implementation."""

    exploration_weight: float = 1.0
    total_rewards: Dict[Node, float] = field(default_factory=lambda: defaultdict(float))
    visit_counts: Dict[Node, int] = field(default_factory=lambda: defaultdict(int))
    children: Dict[Node, Set[Node]] = field(default_factory=lambda: defaultdict(set))

이제 현재 노드에서 최선의 수를 선택할 select_best_move 메서드를 구현하겠습니다.

    def select_best_move(self, node: Node) -> Node:
        """Select the best move from the current node."""
        if node.is_terminal():
            raise ValueError(f"Cannot select move from terminal node: {node}")

        if node not in self.children:
            return node.get_random_child()

이 알고리즘에서는 최선의 수를 선택하기 위해 UCT(Upper Confidence Trees) 공식을 사용하겠습니다.

$$UCT(v)=\frac{w_v}{n_v}+c\sqrt{\frac{\ln (N)}{n_v}}$$

여기서:

• $w_v$는 노드의 총 보상입니다.
• $n_v$는 노드가 방문된 횟수입니다.
• $N$은 시뮬레이션의 총 횟수입니다.
• $c$는 탐험 상수입니다.

    def simulate(self, node: Node) -> None:
        """Perform one iteration of the MCTS algorithm."""
        path = self._traverse_tree(node)
        leaf = path[-1]
        self._expand_node(leaf)
        reward = self._simulate_random_playout(leaf)
        self._backpropagate(path, reward)

    def _traverse_tree(self, node: Node) -> List[Node]:
        """Traverse the tree to find an unexplored node."""
        path = []
        while True:
            path.append(node)
            if node not in self.children or not self.children[node]:
                return path
            unexplored = self.children[node] - set(self.children.keys())
            if unexplored:
                path.append(unexplored.pop())
                return path
            node = self._select_uct(node)

    def _expand_node(self, node: Node) -> None:
        """Expand the node by adding its children to the tree."""
        if node in self.children:
            return
        self.children[node] = node.find_children()

이제 주어진 노드에서 무작위 플레이아웃을 시뮬레이션할 _simulate_random_playout 메서드를 구현하겠습니다.

def _simulate_random_playout(self, node: Node) -> float:
    """Simulate a random playout from the given node."""
    invert_reward = True
    while True:
        if node.is_terminal():
            reward = node.reward()
            return 1 - reward if invert_reward else reward
        node = node.get_random_child()
        invert_reward = not invert_reward

이제 경로상의 노드들에 대한 통계를 갱신할 _backpropagate 메서드를 구현하겠습니다.

def _backpropagate(self, path: List[Node], reward: float) -> None:
    """Update the statistics for the nodes in the path."""
    for node in reversed(path):
        self.visit_counts[node] += 1
        self.total_rewards[node] += reward
        reward = 1 - reward

select 메서드는 UCT 지표를 사용하여 자식 노드를 선택합니다.

    def _select_uct(self, node: Node) -> Node:
        """Select a child node using the UCT formula."""
        assert all(n in self.children for n in self.children[node])
        log_n_parent = math.log(self.visit_counts[node])

        def uct(n: Node) -> float:
            return self.total_rewards[n] / self.visit_counts[
                n
            ] + self.exploration_weight * math.sqrt(log_n_parent / self.visit_counts[n])

        return max(self.children[node], key=uct)

그리고 마지막으로 노드의 평균 보상을 바탕으로 노드의 점수를 계산할 _calculate_node_score 메서드를 구현하겠습니다.

def _calculate_node_score(self, nodeNode) -> float:
    """Calculate the score for a node based on its average reward."""
    if self.visit_counts[node] == 0:
        return float("-inf")
    return self.total_rewards[node] / self.visit_counts[node]

이제 이를 사용하려면 게임의 상태를 표현하는 데 사용할 TicTacToeNode 클래스를 정의해야 합니다.

class TicTacToeNode(Node):
    def __init__(self, state: str, player: str):
        self.state = state
        self.player = player

    def find_children(self) -> Set["TicTacToeNode"]:
        if self.is_terminal():
            return set()
        return {
            TicTacToeNode(
                self.state[:i] + self.player + self.state[i + 1 :],
                "O" if self.player == "X" else "X",
            )
            for i, value in enumerate(self.state)
            if value == " "
        }

    def get_random_child(self) -> Optional["TicTacToeNode"]:
        if self.is_terminal():
            return None
        empty_spots = [i for i, value in enumerate(self.state) if value == " "]
        index = random.choice(empty_spots)
        return TicTacToeNode(
            self.state[:index] + self.player + self.state[index + 1 :],
            "O" if self.player == "X" else "X",
        )

    def is_terminal(self) -> bool:
        return self.winner() is not None or " " not in self.state

    def reward(self) -> float:
        winner = self.winner()
        if winner is None:
            return 0.5  # Draw
        return 1.0 if winner == self.player else 0.0

    def __hash__(self) -> int:
        return hash(self.state)

    def __eq__(self, other: object) -> bool:
        return isinstance(other, TicTacToeNode) and self.state == other.state

    def winner(self) -> Optional[str]:
        lines = [
            (0, 1, 2),
            (3, 4, 5),
            (6, 7, 8),  # Rows
            (0, 3, 6),
            (1, 4, 7),
            (2, 5, 8),  # Columns
            (0, 4, 8),
            (2, 4, 6),  # Diagonals
        ]
        for line in lines:
            if self.state[line[0]] == self.state[line[1]] == self.state[line[2]] != " ":
                return self.state[line[0]]
        return None

이제 MCTS 클래스를 사용하여 틱택토 게임을 할 수 있습니다.

def play_game():
    state = " " * 9
    mcts = MCTS()
    board = TicTacToeNode(state, "X")

    print("Initial board:")
    print_board(board.state)

    while True:
        # Human player's turn (O)
        human_move = int(input("Enter your move (0-8): "))
        board = TicTacToeNode(
            board.state[:human_move] + "O" + board.state[human_move + 1 :], "X"
        )
        print("\nBoard after your move:")
        print_board(board.state)

        if board.is_terminal():
            break

        # AI player's turn (X)
        for _ in range(1000):  # Number of MCTS iterations
            mcts.simulate(board)
        board = mcts.select_best_move(board)
        print("\nBoard after AI move:")
        print_board(board.state)

        if board.is_terminal():
            break

    winner = board.winner()
    if winner:
        print(f"\nPlayer {winner} wins!")
    else:
        print("\nIt's a draw!")


def print_board(state: str):
    for i in range(0, 9, 3):
        print(" ".join(state[i : i + 3]))


if __name__ == "__main__":
    play_game()