게임 트리 알고리즘, 인공지능 의사결정의 뼈대로 주목...미니맥스·알파베타 가지치기가 핵심 원리

[한국정보기술신문] 인공지능이 틱택토(Tic-Tac-Toe)나 체스, 바둑 같은 게임에서 다음 수를 결정하는 핵심 원리로 게임 트리 기반 알고리즘이 다시 조명받고 있다. 게임은 규칙이 명확해 추상적으로 정의할 수 있고, 인간의 지적 능력과 연관이 있는 것으로 여겨져 인공지능 분야에서 오래전부터 중요한 연구 주제로 다뤄져 왔다.

게임 트리 알고리즘은 두 명이 번갈아 수를 두는 게임을 전제로 한다. 두 경기자는 각각 맥스(MAX)와 민(MIN)으로 불리며, 맥스가 항상 먼저 수를 둔다고 가정한다. 또한 한 명이 이기면 다른 한 명은 반드시 지는 제로섬(zero-sum) 구조로, 둘이 함께 이기는 협동적 승리는 존재하지 않는다.

대표적인 사례인 틱택토는 가로세로 3×3 크기의 판에서 진행된다. 한 곳에 수를 놓으면 상대가 놓을 수 있는 칸이 하나씩 줄어든다. 이 때문에 가능한 모든 경우의 수는 9×8×7×…×1, 즉 9!(팩토리얼)인 36만2880가지에 이른다. 인공지능은 이처럼 방대한 게임 상태를 나무 모양의 구조인 '게임 트리'로 표현해 분석한다.

다만 모든 경우의 수를 전부 계산하는 일은 드물다. 경우에 따라 전부 따져야 할 때도 있지만, 실제로는 그렇지 않은 경우가 더 많기 때문이다. 불필요한 계산을 줄이기 위한 여러 기법이 고안된 배경이다.

가장 기본이 되는 방식은 미니맥스(minimax) 알고리즘이다. 현재 보드 상태를 트리의 뿌리(루트)로 놓고, 인공지능이 둘 수 있는 빈칸의 수만큼 가지를 뻗어 가능한 미래 상태를 모두 펼친다. 게임이 끝나는 최종 상태에 도달하면 더 이상 가지를 나누지 않고 점수를 매긴다. 인공지능이 이기면 +1점, 지면 -1점, 비기면 0점이 부여된다.

핵심은 상대방이 항상 최선의 수를 둔다고 가정하는 데 있다. 작은 숫자를 골라야 유리한 민은 가지 중 가장 작은 값을 선택하고, 큰 숫자를 골라야 유리한 맥스는 가장 큰 값을 선택한다. 트리의 아래쪽 단말 노드부터 위로 올라오며 이 과정을 반복해 최선의 수를 결정한다.

미니맥스는 게임 트리 전체를 깊이 우선으로 완벽하게 탐색한다. 트리의 최대 깊이가 m이고 각 노드에서 가능한 수가 b개일 경우, 이 알고리즘의 시간 복잡도는 b의 m제곱, 즉 O(b^m)으로 표현된다. 깊이가 깊어질수록 계산량이 기하급수적으로 늘어난다는 의미다.

이러한 계산 부담을 덜기 위한 기법이 알파베타 가지치기다. 미니맥스가 만드는 탐색 트리 가운데 상당수는 최종 결과에 영향을 주지 않는데, 이런 가지를 미리 쳐내는 방식이다. 탐색 과정에서 맥스는 알파(α) 값만, 민은 베타(β) 값만 갱신하며, 자식 노드로 두 값을 전달해 비교한다.

예를 들어 맥스가 이미 7이라는 값을 확보한 상태에서 다른 경로를 탐색할 때, 그 경로가 6보다 작은 값을 보낼 것이 분명하다면 나머지 단말 노드는 계산할 필요가 없다. 맥스는 7보다 큰 값을 찾고 있기 때문이다. 이처럼 부모 노드의 현재 값에 따라 트리 전체를 탐색하지 않고도 같은 결론에 도달할 수 있다.

미니맥스 알고리즘은 본래 탐색 공간 전체를 살피는 것을 전제로 한다. 그러나 실제 게임에서는 탐색 공간이 매우 커 정해진 시간 안에 모든 경우를 따지기가 사실상 불가능하다. 적당한 시간 안에 다음 수를 결정해야 하기 때문이다.

이때 활용되는 것이 휴리스틱 평가 함수(evaluation function)다. 탐색을 마쳐야 하는 시간에 도달하면 탐색을 중단하고, 아직 게임이 끝나지 않은 비단말 노드를 마치 최종 상태에 도달한 것처럼 간주해 점수를 추정한다. 완벽한 계산 대신 합리적인 추정을 통해 제한된 시간 안에서 최선에 가까운 결정을 내리는 셈이다.

게임 트리에서 출발한 이들 기법은 오늘날 다양한 인공지능 의사결정 모델의 기초로 활용되며, 탐색 효율을 높이려는 연구가 꾸준히 이어지고 있다.