[정보] 알파고 (바둑 인공지능)의 작동 원리

알파고의 작동 원리를 설명한 슬라이드입니다. 내용 참고 하세요..

 

 

알파고 (바둑 인공지능)의 작동 원리 from Shane (Seungwhan) Moon

 

 
1. 발표자: 문승환 PhD  student Language  Technologies  Institute,  School  of  Computer  Science Carnegie  Mellon  University 3/2/2016 작동원리
2.  알파고 vs  유럽챔피언 (판 후이 2단) 2015년 10월 5일 – 9일 <공식경기> -­‐ 제한시간 1시간, 30초 초읽기 3회 -­‐ 5:0  알파고 승리 (불계승 4번)
3.  알파고 vs  세계챔피언 (이세돌 9단) 2016년 3월 9일 – 15일 <공식경기> -­‐ 제한시간 2시간, 1분 초읽기 3회 서울 광화문 포시즌스 호텔 이미지 출처: 조선일보 1월 28일자 인간과 컴퓨터의 자존심을 건 '세기의 대결'
4.  이세돌 사진 출처: 매일경제 2013/04
 5.  “자신이 없어요. 질 자신이요” 사진 출처: 바둑 TV
 6.  "아,  싸울만 해서 싸워요.  수가 보이는데 어쩌란 말이에요." 사진 출처
7.  "불리하다보니 이기자는 생각없이 대충 뒀는데 이겼네요.” -­‐ 구리 九단에게 대역전승을 거둔 직후의 인터뷰 사진 출처
8.  바둑 인공지능?
9.  바둑 인공지능? 정의하자면: s (state) d  =  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = (예를 들면 이런 식으로 행렬로 표현) *  실재론 board  position  외 다른 feature들도 포함
10.  바둑 인공지능? 정의하자면: s (state) d  =  1 d  =  2 a (action) Given  s,  pick  the  best  a 바둑 인공지능s a s'
 11.  바둑 인공지능?  이렇게 만들어 보면? d  =  1 d  =  2 … 모든 경우의 수를 시뮬레이션
12.  바둑 인공지능?  이렇게 만들어 보면? d  =  1 d  =  2 … d  =  3 … … … …
13.  바둑 인공지능?  이렇게 만들어 보면? d  =  1 d  =  2 … d  =  3 … … … … … d  =  maxD 끝까지 시뮬레이션 해서 Win? Lose?  결과 리포트
14.  바둑 인공지능?  이렇게 만들어 보면? d  =  1 d  =  2 … d  =  3 … … … … … d  =  maxD Win? Lose?  결과 리포트 여기에 두면 13번 이기더라 37,839번 431,320번 끝까지 시뮬레이션 해봤을 때 제일 많이 이긴 “다음 수”를 고름
15.  Maximum  depth  search:   이 방법은 경우의 수가 우주의 원자 수보다 많아 불가능
16.  핵심: 경우의 수 (Search  Space) 줄이기
17.  경우의 수 (Search  Space) 줄이기 1.  “action”  후보군 줄이기 (Breadth  Reduction) d  =  1 d  =  2 … d  =  3 … … … … d  =  maxD Win? Lose? “이런 수는 사람이 두지 않는다”고 판단하는 모델이 있다면 …
18.  경우의 수 (Search  Space) 줄이기 1.  “action”  후보군 줄이기 (Breadth  Reduction) d  =  1 d  =  2 … d  =  3 … … d  =  maxD Win? Lose? Search  후보군에서 미리 제외 (breadth  reduction)
 19.  경우의 수 (Search  Space) 줄이기 2.  결과 더 빨리 예측하기 (Depth  Reduction) d  =  1 d  =  2 … d  =  3 … … d  =  maxD Win? Lose? Maximum  depth까지 시뮬레이션 하지 않고 ..
20.  경우의 수 (Search  Space) 줄이기 2.  결과 더 빨리 예측하기 (Depth  Reduction) d  =  1 d  =  2 … d  =  3 … V  =  1 V  =  2 V  =  10 V(s):  “state  s의 판세” 로 요약
21.  경우의 수 (Search  Space) 줄이기 1. “action”  후보군 줄이기 (Breadth  Reduction) 2. 결과 더 빨리 예측하기 / 판세 평가하기 (Depth  Reduction)
 22.  1.  “action”  후보군 줄이기 Learning:  P  (  next  action  |  current  state  ) =  P  (  a  |  s  )
 23.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 현재 판 예측 모델 다음 판 s1 s2 s2 s3 s3 s4 Data:  온라인 바둑 고수 (5~9단) 기보 16만 개, 착점 3000만 개
24.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 예측 모델 현재 판 다음 판
25.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 예측 모델 현재 판 다음 액션
26.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 예측 모델 현재 판 다음 액션 0 0   0 0 0   0 0 0 0 0 0   0 0 0 1 0 0 0 0 -­‐1 0 0 1 -­‐1 1 0 0 0 1 0 0 1 -­‐1 0 0 0 0 0   0 0 -­‐1 0 0 0 0 0 0   0 0 0   0 0 0 0 0 -­‐1 0 0 0   0 0 0 0 0 0   0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s af:  s à a *  실재론 board  position  외 다른 feature들도 포함
27.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 예측 모델 현재 판 다음 액션 0 0   0 0 0   0 0 0 0 0 0   0 0 0 1 0 0 0 0 -­‐1 0 0 1 -­‐1 1 0 0 0 1 0 0 1 -­‐1 0 0 0 0 0   0 0 -­‐1 0 0 0 0 0 0   0 0 0   0 0 0 0 0 -­‐1 0 0 0   0 0 0 0 0 0   0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s g:  s à p(a|s) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0             0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.2 0.1 0 0 0 0 0 0 0 0.4  0.2 0 0 0 0 0 0 0 0.1       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p(a|s) aargmax
 28.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 예측 모델 현재 판 다음 액션 0 0   0 0 0   0 0 0 0 0 0   0 0 0 1 0 0 0 0 -­‐1 0 0 1 -­‐1 1 0 0 0 1 0 0 1 -­‐1 0 0 0 0 0   0 0 -­‐1 0 0 0 0 0 0   0 0 0   0 0 0 0 0 -­‐1 0 0 0   0 0 0 0 0 0   0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s g:  s à p(a|s) p(a|s) aargmax
 29.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) Deep  Learning (13  Layer  CNN) 현재 판 다음 액션 0 0   0 0 0   0 0 0 0 0 0   0 0 0 1 0 0 0 0 -­‐1 0 0 1 -­‐1 1 0 0 0 1 0 0 1 -­‐1 0 0 0 0 0   0 0 -­‐1 0 0 0 0 0 0   0 0 0   0 0 0 0 0 -­‐1 0 0 0   0 0 0 0 0 0   0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s g:  s à p(a|s) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0             0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.2 0.1 0 0 0 0 0 0 0 0.4  0.2 0 0 0 0 0 0 0 0.1       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p(a|s) aargmax
 30.  Convolutional  Neural  Network  (CNN) CNN은 레이어별로 input  image를 추상화 시켜 Image  Recognition을 굉장히 잘함이미치  출처
31.  Convolutional  Neural  Network  (CNN) 이걸 바둑의 판세를 읽는 데에 사용
32.  바둑: 추상화하는 능력이 중요 CNN:  추상화하는 능력이 뛰어난 모델 바둑 두는 Task와 CNN의 장점이 맞물린 경우
33.  Deep  Learning ~=  Representation  Learning à 단을 쌓아 올라갈수록 추상화된 feature를 익힘
34.  1.  “action”  후보군 줄이기 (1) 프로 바둑기사 따라하기 (supervised  learning) 프로기사 흉내내는 모델 (w/  CNN) 현재 판 다음 액션 Training:
 35.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 프로기사 흉내내는 모델 (w/  CNN) 프로기사 흉내내는 모델 (w/  CNN) VS
 36.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 프로기사 흉내내는 모델 (w/  CNN) 프로기사 흉내내는 모델 (w/  CNN) VS Return:  대국 기보, 승/패자 정보
37.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 프로기사 흉내내는 모델 (w/  CNN) 어느 판 승/패 Training: 패 z  =  -­‐1
 38.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 프로기사 흉내내는 모델 (w/  CNN) 어느 판 승/패 Training: 승 z  =  +1
 39.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 업데이트 모델 ver 1.1 업데이트 모델 ver 1.3VS Return:  대국 기보, 승/패자 정보 프로기사 흉내내는 모델과 똑같은 topology,  업데이트 된 parameters를 사용
40.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 업데이트 모델 ver 1.3 업데이트 모델 ver 1.7VS Return:  대국 기보, 승/패자 정보
41.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 업데이트 모델 ver 1.5 업데이트 모델 ver 2.0VS Return:  대국 기보, 승/패자 정보
42.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning) 업데이트 모델 ver 3204.1 업데이트 모델 ver 46235.2VS Return:  대국 기보, 승/패자 정보
43.  1.  “action”  후보군 줄이기 (2) 스스로 발전하기 (reinforcement  learning)  트레이닝 결과 업데이트 모델 ver 1,000,000VS 최종 모델이 80% 승리 프로기사 흉내내는 모델
44.  2.  판세 평가하기
45.  2.  판세 평가하기 업데이트 모델 ver 1,000,000 어느 판 Training: 승/패 승 (0~1) 예측 모델 (Regression) 기존 모델에 regression  layer를 더함 0~1 사이의 값으로 예측 1에 가까우면 좋은 판세 0에 가까우면 좋지 않은 판세
46.  경우의 수 (Search  Space) 줄이기 1. “action”  후보군 줄이기 (Breadth  Reduction) 2. 판세 평가하기 (Depth  Reduction) Policy  Network Value  Network 알파고 논문에서 이런 용어를 만들어서 부름
47.  +수 읽기 (w/  Monte  Carlo  Search  Tree) Action  후보군 줄이기 (Policy  Network) 수 평가하기 (Value  Network) (Rollout):  Faster  version  of  estimating  p(a|s) ;  shallow  network  (3  ms à 2µs) *  Rollout   결과와 value  network  결과 값을 반반씩 합쳐서 최종 prediction
 48.  결과 Elo rating  system 알파고 components  들의  조합에  따른  성능  비교
49.  Takeaways 임의의 task를 위해 training한 network를 다양하게 활용
50.  이세돌 9단 vs  알파고