코드: MCTS 노드 클래스

MCTS 노드의 핵심 필드:

game — 이 노드의 게임 상태
parent, children — 트리 구조
untried_moves — 아직 자식으로 안 만들어진 수들 (Expand에서 골라감)
visits — 이 노드 방문 횟수
wins — 누적 승수 (UCB1의 분자)
ucb1() — UCB1 점수 계산 메서드

📖 ucb1() 메서드의 두 케이스

visits == 0: ∞ 반환 — 안 가본 노드를 무조건 먼저 가게 함. 모든 자식이 적어도 한 번씩 방문되도록.
visits > 0: w/n + c·√(ln(parent.visits)/n) — 표준 UCB1.

이 단순한 트릭으로 "초기에 모든 자식을 한 번씩 시도"가 자동 처리.

💡 wins의 정확한 의미

wins는 "이 노드의 부모 입장에서의 승수". 왜 부모 입장?

UCB1로 자식을 고를 때 부모가 결정하잖아. 부모는 자기한테 유리한 자식을 고름. 그래서 wins가 "부모에게 유리한 결과"의 횟수로 정의되어야.

구체적으로: 부모 차례가 X면, wins는 X 승 횟수. 부모 차례가 O면, wins는 O 승 횟수.

다음 페이지에서 4단계를 메서드로 구현.

PYTHON

# MCTS 노드 — 트리의 한 노드를 표현.
# 핵심 필드: 게임 상태, 부모, 자식들, visits, wins.

import math
import 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


# === MCTS 노드 ===
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 is_terminal(self):
        return self.game.is_terminal()

    def ucb1(self, c=math.sqrt(2)):
        """이 노드의 UCB1 점수 (부모 차례 입장에서 본 점수)"""
        if self.visits == 0:
            return float('inf')  # 안 가본 노드 우선
        exploit = self.wins / self.visits
        explore = c * math.sqrt(math.log(self.parent.visits) / self.visits)
        return exploit + explore

    def select_best_child(self, c=math.sqrt(2)):
        """UCB1 최대 자식 반환"""
        return max(self.children, key=lambda ch: ch.ucb1(c))


# === 테스트: 빈 보드에서 루트 만들기 ===
root = Node(TicTacToe())
print(f"루트 visits: {root.visits}")
print(f"루트 wins: {root.wins}")
print(f"루트의 가능한 수: {root.untried_moves}")
print(f"루트의 자식 수: {len(root.children)}")
print(f"루트가 완전 확장됨? {root.is_fully_expanded()}")
print(f"루트가 종료 상태? {root.is_terminal()}")

# 자식 하나 만들어 보기 (수 0에 둠)
move = 0
child_game = root.game.play(move)
child = Node(child_game, parent=root, move_from_parent=move)
root.children.append(child)
root.untried_moves.remove(move)

print()
print(f"=== 자식 추가 후 ===")
print(f"루트의 자식 수: {len(root.children)}")
print(f"루트의 남은 untried_moves: {root.untried_moves}")
print(f"자식의 부모: {child.parent is root}")
print(f"자식의 차례: {child.game.turn} (X가 0에 뒀으니 O 차례)")

출력

기대 출력:

루트 visits: 0
루트 wins: 0
루트의 가능한 수: [0, 1, 2, 3, 4, 5, 6, 7, 8]
루트의 자식 수: 0
루트가 완전 확장됨? False
루트가 종료 상태? False

=== 자식 추가 후 ===
루트의 자식 수: 1
루트의 남은 untried_moves: [1, 2, 3, 4, 5, 6, 7, 8]
자식의 부모: True
자식의 차례: O (X가 0에 뒀으니 O 차례)

← 이전 4단계를 그림으로 다음 → 코드: 1번의 MCTS Iteration