전통적 방법의 한계

딥러닝이 등장하기 전, 연구자들은 수십 년간 '전통적' 방법으로 바둑 문제를 해결하려고 시도했습니다. Minimax 알고리즘부터 몬테카를로 트리 검색(MCTS)까지, 매번의 발전은 컴퓨터 바둑을 조금씩 더 강하게 만들었지만, 인간 프로 기사 수준에는 결코 도달하지 못했습니다.

이 글에서는 이러한 방법들의 원리, 장단점, 그리고 왜 바둑에서 병목 현상에 부딪혔는지 심층적으로 살펴보겠습니다.

Minimax 알고리즘: 게임 이론의 기초

기본 원리

Minimax 알고리즘은 게임 이론의 핵심 개념으로, 1928년 John von Neumann이 제안했습니다. 기본 아이디어는 다음과 같습니다:

제로섬 게임에서, 나는 상대의 '최선의 대응' 후에도 여전히 가장 좋은 선택지를 골라야 합니다.

다시 말해:

**나(Max)**는 점수를 최대화하려 합니다
**상대(Min)**는 내 점수를 최소화하려 합니다
나는 상대가 항상 최선의 대응을 한다고 가정해야 합니다

수학적 형식화

상태 s의 가치를 V(s)라 하고, 재귀적으로 다음과 같이 정의합니다:

V(s) = eval(s)                        // s가 종료 상태인 경우
V(s) = max{ V(result(s, a)) | a ∈ A(s) }  // Max의 차례인 경우
V(s) = min{ V(result(s, a)) | a ∈ A(s) }  // Min의 차례인 경우

여기서:

A(s): 상태 s에서의 모든 합법적 행동
result(s, a): 상태 s에서 행동 a를 실행한 후의 결과
eval(s): 종료 상태에 대한 평가

검색 트리 도식

이 예시에서:

Min 층은 나에게 가장 불리한 값(최소값)을 선택합니다
Max 층은 나에게 가장 유리한 값(최대값)을 선택합니다
최종적으로, Max는 중간 가지(+5)를 선택해야 합니다

코드 구현

def minimax(state, depth, is_max_turn):
    """
    Minimax 알고리즘의 기본 구현

    Args:
        state: 현재 상태
        depth: 검색 깊이
        is_max_turn: Max의 차례인지 여부

    Returns:
        (최적 가치, 최적 행동)
    """
    # 종료 조건: 깊이 제한 도달 또는 게임 종료
    if depth == 0 or is_terminal(state):
        return evaluate(state), None

    legal_moves = get_legal_moves(state)
    best_move = None

    if is_max_turn:
        best_value = float('-inf')
        for move in legal_moves:
            next_state = apply_move(state, move)
            value, _ = minimax(next_state, depth - 1, False)
            if value > best_value:
                best_value = value
                best_move = move
    else:
        best_value = float('inf')
        for move in legal_moves:
            next_state = apply_move(state, move)
            value, _ = minimax(next_state, depth - 1, True)
            if value < best_value:
                best_value = value
                best_move = move

    return best_value, best_move

Minimax가 바둑에서 직면한 문제

1. 검색 공간 폭발

이전 글에서 설명했듯이, 바둑의 분기 계수는 약 250입니다. N 수 앞을 보려면:

노드 수 ≈ 250^N

깊이	노드 수	1초에 100만 노드 평가 기준
2	62,500	0.06초
4	39억	65분
6	2.4×10^14	7,600년
8	1.5×10^19	4.8억 년

6수 앞을 보는 데만 7,600년이 걸리니, 전체 대국을 보는 것은 말할 것도 없습니다.

2. 평가 함수의 어려움

4수 앞만 본다 해도, 비종료 상태의 가치를 판단할 정확한 평가 함수가 필요합니다. 하지만 이전 글에서 설명했듯이, 바둑의 국면 평가는 극도로 어렵습니다.

결론: 순수 Minimax는 바둑에서 전혀 실행 불가능합니다.

Alpha-Beta 가지치기: 불필요한 검색 줄이기

핵심 통찰

Alpha-Beta 가지치기의 핵심 통찰은: 모든 가지를 검색할 필요가 없다는 것입니다.

어떤 가지가 "확실히 나쁘다"는 것을 이미 알고 있다면, 바로 건너뛸 수 있습니다.

가지치기 원리

이 예시에서:

A는 이미 값이 +5인 선택지를 가지고 있습니다
B의 첫 번째 자식 가지가 +3이므로, B의 최종 값은 ≤ +3입니다
B ≤ +3 < +5이므로, A는 B를 선택하지 않습니다
B2는 평가할 필요가 없습니다

이것이 Beta 가지치기입니다. 마찬가지로, Alpha 가지치기도 있습니다.

수학적 형식화

두 개의 매개변수를 도입합니다:

α(alpha): Max가 현재 보장할 수 있는 최소값(하한)
β(beta): Min이 현재 보장할 수 있는 최대값(상한)

가지치기 조건:

Max 노드에서, value ≥ β이면 가지치기(Beta 가지치기)
Min 노드에서, value ≤ α이면 가지치기(Alpha 가지치기)

코드 구현

def alpha_beta(state, depth, alpha, beta, is_max_turn):
    """
    Alpha-Beta 가지치기 알고리즘

    Args:
        state: 현재 상태
        depth: 검색 깊이
        alpha: Max의 하한
        beta: Min의 상한
        is_max_turn: Max의 차례인지 여부

    Returns:
        (가치, 최적 행동)
    """
    if depth == 0 or is_terminal(state):
        return evaluate(state), None

    legal_moves = get_legal_moves(state)
    best_move = None

    if is_max_turn:
        value = float('-inf')
        for move in legal_moves:
            next_state = apply_move(state, move)
            child_value, _ = alpha_beta(next_state, depth - 1,
                                        alpha, beta, False)
            if child_value > value:
                value = child_value
                best_move = move
            alpha = max(alpha, value)
            if value >= beta:
                break  # Beta 가지치기
        return value, best_move
    else:
        value = float('inf')
        for move in legal_moves:
            next_state = apply_move(state, move)
            child_value, _ = alpha_beta(next_state, depth - 1,
                                        alpha, beta, True)
            if child_value < value:
                value = child_value
                best_move = move
            beta = min(beta, value)
            if value <= alpha:
                break  # Alpha 가지치기
        return value, best_move

# 호출 방식
value, best_move = alpha_beta(state, depth=4,
                               alpha=float('-inf'),
                               beta=float('inf'),
                               is_max_turn=True)

가지치기 효율

이상적인 경우(완벽한 수순 정렬)에서, Alpha-Beta는 유효 분기 계수를 b에서 √b로 줄일 수 있습니다:

유효 분기 계수 = b^0.5

이는 다음을 의미합니다:

체스: 35에서 ~6으로 감소
바둑: 250에서 ~16으로 감소

깊이	원래 노드 수	Alpha-Beta(이상적)	가속비
4	39억	6.5만	60,000×
6	2.4×10^14	1600만	1.5×10^7 ×
8	1.5×10^19	42억	3.6×10^9 ×

여전히 불충분한 이유

Alpha-Beta 가지치기가 있어도, 바둑은 여전히 처리하기 어렵습니다:

1. 이상적인 가지치기에는 완벽한 정렬이 필요

이상적인 가지치기 효율을 달성하려면, '가장 좋은' 가지를 먼저 검색해야 합니다. 하지만 어떤 가지가 가장 좋은지 알려면 검색이 필요합니다... 이것은 닭이 먼저냐 달걀이 먼저냐의 문제입니다.

실제로, 바둑의 가지치기 효율은 이상치보다 훨씬 낮으며, 유효 분기 계수가 여전히 50-100일 수 있습니다.

2. 깊이가 여전히 불충분

유효 분기 계수가 50으로 낮아져도, 10수 앞을 보려면 여전히 50^10 ≈ 10^17 개의 노드가 필요합니다. 이는 컴퓨터에게 여전히 너무 많습니다.

3. 평가 함수의 병목

Alpha-Beta는 '검색 효율' 문제만 해결하고, '평가 정확도' 문제는 해결하지 못합니다. 형편없는 평가 함수에 아무리 빠른 검색을 결합해도, 결과는 여전히 형편없습니다.

결론: Alpha-Beta는 체스 AI를 크게 향상시켰지만, 바둑에는 도움이 제한적이었습니다.

순수 몬테카를로 방법: 무작위의 힘

평가 함수 포기

1990년대, 연구자들은 급진적인 아이디어를 시도하기 시작했습니다: 평가 함수를 사용하지 않기.

대신 무작위 시뮬레이션(Random Playout)을 사용합니다:

현재 상태에서 시작
양쪽 모두 무작위로 두어 게임이 끝날 때까지 진행
결과 기록(승/패)
N번 반복하고 승률 통계

통계적 추정 원리

대수의 법칙에 따르면, 시뮬레이션 횟수 N이 충분히 크면:

V̂(s) = 시뮬레이션 승리 횟수 / N ≈ V(s)

이 추정의 표준오차는:

SE = √(V(s)(1-V(s))/N) ≈ 1/(2√N)

시뮬레이션 횟수	표준오차
100	5%
1,000	1.6%
10,000	0.5%
100,000	0.16%

코드 구현

import random

def random_playout(state, player):
    """
    현재 상태에서 시작하여, 양쪽 모두 무작위로 두어 종료까지 진행

    Returns:
        player가 이기면 1, 지면 0
    """
    current = state.copy()
    current_player = player

    while not is_terminal(current):
        legal_moves = get_legal_moves(current)
        if not legal_moves:
            current_player = opponent(current_player)
            continue

        # 무작위로 한 수 선택
        move = random.choice(legal_moves)
        current = apply_move(current, move)
        current_player = opponent(current_player)

    return 1 if get_winner(current) == player else 0


def monte_carlo_move_selection(state, player, num_simulations=10000):
    """
    몬테카를로 방법을 사용하여 최적의 착점 선택
    """
    legal_moves = get_legal_moves(state)

    if len(legal_moves) == 0:
        return None

    # 각 합법적 착점에 시뮬레이션 횟수 할당
    sims_per_move = num_simulations // len(legal_moves)

    best_move = None
    best_win_rate = -1

    for move in legal_moves:
        next_state = apply_move(state, move)

        wins = 0
        for _ in range(sims_per_move):
            wins += random_playout(next_state, opponent(player))

        # 상대 승률이 낮음 = 내 승률이 높음
        my_win_rate = 1 - (wins / sims_per_move)

        if my_win_rate > best_win_rate:
            best_win_rate = my_win_rate
            best_move = move

    return best_move, best_win_rate

장점과 한계

장점

평가 함수 불필요: 완전히 시뮬레이션에 의존
모든 게임에 적용 가능: 규칙만 알면 됨
확률 추정 제공: '얼마나 확실한지' 알 수 있음

한계

무작위성이 너무 강함: 무작위 착점과 프로 착점의 격차가 너무 큼
대량의 시뮬레이션 필요: 매 수마다 수만 번의 시뮬레이션 필요
전술적 사각지대: 핵심 전술이 무작위로 놓칠 수 있음

순수 몬테카를로의 바둑 성능

순수 몬테카를로 방법을 사용하는 바둑 프로그램은 대략 다음 수준에 도달할 수 있습니다:

아마추어 5-10급 수준

이는 이전의 순수 Minimax + 평가 함수 프로그램보다 나았지만, 프로 수준과는 여전히 큰 격차가 있었습니다.

MCTS의 돌파구 (2006)

UCT 알고리즘의 탄생

2006년, Rémi Coulom은 트리 검색과 몬테카를로 시뮬레이션의 장점을 결합한 MCTS(Monte Carlo Tree Search) 알고리즘을 제안했습니다. 같은 해, Levente Kocsis와 Csaba Szepesvári는 MCTS에 이론적 기반을 제공하는 UCT(Upper Confidence Bounds for Trees) 알고리즘을 제안했습니다.

이것은 컴퓨터 바둑의 이정표적 돌파구였습니다.

UCB1 공식

MCTS의 핵심은 UCB1(Upper Confidence Bound) 공식입니다:

UCB1(s, a) = X̄(s,a) + C × √(ln(Ns) / n(s,a))

여기서:

X̄(s,a): 상태 s에서 행동 a의 평균 가치(승률)
Ns: 상태 s가 방문된 총 횟수
n(s,a): 상태 s에서 행동 a가 취해진 횟수
C: 탐색 상수(보통 C = √2)

이 공식은 활용(알려진 좋은 것 선택)과 탐색(미지의 것 시도)을 교묘하게 균형 잡습니다.

MCTS의 네 단계

載入中...

MCTS의 각 반복은 네 단계로 구성됩니다:

1. Selection(선택)

루트 노드에서 시작하여, UCB1 공식을 사용해 자식 노드를 선택하고, 리프 노드에 도달할 때까지 진행합니다.

def select(node):
    """UCB1을 사용하여 최적의 자식 노드 선택"""
    while node.is_fully_expanded():
        node = max(node.children,
                   key=lambda c: ucb1(c, node.visits))
    return node

def ucb1(child, parent_visits, C=1.414):
    """UCB1 공식"""
    if child.visits == 0:
        return float('inf')  # 미방문 노드 우선

    exploitation = child.wins / child.visits
    exploration = C * math.sqrt(math.log(parent_visits) / child.visits)

    return exploitation + exploration

2. Expansion(확장)

리프 노드에 하나 이상의 자식 노드를 추가합니다.

def expand(node, state):
    """노드 확장"""
    legal_moves = get_legal_moves(state)
    untried = [m for m in legal_moves if m not in node.tried_moves]

    if untried:
        move = random.choice(untried)
        new_state = apply_move(state, move)
        child = Node(move=move, parent=node)
        node.children.append(child)
        node.tried_moves.add(move)
        return child, new_state

    return node, state

3. Simulation(시뮬레이션)

새 노드에서 시작하여, 게임이 끝날 때까지 무작위 시뮬레이션을 수행합니다.

def simulate(state, player):
    """게임이 끝날 때까지 무작위 시뮬레이션"""
    return random_playout(state, player)

4. Backpropagation(역전파)

시뮬레이션 결과를 모든 조상 노드에 역전파합니다.

def backpropagate(node, result):
    """결과를 모든 조상에게 역전파"""
    while node is not None:
        node.visits += 1
        node.wins += result
        result = 1 - result  # 시점 전환
        node = node.parent

완전한 MCTS 구현

class MCTSNode:
    def __init__(self, move=None, parent=None):
        self.move = move
        self.parent = parent
        self.children = []
        self.wins = 0
        self.visits = 0
        self.tried_moves = set()

    def is_fully_expanded(self, legal_moves):
        return len(self.tried_moves) == len(legal_moves)


def mcts(root_state, player, num_iterations=10000):
    """
    MCTS 메인 함수

    Args:
        root_state: 초기 상태
        player: 현재 플레이어
        num_iterations: 반복 횟수

    Returns:
        최적 행동
    """
    root = MCTSNode()

    for _ in range(num_iterations):
        node = root
        state = root_state.copy()
        current_player = player

        # 1. Selection
        while node.children and node.is_fully_expanded(get_legal_moves(state)):
            node = max(node.children,
                      key=lambda c: ucb1(c, node.visits))
            state = apply_move(state, node.move)
            current_player = opponent(current_player)

        # 2. Expansion
        legal_moves = get_legal_moves(state)
        if not node.is_fully_expanded(legal_moves) and not is_terminal(state):
            move = random.choice([m for m in legal_moves
                                  if m not in node.tried_moves])
            state = apply_move(state, move)
            child = MCTSNode(move=move, parent=node)
            node.children.append(child)
            node.tried_moves.add(move)
            node = child
            current_player = opponent(current_player)

        # 3. Simulation
        result = simulate(state, current_player)

        # 4. Backpropagation
        backpropagate(node, result)

    # 방문 횟수가 가장 많은 자식 노드 선택
    return max(root.children, key=lambda c: c.visits).move

MCTS가 왜 효과적인가?

MCTS의 성공에는 몇 가지 핵심 요인이 있습니다:

1. 점진적 집중

MCTS는 모든 가지를 균등하게 검색하지 않고, 더 유망해 보이는 가지에 더 많은 자원을 투입합니다. 이를 통해 명백히 나쁜 수를 '무시'할 수 있습니다.

2. 임의 시간 알고리즘

MCTS는 언제든지 중단하고 현재 최적의 답을 제공할 수 있습니다. 시간이 많을수록 답이 더 좋아집니다.

3. 평가 함수 불필요

MCTS는 시뮬레이션을 통해 가치를 추정하며, 수작업으로 평가 함수를 설계할 필요가 없습니다.

2006-2015: MCTS 시대

MCTS의 등장으로 컴퓨터 바둑은 새로운 시대에 진입했습니다:

프로그램	연도	특징	실력
Crazy Stone	2006	최초의 MCTS 바둑 프로그램	아마추어 고단
MoGo	2007	최적화된 MCTS	아마추어 5단
Zen	2009	패턴 인식 추가	아마추어 6단
Crazy Stone	2013	4점 접바둑으로 프로 9단 격파	프로 초단(접바둑)

이것은 역사적인 발전이었지만, 여전히 큰 격차가 있었습니다:

가장 강력한 MCTS 프로그램도, 호선에서는 프로 기사를 이길 수 없었습니다.

평가 함수의 병목

수작업 특징의 한계

MCTS 이전에, 연구자들은 국면을 평가하기 위한 다양한 수작업 특징을 설계하려 시도했습니다:

일반적인 특징

def evaluate_position(state):
    """수작업으로 설계된 평가 함수"""
    score = 0

    # 1. 집 추정
    score += count_territory(state, BLACK) - count_territory(state, WHITE)

    # 2. 돌의 자유도(활로 수)
    score += sum(liberties(group) for group in groups(state, BLACK))
    score -= sum(liberties(group) for group in groups(state, WHITE))

    # 3. 눈의 수
    score += count_eyes(state, BLACK) * 10
    score -= count_eyes(state, WHITE) * 10

    # 4. 연결 강도
    score += connectivity_score(state, BLACK)
    score -= connectivity_score(state, WHITE)

    # ... 더 많은 특징

    return score

문제점

특징이 불완전: 인간 직관의 많은 요소를 프로그램으로 설명하기 어려움
가중치 조정 어려움: 각 특징의 상대적 중요도를 어떻게 결정할 것인가?
지역 vs 전역: 지역 계산은 쉽지만, 전역 판단은 어려움
상호작용: 특징 간의 상호작용을 모델링하기 어려움

MCTS에서의 시뮬레이션 문제

MCTS에서 평가 함수를 직접 사용하지 않더라도, 시뮬레이션의 품질은 여전히 핵심 병목입니다.

무작위 시뮬레이션의 문제

무작위 착점은 많은 '비합리적인' 국면을 생성하여, 추정이 부정확해집니다:

대마가 헛되이 죽음
따낼 수 있는데 따내지 않음
간단한 사활을 놓침

개선 시도

연구자들은 시뮬레이션에 사전 지식을 추가하려 시도했습니다:

def simulation_policy(state, legal_moves):
    """
    사전 지식이 있는 시뮬레이션 정책
    """
    # 우선 고려:
    # 1. 따냄
    # 2. 도망
    # 3. 연결
    # 4. 큰 곳 차지
    # ...

    for move in legal_moves:
        if is_capture(state, move):
            return move
        if saves_group(state, move):
            return move

    # 나머지는 무작위
    return random.choice(legal_moves)

하지만 이러한 휴리스틱 규칙은:

계산 비용 증가
편향 도입 가능
여전히 충분히 정밀하지 않음

왜 신경망이 필요한가

전통적 방법의 병목은 본질적으로 표현 학습의 문제입니다:

바둑판 픽셀(361개 점의 상태)에서 '좋은 수'의 특징을 어떻게 학습할 것인가?

이것이 바로 딥러닝의 강점입니다:

자동 특징 학습: 인공 설계가 필요 없음
비선형 매핑: 복잡한 관계를 포착 가능
종단간 학습: 입력에서 출력까지 직접

2012년 딥러닝의 ImageNet 돌파구는 연구자들이 다음을 생각하게 했습니다:

신경망이 사진을 '이해'할 수 있다면, 바둑판도 '이해'할 수 있지 않을까?

이 질문에 대한 답이 바로 AlphaGo입니다.