AlphaGo의 인공지능 알고리즘 분석 2

1. AlphaGo 인공지능 바둑 프로그램의 등장

□ AlphaGo는 DeepMind 팀이 개발한 바둑 인공지능 프로그램

 ￮ 바둑은 아직 인공지능 프로그램이 정복하지 못한 “그랜드 챌린지”

 －기존 인공지능 바둑 프로그램은 아마추어 수준이 한계 (아마추어 6단)

 －AlphaGo는 프로 바둑기사와 대등하게 대국하여 승리한 최초의 바둑 인 공지능 프로그램

 ＊프로기사와 대국한 기존의 바둑 프로그램은 4점 접바둑에서 승리한 것이 최고의 성적

 ＊2016년 3월 세계 최고의 프로 바둑기사 중 한 명인 이세돌 9단에게 도전

 ￮ 그동안 인공지능에 의해 바둑이 정복되지 않은 가장 큰 이유는 바둑의 경 우의 수가 매우 많기 때문

 －바둑 게임은 검은 돌과 흰 돌이 번갈아가면서 두고, 빈 바둑판으로부터 시작하여 기권이나 더 이상 둘 곳이 없을 때까지 진행

 －(바둑판의 상태는 10^170가지) 19x19 격자로 구성된 바둑판의 착수할 수 있는 지점은 361개 이고, 지점마다 3가지 상태(검은 돌, 흰 돌, 빈 칸)가 있으므로 바둑판 상태는 3^361 ≈ 10^170가지가 존재

 ＊10^170이라는 숫자는 단순히 바둑판의 상태를 나타낸 것이므로 바둑 경기 를 진행하는 수순과는 다름

 －(바둑판의 경로는 10^360가지) 10^170가지의 바둑판 상태가 수순에 따라 중 복될 수 있으므로, 수순을 고려한 경로는 약 10^360가지가 존재

 ＊빈 바둑판에 첫 수를 둘 수 있는 경우의 수는 361 개, 두 번째 수는 360 개로 마지막 361 번째 수까지 총 361!(팩토리얼)의 경우의 대국이 존재

 ＊착수 금지점 등 바둑의 규칙을 고려하면, 평균적으로 다음 수를 둘 수 있 는 경우의 수가 250개이고 바둑 게임의 평균 수(길이)는 약 150수 정도임 (빈 바둑판으로부터 시작하여 약 250^150≈10^360 가지의 경우의 수, 그림 1)

＊250^150은 우주의 원자수(약 10^80개) 보다 월등히 많은 수로 모든 경우의 수를 계산한다는 것이 사실상 불가

 ￮ 인공지능 바둑 프로그램은 250^150의 경우의 수를 모두 탐색하지 않고, 제한 된 시간 안에 가장 승리할 가능성이 높은 경로를 탐색

 ＊탐색의 전략이 인공지능 바둑 프로그램의 성능을 좌우함

□ AlphaGo와 프로 바둑기사의 대결

 ￮ AlphaGo는 딥러닝을 통해 프로 바둑기사의 패턴을 학습하여 바둑 인공지능 의 성능을 획기적으로 개선

 ￮ 2015년 10월 유럽 바둑챔피온 판후이(Fan Hui) 프로 2단을 5:0으로 완파

AlphaGo 관련 인터뷰

Ÿ (판 후이, 유럽 바둑챔피온) “만약 AlphaGo를 컴퓨터 프로그램이라고 알려 주지 않았다면, AlphaGo는 약간 이상하지만 매우 실력있는 바둑기사라고 생각했을 것이다. 게다가 AlphaGo는 지치지 않기 때문에, 공격적인 수를 두 어도 덤덤하게 반응하는 마치 벽을 연상케 했다.”

Ÿ (토비 매닝, 심판) “누가 컴퓨터이고 사람인지 구분할 수 없을 정도로 AlphaGo는 사람과 유사하다. AlphaGo가 사람과 다른 점은 공격적인 수를 잘 두지 않는 점뿐이다. ”

Ÿ (박승철, 한국기원 프로 7단) “판후이와의 대결을 복기해본 결과, 전반적으 로 판후이 2단의 기량이 AlphaGo에 미치지 못한다고 판단한다. AlphaGo는 대국 전체를 읽는 것에는 능통하나, 상대의 수를 분해하여 대세점을 찾는 능력은 부족하다.”

－공식경기(formal) 5회, 비공식 경기(informal) 5회 대결. 비공식 경기에서 는 3:2로 AlphaGo 승리, 중국식 규칙을 적용 (덤 7.5집)

경기 형태                       제한시간                 비 고

공식경기(formal)         1시간, 초읽기 30초 3회       장고바둑

비공식 경기(informal)        초읽기 30초 3회           속기바둑

<표 1> 공식경기와 비공식경기

￮ 2016년 3월 9일부터 15일 까지 바둑 세계 챔피온인 우리나라 이세돌 9단과 대결 예정 －전문가들은 이세돌 9단의 승리를 예측했으나, 지속적인 학습이 가능한 AlphaGo의 능력이 결국 바둑을 정복할 수도 있을 것이라 전망함

□ AlphaGo의 구조와 성능

 ￮ AlphaGo와 분산(distributed) AlphaGo

 －AlphaGo는 단일 컴퓨터버전(single)과 분산 컴퓨터버전(distributed)으로 구현되었고 비용대비 최대의 성능을 나타낸 환경은 다음 <표 2>와 같음

－분산 AlphaGo 환경은 다수의 컴퓨터를 활용하여 제한된 시간 안에 최대 한의 경로를 탐색하기 위해 개발 ＊유럽 바둑챔피온 판후이와의 대결에서는 분산 AlphaGo가 사용 －AlphaGo의 확장성(scalability)은 다음 [그림 2]와 같음

￮ AlphaGo의 성능은 KGS 기준 프로 2~5단 수준

 －AlphaGo와 분산 AlphaGo의 성능을 추정하기 위해서 5개의 기존 바둑 인공지능 프로그램과 495 경기 수행

 －경기결과 AlphaGo가 총 495게임 중 494번 승리 (승률 99.8%, <표 3> 참조)

 ＊분산 AlphaGo의 승률은 100%

 ＊돌을 놓는데 걸리는 계산시간(착수시간)은 최대 5초로 설정

－기존의 바둑게임 프로그램과의 성능 비교. [그림 3] 참조

출처 : 소프트웨어정책연구소