Changes

Jump to: navigation, search

Alpha-Beta

2,249 bytes added, 15:20, 1 December 2021
no edit summary
'''[[Main Page|Home]] * [[Search]] * Alpha-Beta'''
[[FILE:AlphaBetaBackB.jpg|border|right|thumb|220px|link=http://vangelismovements.com/alphabeta.htm|Alpha Beta <ref>[http://vangelismovements.com/alphabeta.htm Alpha Beta - Astral Abuse] a look at the music of [[Videos#:Category:Vangelis|Vangelis Papathanassiou]]</ref> ]]
The '''Alpha-Beta''' algorithm (Alpha-Beta Pruning, Alpha-Beta Heuristic <ref>[[Arthur Samuel]] ('''1967'''). ''Some Studies in Machine Learning. Using the Game of Checkers. II-Recent Progress''. [https://researcher.ibm.com/researcher/files/us-beygel/samuel-checkers.pdf pdf], IBM Journal - November 1967,
=History=
Alpha-Beta was invented independently by several researchers and pioneers from the 50s <ref>[[Jaap van den Herik]] ('''2001'''). ''Science, Competition and Business''. [[ICGA Journal#24_4|ICGA Journal, Vol. 24, No. 4]], [http://arno.uvt.nl/show.cgi?fid=107331 pdf]</ref>, and further research until the 80s, most notable by
* [[John McCarthy]] proposed the idea of Alpha-Beta in after the representation of the [[Timeline#1955The Bernstein Chess Program|1955Chess Program]] by [[Alex Bernstein]] <ref>[http://www-formal.stanford.edu/jmc/slides/dartmouth/dartmouth/node1.html The Dartmouth Workshop--as planned and as it happened]</ref> at the [https://en.wikipedia.org/wiki/Dartmouth_Conference Dartmouth_workshop Dartmouth ConferenceWorkshop] in [[Timeline#1956|1956]] <ref>[http://www-formal.stanford.edu/jmc/history/dartmouth/dartmouth.html A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence] by [[John McCarthy]], [[Marvin Minsky]], [https://en.wikipedia.org/wiki/Nathan_Rochester [Nathaniel Rochester]], [[Claude Shannon]], August 31, '''1955'''</ref>
* [[Allen Newell]] and [[Herbert Simon]] Approximation in [[Timeline#1958|1958]]
* [[Arthur Samuel]] Approximation in [[Timeline#1959|1959]]
=See also=
* [[Alpha]]
* [[Stephen F. Wheeler#Alpha-Beta Benchmark|Alpha-Beta Benchmark]] by [[Stephen F. Wheeler]]
* [[Beta]]
* [[Beta-Cutoff]]
* [[James R. Slagle#TheoremProving|Theorem-Proving and M & N procedure]]
* [[Window]]
 
=Videos=
* [[Patrick Winston#Lecture_6|Patrick Winston - Video Lecture 6]]
* [[History#AIPerspective|The History of Computer Chess - an AI Perspective - Video]]
=Selected Publications=
* [[Toshihide Ibaraki]] ('''1986'''). ''Generalization of Alpha-Beta and SSS* Search Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 29
* [[Matthew Huntbach]], [[F. Warren Burton]] ('''1988'''). ''[http://www.sciencedirect.com/science/article/pii/0020025588900540 Alpha-beta search on virtual tree machines]''. [http://www.journals.elsevier.com/information-sciences/ Information Sciences], Vol. 44, No. 1
* [[Robert Hyatt]], [[Bruce W. Suter]], [[Harry Nelson]] ('''1989'''). ''A Parallel Alpha-Beta Tree Searching Algorithm''. [https://www.journals.elsevier.com/parallel-computing Parallel Computing], Vol. 10, No. 3
==1990 ...==
* [[Ingo Althöfer]], [[Bernhard Balkenhol]] ('''19921991'''). ''[https://www.sciencedirect.com/science/article/abs/pii/000437029190042I#! A Game Tree with Distinct Leaf Values which is Easy for the Alpha-Beta Algorithm]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 52, No. 2
* [[Alois Heinz]], [[Christoph Hense]] ('''1993'''). ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.872 Bootstrap learning of α-β-evaluation functions]''. [http://dblp.uni-trier.de/db/conf/icci/icci1993.html#HeinzH93 ICCI 1993], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.872&rep=rep1&type=pdf pdf]
* [[Van-Dat Cung]] ('''1993'''). ''Parallelizations of Game-Tree Search''. [http://dblp.uni-trier.de/db/conf/parco/parco1993.html#Cung93 PARCO 1993], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.6959&rep=rep1&type=pdf pdf] hosted by [https://en.wikipedia.org/wiki/CiteSeer CiteSeerX]
* [[Alois Heinz]] ('''1994'''). ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.3994 Efficient Neural Net α-β-Evaluators]''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.3994&rep=rep1&type=pdf pdf]
* [[Yanjun Zhang]] ('''1995'''). ''[https://epubs.siam.org/doi/abs/10.1137/S009753979223037X On the Optimality of Randomized Alpha-Beta Search]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Computing SIAM Journal on Computing], Vol. 24, No. 1
* [[Ernst A. Heinz]] ('''1999'''). ''[http://people.csail.mit.edu/heinz/node1.html#scale-cchess Scalable Search in Computer Chess]''. [https://en.wikipedia.org/wiki/Morgan_Kaufmann Morgan Kaufmann], ISBN 3-528-05732-7
==2000 ...==
* [[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Analysis of pruned minimax trees''. [https://dl.dropboxusercontent.com/u/55295461/analysis/pruning.pdf pdf] » [[Late Move Reductions]], [[Null Move Pruning]]
* [[Jr-Chang Chen]], [[I-Chen Wu]], [[Wen-Jie Tseng]], [[Bo-Han Lin]], [[Chia-Hui Chang]] ('''2015'''). ''[https://ir.nctu.edu.tw/handle/11536/124541 Job-Level Alpha-Beta Search]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 7, No. 1
* [[Bojun Huang]] ('''2015'''). ''[https://www.semanticscholar.org/paper/Pruning-Game-Tree-by-Rollouts-Huang/a38b358745067f71a9c780db117ae2471e693d63 Pruning Game Tree by Rollouts]''. [[AAAI]] » [[Monte-Carlo Tree Search|MCTS]], [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]], [[Bojun Huang#Rollout|Rollout Paradigm]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[LCZeroLeela Chess Zero]]</ref>* [[Naoyuki Sato]], [[Kokolo Ikeda]] ('''2016'''). ''[https://ieeexplore.ieee.org/document/7860427 Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games]''. [https://dblp.uni-trier.de/db/conf/cig/cig2016.html CIG 2016]
* [[Hendrik Baier]] ('''2017'''). ''[https://link.springer.com/chapter/10.1007/978-3-319-57969-6_5 A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta]''. [https://link.springer.com/book/10.1007%2F978-3-319-57969-6 Computer Games] » [[MCαβ]], [[Monte-Carlo Tree Search]]
* [[Shogo Takeuchi]] ('''2019'''). ''Advice is Useful for Game AI: Experiments with Alpha-Beta Search Players in Shogi''. [[Advances in Computer Games 16]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=13725 Basic alpha-beta question] by John Scalo, [[CCC]], January 06, 1998
* [https://www.stmintz.com/ccc/index.php?id=19760 alpha-beta is silly?] by [[Werner Inmann]], [[CCC]], June 02, 1998
: [https://www.stmintz.com/ccc/index.php?id=19922 Re: alpha-beta is silly?] by [[Don Dailey]], [[CCC]], June 03, 1998* [https://www.stmintz.com/ccc/index.php?id=28262 Re: Basic questions about alpha beta] by [[Bruce Moreland]], [[CCC]], September 28, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=98141 Another Alpha-Beta algorithm question] by Jeff Anderson, [[CCC]], February 18, 2000
* [https://www.stmintz.com/ccc/index.php?id=314585 Fail soft alpha-beta] by [[Russell Reagan]], [[CCC]], September 08, 2003 » [[Fail-Soft]]
* [https://www.stmintz.com/ccc/index.php?id=319935 Complexity Analyses of Alpha-Beta] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], October 07, 2003
* [https://www.stmintz.com/ccc/index.php?id=343084 Mixing alpha-beta with PN search] by [[Tord Romstad]], [[CCC]], January 18, 2004 » [[Proof-number Number Search]]
* [https://www.stmintz.com/ccc/index.php?id=347303 Question for Hyatt about Alpha/Beta] by Bob Durrett, [[CCC]], February 05, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=60581 Search] by [[Laurie Tunnicliffe]], [[CCC]], June 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=66414 Alpha-Beta as a rollouts algorithm] by [[Daniel Shawul]], [[CCC]], January 25, 2018 » [[MCαβ]], [[Monte-Carlo Tree Search]], [[Scorpio]]
==2020 ...==* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74771 AB search with NN on GPU...] by [[Srdja Matovic]], [[CCC]], August 13, 2020 » [[GPU]], [[Neural Networks|NN]] <ref>[https://forums.developer.nvidia.com/t/kernel-launch-latency/62455 kernel launch latency - CUDA / CUDA Programming and Performance - NVIDIA Developer Forums] by LukeCuda, June 18, 2018</ref>* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77208 Mathematical proof that AB with B-cutoff does not miss a variation] by [[Yves De Billoëz]], [[CCC]], April 30, 2021* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77497 Alpha-beta search for drawing endgames] by Emanuel Torres, [[CCC]], June 16, 2021 » [[Draw Evaluation]], [[Graph History Interaction]], [[Repetitions]]
=External Links=
* [https://en.wikipedia.org/wiki/Alpha-beta_pruning Alpha-beta Pruning from Wikipedia]
* [http://web.archive.org/web/20070811182954/www.seanet.com/%7Ebrucemo/topics/alphabeta.htm Alpha-Beta Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [http://www.ics.uci.edu/%7Eeppstein/180a/970422.html Lecture notes for April 22, 1997 Alpha-Beta Search] by [[David Eppstein]]
* [http://web.archive.org/web/20070113132331/http://www.maths.nottingham.ac.uk/personal/anw/G13GT1/alphabet.html G13GAM -- Game Theory - alpha-beta pruning] by [[Andy Walker]]([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])* [https://web.archive.org/web/20120331060714/http://www.top-5000.nl/authors/rebel/chess840.htm#SEARCH Alpha-Beta] from [https://web.archive.org/web/20120331060714/http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]]([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])* [https://web.archive.org/web/20060107101829/http://chess.verhelst.org/1997/03/10/search/#alpha-beta Alpha-Beta search] from [[Paul Verhelst|Paul Verhelst's]] [http://www.xs4all.nl/%7Everhelst/chess/programming.html Computer Chess Sites]* ([httphttps://wwwen.computerhistorywikipedia.org/chesswiki/main.php?sec=thm-42b86c2029762&sel=thm-42b86c6ab9811 The Minimax Algorithm and Alpha-Beta Pruning] from [[The Computer History Museum]Wayback_Machine Wayback Machine])* [httphttps://www.emunix.emich.edu/%7Eevett~mevett/AI/AlphaBeta_movie/sld001.htm Alpha-Beta Slide Show in 18 steps] by [httphttps://staff.scmb.uq.edu.au/staffprofile/321/mikael-boden Mikael Bodén]* [http://hamedahmadi.com/gametree/ An Introduction to Game Tree Algorithms] by [[Hamed Ahmadi]]* [https://vangelismovements.com/alphabeta.htm Alpha Beta] - [https://en.wikipedia.org/wiki/Vangelis_discography Astral Abuse], 1971, [https://en.wikipedia.org/wiki/YouTube YouTube] Video: Alpha Beta are [http://www.vangelismovements.com/vilmalado.htm Vilma Lado], [[Videos#:Category:Vangelis|Vangelis Papathanassiou]], [https://tr.wikipedia.org/wiki/Argyris_Koulouris Argyris Koulouris] and [https://en.wikipedia.org/wiki/Giorgio_Gomelsky Giorgio Gomelski]
: {{#evu:https://www.youtube.com/watch?v=qhmwTc_MNjM|alignment=left|valignment=top}}
=References=
<references />
 
'''[[Search|Up one level]]'''
[[Category:Quotes]]
[[Category:McCarthy Quotes]]
[[Category:Vangelis]]

Navigation menu