초기 인공지능 연구: 알파-베타 가지치기(Alpha-Beta Pruning)

알파-베타 가지치기(Alpha-Beta Pruning)는 최대-최소 탐색(Minimax Algorithm)의 연산량을 줄이기 위한 최적화 기법이다. 이 개념은 1950년대 초반 인공지능 및 체스 프로그램 연구에서 처음 등장했다. 당시 체스 AI 개발자들은 가능한 모든 수를 계산하는 방식의 비효율성을 극복하기 위해 불필요한 탐색을 줄이는 방법을 고민했고, 그 결과 알파-베타 가지치기가 탄생했다. 이후 다양한 턴제 전략 게임과 의사결정 시스템에서도 활용되며, 효율적인 탐색 기법으로 자리 잡았다. 게임 트리에서 불필요한 노드의 탐색을 생략함으로써 연산 속도를 향상시키고 보다 깊은 탐색이 가능하게 한다.
 
최대-최소 탐색의 문제점 중 하나는 가능한 모든 경우를 탐색해야 하기 때문에 연산량이 기하급수적으로 증가한다는 점이다. 예를 들어, 체스에서 한 턴당 약 35개의 선택지가 있고, 80턴 이상 진행된다고 가정하면 O(35⁸⁰)개의 경우를 탐색해야 한다. 이러한 계산량을 줄이기 위해 불필요한 경로를 미리 제거하는 기법이 알파-베타 가지치기이다.
 
알파(α)와 베타(β)는 탐색 중 발생하는 최상의 선택지를 나타내는 값이다. 이를 쉽게 이해하기 위해 문을 여닫는 과정에 비유할 수 있다. 문이 여러 개 있는 복도를 지나가면서, 어떤 문을 열지 결정하는 상황을 생각해보자. 알파 값은 지금까지 발견한 가장 좋은 문이며, 베타 값은 상대가 선택할 가능성이 있는 문이다. 특정 시점에서 상대가 이미 자신에게 최적의 선택을 했다고 판단되면, 이후의 문들을 열어볼 필요 없이 탐색을 종료할 수 있다. 즉, 더 좋은 선택지가 있을 가능성이 남아 있더라도, 현재까지의 탐색 결과를 고려할 때 추가 탐색이 의미 없다고 판단하는 과정이 알파-베타 가지치기의 핵심이다. 알파는 최대화 플레이어(Max 노드)가 현재까지 찾은 최선의 선택지를 의미하고, 베타는 최소화 플레이어(Min 노드)가 현재까지 찾은 최선의 선택지를 의미한다. 탐색 도중 알파 값이 베타 값 이상이 되는 경우, 더 이상의 탐색은 불필요하게 되어 해당 분기를 가지치기한다.
 
이를 쉽게 이해하기 위해, 시험 문제 풀이 과정을 생각해 보자. 대부분의 시험에서는 합격을 위한 커트라인이 존재한다. 즉, 일정 점수 이상을 획득하면 추가적으로 문제를 푸는 것이 의미가 없을 수 있다. 시험에서 100문제가 주어졌다고 가정하자. 시간이 충분하다면 모든 문제를 푸는 것이 가능하겠지만, 제한된 시간이 있다면 중요한 문제를 우선적으로 풀어야 한다.
예를 들어, 초반 몇 문제를 풀었을 때 정답률이 높아 목표 점수를 충분히 초과할 가능성이 크다면, 이후의 문제를 전부 풀지 않아도 된다. 반대로, 특정 문제를 푸는 도중 남은 시간 내에 목표 점수를 넘기기 어렵다고 판단된다면, 나머지 문제를 푸는 것은 의미가 없다. 즉, 목표 점수를 이미 초과했거나, 남은 문제를 풀어도 목표 점수에 도달할 가능성이 없다면, 남은 문제를 푸는 것은 시간 낭비가 된다. 이러한 방식으로 불필요한 문제 풀이를 줄이는 것이 바로 알파-베타 가지치기와 유사한 개념이다.
 
이처럼, 알파-베타 가지치기도 불필요한 탐색을 줄이기 위해, 특정 시점에서 더 이상의 탐색이 의미 없다고 판단되면 남은 분기를 건너뛰는 방식으로 작동한다. 알파-베타 가지치기는 상대가 이미 최적의 선택을 했다고 판단되면, 이후의 탐색을 생략하여 연산을 줄이고 더 효율적으로 최적의 수를 찾는다.
 

알파-베타 가지치기(Alpha-Beta Pruning) 동작 원리

1. 탐색을 진행하면서 Max 노드와 Min 노드가 각각 최적의 선택지를 갱신한다.
2. Max 노드는 현재까지의 최대 값을 알파(α)로 유지하고, Min 노드는 최소 값을 베타(β)로 유지한다.
3. 탐색을 하다가 α ≥ β 조건이 성립하면, 해당 분기에서 더 이상 탐색할 필요가 없으므로 가지치기를 수행한다.
4. 이를 반복하면 동일한 결과를 도출하면서도 탐색해야 할 노드의 수를 줄일 수 있다.

하나의 예로, 틱택토(Tic-Tac-Toe) 게임에서 특정한 수를 두었을 때, 일부 분기는 더 이상 탐색할 필요가 없다. 예를 들어, 한 노드에서 이미 상대가 필승하는 수가 나왔다면, 그 이후의 탐색은 불필요하다. 즉, 알파-베타 가지치기를 적용하면 불필요한 경우의 수를 배제하고 보다 효율적으로 최적의 수를 찾을 수 있다.
 

시간 복잡도 개선 효과

 
최대-최소 탐색의 일반적인 시간 복잡도는 O(bᵈ)이지만, 알파-베타 가지치기를 적용하면 최적의 경우 O(b^(d/2))로 줄어들 수 있다. 예를 들어, 체스에서 가능한 선택지가 35개이고 게임이 6턴 깊이까지 진행된다고 가정하면, 일반적인 Minimax 탐색에서는 O(35⁶)의 연산이 필요하다. 하지만 알파-베타 가지치기를 적용하면 탐색할 필요가 없는 노드를 건너뛰어 최적의 경우 O(35³) 수준으로 탐색량이 감소할 수 있다. 이는 실전에서 더 깊은 수를 고려할 수 있도록 해주며, AI의 연산 효율성을 크게 향상시킨다. 예를 들어, 체스 게임에서 특정 수를 두었을 때 상대가 체크메이트로 이어지는 수를 발견한 경우, 이후의 탐색은 의미가 없다. 이미 승패가 결정된 경로에서는 추가적인 수를 고려할 필요가 없으므로, 탐색을 중단하고 다른 선택지를 검토하는 것이 효율적이다. 이로 인해 탐색할 노드 수가 줄어들어 연산이 더욱 효율적으로 수행되며, 게임에서 더 깊은 수를 고려할 수 있는 여유가 생긴다. 이는 탐색할 노드 수를 획기적으로 줄이는 효과를 가져오며, 보다 깊은 탐색을 가능하게 한다.
 

활용

 
체스, 바둑, 오목과 같은 전략 게임의 AI에서 필수적으로 사용되며, 보다 정교한 게임 트리 탐색을 가능하게 한다. 예를 들어, 체스에서는 엔드게임 분석에 사용되어 제한된 말 개수 내에서 최적의 수를 찾는 데 도움을 주며, 바둑에서는 초반 정석 탐색과 같은 결정적인 수를 판별하는 데 활용된다. 이러한 게임들은 선택지가 많고 탐색해야 할 경우의 수가 방대하기 때문에, 알파-베타 가지치기를 적용하면 연산량을 줄이고 더욱 효율적인 탐색이 가능해진다. 또한 인공지능의 의사결정 시스템에서도 최적의 선택지를 빠르게 찾는 데 활용될 수 있다. 그러나 알파-베타 가지치기는 완벽한 평가 함수가 필요하다는 한계가 있으며, 확률적 요인이 많은 게임에서는 적용이 어렵다. 여기서 '완벽한 평가 함수'란 현재 게임 상태를 수치적으로 평가하여 어느 플레이어에게 유리한지를 정확하게 판단하는 함수이다. 예를 들어, 체스에서는 각 기물의 가치를 점수로 환산하여 평가하며, 바둑에서는 차지한 영역(집)과 돌의 배치를 기준으로 평가할 수 있다. 하지만 이런 평가 함수가 완벽하지 않거나 부정확할 경우, 알파-베타 가지치기의 효율성이 떨어질 수 있다.
 
몬테카를로 트리 탐색(MCTS)은 이러한 한계를 극복하기 위해 개발된 기법으로, 확률적 샘플링을 활용하여 최적의 수를 찾는다. 알파-베타 가지치기는 완벽한 평가 함수가 필요하고, 게임 트리가 깊어질수록 성능이 저하될 수 있다는 한계를 가진다. 반면, 몬테카를로 트리 탐색(MCTS)은 확률적 샘플링을 활용하여 탐색 공간을 줄이고, 불확실성이 높은 환경에서도 효과적으로 작동한다. 다음 글에서는 이러한 차이를 보다 자세히 살펴보고, MCTS가 알파-베타 가지치기와 어떻게 비교되는지에 대해 다룰 예정이다.

 
2025.03.14 - [Algorithm] - 게임 이론: 최대-최소 탐색(Minimax Algorithm) 이해하기

게임 이론: 최대-최소 탐색(Minimax Algorithm) 이해하기