바둑, 정복해야할 마지막 게임

중국 송(宋)시대 바둑두는 모습 ⓒ 위키피디아

 바둑의 기원: 2500년 이상의 역사
바둑의 기원은 확실치 않으나 고대 중국에서 창시된 것으로 추정되고 있다. 제1설은 기원전 2300년경 중국 요순(堯舜)시대 요제(堯帝)가 우둔한 아들인 단주(丹朱)를 교화시키기 위해 바둑을 창시했다는 요순 창시설이 된다. 제2설은 천체도구설로 바둑판과 바둑알을 이용하여 천문을 연구하였다는 설이다.
한편 기록 문화에 철저히 의존하는 서구에서는 바둑이 최초 언급된 기원전 548년 공자의 논어(論語)의 자료를 근거로 바둑의 기원을 보고 있다. 또한 바둑의 한반도 전래설로는 기자동래설(箕子東來說)과 한사군설(漢四郡說)이 있으나 이 역시 문헌의 기록이 없는 실정이다.
바둑의 복잡성: 게임트리 복잡도
1997년 IBM의 컴퓨터 체스 프로그램인 디프 블루(Deep Blue)가 세계 체스 챔피언인 게리 카스파로프(Garry Kasparov)를 물리쳤을 때 수학자를 포함한 전 세계 과학자들은 환호를 외쳤다. 그들은 인간과의 게임에서 컴퓨터가 인간 이상의 생각을 할 수 있는 인공지능(Artificial Intelligence)을 가져다 줄 것으로 기대했다. 그러나 결과는 참혹했다. 컴퓨터는 단지 주어진 게임 공간 내에서 신속하고 정확한 탐색만을 수행했을 뿐 아무런 것도 제시해 주지 못했다.
이에 과학자들은 또 다른 미지의 게임인 바둑에 눈을 돌려 이를 풀려고 시도했으나, 기존의 방법으로는 풀 수 없는 상황에 이르렀다. 그 이유는 체스에 비해 바둑이 훨씬 복잡하기 때문이다. 게임 복잡도는 게임이 얼마나 복잡한가를 나타내며, 일반적으로 상태공간 복잡도(State-space complexity)와 게임트리 복잡도(Game-tree complexity)로 설명이 된다.

체스와 바둑의 복잡도 비교 ⓒ 이병두

19줄 바둑에서 착점 가능한 곳은 (1 )개가 되며, 한 곳당 흑, 백, 빈 공간 등 세 가지 상태로 구성되기 때문에 상태공간 복잡도는 (2 )이 된다. 또한 게임트리에 있어 가짓수(branching factor)는 평균 200 이내가 되며, 게임깊이(game depth)는 평균 250∼300이내가 되기 때문에 게임트리 복잡도는 (3 )이 된다.

이와 같은 게임 복잡도로 인해 단순한 탐색방법으로는 풀 수가 없기 때문에 최신의 인공지능 기법인 인공신경망(ANN: Artificial Neural Network), 강화학습(Reinforced Learning), 진화연산(Evolutionary Computation) 등으로 시도를 하였으나 그 결과는 부진하였다.
즉 현재의 수학 및 과학 기술로는 풀 수가 없는 상황에 이르렀다.
수학으로 바둑 풀기: 초현실수

끝내기 상황에서 흑선인 경우 A, B, C, D, E 각점의 값어치에 따라 흑은 E점을 우선적으로 두어야 한다. Mathematical Go

영국의 수학자 존 콘웨이(John H. Conway)는 1969년 게임이론의 여러 현상을 설명하기 위해 초현실수(Surreal number)를 창안하였으며, 이를 통해 바둑의 끝내기를 풀려고 시도했다.
바둑의 끝내기에서 패와 사활의 문제가 없거나 흑백간의 영역이 독립적인 경우에 초현실수를 적용하게 되면 끝내기 수순을 정확하게 계산해낸다.
한 예로 우측의 끝내기 상황에서 흑선인 경우 A, B, C, D, E 각점의 값어치는
가 되어, 흑은 E점을 우선적으로 두어야 한다.
새로운 방법 절실: 범용 알고리즘
바둑은 세 단계인 포석, 전투, 끝내기로 진행되며, 한 단계에서 적용되는 기법이 전 단계에 걸쳐 통용되지는 않는다. 바둑에서 중요한 개념으로는 형세판단과 수읽기가 되며, 특히 형세판단은 승패를 좌우하기에 정확한 계산이 이루어져야 한다.

흑에게 유리한 포석(1-47) ⓒ이병두

좌상과 같은 포석의 장면에서 프로기사는 흑백간의 우위를 정확히 계산해 내어 새로운 전략(Strategy) 및 전술(Tactics)을 시도해 낼 수 있으나, 기력이 약한 아마 기사들은 형세판단이 안 되어 이를 시도할 수 없다.포석에 적용된 방법이 전투나 끝내기에서 적용되는 것은 아니다. 결국 인간과의 대결에서 컴퓨터 바둑이 승리를 하기 위해서는 전 단계에 걸쳐 통용되는 새로운 기법이 절실하다.
또 다른 시도: 몬테카를로 트리검색

각 착점의 승리확률 ⓒ이병두

몬테카를로 방법(Monte-Carlo method)은 난수를 이용하여 함수의 값을 확률적으로 계산하는 방법이다. 계산하려는 값이 수학적 형식으로 표현되지 않거나 아주 복잡한 경우에 근사적인 값을 계산하기 위하여 사용된다.
특히 인공지능 게임분야에 있어 성공적인 결과를 보였으며, 현재는 바둑에 몬테카를로 트리탐색(MCTS: Monte-Carlo Tree Search)을 적용하여 놀라운 성과를 내고 있다.
한 예로 MCTS를 삼목(Tic-Tac-Toe)에 적용하게 되면, 우상에서 보듯이 중앙 첫 착점의 승리 확률이 50.6%가 됨을 10만 번의 시뮬레이션을 통해 알 수 있다. 즉 첫 착점으로 중앙이 가장 좋고, 그 다음은 귀가 되며, 변은 제일 나쁜 착점이 된다.

MoGo와 CrazyStone과 같은 강력한 컴퓨터바둑 프로그램은 이미 9줄 접바둑에서 프로기사들을 제압하였고, 2008년부터는 19줄 바둑에서도 9점에서 6점 접바둑으로 하향되는 등 많은 선전을 하고 있다.
이러한 추세를 감안하여 일부 과학자들은 아마도 30∼50년 이내에 컴퓨터가 인간을 제압할 수 있을 것으로 조심스레 전망하고 있다.
바둑과 수학: 또 다른 이론 탄생 기대
바둑이 많은 수학자나 과학자에게 흥미로운 연구영역이 되는 주된 이유는 연구결과를 쉽게 확인할 수 있으며, 필요시 프로기사에게 연구결과에 대한 정확한 평가를 받을 수 있기 때문이다.
아울러 바둑은 무한의 복잡도를 갖고 있어 마치 현실세계와 유사한 현상을 보이는 장점이 있다.
이와 같은 복잡한 현상을 풀기 위해서는 기존의 이론으로는 어렵기 때문에 또 다른 새로운 이론의 탄생을 기대해 본다.
 

•  ScienceTimes