AlphaGo 알고리즘 요약

Data & Analytics

jooyoul-lee
  • 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
  • 감사합니다.
Please download to view
10
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
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