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

1
착한왕님과 bud1027님이 지적하신대로, 체스와 달리 바둑은 게임진행 초반에서 앞으로 게임이 전개될 기초가 되는 작업을 해야 합니다 -- "포석". 따라서 move를 체스처럼 각 말에 정해진 move 규칙에 따라 게임을 진행하는 것으로만 본다면 move는 바둑에서 아무런 의미가 없게 됩니다.
그러나 제가 쓴 글에 나오는 move는 말이 board 위에 미리 놓여져 있든 아니든 게임에 사용된 말의 정보를 가리킵니다. 즉, 말이 게임에서 어떻게 사용되었는가를 기록한다는 것입니다. 반상에 정해진 좌표와 착수된 돌이 사석인가의 여부 등을 move로 봐야 한다는 말입니다. 따라서 move 자체는 board에 미리 돌이 놓여 있는가와 관계 없습니다.

2.
오해를 피하기 위해 밝혀두겠습니다. 바둑의 승패를 verify하는 것과 실제로 바둑을 진행하는 것은 전혀 다른 개념에 속하는 문제입니다. interactive proof system에서 보자면 [*] 바둑의 승패를 verify하는 것은 verifier, 바둑을 진행하는 것은 prover의 문제라고 볼 수 있습니다. [**] 이렇게 설정하려면, 먼저, 문제가 무엇인가 제대로 정해야 합니다만 -- 계속 생각할 문제입니다.

3.
착한왕님이 언급하신 명제

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

를 좀 다르게 생각해보겠습니다. 제가 바둑의 기본적인 규칙 밖에 모르기 때문에, 제게 친숙한 게임인 sokoban을 가지고 말하겠습니다. [#]

sokoban은 puzzle, 즉 one-party game입니다. 이것을 다음과 같이 two-party game으로 확장합니다.

1. prover는 게임이 진행할 board와 configutaion (B, C)를 정한다.
2. verifier는 (B, C)가 valid한지 결정한다. valid하지 않으면 prover 승리.
3. prover가 (B, C)으로 게임을 진행한다. 답을 못 찾으면 verifier 승리.

이 문제는 아직까지 open problem입니다. :-) 문제는 2에서 validity를 결정하는 것이 어렵다는 것입니다. sokoban은 PSPACE-complete로 알려져 있습니다. [첨부화일1]

포석을 이와 같이 미리 게임을 세팅한다 정도로 이해할 때, 포석은 PSPACE-complete하거나 더 힘든 계산이 될 것입니다. 물론 이렇게 말한 것은 바둑이 EXPTIME-complete하지만 sokoban은 PSPACE-complete하다는 것을 전혀 고려하지 않고 말한 것입니다.

이런 분석들은 가능한 게임의 configuration을 모두 search하기 때문에 계산이 힘든 게  아닌가, 라고 생각하고 있습니다. 따라서 저는 직관이 search할 대상을 줄이는 기능을 하는 게 아닐까, 이렇게 추측하고 있습니다.

A.
돌아다니다가 이런 걸 건졌습니다.
http://black.csl.uiuc.edu/~krohloff/publications/krohloff/CSD_2003.pdf
--
[*] interactive proof system에 대해서는 다음을 참고
http://www.wisdom.weizmann.ac.il/~oded/book1.htm
Lecture 11 in http://www.wisdom.weizmann.ac.il/~oded/cc99.html
[**] 아니면 이렇게도 볼 수 있습니다. P에 속하는 문제는 쉽게 답을 찾을 수 있는 문제이고, NP에 속하는 문제는 그 문제에 대한 답을 쉽게 verify할 수 있는 문제.
[#] 직접 해보시려면 http://www.high-speed-software.com/sokosave/intro.php 에서 다운로드하실 수 있습니다.

*
uberkitcho님의 글입니다.
두뇌는 실제 그런 서치 대상을 줄이는 기능을 갖고 있습니다. 소위 '인지적 지름길'! 이런 인지적 지름길 기능이 없다면 생존하기가 매우 힘들거든요. 생존은 환경 문맥과 고나련되기에 진짜 인간 마음을 닮은 기계는 '환경 적응 역사'라는 것을 어떻게든 기억 장치에 갖고 있어야 할 겁니다. 기거렌쩌가 주장했듯, 그리고 인공지능의 대부인 허버트 사이몬이 지적했듯, 실제 인간의 판단은 검색에서 많은 변수를 무시하고, 이에 의해 역르로 신속한 문제 풀기가 가능해집니다. 우리가 야구공을 잡으려고 공의 위치 속도 모두를 고려해 계산한다면 공메 맞아 코뼈가 부러집니다.(기거렌쩌의 말) 단지 공을 보고 잡는 것이고, 그 안에는 응시 각도가 일정하게 유지된다는 환경 변수가 다른 변수를 고려하지 않게끔 만듭니다. 아주 얇은 사이몬이 쓴 합리성에 관한 책이 있는데, 사이몬이 자신의 초기 인공지능 이론에 비해 그 후의 진행방향은 잘못되었다는 식의 뉘앙스를 풍깁니다.

인간을 prover로 본다면 인간을 알기 위한 테스트 기계로서 컴퓨터 및 계산이 이용되어야 하는데, 계산에 동원되는 이론을 가지고 인간이 이렇다 저렇다 선 판단하는 것이 사이몬에게 못마땅 했겠죠.

와이즈맨의 사이트는 좋은 자료로 보입니다. 찾느라 애쓰셨습니다. NP에 속한 문제의 답은 쉽게 verify할 수 있지만, 인간의 경우는 그 답 찾기 과정은 지적하신 대로 구별되어야 합니다. 그 답 찾기 과정은 단순한 계산이 아니라 환경 문맥에 의존하는 인지적 지름길로서 일종의 직관관 관련되며. 그것이 무엇인지 찾아나감으로써 인간과 기계의 사이를 좁히는 것입니다. 우리가 우리 자신을 알지 못하기 때문에, 이렇게 함으로써 점진적으로 우리 마음을 조금씩 파헤쳐 나가야 할 것 같습니다.

- 착한왕 [2004-11-12 13:55:49]
자 이제 이정도만 해도 꽤 정리할 분량이 많습니다. 이것만 제대로 정리해도 게임의 결과를 놓고 덤 계산에 의존해 경매 가치를 알에 매겨 바둑과 체스의 차이를 구별하는 방식보다는 좀 더 본질적인 구별 방식이 얻어진다고 여깁니다. 방학 때 한번 오프라인으로 모여서 그간 각자 정리한 것을 토론해보고, 대책을 마련해야 할 듯 싶어요.

uberkitcho [2004-11-12 15:34:45]
Oded Goldreich는 제가 관심있는 분야 -- pseudorandomness, zero-knowledge argument, probabilistically checkable proofs - 에서 일급 전문가입니다. 그리고 제가 발표했던 논문의 thesis를 부정하는 논문을 내놓아 다음 논문 한개가 리젝 먹게한 사람이기도 합니다. ㅋ 뭐, 리젝 먹은 다음다음해 컨퍼런스에서 발표된 논문들 중 하나에 그 논문이 인용되기는 했지만. ㅋ

Oded Goldreich와 Madhu Sudan -- 2002년 Nevanlinna Prize 수상자, 그 유명한 필즈 메달의 이론전산분야 메달입니다 -- 은 제가 가장 좋아하는 이론전산학자들입니다.

착한왕 [2004-11-12 15:51:50]
골드라이히가 암만 뛰어나도 진짜 인간 판단 방식과 유사한 이론을 수학적으로 모델링하면, 골드라이히는 별볼일 없어집니다. 그의 이론을 아직 첵크를 완전하게 하지 않았지만, 기존의 이론이 굳어질 수록 수식은 어려워지고 복잡해집니다. 그의 상호작용 증명 체계도 기존의 이론보다 조금은 더 현실 세계에 맞아보이기 때문이고, 제가 보기엔 여전히 상식적인 인간 판단 방식의 많은 측면을 빠트리고 있다고 봅니다.

uberkitcho [2004-11-12 16:40:32] 위 코멘트는 그냥 제가 좋아하는 학자의, 이미 알고 있던 자료들이라 별로 애쓰지 않고 자료를 인용했다는 의도에서 쓴 겁니다. interactive proof system은 원래 수학자들이 하는 proof를 다루는 것이 아니라, 비밀번호와 같은 string을 안전하게 주고 받기 위해 고안되었습니다. zero-knowledge system은 IPS 중에 하나입니다. 여기서 zero-knowledge란 통신한 내용을 가지고 새로운 지식 -- 보통 암호학적 key나 인증에 필요한 지식 -- 알아 낼 수 없는 상태를 가리킵니다. 다시 말해, 도청을 당하더라도 통신을 하고 있는 당사자의 지식을 도청자가 알아 낼 수 없게 하는 프로토콜을 가리킵니다. 때문에 IPS에서 말하는 proof는 "신원증명"과 비슷하다고 보면됩니다: 즉, "내가 정당한 사용자이다"나 "내가 이 시스템을 정당하게 쓸 수 있는 사용자"와 같은 것을 증명하는 것입니다. 그래서 이 분야에서 말하는 지식도 보통 말하는 지식이 아닙니다: 스마트카드 같은 데 들어 있는 데이터 그 자체나 인증 회로의 구조이 여기서 말하는 지식이 될 수는 있지만요. 이 분야에서 직관이나 직관적 발견법이랑은, 적어도 아직까지는, 전혀 관련없는 연구만이 진행되었습니다. :-) 그런 함축을 갖는 논문도 저는 본 적이 없습니다. 참고로, IPS이나 PCP는 암호론 말고 complexity 쪽으로 몇 가지 중요한 함의들이 있습니다: IP, ZPP, BPP. 그 때문에 Sudan이 2002년 Nevanlinna Prize를 수상한 것 같습니다.

*

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