해외화제 컴퓨터와 체스

[동향 소식 p.136–138] 컴퓨터와 체스

• 컴퓨터와 체스p.136–138

  86년 7월, 서부 독일의 코로너시에서는 세계의 내노라 하는 실력자들이 모여 세계 체스 참피온 자리를 두고 경합을 벌였다. 그런데 이 대회에서 가장 각광을 받은 인물은,「하이테크」라는 컴퓨터였다. 이는 카네기멜론 대학의 한스 베를리너와 칼 에벨링이 만든 컴퓨터로, 지난해 다른 훌륭한 컴퓨터들을 제치고 북미 컴퓨터 체스 선수권 대회에서 우승한 바도 있다(이것은「하이테크」가 세계의 어느 컴퓨터 체스 선수보다 우수하며, 99%의 인간보다 적어도 체스 분야 만큼은 뛰어나다는 의미를 지닌다).

  「하이테크」의 비밀은 다른 어떤 체스 기계보다도 2배나 빨리 연산을 수행한다는 데 있다. 매초 175,000회씩 체스판 위의 말들의 위치를 예상해 볼 수 있고, 3분 동안 3천만 번이나 이러한 연산을 수행할 수 있는 능력을가지고 있다. 보통 토너먼트 경기에서「하이테크」가 말을 한 번 움직일 때 3분을 소비하니까 매번 3천만 가지의 경우의 수를 생각해 본다는 얘기가 된다.「하이테크」의 제작자 베를리너는 이렇게 말한다. "의심스러운 것은 인간이 과연 장기말을 한 번 움직일 때 3천만 번씩 생각해볼까 하는 점입니다. 아마 한 평생토록 그렇게 엄청난 경우의 수를 따지지도 못할 것입니다."

  1949년, 아직 컴퓨터가 유아일 시절에 미국의 수학자 샤논은 그의 논문에서 체스 기계에 대한 대략적인 프로그래밍 방법을 제시하였다. 이 논문에 영향을 받은 일단의 인공 지능연구가들은 샤논의 아이디어를 실현시키기 위한 노력을 시작하였다.

  노벨상 수상자인 허버트사이몬 교수는 1957년 다음과 같은 말을 하였다. "10년 안에 디지탈 컴퓨터는 인간을 누르고 세계 참피온 자리에 오를 것이다." 그러나 그로부터 30년이 지난 오늘날까지 세계 체스 참피온 자리는 인간이 지키고 있으며,「하이테크」마저도 이 아성에 도전하지 못했다. 250여개나 되는 각종 타이틀전에서 컴퓨터는 한번도 우승한 적이 없으나, 단 하나 예외가 있었다. 바로 '블리츠 체스(blitz chess)' 라 하여 양선수가 5분간 게임을 치르는 경기에 있어서만은 연산 속도가 빠른 컴퓨터가우승했던 것이다.

  베를리너는 1990년까지 세계 체스 참피온이 될 컴퓨터를 만들어 낼 것이라고 장담하고 있다. 그는 인간을 이길 수 있는 기계를 만드는 데, 그리고 세계 정상급의 실력을 가진 기계를 만드는 데 필요한 요소를 알고 있다. 1979년, 그가 만든 서양 주사위 놀이 프로그램「BKG 9.8」은 이탈리아의 루이지 빌라를 물리치고 세계 참피온 자리에 오른 바 있으며(이 대회에서「BKG 9.8」은 7-1이라는 일방적인 스코어로 이기고 상금 5천달러를 받았다), 1968년에는 베를리너 자신이 체스대회에 출전하여 우승한 바도 있다.

  체스는 보기보다 어려운 게임이다. 흔히 우리들은 체스의 명인들이란 사회적으로 제대로 적응하지 못하고 고독을 즐기는 천재라 여긴다. 한마디로 일종의 정교한 계산기라 생각하는 것이다. 체스의 명인이 말을 하나 움직일 때는 마음속으로 수백가지의 가능성을 생각하며, 그것을 눈깜짝할 사이의 빠르고 정확한 속도로 수행한다고 믿기 쉽다. 그러나 실제로 체스 명인들은 체스 게임을 계산해 내는 계산기가 아니다. 그보다는 체스판의 전체 상황을 보면서 체스를 두는 '패턴 인식(pattern recognition)' 기술을 사용한다고 보아야 한다.

  독일의 심리학자 구트는 체스의 말을 한 번 움직이는 데 보통 38가지의 경우의 수가 있다고 주장한다. 그리고 체스 명인은 대개 이중에서 2가지 경우만을 추려내 둘 중에서 보다 유리한 자리를 선택한다고 설명한다. 수천 수만 번 두었거나 보아온 체스의 경험, 고도로 축적된 잠재적 경험이 경기를 승리로 이끄는 것이다. 초기의 컴퓨터프로그램도 이러한 방법을 채택하였다. 그러나 문제는 컴퓨터 언어로 어떻게 이러한 제한적 탐색방법(selective-search approach)을 실현하는가에 있었다. 이 문제가 해결된 것은 1966년의 일이다.「맥호크(Mac Hack)」라 불리우는 프로그램은 제한적 탐색 방법을 완전하게 구현하는데 성공, 드디어 웬만한 사람에게는 승리를 거두었다. 그리고 마침내 토너먼트 경기에 출전, 최초로 인간을 이긴 컴퓨터 프로그램으로 기록되었다. 그리하여 당시에「컴퓨터가 할 수 없는 일들」이라는 책으로 유명해진 드리퓨즈의 콧대를 단단히 꺾어 놓았다.

  이 승리는 컴퓨터 체스의 역사에 이정표를 세운 기념비적 사건이었다. 그러나 또한 이것은 세계 참피온 자리를 향한 체스기계의 험난한 도전의 시작에 불과하였다. 맥호크의 프로그램은 마주앉아 체스를 둘 수 있는 최초의 프로그램이라는 점에선 크게 평가 받을만 했으나 가끔가다 어이없는 실수를 저지르곤 하였다.

  맥호크 개발의 여파로 1970년에는 이미 여러 종류의 프로그램이 출현, 토너먼트 대회를 개최하게 되었다. 첫 대회에는 6명의 컴퓨터 선수가 출전 기량을 겨루었고, 다음 해에는 8명의 컴퓨터 선수가 출전 치열한 경합을 벌였다.

  1970년대에 들어와 노스웨스턴대학의 대학원생 데이빗 스레이트와 로렌스 에킨 두 사람은 미니막스 기법, 알파베타 알고리즘, 경험적 축적 방법, 패턴화 기법 등을 사용하여「체스 4.7」이라는 프로그램을 완성하였다. 이 프로그램은 체스 명인의 수준에 약간 밑도는 실력을 가지고 있었다.

  1981년이 되면「체스 4.7」을 능가하는 새로운 프로그램이 벨연구소의 켄 톰슨과 조 코돈에 의해 등장한다.「벨레(Belle)」라고 명명된 이 프로그램이「체스 4.7」을 능가할 수 있었던 비밀은 하드웨어 있어 체스 경기의 수행을 위해 특별히 설계된 칩을 사용한 것이었다. 이로 인해 프로그램수행 속도는 몇 배나 빨라져서 벨레는 매초 12만자리를 분석하여 평균 8수 앞까지 내다볼 수 있게 되었다.

  하이테크의 제작자인 베를리너는 종래의 방식에 체스의 구체적 지식을 주입시켜 그 실행 능력을 엄청나게 향상시킬 구상을 하고 있다. 즉 '생각하는 기계'를 실현하고자 하는 것이다.

  하이테크는 대학원생 에벨링에 의해 설계된 64개의 특별한 칩으로 구성된 2만 5천달러짜리 컴퓨터이다. 1만 5천개의 전자 회로가 집적된 이 칩들은 VLSI 기술의 결정체이다. 각 칩들은 체스판의 네모칸을 하나씩 맡아 말들의 움직임을 체크하고 가장 적절한 공략책을 생각해낸다. 모든 칩들은 각기 독립적으로 작동하므로 동시에 64가지의 연산이 가능하다. 이 점은 하이테크의 연산 시간을 대폭 단축해 준다. 각 칩들을 유기적으로 관리하는 장치는 오라클(oracle : 신의 사자)인데, 이 장치는 하이테크에 필요한 체스 지식을 담고 있어 64개의 칩들이 올바로 연산을 수행하고 빨리 판단하도록 한다.

  지난 8월「하이테크」의 강력한 라이벌인「크레이 블리츠」는 하이테크와의 경기에서 지고 말았다. 크레이블리츠는타 프로그램과 마찬가지로 6만개의 경우를 기록하여 일정 방법으로 체스를 두어가도록 되어 있다.

  이 방법의 치명적인 약점은 무작정 흉내만 냄으로써 상대방의 교묘한 작전에 말려들어 표준적이지 못한 상황에 대처할 수 없는 것이다. 이러한 점을 보완하고자 크레이블리츠에 커다란 수정이 가해졌다. 그러나 이러한 수정에도 불구하고 크레이 블리츠는 하이테크에 비하여 스피드나 체스 지식면에서 상대가 되지 못할 것으로 예상된다. 그러나 분명한 것은 기계와 기계의 대결에서 야기되는 승패의 희열은 인간끼리의 대결에서의 그것에 못지 않으리라는 것이다.

  카르포프가 필리핀에서 열린 세계 참피온 대회에서 카르노이에게 패했을 때, 전하는 바에 의하면 그를 위로하기 위해 소련의 일급 심리학자가 비행기로 날아오는 등 소동을 벌였다 한다. 또한 먼 옛날 정복자 윌리엄은 게임에서 진 후 너무 흥분한 나머지 체스판을 프랑스 왕자의 머리에 내려쳤다고 한다. 또 러시아의 황자 아론 림조비치는 경기에 지자 체스판 위에 올라가 무릎을 꿇고 두 팔을 들어 하늘로 향한 후, 이렇게 외쳤다고 한다. "오, 신이여! 어찌하여 내가 이런 바보에게 패하도록 하였읍니까?"

  미니막스 기법 (MINIMAX APPROACH)

  현대 컴퓨터 체스 기술은 미니막스(최대최소) 기법에 크게 의존하고 있다. 임의로 평가함수를 정하여 그 범위를 −10에서 +10사이로 할 때, +10은 우리편의 승리를, −10은 상대방의 승리를, 0은 비기는 경우를 나타낸다 하자. 아래 그림의 경우,

  즉, 현재 우리의 위치가 A이고 A의 위치에서 선택할 수 있는 가지수가 B, C, D 3가지 상태일 때, 당연히 우리는 B를 선택할 것이다. 그런데 여기에 한 가지 중대한 문제가 있다. 다음 그림을 보라.

  B를 선택할 경우 상대방은 E와 F의 경우 중 하나를 택할 것이다. 상대방은 −10에 가까운 경우를 택할수록 유리하므로 우리에게 매우 불리하다. 따라서 우리는 C를 선택하는 것이 가장 무난함을 알 수 있다. 상대방이 반격해 오더라도 −2 값을 가진 H를 택할 것이므로 피해가 가장 적게 될 수 있다.

  이것이 바로 인공지능학에서 유명한 최대최소 방법이다.