코드: 완성된 MCTS — best_move 함수

완성된 MCTS의 두 가지 테스트:

🎯 테스트 1: 빈 보드

1000번 iteration. 가운데 (1,1)에 191번 방문 (19%) — 최다
코너 (2,2)도 171번 — 2위 (코너도 강한 수)
약한 변 자리 (0,1)는 64번만 시도
MCTS의 답: (1,1) — 정답

🎯 테스트 2: 응징 시나리오

X(0,0), O(0,1) 후 X 차례. PART 2 Ch 5 §5와 같은 상황. minimax는 (1,1)이 정답이라고 했지.

2000번 iteration 중 (1,1)에 725번 방문 (36%)
(1,1) 승률 85.9% — 압도적
2위 (2,0) 519번 방문, 83% 승률 — 대각 코너도 강함
MCTS의 답: (1,1) — minimax와 일치

MCTS가 minimax와 같은 정답을 다른 방식으로 찾았다. 끝까지 안 보고, 통계로.

💡 MCTS의 강점

평가 함수 불필요 — 게임 규칙만 알면 됨
시간 가변 — iteration 수로 조절 (1000번이든 10만 번이든)
점진적 개선 — 더 많이 돌리면 더 정확
비대칭 트리 — 좋은 가지로 깊이 들어감

이게 minimax의 두 약점(평가 함수, 분기 인자)을 동시에 우회. 알파고가 이걸로 도약.

다음 챕터에서 같은 MCTS를 7x7 바둑에 적용해 minimax 7x7과 정면 대결.

PYTHON

# 완성된 MCTS — 임의 게임 상태에서 최선의 수를 반환.
# iteration 수가 많을수록 정확. 시뮬레이션 + 통계의 본질.

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
    def show(self):
        for r in range(3):
            print(' | '.join(self.board[r*3:(r+1)*3]))
            if r < 2: print('-'*9)

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))


def mcts_best_move(game, n_iterations=1000):
    """주어진 게임 상태에서 N번 iteration 후 최선의 수 반환"""
    root = Node(game)
    for _ in range(n_iterations):
        # ① Select
        node = root
        while node.is_fully_expanded() and not node.game.is_terminal():
            node = node.best_child()
        # ② Expand
        if not node.game.is_terminal() and node.untried_moves:
            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)
            node = child
        # ③ Simulate
        g = node.game
        while g.winner() is None:
            g = g.play(random.choice(g.possible_moves()))
        winner = g.winner()
        # ④ Backup
        cur = node
        while cur is not None:
            cur.visits += 1
            if cur.parent is not None:
                parent_turn = cur.parent.game.turn
                if winner == parent_turn:
                    cur.wins += 1
                elif winner == 'draw':
                    cur.wins += 0.5
            cur = cur.parent
    # 가장 많이 방문된 자식 반환
    best = max(root.children, key=lambda ch: ch.visits)
    return best.move_from_parent, best.visits, root.children


# === 테스트 1: 빈 보드 (X 선) ===
random.seed(42)
print("=== 빈 보드에서 MCTS (1000번 iteration) ===")
move, visits, children = mcts_best_move(TicTacToe(), n_iterations=1000)
r, c = move // 3, move % 3
print(f"MCTS의 최선 수: ({r},{c}), visits {visits}")
print(f"자식별 visits: {sorted([(ch.move_from_parent, ch.visits) for ch in children])}")

# === 테스트 2: 응징 시나리오 (Ch 5 §5와 같음) ===
print()
print("=== 시나리오: X(0,0), O(0,1) 실수. X 차례 — 정답은 (1,1) ===")
random.seed(42)
g = TicTacToe().play(0).play(1)
g.show()
print()
move, visits, children = mcts_best_move(g, n_iterations=2000)
r, c = move // 3, move % 3
print(f"MCTS 다음 수: ({r},{c}), visits {visits}")
sorted_ch = sorted(children, key=lambda ch: -ch.visits)
print("상위 3개:")
for ch in sorted_ch[:3]:
    p = ch.move_from_parent
    rate = ch.wins/ch.visits if ch.visits else 0
    print(f"  ({p//3},{p%3}) visits={ch.visits} 승률={rate:.1%}")

출력

기대 출력:

=== 빈 보드에서 MCTS (1000번 iteration) ===
MCTS의 최선 수: (1,1), visits 191
자식별 visits: [(0, 105), (1, 64), (2, 129), (3, 84), (4, 191), (5, 86), (6, 94), (7, 76), (8, 171)]

=== 시나리오: X(0,0), O(0,1) 실수. X 차례 — 정답은 (1,1) ===
X | O |  
---------
  |   |  
---------
  |   |  

MCTS 다음 수: (1,1), visits 725
상위 3개:
  (1,1) visits=725 승률=85.9%
  (2,0) visits=519 승률=83.1%
  (1,0) visits=212 승률=73.3%

← 이전 코드: 1번의 MCTS Iteration 다음 → 비대칭으로 자라는 트리