코드: 7x7 바둑 MCTS

실측 결과:

1000번 iteration이 0.47초 — 빠름
MCTS의 첫 수: (5,5) — 중앙 부근
49 자식 모두 21번씩 시도 (균등)
모든 자식의 승률이 50% — 어? 신호가 안 잡힘?

⚠️ 모든 자식의 승률 50% — 단순 평가 함수의 한계

우리 코드의 평가 함수는 매우 단순 — "돌 수가 많은 쪽 승, 동률은 draw". 7x7 무작위 게임에서는 양쪽 돌 수가 거의 항상 동률에 가까워 → 대부분 무승부.

그래서 MCTS가 어떤 첫 수를 둬도 결과적으로 50:50으로 보임. 신호가 없으니 UCB1이 모든 자식을 균등하게 시도.

이게 Ch 5의 주제 — MCTS의 한계. 평가가 너무 단순하면 통계 신호가 묻힘.

🎯 PART 2 Ch 6 minimax와의 비교

알고리즘	첫 수 추천	시간	선택 양상
minimax 깊이 4	(0,0) 코너	0.02s	사전순 첫 자리에 갇힘
MCTS 1000 iter	(5,5) 중앙 부근	0.47s	균등 탐색, 우연한 중앙 선택

둘 다 약한 평가 함수에 막혀있지만, minimax는 사전순으로 망함, MCTS는 적어도 균등하게 탐험 — 우연이라도 중앙을 선택. 진짜 다른 게임에서는 (실제 영역 평가 사용 시) MCTS가 압승.

다음 페이지에서 iteration 수를 늘리면 어떻게 변하는지 보자.

PYTHON

# 바둑 게임 클래스 + MCTS 결합.
# PART 1 Ch 6의 Board 클래스를 단순화해서 사용.

import math, random, time

class GoBoard:
    """7x7 바둑 (단순화: 따냄/자살수 무시, 일정 수 이상이면 끝)"""
    EMPTY, BLACK, WHITE = 0, 1, 2
    SIZE = 7
    MAX_MOVES = SIZE * SIZE - 5  # 거의 다 차면 종료

    def __init__(self, board=None, turn=None, move_count=0):
        self.board = board if board else [[0]*self.SIZE for _ in range(self.SIZE)]
        self.turn = turn if turn else self.BLACK
        self.move_count = move_count

    def possible_moves(self):
        return [(r, c) for r in range(self.SIZE) for c in range(self.SIZE)
                if self.board[r][c] == self.EMPTY]

    def play(self, move):
        r, c = move
        nb = [row[:] for row in self.board]
        nb[r][c] = self.turn
        next_turn = self.WHITE if self.turn == self.BLACK else self.BLACK
        return GoBoard(nb, next_turn, self.move_count + 1)

    def is_terminal(self):
        return self.move_count >= self.MAX_MOVES or not self.possible_moves()

    def winner(self):
        """단순 평가: 돌 수가 많은 쪽 승. 동률은 black이 작은 쪽 패 (덤 효과)."""
        if not self.is_terminal():
            return None
        b = sum(row.count(self.BLACK) for row in self.board)
        w = sum(row.count(self.WHITE) for row in self.board)
        if b > w: return self.BLACK
        if w > b: return self.WHITE
        return 'draw'

    def show(self):
        sym = {self.EMPTY:'.', self.BLACK:'X', self.WHITE:'O'}
        for row in self.board:
            print(' '.join(sym[v] for v in row))


# === MCTS Node (Ch 3와 거의 동일) ===
class Node:
    def __init__(self, game, parent=None, move=None):
        self.game = game; self.parent = parent; self.move = move
        self.children = []
        self.untried = list(game.possible_moves())
        self.visits = 0; self.wins = 0
    def fully_expanded(self):
        return len(self.untried) == 0
    def ucb1(self, c=1.41):
        if self.visits == 0: return float('inf')
        return self.wins/self.visits + c*math.sqrt(math.log(self.parent.visits)/self.visits)


def mcts(root, n_iter):
    for _ in range(n_iter):
        # Select
        node = root
        while node.fully_expanded() and not node.game.is_terminal():
            node = max(node.children, key=lambda c: c.ucb1())
        # Expand
        if not node.game.is_terminal() and node.untried:
            m = random.choice(node.untried)
            node.untried.remove(m)
            child = Node(node.game.play(m), node, m)
            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:
                if winner == cur.parent.game.turn:
                    cur.wins += 1
                elif winner == 'draw':
                    cur.wins += 0.5
            cur = cur.parent
    return root


# === 7x7 빈 보드에서 MCTS의 첫 수 ===
print("=== 7x7 빈 보드에서 MCTS 첫 수 결정 (1000 iter) ===")
random.seed(42)
g = GoBoard()
root = Node(g)
mcts(root, 1000)

best = max(root.children, key=lambda c: c.visits)
print(f"MCTS의 첫 수: {best.move}, visits {best.visits}")
print()
print("상위 5개 자식:")
for child in sorted(root.children, key=lambda c: -c.visits)[:5]:
    rate = child.wins/child.visits if child.visits else 0
    print(f"  {child.move} visits={child.visits} 승률={rate:.1%}")
print()
print(f"방문된 자식 수 (전체 49 중): {len(root.children)}")

출력

기대 출력:

=== 7x7 빈 보드에서 MCTS 첫 수 결정 (1000 iter) ===
MCTS의 첫 수: (5, 5), visits 21

상위 5개 자식:
  (5, 5) visits=21 승률=50.0%
  (5, 3) visits=21 승률=50.0%
  (0, 3) visits=21 승률=50.0%
  (4, 2) visits=21 승률=50.0%
  (5, 4) visits=21 승률=50.0%

방문된 자식 수 (전체 49 중): 49

← 이전 7x7 바둑에 MCTS — Ch 6 응징 다음 → Iteration 수와 결과 품질