코드: 1번의 MCTS Iteration

드디어 진짜 MCTS! 한 번의 iteration이 4줄 함수:

def mcts_iteration(root):
    leaf = select(root)           # ① 트리 따라 내려감
    new_child = expand(leaf)      # ② 새 자식 추가
    winner = simulate(new_child)  # ③ Rollout
    backup(new_child, winner)     # ④ 결과 역전파

500번 iteration 후 결과:

가운데 (1,1)에 90번 방문, 승률 75% — 가장 많이 시도되고 가장 강함
코너들 (0,0), (0,2), (2,2): 49~74번 방문, 61~71%
변들 (0,1), (1,0), (1,2), (2,1): 39~54번 방문, 55~64%
약한 자리 (2,0): 34번만 방문 — UCB1이 별로라 판단

🎯 Pure Monte Carlo와의 차이

지난 챕터 Pure MC: 모든 자리에 1000번씩 균등 시도 (9000번 총). 가운데 70.7% 발견.

지금 MCTS: 500번만 시도. 가운데에 90번 (가장 많이) 시도하면서 75% 발견. 1/18의 시도로 더 정확한 답.

이게 UCB1의 힘 — 좋은 수에 더 많은 자원 자동 집중.

💡 visits가 더 신뢰할 만한 지표

약한 자리 (2,0)의 승률이 54%로 나오는데, 시도가 34번뿐이라 통계적으로 의미 약함. UCB1이 별로라 판단해 덜 시도.

그래서 MCTS에서 최선의 수는 "승률 최고"가 아니라 "visits 최고". 위 결과에서 (1,1)이 압도적 최다 → 정답.

다음 페이지에서 더 많은 iteration으로 정확도를 높이고, 다양한 보드에 적용.

PYTHON

# MCTS iteration 1번 = Select → Expand → Simulate → Backup
# 모든 부품을 합쳐서 한 번의 트리 성장을 실현.

import math, random

EMPTY, X, O = ' ', 'X', 'O'

class TicTacToe:
    LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
    def __init__(self, board=None, turn=None):
        self.board = board if board is not None else [EMPTY]*9
        self.turn = turn or X
    def possible_moves(self):
        return [i for i in range(9) if self.board[i] == EMPTY]
    def play(self, pos):
        nb = self.board[:]; nb[pos] = self.turn
        return TicTacToe(nb, O if self.turn == X else X)
    def winner(self):
        for a, b, c in self.LINES:
            if self.board[a] != EMPTY and self.board[a] == self.board[b] == self.board[c]:
                return self.board[a]
        if EMPTY not in self.board: return 'draw'
        return None
    def is_terminal(self):
        return self.winner() is not None


class Node:
    def __init__(self, game, parent=None, move_from_parent=None):
        self.game = game
        self.parent = parent
        self.move_from_parent = move_from_parent
        self.children = []
        self.untried_moves = list(game.possible_moves())
        self.visits = 0
        self.wins = 0

    def is_fully_expanded(self):
        return len(self.untried_moves) == 0

    def ucb1(self, c=math.sqrt(2)):
        if self.visits == 0: return float('inf')
        return self.wins/self.visits + c*math.sqrt(math.log(self.parent.visits)/self.visits)

    def best_child(self, c=math.sqrt(2)):
        return max(self.children, key=lambda ch: ch.ucb1(c))


# ===== MCTS 4단계 =====

def select(node):
    """① Select — 완전 확장됐고 종료 아니면 best_child로 내려감"""
    while node.is_fully_expanded() and not node.game.is_terminal():
        node = node.best_child()
    return node

def expand(node):
    """② Expand — 미시도 수 하나로 새 자식 추가"""
    if node.game.is_terminal():
        return node
    move = random.choice(node.untried_moves)
    node.untried_moves.remove(move)
    child_game = node.game.play(move)
    child = Node(child_game, parent=node, move_from_parent=move)
    node.children.append(child)
    return child

def simulate(node):
    """③ Simulate — rollout. 끝까지 무작위로 두고 승자 반환"""
    game = node.game
    while game.winner() is None:
        game = game.play(random.choice(game.possible_moves()))
    return game.winner()

def backup(node, winner):
    """④ Backup — 노드부터 루트까지 visits, wins 갱신"""
    while node is not None:
        node.visits += 1
        # 이 노드의 부모 차례 입장에서 승자가 좋은지
        if node.parent is not None:
            parent_turn = node.parent.game.turn
            if winner == parent_turn:
                node.wins += 1
            elif winner == 'draw':
                node.wins += 0.5
        node = node.parent

def mcts_iteration(root):
    """1번의 MCTS iteration"""
    leaf = select(root)
    new_child = expand(leaf)
    winner = simulate(new_child)
    backup(new_child, winner)


# === 500번 iteration 후 루트 자식들 살펴보기 ===
random.seed(42)
root = Node(TicTacToe())

for _ in range(500):
    mcts_iteration(root)

print(f"=== 500번 iteration 후 ===")
print(f"루트 visits: {root.visits}")
print(f"루트 자식 수: {len(root.children)}")
print()
print(f"=== 자식들 통계 (visits 내림차순) ===")
print(f"  {'자리':<8} {'visits':>8} {'wins':>8} {'승률':>8}")
for child in sorted(root.children, key=lambda c: -c.visits):
    pos = child.move_from_parent
    r, c = pos // 3, pos % 3
    rate = child.wins / child.visits if child.visits > 0 else 0
    print(f"  ({r},{c})    {child.visits:>8} {child.wins:>8.1f} {rate:>7.1%}")

출력

기대 출력:

=== 500번 iteration 후 ===
루트 visits: 500
루트 자식 수: 9

=== 자식들 통계 (visits 내림차순) ===
  자리         visits     wins       승률
  (1,1)          90     67.5   75.0%
  (2,2)          74     52.5   70.9%
  (0,2)          62     42.0   67.7%
  (1,0)          54     34.5   63.9%
  (1,2)          53     33.5   63.2%
  (0,0)          49     30.0   61.2%
  (2,1)          45     27.0   60.0%
  (0,1)          39     21.5   55.1%
  (2,0)          34     18.5   54.4%

← 이전 코드: MCTS 노드 클래스 다음 → 코드: 완성된 MCTS — best_move 함수