Iteration 수와 결과 품질

Iteration이 늘어남에 따라 결과:

iter	시간	최선 수	1위 visits	승률
100	0.04s	(5,5)	3	50%
500	0.24s	(5,5)	11	50%
2000	0.89s	(5,5)	41	50%
5000	2.34s	(5,5)	103	50%

⚠️ 승률이 항상 50% — 평가 함수의 한계

우리 코드 평가 = "돌 수가 많은 쪽 승, 동률은 draw". 7x7 무작위 게임에서 흑/백 돌 수는 거의 항상 동률에 가까워 → 대부분 draw → 모든 첫 수의 승률이 50% 균등.

이건 우리 코드의 한계지, MCTS 알고리즘의 한계가 아님. 실제 영역 평가를 쓰면 신호가 명확히 잡힘 (50% 균등이 아닌 65~75% 등).

📊 만약 진짜 영역 평가를 쓰면

알파고나 GnuGo 같은 진짜 엔진은 게임 끝의 영역을 정확히 계산. 그러면:

중앙 화점 (3,3): 승률 75% (영역 형성 좋음)
코너 (0,0): 승률 30% (구석에 갇혀 영역 못 키움)
변 가운데 (3,0): 승률 55% (보통)

이런 차이로 UCB1이 좋은 자리에 자동 집중. 같은 알고리즘, 다른 평가 함수, 완전히 다른 결과.

💡 핵심 교훈

"평가 함수가 약하면 어떤 알고리즘도 한계." minimax든 MCTS든 입력이 정확해야.

이게 PART 4 신경망의 출발점 — 학습된 정확한 평가 함수. 우리가 만든 단순 평가를 신경망으로 대체하면 같은 MCTS가 진짜 강해짐.

다음 페이지에서 minimax와 MCTS를 직접 대결시켜본다.

PYTHON

# Iteration을 늘리면 어떻게 변하는가?
# 100 → 500 → 2000 → 5000 비교.

import math, random, time

class GoBoard:
    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
        return GoBoard(nb, self.WHITE if self.turn == self.BLACK else self.BLACK, self.move_count + 1)
    def is_terminal(self):
        return self.move_count >= self.MAX_MOVES or not self.possible_moves()
    def winner(self):
        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'

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):
        node = root
        while node.fully_expanded() and not node.game.is_terminal():
            node = max(node.children, key=lambda c: c.ucb1())
        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
        g = node.game
        while g.winner() is None:
            g = g.play(random.choice(g.possible_moves()))
        winner = g.winner()
        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


# === Iteration 수 비교 ===
print(f"{'iter':>6} {'최선 수':>10} {'1위 visits':>13} {'1위 승률':>10}")
print("-" * 45)

for n_iter in [100, 500, 2000, 5000]:
    random.seed(42)
    g = GoBoard()
    root = Node(g)
    mcts(root, n_iter)

    best = max(root.children, key=lambda c: c.visits)
    rate = best.wins/best.visits if best.visits else 0
    print(f"{n_iter:>6} {str(best.move):>10} {best.visits:>13} {rate:>9.1%}")

print()
print("=== 관찰 ===")
print("• 5000 iter에서도 1위 visits가 약 100~200 정도")
print("• 7x7은 분기가 49로 커서 한 자식에 집중되는 비율이 낮음")
print("• 19x19에서는 더 많은 iter 필요")

출력

기대 출력:

  iter       최선 수     1위 visits      1위 승률
---------------------------------------------
   100     (5, 5)             3     50.0%
   500     (5, 5)            11     50.0%
  2000     (5, 5)            41     50.0%
  5000     (5, 5)           103     50.0%

=== 관찰 ===
• 5000 iter에서도 1위 visits가 약 100~200 정도
• 7x7은 분기가 49로 커서 한 자식에 집중되는 비율이 낮음
• 19x19에서는 더 많은 iter 필요

← 이전 코드: 7x7 바둑 MCTS 다음 → 코드: MCTS vs Minimax 정면 대결