Changes

Jump to: navigation, search

Alpha-Beta

1,840 bytes added, 15:20, 1 December 2021
no edit summary
=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]]
* [[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 » [[Leela 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
* [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], [[: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 />
'''[[Search|Up one level]]'''
[[Category:Quotes]]
[[Category:McCarthy Quotes]]
[[Category:Vangelis]]

Navigation menu