섀넌의 '마우스 테세우스'는 단순한 놀잇거리나 구경거리인 장난감은 아니었다. 마우스는 처음 미로의 한 지점에 놓이면 스스로 미로의 구석구석을 돌아다니며 목표 지점을 찾아내는 작업을 했다. 이는 정해진 대로만 작동하는 것이 아닌, 답을 찾기 위한 과정을 스스로 진행하는 것이다. 인공지능(AI)에서는 ‘탐색’이라고 하는 과정이다. 또 목표지점에 대한 올바른 경로를 탐색한 마우스는 이전에 돌아다녔던 경로 중 임의의 지점에 다시 놓이게 되더라도 목표 지점까지 바로 찾아갈 수 있었다. 이 역시 정해진 대로 작동하는 것이 아니라, 마우스가 문제 풀이의 전체 과정을 알고 변경된 현재의 위치를 전체 과정의 부분으로 판단해서 이동 방법을 스스로 수정해 나간 것이다. 미로가 변경되면, 추가 탐색을 통해 마우스는 새로운 경로의 풀이를 하는 과정을 반복하는데 이런 과정을 ‘학습’한다고 표현할 수 있을 것이다.
기계가 생각할 수 있다는 개념을 입증하기 위해 AI 연구자들은 저마다 다양한 방식으로 접근했는데, 그중 하나는 기계가 스스로 복잡한 문제를 풀게 하는 것이었다. 복잡한 문제를 풀어 나간다는 것은 지능을 필요로 하는 일이고, 인간과 동물이나 기계를 구분할 수 있는 한 방법으로 생각했다. 초기 과학자들은 퍼즐, 미로, 게임 등을 복잡한 문제로 봤고, 기계가 문제를 해결하도록 다양한 수학적, 공학적 방법으로 접근했다.
섀넌의 마우스나 체스 프로그램은 초기 AI 시기에 중심적 역할을 한 ‘탐색(Search)’에 관한 연구였다. 탐색이란 문제해결 기술의 하나로, 어떤 동작 뒤 무슨 일이 일어날 것인지에 대한 체계적 고려이자 예측이다. 또 탐색을 통해 뒤에 일어나는 일들을 예측하고 그런 일들이 연속될 때, 최종적으로 원하던 목적을 이루는 방향으로 진행될지 또는 그렇게 되지 않을지를 판단하는 것을 ‘평가’라고 한다. 목적을 성취하기 위한 지적인 행동은 이처럼 탐색과 평가라는 두 행위를 통해 이뤄진다.
이런 방식은 발생할 수 있는 모든 경우의 수를 따지는 것으로 프로그램을 설계한다면, 기본적으로 컴퓨터로 구현하기 아주 어렵지는 않다. 한 동작이 일어났을 때 발생할 수 있는 그다음의 연쇄 동작의 모든 경우를 계산하고, 그 연쇄 동작이 일어나면 또 발생할 수 있는 모든 연쇄 동작의 경우를 계산하는 과정을 반복, 목적한 방향으로 진행되는지 평가하거나 최종적으로 목적한 바를 성취할 수 있는 경우들만 선택하는 것이다.
섀넌의 테세우스 구조와 같은 5 X 5 미로를 생각해 보자. 시작 지점인 S에 처음 테세우스를 놓아두고 G를 목표 지점으로 설정했을 때, 목표에 도달하는 최단 경로를 찾기 위해 인간은 눈으로 따라가거나 손가락 또는 펜으로 경로를 그려가며 찾아볼 것이다.
그러나, 테세우스는 그럴 수 없기 때문에 먼저 전체 경로를 확인하기 위해 미로 내의 모든 지점을 돌아다니며 S에서 G에 이르는 이동할 수 있는 모든 경로를 나열해 본다. 분기점과 막다른 지점 그리고 목표 지점에 적당한 기호를 붙여 기억하고 분석한다. 이런 방식으로 모든 가능한 경로를 나열해 정리하면 마지막 그림과 같은 모습이 되고, 이를 ‘탐색 트리(Search Tree)라고 한다. 탐색 트리에서 가능한 모든 경로 중 목표 지점에 가는 가장 최단 경로는 ‘S-A-D-G’가 될 것이고, 테세우스는 이 경로를 해답으로 제시하게 된다.
이처럼 미로의 구조가 간단하고 시작 지점과 목표 지점이 고정된 경우는 사람에게도 어렵지 않다. 그러나, 시작 지점을 계속 바꿔가며 반복적으로 미로 찾기를 하면 인간은 지쳐버릴 수 있다.
테세우스는 지점들의 기억을 바탕으로 새로운 시작 지점에 놓이게 되더라도, 새로운 시작 지점에서 다시 전체 탐색트리를 만들고 최단 경로를 계산하고 길을 따라가면 되기 때문에 그렇게 어려운 일이 아니다. 이렇게 탐색 트리란 경우의 수를 따지는 것으로, 목표로 하는 조건을 만날 때까지 선택 가능한 경우를 반복적으로 나눠가는 방식이다. 사람과 달리, 테세우스나 컴퓨터는 미로의 규모가 커지고 복잡해지더라도 이런 단순하고 반복적인 작업을 지치지 않고 수행해 낼 수 있다.
이렇게 가능한 모든 경우의 수를 두고 미리 정해진 순서에 따라 단순히 탐색하는 방법을 ‘맹목적 탐색(Blind Search)’이라고 한다. 맹목적 탐색에는 기본적으로 ‘깊이우선 탐색(DFS, Depth-First Search)’과 ‘너비우선 탐색(BFS, Breadth-First Search)’의 두가지가 있다. 깊이우선 탐색은 갈 수 있는 경로의 끝까지 가보고, 목표 지점이 아니면 경로의 가장 마지막 분기점에서 다시 확인하는 방식이다. 너비우선 탐색 방식은 시작 지점에 인접한 계층을 다 확인하고, 목표지점이 없으면 다음 계층을 모두 확인하는 방식이다.
너비우선 탐색은 목표 지점에 대한 최단 경로를 반드시 찾을 수 있도록 보장하지만, 목표 지점을 찾을 때까지 가는 경로와 노드를 모두 기억해야 한다. 따라서 경로가 길어져서 탐색 트리가 급격하게 증가하면 컴퓨터의 방대한 메모리 자원이 필요하다. 반면, 깊이우선 탐색은 목표에 이르는 경로가 다수인 경우에 최단 경로, 즉 최적의 값이 아닌 경로를 답으로 내놓을 수도 있다. 또 운이 좋으면 빠르게 답을 찾을 수도 있고, 그렇지 않을 수 있는 등 답을 구하는 시간에 대한 예측이 탐색 트리 설정에 따라 변동 폭이 크다. 그러나 최근 탐색한 경로상의 노드 정보만 기억하면 되기 때문에 컴퓨터 메모리 사용량이 많지 않다는 것이 장점이다.
이 두가지 기본 탐색 방법은 장단점을 갖고 있기 때문에, 두 방식 중 좋은 점만 취한 '반복적 깊이심화 탐색' 기법이나, 특수한 문제에 대해서는 특별히 빨리 푸는 다양한 방법이 연구됐다. 그러나 이런 방법을 사용해도 맹목적 탐색법은 답을 찾지 못하거나 여러 개의 답이 존재, 컴퓨팅 자원과 시간의 낭비를 가져오는 비효율성을 내포하고 있다. 그러나 심각한 비효율성 외에도 맹목적 탐색은 더 근본적인 문제를 가지고 있다.
특히, 체스나 바둑 같이 상대가 있는 게임의 경우는 한편의 수에 상대편이 응수하고 그 응수에 대해서 한편이 다시 수를 설정하는 과정이 반복적으로 이뤄지는 등 모든 경우의 수를 고려해야 한다. 이런 탐색 트리를 만들기 위해서는 천문학적인 숫자의 경우가 나오게 돼, 초기의 컴퓨터들로는 끝까지 탐색하기가 쉽지 않았다.
이렇게 문제 해결을 위한 탐색 과정에서 가능한 수가 폭발적으로 증가하는 상황을 ‘조합폭발’이라고 하는데, 연구를 통해 탐색량을 줄이는 방법들이 제시되기도 했다. 특히 모든 상태를 검토하지 않고도 그 평가가 목적한 바에 더 가까울 가능성을 계산하는 '휴리스틱 탐색(Heuristics Search)'이 도입되며, 전체 계산의 효율도 높이고 좋은 결과도 얻어낼 수 있게 됐다. 그렇게 탐색 트리에 추가적인 알고리즘을 도입하며 AI 프로그램이 탄생하는데, 휴리스틱 탐색에 대해서는 다음에 살펴본다.
문병성 싸이텍 이사 moonux@gmail.com
