알파-베타 가지치기

1. 개요

알파-베타 가지치기는 게임 트리에서 최적의 수를 찾기 위한 탐색 알고리즘으로, 2인 제로섬 게임에 주로 사용된다. 1950년대에 아이디어가 제안되었고, 1975년 도널드 커누스와 로널드 W. 무어에 의해 알고리즘이 재정립되었으며, 1982년 유디 펄에 의해 최적성이 증명되었다. 이 알고리즘은 미니맥스 알고리즘을 개선하여 탐색 범위를 줄이고 성능을 향상시키며, 휴리스틱 정렬, 야망 창 기법 등을 활용한다. 알파와 베타 값을 사용하여 탐색 범위를 제한하고, '알파 컷', '베타 컷'을 통해 불필요한 노드 탐색을 줄이는 것이 핵심이다.

2. 역사

앨런 뉴얼과 허버트 사이먼은 1958년에 알파-베타가 여러 번 재발명되었다고 언급했다. 아서 새뮤얼(Arthur Samuel)은 알파-베타 가지치기의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 미국에서 독립적으로 알파-베타 가지치기의 기초를 세웠다. 존 매카시는 1956년 다트머스 회의에서 "근사치"라는 용어를 사용하며 비슷한 아이디어를 제안했고, 1961년에 MIT의 앨런 코톡(Alan Kotok)에게도 가르쳤다. 알렉산더 브루드노는 1963년에 독자적으로 알파-베타 알고리즘을 발표했다. 도널드 커누스와 로널드 W. 무어는 1975년에 알고리즘을 재정립했고, 유디 펄은 1982년에 이 방법이 최적임을 증명했다.

3. 핵심 아이디어

게임 트리에서 알파-베타 가지치기는 각 노드가 게임의 가능한 상황을 나타내고, 두 플레이어(최대화 플레이어와 최소화 플레이어)가 번갈아 가며 수를 두는 제로섬 게임에서 최적의 수를 찾기 위해 사용되는 탐색 알고리즘이다. 핵심 아이디어는 다음과 같다.

알고리즘은 두 가지 값, 알파(α)와 베타(β)를 사용한다. 알파는 최대화 플레이어(자신)가 보장하는 최소 점수를 나타내며, 베타는 최소화 플레이어(상대방)가 보장하는 최대 점수를 나타낸다. 초기에는 알파는 음의 무한대(-∞), 베타는 양의 무한대(+∞)로 설정되어, 각 플레이어는 최악의 점수에서 시작한다.

탐색 과정에서, 최소화 플레이어가 보장하는 최대 점수(β)가 최대화 플레이어가 보장하는 최소 점수(α)보다 작아지면(β < α), 최대화 플레이어는 해당 노드의 하위 노드를 더 이상 탐색할 필요가 없다. 이를 베타 컷(β cut)이라고 한다. 왜냐하면 실제 게임에서 그러한 상황은 발생하지 않기 때문이다.

예를 들어, 체스 게임에서 자신의 차례에 "A"라는 좋은 수를 찾았다고 가정하자. 더 나은 수를 찾기 위해 계속 탐색하던 중, "B"라는 수도 좋아 보이지만, 이 수를 두면 상대방이 두 수 안에 체크메이트를 강요할 수 있다는 것을 발견한다. 이 경우, 상대방이 "B" 수 이후에 강요할 수 있는 최대 점수는 음의 무한대(-∞, 즉 자신의 패배)가 된다. 이는 "A" 수를 두었을 때보다 더 나쁜 결과이므로, "B" 수의 하위 노드는 더 이상 탐색할 필요가 없다.

반대로, 알파 값이 베타 값보다 커지면(α ≥ β), 최소화 플레이어는 해당 노드의 하위 노드를 더 이상 탐색하지 않아도 된다. 이를 알파 컷(α cut)이라고 한다.

알파(α)와 베타(β)는 탐색에서 고려해야 할 값의 범위를 나타낸다. 예를 들어, 여러 최소값 중 최대값을 찾는 상황에서 첫 번째 최소값이 3이라면, 3 이하의 값은 최대값으로 선택되지 않는다. 즉, 관심의 하한(α)은 3이 된다. 만약 두 번째 최소값에서 3 이하의 값이 나오면, 그 값은 더 이상 고려할 필요가 없으므로 탐색을 중단(컷)한다. 마찬가지로, 베타(β)는 관심의 상한을 나타내며, 최대값 안에서 값이 상한을 넘으면 탐색을 중단한다.

4. 미니맥스 알고리즘 개선

알파-베타 가지치기는 미니맥스 알고리즘의 탐색 효율성을 개선한 알고리즘이다. 미니맥스 알고리즘은 모든 가능한 경우의 수를 탐색하지만, 알파-베타 가지치기는 불필요한 탐색을 줄여 계산량을 줄인다.

알파-베타 가지치기는 탐색 트리의 가지를 쳐낼 수 있다는 장점이 있다. 이러한 방식으로 탐색 시간을 '더 유망한' 하위 트리로 제한할 수 있으며, 동일한 시간 내에 더 깊은 탐색을 수행할 수 있다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색 깊이를 미니맥스의 절반 정도로 최적화할 수 있다.

분기 계수를 b, 검색 깊이를 d라고 할 때, 최악의 경우(이동순서가 최악) 평가되는 잎 노드 위치는 $O(b^d)$로 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가되는 잎 노드의 수는 약 $O(b^\backslash frac\{d\}\{2\})$까지 줄일 수 있다. 즉, 같은 연산 작업으로 거의 두 배 깊이로 탐색할 수 있다. 노드 순서가 무작위라면, 평균적으로 평가하는 노드의 수는 약 $O(b^\backslash frac\{3d\}\{4\})$이다.

일반적으로 알파-베타 동안 하위 트리는 일시적으로 첫 번째 플레이어의 이점에 의해 지배되거나 그 반대의 경우도 마찬가지이다. 이 이점은 이동 순서가 잘못된 경우 탐색 중에 여러 번 전환될 수 있으며, 각 전환은 비효율성을 초래한다. 검색된 위치 수가 현재 위치에 가까워질수록 기하급수적으로 감소하므로, 초기 이동 정렬에 상당한 노력을 기울일 가치가 있다.

4.1. 휴리스틱 개선

알파-베타 가지치기의 정확성을 훼손하지 않으면서 탐색 효율을 높이기 위해 휴리스틱 정렬을 사용할 수 있다. 휴리스틱 정렬은 알파-베타 컷오프를 유발할 가능성이 높은 노드를 우선적으로 탐색하도록 순서를 조정한다. 예를 들어, 체스에서는 말을 잡는 수나 이전 탐색에서 높은 점수를 받은 수를 우선적으로 고려할 수 있다. 킬러 휴리스틱은 이전 탐색에서 베타 컷오프를 발생시킨 수를 우선적으로 고려하는 방법이다. 이 아이디어는 반박 테이블 집합으로 일반화할 수도 있다.

반복 심화 깊이 우선 탐색과 함께 휴리스틱 정렬을 사용하면 탐색 깊이를 점진적으로 늘려나가면서도 효율성을 높일 수 있다. 실제로, 이동 순서는 종종 반복 심화 깊이 우선 탐색과 같은 이전의 작은 탐색 결과에 의해 결정된다.

야망 창(좁은 탐색 창)을 설정하여 탐색 속도를 높일 수 있다. 극단적인 경우, 알파와 베타가 동일하게 수행되는 제로 창 탐색, 널 창 탐색 또는 스카우트 탐색이라고 하는 기법이 사용된다. 이는 좁은 창에서 얻은 추가 깊이와 간단한 승/패 평가 함수가 결정적인 결과로 이어질 수 있는 게임 종료 시점에 가까운 승/패 탐색에 특히 유용하다. 야망 탐색이 실패하면, 실패가 "높음"(창의 높은 가장자리가 너무 낮음)인지 "낮음"(창의 낮은 가장자리가 너무 높음)인지를 쉽게 감지할 수 있다. 이를 통해 해당 위치의 재탐색에 유용할 수 있는 창 값에 대한 정보를 얻을 수 있다.

5. 의사 코드

알파-베타 가지치기 알고리즘의 의사 코드는 여러 가지 버전이 존재한다.

* 페일 소프트(Fail-soft) 버전: 함수 호출 인수로 설정된 α 및 β 경계를 초과하는 값(v < α 또는 v > β)을 반환할 수 있다.
* 페일 하드(Fail-hard) 버전: 함수 반환 값을 α와 β의 포함 범위로 제한한다.
* 네가맥스(Negamax) 버전: 노드를 평가할 때 얻는 값의 부호(+, -)를 턴에 따라 바꿔야 한다.

일반적인 알파-베타 가지치기 의사 코드는 다음과 같다.

```
function minimax(node, depth)
return alphabeta(node, depth, -∞, +∞)

function alphabeta(node, depth, α, β)
if node가 종단 노드 or depth = 0
return node의 평가값
if node가 자신의 노드
foreach child of node
α = max(α, alphabeta(child, depth-1, α, β))
if α ≥ β
break // β 컷
return α

else node가 대전자의 노드
foreach child of node
β := min(β, alphabeta(child, depth-1, α, β))
if α ≥ β
break // α 컷
return β
```

여기서 α와 β는 관심 있는 값의 범위를 나타낸다. 예를 들어 max(min(...), min(...), ..., min(...))의 값을 조사할 때, 첫 번째 min의 값이 3이었다면, 3 이하의 값은 max에 의해 선택되지 않는다. 즉, 관심의 하한(=α)이 3이 된다. 두 번째 min 안에 3 이하의 값이 나타나면 min의 값은 반드시 3 이하가 되지만, 그 값에는 관심이 없으므로, 3 이하의 값이 나타나는 시점에서 탐색을 중단(컷)한다. β는 관심의 상한을 나타내며, max 안에서 값이 관심의 상한을 넘는다고 판단되면 컷이 된다.

5.1. 페일 소프트(Fail-soft) 버전

페일 소프트 알파-베타는 함수 호출 인수로 설정된 α 및 β 경계를 초과하는 값(v < α 또는 v > β)을 반환할 수 있다. 반면에 페일 하드 알파-베타는 함수 반환 값을 α와 β의 포함 범위로 제한한다.

다음은 페일-소프트 알파-베타의 의사 코드이다.

```
function alphabeta(노드, 깊이, α, β, 최대화하는플레이어) is
if 깊이 == 0 or 노드가 터미널 then
return 노드의 휴리스틱 값
if 최대화하는플레이어 then
value := −∞
for each 노드의 자식 do
value := max(value, alphabeta(자식, 깊이 − 1, α, β, FALSE))
α := max(α, value)
if value ≥ β then
break (* β 차단 *)
return value
else
value := +∞
for each 노드의 자식 do
value := min(value, alphabeta(자식, 깊이 − 1, α, β, TRUE))
β := min(β, value)
if value ≤ α then
break (* α 차단 *)
return value

(* 초기 호출 *)
alphabeta(origin, 깊이, −∞, +∞, TRUE)

5.2. 페일 하드(Fail-hard) 버전

페일 하드 알파-베타는 반환 값을 α, β 범위로 제한한다. 다음 의사 코드는 페일 하드(Fail-hard) 알파-베타 가지치기 알고리즘을 보여준다.

```
function alphabeta(노드, 깊이, α, β, 최대화하는플레이어) is
if 깊이 == 0 or 노드가 터미널 then
return 노드의 휴리스틱 값
if 최대화하는플레이어 then
value := -∞
for each 노드의 자식 do
value := max(value, alphabeta(자식, 깊이 - 1, α, β, FALSE))
if value > β then
break (* β 차단 *)
α := max(α, value)
return value
else
value := +∞
for each 노드의 자식 do
value := min(value, alphabeta(자식, 깊이 - 1, α, β, TRUE))
if value < α then
break (* α 차단 *)
β := min(β, value)
return value

(* 초기 호출 *)
alphabeta(origin, 깊이, -∞, +∞, TRUE)
```

페일 소프트 알파-베타와는 다르게, 페일 하드 알파-베타는 함수 반환 값을 α와 β의 포함 범위로 제한한다. 페일-소프트와 페일-하드 구현의 주요 차이점은 차단 검사 전후에 α와 β가 업데이트되는지 여부이다. 검사 전에 업데이트되면 초기 경계를 초과할 수 있으며 알고리즘은 페일-소프트가 된다.

5.3. 네가맥스(Negamax) 버전

네가맥스(Negamax) 버전은 알파-베타 가지치기 코드를 더 간결하게 만들 수 있는 방법이다. 하지만, 이 버전을 사용할 때는 노드를 평가할 때 얻는 값의 부호(+, -)를 턴에 따라 바꿔야 하는 점에 주의해야 한다.

```
function alphabeta(node, depth, α, β)
if node가 종단 노드 or depth = 0
return node의 평가값
foreach child of node
α := max(α, -alphabeta(child, depth-1, -β, -α))
if α ≥ β
return α // 컷
return α
```

위 코드는 네가맥스 버전의 알파-베타 가지치기 알고리즘을 나타낸다. 여기서 핵심은 `α := max(α, -alphabeta(child, depth-1, -β, -α))` 부분이다. 이 부분은 기존 알파-베타 알고리즘과 비교했을 때, 자식 노드에 대한 재귀 호출 시 `-alphabeta(child, depth-1, -β, -α)`와 같이 부호를 반전시켜서 호출하고, 최댓값을 구하는 부분도 α와 -alphabeta 결과 중 큰 값을 선택하도록 변경된 것을 알 수 있다. 이렇게 부호를 바꾸면서 최댓값/최솟값 연산을 번갈아 하는 방식으로 코드를 간결하게 만들 수 있다.

6. 기타 알고리즘

미니맥스 알고리즘과 그 변형은 기본적으로 깊이 우선 탐색을 사용한다. 반복적 깊이 우선 탐색과 함께 사용하면, 알고리즘이 완료되기 전에 중단되더라도 적절한 수를 반환할 수 있다. 반복적 깊이 우선 탐색을 사용하는 또 다른 장점은 얕은 깊이에서의 검색이 수 순서 힌트를 제공하며, 얕은 알파 및 베타 추정치를 제공하여 그렇지 않은 경우보다 훨씬 더 빨리 더 높은 깊이 검색에 대한 차단을 생성하는 데 도움이 될 수 있다는 것이다.

반면에 SSS*와 같은 알고리즘은 최선 우선 탐색 전략을 사용한다. 이는 잠재적으로 시간 효율성을 높일 수 있지만, 일반적으로 공간 효율성 측면에서 큰 대가를 치른다.

7. 응용

게임 트리는 체스, 체커, 리버시와 같은 2인 제로섬 게임을 표현하는 데 사용될 수 있다. 게임 트리의 각 노드는 게임에서 가능한 상황을 나타내며, 각 분기의 끝에 있는 노드(결과)에는 다음 수를 두는 플레이어에게 해당 결과의 가치를 나타내는 숫자 점수가 할당된다.

알파-베타 가지치기 알고리즘은 최대화 플레이어가 보장하는 최소 점수(알파)와 최소화 플레이어가 보장하는 최대 점수(베타)를 유지한다. 초기에는 알파는 음의 무한대, 베타는 양의 무한대로 설정되어 두 플레이어 모두 최악의 점수에서 시작한다. 최소화 플레이어(베타)가 보장하는 최대 점수가 최대화 플레이어(알파)가 보장하는 최소 점수보다 작아지면(베타 < 알파), 최대화 플레이어는 해당 노드의 하위 노드를 더 이상 고려할 필요가 없다. 실제 게임에서는 이러한 상황에 도달할 수 없기 때문이다.

예를 들어, 체스 게임에서 자신의 차례에 "A"라는 수를 두면 플레이어의 위치가 좋아진다. 더 나은 수가 있는지 확인하기 위해 계속 수를 찾던 중 "B"라는 수도 좋은 수임을 발견했지만, 이 수를 두면 상대방이 두 수 안에 체크메이트를 걸 수 있다는 것을 알게 된다. 따라서 "B" 수는 상대방에게 승리를 허용하므로 더 이상 고려할 필요가 없다. "B" 수를 뒀을 때 상대방이 얻을 수 있는 최대 점수는 음의 무한대, 즉 플레이어의 패배이며, 이는 이전에 찾은 최소 점수보다 작다. 반면 "A" 수는 두 수 안에 강제된 패배를 초래하지 않는다.