알파-베타 가지치기 문서 원본 보기

{{위키데이터 속성 추적}}
{{알고리즘 정보
|그림 =
|그림설명 =
|분류 =[[검색 알고리즘]]
|자료구조 =
|최선 =<math>O\left(\sqrt{b^d}\right)</math>
|평균 =
|최악 =<math>O(b^d)</math>
|공간복잡도 =
}}
{{그래프 탐색 알고리즘}}
'''알파-베타 가지치기'''(Alpha–beta pruning)는 탐색 [[트리 구조|트리]]에서 [[최소극대화]](미니맥스) 알고리즘을 적용할 때 평가(evaluate)하는 노드의 수를 줄이기 위한 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘의 일종으로, 기계가 플레이하는 2인용 게임([[틱택토]], [[체스]], [[바둑]])에 주로 사용된다. 이 알고리즘은 이전에 평가한 노드보다 현재 평가하는 노드가 더 좋지 않을 가능성이 존재하면 평가를 중단한다. 이 노드의 남은 형제(sibling) 노드와 모든 후손 노드는 가지치기되어 평가하지 않는다. 이 알고리즘을 일반적인 미니맥스에 적용하면 동일한 결과를 얻게 된다. 최종 결정에 영향을 미치지 않는 가지들을 쳐낼 뿐이다.<ref name="RN10">{{서적 인용| first = Stuart J. | last = Russell | first2 = Peter | last2 = Norvig | title = Artificial Intelligence: A Modern Approach | url = http://aima.cs.berkeley.edu/ | year = 2010 | edition = 3rd | publisher = Pearson Education, Inc. | publication-place = Upper Saddle River, New Jersey | isbn = 0-13-604259-7 | author-link=Stuart J. Russell | author2-link=Peter Norvig | page=167}}</ref>

== 역사 ==
[[앨런 뉴얼]]과 [[허버트 사이먼]]에 따르면 1958년 당시에도 알파-베타는 여러 번 재발명되었다.<ref name="NS">{{저널 인용|title=Computer Science as Empirical Inquiry: Symbols and Search|journal=Communications of the ACM|author1=Newell, Allen|author2=Herbert A. Simon|url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-3.Computer_science_as_empirical_inquiry/2-3.Computer_science_as_empirical_inquiry.newell_simon.1975.ACM.062303007.pdf|date=March 1976|volume=19|issue=3|pages=113|format=PDF|doi=10.1145/360018.360022|보존url=https://www.webcitation.org/5PwLLXQSN?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-3.Computer_science_as_empirical_inquiry/2-3.Computer_science_as_empirical_inquiry.newell_simon.1975.ACM.062303007.pdf|보존날짜=2007-06-28|url-status=dead|accessdate=2006-12-21}}</ref> [[아서 새뮤얼]](Arthur Samuel)이 알파-베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 미국에서 독립적으로 알파-베타 가지치기의 기초를 세웠다.<ref name="AIM30">{{웹 인용|author1=Edwards, D.J.  |author2=Hart, T.P.  | title = The Alpha–beta Heuristic (AIM-030)  | publisher = Massachusetts Institute of Technology  | date = 4 December 1961  | url = http://hdl.handle.net/1721.1/6098  | accessdate = 2006-12-21}}</ref> [[존 매카시 (컴퓨터 과학자)|존 매카시]]도 비슷한 아이디어를 1956 다트머스 회의에서 제안하면서 "근사치"<ref name="JMC">{{웹 인용|url=http://www-formal.stanford.edu/jmc/slides/wrong/wrong-sli/wrong-sli.html|title=Human Level AI Is Harder Than It Seemed in 1955|author=McCarthy, John|date=27 November 2006|accessdate=2006-12-20}}</ref>라는 용어를 사용했고, 1961년에 MIT에 다니는 [[앨런 코톡]](Alan Kotok)에게도 가르쳤다.<ref name="AIM41">{{웹 인용 | last=Kotok | first=Alan | title=MIT Artificial Intelligence Memo 41 | date=3 December 2004 | url=http://www.kotok.org/AI_Memo_41.html | accessdate=2006-07-01 | archive-date=2020-11-06 | archive-url=https://web.archive.org/web/20201106235753/http://www.kotok.org/AI_Memo_41.html | url-status= }}</ref> Alexander Brudno도 1963년에 독자적으로 발표하였다.<ref name=Marsland>{{웹 인용|author=[http://www.cs.ualberta.ca/~tony/ Marsland, T.A.] |title=Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor) |publisher=J. Wiley & Sons |date=May 1987 |pages=159–171 |url=http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf |format=PDF |accessdate=2006-12-21 |url-status=dead |archiveurl=https://web.archive.org/web/20081030023047/http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf |archivedate=October 30, 2008 }}</ref> [[도널드 커누스]]와 로널드 W. 무어는 1975년에 알고리즘을 재정립하였고,<ref name=Knuth-Moore>{{저널 인용  | author1 = Knuth, D. E.  | author2 = Moore, R. W.  | title = An Analysis of Alpha–Beta Pruning  | journal = Artificial Intelligence  | volume = 6  | issue = 4  | year = 1975  | pages = 293–326  | url = http://www.fileserve.com/file/ZgR5t3j/An_Analysis_of_Alpha-Beta_Pruning.pdf  | doi = 10.1016/0004-3702(75)90019-3  }}{{깨진 링크|url=http://www.fileserve.com/file/ZgR5t3j/An_Analysis_of_Alpha-Beta_Pruning.pdf }}</ref> 1982년 [[유디 펄]]이 이 방법이 최적임을 증명하였다.

== 단순한 미니맥스 너머의 발전 ==
알파-베타 가지치기의 장점은 탐색 트리의 가지를 쳐낼 수 있다는 점이다. 이러한 경우 탐색은 ‘더 유망한’ 서브트리에 한해서 이루어지고, 같은 시간 안에 더 깊은 노드까지 탐색할 수 있다. 알파-베타 가지치기는 [[분기 한정법]]의 일종이다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색 깊이가 기본적인 미니맥스의 반 정도가 되도록 최적화할 수 있다.

분기 계수를 b라고 하고, 검색 깊이를 d라고 한다면, (이동순서가 최악이라면) 평가된 잎 노드 위치는 <math>O(b \times b \times \cdots  \times b) = O(b^d)</math>이므로 기본적인 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가된 잎 노드의 수는 홀수 깊이일 때 약 <math>O(b \times 1 \times b \cdots \times b ),</math> 즉 <math> O(b^\frac{d}{2})</math>이고, 짝수깊이일 때 <math>O(b \times 1 \times b \cdots \times 1)</math> 즉, <math>O(b^\frac{d}{2})</math>이다. 후자의 경우 사실상의 분기 계수는 제곱근으로 줄어든다. 다시 말해 같은 양의 연산 작업으로 거의 두 배 만큼 더 깊게 탐색할 수 있다. <math>b \times 1 \times b \cdots</math> 식의 설명은 최적의 이동을 찾기 위해서는 첫 번째 플레이어의 이동은 반드시 연구돼야 하지만, 사실은 두 번째 플레이어의 최적의 움직임은 첫 번째 플레이어의 첫 번째 움직임을 제외한 모든 움직임을 쳐내기 위해 필요하다. 노드 순서가 랜덤하다면, 평균적으로 평가하는 노드의 수는 약 <math>O(b^\frac{3d}{4})</math>이다.

== 의사코드 ==
알파-베타 가지치기의 페일 소프트(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 > β) 반면에 페일 하드 알파-베타는 반환하는 값을 알파와 베타의 범위로 제한한다. (<math>\alpha  \leq  v \leq  \beta </math>)

== 같이 보기 ==
* [[최소극대화]]
* [[분기 한정법]]
* [[조합 최적화]]
== 각주 ==
<references />

== 참고 문헌 ==
* {{서적 인용| author=George T. Heineman, Gary Pollice, and Stanley Selkow | title= Algorithms in a Nutshell | publisher=[[오라일리 미디어]] | year=2008 | chapter=Chapter 7: Path Finding in AI | pages = 217–223 | isbn=978-0-596-51624-6 }}
* [[유디 펄]], ''Heuristics'', Addison-Wesley, 1984
* {{서적 인용| author=John P. Fishburn | title= Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis) | url=https://archive.org/details/analysisofspeedu0000fish | publisher=[[UMI Research Press]] | year=1984 | chapter=Appendix A: Some Optimizations of α-β Search | pages = [https://archive.org/details/analysisofspeedu0000fish/page/107 107]-111 | isbn=0-8357-1527-2 }}

{{게임 이론}}

[[분류:검색 알고리즘]]
[[분류:그래프 알고리즘]]
[[분류:게임 인공지능]]
[[분류:최적화 알고리즘]]