[RL] Lecture 10: Case Study: RL in Classic Games by David Silver

| 강의 목표

• 고전 게임에서 강화학습의 적용 사례를 이해한다.
• Minimax Search, Self-Play RL, TD Learning, MCTS 등 다양한 기법의 실제 활용을 살펴본다.
• 완전정보 게임(체스, 바둑과 불완전정보 게임(포커)에 대한 접근법 차이를 이해한다.

---

| Classic Games란?

이유

• 단순한 규칙, 깊은 전략
• 수 세기에 걸쳐 연구됨
• 인공지능 연구의 실험실 (AI의 초파리)
• 인간 지능 테스트의 대표 사례
• 재미있다!

---

| 게임 AI의 역사적 성과

게임	AI 수준	프로그램
체커	완벽	Chinook
체스	초인간	Deep Blue
오델로	초인간	Logistello
백개먼	초인간	TD-Gammon
스크래블	초인간	Maven
바둑	그랜드마스터	MoGo, Crazy Stone
포커	초인간	Polaris, SmooCT

TD-Gammon, Logistello, SmooCT 등은 모두 강화학습 기반 프로그램이다.

---

| 게임 이론 기초

최적 정책: Best Response

• 한 플레이어가 고정된 정책을 쓸 때,
  다른 플레이어의 최적 응답이 Best Response

내시 균형(Nash Equilibrium)

• 각 플레이어의 정책이 서로의 Best Response인 상태
• 변경 시 손해 → 학습의 고정점

Self-Play RL = 내시 균형 추정

• 플레이어들이 서로 적응하며 학습
• 각자의 정책이 상대의 환경이 됨
• 반복 학습으로 고정점 수렴 가능

---

| 완전정보 게임 vs 불완전정보 게임

게임 종류	예시	특성
완전정보	체스, 바둑, 오델로	상태 완전 관측
불완전정보	포커, 스크래블	부분 관측, 정보 은닉

이번 강의에서는 먼저 완전정보 게임을 집중적으로 다룬다.

---

| Minimax Search

정의

• Max player는 white, Min player는 black
• 유일한 minimax 값 존재 → 내시 균형

Search 방법

• 깊이 우선 탐색으로 트리를 구성
• 말단 노드에 value function 적용
• Shannon의 체스 탐색 논문이 시초

가치 함수 예시: Binary-Linear Value Function

• 특징 벡터 $x(s)$ 와 가중치 $w$

• 체스: 8000개 수작업 특징 (Deep Blue)
• 체커: 21개 특징, 단계별 분할 (Chinook)

---

| Self-Play RL

TD Learning in Self-Play

방식	업데이트 수식
MC	$\Delta w = \alpha (G_t - v(s,w)) \nabla_w v(s,w)$
TD(0)	$\Delta w = \alpha (v(s',w) - v(s,w)) \nabla_w v(s,w)$
TD(λ)	λ-return 기반 업데이트

Afterstate 기반 개선

• 상태-행동의 가치가 아닌, 행동 후 상태의 가치 추정:

• 규칙으로 다음 상태 계산 가능 (succ)

→ min/max로 행동 선택 가능

사례: Logistello (오델로)

• 150만 개의 특징 생성 (합성적)
• Monte-Carlo로 학습
• World Champion에게 6:0 완승

사례: TD-Gammon (백개먼)

• 비선형 TD 학습 사용
• 무작위 초기화 → self-play
• 3-ply search로 초인간 성능
• Luigi Villa (세계 챔피언) 7:1 승리

---

| RL과 Search의 결합

TD Variants

이름	설명
TD	v(s) ← v(s′)
TD Root	v(s) ← minimax value of s′
TD Leaf	v(s) ← minimax leaf value
TreeStrap	모든 노드에서 minimax backup

사례

프로그램	방법	성과
KnightCap (체스)	TD Leaf	마스터급 성능
Chinook (체커)	TD Leaf	자가학습으로 성능 향상
Meep (체스)	TreeStrap	국제 마스터 상대 13/15 승

---

| Simulation-Based Search

MCTS (Monte-Carlo Tree Search)

• Root 상태부터 self-play 시뮬레이션
• 각 노드에서 UCB 기반 행동 선택 (UCT 알고리즘)
• 평균 보상을 기반으로 트리 업데이트
• Go, Hex, Amazons 등에서 압도적 성능

Maven (스크래블)

• 랙의 조합을 특징으로 가치 함수 구성
• n-step rollout self-play 사용
• 평균 스코어로 행동 평가
• World Champion Adam Logan에게 9:5 승리

---

| 불완전정보 게임에서의 RL

Information State (정보 상태)

• 플레이어가 관측 가능한 정보를 상태로 구성
• 같은 정보 상태에 여러 실제 상태가 포함됨
• 상태 집합 간 유사성 기반 집계 가능

---

해결 방법들

방법	설명
CFR	Counterfactual Regret Minimization (정해진 트리 탐색)
Smooth UCT	MCTS 변형, 평균 정책 기반 학습
Bayesian MDP	정보 상태 기반 샘플링

Smooth UCT (포커)

• 상태에서 두 정책 사용:

  • UCT로 선택 (η 확률)
  • 평균 정책 π_avg로 선택 (1−η 확률)

• Nash 수렴 가능

• MCTS보다 안정적 (포커에서 divergence 방지)

---

| 정리

게임	입력	가치 함수	학습	탐색
체스	피스 벡터	Binary Linear	TreeStrap	αβ Search
오델로	디스크 배열	Binary Linear	MC	αβ
백개먼	체커 수	Neural Network	TD(λ)	MC Search
스크래블	랙 문자	Binary Linear	MC	MC Search
포커	카드 추상화	Binary Linear	MCTS	없음