세일즈맨 문제와 알파고 문제

이야기를 진행하기 전에 전과 같이 약간의 편견, 선입견을 없앨 필요가 있습니다.

  

  

먼저 함수에 대한 것입니다. 우리가 통상 중고등학교 때 함수를 배웠지요. 어떤 집합의 원소에다 특정 하나의 값을 부여하는 것을 함수라 합니다. 대표적으로 y=x^2이라 하면 흔히 정의역의 원소인 x에 y값을 부여하는 관계를 이야기합니다. x=0이면 y=0을 부여하고 x=2면 y=4를 부여하는 것이죠.

  

  

그런데 함수의 정의역이라는 것이 꼭 숫자일 이유는 없습니다. {남자, 여자}일 수도 있고, 함수 자체가 정의역의 원소가 될 수 있습니다. 적분이 그 대표적인 함수입니다. 즉 적분 함수를 I라 하면 정의역 원소 f(x)에 0에서 1까지 적분한 값 I(f(x))[0,1]을 부여하고, 원소 g(x)도 0에서 1까지 적분한 값 I(g(x))[0.1]을 부여하고. 그래서 함수의 개념을 확장시켜야 합니다.

  

  

좀 더 골치 아픈 함수가 여행하는 세일즈 맨에서 나오는 세일즈 맨의 경로에 거리를 부여하는 함수입니다. 오로지 5개 도시가 있다고 하죠. 그럼 거리 함수의 정의역 원소는 숫자도 아닌 함수도 아닌 경로 A==>C==>D==>B==>E==>A, A==>E==>C==>B==>D==>A 등 입니다.  이 정의역 원소인 경로에 거리값을 함수값으로 부여하여야 하거든요.

  

  

그럼 이런 상황에서는 두 가지 문제가 생깁니다.

  

  

첫째, 함수 모양을 상상할 수가 할 수도 없습니다. 그래서 함수의 최대값, 최소값이 무엇인지 추측조차도 할 수가 없다는 것이죠.

  

  

둘째, 함수 모양을 상상할 수 없기 때문에 이 함수가 부분적인 최대값, 최소값이 몇 개나 있는지 모른다는 것이죠. 이 함수가 봉우리나 골이 딱 하나인지 아니면 조그만 봉우리나 골이 수 만개가 있는 함수인지 알 수가 없다는 것이죠. 이런 봉우리나 골을 local maxium, local mimum 이라고 합니다.

  

  

이 문제를 좀 더 상세히 이야기해보죠. y=-x^2이라고 하죠. 우리는 이미 중고등학교에서 미분을 배웠기 때문에 이 함수를 미분해서 0에 놓고 풀면 이 함수가 0에서 최대값 0을 갖는다는 것을 다 알고 있습니다. 이렇게 수학적으로 푸는 것을 analytically 푼다고 합니다.

  

  

그러나 우리가 수학에 대해 전혀 모르는 원시인이라고 하죠. y=-x^2가 어떻게 생긴지도 잘 모른다는 것이죠. 그럼 이 함수가 최대가 되는 점이 어디인지 어떻게 풀까요. 그냥 무식하게 x에 숫자를 넣어봅니다. x가 취하는 값이 -무한대에서 +무한대까지 이니까 x에 천만개 값을 집어 넣어 y 값들을 일일이 다 구해보고 이걸 그림으로 찍어서 본다는 것이죠. 이렇게 하는 방법을 brutal force 식으로 푼다고 합니다. 학계에서는 당연히 이런 방법을 받아주지 않지만 기업 등 현실에서 뭘 만들어 내야 하는 경우 전혀 풀수 있는 방법이 없으면 이런 방법이라도 써야 하죠.

  

  

그러다 통상 이렇게 안 하죠. 학계에서 하는 방법은 처음에 초기값을 주고 그 근처에서 기울기가 가장 가파른 방향쪽으로 다음 값을 찾고 그 다음 값의 근처에서 기울기가 가장 가파른 방향쪽으로 그 다음값을 찾고 이런 식으로 계속 찾아 값니다. 그래서 더 이상 함수값이 올라가지 않으면 거기에 멈춥니다. 이렇게 접근해 푸는 것을 수치해석적으로 푼다고 합니다. 여기서 기울기가 가장 가파른 다음 점을 찾는 방법으로 또 수많은 이론들이 있습니다. 정의역이 2차원 이상이면 골치 아픈 문제입니다. 하여간 초기값을 잘 추측해서 잡아야 빨리 계산이 끝나겠지요.

 

  

그러나  함수가 봉우리가 하나(unimodal 이라고 합니다)가 아닌 여러 개가 있는 경우는 위 방법으로 기울기가 가장 가파른 방향으로 찾아 가면 심각한 문제입니다.  local maximum에 빠질 가능성이 매우 높습니다. 똥통에 빠지는 것이죠. 우리나라 경제랑 비슷하죠. 각 기업 나름대로 효율성을 추구해 정리해고하고 비정규직을 쓰면 로칼하게 각 기업의 최대의 이윤을 얻습니다. 그러나 사회전체적으로 소득이 낮아져 전체 봉우리에 도달하지 못하는 것이죠.

하여간  이 문제를 어떻게 해결해야 할까요? 로칼 최대값이 빠지지 않으려면 다음 값의 함수값이 이전 함수값보다 낮아져도 넘어갈 가능성을 어느 정도 줘야 합니다. 즉,

 

x(n)==>x(n+1)       even though   f(x(n+1)) < f(x(n))  with  some probability

  

   아래 그림 참조하고요.

처음에는 이렇게 점프할 가능성을 많이 줘야 하지만 알고리즘이 점점 더 진행되면 이 때는 최대값 근처에 있을 가능성이 높기 때문에 점프할 가능성을 점점 줄여줘야 합니다. 이런 알고리즘을 simulated annealing 알고리즘이라 합니다. 이 방법은 대장간에서 쇠를 확 뜨겁게 했다가 천천히 온도를 낮추면서 때리면 최종적으로 쇠 표면이 매우 부드럽게 된다는 것에 착안을 한 것입니다.

  

  

여행하는 세일즈맨 문제도 이런 방법으로 해결합니다. 그럼 문제는 어떤 경로에서 출발은 하는데 그 근처에서 시도하는 다음 경로는 어떻게 찾는가 하는 점입니다. 이 경우는 두 도시의 순서만 바꾸는 것으로 해결합니다. 즉

  

  

초기경로가 A==>C==>D==>B==>E==>A라 하면 이 초기 경로의 근처(neighborhood)에는 중간의 두 도시만 살짝 바꾸는 경로를 정의하면 됩니다.

 

즉,

A==>E==>D==>B==>C==>A,

A==>C==>B==>D==>E==>A,

A==>D==>C==>B==>E==>A

  

  

등이 A==>C==>D==>B==>E==>A의 근처(neighborhood) 경로가 됩니다. 여기서 하나를 뽑아내 거리를 재고 두 경로간의 거리를 비교하는 것이죠.

  

  

이런 방식으로 찾아가는 것이 마코프체인이라는 것이 증명되어 있습니다.

  

  

알파고에서도 비슷한 상황이 생겨납니다. 바둑판을 계산상 편리를 위해 20*20이라고 하죠. 즉 400개 착점이 있다고 생각하죠. 그럼 20수 까지 진행되고 알바고가 21번째 착점을 할 시점입니다. 그럼 알파고가 착점 가능한 점은 모두 400-20해서 380군데나 존재합니다. 이때 알파가고 생각할 수 있는 방법은 2가지입니다. 380군데 중에서

  

  

첫째는 남들이 많이 둔 곳에 둔다.

  

  

둘째는 가장 이길 확률이 높은 곳에 둔다.

  

  

첫 번째는 알파고에 저장되어 있는 바둑판 디비가 충분하면 어느 정도 무난한 수가 되겠습니다. 그러나 하수들 바둑으로 디비를 만들었다면 매우 심각한 문제가 되겠고요. 어느 정도 고수들 바둑으로만 알파고 바둑 비디를 만들었다면 굉장히 유용한 전략이 될 수 있습니다.

  

  

왜 그러냐 하면 일단 정석, 패, 단수, 축 등 바둑 룰에 대해 알파고가 신경 쓸 필요가 없습니다. 초반에 두는 수는 대부분 정석이기 때문에 두 번째 승률로 계산하는 것은 별 의미도 없고, 대부분 프로들은 정석시 거의 일정시 수순으로 둡니다. 따라서 거기에 맞춰 가장 많이 두는 수를 따라 두면 됩니다. 또 패라면 다시 바로 따내는 경우가 없기 때문에 다른 사람들이 둘 가능성은 0%입니다. 또 단수인 경우 축이 아니면 살려는 것이 거의 100%에 가깝게 때문에 다른 사람들이 둘 가능성이 매우 높게 나와서 자동적으로 늘리는 수를 선택한다는 것이죠.

  

  

따라서 다른 사람이 거의 두지 않는 수는 일단 배제하고, 또 거의 절대적으로 두는 수, 즉 둘 확률이 100%에 가까운 경우는 다음 착점으로 바로 둔다는 것이죠.

  

  

그러나 무난하게 두어서는 프로기사들에게 이기는 경우는 많지 않겠죠.

  

  

그래서 앞에서 배제하는 경우를 제외하고는 수 읽기를 해서 이길 확률을 계산해서 둬야 합니다. 여기서 좀 심각한 문제가 생깁니다. 다음 착수에서 A라는 곳에 두면 이길 확률이 90%가 나온다고 해서 여기에 둬서는 안된다는 것이죠.

왜냐하면 몇 수가 지나서 이길 확률이 20%로 확 떨어질 수 있기 때문입니다. 지난번 이세돌 4국에서 78수와 같은 묘수가 등장하면 이길 확률이 확 떨어진다는 것이죠. 이런 경우가 자주 생겨날 수 있을가요? 충분히 생깁니다. 대부분 사람들이 묘수를 모르면 알파고가 이기고 일부 사람만이 묘수를 알면 절대적으로 진다고 하면 이런 경우가 생긴다는 것이죠. 그래서 일부 사람이라도 묘수를 알 경우를 고려해서 몇 수까지 수 읽기를 해야 합니다. 이 몇 수 까지 수 읽기를 이쪽에서는 selection 이라고 하는 모양입니다.

  

  

이것만 문제가 생기는 것이 아닙니다. 알파고는 다음 착수시 이길 확률을 계산해 내는데 문제는 이 확률값이 믿을만한가입니다. 현재 21수에 A라는 곳에 착점했을 때 바둑판 디비에서 이렇게 진행된 바둑수가 5판 정도 밖에 없다면 여기서 나온 이길 확률은 통계적으로 믿을 만 한 것이 아닙니다. 한 50판 정도 되어서 여기서 계산된 이길 확률은 어느 정도 신뢰할 수 있지만요.

  

  

여기서 알파고의 문제, 즉 바둑 프로그램의 문제가 생깁니다. 이런 믿을 만한 승률 계산이 되려면 어마어마한 바둑판 디비가 있어야 한다는 것이죠. 바둑에 이런 이야기가 있지요. 똑같이 진행되는 바둑판은 없다고요. 이런 상황에서 알파고는 어떻게 해결할가요.

  

  

제 판단에는 초기에는 고수, 하수 가릴 것없이 바둑판 디비를 생성합니다. 또 어느 정도 바둑을 둘 수 있는 상태가 되면 알파고가 스스로 사람들과 바둑을 둡니다. 또 상당한 수준이 되면 자기들끼리 바둑판을 둡니다.

  

  

이렇게 해도 충분하지 않다는 것이죠. 바둑 수 읽기를 하는데 몇 수 진행해보니 바둑 디비에 전혀 없는 경우나 아니면 몇 판이 없는 경우가 튀어 나올 수가 있다는 것이죠. 그럼 여기서 수 읽기를 멈추고 그 다음 수 부터는 몬테 카를로 방법으로 무작위로 수순을 뽑아 진행해 본다는 것이죠. 언제까지? 바둑 끝까지는 아닌 것 같고, 어느 정도 믿을 만한 승률 계산이 나오는 바둑 모양을 발견할 때까지 뽑아본다는 것입니다. 이게 expansion 이라는 단계로 보입니다.

  

  

윗그림은 seri에서 나온 보고서에 있는 그림인데 selection과 expansion에 대해 전혀 설명을 못해주고 있네요. 하여간 제가 여기 저기 보고 이해한 바로는 위의 설명한 부분입니다.

  

  

이런식으로 각 수 진행에 따라 승률을 구할 수가 있을 겁니다. 여기서 각 진행 방법, 즉 여행하는 세일즈 문제처럼 목적함수(세일즈 맨 문제에서는 각 경로에서 거리를 구하죠)을 정의하여야 하죠. 이 목적함수를 mini-max을 택해 수 읽기 마지막 착점에서 거꾸로 올라온다고 합니다. 이건 seri 보고서에 보면 알 수 있습니다. 다음 그림입니다. 

  

  

하여간 여기까지 보면 알파고는 MCMC를 사용한 것이 아니고 그냥 가능한 수순에서 랜덤하게 뽑아내는 것 같고요, 앞의 이야기한 simulated annealing 알고리즘도 사용한 것 같지 않습니다. 뭔가 적용하기에는 문제가 있으니까 안 했겠죠. 그 분야 전문가들만 모였는데 이런 알고리즘을 모를리는 없겠죠.

  

  

이와 같이 하는 것을 몬테 카를로 트리 서치라고 하는 것 같습니다.

  

  

문제는 CNN이라는 알고리즘인데 이건 공부를 더 해야 할 것 같고요. 딱 현실에서 부딪치는 예를 들어서 설명한 논문을 아직 뱔견을 못해서 애매모호 합니다. 그러나 한 가지 느끼는 점은 이 알고리즘이 여러 분야에서 매우 가능성이 높아 보이는 알고리즘 같습니다.

예를 들어 단수의 경우 컴퓨터에서 어떻게 알가요? 앞에서 이야기 했지만 알파고 바둑 디비가 엄청 많으면 단수라는 것을 알파고가 인식할 필요는 없습니다. 축이 아니면 대부분 늘어야 하고, 축이면 늘이는 수는 절대로 안되고. 그래서 첫 번째 가장 많이 나오는 수나 나와서는 안되는 수를 따지는 알고리즘을 적용하면 됩니다. 맨 왼쪽이 단수 모양입니다. 그 옆이 이것을 숫자로 코딩한 값입니다. 상대방 흑은 -1, 자기 백돌은 1, 공배는 0입니다.

 

				0	-1	0			0	8	0			0	-8	0
				-1	1	0			8	0	8			-8	0	0
				0	-1	0			0	8	0			0	-8	0

  

  

만약 일반 프로그래머에게 단수인지 아닌지 판단하려고 하면 다음과 같이 코딩할 겁니다. 현재 흰돌이 (20, 20)에 있다고 하면 (19,20), (20,21), (20, 19)에 흑돌이 있다면 단수, 하나라도 아니면 단수가 아님 이런 식으로 코딩할 겁니다. 그러나 이렇게 하지 않고 CNN 방식을 도입하면 두 번째 코딩한 3*3 행렬에 세 번째 있는 3*3 크기의 필터링을 적용합니다. 즉 convolution을 적용합니다. 계산은 간단합니다. 네 번째 행렬이 두 행렬을 곱하기 한 값입니다. 행력의 원소끼리 서로 곱해서 더하면 됩니다. 즉

    

 

(0*0+(-1)*8+0*0+(-1)*8+1*0+0*8+(-1)*8+0*0)=-24

  

  

즉 음수로 엄청나게 큰 값이 나오면 단수로 판단하면 된다는 것이죠. 이걸 바둑판 20*20에 모두 적용한다는 것이죠. 시간이 제법 걸리는 것 같지만 프로세스가 400개 있으면 하나의 프로세스가 한 점식 맡아 계산하면 바로 끝납니다.

  

  

알파고가 이런 형태로 부분적인 상태를 판단해서 다음 수를 선택하는데 있어, 즉, seletion 단계나 expansion 단계에 적용하여 계산 수를 많이 줄였다고 합니다. 구체적인 것은 알파고 논문을 보지 않아서 잘 모르겠고요. 사람들 소개한 글에서는 패딩이라는 것이 나오는 데 이런 것 핵심적인 사안이 아닙니다. 바둑판 변에 있는 점은 3*3나 5*5 필터를 바로 적용할 수 없기 때문에 가상의 테두리를 만든 것에 불과합니다. 이건 스펙트럴 이론의 기초적인 것이고요.

  

  

그래서 알파고 문제에서는 충분한 바둑디비가 없다는 점이고요. 특히 승률 계산에서요. 하여간 알파고는 처음에 바둑디비를 어떻게 모았을가요. 나온 이야기를 보니 한국에서 운영하는 바둑서버가 있는 모양입니다. 물론 바둑끝까지 진행된 기보가 이미지 형태로 있겠죠. 이걸로 알파고 처음 단계 바둑비디를 만드는 것은 매우 쉬운 작업입니다. 기보에 검은 돌에 흰 숫자가 있고, 흰돌에 검은 숫자가 있죠.

  

  

이 이미지는 규격이 똑같고 숫자도 규격이 똑 같기 때문이 이런 종류의 숫자 판독은 이쪽에서는 초보적인 일입니다. 한국 바둑 서버에 있는 기보들 전부를 알파고 바둑 디비로 만드는데는 아마 며칠 걸리지도 않았을 겁니다.