알파-베타 가지치기는 미니맥스 알고리즘이 탐색 트리에서 평가하는 노드의 수를 줄이기 위해 고안된 트리 탐색 알고리즘이다. 이는 틱택토, 체스, 커넥트 4와 같은 2인용 조합 게임의 기계 플레이에 흔히 사용되는 적대적 탐색 알고리즘이다. 이 알고리즘은 어떤 수가 이전에 검토된 수보다 나쁘다는 것을 증명하는 가능성이 하나 이상 발견되면 해당 수의 평가를 중단하므로, 그러한 수는 더 이상 평가할 필요가 없다. 표준 미니맥스 트리에 적용될 때, 미니맥스와 동일한 수를 반환하지만 최종 결정에 영향을 줄 수 없는 가지를 제거한다.
이 알고리즘은 Artificial intelligence 분야에서 분기 한정법 접근 방식의 전형적인 예이며, 초기 체스 컴퓨터와 현대 엔진을 포함한 많은 게임 프로그램의 기반이 된다. 효율성 향상을 통해 동일한 계산 예산 내에서 더 깊은 탐색이 가능해져, 적대적 탐색의 기초 기술로 자리 잡았다.
역사
존 매카시는 1956년 다트머스 워크숍에서 체스 프로그램을 작성 중이던 IBM의 알렉스 번스타인을 만났다. 매카시는 알파-베타 탐색을 발명하여 번스타인에게 추천했지만, 번스타인은 "확신하지 못했다." 앨런 뉴웰과 허버트 A. 사이먼은 1958년에 매카시가 "근사치"라고 부른 것을 사용했으며, 알파-베타는 "여러 번 재발명된 것으로 보인다"고 썼다. 아서 사무엘은 체커 시뮬레이션을 위한 초기 버전을 가지고 있었다. 리처즈, 티모시 하트, 마이클 레빈, 그리고/또는 다니엘 에드워즈도 미국에서 독립적으로 알파-베타를 발명했다. 매카시는 다트머스 워크숍에서 유사한 아이디어를 제안했고 1961년 MIT의 앨런 코톡을 포함한 학생 그룹에게 제안했다. 알렉산더 브루드노는 독립적으로 알파-베타 알고리즘을 구상하여 1963년에 결과를 발표했다. 도널드 커누스와 로널드 W. 무어는 1975년에 알고리즘을 개선했다. 주드 펄은 두 편의 논문에서 무작위로 할당된 잎 값을 가진 트리에 대한 예상 실행 시간 측면에서 최적성을 증명했다. 알파-베타의 무작위 버전의 최적성은 1986년 마이클 삭스와 아비 위그더슨에 의해 증명되었다.
핵심 아이디어
게임 트리는 체스, 체커, 오델로와 같은 많은 2인 제로섬 게임을 나타낼 수 있다. 트리의 각 노드는 게임의 가능한 상황을 나타낸다. 각 분기의 터미널 노드(결과)에는 다음 수를 둘 플레이어에게 결과의 가치를 결정하는 숫자 점수가 할당된다.
알고리즘은 알파와 베타라는 두 값을 유지하며, 각각 최대화 플레이어가 보장받는 최소 점수와 최소화 플레이어가 보장받는 최대 점수를 나타낸다. 처음에 알파는 음의 무한대이고 베타는 양의 무한대이며, 이는 두 플레이어 모두 최악의 점수에서 시작함을 의미한다. 최소화 플레이어("베타" 플레이어)가 보장받는 최대 점수가 최대화 플레이어("알파" 플레이어)가 보장받는 최소 점수보다 작아질 때마다(즉, 베타 < 알파), 최대화 플레이어는 이 노드의 추가 하위 노드를 고려할 필요가 없으며, 실제 플레이에서 도달되지 않을 것이기 때문이다.
실생활 예로 설명하면, 누군가 체스를 두고 있고 자신의 차례라고 가정하자. 수 "A"는 플레이어의 위치를 개선할 것이다. 플레이어는 더 나은 수를 놓치지 않았는지 확인하기 위해 계속 수를 찾는다. 수 "B"도 좋은 수이지만, 플레이어는 상대가 두 수 안에 체크메이트를 강제할 수 있음을 깨닫는다. 따라서 수 B를 둔 후의 다른 결과는 상대가 승리를 강제할 수 있으므로 더 이상 고려할 필요가 없다. 수 B 후에 상대가 강제할 수 있는 최대 점수는 음의 무한대, 즉 플레이어의 패배이다. 이는 이전에 발견된 최소 위치보다 낮으며, 수 A는 두 수 안에 강제 패배를 초래하지 않는다.
순진한 미니맥스 대비 개선
알파-베타 가지치기의 이점은 탐색 트리의 가지를 제거할 수 있다는 점에 있다. 이렇게 하면 탐색 시간을 '더 유망한' 하위 트리로 제한할 수 있으며, 동일한 시간에 더 깊은 탐색을 수행할 수 있다. 전임자와 마찬가지로 분기 한정법 알고리즘 클래스에 속한다. 이 최적화는 노드가 최적 또는 최적에 가까운 순서로 평가될 경우(각 노드에서 수를 둔 쪽의 최선 선택이 먼저 오도록) 유효 깊이를 단순 미니맥스의 절반보다 약간 더 줄인다.
평균(또는 일정한) 분기 계수 b와 탐색 깊이 d 플라이(ply)를 가정할 때, 평가되는 리프 노드 위치의 최대 수(수 순서가 최악일 때)는 O(b^d)로 단순 미니맥스 탐색과 동일하다. 탐색 수 순서가 최적(즉, 최선의 수가 항상 먼저 탐색됨)이면, 평가되는 리프 노드 위치의 수는 홀수 깊이에 대해 약 O(b 1 b 1 ... b)이고 짝수 깊이에 대해 O(b 1 b 1 ... 1)이며, 즉 O(b^(d/2)) = O(sqrt(b^d))이다. 후자의 경우, 탐색의 플라이가 짝수일 때 유효 분기 계수는 제곱근으로 줄어들며, 동일한 계산량으로 탐색 깊이를 두 배로 할 수 있다. b1b1...의 설명은 첫 번째 플레이어의 모든 수를 연구하여 최선을 찾아야 하지만, 각 수에 대해 두 번째 플레이어의 최선 수만 첫 번째(그리고 최선) 플레이어 수를 제외한 모든 수를 반박하는 데 필요하며, 알파-베타는 다른 두 번째 플레이어 수를 고려할 필요가 없음을 보장한다.
노드가 무작위 순서로 고려될 때(즉, 알고리즘이 무작위화됨), 점근적으로 이진 잎 값을 가진 균일 트리에서 평가되는 노드의 예상 수는 Theta(((b-1+sqrt(b^2+14b+1))/4)^d)이다. 동일한 트리에서 잎 값이 서로 독립적으로 할당되고 0과 1이 모두 동일하게 확률이 있을 때, 평가되는 노드의 예상 수는 Theta((b/2)^d)이다.
구현 고려 사항
실제로 알파-베타 가지치기는 탐색 깊이를 점진적으로 증가시키는 반복적 심화와 함께 구현되는 경우가 많다. 수 순서는 최적에 가까운 성능을 달성하는 데 중요하며, 일반적인 휴리스틱에는 캡처를 먼저 검사하고, 킬러 수를 사용하며, 트랜스포지션 테이블을 활용하는 것이 포함된다. 알고리즘은 지평선 효과를 피하기 위해 정적 탐색과 같은 기술로 확장될 수 있으며, 주 변형 탐색 및 네가스카우트와 같은 더 고급 알고리즘의 기초를 형성한다. 알파-베타 가지치기는 Chess computer 시스템과 같은 플랫폼에서 실행되는 것을 포함한 체스 프로그램에서 널리 사용되며, 다양한 게임 플레이 AI 프레임워크에 통합되었다.
유산과 영향
알파-베타 가지치기는 Artificial intelligence와 게임 이론에 지속적인 영향을 미쳤다. 초기 체스 프로그램의 핵심 구성 요소였으며, 특히 분기 계수가 큰 게임에서 현대 게임 엔진에서도 여전히 관련이 있다. 알고리즘의 효율성 개선은 광범위하게 연구되었으며, 그 원리는 탐색 및 최적화의 다른 영역에도 영향을 미쳤다. Machine learning 및 Deep learning과 같은 새로운 기술이 게임 AI를 변화시켰지만, 알파-베타 가지치기는 여전히 적대적 탐색의 기본 도구로 사용되며, 그 역사적 발전은 AI 연구의 협력적이고 반복적인 특성을 강조한다.