이산수학 Discrete Mathematics 알파고알고리즘이야기 인천대학교컴퓨터공학과공학시인이숙이철호교수 Jullio@chol.com zullio@inu.ac.kr 010 3957 6683 모바일컴퓨팅연구실 07 401 호
알파고에대하여 알파고의 HW 사양 최종버전 ( 싱글 ) 40개의탐색쓰레드 48개 CPU 8개 GPU를사용 분산구현버전 40개의탐색쓰레드 1202개의 CPU 176개의 GPU를사용 2
AlphaGo 와상용바둑프로그램성능비교 ELO rating??? 3
상용바둑게임프로그램비교 명칭 Crazy Stone Zen Pachi Fuego 개발자대표 Coulom R ( 프랑스 ) 요지오지마 ( 일본 ) Baudis P ( 체코 ) Baudis P ( 캐나다 ) 출시년도 최신버전 2005 2015 MCTS + Pattern Learning (Bradly-Terry 모델적용 ) 사용알고리즘 전적 수 준 2007, 2008 UEC 컵우승 2013 년제 1 회전성전에서이시다 9 단에게 4 점접바둑승리 2009 5 MCTS 2009, 2011 컴퓨터올림피아드우승, 2012년다케미야아사키 9단에게 4점접바둑승리 2012 11 수정 MCTS + UCT + RAVE ( 오픈소스 ) 2010 SVN 1989 MCTS + UCT ( 오픈소스 ) GnuGo GNU-FSF 1989 3.8 MCTS(3.8 버전 ) Bouzy s 5/21(2.6 버전 ) ( 오픈소스 ) 2011 년인간 vs 컴퓨터바둑대결 ( 파리 ) 에서주준훈 ( 중국 ) 9 단 7 점접바둑승리 2009 년프로그램최초로 9x9 바둑에서주준훈 ( 중국 ) 9 단프로에게이김 6d 6d 2d 1d 5k 4
ELO rating??? 참고 : http://egloos.zum.com/webpd77/v/4102040 실제실력으로순위를정하자 ' 라는취지에부합되는시스템 전적누계방식 ' 승이든패든많은게임을해서전적을많이쌓으면순위가올라가는 ' 방식 각플레이어를 A, B라고할때, 그에대응되는승률 E R 은현재플레이어의레이팅점수 5
ELO rating??? 참고 : http://egloos.zum.com/webpd77/v/4102040 R은현재플레이어의레이팅점수 레이팅점수 각플레이어의 ' 실력 ' 을나타낸다고생각하면됨 처음시작하는사람의수준은임의의한숫자로나타냄. 이를테면 '1500' 만약 A플레이어가 B플레이어보다레이팅 400점이높다면, EA는약0.9090..., EB는약 0.0909... A플레이어가이길확률이약 90%, B플레이어가이길확률이약 10% 두승률을합치면 1, 즉 100% 6
게임트리탐색알고리즘 게임에서장기, 바둑과같이두플레이어가번가아가면서한번씩게임을하는방식 특정게임상태에서다음수를예측하기위해서는수읽기를통해가장승리할확률이높은곳을결정하는알고리즘. 이과정이트리의탐색이고, 이론적으로는현재상태에서가능한모든결과를미리알경우가장승률이높은수를선택하는방법 알파고의인공지능바둑프로그램은 250 150 의경우의수를모두탐색하지않고, 제한된시간안에가장승리할가능성이높은경로를탐색. 탐색의전략이인공지능바둑프로그램의성능을좌우함 7
게임트리의탐색알고리즘 트리탐색기법 ( 트리순회 : Tree traversal) 은트리구조에서각각의노드를한번씩, 체계적인방법으로방문하는과정. 트리탐색기법에는탐색순서에따라전 중 후위및레벨순서순회기법이있음. 이중전위순회 (preorder) 는깊이우선의탐색 (depth-first search: DFS) 이라고도하며, MinMax 알고리즘의탐색방법임. < 탐색순서 > 1. 루트노드에서시작 2. 왼쪽자식노드를방문 - 왼쪽서브트리의전위순회 3. 오른쪽자식노드를방문 - 오른쪽서브트리의전위순회 깊이우선탐색 ( 전위순회 ) 의과정 < 탐색노드의순서 > 1 2 3 4 5 6 7 8 9 8
바둑에서의탐색알고리즘 바둑 (19 X 19) 보다탐색정도가낮은체스 (8 x 8) 의경우완전한게임트리에는약 1040 개의노드가존재 ( 약 35 80 가지의경우의수 ) 효율적인탐색을위해휴리스틱 (Heuristic) 기법깊이또는너비우선탐색기법이사용. 바둑과같은복잡한게임에서는충분한도움이되지않음. 바둑은게임중에서도극단적으로계산량이많음. 가장어려운문제로알려져있음. ( 약 250 150 가지의경우의수 ) 9
몬테카를로방법 (Monte Carlo method) 난수를이용하여함수의값을확률적으로계산하는알고리즘. 수학이나물리학등에자주사용. 계산하려는값이닫힌형식으로표현되지않거나복잡한경우에근사적으로계산할때사용. 모나코의유명한도박의도시몬테카를로의이름에서명명. 10
몬테카를로알고리즘 출처 : https://ko.wikipedia.org/wiki/ 원주율계산알고리즘 에서점를표집. 표집한점의중심이에있고, 반지름이 1인원에속하는지계산. 원의정의에따라와 1을비교함으로써계산. 위의두과정을충분히반복하여, 원에속한점들의개수를계산. 표집영역과원의공통영역은의넓이를가지며, 전체점갯수를원에속한점갯수로나눈비율은이값을근사화 11
몬테카를로트리탐색알고리즘 MCTS(Monte Calro Tree Search) 바둑에서가장널리사용되는인공지능알고리즘 MCTS는최소-최대알고리즘의성능을개선한것 모든경로를탐색하는것이불가능할때효율적 12
MCTS 의 4 단계과정 1 선택현재바둑판상태에서특정경로로수읽기를진행 2 확장일정수이상수읽기가진행되면그지점에서한단계더착수지점을예측 ( 게임트리의확장 ) 3 시뮬레이션 2 에서선택한노드에서바둑이종료될때까지무작위 (random) 방법으로진행. 속도가빠르기때문에여러번수행할수있으나착수의적정성은떨어짐 4 역전파 3 의결과를종합하여확장한노드의가치 (2 에서한단계더착수한것의승산 ) 를역전파하여해당경로의승산가능성을갱신 13
MCTS 의핵심요소 정책트리의폭을제한하는역할 MCTS 의두번째단계인확장에서주로사용특정시점에서가능한모든수중가장승률이높은것을예측 가치트리의깊이를제한하는역할가치는현재대국상황의승산을나타낸것승산이정확할수록많은수 ( 더깊은노드 ) 를볼필요가없음 스스로대국하는학습기법을통해정책과가치의성능을향상시킴 14
15
AlphaGo 의차별성 딥러닝 (Deep Learning) 딥러닝을활용하여전문바둑기사들의패턴을학습함. 바둑기보를 19x19 픽셀을갖는이미지로입력받아전문바둑기사의다음착수를학습하는과정. * 바둑입문자가기보를공부하여바둑기사들의패턴을습득하는것과유사함. *AlphaGo 개발자인데이비드실버는 AlphaGo는 16만개의기보를 5주만에학습했다 라고밝힘. AlphaGo 는딥러닝기법중특히이미지처리에강한컨볼루션신경망을기반으로학습하기때문에국지적인패턴인식에도강점을가짐 * 바둑에서지역적인대국이전체적인형세판단에매우중요한역할을함 바둑기사의착수를학습한것은정책네트워크임 국지적인패턴인식을통한승산판단은가치네트워크로구현 정책과가치네트워크는 MCTS 에서게임트리를탐색할때적용됨 16
AlphaGo 의정책과가치네트워크 정책네트워크 (Policy Network) 정책계산을위한딥러닝신경망 - 정책네트워크에서사용된딥러닝기법은컨볼루션신경망 (Convolution Neural Network, CNN) 으로 19x19 바둑판상태를입력하여바둑판모든자리의다음수선택가능성확률분포를출력. * 컨볼루션신경망은페이스북의얼굴인식기술인 DeepFace 에적용된기술로입력이미지를작은구역으로나누어부분적인특징을인식하고, 이것을결합하여전체를인식하는특징을가짐. - 바둑에서는국지적인패턴과이를바탕으로전반적인형세를파악하는것이중요하므로컨볼루션신경망을활용하는것이적절한선택 17
정책네트워크학습 - 지도학습 (supervised learning) 프로바둑기사들의착수전략학습 *KGS Go Server 프로 6단에서 9단사이의실제대국 16만개기보로부터 3000만가지바둑판상태를추출하여데이터로사용함 * 이중약 2900만개를학습에이용하고, 나머지 100만가지바둑판상태를시험에이용 ( 정확도 57%). 이것은사람이다음수를두는경향을모델링한것 *50개의 GPU를사용하여학습 ( 기간 : 3주, 3억4천번의학습과정 ) - 강화학습 (reinforcement learning) 스스로경기하여지도학습을강화함 * 지도학습의결과로구해진정책네트워크는사람의착수선호도를표현하지만이정책이반드시승리로가는최적의선택이라고볼수없음 * 이것을보완하기위해지도학습으로구현된정책네트워크와자체대결 (self-play) 을통해결과적으로승리하는선택을 강화 학습함약 128번의자체대결을수행 * 이로부터도출된경기결과 (reward) 를바탕으로이기는방향으로가도록네트워크의가중치를강화 ( 개선 ). 강화학습후의정책네트워크로도기존바둑프로그램인 Pachi와대결하여 85% 의승률 *50개의 GPU를사용하여학습 ( 기간 : 1일 ) 18
가치네트워크 (Value Network) 바둑의전체적인형세를파악 - AlphaGo에서는가치 (value) 를계산하기위해딥러닝을이용한가치네트워크 (value network) 사용 * 기존프로그램의가치함수는비교적간단한선형결합으로표현인공신경망을활용하여더정확한값을기대할수있음 - 인공신경망의입력층과은닉층구조는정책네트워크와유사한컨볼루션신경망이지만출력층은현재의가치 ( 형세 ) 를표현하는하나의값 (scalar) 이나오는구조 - 특정게임상태에서의승률 (outcome) 을추정 * 강화학습의자체대결에서생성된 3천만개의바둑상태로부터가치네트워크를학습함 * 게임에서이길경우의승률을 1이라고볼때, 가치네트워크의오차는약 0.234 수준 ( 강화학습의자체대결로학습된신경망을시험 (test) 한오차 ) *50개의 GPU를사용하여학습 ( 기간 : 1주 ) 19
AlphaGo 의컨볼루션신경망 컨볼루션신경망개요 컨볼루션신경망은이미지나비디오에서객체의분류에특화된방법 이미지의객체분류는전통적인인공신경망인다층퍼셉트론으로도충분히가능했으나, 노드간링크가모두연결되어있는구조 (fully-connected) 가갖는한계때문에그대안으로컨볼루션신경망이부상함 이미지처리 (Image processing) 분야에서의컨볼루션은필터 ( 커널 ) 을지칭하고, 이컨볼루션필터로원본이미지를처리하여특징을추출해냄 바둑에서컨볼루션필터의의미는국소적, 지역적인대국의특징을추출해내서전반적인형세를추론하는도구로볼수있음 20
AlphaGo 의컨볼루션신경망 AlphaGo 에서사용된컨볼루션신경망구조 특정바둑상태는 19x19 의행렬에대하여 48 가지특징을추출 흰돌, 검은돌, 빈칸, 축, 활로, 과거기록등 각각 48 가지특징맵 (feature map) 19x19 의이진행렬로구성됨 컨볼루션신경망의미지수는필터의가중치값 신경망구조 입력층 : 특정대국에대한 48 가지특징맵 은닉층 : 13 개의컨볼루션층 결과층 : 착수가능한다음수의확률분포 (19x19, 정책네트워크 ) 현재대국에서의승산 ( 스칼라, 가치네트워크 ) 21
AlphaGo 의컨볼루션신경망 컨볼루션층의상세구조 컨볼루션필터는 k개로 AlphaGo에서는 k=128, 192, 256, 384의경우모두테스트함 ( 성능이가장좋은필터개수는 192) 첫번째은닉층의컨볼루션필터는 5x5 크기로총 k개. zero-padding으로 19x19를 23x23으로표현 (stride는 1) 두번째부터 12번째은닉층의컨볼루션필터는 3x3 크기로총 k개 (1 zero-padding, stride는 1) 13 번째은닉층은 1x1 컨볼루션필터한개로 19x19 한개가 13번째층의결과값 ( 정책네트워크결과층 ) softmax 활성함수를통해착수가능한지점의확률분포산출 ( 가치네트워크결과층 ) fully-connected된 256노드의은닉층을지나결과층으로전파됨. 마지막으로 tangent hyperbolic 활성함수를지나스칼라값산출 22
AlphaGo 의컨볼루션신경망 AlphaGo 의컨볼루션신경망구조 ( 정책, 가치네트워크 ) 23