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

1.
일단, 제한된 시간 동안 게임이 끝나지 않으면 무승부라고 가정하겠습니다.

체스와 바둑의 말-이동은 모두 2차원 좌표 위에서 표시됩니다. 그리고 두 게임 모두 게임 종료를 정의하는 규칙을 가지고 있습니다. 이러한 요소들을 고려하면, 말-이동을 표현하는 [형식] 문법을 얻을 수 있습니다 -- 이 [형식] 문법을 G라고 부릅시다. 특별히, 시간 초과로 생긴 무승부를 생각해보면, (1) 무승부는 말-이동을 기술하는 string의 길이가 상수 N보다 클 때 선언되며[*], (2) 그때 G를 accept하는 automaton이 halt되기 때문에, 무승부가 있는 게임 자체는 계산가능합니다.

보다 정확히 말하자면, 무승부를 포함한 게임의 승부를 결정하는 것은 computable합니다. 실제로는 시간이 초과한 쪽이 지도록 되어 있을 것입니다. 그렇다면 무승부라는 state 대신 그 turn에 말-이동을 하도록 되어 있는 쪽이 졌다고 선언하게 하면 됩니다.

2.
앞에서 설명한 것은 이 토론이 무엇에 초점을 맞추어야 하는가, 라고 질문하기 위해서 입니다. "바둑은 계산이 아니다"라는 문제가

 I. 바둑의 승부를 판정하는 것이 computable한가
 II. 바둑의 winning strategy가 computable한가
 III. 바둑의 winning strategy를 만들어내는 것이 computable한가

가운데 어떤 것과 관련있는지 또는 어떤 것으로 환원되는지 분명하지 않습니다.
I에 대한 대답은 1에서 스케치 된 대로 "그렇다"입니다. 무승부를 인정하지 않을 때 winning strategy는 반드시 시간 내에 말-이동을 계산해야 하므로, II에 대한 대답은 "그렇다"입니다. 따라서 III이 [철학적으로] 의미있는 질문이라고 생각합니다.

3.
만주인님이 이렇게 쓰셨습니다:

 I. 게임은 목적을 가졌다는 점에서 단순 계산과는 다를 겁니다.
 II. 어떤 과학잡지를 보면 지금까지의 컴퓨터의 연산방식은 직렬방식인데, 이게 병렬방식으로 바뀌면 인간의 사고과정을 모방할 수 있을 거라는 이야기가 있더군요.

먼저 II에 대해 생각해보면, 병렬이건 직렬이건 계산가능성은 차이가 없습니다: 다시 말해, 병렬 계산 모델에서 계산가능하면 직렬 계산 모델에서도 계산가능하고, 반대는 정의에 의해 당연합니다. [이참에 Turing-Church thesis에 대해서도 찾아 보세요.]

2-I~III을 생각하면, I은 잘못된 질문입니다. 질문을 고치자면, 문맥 상 그 의도를 추측해볼 때, 이렇지 않을까 싶습니다:

 III. 게임의 winning strategy를 만들어 내는 것은 [Turing-]computable하지 않다.

이 명제가 참인가 거짓인가 결정하는 것은 무척 힘들지만, 이 명제로부터, 적어도, [수학적] 게임의 범위를 결정하고 그것들을 분류할 필요가 있다는 것은 알 수 있습니다.
이를 테면, 사람들이 둘러 앉아 하는 "삼/육/구" 게임은 여기서 생각하는 게임에 포함시키면 안 될 것입니다. 이 게임에서는 참가자들 -- 여기서는 컴퓨터 또는 계산모델 -- 가운데 누가 가장 먼저 시작할 것인가를 결정하는 것이 승패를 결정하니까 winning strategy가 없는 게임입니다. 특정 참가자가 항상 이길 수 있게 하는 알고리즘이 없는  이런 게임은 굳이 생각할 필요가 없겠죠. 만일 게임이라는 범주에 그런 게임들까지 넣는다면, III은 undecidable한 명제가 됩니다.

4.
요즘 combinatorial game theory가 많이 연구되고 있습니다.
http://www.msri.org/activities/events/9900/gametheory/cgt-info.html
제 관심을 끄는 것은 MIT의 Professor E. Demaine이 보인 다음 결과입니다:
http://theory.csail.mit.edu/~edemaine/papers/Tetris_TR2002/
[제가 1에서 제한된 진행 시간을 갖는 게임을 설명하면서 무승부를 가정했는데, tetris가 NP-complete이며 심지어 근사조차 할 수 없는 것이 끝이 없는 게임이기 때문이 아닌가 하는 생각을 갖고 있어서 그랬습니다. 일단 무승부를 도입하면 논의를 전개하기가 더 쉬워진다고 생각했으니까요.]
시간 제한으로 무승부를 선언하면 최종적인 승패무를 항상 결정할 수 있지만, 그렇지 않을 경우에는 단지 얼마나 오래 버티느냐, 즉 문제 해결 전략의 time complexity가 얼마나 작은가에 의해 승패가 결정됩니다. 그럴 경우, 굳이 게임을 하지 않고도 알고리즘의 time complexity를 꼼꼼하게 계산하면 승자를 알 수 있습니다.

5.
승패결정이 decidable한 2인 게임 H를 생각해 보죠. 이 게임은 tetris처럼 제한 시간이 없고, 누가 먼저 지는가로 승패를 결정한다고 가정합니다. 또 아직까지 winning strategy가 발견되지 않았고 심지어 그에 대한 근사조차 불가능하다고 가정합니다. 편의상, 이 게임이 Scheme-computable하다고 가정합니다 [Scheme은 Lisp을 닮은 functional programming lanugage입니다. http://www.schemers.org 참고]. 게임 H의 승패를 결정하는 프로그램 A를 Scheme으로 작성된 Scheme interpreter B로 돌립니다. 그리고 프로그램 A에 프로그램 C, D를 입력으로 하고, 각 프로그램은 게임 플레이를 진행할 알고리즘을 각각 구현한 것이라고 가정합니다.

각 요소들이 인간 정신의 창조물인 것은 틀림없지만 -- 정말? -- 게임 진행 자체는 기계적 절차에 의해 수행됩니다. 그렇다면, 이 기계적 절차가 그 자체로 어떤 목적이 있다고도 볼 수 있을까요? 만일 그렇다면 [Turing-]computable한 모든 알고리즘은 모두 "목적적인" 것인가요?

6.
굳이 게임의 계산가능성에 대한 논의에 "인간 정신"을 끌어 들이지 않고, deterministic winning strategy와 nondeterministic winning strategy의 차이점을 생각하는 것도 괜찮을 것이라고 봅니다. 기회와 시간이 주어진다면 저는 interactive winning strategy에 대해 생각해보고 싶습니다. Interactive winning strategy란 oracle과 interaction을 하며 게임을 승리로 이끄는 알고리즘입니다. 여기서 Oracle은 어떤 질문에 대해 항상 답을 주는 계산 모델 상의 요소를 말합니다 -- 보통 암호론에서 많이 논의하는데, 요즘은 quantum computing하는 쪽에서도 많이 논의하더군요.
http://www.wordiq.com/definition/Interactive_proof_system
http://encyclopedia.thefreedictionary.com/oracle%20machine
--
[*] 정확하게 말하자면 이렇습니다. 먼저 제한 시간을 N 단위시간이라고 합니다. 각 말-이동은 단위 시간당 기껏해야 한번 가능하다고 합니다 -- 한번의 말-이동을 위해 여러 단위 시간을 쓸 수도 있으니까요. 이때 말-이동은 최대 N번 가능합니다. 따라서 G를 accept하는 automaton은 입력 string의 길이가 N+1이면 무승부 state를 가리키고 halt되도록 하면 됩니다.
--
In terra pax hominibus bonae voluntatis.

_ 착한왕 : 키쵸? 드뎌 나타났군!^^
반갑고 수학자가 우리 대열에 합류한다면 달리는 말에 날개를 다는 겪!

이 문제에 고심하는 이유는 궁극적으로 두되의 각 모듈단위의 연결을 일괄적으로 제어하는 메타 알고리듬을 부정하고 그 대신 모듈 혹은 하부 알고리듬 사이의 연결 방식을 제한하는 환경 변수를 끌어들임으로써 두뇌 진화의 새 접근법을 만들려고 하는 것임! 나는 성공한다는 보장이 없고 수학자라면 관점만 바꾸면 의외로 쉽게 풀 수 있을지도 모른다는...~! 진화론과 관련해 알고리듬이 환경 구조와 무관하게 자연선택된 것이라는 주장은 내가 보기에 너무나 비상식적이고 무책임한 가설인데, 일단 이 문제는 접도록 합시다. 이런 문제까지 다루기 위해서는 먼저 카쵸님의 답변에 대한 제 답변을 달겠습니다.

키쵸님의 답변과 유사한 내용을 computaion, simulation, heurisics 개념을 가지고 다시 구성하겠습니다

- Gravi : 모듈 혹은 하부 알고리듬 사이의 연결 방식을 제한하는 환경 변수를 끌어들임으로써 두뇌 진화의 새 접근법을 만들려고 하는 것임 -> 에 대해서 조금만 자세히 설명해 주세요. 잘하면 공짜로 졸업논문을 쓸 수 있을 것 같아서 :)

-

만주인 : 갑자기 게임이론에 대해 관심이 가게 되네요. 좋은 답변 감사합니다만, 기왕에 질문을 하나 더 해도 되겠습니까? 게임을 하는 두 주체, A, B는 서로 한쌍의 수를 교환하죠. 그리고 이 한쌍의 과정은 다음과정의 두번째 쌍의 원인이 되죠. 즉 A가 낸 수 a는 B가 낸 수 b와 대응되죠. 그런데, B가 낸 수 b는 다시 A가 내는 두번째 수 a'와 쌍이 되죠. 이것을 정리하면 a->b, b->a', a'->b'.... 이렇게 될라나요? 이 경우 첫 수인 a-b의 선택은 무작위에 가까울 겁니다. 왜냐? 선행하는 a!-b!가 존재하지 않으니까요. 그런데 다음 과정인 a'-b'은 첫단계의 a-b와 어떤 인과적 관계는 성립한다고 볼 수 있을 겁니다. 그러나 a'-b'에 대응하는 다음 과정인 a''-b''은 단 하나뿐이 아니라 다수가 존재하고 여기서 게이머의 역할은 성립 가능한  여러 a''-b''중 하나를 선택하는 것일 겁니다. 이러한 선택의 경우의 수가 적으면 적을수록 그 게임은 비교적 단순해지겠죠. 반면 그 수가 복잡하면 복잡할 수록 그 게임은 복잡한 대신 재미가 있을 겁니다. 키쵸님이 말씀하시는 방식으로 게임을 계산(?)할 경우, 그 선택행위는 어떻게 이루어지나요? 단순히 무작위 선택일까요? 아니면 그마저도 선행하는 어떤 다른 규칙에 의해 결정되게 하는 걸까요? 제가 영혼이라는 부정확한 말을 쓰는 것은 그런 점과 관계는 있습니다. 물론 현재 논의되고 있는 게임이론이 그런 문제는 부차적으로 보는 거라면, 저의 질문은 선문답이 되겠지요? 또 한가지 게임을 종결시키는 방식을 시간초과로 설정하셨는데, 실제 인간이 하는 게임의 양상을 보면 물론 시간초과가 게임종결의 규칙인 경우도 있지만, 그렇지 않은 경우가 더 많죠. 예를 들어 장기와 같은 경우 상대방의 왕을 잡는다면 단 한수만 두더라도 게임 오바입니다. 이럴 경우 게임의 종결을 선언하는 규칙은 다수의 해가 나오는 방정식으로 설정될 수 있지 않을까요? 예를 들어 왕을 잡는 경우의 해를 0으로 하고 그렇지 못한 경우는 1이나 2의 해가 나오게 해서 0의 해가 나올때까지 계산을 반복하게 한다... 뭐 이런 식의 계산방식도 가능하지 않을까요? 이건 그냥 질문입니다. 너무 심각하게 생각하지 마세요.

*
[=]  http://goodking.new21.net/bbs/index.php