AlphaGo 알고리즘 요약

Data & Analytics

jooyoul-lee
of 10
Description
Text
  • AlphaGo 알고리즘 요약 이주열
  • 바둑(or�체스) 인공지능 프로그램 기본 • 게임 경우의 수 탐색à 트리(tree)�탐색 알고리즘 (e.g.�깊이 우선 탐색, 넓이 우선 탐색 알고리즘) 체스의 게임 트리 예시 트리 탐색 예시
  • 바둑이 쉽게 정복되지 않은 이유 • 10360 가지 경우 수 존재 • 바둑 규칙을 고려한 평균 경우 수가 250개, 바둑 평균 약 150수 정도. 따라서, 250150 ≈ 10360 • 우주의 원자 개수(1080)보다 많은 경우 수! • 현재의 컴퓨팅 파워로 정복하기 어렵다는 평가였음 • 1997년 체스 세계 챔피언 카스파로프를 이긴 IBM�Deeper�Blue는 Brute�force�방식으로 게임 트리 Full�search • 따라서, 바둑 정복을 위해서 게임 트리의 탐색 범위를 줄이는 방법 필요
  • AlphaGo 알고리즘 아웃라인 • 게임 트리 탐색 방법: 몬테카를로 트리 탐색(Monte�Carlo�tree�search,�MCTS) • 현재 많은 인공지능 바둑 프로그램(e.g.�Crazy�Stone,�Zen�등)이 채택한 게임 트리 탐색 알고리즘 • 현재 상태(selection)에서 한 단계 예측(Expansion)�후 시뮬레이션(Simulation)한 최종 결과에 따른 트리 상태 정보 업데이트(Backpropagation).�이 과정을 X�번 반복à 모든 경로 탐색 불가능시 효율적 • 게임 트리 탐색 범위 줄이는 방법: AlphaGo 핵심 알고리즘 • 넓이 탐색 범위 줄이기 : 현재 상태에서 다음 착수 위치 찾기à MCTS의 Expansion • 깊이 탐색 범위 줄이기 : 해당 착점의 승률 계산à MCTS의 Simulation
  • 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
  • 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�학습
  • 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’
  • 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 단계è
  • 참고문헌 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
  • 감사합니다.
Comments
Top