게임 프로그램과 인공지능(AI)은 긴 역사를 공유하고 있다.
초기의 AI 연구는 컴퓨터의 연산 능력이 인간의 지능을 모방, 인간 수준의 문제 풀이 능력을 구현하는 것을 하나의 목표로 세웠다. 우리가 오목, 장기, 바둑을 두거나 게임을 할 때 ‘머리를 쓴다’라고 표현하는데, 바로 그 머리를 쓰는 행위를 기계로 구현하고자 한 것이다.
특히 기호주의 AI 연구는 기호 조작과 탐색을 통해 해결책을 추론하는 접근을 했다. 게임은 풀이 과정이 길고 복잡하지만 규칙성과 상호 작용이 있으며 어느 정도의 창의성도 필요하기 때문에 지능 또는 인간의 지적 활동의 일부를 컴퓨터가 구현할 수 있는지 확인해 보려는 접근이었다.
방법은 '탐색'이었다. 문제 해결 방법 탐색은 인간의 접근 방식과 유사하지만, 전체 과정이 조금만 복잡해지면 인간이 직접 하기에 매우 어려운 문제가 된다. 마우스의 미로 찾기와 함께, 탐색의 대표 사례로 거론되는 것은 '하노이탑 풀이' 문제이다.
1883년 프랑스 수학자인 뤼카(Édouard Lucas)가 고안, '뤼카의 탑'이라고도 불리는 이 문제는 탐색 트리를 이용한 컴퓨터의 맹목적 탐색과 이의 비효율성을 개선하기 위한 추가 탐색 기법을 설명할 때 많이 활용된다. 그러나 하노이 탑과 같이 정형화할 수 있는 문제는 1959년 뉴웰과 사이먼이 개발한 두번째 AI 프로그램 'GPS(General Problem Solver)'로도 충분히 풀이가 가능했다.
같은 탐색 문제라도 하노이 탑과 달리, 상대가 있는 게임의 경우는 훨씬 어려운 문제다. 하나의 수에 대응 가능한 상대편의 모든 수를 고려해야 하고, 그 모든 수에 대해 다시 가능한 모든 수를 결정해야 하는 과정이 반복되며 천문학적인 숫자의 탐색 경우가 나오게 된다. 초기 컴퓨터의 능력으로는 끝까지 탐색하고 답을 찾기가 쉽지 않았다. 그런 예들이 틱택토부터 오셀로, 체커, 체스 등과 같은 게임으로, AI 연구자들은 규칙성과 상호 작용을 고려해 인간처럼 생각하고 풀이할 수 있는 프로그램을 연구하고 개발해 왔다.
이런 게임들의 풀이에 대한 어려움의 수준을 측정하고 표현하는 수단으로 '게임 복잡도(Game Complexity)'가 있다. 위키피디아를 찾아보면, 40여종의 다양한 보드게임들의 복잡도가 몇가지 기준으로 표현돼 있다. 예를 들어, 게임 트리의 복잡성을 기준으로 보면 가장 간단한 틱택토는 10의 5제곱 정도이지만, 커넥트포는 10의 21제곱, 8x8 말판의 미국식 체커는 10의 40제곱, 10x10 말판의 국제식 체커는 10의 54제곱의 복잡도를 보여 준다.
또, 8x8 말판을 사용하지만 말이 뒤집어질 수 있는 오셀로는 10의 58제곱, 체스는 10의 123제곱, 동양의 장기는 10의 160제곱 그리고 바둑은 10의 360제곱이다. 이 정도가 되면 복잡성이 기하급수적으로 증가, 일반적인 탐색 기법만으로는 도저히 풀어낼 수가 없다.
이전에는 모눈종이에 흑과 백의 기호를 그려 다섯개의 같은 기호가 직선이 되면 승리하는 간이 오목 게임을 즐기곤 했다. 이런 오목과 비슷한 게임이 틱택토와 커넥트포 등이다. 말판 공간의 제한이 없는 오목과 달리, 틱택토(Tic-tac-toe)는 3x3의 제한된 공간에서 동일한 기호 세개를 연결하는 게임이다. 커넥트포(Connect Four)는 가로 7칸 세로 6칸의 말판이 수직으로 세워져 있다. 위에서 말을 떨어뜨려 비어 있는 가장 아래의 칸까지 말이 내려가서 쌓이는 구조인데, 동일한 색깔의 말 네개를 연결하는 게임이다.
이런 게임과 체스, 바둑 등은 플레이어가 게임 내 모든 움직임을 파악할 수 있는 ‘완전 정보’ 게임에 해당한다. 또 참가자가 차례로 돌아가며 말을 움직이는 즉, 먼저 어떤 행동을 취한 다음 다른 참가자가 이를 보고 자신의 행동을 취하는 ‘순차 게임’이다. 주사위 같은 것을 사용하지 않아. 임의의 상황이 발생하지 않는 게임이기도 하다.
이미 1960년대 해결 프로그램이 나온 틱택토는 풀이가 나름 간단하지만, 탐색의 미니맥스와 알파 베타 가지치기 알고리즘을 이해하기 좋아서 AI 프로그램 연구자들이 입문용으로 공부하는 경우가 꽤 된다. 커넥트포 게임이 처음 등장한 것은 1974년이었는데, 당시 컴퓨터의 능력으로는 풀이가 불가능하다고 여겨졌다. 그러나, 1988년 컴퓨터 학자인 제임스 알렌(James Allen)과 네덜란드의 컴퓨터 과학자 빅터 앨리스(Victor Allis)에 의해 각각 해결됐다. 현재는 첫수를 두는 사람이 완벽하게 수를 외우고 있으면, 무조건 이기는 ‘해결된 게임’이 됐는데, 커넥트포의 풀이도 미니맥스와 알파 베타 가지치기 알고리즘을 기본으로 하고 있다.
1956년 아서 사무엘에 의해 공개적으로 시연된 체커 프로그램의 경우, 40년이 지난 뒤인 1996년에 조나단 셰퍼(Jonathan Schaeffer)의 '치누크(Chinook')는 인간과의 시합에서 현격한 실력 차로 승리하자 더 이상 입증해야 할 것이 없다며 은퇴했다. 셰퍼와 동료들은 치누크를 은퇴시킨 뒤에도 계속 연구, 2007년에는 체커 게임은 참가자 모두 완벽하게 게임을 하면 결국 무승부로 끝난다는 것을 증명했다. 이 증명은 다른 의미에서 본다면 인간에게 절대로 지지 않는 기계를 만드는 것이 이론적으로 가능하다는 것을 보여줬다.
리버시(Reversi)라고도 불리는 오셀로(Othello) 게임은 8x8 말판에 흑과 백의 두가지 말로 구성, 미국식 체커와 비슷하게 보인다. 그러나, 경기 중 말을 뒤집어 색깔이 바뀔 수도 있기 때문에, 미국식 체커의 복잡도를 훨씬 넘어서는 10의 58제곱의 게임 트리 복잡성을 가지고 있다.
1970년대 후반부터 본격 개발된 오셀로 프로그램은 1980년대부터 인간을 쉽게 이겼는데, 1997년 독일에서 마이클 부로(Michael Buro)가 박사과정 논문 작업으로 작성한 프로그램 '로지스텔로(Logistello)'가 인간 챔피언을 6대 0으로 꺾으며 완벽히 인간을 능가했다고 인정됐다.
완벽한 수를 외우면 무조건 이기거나 무승부로 게임이 끝나는 것이 증명된 틱택토와 커넥트포, 체커 등은 '해결된 게임'인 반면, 오셀로는 아직도 완벽한 경기를 펼치면 결과가 어떻게 될지 모른다는 점에서 ‘해결되지 않은 게임’으로 간주한다.
AI 연구에서 인간의 지적 활동 중 하나를 구현하려는 방법으로 게임 프로그램들이 개발됐지만, 일부 AI 연구자들은 이를 긍정적으로 평가하지 않았다. 앞서 존 매카시가 체스 프로그램 딥블루에 대해 "AI 연구에 크게 기여하지 못했고, 단지 빨라진 컴퓨터 연산 능력만 과시했다"라고 평가 절하한 바 있다고 했다. 마빈 민스키도 이런 연구들은 일반 지능 문제를 연구하는 것이 아니라, 단순한 애플리케이션 연구에 불과하다며, 그간 개발된 게임 풀이 AI에 대해 단지 게임에 불과하다고 일축했다.
스탠포드대학교와 MIT 대학 모두에서 교수를 역임했으며, MIT 인공지능연구소장을 역임했던 로드니 브룩스(Rodney Brooks)도 좀 다른 관점에서 게임 AI를 평가 절하하며 새로운 연구 방향을 제시했다. 1990년 발표된 에세이 ‘코끼리는 체스를 두지 않는다’에서 그는 지난 30여년간 추구된 전통적인 AI 연구는 규칙, 기호처리, 탐색과 같은 고전적인 방식의 기호 추상화를 통해 접근해 왔지만, AI의 연구는 주위 환경과 지속적인 물리적 상호 작용을 원천으로 해서 연구돼야 한다고 주장했다.
즉, 미리 정의된 규칙과 완전한 정보 그리고 정적이라는 환경이라는 특수 환경에서만 의미가 있는 체스와 같은 게임 프로그램은 문제 해결 능력이 있지만, 고도록 제한된 환경에서의 해결이라 진짜 지능이라고 보지 않았다. 반면, AI가 진정한 지능을 갖추려면 정보가 불완전하고 지속적으로 변화하는 실제 세계에서 대응하고 적응하는 능력을 갖춰야 한다고 했다.
그러면서 코끼리와 같은 동물들은 뛰어난 사회성과 기억력을 바탕으로 한 지능을 갖고 있고 이는 몸과 환경과의 상호 작용의 결과이지만, 체스는 이와는 다른 추상적 문제 해결 방법이라고 설명했다. 이런 자신의 주장을 바탕으로 브룩스는 실제 세계와의 상호작용을 통한 단순한 행동으로부터 유기적인 지능이 형성될 수 있다는 '누벨 AI(Nouvelle AI)'를 주창하고 AI 연구를 로봇을 통해 구현하려 했다.
이전에도 많은 로봇을 개발해 왔던 그는 에세이를 발표한 그해 청소기 '룸바'로 대표되는 아이로봇사를 설립하고, 이후에는 양팔형 협동 로봇 벡스터로 대표되는 리씽크 로보틱스를 설립했다.
문병성 싸이텍 이사 moonux@gmail.com
