알파-베타 가지치기
| 분류 | 검색 알고리즘 |
|---|---|
| 최악 시간복잡도 | |
| 최선 시간복잡도 |
| 목록 |
|---|
| 관련 주제 |
알파-베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화(미니맥스) 알고리즘을 적용할 때 평가(evaluate)하는 노드의 수를 줄이기 위한 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘이라고도 하며, 기계가 플레이하는 2인용 게임(틱택토, 체스, 바둑)에 주로 사용된다. 이 알고리즘은 이전에 평가한 노드보다 현재 평가하는 노드가 더 좋지 않을 가능성이 있으면 평가를 중단한다. 이 노드의 남은 형제(sibling) 노드와 모든 후손 노드는 가지치기되어 평가하지 않는다. 이 알고리즘을 일반적인 미니맥스에 적용하면 동일한 결과를 얻게 된다. 최종 결정에 영향을 미치지 않는 가지들을 쳐낼 뿐이다.[1]
역사[편집]
앨런 뉴얼과 허버트 사이먼에 따르면 1958년 당시에도 알파-베타는 여러 번 재발명되었다.[2] 아서 새뮤얼(Arthur Samuel)이 알파-베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 미국에서 독립적으로 알파-베타 가지치기의 기초를 세웠다.[3] 존 매카시도 비슷한 아이디어를 1956 다트머스 회의에서 제안하면서 "근사치"[4]라는 용어를 사용했고, 1961년에 MIT에 다니는 앨런 코톡(Alan Kotok)에게도 가르쳤다.[5] Alexander Brudno도 1963년에 독자적으로 발표하였다.[6] 도널드 커누스와 로널드 W. 무어는 1975년에 알고리즘을 재정립하였고,[7] 1982년 유디 펄이 이 방법이 최적임을 증명하였다.
단순한 미니맥스 너머의 발전[편집]
알파-베타 가지치기의 장점은 탐색 트리의 가지를 쳐낼 수 있다는 점이다. 이러한 경우 탐색은 ‘더 유망한’ 서브트리에 한해서 이루어지고, 같은 시간 안에 더 깊은 노드까지 탐색할 수 있다. 알파-베타 가지치기는 분기 한정법의 일종이다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색 깊이가 기본적인 미니맥스의 반 이하가 되도록 최적화할 수 있다.
분기 계수를 b라고 하고, ply(한 턴의 1/2)의 검색 깊이를 d라고 한다면, (이동순서가 최악이라면) 평가된 잎 노드 위치는 O(b*b*...*b) = O(b**d)이므로 기본적인 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가된 잎 노드의 수는 홀수 깊이일 때 약 O(b*1*b*1*...*b) 이고, 짝수깊이일 때 O(b*1*b*1*...*1) 즉, O(b**d/2)이다. 후자의 경우 사실상의 분기 계수는 제곱근으로 줄어든다. 다시 말해 같은 양의 연산 작업으로 거의 두 배 만큼 더 깊게 탐색할 수 있다. b*1*b*1... 식의 설명은 최적의 이동을 찾기 위해서는 첫 번째 플레이어의 이동은 반드시 연구돼야 하지만, 사실은 두 번째 플레이어의 최적의 움직임은 첫 번째 플레이어의 첫 번째 움직임을 제외한 모든 움직임을 쳐내기 위해 필요하다. 노드 순서가 랜덤하다면, 평균적으로 평가하는 노드의 수는 약 O(b**3d/4)이다.
의사코드[편집]
알파-베타 가지치기의 페일 소프트(fail-soft) 버전 의사코드는 다음과 같다:
01 function alphabeta(node, depth, α, β, maximizingPlayer) 02 if depth = 0 or node is a terminal node 03 return the heuristic value of node 04 if maximizingPlayer 05 v := -∞ 06 for each child of node 07 v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) 08 α := max(α, v) 09 if β ≤ α 10 break (* β cut-off *) 11 return v 12 else 13 v := ∞ 14 for each child of node 15 v := min(v, alphabeta(child, depth - 1, α, β, TRUE)) 16 β := min(β, v) 17 if β ≤ α 18 break (* α cut-off *) 19 return v
페일 소프트 알파-베타에서는 알파와 베타값 범위를 넘는 v값을 반환할 수 있다. (v < α or v > β) 반면에 페일 하드 알파-베타는 반환하는 값을 알파와 베타의 범위로 제한한다. ()
각주[편집]
- ↑ Russell, Stuart J.; Norvig, Peter (2010). 《Artificial Intelligence: A Modern Approach》 3판. Upper Saddle River, New Jersey: Pearson Education, Inc. 167쪽. ISBN 0-13-604259-7.
- ↑ Newell, Allen; Herbert A. Simon (March 1976). “Computer Science as Empirical Inquiry: Symbols and Search” (PDF). 《Communications of the ACM》 19 (3): 113. doi:10.1145/360018.360022. 2007년 6월 28일에 원본 문서 (PDF)에서 보존된 문서. 2006년 12월 21일에 확인함.
- ↑ Edwards, D.J.; Hart, T.P. (1961년 12월 4일). “The Alpha–beta Heuristic (AIM-030)”. Massachusetts Institute of Technology. 2006년 12월 21일에 확인함.
- ↑ McCarthy, John (2006년 11월 27일). “Human Level AI Is Harder Than It Seemed in 1955”. 2006년 12월 20일에 확인함.
- ↑ Kotok, Alan (2004년 12월 3일). “MIT Artificial Intelligence Memo 41”. 2020년 11월 6일에 원본 문서에서 보존된 문서. 2006년 7월 1일에 확인함.
- ↑ Marsland, T.A. (May 1987). “Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)” (PDF). J. Wiley & Sons. 159–171쪽. 2008년 10월 30일에 원본 문서 (PDF)에서 보존된 문서. 2006년 12월 21일에 확인함.
- ↑ Knuth, D. E.; Moore, R. W. (1975). “An Analysis of Alpha–Beta Pruning” (PDF). 《Artificial Intelligence》 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3.[깨진 링크(과거 내용 찾기)]
참고 문헌[편집]
- George T. Heineman, Gary Pollice, and Stanley Selkow (2008). 〈Chapter 7: Path Finding in AI〉. 《Algorithms in a Nutshell》. 오라일리 미디어. 217–223쪽. ISBN 978-0-596-51624-6.
- 유디 펄, Heuristics, Addison-Wesley, 1984
- John P. Fishburn (1984). 〈Appendix A: Some Optimizations of α-β Search〉. 《Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis)》. UMI Research Press. 107-111쪽. ISBN 0-8357-1527-2.