알파-베타 가지치기
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
알파-베타 가지치기는 게임 트리에서 최적의 수를 찾기 위한 탐색 알고리즘으로, 2인 제로섬 게임에 주로 사용된다. 1950년대에 아이디어가 제안되었고, 1975년 도널드 커누스와 로널드 W. 무어에 의해 알고리즘이 재정립되었으며, 1982년 유디 펄에 의해 최적성이 증명되었다. 이 알고리즘은 미니맥스 알고리즘을 개선하여 탐색 범위를 줄이고 성능을 향상시키며, 휴리스틱 정렬, 야망 창 기법 등을 활용한다. 알파와 베타 값을 사용하여 탐색 범위를 제한하고, '알파 컷', '베타 컷'을 통해 불필요한 노드 탐색을 줄이는 것이 핵심이다.
더 읽어볼만한 페이지
- 게임 인공지능 - 구글 딥마인드
구글 딥마인드가 개발한 스타크래프트 II 인공지능 알파스타는 프로게이머를 상대로 뛰어난 실력을 입증했으며, 딥마인드는 이를 인공 일반 지능 개발을 위한 시도로 간주한다. - 게임 인공지능 - 컴퓨터 올림피아드
컴퓨터 올림피아드는 컴퓨터 프로그램 간의 지능 대결을 펼치는 대회로, 1989년 런던에서 시작되어 1992년 중단되었다가 2000년에 부활했으며, 국제 컴퓨터 게임 협회가 매년 체스, 바둑, 브리지 등 다양한 게임의 컴퓨터 프로그램들을 대상으로 대회를 개최한다. - 최적화 알고리즘 - 기댓값 최대화 알고리즘
- 최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다. - 검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다. - 검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.
| 알파-베타 가지치기 | |
|---|---|
| 알고리즘 개요 | |
| 종류 | 탐색 알고리즘 |
| 시간 복잡도 | O(b^d) |
| 최적 시간 복잡도 | O(√(b^d)) |
| 공간 복잡도 | O(b^d) |
2. 역사
앨런 뉴얼과 허버트 사이먼은 1958년에 알파-베타가 여러 번 재발명되었다고 언급했다.[15] 아서 새뮤얼(Arthur Samuel)은 알파-베타 가지치기의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 미국에서 독립적으로 알파-베타 가지치기의 기초를 세웠다.[16] 존 매카시는 1956년 다트머스 회의에서 "근사치"[17]라는 용어를 사용하며 비슷한 아이디어를 제안했고, 1961년에 MIT의 앨런 코톡(Alan Kotok)에게도 가르쳤다.[18] 알렉산더 브루드노는 1963년에 독자적으로 알파-베타 알고리즘을 발표했다.[19] 도널드 커누스와 로널드 W. 무어는 1975년에 알고리즘을 재정립했고,[20] 유디 펄은 1982년에 이 방법이 최적임을 증명했다.
게임 트리에서 알파-베타 가지치기는 각 노드가 게임의 가능한 상황을 나타내고, 두 플레이어(최대화 플레이어와 최소화 플레이어)가 번갈아 가며 수를 두는 제로섬 게임에서 최적의 수를 찾기 위해 사용되는 탐색 알고리즘이다. 핵심 아이디어는 다음과 같다.
알파-베타 가지치기는 미니맥스 알고리즘의 탐색 효율성을 개선한 알고리즘이다. 미니맥스 알고리즘은 모든 가능한 경우의 수를 탐색하지만, 알파-베타 가지치기는 불필요한 탐색을 줄여 계산량을 줄인다.
3. 핵심 아이디어
알고리즘은 두 가지 값, 알파(α)와 베타(β)를 사용한다. 알파는 최대화 플레이어(자신)가 보장하는 최소 점수를 나타내며, 베타는 최소화 플레이어(상대방)가 보장하는 최대 점수를 나타낸다. 초기에는 알파는 음의 무한대(-∞), 베타는 양의 무한대(+∞)로 설정되어, 각 플레이어는 최악의 점수에서 시작한다.
탐색 과정에서, 최소화 플레이어가 보장하는 최대 점수(β)가 최대화 플레이어가 보장하는 최소 점수(α)보다 작아지면(β < α), 최대화 플레이어는 해당 노드의 하위 노드를 더 이상 탐색할 필요가 없다. 이를 베타 컷(β cut)이라고 한다. 왜냐하면 실제 게임에서 그러한 상황은 발생하지 않기 때문이다.
예를 들어, 체스 게임에서 자신의 차례에 "A"라는 좋은 수를 찾았다고 가정하자. 더 나은 수를 찾기 위해 계속 탐색하던 중, "B"라는 수도 좋아 보이지만, 이 수를 두면 상대방이 두 수 안에 체크메이트를 강요할 수 있다는 것을 발견한다. 이 경우, 상대방이 "B" 수 이후에 강요할 수 있는 최대 점수는 음의 무한대(-∞, 즉 자신의 패배)가 된다. 이는 "A" 수를 두었을 때보다 더 나쁜 결과이므로, "B" 수의 하위 노드는 더 이상 탐색할 필요가 없다.
반대로, 알파 값이 베타 값보다 커지면(α ≥ β), 최소화 플레이어는 해당 노드의 하위 노드를 더 이상 탐색하지 않아도 된다. 이를 알파 컷(α cut)이라고 한다.
알파(α)와 베타(β)는 탐색에서 고려해야 할 값의 범위를 나타낸다. 예를 들어, 여러 최소값 중 최대값을 찾는 상황에서 첫 번째 최소값이 3이라면, 3 이하의 값은 최대값으로 선택되지 않는다. 즉, 관심의 하한(α)은 3이 된다. 만약 두 번째 최소값에서 3 이하의 값이 나오면, 그 값은 더 이상 고려할 필요가 없으므로 탐색을 중단(컷)한다. 마찬가지로, 베타(β)는 관심의 상한을 나타내며, 최대값 안에서 값이 상한을 넘으면 탐색을 중단한다.
4. 미니맥스 알고리즘 개선
알파-베타 가지치기는 탐색 트리의 가지를 쳐낼 수 있다는 장점이 있다. 이러한 방식으로 탐색 시간을 '더 유망한' 하위 트리로 제한할 수 있으며, 동일한 시간 내에 더 깊은 탐색을 수행할 수 있다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색 깊이를 미니맥스의 절반 정도로 최적화할 수 있다.
분기 계수를 b, 검색 깊이를 d라고 할 때, 최악의 경우(이동순서가 최악) 평가되는 잎 노드 위치는 로 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가되는 잎 노드의 수는 약 까지 줄일 수 있다. 즉, 같은 연산 작업으로 거의 두 배 깊이로 탐색할 수 있다. 노드 순서가 무작위라면, 평균적으로 평가하는 노드의 수는 약 이다.
일반적으로 알파-베타 동안 하위 트리는 일시적으로 첫 번째 플레이어의 이점에 의해 지배되거나 그 반대의 경우도 마찬가지이다. 이 이점은 이동 순서가 잘못된 경우 탐색 중에 여러 번 전환될 수 있으며, 각 전환은 비효율성을 초래한다. 검색된 위치 수가 현재 위치에 가까워질수록 기하급수적으로 감소하므로, 초기 이동 정렬에 상당한 노력을 기울일 가치가 있다.
4. 1. 휴리스틱 개선
알파-베타 가지치기의 정확성을 훼손하지 않으면서 탐색 효율을 높이기 위해 휴리스틱 정렬을 사용할 수 있다. 휴리스틱 정렬은 알파-베타 컷오프를 유발할 가능성이 높은 노드를 우선적으로 탐색하도록 순서를 조정한다. 예를 들어, 체스에서는 말을 잡는 수나 이전 탐색에서 높은 점수를 받은 수를 우선적으로 고려할 수 있다.[10] 킬러 휴리스틱은 이전 탐색에서 베타 컷오프를 발생시킨 수를 우선적으로 고려하는 방법이다. 이 아이디어는 반박 테이블 집합으로 일반화할 수도 있다.[10]
반복 심화 깊이 우선 탐색과 함께 휴리스틱 정렬을 사용하면 탐색 깊이를 점진적으로 늘려나가면서도 효율성을 높일 수 있다. 실제로, 이동 순서는 종종 반복 심화 깊이 우선 탐색과 같은 이전의 작은 탐색 결과에 의해 결정된다.
야망 창(좁은 탐색 창)을 설정하여 탐색 속도를 높일 수 있다. 극단적인 경우, 알파와 베타가 동일하게 수행되는 ''제로 창 탐색'', ''널 창 탐색'' 또는 ''스카우트 탐색''이라고 하는 기법이 사용된다. 이는 좁은 창에서 얻은 추가 깊이와 간단한 승/패 평가 함수가 결정적인 결과로 이어질 수 있는 게임 종료 시점에 가까운 승/패 탐색에 특히 유용하다. 야망 탐색이 실패하면, 실패가 "높음"(창의 높은 가장자리가 너무 낮음)인지 "낮음"(창의 낮은 가장자리가 너무 높음)인지를 쉽게 감지할 수 있다. 이를 통해 해당 위치의 재탐색에 유용할 수 있는 창 값에 대한 정보를 얻을 수 있다.
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*와 같은 알고리즘은 최선 우선 탐색 전략을 사용한다. 이는 잠재적으로 시간 효율성을 높일 수 있지만, 일반적으로 공간 효율성 측면에서 큰 대가를 치른다.[13]
7. 응용
게임 트리는 체스, 체커, 리버시와 같은 2인 제로섬 게임을 표현하는 데 사용될 수 있다. 게임 트리의 각 노드는 게임에서 가능한 상황을 나타내며, 각 분기의 끝에 있는 노드(결과)에는 다음 수를 두는 플레이어에게 해당 결과의 가치를 나타내는 숫자 점수가 할당된다.[9]
알파-베타 가지치기 알고리즘은 최대화 플레이어가 보장하는 최소 점수(알파)와 최소화 플레이어가 보장하는 최대 점수(베타)를 유지한다. 초기에는 알파는 음의 무한대, 베타는 양의 무한대로 설정되어 두 플레이어 모두 최악의 점수에서 시작한다. 최소화 플레이어(베타)가 보장하는 최대 점수가 최대화 플레이어(알파)가 보장하는 최소 점수보다 작아지면(베타 < 알파), 최대화 플레이어는 해당 노드의 하위 노드를 더 이상 고려할 필요가 없다. 실제 게임에서는 이러한 상황에 도달할 수 없기 때문이다.
예를 들어, 체스 게임에서 자신의 차례에 "A"라는 수를 두면 플레이어의 위치가 좋아진다. 더 나은 수가 있는지 확인하기 위해 계속 수를 찾던 중 "B"라는 수도 좋은 수임을 발견했지만, 이 수를 두면 상대방이 두 수 안에 체크메이트를 걸 수 있다는 것을 알게 된다. 따라서 "B" 수는 상대방에게 승리를 허용하므로 더 이상 고려할 필요가 없다. "B" 수를 뒀을 때 상대방이 얻을 수 있는 최대 점수는 음의 무한대, 즉 플레이어의 패배이며, 이는 이전에 찾은 최소 점수보다 작다. 반면 "A" 수는 두 수 안에 강제된 패배를 초래하지 않는다.
참조
[1]
웹사이트
The Dartmouth Workshop--as planned and as it happened
https://www-formal.s[...]
2006-10-30
[2]
웹사이트
Human Level AI Is Harder Than It Seemed in 1955
http://www-formal.st[...]
Stanford University
2006-12-20
[3]
간행물
Computer science as empirical inquiry: symbols and search
1976-03-01
[4]
간행물
The Alpha–beta Heuristic
Massachusetts Institute of Technology
1961-12-04
[5]
웹사이트
A Chess Playing Program
http://www.kotok.org[...]
RLE and MIT Computation Center
2006-07-01
[6]
서적
Encyclopedia of Artificial Intelligence
Wiley
1987-05
[7]
간행물
An analysis of alpha-beta pruning
[8]
간행물
Control strategies for two-player games
1989-06-01
[9]
뉴스
Alpha-Beta Soup
https://archive.org/[...]
2021-10-19
[10]
서적
27th Annual Symposium on Foundations of Computer Science
[11]
간행물
Asymptotic Properties of Minimax Trees and Game-Searching Procedures
[12]
간행물
The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality
[13]
간행물
Search techniques
[14]
서적
Artificial Intelligence: A Modern Approach
http://aima.cs.berke[...]
Pearson Education, Inc.
[15]
간행물
Computer Science as Empirical Inquiry: Symbols and Search
http://archive.compu[...]
2006-12-21
[16]
웹인용
The Alpha–beta Heuristic (AIM-030)
http://hdl.handle.ne[...]
Massachusetts Institute of Technology
1961-12-04
[17]
웹인용
Human Level AI Is Harder Than It Seemed in 1955
http://www-formal.st[...]
2006-11-27
[18]
웹인용
MIT Artificial Intelligence Memo 41
http://www.kotok.org[...]
2004-12-03
[19]
웹인용
Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)
http://www.cs.ualber[...]
J. Wiley & Sons
1987-05
[20]
간행물
An Analysis of Alpha–Beta Pruning
http://www.fileserve[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com