자유토론 AlphaGo, 바둑, 수학과 Al 바둑...

자유토론 AlphaGo, 바둑, 수학과 Al


바둑은 내가 어릴 때 가장 좋아하던 게임이다. 더 중요한 것은 바둑과 수학은 많은 특별한 관계가 있다는 것이다. 이 절에서는 바둑과 수학의 관계 및 최근 이슈인 인공지능에 대해 이야기해보려고 한다. - P315

컴퓨터를 이용하여 19×19의 바둑판의 상태를 모두 열거하고 각각의 상태가 합리적인지 판단하는 것은 불가능해 보이지만, 이미 2006년에 누군가가 실험을 했다. 무작위로 하나의 바둑판 상태를 생성하고 ‘합리적인‘ 변화의 확률을 고찰하면, 그 결과는 약 1.2%이다. - P316

공식적인 계산은 2015년 3월에 시작하여 같은 해 12월에 이르러서야 끝났으며, 이로 인해 생성된 중간 파일은 30PB(1PB=10⁶GB)라는 어마어마한 규모가 되었다. 크고 작은 바둑판의 ‘합법적인‘ 국면이모든 국면에서 차지하는 비율의 변화를 살펴보면 다음과 같이 흥미롭다. - P317

그리고 그때 바둑에 관한 최첨단 AI프로그램이 어떤 수준인지에 대해 관심을 가지기 시작했는데, 그 결과는 역시 나를 실망시켰다. (중략).
특히 이 기간 중국의 중산대학교 화학과 진지행 교수는 은퇴 후 바둑 관련 AI 프로그램 개발에 전념했다. 개발한 ‘수담‘ 프로그램으로1995~1998년 바둑 AI 대회에서 7연승을 했다. - P318

(전략). 끝내기 단계는겨우 이렇게 계산할 수 있을지 모르지만, 바둑판의 처음 판이 텅 비었을 때 사람들은 한 국면에 대한 정적 평가 방법을 전혀 찾지 못했다. 인간 고수들 사이에서도 국면에 대한 평가는 때로는 엇갈리는데더구나 컴퓨터를 사용한다면 곤란하기 짝이 없다. - P319

하지만 바둑 AI 프로그래밍은 2006년 한 차례 도약했고, 누군가가새로운 알고리즘을 바둑에 적용한 것이 몬테카를로 알고리즘 MonteCarlo Algorithms (MC 알고리즘)이다. - P319

그렇다면 이런 알고리즘은 바둑에 어떻게 쓰일까. 앞서 언급한 바둑 AI 프로그래밍의 한 가지 난점인 국면 평가에 대한 아이디어가 나왔는데 컴퓨터가 하나의 국면에서 계발식 알고리즘으로 최적의 점을찾는 것이 아니라 양쪽이 ‘임의로 바둑을 두고 마지막에 가서 누가 지는지 다시 한 번 보는 것이다. - P321

몬테카를로 알고리즘 도입 이후 모든 계발식 알고리즘 프로그램이 역사 속으로 밀려나면서 바둑 AI 프로그램의 실력은 급상승하기 시작했다.  - P322

당신은 끝내기 국면에서 바둑판의 낙점이 크게 줄어들어 바둑프로그램이 더 잘 처리될 것이라고 생각할지도 모른다. 하지만 사실은 그렇지 않다. 지금까지 임의의 바둑끝내기 국면을 완벽하게 해결할 수 있는 범용 AI 프로그램은 전무하다. 어쨌든 2012년 바둑 프로그램은 설계 개발에 큰 돌파구를 만들었는데, 이때는 몬테카를로 알고리즘이 지배적이던 시기이다. - P323

전략 네트워크는 알파고가 주로 고려해야 할 다음 수의 위치를 빠르게 선별하는 데 도움을 줄 수 있다. ‘전략 네트워크‘의 구축 방법은 인간의 생각을 모방하여 역사적으로 모든 인류가 학습해 온, 특히 고수가 놓았던 기보를 끊임없이 입력하는 것이다. - P324

알파고가 바둑을 두도록 지도하는 사람은 없지만 알파고가 구사하는 속도는 매우 빠른 편이다. 위의 과정은 말하기는 쉽지만 두기는힘들다. 왜냐하면 기보에 따라 바둑을 놓는 목표는 단순히 인간을 모방하는 것이 아니기 때문이다. 바둑판에서 옛사람과 똑같은 판을 만났다고 해도, 다음 9단 고수가 놓은 수가 최고의 수가 틀림없다고 말하기 힘들다. - P325

(전략). 이제 알파고는 바둑판의 한 국면에 따라 4~5개의 가장 가능성 있는 착법을 신속하게 선별할 수 있는데, 어떻게 이러한 착법의 좋고 나쁨을 평가할 수 있을까? 이것은 ‘가치 네트워크 Value Network‘를 사용한 결과이다. - P325

알파고가 이렇게 강한데 인간이 그것을 무너뜨릴 수 있을까? 다음은 내가 알파고 작업 원리에 대한 이해에 근거하여 알파고에 대응할수 있는 세 가지 안을 생각해 낸 것으로, 타당성에 따라 낮은 것에서높은 것으로 순위를 매겨보았다.
첫 번째는 축을 만들고 끌어들이는 것이다. - P327

두 번째 수는 바둑을 모방하는 것이다. 컴퓨터와 바둑을 두고 이바둑 경기를 모방하는 것은 좋은 것이다. (중략). 알파고가 계산하도록 하고 당신은 산출한 결과를 쓰면 된다. - P328

세 번째 수는 속임수이다. 소위 ‘속임수‘라는 것은 이런 수이다. 당신의 상대를 한 수씩 모두 마치 바둑의 이치에 맞는 것처럼 당당하게 대적하다가 결국 당신이 배치한 함정에 빠지게 만드는 것이다. 그러나 이런 바둑은 만약 올바른 대응 수단을 안다면 실제로는 나쁜 바둑이다. - P329

요약하자면 알파고에 대응하는 두 가지 요점은 각각 그것의 두 대뇌를 공격하는 것이다.

1. 전반적인 국면에서, 다음 수의 최선의 선택을 전체 국면에서 판단하도록 하는 것은 ‘전략 네트워크‘를 공격하는 것이다.
2. 아주 깊이 있고 정확한 계산이 필요한 국지적 국면을 조성한다.
예를 들면, 축과 속임수를 써서 가치 네트워크를 공격한다. - P330

다각형을 품고 있는 점의 개수 구하기_해피엔딩문제


실험을 하나 해보자. 종이 한 장을 펴고 그 위에 5개의 점을 찍자. 이 중 어느 세 점도 한 직선 위에 있지 않다. 그리고 5개의 점이 어떻게 놓여 있든지 이 중에서 4개의 점을 잇는다. 목표는 바로 볼록 사각형 하나를 만드는 것이다. - P64

일반적으로 평면상 볼록 각형을 만들 수 있는 최소한의 점의 개수를 묻는 문제를 ‘해피엔딩문제‘라고 부른다.
이 문제와 ‘해피엔딩‘이 무슨 상관이 있을까? 여기에는 아름다운 이야기가 있다. - P65

1933년 헝가리 부다페스트에 수학을 사랑하는 젊은이들이 있었고 그들은 자주 모여 수학문제를 논의했다. 그중에서도 활발한 활동을 했던 세 사람이 있었다. 당시 23세 여성 클라인 Klein, 그녀보다 한 살적은 남성 세케레시 Szekeres, 20세 에어디쉬 Erdos였다.
어느 날, 클라인은 두 친구에게 이 문제를 선보였다. 그들이 이 문제를 증명하기 원했고 몇 개의 예를－평면상의 5개의 점이 있을 때 그 중 4개의 점은 반드시 볼록 사각형이 되는지－제시했다. (중략).
이것을 ‘에어디쉬－세케레시 정리‘라고 부른다. - P65

(전략). 2005년 두 사람은 한 시간 차이로 잇달아 생을 마감한다. 그래서 그들의 인생은 절대적으로 해피엔딩이라고 불릴 만하다.
이 문제를 ‘해피엔딩‘이라고 불렀던 에어디쉬에 대해서 말하려고한다. 그는 수학계에서 매우 저명한 학자였다. (후략). - P66

에어디쉬와 세케레시는 볼록 오각형은 9개의 점이 필요하다는 것을 증명했다. 삼각형은 점 3개가 필요하다는 것이 자명하고 볼록 사각형은 5개의 점이 필요하다. - P67

n=4인 경우에 어떤 식으로 증명하는지 들여다보자.
다음 그림에서 평면 위에 5개의 점이 있다고 하자. 여기서 어느 세 점도 일직선 위에 있지 않다. 그중 세 점을 택해 삼각형을 만들자. 남은 2개의 점에 A, B라고 이름을 붙이고 두 점을 연결하여 직선 AB를그린다. 만약 점 A, B가 모두 삼각형 내부에 있다면 직선 AB는 반드시 삼각형의 두 변과 만나고 삼각형을 2개의 부분으로 나눈다. - P67

n=4인 경우가 이렇게 간단하다고 이 문제를 얕보지 마라. 임의의 볼록 각형에 대한 증명은 상당히 곤란하다. 에어디쉬와 세케레시의 증명에 근거한 볼록 오각형일 때, 최솟값f (5)=9는 1935년 마카이E. Makal에 의해 증명되었다. - P69

가장 최근의 성과는 앤드류 수커 교수가 2016년에 증명한 것으로 알려져 있다. 이밖에 의미 있는 것은 해피엔딩문제는 ‘램지이론Ramsey theory‘의 첫 번째 중요한 응용이라는 것이다. - P69

해피엔딩문제는 ‘공심해피엔딩문제‘로 확장된다. 이것은 해피엔딩문제보다 더 많은 조건이 필요한데 볼록다각형을 만들 때 다른점을 내부에 포함하지 않는 것이다. (중략).
당신은 공심해피엔딩문제에서 많은 점을 찍기만 하면 된다고 생각할지도 모른다. 그러나 1983년에 조제프 호턴Joseph Horton은 점의 수가 충분히 많을 때 공심볼록칠각형을 찾을 수 없음을 증명했다. - P70

Let‘s play with MATH together

1. 평면 위에 17개의 점이 있을 때 (오목, 볼록 상관없이) 얼마나 많은 육각형을 만들 수 있을지 생각해보자.

2. 평면 위에 1+2^(n-2)개의 점이 있다면 몇 개의 각형을 만들 수 있을까? - P70

‘수학병‘에 걸리게 하는 문제_콜라츠추측


만약 당신이 제목 ‘콜라츠추측collatz conjecture‘을 보고 감이 전혀 오지 않는다면, 힌트를 몇 개 더 주겠다. 3+1 추측, 우박추측, 카쿠타니Kakutani 추측. 하세Hasse 추측, 울람 Ulam 추측과 시라쿠스Syracuse추측. 어떤가, 떠오르는 것이 있는가? - P71

이 추측은 1930년대 초, 그 당시 독일의 대학생이었던 콜라츠에 의해 제기되었다. 1960년대에 일본 수학자 카쿠타니가 이 문제를 연구하면서 중국으로 전해졌고 중국에서는 이 추측을 카쿠타니 추측이라고 불렀다. - P73

1만 이내의 항로 중에서 가장 긴 것은 6171호, 길이는 261이다. 1억이내에서는 가장 긴 항로가 63,728,127이고 947회 공유된다. 이미 사람들은 컴퓨터를 이용하여 5×10‘에 이르렀고 이 범위 내에서 반례는 찾지 못했다. 그러나 많은 문제에서처럼 테스트를 많이 한다고 해서 문제의 증명에 도움이 되는 것은 아니다. - P75

중국계 호주인 수학자 테렌스 타오Terence Tao는 2011년에 콜라츠추측을 연구하며 얻은 결과와 감상을 블로그에 남겼다. 비록 블로그에올린 글이지만 내용은 매우 심오하다. 그중 주된 내용과 요점을 당신에게 소개하고자 한다. - P76

앤드류 와일즈는 이 점을 이해한 후에 몇 가지 사고 과정을 통해서 타니야마 시무라추측‘을 정복할 수 있다고 생각했다. 그래서 그는 바로 이 방향으로 전진했고 결국은 타니야마 시무라추측을 통해페르마 대정리를 이끌어냈다. 이것은 특정 수학난제에 대해서 심하게 연연해하거나 얽매이는 것은 바람직하지 않다는 것을 말해주는것 같다. - P77

다음으로 테렌스 타오도 콜라츠추측을 수학자들이 주력해야 하는 문제가 아니라고 여겼는데 아직은 이론적 도구가 잘 정비되지 않았다고 생각해서일 것이다. 그는 출중한 수학자는 마땅히 그런 수학도구를 능가하는 문제를 고려해야 한다고 여겼다. - P77

그는 우선 ‘약한 콜라츠추측의 명제 하나를 꺼냈다. 콜라츠연산을 거친 어떤 자연수가 있다고 가정하자. 그러면 이 자연수는 1, 2, 4세 개중의 하나이다. 이것을 ‘약한 콜라츠추측‘이라고 부르는 이유는 무엇일까? 이유는 그것을 증명할 때 콜라츠추측을 증명할 수 없고 발산할 가능성이 더 크기 때문이다. 그러나 콜라츠추측을 증명한다는 것은 바로 그것을 증명한 것이나 다름없다. 그래서 비교적 약해 보인다. - P79

당연히 테렌스 타오도 이 약한 콜라츠추측의 명제를 증명할 수 없다고 했지만 이 명제에 대해 분석했다. 만약 이 명제가 성립하지 않는다면 약한 콜라츠추측은 다른 순환이 있다는 반례가 된다는 것이다. 그러면 이 순환의 길이는 적어도 105000이다. 우리는 이미 5×10¹⁸이내의 자연수에 대해서 모두 콜라츠추측을 검증했다. - P80

이 문제와 관련된 결론은 1972년 존 콘웨이 (3명의 케이크 문제에서거론되었던 수학자)가 증명했다. 콘웨이는 일반화된 콜라츠추측은 ‘결정할 수 없는 것 undecidable‘으로 ‘어떤 정수를 입력하면 유한시간 안에 일반화된 콜라츠연산을 통과한 정수가 순환 상태로 진입가능한지를알려주는 이런 컴퓨터 프로그램은 없다‘고 했다. - P83

마지막으로 다시 콜라츠 나무로 거슬러 올라가보자. 2011년 콜라츠의 한 학생은 콜라츠추측을 증명했다. 그런데 이후 그의 증명에는 결함이 하나 있었는데 증명에 이용된 나무가 수많은 자연수를 커버한다는 증명이 없다는 것이다. - P83

나는 ‘거의‘ 알아차렸다.


수학에서 ‘거의‘에 대한 표현을 이야기하려고 한다. 수학명제에서 ‘거의 almost‘를 사용한 것을 본 적이 있는가? ‘실수는 거의 모두 무리수이다.‘ 이 명제를 어디선가 들어본 것 같지 않은가? 하지만 좀 이상하게 들리는 건 사실이다. 왠지 수학 같지가 않다. 유리수가 그렇게 많은데 무엇을 근거로 ‘실수는 거의 모두 무리수‘라고 할까?  - P217

분명한 것은 ‘거의‘는 함부로 사용되지 않았다. 수학에서 ‘거의‘는 엄격한 정의가 있다. - P218

‘측도‘ 또한 수학에서 꽤 재미있는 개념이다. 정확한 정의는 좀 추상적이지만 당신은 글자만 보고도 대강의 뜻을 짐작할 수 있을 것이다. 소위 측도가 0이라고 하면 측량의 크기가 0이라는 것이다. 앞의것을 예로 들면, 우리는 유리수 집합의 크기를 잴 수 있고 그것을 실수집합과 비교하면 크기는 0이다. - P219

‘거의‘를 포함한 명제로 다시 돌아가 보자. 예로, 그래프이론에서두 개의 흥미로운 명제가 있는데 하나는 거의 모든 유한 그래프는비대칭이다‘이고 또 다른 하나는 ‘거의 모든 무한 그래프는 대칭이다‘라는 것이다. - P219

당연히 여기서 ‘대칭‘은 기하에서 말하는 그 대칭이 아니다. 임의로 그린 그래프가 마침 대칭이 될 확률은 0이다. 그래프 이론에서 대칭은 ‘자기동형사상‘을 가리키는데, 즉 그래프의 점이 자신으로 대응되는 구조로 각 점은 모두 자신의 어떤 점으로 대응될 수 있다. - P220

만약 하나의 그래프에 유한 개의 많은 점이 있고 점의 수가 계속많아지면 대칭의 확률은 0으로 가까워진다. 그러나 만약 한 그래프에 무수히 많은 점을 나타낼 수 있다면 그것은 거의 100% 대칭이다.  - P220

마지막으로 예상을 완전히 뒤엎는 것은 ‘칸토어집합 Cantor Sets‘이라고 불리는 것이다. 앞에서 말한 ‘실수는 거의 모두 무리수이다.‘ 이명제에서 당신은 유리수의 수가 매우 적기 때문이라고 여길 수 있다.
유리수 집합은 가산집합이고 그것의 측도는 00이 맞다. - P221

또한 믿기 어려운 결과를 확인할 수 있는데 칸토어집합을 기하관점에서 설명하면 길이는 0에 한없이 가까워지고 측도는 0이다. 그러나 집합의 크기로 설명하면 그것은 무리수 혹은 실수와 같은 정도로수직선 위의 수만큼 많다는 것이다. 이것이 사람들에게 무한히 작다는 느낌을 주지만 동시에 수직선 위의 모든 수를 포함할 만큼 매우크기도 하니 보통 사람으로서는 생각하기 힘든 사실이다. - P223

이밖에도 칸토어 집합의 기수와 실수집합은 같기 때문에 일대일대응 함수를 하나 만들 수 있다. 이 함수를 ‘칸토어함수‘라고 한다. (중략).
칸토어함수는 전통적인 의미의 연속 함수라는 것이 증명되었고 각 점에서 도함수는 ‘거의‘ 이기 때문에 이 함수의 이미지가 수평선이어야 한다고 생각할 것이다. 그러나 이 함수는 실제로 증가할 수 있다. - P224

 칸토어함수는 ‘균등연속 uniform continuity‘이지만 ‘절대 연속absolutelycontinuity‘은 아니다. - P224