전문가 입장에서 본 알파고의 알고리즘과 약점(이세돌에게 전해주세요)

OO · 2016.03.11 20:20:49

2016/03/11 10:43

알파고의 알고리즘과 약점 나홀로 리서치

먼저 저는 전공자가 아니고 알파고의 네이처 논문만 보고 느낀 점을 정리한 것이기 때문에 한계가 있다는 점은 이해 바랍니다.

바둑이나 체스와 같은 보드게임을 포함한 모든 게임에서 필요한 모든 정보를 가지고 있다고 가정할 때, 현재의 상태를 보면 누가 이길지에 대한 확률을 계산할 수 있습니다. 바둑에서 현재 돌이 놓인 모양을 보고 사람들이 대충 누가 유리하겠구나 판단하는 것이 이 과정에 해당합니다. 이것을 가치 함수 (value function) 라고 합니다.

단순한 게임일 수록 이 확률을 정확하게 계산하기 쉽죠. 예를 들면 기본적인 룰만 적용한 오목은 현재 놓인 돌의 모양을 보고 누가 이길지 100% 예측할 수 있으며 심지어 아무 돌이 놓여 있지 않아도 100% 예측할 수 있습니다. 다시 말해 무조건 선이 이깁니다. 물론 이것은 각 플레이어가 최선의 선택을 한다는 가정하에서 입니다. 사람은 그 모든 경우를 다 계산할 수 없지만 컴퓨터는 가능합니다. 이처럼 가능한 경우의 수를 플레이해 보는 것을 트리 탐색 (tree search) 이라고 합니다. 트리 탐색을 완벽하게 하면 정확한 가치 함수를 계산할 수 있습니다.

하지만 게임이 복잡해 질 수록 경우의 수가 기하급수적으로 늘어나서 아무리 빠른 컴퓨터로도 그 모든 경우를 다 계산하는 것은 불가능해 집니다. 바둑이 그 대표적인 예입니다. 바둑에서 나올 수 있는 모든 경우의 수를 다 플레이해 보고 이길 확률을 계산하는 것은 인간이 만들 수 있는 컴퓨터로는 불가능합니다.

따라서 모든 경우를 다 플레이해 보지 않고도 최선의 수를 찾아내는 것이 인공지능 개발에서 핵심적인 알고리즘이 됩니다.

경우의 수를 줄이는 첫 번째 방법은 경우의 수를 플레이해보는 단계를 줄이는 것입니다. 바둑이라면 끝까지 두어보는 것이 아니라 한 20~30 수 정도만 두어보고 좋은 수인지 나쁜 수인지를 판단하는 거죠. 하지만 끝까지 두어보지 않으면 승패를 알 수 없죠. 따라서 20~30 수 정도를 둔 후에 높은 가치 함수를 갖는 모양이 나올 수 있는 경우의 수를 좋은 수라고 판단하고 이를 바탕으로 가치 함수를 계산합니다.

여기서 잠깐 뭔가 이상한 것을 느끼셨을 겁니다. 가치 함수를 계산하기 위해서는 트리 탐색을 해야 하는데 그 트리 탐색을 하기 위해서 서는 가치 함수가 필요한 무한 반복에 빠지게 되는 거죠. 이런 경우에는 가상의 가치 함수를 가정하고 트리 탐색을 한 뒤 새로운 가치 함수를 계산합니다. 그 뒤 계산한 가치 함수를 이용하여 다시 트리 탐색을 해서 더 나은 가치 함수를 계산하는 거죠. 이와 같은 과정을 계속 반복하면 가치 함수가 점점 가장 정확한 값에 수렴하게 됩니다. 이와 같은 방법을 반복법 (iteration) 이라고 합니다. 어려운 문제에서 최적값을 찾기 위해 가장 흔하게 쓰는 방법이죠.

물론 이 방법이 100% 정확하지는 않습니다. 구하는 값이 진짜 최적값이 아니라 인접한 구간에서의 최적값에 수렴할 수도 있거든요. 예를 들면 열심히 등산을 해서 정상에 올랐는데 알고보니 안개에 가린 저 멀리에 진짜 최고봉이 있었다라는 식입니다. 그래도 대부분의 경우에는 상당히 정확합니다. 체스 챔피언을 이긴 인공지능도 이 알고리즘으로 만들어졌죠.

하지만 바둑은 경우의 수가 훨씬 많아서 이 방법만으로는 부족합니다. 그래서 나온 두 번째 방법이 모든 경우의 수를 다 플레이해보지 않고 일부 경우의 수만 플레이해 보는 것입니다. 이를 몬테카를로 (Monte carlo) 방법이라고 합니다. 다음 수를 두었을 때 벌어질 수 있는 모든 경우를 다 고려하는 것이 아니라 일부 경우만 골라 계산해보고 거기서 나오는 부분 평균값을 전체의 평균이라고 가정하는 거죠.

일부의 경우를 고르는 방법은 그냥 랜덤하게 고르기도 하지만 바둑과 같이 일반적인 플레이어가 바둑판에 랜덤하게 돌을 놓는 것이 아니라 나름의 결정에 의해 플레이 하는 경우에는 상식적으로 많이 돌을 놓는 경우를 골라 플레이해 보는 것이 더 좋겠죠. 이와 같이 다음에 어디에 돌을 놓을까에 대한 정보를 제공하는 것을 정책 (policy) 이라고 합니다.

즉, 모든 경우를 다 플레이해 보는 것이 아니라 사전에 결정된 정책에 의해 나올 확률이 높은 경우들만 골라 플레이해보고 이를 바탕으로 가치 함수를 계산한다는 거죠. 그럼 그 정책은 어떻게 결정될까죠. 물론 가치 함수에 기반해서 결정됩니다. 또 무한 반복이 나왔죠. 가치 함수를 계산하기 위해서는 정책이 필요한데 그 정책을 결정하기 위해서는 가치 함수가 필요한거죠. 하지만 걱정하지 말고 위에 나왔던 반복법을 다시 쓰면 됩니다. 지금까지의 바둑 인공지능은 이 방법을 이용해서 아마추어 수준의 기력을 갖출 수 있었죠.

알파고는 이를 더 발전시키기 위해 몇 가지 추가적인 방법을 적용합니다. 첫 번째는 신경망 (neural network) 기술입니다. 신경망 기술이란 인간의 뉴런 구조에 착안한 것으로 서로 직접적인 연관성이 약한 수 많은 요소들이 결합되어 만들어 내는 결과를 예측하기 위해 쓰는 기법입니다. 신경망 자체는 예전부터 많이 활용되던 기법이지만 알파고는 최신 신경망 기법을 활용하여 앞서 설명한 가치를 평가하는 가치 네트워크와 정책을 결정하는 정책 네트워크 간의 적절한 상호작용을 만들어 내어, 트리 탐색을 수행하는 단계 (depth) 를 줄이고, 몬테카를로 트리 탐색과 결합하여 탐색을 수행하는 회수 (breadth) 를 줄이는 데 성공합니다.

또한 이러한 신경망 구조를 훈련시키는 단계에서 기존에 사람이 플레이하였던 기보들을 입력하는 감독 학습 (supervised learning) 뿐 아니라 자기 자신과의 대국을 통해 만들어 지는 기보를 이용한 강화 학습 (reinforcement learning)을 통해 가치 네트워크와 정책 네트워크의 정확성을 더욱 끌어올립니다. 이렇게 함으로써 알파고는 인간을 뛰어넘는 기력을 갖추게 된거죠.

많은 기사에서 알파고 알고리즘의 핵심이 몬테카를로 인 것 처럼 보도되었지만 (그리고 실제 해당 전공분야에서 핵심적인 기술 진보가 그 부분일 지도 모르지만), 일반인 입장에서 이해할 수 있는 핵심적 기법은 신경망과 강화 학습이라고 생각됩니다. 신경망 기법은 수 많은 요소들이 조금씩 기여하여 결과를 만들어 내고 그 기여도가 수렴되는 방향이 미리 계획되지 않기 때문에 알고리즘을 설계한 사람 조차 어떤 결과가 나올지는 알 수 없습니다. 이러한 신경망이 강화 학습을 통해 최적화 되면서 인간이 만들었지만 인간이 이해할 수는 없는 인공지능이 탄생하게 되는 거죠.

그럼 이렇게 만들어 진 알파고를 인간이 이길 수 있는 방법은 없을까요. 굉장히 힘들겠지만 굳이 방법을 억지로 생각해 보자면 다음과 같습니다.

알파고가 다음 수를 계산하는 과정은 다음과 같습니다.

D. Silvar, et al. "Mastering the game of Go with deep neural networks and tree search", Nature 529, 484–489 (2016)

먼저 알파고는 가치 네트워크를 이용하여 좋은 착점을 선별합니다(a). 그리고 트리 탐색을 통해 선별한 착점을 평가합니다(b,c). 그 뒤 선택된 착점들에 대해 정책 네트워크를 이용하여 가상으로 대국을 진행해 보며 착점들을 다시 걸러냅니다(d,e). 그 결과 선택된 최종적인 착점 (붉은 원) 과 알파고의 이후 예상 진행이 (f) 입니다. 실제 판후이 2단이 대응한 곳은 흰색 네모 (붉은 원 바로 위) 였지만 후분석을 통해 알파고가 예상한 흰색 1이 더 좋은 대응이었다고 평가되었습니다.

구체적으로 알 수는 없지만 알파고는 단계적으로 선택의 수를 줄여가며 점점 더 많은 단계를 플레이 해 보는 식으로 계산 양을 줄이는 것 같습니다. 즉, 트리의 폭 (breadth) 을 줄이며 깊이 (depth) 를 늘리는 방식인 거죠. 일단 알파고가 많은 단계를 시뮬레이션 해 본다면 실수를 기대하기 힘듭니다. 따라서 좋은 착점이 깊이가 얕은 단계에서 버려지기를 기대해야 합니다.

이를 위해서는 일단 처음에 버려지는 착점이 많은 초반이 유리합니다. 또한 가치 네트워크를 이용하여 일차적인 선택을 하는 알파고의 특성상 포석에서의 가치가 높은 귀나 변은 버려지지 않을 확률이 높습니다. 따라서 초반에 반드시 중앙에 돌을 놓아야 하는 상황이 나왔을 때 알파고가 실수할 확률이 있습니다.

만일 초반에 전투가 벌어져서 그 전투가 중앙으로 번진다면 알파고가 사활이 걸린 수를 놓치고 세력을 위해 잘못된 선택을 하는 경우가 발생할 수도 있지 않을까요. 저는 바둑을 잘 모르기 때문에 그게 가능한 지는 알 수 없습니다. 어쩌면 2국 초반에 좌하변에서 알파고에게 불리하게 진행된 대국 양상이 그와 관련되어 있지는 않을까 조심스럽게 추측해 봅니다.

번호	제목	글쓴이	작성일	조회	추천
설문	소신발언으로 오히려 이미지 타격입은 것 같은 스타는?	운영자	24/08/26	-	-
공지	[공지] 입문자 및 바둑뉴비들을 위한 바둑의 룰과 규칙 [125]	*Godzney*	14.12.01	208792	664
공지	바둑 갤러리 이용 안내 [108]	운영자	05.07.29	83472	46
970113	당가문 로리력 상승하는 시간이구나	바갤러(121.141)	00:29	10	1
970112	28블럭이랑 6점 둬봤는데 별로 잘두는지 몰루겠당	75%	00:28	9	0
970111	레전드다 일본 하에하라 초단	ㅇㅇ(211.208)	00:22	37	3
970110	졸라벌었네 ㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅㅅ	meqkcl(115.143)	00:18	9	0
970109	강지훈이 양딩신	바갤러(211.204)	00:18	23	0
970108	일본 거물급 미모여기사 입단 하에아라 초단 레전드급 [2]	ㅇㅇ(211.208)	00:16	57	2
970107	위즈잉 스타만들기하다가 개같이 실패한 애들이	ㅇㅇ(115.92)	00:14	35	1
970106	중국 바둑팬들 현 상황.. [1]	뮌짜이	00:09	80	8
970105	난 정준우 자오선생 바둑을 보고 싶었을 뿐이야..	진서의커제따라잡기	00:02	32	2
970104	왜 자칭 '일반팬'들은 아직도 현실 파악을 못함?	바갤러(121.141)	08.29	44	0
970103	오늘 한큐바둑 공식 생중계: 신진서 vs 박정환	squeak	08.29	75	3
970102	중국이 부럽긴 함	샤이나리	08.29	58	2
970100	오늘자 미녀3총사 직사진 [3]	ㅇㅇ(211.208)	08.29	118	5
970099	이세돌,최철한 이거진짜임? [3]	바갤러(175.223)	08.29	112	1
970097	한국기원 방송국 게으른거 이거 문제가 진짜 심각하다. [1]	ㅇㅇ(211.234)	08.29	89	5
970096	페미라는 거창한 말 쓸것도 없다ㅋ	ㅇㅇ(106.101)	08.29	51	1
970095	한국 바둑은 철저하게 망할 수 밖에 없음 [3]	바갤러(223.39)	08.29	116	3
970093	짱깨 기원 이새끼들은 [1]	바갤러(180.64)	08.29	80	0
970092	오청원배 통합예선 대진 뜸 [4]	오오타니쇼헤이	08.29	157	2
970091	바둑 역대급 개떡수 [8]	바갤러(110.70)	08.29	150	0
970090	언더독의 반란이 재밌지	바갤러(112.186)	08.29	32	1
970089	페미국가가 아닌 나라에서 보면	바갤러(39.7)	08.29	45	5
970088	갑조는 한기가 중국에 돈 내고 중계하는 건 아니지? [1]	ㅇㅇ	08.29	59	0
970087	그럼 강지훈이 양딩신 이긴 기보는 어디에서도 못봄? [3]	바갤러(211.107)	08.29	154	6
970086	바둑tv 시청률 올릴려면 이창호가 나와야지 [1]	ㅇㅇ(104.28)	08.29	77	0
970085	안타까운 부분은 이거야 [3]	ㅇㅇ	08.29	143	7
970084	한국이 여자바둑 특혜가 좀 있긴 해 [3]	진서의커제따라잡기	08.29	128	5
970083	예언) 쿠키뉴스에 저 시에루이 기자 글 올라올 듯 ㅋㅋ [3]	ㅇㅇ(175.223)	08.29	82	5
970082	중국에서는 받아들이기 힘들 수도 [1]	ㅇㅇ	08.29	101	1
970081	신진서 홀대?는 아니지	ㅇㅇ	08.29	41	0
970080	타이젬에 재밌는거 떴네 어디에 베팅할까? ㅋㅋ [1]	ㅇㅇ(175.223)	08.29	69	0
970079	지금 한기 옹호하며 중국기사 까는 바갤러 특징 [1]	ㅇㅇ(175.223)	08.29	65	3
970078	아니 병신들이 왜 자꾸 바둑티비와 한기 입장을 옹호함? [15]	ㅇㅇ(211.234)	08.29	284	18
970076	김경동 대기자님한테 부탁해서 아구창을 날리고 싶노 [2]	ㅇㅇ(39.7)	08.29	69	1
970075	최정vs듣보잡 붙어도 시청률이 신진서제외 다른기사 세계대회 4강,8강급임 [5]	바갤러(110.35)	08.29	118	0
970074	정당비판과 내정간섭 사이. [5]	75%	08.29	91	0
970072	니네는 아겜 준결승 수순중계 안했잖아 [1]	ㅇㅇ	08.29	74	0
970071	이번에 다른대국 수순중계 안한거 바둑예산 삭감과 관련있나??? [1]	바갤러(110.35)	08.29	63	1
970070	손흥민 원정뛰러 갔는데 [2]	바갤러(106.102)	08.29	80	2
970069	오늘 바티는 좀 심하긴 했지 [1]	바갤러(112.186)	08.29	124	7
970068	나라망신 ㅇㅇ	ㅇㅇ(175.223)	08.29	40	2
970067	수순 중계도 안한거는 비판받을 만 함 [2]	ㅇㅇ	08.29	94	4
970066	진위청 한자 김우승 ㄷㄷㄷㄷㄷㄷ [1]	바갤러(39.125)	08.29	78	1
970065	(충격) 중국 씨에루이 기자 한국 바둑 방송 맹비난 ..;; [7]	ㅇㅇ(175.223)	08.29	319	18
970064	셰루이 기자 "삼성배 편파중계, 한기의 병이 가볍지 않다" [12]	ㅇㅇ	08.29	290	11
970063	와카 당연히 한국기사 줄테지만 [2]	ㅇㅇ(59.19)	08.29	74	0
970062	통합대회 여자기사 와일드카드는 이제 그만	바갤러(39.7)	08.29	46	1
970060	와카는 양딩신 or 커제가 베스트	바갤러(39.7)	08.29	57	0

최근 방문

즐겨찾기

즐겨찾기 갤러리

갤러리 이슈박스, 최근방문 갤러리

연관 갤러리

개념글 리스트

차단하기

[바둑 갤러리]

갤러리 본문 영역

알파고의 알고리즘과 약점 나홀로 리서치

추천 비추천

댓글 영역

① NFT 발행

② NFT 구매

파워링크 광고

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

페이지 이동

오른쪽 컨텐츠 영역

알림 설정

알림

디시콘 리스트

디시콘

디시콘 검색결과(0)

인기 디시콘

지갑 연결