바둑은 왜 어려운가?
AlphaGo가 등장하기 전, 바둑은 인공지능의 "마지막 보루"로 여겨졌습니다. 수십 년간 연구자들이 다양한 방법을 시도했지만 컴퓨터가 프로 기사 수준에 도달하게 할 수 없었습니다.
이것은 연구자들의 노력이 부족해서가 아니라, 바둑이 본질적으로 극도로 어려운 계산 문제이기 때문입니다.
본 문서에서는 바둑이 정확히 어디가 어려운지, 왜 "AI의 성배"라고 불리는지 심층적으로 탐구합니다.
상태 공간의 폭발: 10^170의 의미
상태 공간이란?
어떤 보드 게임에서든 상태 공간(State Space)은 가능한 모든 바둑판 국면의 총 수를 의미합니다. 이 숫자가 무차별 대입 탐색의 실현 가능성을 결정합니다.
바둑의 경우, 이 숫자는:
바둑 상태 공간 ≈ 10^170
이것이 어떤 개념일까요? 몇 가지 비교를 해보겠습니다.
우주 원자 수와의 비교
물리학자들의 추정에 따르면, 관측 가능한 우주의 총 원자 수는 약:
우주 원자 수 ≈ 10^80
이것은 다음을 의미합니다:
바둑의 가능한 국면 수는 우주 원자 수의 10^90배입니다.
만약 우주의 모든 원자를 슈퍼컴퓨터로 쓰고, 각 컴퓨터가 초당 10억 개의 국면을 처리할 수 있다면, 빅뱅부터 지금까지(약 138억 년) 해도 모든 국면을 열거하는 것은 불가능합니다.
숫자의 직관적 이해
| 숫자 | 의미 |
|---|---|
| 10^9 | 10억, 인류 총인구 수준 |
| 10^12 | 1조, 전 세계 개미 수 |
| 10^23 | 1몰의 분자 수 |
| 10^80 | 우주의 원자 수 |
| 10^120 | 체스의 상태 공간 |
| 10^170 | 바둑의 상태 공간 |
왜 바둑의 상태 공간은 이렇게 큰가?
바둑 상태 공간이 거대한 이유는 몇 가지가 있습니다:
1. 바둑판 크기
바둑은 19×19 바둑판을 사용하며, 총 361개의 교차점이 있습니다. 비교하자면:
- 체스: 8×8 = 64칸
- 장기: 9×10 = 90개의 교차점
- 오목: 15×15 = 225개의 교차점
2. 각 자리의 세 가지 상태
각 교차점은 다음 중 하나일 수 있습니다:
- 비어있음 (돌 없음)
- 흑돌
- 백돌
대략적으로 추정하면, 가능한 조합 수는 3^361 ≈ 10^172입니다. 바둑 규칙(패, 활로 제한 등)을 고려하면 실제 합법적인 국면은 약 10^170입니다.
3. 돌은 이동하지 않음
체스와 달리, 바둑의 돌은 일단 놓이면 이동하지 않습니다(잡히지 않는 한). 이것은 각 수가 기존 돌의 이동이 아닌 새 돌의 추가라는 것을 의미하며, 가능한 경로가 더 많아집니다.
코드 예시: 상태 공간 추정
import math
# 바둑판 크기
BOARD_SIZE = 19
TOTAL_POINTS = BOARD_SIZE ** 2 # 361
# 각 자리 세 가지 상태 (비어있음, 흑, 백)
# 대략적 상한
upper_bound = 3 ** TOTAL_POINTS
print(f"대략적 상한: 3^{TOTAL_POINTS} ≈ 10^{math.log10(upper_bound):.0f}")
# 출력: 대략적 상한: 3^361 ≈ 10^172
# 규칙 제한을 고려한 실제 추정
# Tromp-Taylor의 정확한 계산은 약 2.08 × 10^170
actual_estimate = 2.08e170
print(f"실제 추정: {actual_estimate:.2e}")
# 우주 원자 수와 비교
universe_atoms = 1e80
ratio = actual_estimate / universe_atoms
print(f"바둑 국면 수 / 우주 원자 수 = 10^{math.log10(ratio):.0f}")
# 출력: 바둑 국면 수 / 우주 원자 수 = 10^90
분기 인수의 저주: 평균 250가지 선택
분기 인수란?
분기 인수(Branching Factor)는 게임의 임의의 한 수에서 평균적으로 몇 가지 합법적인 착수가 있는지를 나타냅니다. 이 숫자가 탐색 트리의 너비를 결정합니다.
| 게임 | 평균 분기 인수 |
|---|---|
| 틱택토 | ~4 |
| 체스 | ~35 |
| 장기 | ~38 |
| 오셀로 | ~10 |
| 바둑 | ~250 |
탐색 트리의 폭발적 성장
트리 탐색 알고리즘으로 N수 앞을 본다고 가정합시다. 고려해야 할 국면 수는 약:
여기서 b는 분기 인수입니다.
체스와 바둑을 비교해 보겠습니다:
| N수 앞 | 체스 (b=35) | 바둑 (b=250) | 차이 |
|---|---|---|---|
| 1수 | 35 | 250 | 7배 |
| 2수 | 1,225 | 62,500 | 51배 |
| 4수 | 150만 | 39억 | 2,600배 |
| 6수 | 18억 | 2.4×10^14 | 1.3억 배 |
| 10수 | 2.8×10^15 | 9.5×10^23 | 3.4억 배 |
10수 앞을 보면, 바둑이 고려해야 할 국면은 체스의 3억 배입니다.
왜 딥 블루의 방법이 바둑에서 실패했나
1997년 카스파로프를 이긴 딥 블루가 사용한 핵심 기술은:
- 알파-베타 가지치기: 탐색 노드 감소
- 하드웨어 가속: 초당 2억 개 국면 평가
- 수작업 평가 함수: 전문가가 설계한 국면 평가
하지만 같은 방법을 사용해도:
- 체스: 12-14수 앞을 보려면 약 10^18개 노드 평가 필요
- 바둑: 12수 앞을 보려면 약 10^29개 노드 평가 필요
차이는 100경 배입니다. 어떤 하드웨어도 이 격차를 메울 수 없습니다.
포석에서의 선택은 더욱 천문학적
바둑 포석 단계에서 분기 인수는 더 높습니다:
- 1수: 361가지 선택
- 2수: 360가지 선택
- 3수: 359가지 선택
- ...
처음 10수만 봐도:
이것이 "포석 정석"이 그토록 중요한 이유입니다—인간 기사는 많은 포석 변화를 암기해야 하는데, 실시간으로 계산할 수 없기 때문입니다.
평가의 어려움: 단순한 기물 가치가 없음
체스의 기물 우위
체스에서 국면 평가는 비교적 직관적입니다:
| 기물 | 가치 (전통적) |
|---|---|
| 폰 | 1 |
| 나이트 | 3 |
| 비숍 | 3 |
| 룩 | 5 |
| 퀸 | 9 |
실제 평가는 더 복잡하지만(위치, 구조 등), "기물 세기"는 좋은 출발점입니다. 상대의 퀸을 잡으면 거의 확실히 좋은 일입니다.
바둑: 모든 돌이 평등함
바둑에서는 모든 돌의 내재적 가치가 완전히 같습니다—그저 돌일 뿐입니다.
돌의 가치는 완전히 다음에 의존합니다:
- 바둑판 위의 위치
- 다른 돌들과의 관계
- 전체 국면에 대한 영향
이것이 평가를 극도로 어렵게 만듭니다.
두터움과 외세의 추상성
바둑에는 많은 추상적 개념이 있습니다:
두터움(Thickness)
"두터움"은 돌 무리가 견고하고, 안정적이며, 영향력이 있다는 것을 의미합니다. 하지만 "두터움"은 정량화하기 어렵습니다:
- 두터운 모양이 몇 집의 가치가 있을까?
- 언제 두터움을 활용해 공격해야 할까?
- 언제 두터움이 "우형"(비효율적인 모양)이 될까?
최고 기사들은 "이 돌 무리가 두텁고, 대략 15집 정도의 가치가 있을 것 같다"라고 말할 수 있습니다. 하지만 이것은 수십 년 경험에 기반한 직관이지 정확한 계산이 아닙니다.
외세(Influence)
바둑의 외세는 돌이 주변 공간에 대해 가지는 잠재적 통제력을 의미합니다. 이 통제력은 "허"합니다—실리로 전환될 수도, 공방에서 역할을 할 수도, 결국 아무것도 아닐 수도 있습니다.
"잠재적" 가치를 어떻게 평가할까요? 이것은 컴퓨터에게 극히 어렵습니다.
맛(Aji)
"맛"은 바둑에서 가장 추상적인 개념 중 하나입니다. 바둑판 어딘가의 잠재적 가능성을 의미합니다.
"죽은 돌"도 "활용 가치"가 있을 수 있습니다—그 자체로는 살릴 수 없지만 미래 전투에서 간섭을 일으킬 수 있습니다. 이런 "잠재적 가능성"은 숫자로 표현하기가 거의 불가능합니다.
왜 수작업 평가 함수가 실패했나
딥 블루 이전의 컴퓨터 체스는 인간 전문가가 설계한 평가 함수를 사용했습니다:
평가값 = 기물 점수 + 위치 점수 + 킹 안전성 + 폰 구조 + ...
이 항목들은 정량화하고 가중치를 조정할 수 있어 효과가 좋았습니다.
하지만 바둑은?
연구자들은 다양한 특징을 시도했습니다:
- 통제하는 교차점 수
- 돌의 "자유도" (활로 수)
- 연결 강도
- 눈 모양의 완전성
- ...
하지만 이 특징들의 조합으로는 아마추어 고단의 수준에도 도달하지 못했습니다.
핵심 문제: 바둑의 국면 평가는 고도로 비선형적이고 전역적인 문제입니다.
돌 하나의 가치는 전체 바둑판 상태에 의존하며, 국부 특징의 단순한 합이 아닙니다.
장기 계획의 필요성: 한 대국 150수
바둑의 세 단계
표준 바둑 대국은 보통 세 단계를 거칩니다:
| 단계 | 수 (약) | 특성 |
|---|---|---|
| 포석 | 1-50 | 땅 차지하기, 프레임 구축, 전체 방향 설정 |
| 중반 | 50-200 | 전투, 공방, 국부와 전체의 균형 |
| 끝내기 | 200-300 | 마무리, 계산, 정확성 |
평균 한 대국 약 250-300수이며, 처음 150수가 승패의 대국을 결정합니다.
포석: 30수 이후의 계획
포석 단계의 모든 수는 수십 수 심지어 백 수 이후를 준비하는 것입니다.
예를 들어, "삼연성" 포석:
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . ● . . . . . ● . . . . . ● . . .
. . . . . . . . . . . . . . . . . . .
...
이 세 개의 흑돌은 "외세형" 포석을 구성하며, 그 의도는:
- 집짓기를 서두르지 않음
- 백이 들어오면 공격함
- 공격을 통해 실리나 외세를 얻음
- 최종적으로 끝내기에서 우세 실현
이 "계획"은 50-100수 이후의 국면을 내다봐야 합니다. 어떤 탐색 알고리즘도 그렇게 멀리 볼 수 없습니다.
중반: 국부와 전체의 균형
중반 전투는 바둑에서 가장 복잡한 부분입니다. 기사는 매 수마다 고려해야 합니다:
- 국부 계산: 이 전투에서 누가 이길까?
- 전체 판단: 여기서 싸울 가치가 있을까?
- 순서 선택: 어디를 먼저 두는 게 가장 효율적일까?
- 포기 결정: 언제 돌을 버리고 전환해야 할까?
전형적인 중반 결정:
"여기서 끊으면 상대가 반격할 것이고, 난 한 덩어리를 살려야 하고, 이것 때문에 상대가 선수로 대장을 차지하게 될 것이고...결국 5집 정도 손해다. 하지만 먼저 보강한 후 끊으면, 선수는 잃지만..."
이런 다층적, 다차원적 사고는 국부와 전체, 단기와 장기를 동시에 처리해야 합니다.
끝내기: 정확한 계산과 역전
끝내기 단계는 단순해 보입니다—그냥 마무리. 하지만 실제로:
- 매 수의 "집수 가치"를 정확히 계산해야 함
- 선후수의 차이가 승패를 결정할 수 있음
- "패싸움"이 국면을 완전히 바꿀 수 있음
프로 기사들의 끝내기 계산 정확도는 0.5집에 달할 수 있으며, 한 대국의 승패는 1집 차이일 수 있습니다.
왜 멀리 못 보는 것이 치명적인가
간단한 계산을 해봅시다:
- 한 대국 평균 250수
- 결과를 완벽히 예측하려면 이론적으로 250수를 모두 봐야 함
- 분기 인수가 100으로 줄어도(끝내기 단계), 탐색 공간은 100^250 ≈ 10^500
이것은 어떤 컴퓨터의 능력도 훨씬 초과합니다.
이것이 바둑 AI가 "계산"만에 의존할 수 없고 국면을 "평가"하는 법을 배워야 하는 이유입니다.
직관의 중요성: "이 수는 느낌이 맞다"
인간 기사의 사고 방식
최고 바둑 기사들이 자신의 사고 과정을 설명할 때 자주 사용하는 표현들:
"이 수가 느낌이 맞다."
"이 모양이 매우 편하다."
"그쪽 돌이 맛이 안 좋다."
"여기에 말로 표현할 수 없는 위험감이 있다."
이것은 시적인 표현이 아니라 실제 인지 과정입니다. 인간 기사는 패턴 인식과 직관적 판단을 사용하여 바둑의 복잡성을 처리합니다.
패턴 인식: 1초 만에 핵심 파악
실험에 따르면, 프로 기사가 바둑판을 한 번 보면(1초도 안 됨):
- 핵심 영역 식별
- 가능한 "좋은 수" 발견
- 국면의 대략적인 형세 감지
이 능력은 수만 대국의 경험 축적에서 나와 "기감"을 형성합니다.
AlphaGo 이전의 컴퓨터 바둑에서 가장 큰 어려움은 이 직관을 복제할 수 없다는 것이었습니다.
직관의 수학적 설명
머신러닝 관점에서 인간의 바둑 직관은 다음과 같이 이해할 수 있습니다:
잘 훈련된 뇌는 바둑판 국면에 따라 즉시 각 위치가 "좋은 수"일 확률 분포를 출력할 수 있습니다.
이것이 바로 Policy Network가 학습해야 하는 것—그리고 이것은 딥 뉴럴 네트워크가 필요합니다.
왜 "AI의 성배"라 불리는가
보드 게임의 이정표
인공지능 역사에서 보드 게임은 항상 중요한 이정표였습니다:
| 연도 | 사건 | 의미 |
|---|---|---|
| 1951 | 최초의 체커 프로그램 | 최초의 게임 AI |
| 1997 | 딥 블루가 카스파로프를 이김 | 무차별 대입 탐색의 승리 |
| 2007 | 체커가 완전히 해결됨 | 완전 정보 게임의 한계 |
| 2016 | AlphaGo가 이세돌을 이김 | 딥러닝의 승리 |
왜 바둑이 특별한가
바둑이 "AI의 성배"라 불리는 이유는 모든 어려운 특성을 결합하기 때문입니다:
| 특성 | 바둑 | 체스 |
|---|---|---|
| 상태 공간 | 10^170 | 10^120 |
| 분기 인수 | ~250 | ~35 |
| 평균 수 | ~250 | ~40 |
| 평가 난이도 | 극히 높음 | 중간 |
| 직관 의존도 | 매우 높음 | 높음 |
AI가 바둑을 해결할 수 있다면, 다음을 의미합니다:
- 극대한 탐색 공간을 처리할 수 있음
- 추상적 평가를 배울 수 있음
- 장기 계획을 할 수 있음
- "직관"을 형성할 수 있음
이러한 능력은 "바둑 두기"의 범위를 훨씬 넘어서며, 범용 지능의 핵심 특징입니다.
학계의 예측
2016년 이전, "AI가 언제 인간 바둑 챔피언을 이길 수 있을까"에 대한 학계의 예측은 대체로:
"적어도 10-20년은 더 걸릴 것이다."
— 대부분의 AI 연구자 (2015년)
이 예측은 당시 기술 진보 속도에 기반한 것이었습니다. 바둑 프로그램은 매년 약 1-2단 진보했고, 인간 프로 9단과는 18단의 실력 차이가 있었습니다. 이 속도라면 정말 10-20년이 필요했습니다.
아무도 딥러닝이 도약적 돌파를 가져올 것을 예측하지 못했습니다.
애니메이션 대응
본 문서에서 다루는 핵심 개념과 애니메이션 번호:
| 번호 | 개념 | 물리/수학 대응 |
|---|---|---|
| 🎬 B2 | 상태 공간 폭발 | 조합수학, 지수 성장 |
| 🎬 B8 | 조합 폭발 | 팩토리얼 성장, 탐색 트리 |
| 🎬 A3 | 분기 인수 비교 | 그래프 이론, 트리 구조 |
| 🎬 B5 | 평가 함수 딜레마 | 비선형 매핑 |
핵심 요점 정리
바둑이 "AI의 성배"라 불리는 이유는 세 가지 주요 난제를 결합하기 때문입니다:
1. 공간의 저주
- 10^170 가지 가능한 국면, 우주 원자 수를 훨씬 초과
- 분기 인수 ~250, 탐색 트리의 폭발적 성장
- 무차별 대입 탐색은 물리적으로 불가능
2. 평가의 어려움
- 모든 돌의 가치가 동등, 기물 우위 없음
- "두터움" "외세" "맛" 등 추상적 개념은 정량화하기 어려움
- 국면 평가는 고도로 비선형적이고 전역적인 문제
3. 시간의 도전
- 한 대국 ~250수, 장기 계획 필요
- 포석 결정이 50-100수 이후의 국면에 영향
- 국부 전투와 전체 균형을 동시에 고려해야 함
바로 이러한 난제들의 조합이 전통적 AI 방법(무차별 대입 탐색 + 수작업 평가)을 바둑에서 완전히 실패하게 만들었습니다.
AlphaGo의 돌파는 바로 딥 뉴럴 네트워크로 평가 문제를, 몬테카를로 트리 탐색으로 계획 문제를, 강화학습으로 인간을 초월하는 문제를 해결했기 때문입니다.
더 읽을거리
- 다음 글: 전통적 방법의 한계 — Minimax에서 MCTS까지, 왜 모두 부족한가
- 기술적 세부사항: Policy Network 상세 설명 — AlphaGo가 "직관"을 배우는 방법
- 총괄로 돌아가기: AlphaGo 완전 분석 — 시리즈 문서 안내
참고 자료
- Tromp, J. (2016). "Number of legal Go positions." — 바둑 상태 공간의 정확한 계산
- Allis, L.V. (1994). "Searching for Solutions in Games and Artificial Intelligence." PhD thesis, University of Limburg. — 게임 복잡도의 이론적 분석
- Müller, M. (2002). "Computer Go." Artificial Intelligence, 134(1-2), 145-179. — 컴퓨터 바둑의 초기 연구 종합
- Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489. — AlphaGo 원본 논문