[=] 바둑이란 무엇일까?

*다음은 바둑 사이트 타이젬(tygem.com)에 ksyalf 님이 올리신 글입니다. (바둑논단 3629)

http://www.tygem.com/column/forum/view.asp?gubun=1&seq=6739&pagec=102&find=&findword=

바둑이란 무엇일까?

 '바둑이란 무엇일까'라는 질문에 대해서는 많은 사람들이 말해 왔습니다. 바둑은 놀이고, 예술이며 스포츠고 연구의 대상이고 잡기이고 문화라고 이야기를 합니다. 사실 어떤 것이든 시간이 지나면 많은 것이 덧붙여져 유기체같이 되고 딱 경계를 잘라 정의하기가 힘든 면이 있습니다. 그래도 굳이 정의를 하려고 한다면 대개는 가장 중요하고 핵심적인 측면을 찾기 마련입니다. 그렇다면 바둑에서는 그 핵심적인 측면이 무엇일까요?

서봉수 명인은 “바둑이란 나무판에 돌을 놓는 것이다 .”라고 말했습니다. 하지만 요즘 인터넷 바둑을 보면 나무판도 돌도 없는 것 같습니다. 나무판에 돌이건 혹은 이진법 신호의 전달이건 상관없이 이것들이 다 바둑이라 불리는 이유는, 이것들이 같은 규칙을 준수하고 있기 때문인 것인 것 같습니다. 이렇게 본다면 바둑은 구성하는 물질에 상관없이, 추상적인 규칙으로 정의 가능한 것이 아닐까 생각하게 됩니다. 다시 말해서, 바둑이란 것을 '어떤 규칙들의 모음'으로 정의할 수도 있지 않을까 하는 생각입니다.

어떻게 보면 수학의 공리주의와도 닮은 생각인데, 이러한 방향으로 한 번 가 봅시다. 

타이젬에서 찾은 한국기원 바둑규칙을 보면 "바둑은 두 사람이 흑과 백의 바둑돌로 규칙에 따라 바둑판의 교차점에 교대로 착수하여 쌍방이 차지한 집이 많고 적음으로 승패를 가리는 경기이다." 라고 되어 있습니다. 이를 따르자면 우선 바둑이 구성되기 위해서는 바둑돌이 필요하고, 바둑판이 필요합니다. 하지만 인터넷 바둑에서 보듯이 바둑돌이 꼭 '돌'일 필요는 없고, 바둑판이 꼭 나무일 필요는 없습니다. 넓게 생각하면 바둑돌은 어떤 '상태'를 나타내기 위한 '상징'으로 생각할 수도 있고, 바둑판은 그 '상태'들이 표시되는 어떤 '공간'으로 생각할 수 있습니다. 대충 보면 가능한 상태는 '흑', '백', '비어있음' 의 세 상태가 있어 보이고, (물론 '비어있는' 상태를 세분화할 수도 있겠습니다만) 그 상태들은 어떤 '공간(바둑판)'에서 구체화됩니다 (착수를 하지요). 그 공간은 2차원의 직교 좌표계로 나타낼 수 있는 공간입니다.

바둑판에서 착수를 할  때 (혹은 공간에서 상태들이 바뀔 때), 착수(상태의 바뀜)은 어떤 규칙을 따라야만 합니다. 어떤 규칙이 있을까요? 한 번 핵심적으로 보이는 규칙들만 모아보면,
     
     (1) 흑과 백이 교대로 둔다.
           단, 특정한 경우에는 착수 포기가 허용된다.
    
     (2)  공배가 없는 돌은 들어내어진다. (죽는다)
    
     (3) 착수함으로서 자신과 상대의 돌의 공배를 모두 없앨 경우에는 착수한 쪽의 돌은 살고 상대의 돌은 죽는다.

     (4) 서로 상대방의 돌 하나를 번갈아 되딸 수 있는 모양을 「패」라고한다. 패는 무한한 동형반복을 방지하기 위하여 한쪽이 패를 따냈을때 즉시 패를 되딸 수 없으며 다른 곳에 한번 착수한 후에야 비로소 되딸 수있다.

대략 이정도가 핵심이 되는 규칙들이 아닐까 생각됩니다.
여기서 보면 규칙 (1) 과 규칙 (2) 는 독립적인 규칙입니다.
규칙 (3) 과 규칙 (4) 는 규칙 (1) 과 (2) 가 있고 나서 다음에 생기는 규칙으로 보입니다.
재미있는 것은, 규칙 (1) 과 (2) 만 가지고도 원시적인 형태의 '바둑'이란 놀이는 만들어지는 것 같다는 것입니다.

 규칙 (1) 과 (2)를 가지고 혼자서 멋대로 상상을 하고 있다 보면, 놀고 있는 두 아이들이 떠오릅니다. 둘이 앉아서 땅에 줄을 그어놓고 놀다가,  재미있는 놀이를 발견합니다. 검은 돌, 흰 돌을 교차점에 교대로 놓으면서, '돌은 둘러싸면 따먹는거다'하면서 돌따먹기 놀이를 하는 거죠. 그런데, 놀다 보니 문제가 생겼습니다. 어떤 지점에 놓으면 둘의 돌들이 동시에 공배가 없어지는 경우가 생긴거죠. 어떻게 해야 할까요? (2)의 원칙대로 둘 다 죽어버린다고 할 수도 있겠지만, 그것보다는 놓은 사람이 따먹는 걸로 하는 것이 더 놀이로 재미있어 보입니다. 만약 둘 다 죽는다고 해버리면 거기는 잘 두려고 하지 않겠죠. 그래서 규칙 (3)을 만들었습니다.

규칙 (3)을 만들고 한참을 또 놀다 보니, 희한한 경우가 생깁니다. 하나가 돌을 따먹으니까, 바로 그 자리에 다른 녀석이 다시 돌을 따먹을 수 있는 경우가 생깁니다. 따먹고, 되따먹고, 또 따먹고... 같은 형태가 반복되고 놀이가 끝나지 않습니다. 이래서는 안되겠다 싶으니 다시 규칙을 만듭니다. 이런 모양이 생겼을 때는, 다른 곳에 한 번 두고 나서 다시 따먹도록 하자. 그러면 규칙 (4) 가 생깁니다.

 이제 규칙을 만들고 보니, 웬만한 경우는 이 규칙들로 다 해결이 됩니다. 그래서 열심히 놀고 있는 데, 문제가 다시 생깁니다. 판 크기를 정해놓지 않으면, 놀이가 끝나지를 않는 겁니다. 돌을 다 따먹었다 싶으면 진 쪽이 금을 더 그어놓고 '나 여기다 둘래'하면, 승패를 가릴 방법이 없고, 사실 판이 유한하지 않으면 놀이도 유한하지 않죠. 그러니 가장자리를 정하고 판을 만들어야 할 건데, 가장 간단히 생각할 수 있는 건 정사각형 판이죠.

그럼, 처음에 유한한 판을 정해놓고 시작했다고 합시다. 판 크기가 유한하면, 웬만한 경우는 놓을 곳 다 놓고 놀이가 끝나겠죠. 웬만하지 않은 경우에는 또 놀이가 끝나지 않을지도 모릅니다. 생각도 못했던 삼패나 장생 같은 것이 생길지도 모르니까요. 삼패나 장생이 생기지 않았다고 하더라도, 누가 이겼는지를 판가름하려면 위의 규칙들로는 모자랍니다. 돌을 많이 따먹은 사람이 이긴 걸로 할까요? 아니면 영역이 넓은 사람? 판 위에 돌이 많은 사람? 여기서 또 누가 이겼는지를 가르려면 새로운 규칙이 필요합니다. 그리고 이 규칙들은 바둑이 이기고 지는 것을 다루는 놀이가 되기 위해선 필수적입니다. 그렇다면, 이런 승패를 결정하는 규칙들은 어떠해야 할까요?

 우선은 규칙들끼리는  모순이 없어야 할 겁니다.
될 수 있는대로 간명하면 좋을 것이고.
그리고 이 새로운 규칙들이 더해짐으로 인해서 확실하게 판이 끝나야 할 겁니다.

 그렇다면, 몇 가지 의문점이 떠오를 수 있습니다. 과연 이런 규칙들이 존재할까요? 간명하면 얼마나 간명해야 할까요?  이러한 판을 끝내는 규칙들은 유일하게 정해질까요?

답하기가 상당히 쉽지 않은 질문들입니다. 대충 생각을 해 보면 중국식과 한국식, 일본식 끝내는 방법이 있는 걸로 봐서 이러한 규칙들이 유일하지는 않다는 게 짐작이 됩니다. (캐나다식도 있는 것 같던데...) 집을 센다, 살아 있는 돌을 센다, 귀곡사, 삼패, 장생, 놓아놓고 석 집 등등 여러 가지 다양한 규칙들이 있습니다. 그렇다면, 과연 이러한 규칙들이 판을 확실히 끝내는 규칙들일지 의문이 생깁니다. 사실 귀곡사, 놓아두고 석 집 등의 규칙들은 경우 경우에 따라서 (case by case) 정해놓은 것이라, '혹시 생각지 못한 이상한 경우에는 기존 규칙으로 해결이 안되는 일이 생길지 어떻게 알아' 하고 충분히 의심을 할 수 있습니다. 혹은 반대로 '머리를 열심히 굴리면 모순이 없고, 간단하면서도 모든 경우를 해결해서 확실히 바둑을 끝내는 규칙들이 존재할지도 몰라' 라고 열심히 노력을 할 지도 모르지요. (응창치 씨가 많이 노력하셨지요.)

 그런데, 이런 규칙을 만들려고 머리를 굴리다 보면, 잠시 잊었던 사실이 떠오릅니다. 바로 '판의 크기'죠. 위의 새로운 규칙이 더해지는 과정에는 바로 판이 '유한'하다는 중요한 전제 조건이 있었습니다. 바둑이 끝나려면 판이 무한한 크기는 아니고 일정한 크기가 있어야 하는데, 그 크기에 상관 없이 규칙을 정할 수 있을까요? 뭐 '바둑이 19×19  크기의 판에서만 정의되는 것이다' 라고 말한다면 할 말은 없지만, 그러기엔 약간 억울하다는 생각이 듭니다. 9줄 바둑도 있고, 13 줄 바둑도 있고, 예전에는 바둑판이 17줄 이었다는데, 그럼 이게 다 바둑이 아닌 다른 놀이라 불러야 된다고 한다면 약간 번거로운 느낌이 듭니다. 그리고 21×21 판에서 같은 규칙으로 두면서 그 놀이를 '바둑'이라 부르고 싶다는 생각도 들구요.

잠시 다른 방향으로 가서 생각을 해 보면, 또 판이 꼭 정사각형 n×n 일 필요도 없습니다. 직사각형일 수도 있을 거고, 둥글 수도 있을 거고, 어쨌든 사각형 격자 구조만 가지면 되니까요. 심지어는 변과 귀를 없앨 수도 있습니다. 예를 들어 아주 신축성이 좋은 사각형 고무판에다가 n×n 격자 모양을 그린 다음에, 둥글게 말아서 원통형을 만들면서 좌변 끝과 우변 끝을 포갭니다. 그러면 좌변과 우변이 없고 상변과 하변만 남은 (n-1)×n 판이 되겠죠? 그 다음에는 이 원통형 판을 다시 구부려서 위와 아래를 붙이는 도우넛 (다른 말로는 Torus) 형태를 만듭니다. (던킨 도너츠 모양 생각하시면 될 듯) 그러면 이제는 상변과 하변도 사라졌습니다. 이런 판에서는 변도 귀도 없고, 모든 교차점이 평등합니다. 초반부터 공중전만 하는 양상이 되겠죠. (뭐 더 생각하시는 분은 뫼비우스 띠에서 바둑판을 만드시려고도 하실지?) 

그런데 위의 판과 같은 경우에는, 귀가 없으므로 '귀곡사'라는 규칙이 사라집니다. 귀곡사도 중요한 바둑 규칙 중 하나고, 귀곡사가 어떻게 정의되어 있느냐에 따라 바둑의 성질이 달라집니다. 또 위와 같이 귀와 변이 없는 바둑판에서는 다른 이상한 형태가 나타날지 누가 압니까? 이런 이상한 바둑판 예를 들지 않더라도, 3×3 바둑판에서도 귀곡사는 나타날 수 없습니다. 이렇게 보면, 바둑의 규칙들은 그 판의 크기와 경계 조건에 따라서 정해진다고 유추할 수 있습니다.

자, 그럼 다시 머리 속을 정리하고 질문을 해 봅시다.
 '임의의 유한한 판에서, 기본 규칙들 (1-4) 과 모순되지 않으면서 가능한 한 간명한 규칙들을 더해서 놀이의 승부가 결정이 될 수 있도록 (승, 패) 바둑을 정의할 수 있을까요?'

 위의 질문과 그 질문에 대한 답이 이 글을 쓴 주된 이유입니다.
  뭐 눈치 빠르신 분들이나 수학, 컴퓨터를 잘 하시는 분들은 벌써 답을 짐작하고 계시겠지만,  제 수준에서 그 답을 하려면 여러 가지 다른 것들을 명확하게 할 필요가 있습니다.  그래서 우선 답을 하기 앞서서, 다른 것들을 좀 건드려 봅시다.

*
두 번째 글입니다. 바둑의 판 수에 대해서입니다.

요즘 인터넷 바둑을 보고 있다 보면 바둑은 참 디지털로  나타내기 편한 놀이다 하는 생각이 듭니다. 판도 직교 좌표계로 딱 짜여져 있고, 돌도 흑, 백으로 나뉘어져 있고, 모든 양들이 연속적이 아닌 이산적으로 되어 있지요. 참 프로그래밍하기 편한 놀이인 것 같습니다. 인터넷으로 둘 때도 복잡한 그래픽 하나도 없어도 대단히 효율적인 정보 교환으로 엄청난 재미를 줄 수 있습니다. 요즘 화려한 그래픽의 온라인 게임과 비교하면 지극히 경제적이고 잘 만들어진 놀이입니다.

모든 양들이 이산적으로 되어 있다는 건 바둑을 숫자로 나타내기도 굉장히 쉽다는 말이 됩니다. 기보올리기를 해 보신 분들이면 금방 아시겠지만 한 판의 바둑은 하나의 수열로 간단히 나타내어집니다. 하나의 수열은 또 하나의 실수와도 대응 가능하죠. 간단한 예로 호선으로 흑이 먼저 두는 바둑을 생각해 봅시다. 현 바둑판의 착수 가능점은 361개이죠. 그 착수 가능점에 우리는 1에서 361 까지의 숫자를 대입할 수 있습니다. 착수 넘김을 하는 경우는 0이라 하면 수순을 가진 바둑 한 판은 362진법의 소수로 나타낼 수 있습니다. 예를 들어 흑백이 화점에 두면 0.(61)(301)(289).... 같이 나타낼 수 있겠죠. 여기서 홀수 번째 수들은 흑의 좌표이고 짝수 번째 수들은 백의 좌표가 될 겁니다.

이렇게 한 판의 바둑이 하나의 숫자로 나타날 정도로 간단하지만 바둑이 그리도 재미있고 오묘한 이유는 그 나타낼 수 있는 숫자의 가짓수가 어마어마하게 많기 때문이기도 합니다. 그럼, 도대체 한 판의 바둑이 나타낼 수 있는 가능성이 얼마나 되는지 대충 분석을 시도해 보겠습니다. 여기서는 바둑판에서 나타날 수 있는 판의 숫자가 어느 정도 될지 가늠을 해보기로 하지요.

처음 짐작으로는 대충 바둑의 판 수는 361! 정도가 되지 않을까 할 수도 있습니다. (대칭성 무시하고) 처음에 흑이 둘 수 있는 곳은 361곳, 다음에 백이 둘 수 있는 곳은 360 곳, 다음에 흑이 둘 수 있는 곳은 359 곳, 이런 식으로 생각하면 바둑의 판 수는 대략 361*360*359*.... =361! 정도라고 생각이 됩니다.

근데, 대개 세상일이 처음 생각처럼 그리 간단하지 않은지라.... 바둑에서는 돌이 죽고 나면 그 자리가 비고, 빈 자리에 또  둘 수도 있습니다. 이렇게 되면 돌을 따낸 후에는 다음 사람이 둘 자리가 더 늘어나는지라, 361! 보다 더 많아질 수도 있습니다. 더구나, 삼패나 장생같은 것이 나오면 이건 판이 끝나지를 않는지라, 판 수를 세는데 상당히 헷갈리기 시작합니다. 수순이 361 수보다 많은 판도 실제로 있고, 그러면 판 수가 앞에서 말했던 361! 의 정도를 훨씬 뛰어넘지 않을까요?

이런 것을 염도에 두고, 위에서 말한 한 판의 바둑은 하나의 소수로 나타낼 수 있다는 걸 무기로 바둑의 판 수를  분석해 봅시다.  바둑의 판 수를 소수로 나타내면, 유한한 판은 이 소수가 유한한 자리수로 끝날 거고, 둔 곳에 두고 또 두고 하면 무한하게 되겠죠. (예로는 삼패나 장생) 삼패의 경우는 흑이 놓을 수 있는 자리를 1,3,5, 백이 놓을 수 있는 자리를 2,4,6 이라 편의상 놓으면 (1)(6)(3)(2)(5)(4)(1)(6)(3)... 과 같이 순환하는 무한 소수가 될 겁니다. 장생의 경우도 순환하는 무한소수죠.

순환하는 무한 소수만 생긴다면 그래도 좀 간단한데, 때때론 순환하지 않는 무한 소수도 판에 나타날 수 있습니다. 순환하지 않는 무한 소수의 간단한 예로 패가 여러 군데서 발생하는 경우를 들 수 있습니다. 예를 들어 패가 한 6개 정도 생겼다고 합시다. 이렇게 패가 많은 경우에는 흑은 삼패와는 다르게 어느 패를 딸 수 있는 선택권이 있습니다. 백도 마찬가지로 흑이 패를 땄을 때 남아있는 패 중 아무거나 따면 됩니다. 그러면 순환하지 않는 무한 소수를 만들 수 있습니다. 구체적으로 흑이 둘 수 있는 곳을 1,3,5,7,9,11 이라고 하고 백이 둘 수 있는 곳을  2,4,6,8,10,12 라 했을 때, 초기 조건을 흑이 1과 11을 차지한 흑선으로  주면 백이 항상 다음 흑 차례에 흑이 (1,3,5) 와 (7,9,11) 중 어느 한 쪽을 따도록 순서를 넘길 수 있습니다. 그러면 흑이 (1,3,5)를 따는 경우를 0, 흑이 (7,9,11)을 따는 경우를 1로 잡는다면  이런 바둑의 판 수는 [0,1] 구간 사이의 모든 이진수와 일대일 대응이 가능합니다. 이런 순환하지 않는 무한 소수는 셀 수 없고, (uncountable infinity) 이런 무한은 실수의 무한과 같습니다. 무한 중에서도 셀 수 있는 무한보다는 한 단계 급이 높은 무한입니다.

위에서 결국 바둑의 판 수는 실수의 무한과 같다는 걸 보였는데요,이 경우는 동형 반복이 허용되는 경우입니다. 만약 동형 반복을 허용하지 않는 경우는 어떨까요?   영어론 super ko rule 이라고 하던데, 어차피 패의 규칙도 동형 반복을 금지하기 위한 것이니 장생이나 삼패도 다른 곳에 놓고 다시 두어야 하는 식으로 규칙을 정하는 것 말입니다. 이런 경우에는 판의 수는 유한해집니다. 바둑판에 나타나는 모든 형태에는 상한이 있습니다. 바둑판에서 착수가 가능한 지점은 361 곳이고,  대충 생각하면 각 착수 지점마다 (1) 흑돌이 놓여 있다 (2) 백돌이 놓여 있다 (3) 비어 있다 의 세 가지 경우가 있습니다. 좀 더 따지면 (3) 비어 있다의 경우는 비어 있지만 흑은 착수 가능하고 백은 착수 불가능한 경우, 흑은 착수 불가능하지만 백은 착수 가능한 경우, 흑백 모두 착수 불가능한 경우가 있습니다. 여기서 흑은 착수 가능하지만 백은 착수 불가능한 경우는 흑이 한 집 낸 경우나 패의 경우를 생각하시면 쉬울 겁니다. '흑백이 모두 착수 불가능한 지점'은 위의 동형 반복 금지 규칙을 생각하면 이런 점들이 생깁니다. 예를 들어 삼패가 생겼을 경우에 한 번 패를 따는 순환이 거친 후 흑은 동형 반복이 생기므로 삼패를 계속하지 못합니다. 백도 패의 규정에 따른 착수 금지로 돌을 놓지 못하죠. 그런 경우에는 양쪽이 다 착수를 하지 못하는 지점이 생깁니다.

이런 걸 다 고려해서 바둑판에 나오는 모든 형태의 상한을 다시 구하면, 착수 가능점 361 곳에 한 지점마다 가능한 경우의 수는 (1)흑돌이 놓여 있다 (2) 백돌이 놓여 있다 (3) 비어 있고 흑백 착수 가능점 (4) 비어 있고 흑만 착수 가능 (5) 비어 있고 백만 착수 가능 (6) 비어 있고 흑백 모두 착수 불가능 의 6 가지가 있습니다. 그러니 여유있게 잡아도 바둑판에 나오는 모든 형태의 수는 6^(361) 보다 작습니다. 가능한 형태가 유한개니까 어떤 무한한 판에도 같은 형태가 두 번 이상 나타납니다. 따라서 동형 반복을 금지한다면 모든 판은 유한하게 끝나고 그 판들은 362진법의 유한 자리의 소수로 나타냄이 가능합니다.

그렇다면, 유한이면 도대체 얼마나 큰 유한일까요? 여기서도 대충 잡아서 생각을 해 보면,  둔 곳에 또 두고 하면 위에서 말한 (6^361) 보다 적은 정도의 모양이 거의 다 나타나게 하는 것이 가능합니다. 예를 들어 판이 거의 끝난 다음에고의적으로 흑백이 자신의 집을 메꾸고 메꾸고 하여 서로 자폭을 해서 판을 거의 깨끗하게 비우고 다시 거의 깨끗한 판에다 새로 시작할 수도 있는 거죠. 그런 식으로 웬만한 모양을 다 판에다 구현하는 식으로 바둑을 둔다면, 가능한 수는 거의 (6^361)! 정도가 (order of magnitude) 됩니다. 한 판이 끝날 때 나타나는 모양의 갯수가 대략  2^361 정도의 크기라 보고 이게 모두 순환되어 나타날 수 있다고 하면 나타날 수 있는 판의 수는 (2^361)!, 대략 10^(5.1*10^110) 정도가 됩니다. 이게 얼마나 어마어마한 숫자냐 하면, 우선 10^110 이 1 다음에 0 이110개 붙는 숫자입니다. 10^(5.1*10^172) 은 1 다음에 0 이 대략 5.1*10^110 개 만큼 붙었다고 보시면 됩니다. 유한이라 하더라도 좀 무지막지하죠.

좀 지루한 내용이었을지도 모르고 약간은 옆으로 샌 내용인데, 이런 걸 정리해 놓는 것도 앞에서 말했던'바둑을 어떻게 정의하느냐'에 대한 답을 구하는데 도움이 됩니다. (저한테는^^) 이왕 옆으로 샌 김에, '바둑을 이해한다는 것은 어떤 것일까'에 대해 나름대로 주저리주저리 말을 늘어놓아 본 다음에, '바둑을 어떻게 정의하느냐'의 질문으로 다시 돌아가겠습니다.

'바둑을 이해한다는 건 무엇일까?'

이 번에도 좀 옆길로 샌 내용이고, 사실 제가 답하기는 힘든 질문들입니다. 그래도 이런 글을 쓰는 건 순전히 제 재미 때문이죠. 이건 제 개인적인 생각이고 논리의 비약도 있을지 모르니, 아니다 싶으면 마구마구 지적해 주세요.

 '바둑을 이해한다는 건 무슨 뜻일까' 참 생각해 보면 답하기 힘듭니다. 물론 바둑을 이해한다는 건 잘 둔다는 뜻이라고 말을 해 버리면 간단합니다. 그러면 잘 두려면 어떻게 해야 할까요????

 때때론 바둑을 두다 보면 바둑 고수들의 머릿속을 들여다보고 싶어집니다. 사실 사람의 머릿속을 보고 이해한다는 건 힘든 일이지만, 컴퓨터 프로그램을 들여다보는 건 생각 외로 쉽습니다. 그렇다면, 질문을 좀 더 간단하게 바꾸어서, 바둑을 잘 두는 컴퓨터 프로그램을 만든다는 건 어떤 것일까를 생각해 봅니다.

 질문을 간단하게 한다고 하긴 했지만, 사실 바둑을 잘 두는 컴퓨터 프로그램을 만든다는 것도 쉽지 않은 일이지요. 아직까지도 컴퓨터 바둑의 수준은 사람의 수준에 훨씬 못 미칩니다. 왜 그럴까요?
사람보다 컴퓨터가 잘하는 것은 계산이지요. 사람이 몇 년이 걸려도 하지 못하는 계산을 컴퓨터는 몇 초 안에 끝낼 수 있습니다. 그런데도 컴퓨터가 바둑을 사람보다 못 둔다는 건, 두뇌 활동에서 사람이 컴퓨터의 계산을 뛰어넘는 어떤 것을 가지고 있다는 이야길까요?

 질문을 더욱 더 간단히 해서, 판을 좁혔을 경우에 컴퓨터가 어떻게 바둑을 둘 지 생각해 봅시다. 아주 간단하게 3*3 바둑판을 생각한다면, 여기서는 경우의 수가 별로 많지 않습니다. 대칭성까지 고려하면 처음에 가능한 수는 3개, 2 수 까지의 가능한 수는 모두 12개 밖에 없습니다. 대충 생각해도 9!= 362880 개 보다 훨씬 적은 수를 고려해도 될 것 같고, 사실 9! 정도의 숫자는 요즘 컴퓨터는 눈 깜짝할 사이보다 빠르게 계산을 합니다. 이 3*3 바둑판에서는 컴퓨터의 무식하게 모두 다 계산하는 방법이 아주 유효합니다. 모든 경우의 숫자가 다 구해질 수 있고, 재미있는 것은 흑의 최선의 수도 구해집니다. 위의 3*3 바둑판 중앙에 둔 흑 1은 3*3 바둑판에서의 소위 ‘신의 한 수’입니다. 그 이후에 백이 어떻게 두던 흑은 한 집을 냄으로써 백을 다 잡을 수 있습니다. 이렇게 좁은 바둑판에서는 이창호9단이 두건, 제가 두건, 혹은 컴퓨터가 두건 이 한 수만 외워놓으면 결과가 다 같은 것이지요. 컴퓨터의 무식하게 계산하는 방법 (brute force calculation) 이 이 좁은 바둑판에서는 이창호9단에 필적함을 보여주는 빛나는 예입니다.
 
 그런데 생각을 해 보니 약간 억울합니다. 사람은 바둑을 ‘이해’해서 두고, 컴퓨터는 무식하게 모든 경우를 다 계산해서 두는데, 결과가 같다니 말입니다. 좀 더 무식하게 생각하면, 바둑을 하나도 모르는 사람도 위의 ‘신의 한 수’와 그 후의 수순만 외워버리면 3*3 바둑판에서의 ‘흑번 필승’ 신화를 만들어낼 수 있습니다. 이런 경우에도 이 사람은 바둑을 '이해’했다고 할 수 있을까요?

 예전에 독일의 왕과 병사에 관한 우스갯소리를 들은 적이 있습니다. 이 왕은 자주 병영을 시찰했는데, 병영을 시찰하면서 묻는 질문이 항상 같았다죠. ‘자네의 나이는?',‘입대한 지는 어떻게 되나?’ ‘식사와 봉급에 불만은 있나?’였답니다. 그런데, 한 병영에는 독일말을 전혀 모르는 신참 병사가 있었습니다. 그래서 고참이 ‘왕의 질문은 항상 같으니 답만 차례로 독일말로 외워라. ‘19년, 3개월, 둘 다 좋습니다.’이다. 라고 교육을 시켰답니다. 드디어 어느날 왕이 시찰을 왔습니다. 이 신참 병사에게 질문을 던졌는데, 이번에는 ‘입대한 지는 얼마나 되나?’하고 먼저 물었답니다. 병사는 ‘19년 입니다’하고 외운대로 대답했습니다. 대왕이 깜짝 놀라서 ‘그럼 자네의 나이는?’ 하니 ‘3개월 입니다’하고 대답했죠. 대왕이 기가 차서 ‘허허, 자네가 미쳤던지 내가 미쳤던지 둘 중 하나겠군’ 하니 ‘ 둘 다 좋습니다’ 하고 대답했다는군요.

위의 예는 우스개소리지만 ‘이해’라는 것에 대해서 다시 한 번 생각하게 만듭니다. 병사가 외운 답변은 한 가지 경우에는 대단히 유용했죠. 하지만 약간 상황이 바뀌어 버리자 그만 병사의 방법은 무용지물로 변해 버렸습니다. 즉 병사는 언어를 ‘이해’하고 있지 않았습니다. 만약 사전을 통째로 외운 컴퓨터가 있다 하더라도 다변하는 언어적 상황에서는 그리 유용하지 않을 겁니다. 그 예로 중국어 번역기의 번역을 보시면 바로 그런 생각이 드실 겁니다. 반면에 언어를 ‘이해’하고 있는 사람이면 어떤 질문이 들어와도 바로바로 유연하게 대처가 가능하겠죠. 이렇게 본다면, 대개 사람들은 어떤 것을 잘 이해했다고 할 때 그것과 관련된 매우 다양한 질문에 대해 대단히 효과적으로 답을 낼 수 있는 것처럼 보입니다. 컴퓨터로 치면 다양한 입력 (input) 에 대해서도 답을 내는 연산 시간이 상당히 빠른 알고리즘(algorithm)을 가지고 있는 것 정도로 비유가 될 것 같습니다. 

그런데, 많은 경우에 이런 유연하고 빠른 알고리즘을 찾는 것이 쉽지가 않습니다. 위에서 말했던 무식하게 계산하는 컴퓨터 바둑 프로그램은 판이 조금만 커져도 금방 바보가 됩니다. 앞의 '바둑의 판 수'라는 글에서 말했듯이, 바둑의 판 수는 판이 조금만 커져도 지수의 지수로 늘어나는데, 이런 경우의 수의 증가 속도는 무식한 계산 (brute force calculation)으론 도저히 따라잡을 수 없습니다. 무한한 메모리가 있다면야 가능은 하겠지만 그야말로 바둑 두다가 도끼자루 썩고 한 판의 바둑이 백 년인 사태가 발생하겠지요. 그런데 사람은 컴퓨터보다 훨씬 빨리 두는데도 훨씬 잘 둔단 말입니다? 서능욱 9단 같은 분은 바둑 한 판을 15분 정도에 끝낼 수도 있으니까요.

사실 이 문제는 컴퓨터를 연구하는 사람들이 말하는 P-NP 문제와도 관련이 있는데, 컴퓨터 연구하는 사람들은 P(polynomial)-문제라고 입력 (input)의 길이를 x 라 할 때 그 답하는 시간이 기껏해야 x^n 에 비례하는 그런 문제를 좋아합니다. 그런데 세상사가 그렇게 간단치 않습니다. P 가 아닌 것 같은 문제는 세상에 널려 있습니다. '여러 도시를 여행하는 사람이 최단 경로를 어떻게 찾는가?' 같이 간단해 보이는 문제도 도시 숫자가 늘어남에 따라 그 컴퓨터가 최단 경로를 찾는 시간은 무지하게 길어집니다. 간단한 알고리즘이 쉽지 않지요. 반면, 사람은 이런 문제를 상당히 쉽게 푸는 것 같이 보입니다. 여행 계획 잡으면서 최단 경로 때문에 고민하다 여행 못했단 이야기는 흔치 않은 이야기지요.
 
 사람은 어떻게 이런 문제를 간단히 풀 수 있을까요? 한 가지 사람의 강점은, 어림잡는 것에 능하다는 것입니다. 사람이 여행 경로를 잡거나 바둑을 둘 때, 정말로 이것이 최선의 것인가를 확신하고 결정하기 보다는, 대충 최선에 가까울 것 같다라고 어림하고 결정한다는 것입니다. 앞의 계산 문제 같은 건 사람이 몇 년이 걸리는 문제를 컴퓨터는 몇 초 안에 끝내지만, 그런 것이 아닌 훨씬 많은 다른 종류의 문제들에 대해선 컴퓨터가 '확실한' 해답을 찾기 위해서 cpu가 터져라 몇 년 간 연산을 하고 있을 때, 사람은 '이게 대충 맞는 것 같아'하고 몇 초 안에 결정을 해버립니다. 컴퓨터는 결정론적으로 연산을 한다면, 사람은 확률에 따라 사고하고 행동하는 것이 아주 큰 차이입니다.

이 확률적인 사고는 결정론적인 사고와 많은 차이가 있습니다. 확률적으로 생각함으로써 사람은 마침내 불확실성의 세계에 발을 들여놓습니다. 문제 처리 시간에 관한 한 능률은 엄청나게 오른 것 처럼 보이지만, 답이 맞을지 안 맞을지는 확실하지 않습니다. 확률적으로 생각한다 하더라도, 많은 경우에 확률이 몇 퍼센트라고 계산하는 것도 불가능한 경우가 많습니다. 이렇게 되면서, 바둑에 관한 언어도 바뀌기 시작합니다. 계산만 하는 컴퓨터 같으면 '이렇게 두는 것은 저렇게 두는 것에 비해서 몇 집 손해입니다'하고 말하겠죠. 하지만 사람이 판단을 할 때에는 '흑이 편한 느낌입니다' , '이렇게 싸우기는 서로 두렵죠', '기세상 이 한 수 입니다'라는 말이 나오기 시작합니다. '편하다','두렵다' '기세' 같은 건 논리와는 좀 거리가 있는, 감정적인 것과 관련이 있는 단어입니다. 바둑이라는 지극히 논리적이고 결정론적으로 보이는 놀이에, 감정을 개입시키는 것이 효과적일까요?

제가 생각하기에는 효과가 있습니다. 감정에 근거한 판단은, 비록 틀릴 확률이 높을지 몰라도 그 답을 내는 처리 속도에 있어서는 탁월합니다. 어떤 상황에서 '느낌이 좋다' 혹은 '느낌이 좋지 않다'는 초 단위로 판단이 됩니다. 또 다른 예로  맹수가 눈 앞에서  달려드는데, 이성적으로 최선의 도주 경로를 계산하고 있다간 잡아먹히죠. 공포를 느끼고 바로 도망가는 것이 시간과 결과를 같이 고려한 면에서는 상책일 수 있습니다. 이런 면에서 보면 감정이나 느낌이란 것은, 사람이 가지고 있는 가장 기초적인 확률 알고리즘인 측면이 있습니다.

 이렇게 바둑의 수를 사람이 '수읽기'라는 논리적 사고와 함께 '기세', '느낌' 등을 같이 넣어 고려하면서, 문제를 해결하는 방법도 엄청나게 바뀝니다. 계산만 하는 컴퓨터는 문제를 해결하는 방법이 계산 하나 뿐입니다. 하지만 사람과 같이 확률을 다루는 경우에는 그 확률을 추정하는 근거는 온갖 곳에서 다 나올 수 있습니다.  '이렇게 두니 잘 안되더라'하는 바둑 자체의 경험부터, '세상사가 그렇듯이 너무 욕심을 부리면 안돼' 하는 인생의 경험, '승부는 기세 싸움이다!'하는 다른 일반적인 승부로부터 얻은 경험, '이 상대는 하수니까 꼼수가 통할거야' 하는 바둑 외의 고려 등. 바둑의 수를 찾는 문제를 푸는데 사람이 경험한 모든 것이 고려의 대상이 될 수 있습니다.

위에서 말했듯이 이렇게 확률적으로 사고하는 것은, 처리 속도를 엄청나게 빨리 올리는 것과 함께 문제의 답을 찾는 해답 공간을 엄청나게 늘립니다. 사람은 이제 바둑을 바둑 그 자체로만 보는 것이 아니라, 자신의 인생을 포함한 아주 넓은 공간에 바둑을 넣고 보기 시작합니다. 바둑은 그 공간 안에서 온갖 것들과 연관이 되고, 변합니다. 바둑은 놀이고, 철학이고, 목숨을 걸고 두는 어떤 것이고, 미학이고, 자연류이고, 예술이고, 도박이고, 잡기이고 스포츠입니다. 어떻게 보면 이상한 확장인 것 같지만, 어떻게 보면 당연한 것일 수도 있습니다. 어차피 처음에 바둑을 두기 시작한 이유는 '재미있으니까!' '놀려고!' 와 같은 바둑 이외의 것에서 나왔을 확률이 높고, 그렇다면 바둑이 넓은 공간으로 나가는 것은 어떻게 보면 자신이 태어난 공간으로 돌아가는 것일 수도 있습니다......
글을 쓰다가 보니 잡설이 너무 길어진 것 같습니다. 다음 글에서는 처음에 물었던 '바둑을 규칙들의 집합으로 잘 정의할 수 있을까?' 라는 문제로 (마침내!) 돌아가서, 답을 생각해 보도록 하겠습니다.

*
 덧붙이자면, 제가 여기서 '컴퓨터가 사람을 따라잡는 건 불가능하다'라고 말한 것은 아닙니다. 단지 '현재의 결정론적으로 계산하는 컴퓨터로는, 확률적으로 생각하는 사람을 따라잡기 힘들다'라는 것입니다. 미래에 새로운 알고리즘의 새로운 컴퓨터가 나와서 사람을 따라잡을지 아무도 모르는 일이죠.

드디어 이번 글에서는 처음에 물었었던 '임의의 유한한 판에서, 기본 규칙들과 모순되지 않으면서 가능한 한 간명한 규칙들을 더해서 놀이의 승부가 결정이 될 수 있도록 (승, 패) 바둑을 정의할 수 있을까요?' 라는 질문에 답을 시도해 보도록 하겠습니다. 그 답을 하기 전에, 다시 좀 뜬금없는 역사 이야기나 하다가 다시 본래 주제로 돌아가도록 하죠.

 지금으로부터 한 백 년 전 쯤에, 힐버트 (D. Hilbert, 1862-1943)라는 수학자가 있었답니다. 이 힐버트란 사람은 수학을 '공리(Axiom)'라는 걸 통해 몽땅 형식(formal)적으로 바꾸고 싶어했습니다. 힐버트는 수학이라는 것이 직관같은 것에서 오는 것을 싫어했습니다. 가능하면 직관이 가장 적게 들어가고, 가장 순수하게 논리적인 것으로부터 수학의 기초를 다진 다음에, 거기서부터 하나씩 하나씩 단계적으로 증명을 해서 수학을 쌓아올리고 싶어했지요. 그래서 수학에서 가장 기초적이고 가장 직관이 적게 들어가는 것은 '숫자'라고 생각하고, 숫자들과 그 연산을 기초로 해서 차례로 수학적 정리들을 증명하려고 했습니다. 가장 기초적인 '유한'개의 공리와 그 공리들이 서로 모순이 없다(consistent)는 전제만 가지고 모든 수학을 증명하려고 했던 원대한 계획이었습니다.

그런데, (아시는 분은 아시겠지만) 괴델(K. Gödel 1906-1978 )이란 사람이 이 계획에 초를 칩니다.
1931년에 괴델은 수학적인 언어를 자연수와 연산으로 이루어진 형식적 언어로 바꾸고, 그 형식적 언어를 이용해  유명한 두 가지 정리를 발표합니다.

1. 자연수를 공리화할 수 있을 정도로 충분히 강력한 어떤 무모순적 수학적 계에서도,
   증명할 수 없지만 참인 명제를 만들 수 있다.

2. 그 자신의 무모순성을 증명할 수 있는 어떤 무모순적인 계(consistent system)도 없다.


어떻게 보면 충격적이고 상당히 생각을 요구하는 말들인데요...  이 정리들이 발표되면서 힐버트는 그의 계획을 접게 됩니다. 사실 힐버트의 계획은 다른 측면에서 보면 요즘 컴퓨터 과학에서 하는 프로그램 개발하는 것과 비슷한 면이 있었습니다. 힐버트가 하려고 했던 것 중 하나는 다른 말로 바꾸면 어떠한 수학적 명제가 주어지더라도 유한한 단계의 잘 정의된 연산을 가지고 그 명제의 참과  거짓을 분별할 수 있는 일반적인 방법을 만들어내려고 했던 것이었죠. 이건 컴퓨터 프로그램에 이용되는 알고리즘, 즉 어떤 유한한 수의 잘 정의된 연산을 가지고 주어진 초기 조건에 대해 결과를 내는 방법입니다.

1936년, 영국의 수학자인 튜링(A.Turing 1912-1954)은 괴델의 정리를 다른 방식으로 접근합니다. 괴델이 수학적 정리를 수와 연산에 기초한 형식적인 언어로 바꾸어 그의 정리를 증명했다면, 튜링은 그 수와 연산에 기초한 형식적 언어를 다루는 도구로서 튜링 기계 (Turing Machine)라는 것을 생각합니다. 튜링 기계는 유한한 종류의 기호들 (예를 들면 0,1) 로 구성된 입력 테이프와 그 입력 테이프를  읽고 쓰는 장치 , 유한 개의 기계 내부적 상태, 입력과 내부적 상태에 따라 할 행동을 지시하는 목록으로 이루어져 있습니다. 대충 생각하면 이론적으로 단순화한 컴퓨터라고 볼 수 있습니다. 현재의 모든 컴퓨터는 튜링 기계를 현실화한 것이라고도 볼 수 있죠. 힐버트가 생각했던 '어떠한 수학적 명제에 대해 유한한 단계의 연산으로 참, 거짓을 판별할 수 있는 방법이 있는가?' 라는 질문을 튜링의 방식으로 바꾸면 '튜링 기계(컴퓨터) 상에서 구현되는,  어떠한 문제에 대해 유한한 시간 내에 예, 아니오의 답을 줄 수 있는 알고리즘을 만들 수 있는가?'가 됩니다.  어떤 문제에 대해 답을 주는 컴퓨터 프로그램(program) 을 짤 수 있냐? 하고 묻는 것과도 비슷합니다. 많은 문제에 대해서는 아시다시피 좋은 프로그램이 많죠. 그런데 놀랍게도 (혹은 당연하게도) 괴델의 정리를 응용하면 답을 주는 일반적인 알고리즘이 없는 문제들이 있다는 것이 보입니다.

튜링은 컴퓨터 과학의 아버지라고도 불립니다. 튜링의 이론으로 인하여 컴퓨터라는 것이 수학적으로 적용될 수 있게 되었고, 과연 컴퓨터가 할 수 있는 일이 무엇이고 할 수 없는 일이 무엇인가에 대한 수학적인 증명이 가능하게 되었습니다. 튜링이 밝힌 것 중 유명한 것은 괴델의 정리를 이용해서 만들기 불가능한 프로그램들이 있다는 것을 보인 것인데요,그 중 유명한 것이 멈춤 문제 (halting problem) 입니다. 일반적으로 프로그램이 멈추는지 멈추지 않는지를 점검하는 프로그램은 만들 수 없다는 것이죠. 그 후, 여러 연구가 진행되면서 괴델의 정리는 많은 방법으로 증명될 수 있고, 이 정리는 굉장히 많은 곳에 응용이 된다는 사실이 밝혀집니다. 1960년대 후반에 알고리즘적 정보 이론 (Algorithmic information theory) 가 나오면서 괴델 정리는 굉장히 다양한 곳에 적용이 되고, 이를 정보 이론과 컴퓨터와 연관시키면 재미있는 결과들이 나온다는 것을 사람들이 보입니다.

그 중 카이틴 (GJ Chaitin 1947-)이란 사람이 괴델의 정리를 이 알고리즘적 정보 이론의 측면에서 본 것이 있는데, 여기서는 한 번 이를 따라가 보겠습니다.

  이 알고리즘적 정보 이론에서 중요한 개념으로는 복잡성(complexity)란 것이 있습니다. 0과 1로 이루어진 이진법의 수열을 생각해 봅시다. 이 수열의 복잡성은 '이 수열을 정의하기 위한 최소한의 정보'로 정의됩니다. 다른 말로 이야기하면, 어떤 정보를 주었을 때 이 정보를 가지고 수열을 만들어낼 수 있는 최소한의 정보입니다. 컴퓨터를 가지고 이야기하면, 어떤 수열의 복잡성은 그 수열을 만들어 낼 수 있는 프로그램의 길이로 정의가 됩니다. 예를 들어 111111....로 1 이 N 개 있는 길이 N 인 수열을 생각해 봅시다. 이 수열을 만들 수 있는 프로그램은 간단합니다. '먼저 1 출력하고, 이걸 N 번 반복!' 하면 간단하죠. 1이 N 번 반복되는 수열의 경우, 이 수열의 복잡성은  log₂N + C 정도입니다. N 이란 숫자를 프로그램 안에 쓰는데 약 log₂N 정도의 정보가 필요하고, (예를 들어 1 이 1,000,000,000 번 반복되는 수열의 경우엔 '먼저 1 출력하고, 이걸 1,000,000,000 번 반복!' 으로 프로그램의 크기는 1,000,000,000 보다 훨씬 짧습니다.) 나머지 출력, 반복 등의 구문을 쓰는 데 N과 관계없는 일정량 C의 정보가 필요합니다.

그런데, 11111111... 같은 어떤 규칙이 있는 수열이 아닌 01110011100101... 처럼 규칙이 없이 무작위적 (random)으로 숫자가 나오는 N bit 의 수열은 어떻게 만들어야 할까요?  규칙이 없는 경우에는 이런 수열을 만드는 방법은 다 찍는 수 밖에 없습니다.  예를 들어 01110011100101... 같이 규칙이 없는 숫자들의 길이 N= 1,000,000,000 의 수열이 있으면 이걸 만들 수 있는 프로그램은 ' 01110011100101... (해서 ,000,000,000 자리수까지 몽땅) 을 출력!' 밖에 없습니다. 그럴 때에는 이 프로그램의 길이는 N+C 정도가 됩니다. N 자리수를 그대로 찍는 길이 N, 출력같은 명령어에 C정도 길이가 필요하니까요. 그리고 N 이 커짐에 따라 대다수의 길이 N 의 수열은 복잡성 정도가 대략 N 이 됩니다. 규칙을 가지는 수열보다 규칙이 없는 수열이 훨씬 많다는 이야긴데요, 이건 수에서 유리수보다 무리수가 훨씬 많다는 사실과 비슷합니다. 좀 더 구체적으로 이야기하면, 가능한 길이 N 의 수열은 2^N 개가 있고, 길이 N-K 인 프로그램의 숫자는 2^(N-K)보다 적죠. 그러니까 N 이 커질수록 길이가 (N-K)보다 작으면서 길이 N 인 수열을 만드는 프로그램의 숫자는 전체 길이 N 인 수열에 비해 지수 함수적으로 작아집니다.
  
콜모고로프 (A. Kolmogorov 1903-1987) 는 어떤 수열이 대략 자기 자신의 길이와 같은 크기의 복잡성을 가질 때 그런 수열을 '무작위적(random)'이라 부르자고 제안했습니다. 앞에서 말했듯이 큰 N에 대해  거의 대다수의 길이 N인 수열은 무작위적인데, 여기서 사람들은 재미있는 질문을 던집니다.  '어떤 길이 N의 수열이 주어졌을 때, 이 수열이 대략 복잡성 N 을 가진다는 것을 증명할 수  있는가?'하는 질문입니다. 다른 말로 바꾸면, '과연 길이 N 의 수열에 대해 길이 N 보다 짧은 프로그램으로 이 수열을 만드는 방법이 없다는 걸 증명할 수 있는가?'하는 문제지요.

이런 방법이 일반적으로 있으면 참 좋을 겁니다. 어떤 문제에 대해 가장 짧은 프로그램을 짜는 방법을 발견한다는 이야기니까요. 그런데 결론은 이게 잘 안된다는 겁니다.

러셀이 집합론을 할 즈음에 생각했던 많은 역설 중 베리(Berry)의 역설이라는 것이 있는데, 이건 '단어 100개 이하로는 정의될 수 없는 가장 작은 자연수' 가 무엇이냐는 겁니다. 만약  이 자연수가 발견된다면, 바로 역설이 생겨 버리죠. 왜냐하면 '단어 100개 이하로는 정의될 수 없는 가장 작은 자연수'라는 말이 벌써 이 자연수를 단어 100개 이하로 정의하고 있으니까요. 똑같은 질문을 위의 경우에 던져 봅시다. '복잡성이 N bit 보다 크다는 것이 증명되는 것 중 가장 처음의 자연수는 무엇일까?' 만약 여기서 이 질문이 N bit 보다 작은 프로그램으로 바뀔 수 있다면 바로 베리의 역설이 생겨버리는 걸 볼 수 있습니다.

여기서 보면 위 질문의 답은 프로그램이 어떻게 숫자로 변환되는가와 연관이 있습니다. 이건 또 바꾸어서 말하면 프로그램이 만들어짐을 가능하게 만드는 체계, 즉 그 시스템의 공리계가 어떻게 만들어져 있는가와 관계가 있습니다. 여기서 이걸 위의 힐버트가 처음에 생각했던 계획과 엮어 봅시다. 힐버트는 수학을 하나의 거대한 프로그램으로 만들고 싶어했습니다. 몇 개의 공리가 있고, 거기서 단계적으로 하나씩 하나씩 정리를 증명할 수 있는 알고리즘이 있는 체계를 만들려고 한 겁니다. 어떤 명제가 있으면, 그 명제가 참인지 아닌지 판별할 수 있는 일반적인 알고리즘이 항상 존재해서, 기계라도 (예를 들어 튜링 기계) 그 명제를 증명할 수 있게 하고 싶어했죠. 여기서 어떤 명제를 이 알고리즘으로 증명하는 시간이 엄청나게 오래 걸릴지도 모릅니다. 하지만 알고리즘 자체의 크기는 일정하게 유한해야 합니다.

이를 '복잡성이 N bit 보다 크다는 것이 증명되는 것 중 가장 처음의 자연수는 무엇일까?' 라는 질문에 대입해 보면, 만약 이런 자연수가 공리계 안에 존재한다면 이 자연수를 출력하는 프로그램의 크기는 대략   log₂N +C 가 됨을 볼 수 있습니다. 여기서 log₂N 라는 것은 N 이란 숫자를 쓰는데 필요한 프로그램의 크기이고 상수 C는 이 공리계에서 명제를 증명하는 일반적인 프로그램(알고리즘이 컴퓨터에서 실현화된 것) 의 크기입니다. 여기서 log₂N은 N에 따라 아주 천천히 증가하는 함수이고, 따라서 위에서 말했듯이 N이 (log₂N +C) 보다 커지면 바로 베리의 역설이 생깁니다.

이건 무엇을 말할까요? 여기서 명제와 프로그램은 수학적으로 엄밀히 정의될 수 있는 것입니다. 따라서 논리적 모순이 생기지 않으려면 '복잡성이 N bit 보다 크다는 것이 증명되는 것 중 가장 처음의 자연수' 는 N 값이 (log₂N +C) 보다 커지면 존재하지 않아야 합니다.

자, 재미있는 결론이 나왔습니다. 위에서 상수 C는 공리계에 의해 주어지는 알고리즘의 크기이므로, 어떤 유한한 증명 알고리즘을 가지는 공리계에서도 일정 크기 이상인 대부분의  명제들은 증명할 수 없다는 결론이 도출됩니다. 이것이 바로 알고리즘적 정보 이론 측면에서 본 괴델의 불완전성 정리입니다.  

Chaitin은 좀 더 엄밀하게, N bit 의 공리들을 가진 공리계에선 어떤 명제가 N+C bit 이상의 복잡성을 가졌는가는 증명이 불가능함을 보입니다. 이는 다시 말하면, 어떤 공리들이 있다면 이 공리들을 가지고 증명할 수 있는 정리들의 크기에는 한계가 있다는 겁니다. 명제들의 크기가 공리들 스스로의 크기만큼 커지기 시작하면, 이 공리들은 이러한 큰 명제들을 증명할 수 없습니다. 

여기까지 한참을 돌아왔는데,  이 이론을 바둑에 적용하면 어떻게 될까요?
(마침내!!!!)

간단한 예로 타이젬의 바둑 정의를 보아도 한국기원 바둑 규칙은 웹 페이지로 한 페이지 입니다. 이는 바둑을 구성하는 공리계가 상당히 작은 bit으로 구성될 수 있다는 겁니다. 반면에 바둑의 수순에서 표현될 수 있는 공간은 앞의 글에서 보였듯이 굉장히 넓습니다. 따라서 임의의 유한한 바둑판이라면 얼마든지 이 공리계보다 큰 복잡성을 가진 상황들이 출현할 수 있고, 이럴 때에는 바둑을 구성하는 기본 원칙(공리)로 해결할 수 없는 문제가 생깁니다.

예를 들자면 커다란 바둑판에 거의 무작위적으로 보이는 모양을 만들어 놓고 '이러한 모양에서 이 수가 최선인가?'  같은 걸 물을 때, 아니면 복잡한 수순을 늘어놓고서 '이 수순이 과연 최선인가?' 하고 물을 때, 이 질문의 복잡성이 대충 기본 공리들의 복잡성보다 크면 증명이 안 됩니다, 운이 아주 좋으면 모든 경우의 수를 다 따져서라도 결과가 나오겠지만, 아니라면 기존의 공리로는 해결이 되지 않는 상황도 나올 수 있는 겁니다. 그리고 이 복잡성의 크기는 바둑이 바둑판에 자기 스스로를 표현할 수 있을 정도의 크기입니다.

결론을 내자면, '임의의 유한한 판에서, 기본 규칙들과 모순되지 않으면서 가능한 한 간명한 규칙들을 더해서 놀이의 승부가 결정이 될 수 있도록 (승, 패) 바둑을 정의할 수 있을까요?' 에 대한 답은 '아니오'입니다.  일반적으로 바둑은 정의가 될 수 없습니다!!!
이유는?  바둑은 자연수를 공리화할 만큼 충분히 강력한 공리계이고 (비록 알고리즘적 정보 이론 측면의 증명을 따랐지만), 따라서 괴델의 정리가 바로 적용이 되기 때문입니다.

실제 과거의 한 예로 예전 일본 바둑에서 오청원의 1집 혹은 2집 승이 나온 경우가 있습니다. 자신의 패감이 더 많았기 때문에 판이 끝났을 때 패를 잇지 않은 것으로 기억하는데요, 이는 결국 당시 바둑을 정의하는 규칙들로는 해결되지 않는 상황이 출현했었음을 의미합니다.

한참을 돌아서 마침내 첫 글에서 제기했던 질문의 결론을 내었는데요.
이 결론이 바둑을 더 부정적으로 만드는 것일까요? 제 생각은 오히려 그 반대입니다. 이러한 결론은 바둑을 더욱 풍요하게 만든다고 생각합니다. 사실 괴델의 정리는 사람의 사고의 폭을 아주 확장시키는 듯 합니다. 다음 글에서는 이러한 결론이 어떤 것을 의미하는지 한 번 생각을 주저리주저리 늘어놓아 보겠습니다.
 
*덧붙이자면 위의 결론은 19*19 바둑판에서 바둑이 정의될 수 없음을 보이는 것은 아닙니다. 판의 크기를 고정시킨다면 나오는 판 수는 유한하고, 최악의 경우에는 모든 경우 경우를 다 따져서 바둑을 정의할 수 있습니다. 하지만  일정 크기 이하의 공리들로 '임의의 유한한 판'에서 바둑을 정의하려 한다면 그것은 불가능하다는 것입니다.

마침내 마지막 글이자 앞에서 늘어놓았던 이야기들에 대한 요약 겸 감상을 늘어놓을 생각인데요,
이 글을 쓴 동기에 일조했던 후지사와 9단의 인터뷰를 먼저 올립니다.

-----------------------
2004. 9. 18일, 후지사와 9단의 인터뷰

79세의 고령인 일본의 명예기성 후지사와슈코(藤澤秀行)9단이 ‘후지쯔 후지사와 슈코 명예기성 연구회’ 와 중국기원을 찾아, 많은 바둑관계자를 비롯하여 리우샤오광 9단, 창하오9단 등과 함께 기자 회견을 가졌습니다.

희망이 없느냐 있느냐? - 얼마나 자유롭고 창조적인가의 문제

‘일본 바둑이 왜 희망이 없다고 생각하느냐’는 다소 도발적인 질문에 후지사화 슈코는 다음과 같이 길게 답변했다

"(질문에 대해)이전에 일본 기자에게도 말한 적이 있다. 이는 당연히 정상급 기사들의 문제라고 생각한다. 그들은 마땅히 '바둑이 도대체 무엇인가'를 생각해야 한다. 하지만 내 생각에 아무리 생각해도 답을 찾을 수가 없었다.”

“문제는 일본에서 이런 생각을 하는 사람이 전혀 없다는 것이다. 아마 40, 50년가량 나는 줄곧 이 문제를 생각해 왔다.

  내 생각에 바둑은 자유의 세계이다.

내가 젊어서 일본 연구생일때 스승님께서도 이래서는 안되고 저래서도 안된다고 내게 말씀하셨다. 나는 스승에게 그렇게 다른 사람에게 간섭하지 말고 기사가 자유롭게 실력을 발휘하도록 놔두라고 말씀드렸다.”

“일본의 야마시타게이코는 첫수를 5-5자리에 두는 것을 좋아했는데 처음에는 모두가 그것을 받아들일 수 없었지만 그의 승률이 아주 높아지자 사람들은 천천히 그것을 받아들였다. 만약에 그런 방법으로 매번 진다면 그때 버려도 늦지않는 것이다.”라고 말했다.
----------------------------------

전 이 인터뷰를 읽으면서 잔잔한 감동을 느꼈습니다. 이 노기사는 '바둑이란 무엇인가'에 대한 답을 40-50년 간이나 생각해 왔습니다. 그리고 그는 '바둑은 자유의 세계'라고 말했습니다. 과연 이것이 맞는 말일까요? 아니, 이것이 맞는 말이 될 수 있을까요? 현재의 바둑은 다들 알다시피 승부의 세계입니다. 이긴 자는 모든 영예를 다 얻고, 진 자는 아무 말도 못하고 물러나는 곳이죠. 그래서 프로 기사들은 끊임없이 기술을 연마하고, 칼날을 갑니다. 이런 상황에서, '바둑은 자유다'라고 말하는 것이 허용이나 되는 것일까요? 이미 알려진 기술들을 끊임없이 연마하는 것이 더 좋은 것이 아닌가요?

후지사와 9단의 인터뷰를 보면서, 저는 수학자 칸토르 (G. Cantor 1845-1918) 가 한 말이 생각났습니다. 그는 '수학의 본질은 그 자유에 있다'라고 말했습니다. 칸토르는 '무한'에 대해서 연구하고 그걸 정의한 수학자입니다. 당시의 수학계에서 이런 개념은 받아들여지기 힘들었고, 그는 많은 반대에 부딪혔습니다. 심지어는 나중에 정신병에 걸리기까지 했죠. 그러한 그의 삶과 업적에 비추어, 전  '수학의 본질이 그 자유성에 있다'는 말을 이렇게 이해했습니다. 새로운 개념을 도입함에 있어서, 그 새로운 개념은 단지 그것이 모순이 없어야 한다는 전제 하나에만 제약을 받으며, 모순이 없는 이상은 우리는 자유로이 수학을 확장시킬 수 있다고.

다시 바둑으로 돌아가 봅시다. 이미 바둑에는 알려진 길들이 많이 있습니다. 수많은 정석이 있고, 수많은 포석이 있고, 수많은 알려진 전투와 끝내기의 기교가 있습니다. 이런 것들은 이미 안전하다고 검증받은 길입니다. 처음 바둑판을 대할 때, 때론 변이나 중앙에 첫 수를 두고 싶은 욕망에 사로잡히다가도, 다시 접습니다. 위험합니다. 중앙에선 도저히 수가 읽히지 않고, 한 치라도 어긋났다간 그냥 밀려버릴 것 같습니다. 한 판에 몇 천만원이 오가게 된다면, 더욱 더 알려진 길을 고집하는 것이 낫습니다. 자유의 또 다른 무서운 측면은 불확실성임을 승부사들은 아주 잘 알고 있기 때문입니다.

하지만, 그럼에도 불구하고 아무도 가보지 않은 길로 과감히 뛰어든 사람들이 있었습니다.
오청원의 신포석이 있었고, 다케미야의 우주류가 있었습니다. 사람들이 그들의 성취에 열광했던 한 가지 이유는 그들이 확실성의 안전함보다 불확실성의 자유를 택했기 때문이 아닌가 생각됩니다.
 
과연 자유에 그만한 가치가 있는 것일까요? 안전한 확실성보다 불확실한 자유가 훨씬 소중한 것입니까?

전 이런 '가치'에 대해서는 잘 모르겠습니다. 하지만 한 가지 머리 속에 떠오르는 생각은, 자유라는 것은 바로 사람이라는 개체가 살아가는 방식과 깊은 연관이 있다는 것입니다.

어떤 생명체가 살아갈 수 있는 조건은 우선 계가 비평형이어야 한다는 것입니다. 그리고 그 생명체는 낮은 엔트로피(entropy) 가 높은 엔트로피로 바뀌는 흐름 안에서만 살아간다는 것이 가능합니다. (여기서 엔트로피는 무작위도 (degree of randomness), 무질서도, 혹은 선택의 자유도 (amount of freedom of choice) 로 대략 생각하시면 되겠습니다. 여기선 앞에서 말했던 무작위성(randomness)으로 생각하셔도 될 듯) 예를 들면 사람이 살아가기 위해서는 음식을 먹고 똥을 배설하는 것 같은 흐름이 있어야 하죠. 앞에서 말했던 알고리즘의 비유를 들자면 생명체는 적어도 낮은 복잡성을 가진 입력 (예를 들어 111111111.. 같은 수열) 을 받아서 복잡성이 높은 수열 (101101000111..) 을 출력하고 그 와중에 자신을 조직화하는 프로그램의 측면을 가지고 있습니다. 그런데, 이 생명이란 프로그램은 자기 자신을 조직화하면서 스스로를 성장, 진화시킵니다. 이는 결국 입력을 받아 출력을 하면서 프로그램의 크기를 스스로 증대시킨다는 이야기이고, 바꾸어 말하면 자기 자신의 복잡성을 증가시킨다는 이야기입니다.

  약간은 기묘한 이야기 같은데요, 다시 정리를 하자면 이렇습니다. 이 생명이란 프로그램은 낮은 복잡성을 가진 입력을 받아 높은 복잡성을 가진 출력을 내놓으면서 자기 자신을 성장을 시킵니다. 이 프로그램은 그 자체가 대단히 잘 조직이 되어 있습니다. 이 이야기는 프로그램 크기에 대비한 상대적인 복잡성이 굉장히 낮다는 이야기입니다. 그런데, 아무리 조직이 잘 되어 있어도 프로그램의 덩치가 계속 커지면 필연적으로 절대적인 복잡성의 크기는 증가할 수 밖에 없습니다. 다른 말로는 이 프로그램의 엔트로피가 증가한다는 말이기도 합니다. 앞의 글에서 말했지만, 만약에 이 프로그램이 가지는 복잡성의 크기가 이 프로그램을 구성하는 공리들의 복잡성보다 커진다면 더 이상 이 프로그램을 구성하는 공리들은 프로그램 자체를 소화할 수 없게 됩니다. 프로그램이 자기 조직화를 계속하려면 이 프로그램은 새로운 공리를 추가하면서 '진화'할 수 밖에 없습니다. 여기서 새로운 공리는 유일하지 않습니다. 바둑의 예를 들면 귀곡사를 죽음으로 정의하는 것과 아닌 것이 서로 다르지만 가능한 두 바둑계를 만드는 것 처럼.  여기서 이 자기조직하는 프로그램은 '자유'와 '불확실성'을 가집니다. 어떤 임계 상황에서 새로운 공리를 받아들이는 선택은 외부 상황의 무작위성과 프로그램 자체의 구성이 맞물리면서 예측할 수 없는 방향으로 결정이 됩니다. 그리고, 이 새로운 공리를 받아들임으로 해서 '진화'한 프로그램은 그 전의 프로그램보다 훨씬 복잡해지고, 불확정성은 더욱 증가합니다.

위의 이야기는 엄밀히 증명된 것은 아니고, 제가 앞에서 말한 이론으로부터 유추한 것입니다.
인간의 자아의 확장에도 위에서 말한 것과 비슷한 현상이 벌어지는 것처럼 보입니다.
처음 아이가 태어났을 때에는, 아이는 가장 기본적인 느낌과 감정 정도 밖에는 없습니다.
아이가 차츰 자라고 주위의 정보를 받아들이면서, 아이의 자아는 성장합니다.
그리고 어느 순간, 그 자아는 스스로를 구성하는 기본 원칙을 돌아볼 만큼 성장합니다.
이렇게 느끼는 내가 과연 뭐지? 하면서 자신을 돌아보는 겁니다. 철학에서 데카르트가 '나는 생각한다, 고로 나는 존재한다'고 말했던 바로 그 순간입니다. 자기 자신을 성찰하는 자아는 스스로를 성찰할 수 없습니다. ( 금속탐지기가 자기 자신의 금속을 탐지할 수 없는 것과 같은 이치라고나 할까요.) 하지만, 그 이전에 자신을 구성하고 있던 느낌이나 감정 등은 돌아볼 수 있지요. 이 새로이 커진 자아는 자신을 만들어낼
새로운 법칙를 만들어내면서 한 단계 커져야 합니다. 제 2의 탄생의 순간이죠.

하지만, 이러한 한 단계를 뛰어넘는 성장은 확실하게, 미리 결정되어서 일어나는 것이 아닙니다. 충분히 커져버린 자아는, 다음 단계로 성장하기 위해선 불확실성을 무릅써야 합니다. 자신을 확장시키는 법칙을 더하는 일은 선택을 요구합니다. 그 선택은 좋을 지도 모르고, 나쁠지도 모릅니다. 그러나 확실한 것은, 그 불확실성을 받아들이지 않고는 더 큰 자유와 성장도 없다는 사실입니다.  

지금까지 말했듯이, 인간은 부분적으로 완전을 추구하는 것 같으면서도 전체적으로는 더 큰 불완전을 지향하는 것 같습니다. 이 불완전은 완전보다 더 큰 개념입니다. 진실은 증명될 수 있는 것보다 더 큽니다. 사람의 사고 체계가 성장하면서 끊임없는 불확실성과 선택이 따르지만, 대신 그 곳에는 자유도 같이 있습니다.

바둑의 경우에도 마찬가지입니다. 완전한 바둑을 추구하는 것은 오히려 쉽습니다. 바둑판의 크기를 줄여버리면 간단해지죠. 저 번 글에 썼듯이, 3*3 바둑판에서 신의 한 수를 찾는 것은 상당히 쉽습니다. 하지만 사람은 좁은 공간의 완전을 찾기보다는 자유로운 불완전을 선호하는 것 같습니다. 예전에 중국에서 두던 바둑을 보면 판의 크기는 17*17 이었습니다. 그리고 대각선의 화점에 흑백이 먼저 착수하고 시작하는 것도 있었죠. 하지만 시간이 가면서 사람들은 빈 공간에서 시작하는 것을 선호하게 되었고, 판의 크기도 19*19로 늘었습니다. 점점 바둑의 불확실성은 커지고, 알 수 없는 세계로 들어가게 되었습니다. 그리고, 그런 알 수 없는 세계에서 사람들은 '놀기' 시작합니다. 모든 것이 다 알려져 있으면 재미가 없죠. 놀기 위해서는 불확실성은 확실히 필요한 것 처럼 보입니다.

  이제 글을 마무리해 보겠습니다. 처음에 말했던 질문이었던, 임의의 유한한 판에서, 기본 규칙들과 모순되지 않으면서 가능한 한 간명한 규칙들을 더해서 놀이의 승부가 결정이 될 수 있도록 (승, 패) 바둑을 정의할 수 있을까?' '에 대한 답은 '그렇게 할 수 없다' 였습니다 (괴델의 정리에 따라). 바둑은 이 불완전성으로 인해 열린 계가 됩니다. 판이 점점 커지면서, 바둑은 자기 자신을 판에 투영할 만큼 커지게 됩니다. 그리고 그 순간에 바둑은 다시 성장하며, 그 성장하는 모습은 하나로 정해지지 않으며, 진화의 자유를 가집니다. 이를 볼 때, 바둑은 어떠한 열린 체계, 진화하고 성장하는 어떤 것으로서 정의가 되어야 하고, 바둑을 닫힌 공간에 집어넣으려는 시도는 오히려 바둑의 숨통을 막히게 할 수 있다고 봅니다.

바둑을 두는 사람도 마찬가지입니다. 바둑을 두는 사람은 자신의 생각을 바둑판에 투영합니다. 하지만 바둑판이 그 두는 알고리즘을 온전히 표현할 만큼 커지는 순간, 바둑을 두는 사람은 기존의 알고리즘으론 해결할 수 없는 바둑을 만납니다. 그 순간 바둑을 두는 사람도 다시 진화할 수 밖에 없습니다. 글 (3)에서 말했지만, 바둑을  확률적인 세계에 집어넣고 보는 순간 사람은 수많은 가능성과 만납니다.  그 하나 하나가 바둑이 진화할 수 있는 자유도를 가진 공간이 됩니다. 바둑을 지나치게 하나의 관점 (예를 들어 승부의 관점)으로 몰아넣는 것은 잘못하면 가능성의 싹을 자르는 일이 될 수 있습니다.

제가 보기에는 지금까지 바둑은 열린 계로서 존재해 왔고, 그렇게 진화해 왔습니다.
전 바둑이 앞으로도 열린 계로서 계속 존재해야 한다고 생각합니다. 그리하여, 바둑이 사람의 사고를 표현하는 자유롭고 진화하는 계로서 남기를 간절히 기원합니다.

* 여담이지만, 콘웨이(Conway)는 바둑의 끝내기를 연구하다가 'surreal number'라는 수 체계를 발견했다고 합니다. (초실수라 번역해야 하나...) 대충 이건 무한대와 무한소를 포함하는 상당히 요상한 수 체계인데요   'E. Berlekamp 와 D. Wolfe' 의 'Mathematical Go- chilling gets the last point' 란 책에서 이용한 걸로 압니다. 흥미있는 분들은 보셔도 될 듯. 바둑이 수학의 발전과 게임 이론에 의미있는 공헌을 한 것 같아 뿌듯합니다.

[=] http://blog.naver.com/ysyoo00.do?Redirect=Log&logNo=90019900987