알고리즘 분석을 통해 본 알파고의 약점

ㅇ · 2016.03.11 19:52:23

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

바둑이나 체스와 같은 보드게임을 포함한 모든 게임에서 필요한 모든 정보를 가지고 있다고 가정할 때, 현재의 상태를 보면 누가 이길지에 대한 확률을 계산할 수 있습니다. 바둑에서 현재 돌이 놓인 모양을 보고 사람들이 대충 누가 유리하겠구나 판단하는 것이 이 과정에 해당합니다. 이것을 가치 함수 (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국 초반에 좌하변에서 알파고에게 불리하게 진행된 대국 양상이 그와 관련되어 있지는 않을까 조심스럽게 추측해 봅니다.

출처 : http://ncity.egloos.com/7138922

번호	제목	글쓴이	작성일	조회	추천
설문	외모와 달리 술 일절 못 마셔 가장 의외인 스타는?	운영자	24/07/01	-	-
85204	다필요없고 이제와서 정센승리 하는거 존나 꼴사나움 [1]	ㅇㅇ(39.7)	16.03.11	75	2
85203	포석단계 떡수는 떡수 맞음 그건 ㄹㅇ임 [3]	ㅇㅇ(27.124)	16.03.11	148	1
85202	알파고이기려면 초반에 승부봐야한다. [1]	스미조메	16.03.11	101	0
85201	횽님들 바둑 게임어플 추천좀	친알파(1.232)	16.03.11	36	0
85200	바알못인데 돌을 던진다는게 뭐임? [6]	ㅇㅇ(223.62)	16.03.11	109	0
85199	알파고 계산에 약점이 가능할까..? [8]	ㅇㅇ(175.114)	16.03.11	112	0
85198	근데 인공지능뭔가 이상헌데? 약점있다고	ㅇㅇ(223.62)	16.03.11	36	0
85197	★★★급수상관없이 저렴한 당일9단(무료관전가능)★★★	알파고(222.96)	16.03.11	48	0
85196	이세돌은 드디어 존경하는 바둑기사 생겼겠네 ㅋㅋ [7]	ㅇㅇ(110.45)	16.03.11	2011	25
85195	바둑이나 많이둬라 볻놀이야 형은 인간대 인간으로하는리그오브레전드하러간다	ㅁㄹ(125.143)	16.03.11	34	0
85194	이세돌 심정은 맞짱까기로 한놈이 이윤석인줄 알았는데 효도르전성기인걸로 [1]	ㅇㅇ(124.80)	16.03.11	60	0
85193	바둑팬이면 이세돌이 어떻게 하면 이길 수 있을지 고민하는게 먼저 아닌가 [1]	ㅇㅇ(121.130)	16.03.11	58	0
85192	세계는 머지않아 알파고님이 지배할 것이다. [3]	ㅇㅇ(122.36)	16.03.11	97	0
85191	이기는 바둑이 강한 바둑이다.-알파 고	신의경지(1.254)	16.03.11	56	2
85190	초반 떡수 병신인건 인정하는데 [1]	ㅇㅇ(175.192)	16.03.11	68	1
85189	알파고 센세를 차라리 해설위원으로 초빙하지 [1]	ㅇㅇ(211.36)	16.03.11	55	2
85187	알파고 수 문의 [3]	협잡제거	16.03.11	118	1
85186	넷마블 바둑 호선 할사람 ㅇ.ㅇ	꽃놀이✿	16.03.11	39	0
85184	프로10단 알사범.."세돌아 이제 자신감이 좀 생기니?"	ㅁㅁ(61.109)	16.03.11	84	1
85183	한국도 바둑 계보 끊긴거 아니냐 [1]	ㅇㅇ(112.171)	16.03.11	131	1
85182	갓파고 10단 VS 좆세돌 9단	ㅇㅇ(222.112)	16.03.11	50	0
85181	바둑잘두는놈이 알파고 이기는게 아니라 알파고를 약점을 알아내는놈이 이길득 [5]	ㅇㅇ(124.80)	16.03.11	146	3
85180	굮뽕시키들 커제한테 열폭쩌네 ㅋㅋㅋ	ㅇㅇ(112.171)	16.03.11	40	0
85179	이세돌 박정환 더럽게 못두네	ㅇㅇ(66.249)	16.03.11	69	2
85177	이세돌이 이기면 구글도 좀 빡치겠다 [2]	ㅇㅇ(211.216)	16.03.11	132	0
85176	'알파고 떡수 ㅋㅋ' >>알파고입장에선 가장 확률높은 수 [15]	ㅁㄹ(125.143)	16.03.11	191	1
85175	여기가 알파고 갤러리인가요? [1]	ㅁㄴㅇㄹ(175.223)	16.03.11	39	0
85174	알파고 덕분에 이건 바둑판의 명언으로 영원히 남을 듯 [1]	ㅁㅁ(61.109)	16.03.11	145	0
85172	근데 처음 바둑돌 둘때 점찍힌쪽에 두는이유가 뭐임? [7]	ㅇㅇ(223.33)	16.03.11	155	0
85170	ㄹㅇ 알파고 상대로 치수고치기 하면 어떻게 될까 궁금하긴 하다	ㅇㅇ(125.141)	16.03.11	35	0
85169	내일이 중요하다 진리의 패패승승승	ㅇㅇ(211.36)	16.03.11	25	0
85168	애초에 이길 수 없는 싸움이라고 하는데 좀 짜증나네 [10]	ㅇㅇ(121.130)	16.03.11	181	1
85167	이세돌 왈,난 2국 경기 내내 털렸었다. [1]	신의경지(1.254)	16.03.11	165	0
85166	바둑때려치우고 장기나 두자 [2]	스미조메	16.03.11	108	0
85165	체스는 말이라도 멋있지 [1]	리얼(223.62)	16.03.11	76	0
85164	알파고만 9단으로 두고 나머지 인간들은 밑으로 한단씩 까는건 어떰? [2]	ㅇㅇ(59.24)	16.03.11	73	2
85163	알파고 인 만큼 실수라고하기는 힘둘갰지	꽃놀이✿	16.03.11	19	0
85162	지금 분위기 바껴서 이세돌이 한판이라도 이기면 구글로선 상처아니냐 [3]	ㅇㅇ(39.7)	16.03.11	119	2
85161	이세돌 응원하자 외게인하고 싸우는거같다	ㅇㅇ(211.36)	16.03.11	34	0
85160	판후이와의 대국당시 알파고가 이미 이세돌을 넘었을 가능성이 높다. [4]	하마코3	16.03.11	225	1
85159	나도 프로 입단이나 할까? [1]	ㅇㅇ(66.249)	16.03.11	57	0
85158	내일 이기면 일요일은 시청륭 30프로 네이버 100만 각 아니냐	바세돌(211.36)	16.03.11	40	0
85157	알파고 실수같은데요 = 알파고 승	ㅇㅇ(175.211)	16.03.11	26	1
85155	알파고 해설은 구글밖에 못함	ㅇㅇ(211.36)	16.03.11	46	2
85154	근데 알파고한테 이세돌이 2~3점정도 깐다고 치자	ㅇㅇ(143.248)	16.03.11	39	0
85153	1국같은경우는 이세돌 패착이 많았음	꽃놀이✿	16.03.11	34	0
85152	알파고 원리 이해못한 놈은 이 동영상 한번 봐라 [1]	보고(119.192)	16.03.11	108	0
85151	강인공지능 앞으로 몇년안에 나올거같음? [1]	ㅇㅇ(125.133)	16.03.11	57	0
85150	드래곤볼에서 완전체 셀에 대항해 나온게	ㅇㅇ(211.36)	16.03.11	40	0
85149	양놈들의 바둑 = 생명게임(라이프게임) [1]	ㅇㄹㅇㄹ(211.204)	16.03.11	75	0

최근 방문

즐겨찾기

즐겨찾기 갤러리

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

연관 갤러리

개념글 리스트

차단하기

[바둑 갤러리]

갤러리 본문 영역

게시물을 간편하게 NFT로 만들어 보세요!

NFT 발행 방법

NFT 발행

비회원 글삭제,수정

추천 비추천

댓글 영역

① NFT 발행

② NFT 구매

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

페이지 이동

오른쪽 컨텐츠 영역

알림 설정

알림

디시콘 리스트

디시콘

디시콘 검색결과(0)

인기 디시콘

지갑 연결