체스 컴퓨터는 모든 수를 계산하지 않는다, 가지치기의 수학

체스 컴퓨터가 사람 챔피언을 꺾을 수 있었던 비결은 가능한 모든 체스 수를 끝까지 계산했기 때문이 아니라, 상대가 결코 두지 않을 수나 자신에게 불리한 수를 계산 목록에서 과감히 잘라냈기 때문이다. 체스에서 가능한 경기 진행의 가짓수는 10의 120제곱에 달한다. 이는 관측 가능한 우주의 원자 수보다 많은 수치다. 현대 슈퍼컴퓨터로도 이 모든 경로를 일일이 탐색하는 것은 불가능하다. 인공지능 탐색 알고리즘의 핵심은 불필요한 계산을 미리 포기하는 가지치기의 기술이다.

최소최대 알고리즘과 결정 트리의 구조

체스와 같은 보드게임은 두 경기자가 번갈아 가며 수를 두며 한쪽의 이익이 다른 쪽의 손실이 되는 제로섬 게임이다. 이런 게임에서 최적의 수를 찾기 위해 고안된 기본 틀이 최소최대 탐색이다. 최소최대 알고리즘은 둘이서 번갈아 가며 수를 두는 제로섬 게임에서 자신이 얻을 수 있는 최악의 결과 중 가장 나은 선택을 찾는 탐색 방법이다.

경기 상태를 하나의 점으로 두고 다음으로 둘 수 있는 수들을 가지로 연결하면 거대한 나무 모양의 결정 트리가 만들어진다. 컴퓨터는 자신이 수를 두는 차례에는 평가 점수를 최대화하려 하고, 상대방 차례에는 점수를 최소화하려 한다고 가정한다. 맨 아래 깊이에서 판의 유불리를 계산한 다음, 그 점수를 위로 끌어올리며 최적 경로를 역산한다. 하지만 탐색 깊이가 한 단계 깊어질 때마다 계산해야 할 경우의 수는 기하급수적으로 폭증한다. 평균적으로 한 수마다 35가지 선택지가 존재하므로, 불과 서너 수 앞을 내다보는 데에도 수백만 개의 국면을 점검해야 하는 계산 병목이 생긴다.

알파베타 가지치기가 계산량을 줄이는 원리

이 무모한 계산량을 획기적으로 줄인 수학적 해법이 바로 알파베타 가지치기다. 원리는 단순하면서도 강력하다. 어떤 경로를 살펴보던 중 이미 확보한 다른 대안보다 명백히 나쁜 결과로 이어진다는 사실이 확인되면, 그 경로의 나머지 하위 가지들은 아예 계산하지 않고 건너뛴다.

예를 들어 컴퓨터가 A 경로를 선택하면 최소 5점을 얻을 수 있음을 이미 확인했다고 가정한다. 다음으로 B 경로를 탐색하는데, 상대방이 둘 수 있는 첫 번째 반격만으로 점수가 2점까지 떨어지는 상황이 발견된다. 그렇다면 상대방이 더 강력한 반격을 준비하고 있든 말든 B 경로는 이미 A 경로보다 나쁜 선택이 확정된다. 따라서 B 경로 아래에 매달린 수천, 수만 개의 하위 수들을 일일이 계산할 이유가 전혀 없다.

탐색 방법	6단계 깊이 탐색 노드 수	10단계 깊이 탐색 노드 수
단순 최소최대 탐색	약 18억 개	약 2,700조 개
알파베타 가지치기 최적 조건	약 4만 개	약 5,000만 개

이처럼 알파와 베타라는 두 개의 기준값을 유지하며 불필요한 가지를 쳐내면, 최적의 조건에서 동일한 시간에 두 배 더 깊은 수를 내다볼 수 있게 된다. 1997년 세계 체스 챔피언 가리 카스파로프를 꺾은 딥블루의 핵심 병기 역시 특수 하드웨어로 가속된 알파베타 탐색 엔진이었다.

바둑과 딥러닝으로 이어진 탐색 기법

체스보다 판이 훨씬 넓은 바둑에서는 가능한 수의 조합이 10의 360제곱으로 치솟아 알파베타 가지치기만으로는 감당하기 어려웠다. 돌 하나를 놓을 때마다 생기는 경우의 수가 200개가 넘기 때문이다. 이를 극복하기 위해 등장한 기법이 무작위 시뮬레이션을 결합한 몬테카를로 트리 탐색이다.

인공지능은 모든 수를 깊이 파고드는 대신, 유망해 보이는 지점 몇 군데를 골라 게임 끝까지 가상 대국을 빠르게 치러본 뒤 승률을 집계한다. 여기에 인공신경망이 결합되어 현재 판세의 가치를 단숨에 직관적으로 판단하는 가치망과 둘 만한 착점 후보를 좁혀주는 정책망이 더해졌다. 가지를 수학적으로 쳐내는 단계를 넘어, 애초에 탐색할 가치가 있는 가지만 골라내는 방식으로 진화한 셈이다.

무한한 탐색 공간과 컴퓨터의 한계

탐색 알고리즘의 눈부신 발전에도 불구하고 연산 능력의 근본적 한계는 여전히 존재한다. 체스와 바둑은 규칙이 명확하고 숨겨진 정보가 없는 완전 정보 게임이지만, 주식 시장이나 도로 교통처럼 외부 변수와 숨겨진 정보가 넘쳐나는 현실 세계의 결정 트리는 끝없이 요동친다. 수학적으로 완벽한 최적해를 찾는 문제는 여전히 계산 복잡도 이론의 거대한 장벽 뒤에 놓여 있다. 현대 컴퓨터는 모든 미래를 계산해 답을 맞히는 예언자가 아니라, 가장 덜 위험한 경로를 남겨두고 나머지를 신속하게 포기하는 효율적 생존 기계에 가깝다.