[=] 바둑은 계산이 아니다(답변4)

0.
제 글에서 쓰인 winning strategy란 게임을 진행하는 알고리즘 가운데 특정한 party가 반드시 이기게 하는 것을 가리킵니다. 정의에 의해, winning strategy를 사용한 쪽은 상대방이 누구든지 간에 winning strategy에 적당한 입력을 넣으면 반드시 이깁니다. 물론 그렇다고 해서 winning strategy를 이용해서 항상 이긴다는 보장은 없습니다. 이를 테면, 그 strategy를 쓰기 위해 필요한 매개변수가 완전히 갖춰지지 않는다면 그렇습니다.

1.
먼저, 시뮬레이션에 대해 말씀드리겠습니다.

착한왕님은 이렇게 쓰셨습니다:

"일단 승부가 난 게임은 컴퓨터 시뮬레이션이 가능합니다. 이러한 컴퓨터 시뮬레이션이 가능하다는 것은 그 게임에 담긴 전략들을 시뮬레이션 혹은 모방 가능하다는 것인데, 이것이 실제 컴퓨터가 그 전략을 계산하는지 혹은 그냥 그 전략을 묘사하는 것인지를 맞바로 결정하지는 않습니다. 그냥 말 이동을 사진 뜨듯 복사해내는 알고리듬이 가능하고, 이런 알고리듬의 계산 가능성은 실제 게임에서 행해진 전략의 계산가능성과는 다릅니다. 따라서 게임의 전략이 계산가능한가와 게임을 시뮬레이션하는 것은 다르며, 시뮬레이션 가능하다고 하여 실제 게임의 모든 전략이 가능하다는 결론이 바로 도출되지는 않습니다."

계산가능한 게임들을 다시 진행하는 것은 게임의 기록을 다시 한번 계산하는 것에 불과합니다. 때문에 시뮬레이션이라는 말이 정확하지 않습니다. 이와 같은 과정을 시뮬레이션이라고 하려면 게임에 대한 명제 P(n)을 제대로 분석하기 위한 정보가 부족해서 random number를 발생시켜 P(n)을 테스트해야 하는 상황을 상정해야 합니다. 그런 의미에서라면, 착한왕님이 말씀하신대로 "*실제* 게임의 모든 전략이 가능하다는 결론이 바로 도출되지는 않습니다." [강조는 uberkitcho]

제가 줄곧 게임의 형식적 측면이라든가 수학적 게임을 논한다며 논의의 대상을 좁히려고 한 것은, 풍부한 게임의 사례에 대한 분석이 선행되지 않으면 제대로 된 분석을 할 수 없어서 입니다. 그렇다고 해서 *실제* 게임에 대한 논의의 가치가 낮게 평가되어서는 안 됩니다.

때문에 착한왕님이 제기하신

"문제는 과연 승부를 판정하는 것이 계산가능하다고 하여 시뮬레이션 가능한 바둑의 모든 전략이 계산가능할까입니다. 무승부가 없는 경우 말 이동만의 계산가능성만으로 이뤄진 게임이라면 그렇습니다. 여기서 저의 문제는 바로 이겁니다."

문제는 이렇게 볼 수 있습니다. 먼저, 승부를 판정하는 것이 계산가능하다고 해서 계산가능한 바둑의 winning strategy가 가능한가, 라는 질문은 "아니다"입니다. 아직까지 classical Turing machine -- 아니면 sequential RAM -- 에서 deterministic factorization은 불가능합니다 -- 계산불가능하다는 뜻이 아니라 아직까지 알려지지 않았다는 뜻입니다. 반면에 deterministic primality test는 가능합니다 [*]. 따라서 주어진 게임이 승부를 판정하는 것은 primality test로 reduce되고, 그 winning stretegy는 factorization이라면 -- RSA의 private key를 찾는 게임이 구체적인 사례가 되겠네요 -- 착한왕님 명제의 한 가지 사례가 됩니다. 이에 대해서는 첫번째 첨부화일을 좀 더 검토해볼 가치가 있습니다.

2.
착한왕님의 명제

"초기 포석 또한 계산이다. 그것은 바둑알의 이동에 국한된 계산이 아니라 다른 변수를 포함한 두뇌의 계산이다."

를 증명하려면 초기 포석을 수학적으로 정의하고 뒷 문장이 요구하는 조건에 맞는 알고리즘을 찾아야 합니다. 그러려면 "두뇌의 계산" 모델을 먼저 제시해야 합니다.

3.
"삼/육/구" 게임은 이렇습니다. 적어도 4명의 사람이 둘러 앉습니다. 맨 처음 시작할 사람을 정하고 시계방향 -- 또는 반시계방향 -- 으로 돌아가면 자연수를 하는 데 1씩 증가시켜 말합니다: 첫번째 사람은 1, 두번째 사람은 2, ... . 이때 3의 배수를 말할 차례에 있는 사람은 말할 차례가 된 3의 배수가 아니라 다른 말로 바꿔 말해야 합니다. 이 게임은 이 규칙을 깨는 사람이 나올 때까지 진행합니다. 다시 말해, 이 게임은 "실수"로 끝나게 됩니다. 따라서 컴퓨터 만으로 이 게임을 진행한다면 무한루프에 빠지게 됩니다.

4.
착한왕님의 질문

"Troubling Problem: 체스의 경우 말 이동은 특정 형식문법 G에 의해 string들로 구현된다. 사실 1차원 직선 형태로도 그 string들을 나열해도 된다. 마치 백터(vector) 개념이 등장하기 전의 고전물리학에서 물체의 실제 이동 경로를 무시한 것과 같다. 체스는 기본적으로 알고리듬에 의한 계산에 근거한 게임이므로, 체스 경기가 구현될 체스판의 초기 칸수와 모양은 그런 1차원 string들로로부터 끄집어 낼 수 있는 혹은 시뮬레이션 가능한 패턴이다. 과연 바둑도 그럴까? 곧 바둑에 등장하는 기본적인 형식문법에 근거한 알들의 이동 string들을 통해 역으로 초기 바두판의 패턴을 시뮬레이션해낼 수 있을까?"

은 일종의 inverse problem이네요. 이것을 value slicing이라고 부르고 지금 연구 중인 것 같습니다: 두번째 첨부화일을 검토해볼 가치가 있습니다.

5.
제가 쓴 글에 gap이나 정의없이 쓴 것이 있으면, 편하게 생각하시고 지적해주시기 바랍니다. 이런 변명은 좀 그렇습니다만, 여러 가지에 치이고 있어서 꼼꼼하게 쓴 글을 다시 검토할 시간이 없어서 그렇습니다.
--
[*] 다음을 참고 하세요.
http://ego.kaist.ac.kr/~kitcho/thewnote/1/archives/2004/10/the_search_for.html#more
http://www.cse.iitk.ac.in/news/primality.html
--
In terra pax hominibus bonae voluntatis.

- 착한왕 [2004-11-03 16:54:02]
답변 감사!
먼저 다음은 제 명제가 아닙니다.
"초기 포석 또한 계산이다. 그것은 바둑알의 이동에 국한된 계산이 아니라 다른 변수를 포함한 두뇌의 계산이다."
저는 위 명제를 거부합니다. 그러니까 두뇌의 여러 알고리듬들이 어떻게 계산없이 연결 가능한가에 관심을 갖겠죠.
답변만을 본다면 두 번째 파일이 직접적으로 도움을 줄 것 같은데 검토해 보겠습니다. 다만 이제 나이가 먹어서 그런지 갖고 있던 수학적 능력마저 퇴화한다는 ....
 
uberkitcho [2004-11-03 16:56:37]
네 제가 잘못 썼습니다. "착한왕님이 언급하신"으로 써야 맞습니다.

착한왕 [2004-11-03 17:18:37]
바둑의 직관을 수학을 이용해 드러내겠다는 것과 계산가능성과 복잡성을 가지고 게임의 여러 측면을 접근 혹은 규정하는 것은 다른 것 같습니다. 수학을 이론 만들기의 도구로 여기는 울람의 관점 속에서 후자의 문제와 무관하게 전자를 위한 매우 단순한 math. tool을 찾아보겠습니다. 가능한지는 모르겠지만....