신경망과 트리 탐색으로 바둑 정복하기 (AlphaGo)

신경망과 트리 탐색으로 바둑 정복하기 (AlphaGo)

사람 기보로 배운 정책망, 자기 대국 강화학습으로 다듬은 정책망, 판세를 읽는 가치망을 몬테카를로 트리 탐색에 결합해, 처음으로 정식 19줄 바둑에서 프로 기사를 이긴 논문입니다. "탐색 + 학습한 직관"이라는 조합은 이후 AlphaGo Zero · AlphaZero · MuZero로 이어집니다.

들어가기 전에

이 해설은 아래 내용을 안다고 보고 씁니다. 처음이라면 먼저 읽고 오면 수식과 손계산을 훨씬 쉽게 따라올 수 있습니다.

• 딥 강화학습으로 아타리 게임하기 (DQN) — 픽셀만 보고 아타리 게임을 배운 첫 딥 강화학습 모델 — Q-네트워크와 경험 재생
• OpenAI Spinning Up: 딥 강화학습 입문 — 로그 미분 트릭으로 정책 경사를 유도하고 reward-to-go · 기준값 · 액터-크리틱까지 손계산하는 수업
• 스탠퍼드 CS231n 강의 노트(합성곱 신경망) — 합성곱 한 칸 · 출력 크기 · 파라미터 수 · 풀링 · 수용 영역을 손계산으로 익히는 CNN 수업
• 모델 기반 강화학습과 계획: Dyna-Q · MCTS(UCT · PUCT) · 월드 모델 지도 — 몬테카를로 트리 탐색의 네 단계와 UCT · PUCT 점수를 먼저 손계산합니다

한눈에 보기

• 바둑이 왜 체스보다 훨씬 어려운지(탐색의 폭과 깊이)를 숫자로 이해합니다.
• 정책망(policy network)이 탐색의 '폭'을, 가치망(value network)이 탐색의 '깊이'를 줄이는 원리를 알게 됩니다.
• 지도학습 → 강화학습 → 가치 회귀로 이어지는 3단계 학습 파이프라인을 설명할 수 있습니다.
• MCTS가 사전 확률 $P$, 방문 횟수 $N$, 행동 가치 $Q$로 수를 고르는 식을 손으로 계산할 수 있습니다.

초록 (번역)

바둑은 탐색 공간이 엄청나게 크고 판의 형세와 수를 평가하기 어려워, 오래전부터 인공지능에게 가장 어려운 고전 게임으로 여겨져 왔습니다. 이 논문은 '가치망'으로 판의 형세를 평가하고 '정책망'으로 수를 고르는 새로운 컴퓨터 바둑 방법을 소개합니다. 이 심층 신경망들은 사람 전문가 기보를 이용한 지도학습과 자기 대국을 이용한 강화학습을 새롭게 결합해 학습합니다. 앞을 내다보는 탐색을 전혀 하지 않아도, 이 신경망들은 수천 판의 무작위 자기 대국을 시뮬레이션하는 최고 수준의 몬테카를로 트리 탐색 프로그램과 같은 수준으로 바둑을 둡니다. 또한 몬테카를로 시뮬레이션을 가치망 · 정책망과 결합한 새로운 탐색 알고리즘도 소개합니다. 이 탐색 알고리즘을 쓴 프로그램 AlphaGo는 다른 바둑 프로그램을 상대로 99.8%의 승률을 기록했고, 유럽 바둑 챔피언인 사람 기사를 5대 0으로 이겼습니다. 컴퓨터 프로그램이 정식 크기 바둑에서 사람 프로 기사를 이긴 것은 이번이 처음이며, 이는 적어도 10년은 더 걸릴 것으로 여겨지던 일입니다.

무엇을 풀었나

완전 정보 게임은 이론상 모든 수를 끝까지 따져 보면 풀립니다. 하지만 경우의 수는 대략 $b^d$개입니다($b$: 한 수에서 둘 수 있는 곳의 수, $d$: 게임 길이). 논문이 인용한 값으로 체스는 $b \approx 35$, $d \approx 80$, 바둑은 $b \approx 250$, $d \approx 150$입니다. 다 따지는 것은 불가능합니다.

탐색을 줄이는 고전적 방법은 두 가지였습니다.

1. 깊이 줄이기 — 형세 판단: 어느 지점에서 탐색을 멈추고 "이 판은 누가 이길 것 같다"는 근사 가치 $v(s)$로 대신합니다. 체스 · 체커 · 오델로에서는 통했지만, 바둑은 형세 판단이 너무 어려워 불가능하다고 여겨졌습니다.
2. 폭 줄이기 — 수 고르기: 모든 수 대신 정책 $p(a \mid s)$에서 그럴듯한 수만 뽑습니다. 몬테카를로 롤아웃(끝까지 빠르게 두어 보고 평균 내기)이 대표적이지만, 바둑에서는 약한 아마추어 수준에 그쳤습니다.

당시 최강 바둑 프로그램들은 MCTS에 사람이 만든 얕은 정책을 붙인 수준이었습니다. AlphaGo는 이 두 가지를 깊은 합성곱 신경망으로 바꿨습니다.

핵심 아이디어

1234567891011flowchart LR
  A[KGS 기보 3천만 국면] --> B[SL 정책망: 사람 수 예측]
  A --> C[빠른 롤아웃 정책]
  B --> D[RL 정책망: 자기 대국으로 승리 최적화]
  D --> E[자기 대국 3천만 국면 생성]
  E --> F[가치망: 승패 예측 회귀]
  B --> G[MCTS 사전 확률 P]
  F --> H[MCTS 잎 평가]
  C --> H
  G --> I[가장 많이 방문한 수 선택]
  H --> I

1. 지도학습 정책망 (SL policy network)

직관: 먼저 고수의 기보를 보며 "이 자리에서 고수는 어디에 뒀나"를 맞히는 연습을 합니다. 바둑 학원에서 기보를 따라 두는 것과 같습니다(해설용 비유).

단계: ① 판을 19×19 크기의 특징 평면 48장으로 바꿉니다(돌 색, 활로 수 등). ② 13층 합성곱 신경망에 넣습니다. ③ 마지막에 소프트맥스로 '각 자리에 둘 확률'을 냅니다. ④ 실제 고수의 수 $a$의 로그 확률을 높이도록 학습합니다.

결과 수치(논문): KGS 바둑 서버의 3천만 국면으로 학습해, 보지 않은 시험 국면에서 고수의 수를 57.0% 맞혔습니다(원시 판 정보와 수순만 쓰면 55.7%). 당시 다른 연구의 최고는 44.4%였습니다. 함께 학습한 빠른 롤아웃 정책 $p_\pi$는 작은 패턴 특징의 선형 소프트맥스라 정확도는 24.2%지만, 한 수에 2μs로 정책망(3ms)보다 훨씬 빠릅니다.

왜 이렇게 했나: 사람 기보는 즉각적이고 질 좋은 학습 신호를 줍니다. 논문은 정확도가 조금만 올라도 실제 기력이 크게 오른다고 보고합니다. 다만 큰 신경망은 정확하지만 탐색 중 평가가 느려서, 정확도와 속도 사이 균형이 필요했습니다(실전 버전은 필터 192개).

2. 강화학습 정책망 (RL policy network)

직관: 기보만 따라 하면 '사람처럼' 두게 될 뿐 '이기는' 수를 두지는 않습니다. 이제 자기 자신과 대국하며 이긴 판의 수는 더 두고, 진 판의 수는 덜 두도록 고칩니다.

단계: ① SL 정책망을 그대로 복사해 시작합니다. ② 예전 버전들을 모은 '상대 풀'에서 무작위로 상대를 고릅니다. ③ 끝까지 대국해 승패 $z_t$(이기면 $+1$, 지면 $-1$)를 얻습니다. ④ 그 판에서 둔 수들의 로그 확률을 $z_t$ 방향으로 고칩니다(REINFORCE).

왜 이렇게 했나: 상대를 최신 버전 하나로 고정하지 않고 예전 버전 풀에서 뽑는 것은, 현재 상대에게만 과적합하는 것을 막아 학습을 안정시키기 위해서입니다(500회 반복마다 현재 가중치를 풀에 추가).

숫자로 해 보기(해설용 예): 어떤 국면에서 정책망이 수 A에 0.2를 줬고 그 판을 이겼다면($z=+1$), $\log 0.2$를 키우는 쪽으로 가중치를 움직여 A의 확률이 예컨대 0.22로 오릅니다. 졌다면($z=-1$) 반대로 내려갑니다.

결과 수치(논문): 탐색 없이 RL 정책망끼리 붙이면 SL 정책망에 80% 넘게 이겼고, 수당 10만 번 시뮬레이션하는 오픈소스 최강 프로그램 Pachi에게 85% 이겼습니다. 이전의 지도학습 합성곱망은 Pachi에게 11%만 이겼습니다. 학습은 GPU 50개로 128판짜리 미니배치 10,000개, 하루가 걸렸습니다.

3. 가치망 (value network)

직관: 대국을 끝까지 두지 않고도 "지금 판이면 흑이 이길 확률이 얼마"라고 한눈에 읽는 형세 판단력입니다.

단계: ① RL 정책망끼리 자기 대국을 합니다. ② 한 판에서 딱 한 국면만 뽑아 (국면, 최종 승패) 쌍을 만듭니다. ③ 이렇게 3천만 판에서 3천만 국면을 모읍니다. ④ 예측값과 실제 결과의 평균 제곱 오차를 줄이도록 회귀합니다.

왜 한 판에 한 국면만 뽑았나: 한 판 안의 국면들은 돌 하나 차이로 서로 매우 비슷한데 정답(승패)은 같습니다. KGS 전체 기보로 학습하자 가치망이 일반화 대신 결과를 외워, 학습 오차 0.19 · 시험 오차 0.37로 크게 벌어졌습니다. 판마다 한 국면만 쓰자 학습 0.226 · 시험 0.234로 과적합이 거의 사라졌습니다.

결과 수치(논문): 가치망 한 번의 평가는, RL 정책망으로 롤아웃한 몬테카를로 평가와 정확도가 비슷하면서 계산은 15,000배 적었습니다.

4. 정책망과 가치망을 결합한 MCTS

직관: 바둑 고수가 수읽기를 할 때, 직관으로 그럴듯한 몇 수만 떠올리고(정책망), 몇 수 앞의 형세를 판단합니다(가치망 + 빠른 수읽기). 이를 수천 번 반복해 가장 자주 검토한 수를 둡니다.

단계(시뮬레이션 1회): ① 선택: 뿌리에서부터 아래 식이 가장 큰 수를 따라 내려갑니다. ② 확장: 잎에 닿으면 SL 정책망으로 그 국면의 사전 확률 $P$를 계산해 저장합니다. ③ 평가: 잎을 가치망 $v_\theta$와 빠른 롤아웃 결과 $z_L$로 평가해 섞습니다. ④ 역전파: 지나온 모든 가지의 방문 횟수와 평균 가치를 갱신합니다. 탐색이 끝나면 뿌리에서 가장 많이 방문한 수를 둡니다.

왜 이렇게 했나:

• 보너스 $u$는 처음엔 정책망이 좋다고 한 수를 먼저 보게 하고, 방문이 쌓이면 실제 평가 $Q$를 믿게 합니다. 직관과 검증의 균형입니다.
• 사전 확률에는 더 강한 RL 정책망이 아니라 SL 정책망을 썼습니다. 논문은 사람은 유망한 수를 여러 개 고르는 반면 RL은 최선의 한 수에 집중하기 때문으로 추정합니다. 반대로 가치망은 RL 정책망에서 만든 것이 더 좋았습니다.
• 최종 수는 평균 가치가 아니라 방문 횟수로 고릅니다. 이상치에 덜 민감하기 때문입니다.

숫자로 해 보기(해설용 예, 비례상수 1로 단순화): 수 A는 $P=0.5$, $N=4$, $Q=0.1$, 수 B는 $P=0.2$, $N=0$, $Q=0$입니다. A의 점수는 $0.1 + 0.5/5 = 0.2$, B는 $0 + 0.2/1 = 0.2$로 같습니다. A를 한 번 더 방문하면($N=5$) A는 $0.1 + 0.5/6 \approx 0.183$으로 내려가, 다음엔 아직 안 본 B를 탐색하게 됩니다. 잎 평가에서 $\lambda = 0.5$, 가치망 0.6, 롤아웃 결과 $+1$이면 $V = 0.5 \times 0.6 + 0.5 \times 1 = 0.8$입니다.

5. 규모와 계산

• 신경망 평가는 전통적 탐색 휴리스틱보다 훨씬 비싸서, CPU에서 시뮬레이션을 돌리고 GPU에서 정책망 · 가치망을 병렬로 계산하는 비동기 다중 스레드 탐색을 썼습니다.
• 최종 단일 기계 버전: 탐색 스레드 40개, CPU 48개, GPU 8개. 분산 버전: CPU 1,202개, GPU 176개.
• SL 정책망 학습은 GPU 50개로 약 3주(3억 4천만 단계), 가치망 학습은 GPU 50개로 1주였습니다.

결과

• 평가 방식 비교: 가치망만 쓴 버전($\lambda = 0$)도 다른 모든 바둑 프로그램보다 강했습니다. 그러나 가치망과 롤아웃을 반씩 섞은 버전($\lambda = 0.5$)이 가장 강해, 다른 변형들에 95% 이겼습니다. 저자들은 두 평가가 서로 보완한다고 해석합니다.
• 판후이와의 대국에서 AlphaGo는 딥블루가 카스파로프와 체스를 둘 때보다 수천 배 적은 국면을 평가했습니다. 대신 정책망으로 더 똑똑하게 고르고 가치망으로 더 정확하게 평가했습니다.

왜 중요한가 · 이후 영향

• '10년은 걸릴 것'이라던 일을 해냈습니다. 정식 크기 바둑에서 컴퓨터가 프로를 이긴 첫 사례입니다.
• 손으로 만든 평가 함수 없이: 딥블루는 사람이 설계한 평가 함수에 기댔지만, AlphaGo의 신경망은 범용 지도학습 · 강화학습으로 대국 데이터에서 직접 배웠습니다.
• 탐색 + 학습의 표준 틀: 이후 AlphaGo Zero는 사람 기보와 롤아웃을 없애고 정책망 · 가치망을 하나로 합쳤고, AlphaZero는 체스 · 쇼기로, MuZero는 규칙을 모르는 환경으로 넓혔습니다.
• LLM 추론에서 여러 후보를 만들어 평가 모델로 고르는 방식도 "정책(생성) + 가치(평가) + 탐색"이라는 같은 발상과 닮았습니다(해설자의 비교).

한계 · 주의할 점

• 사람 기보에 의존: 첫 단계가 KGS 3천만 국면의 지도학습입니다. 사람 데이터가 없는 분야에는 그대로 옮길 수 없습니다(AlphaGo Zero가 이 한계를 넘습니다).
• 손으로 만든 특징: 입력 48개 특징 평면과 롤아웃 정책의 패턴 특징에는 바둑 지식이 들어 있습니다.
• 계산량이 큽니다. 학습에 GPU 50개를 몇 주 썼고, 대국에도 GPU 여러 개가 필요합니다.
• 규칙이 알려진 완전 정보 2인 게임을 전제로 합니다. 시뮬레이터가 없는 실제 문제에는 바로 적용되지 않습니다.
• 이 해설의 본문은 DeepMind가 공개한 논문 PDF를 바탕으로 했습니다. Nature 판의 세부(부록 표 등)와 다를 수 있습니다.

이어서 읽을 것

• 앞: 딥 강화학습으로 아타리 게임하기 (DQN) · 강화학습 입문 (Sutton · Barto) 8.11절 · 16.6절
• 뒤: 사람 지식 없이 바둑 정복하기 (AlphaGo Zero) · AlphaZero · MuZero

용어 정리

스스로 점검

1. 정책망과 가치망은 각각 탐색의 무엇을 줄이나? — 정책망은 검토할 수의 '폭'을, 가치망은 끝까지 두지 않고 멈추게 해 '깊이'를 줄입니다.
2. 가치망을 학습할 때 한 판에서 한 국면만 쓴 이유는? — 같은 판의 국면들은 서로 매우 비슷한데 정답이 같아, 모두 쓰면 결과를 외우는 과적합이 생겼기 때문입니다.
3. MCTS의 사전 확률에 RL 정책망 대신 SL 정책망을 쓴 이유는? — 논문은 사람의 수 분포가 유망한 수를 여러 개 고르게 담아 탐색에 더 유리하고, RL 정책망은 최선의 한 수에 몰리기 때문으로 추정합니다.

다음에 볼 것

이 글을 이해했다면 이어서 보면 좋은 항목입니다.

• 사람 지식 없이 바둑 정복하기 (AlphaGo Zero) — 사람 기보 없이 자기 대국 강화학습만으로 이전 AlphaGo를 100대 0으로 이긴 AlphaGo Zero

출처

• 원문: nature.com/articles/nature16961 (2016 · David Silver 외)