|
|공간복잡도 =
}}
'''알파-베타 가지치기'''(Alpha–beta pruning)는 탐색트리에서 미니맥스[[최소극대화]] 알고리즘에 의해따라 평가되는 노드의 수를 줄이기 위한 검색 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘이라고도 불리는데, 기계가 플레이하는 2인용게임([[틱택토]], [[체스]], [[바둑]])에 주로 사용된다. 이 알고리즘은 이전에 평가한 이동보다 평가하고 있는 이동이 더 좋지 않다는않을 가능성이 하나라도 발견된다면발견되면 평가하고 있는 이동의 평가를 완전히 멈춘다. 이러한이 이동은 더 이상 평가될평가할 필요가 없다. 이 알고리즘이 표준 미니맥스 트리에 적용된다면 미니맥스와 똑같은 결과를 반환할 것이지만, 마지막최종 결정에 영향을 미치지 않는 가지들은 잘라낼 것이다.<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>
== 역사 ==
John[[존 McCarthy가매카시 (컴퓨터 과학자)|존 매카시]]가 "근사치"<ref name="JMC">{{웹 인용| author = McCarthy, John | title = Human Level AI Is Harder Than It Seemed in 1955 | date = 27 November 2006 | url = http://www-formal.stanford.edu/jmc/slides/wrong/wrong-sli/wrong-sli.html | accessdate = 2006-12-20}}</ref>로 부른 것을 사용한 Allen Newell과 Herbert A. Simon은 1958년에 알파-베타는 여러 번 재조명된 것 같다고 적었다.<ref name=NS>{{저널 인용 | author1=Newell, Allen | author2=Herbert A. Simon | title=Computer Science as Empirical Inquiry: Symbols and Search | journal=Communications of the ACM | volume=19 | issue=3 | pages=113 | date=March 1976 | 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 | format=PDF | accessdate=2006-12-21 | 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 | 깨진링크=예 }}</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> McCarthy는매카시는 비슷한 아이디어를 1956 Dartmouth다트머스 회의에서 제시하였고, 1961년에 MIT에 다니는 Alan Kotok을 포함한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}}</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 |deadurl=yes |archiveurl=https://web.archive.org/web/20081030023047/http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf |archivedate=October 30, 2008 }}</ref> Donald[[도널드 Knuth와커누스]]와 Ronald W. Moore는 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년 Judea Pearl이 이 방법이 최선임을최적임을 증명하였다.
== 단순한 미니맥스 너머의 발전 ==
알파-베타 가지치기의 이점은장점은 탐색트리의 가지가 제거될 수 있다는 점이다. 이러한 경우 탐색은 ‘더 유망한’ 서브트리에 한해서 이루어지고, 같은 시간 안에 더 깊은 노드까지 탐색할 수 있다. 알파-베타 알고리즘은 이전 모델처럼 분기 한정법 알고리즘으로 분류된다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 실질적인 깊이가 기본적인 미니맥스의 깊이의 반 이하가 되도록 최적화할 수 있다.
분기 계수를 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)이다.
|
