Editing Alpha–beta pruning (section)

== History ==
John McCarthy during the [[Dartmouth workshop|Dartmouth Workshop]] met Alex Bernstein of [[IBM]], who was writing a chess program. McCarthy invented alpha–beta search and recommended it to him, but Bernstein was "unconvinced".<ref>{{cite web |last=McCarthy |first=John |date=2006-10-30 |title=The Dartmouth Workshop--as planned and as it happened |url=https://www-formal.stanford.edu/jmc/slides/dartmouth/dartmouth/node1.html |access-date=2023-10-29 |website=www-formal.stanford.edu}}</ref>

[[Allen Newell]] and [[Herbert A. Simon]] who used what [[John McCarthy (computer scientist)|John McCarthy]] calls an "approximation"<ref name="JMC">{{cite web
  | 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
  | access-date = 2006-12-20 |publisher=Stanford University
}}</ref> in 1958 wrote that alpha–beta "appears to have been reinvented a number of times".<ref name="NS">{{cite journal |last1=Newell |first1=Allen |last2=Simon |first2=Herbert A. |title=Computer science as empirical inquiry: symbols and search |journal=Communications of the ACM |date=1 March 1976 |volume=19 |issue=3 |pages=113–126 |doi=10.1145/360018.360022 |doi-access=free }}</ref> [[Arthur Samuel (computer scientist)|Arthur Samuel]] had an early version for a checkers simulation. Richards, Timothy Hart, Michael Levin and/or Daniel Edwards also invented alpha–beta independently in the [[United States]].<ref name="AIM30">{{cite tech report |last1=Edwards |first1=D.J. |last2=Hart |first2=T.P.|date=4 December 1961|title=The Alpha–beta Heuristic |id=AIM-030 |publisher=[[Massachusetts Institute of Technology]] |hdl=1721.1/6098}}</ref> McCarthy proposed similar ideas during the [[Dartmouth workshop]] in 1956 and suggested it to a group of his students including [[Alan Kotok]] at MIT in 1961.<ref name="AIM41">{{cite web | last=Kotok | first=Alan |orig-date=1962 |title=A Chess Playing Program |publisher=RLE and MIT Computation Center |id=Memo 41 |work=Artificial Intelligence Project | date=2004 | url=http://www.kotok.org/AI_Memo_41.html | access-date=2006-07-01}}</ref> [[Alexander Brudno]] independently conceived the alpha–beta algorithm, publishing his results in 1963.<ref name="Marsland">{{cite book |chapter=Computer Chess Methods |title=Encyclopedia of Artificial Intelligence |editor1-first=S. |editor1-last=Shapiro |last=Marsland |first=T.A.|date=May 1987 |publisher=Wiley |pages=159–171 |chapter-url=http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf |isbn=978-0-471-62974-0|archive-url=https://web.archive.org/web/20081030023047/http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf |archive-date=2008-10-30 }}</ref> [[Donald Knuth]] and Ronald W. Moore refined the algorithm in 1975.<ref name="Knuth-Moore">{{cite journal|last1=Knuth|first1=Donald E.|last2=Moore|first2=Ronald W.|s2cid=7894372|year=1975|title=An analysis of alpha-beta pruning|journal=Artificial Intelligence|volume=6|issue=4|pages=293–326|doi=10.1016/0004-3702(75)90019-3}}</ref><ref name="Abramson">{{cite journal |last1=Abramson |first1=Bruce |title=Control strategies for two-player games |journal=ACM Computing Surveys |date=1 June 1989 |volume=21 |issue=2 |pages=137–161 |doi=10.1145/66443.66444 |s2cid=11526154 }}</ref> [[Judea Pearl]] proved its optimality in terms of the expected running time for trees with randomly assigned leaf values in two papers.<ref name="Pearl1980" /><ref name="Pearl1982" /> The optimality of the randomized version of alpha–beta was shown by Michael Saks and Avi Wigderson in 1986.<ref name="SaksWigderson" />