알파-베타 가지치기: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Singleheart (토론 | 기여) 태그: m 모바일 웹 |
Singleheart (토론 | 기여) 태그: m 모바일 웹 |
||
14번째 줄:
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을 포함한 그의 학생들에게도 알렸다.<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) 이다. 후자의 경우 사실상의 분기 계수는 제곱근으로 줄어든다. 다시 말해
== 의사코드 ==
| |||