[정보] AlphaGo 알고리즘

Google DeepMind의 AlphaGo가 작동하는 알고리즘을 간략하게 요약했습니다.
주로 기존의 자료 중 설명이 빈약했던 Reinforcement Learning에 대한 설명이 추가된 자료입니다.
많은 참고 하시기 바랍니다.

 

AlphaGo 알고리즘 요약 from Jooyoul Lee

 

 

1. AlphaGo 알고리즘 요약 이주열
2.  바둑(or 체스) 인공지능 프로그램 기본 • 게임 경우의 수 탐색 à 트리(tree) 탐색 알고리즘 (e.g. 깊이 우선 탐색, 넓이 우선 탐색 알고리즘) 체스의 게임 트리 예시 트리 탐색 예시
3.  바둑이 쉽게 정복되지 않은 이유 • 10360 가지 경우 수 존재 • 바둑 규칙을 고려한 평균 경우 수가 250개, 바둑 평균 약 150수 정도. 따라서, 250150 ≈ 10360 • 우주의 원자 개수(1080)보다 많은 경우 수! • 현재의 컴퓨팅 파워로 정복하기 어렵다는 평가였음 • 1997년 체스 세계 챔피언 카스파로프를 이긴 IBM Deeper Blue는 Brute force 방식으로 게임 트리 Full search • 따라서, 바둑 정복을 위해서 게임 트리의 탐색 범위를 줄이는 방법 필요
4.  AlphaGo 알고리즘 아웃라인 • 게임 트리 탐색 방법: 몬테카를로 트리 탐색(Monte Carlo tree search, MCTS) • 현재 많은 인공지능 바둑 프로그램(e.g. Crazy Stone, Zen 등)이 채택한 게임 트리 탐색 알고리즘 • 현재 상태(selection)에서 한 단계 예측(Expansion) 후 시뮬레이션(Simulation)한 최종 결과에 따른 트리 상태 정보 업데이트(Backpropagation). 이 과정을 X 번 반복 à 모든 경로 탐색 불가능시 효율적 • 게임 트리 탐색 범위 줄이는 방법: AlphaGo 핵심 알고리즘 • 넓이 탐색 범위 줄이기 : 현재 상태에서 다음 착수 위치 찾기 à MCTS의 Expansion • 깊이 탐색 범위 줄이기 : 해당 착점의 승률 계산 à MCTS의 Simulation
 5.  AlphaGo 핵심 알고리즘 (1/2) • 게임 트리의 넓이 탐색 범위 줄이기: 착수 위치 찾기 1) 바둑 기보 패턴 학습 à SL policy network으로 명명 • Convolutional Neural Networks(ConvNet)로 약 3천만 KGS 기보 학습 • Deep Learning 알고리즘 중 하나인 ConvNet은 이미지 패턴 인식에 탁월하며 지도 학습(Supervised Learning, SL)에 해당 • P(a|s)를 최대화하는 방향으로 ConvNet 학습, [P(a|s)는 상태(status, s)에 따른 다음 수 행위(action, a) 확률] 2) 학습한 기보에만 최적화되는 것을 방지하기 위해 자가 대국(self play)으로 강화 학습 à RL policy network으로 명명 • 기보 패턴을 학습한 ConvNet들간 대국으로 승패에 따른 강화 학습1)(Reinforcement Learning, RL) 실행 • Policy Gradient 강화 학습 알고리즘 적용. 이는 강화학습의 Q-function과 같은 reward score 함수 구하기가 아닌 P(a|s)를 직접 구 하는 방법 [policy(s) = arg maxa Q(s, a)] • P(a|s)를 최대화하는 방향으로 ConvNet 학습 3) 단순 패턴 인식 à Rollout policy으로 명명 • 바둑 규칙에 따른 단순 P(a|s) 확률 계산 • SL policy network, RL policy network, Rollout policy를 조합하여 사용 주1) 강화 학습은 결과에 따른 reward score를 부여함: E.g. 승리하면 +1, 패배하면 -1
 6.  AlphaGo 핵심 알고리즘 (2/2) • 게임 트리의 깊이 탐색 범위 줄이기: 해당 착점의 승률 • 앞서 만든 RL policy network으로 승률 계산하는 ConvNet 학습 à Value network으로 명명 • RL policy network에서 확률 함수 대신에 reward score 함수(e.g. Q-function) 정의 • Reward score 예측이 잘 맞는 방향으로 KGS 기보 학습 • Deep Q Network 강화 학습과 유사한 형태로 앞서 RL policy network의 Policy Gradient 알고리즘과 다름 • 학습한 KGS 기보에 최적화되는 것을 방지하기 위해 신규로 자가 대국(self play)한 기보로 학습 • RL policy network들간 자가 대국 후 생성된 기보로 Value network 학습
7.  AlphaGo의 deep neural network 학습 파이프라인 Human expert positions Classification SL Policy network Self Play RL Policy network Self Play Self-play data Value network Regression - Slide from ‘David Sliver’
8.  AlphaGo의 게임 트리 탐색(MCTS) 과정 Q: MCTS action value, u(P): Policy network이 제공하는 확률(P)에 비례, 방문 회수에 반비례하는 함수 a. 특정 단계(L-1)까지 착수 선택: Q + u(P) 최대값 선택, b. 탐색 경로 L단계까지 확장 : 확률(P 𝜎)에 따른 노드 확장 c. 확장한 L단계 노드의 승률 평가: Value network의 value(v 𝜃)와 Rollout policy로 게임 종료까지 시뮬레이션(P 𝜋)하여 평가한 값(r)을 결합하여 승률 평가 d. 바둑 게임 트리의 상태 갱신: 선택 노드에 있는 Q 값 갱신 L 단계 è
 9.  참고문헌 1. [Nature] Mastering the game of Go with deep neural networks and tree search 2.[SPRi] AlphaGo의 인공지능 알고리즘 분석 3. [NIPS] Policy Gradient Methods for Reinforcement Learning with Function Approximation 4.[WIKIPEDIA] Reinforcement learning
 10.  감사합니다.