Changes

Jump to: navigation, search

Alpha-Beta

35,913 bytes added, 08:13, 27 April 2018
Created page with "'''Home * Search * Alpha-Beta''' FILE:AlphaBetaBackB.jpg|border|right|thumb|220px|link=http://vangelismovements.com/alphabeta.htm|Alpha Beta <ref>[http://..."
'''[[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#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,
on the name Alpha-Beta Heuristic pp. 602: So named by [[John McCarthy|Prof. John McCarthy]]. This procedure was extensively investigated by Prof. John McCarthy and his students at M.I.T. but it has been inadequately described in the literature. It is, of course, not a heuristic at all, being a simple algorithmic procedure and actually only a special case of the more general "[https://en.wikipedia.org/wiki/Branch_and_bound branch and bound]" technique which was been rediscovered many times and which is currently being exploited in [https://en.wikipedia.org/wiki/Integer_programming integer programming] research.</ref> ) is a significant enhancement to the [[Minimax|minimax]] search algorithm that eliminates the need to search large portions of the [[Search Tree|game tree]] applying a [https://en.wikipedia.org/wiki/Branch_and_bound branch-and-bound] technique. Remarkably, it does this without any potential of overlooking a better [[Moves|move]]. If one already has found a quite good move and search for alternatives, '''one''' [[Refutation Move|refutation]] is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, [[Alpha|alpha]] and [[Beta|beta]]. They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Consider the following example...

=How it works=
Say it is White's turn to move, and we are searching to a [[Depth|depth]] of 2 (that is, we are consider all of White's moves, and all of Black's responses to each of those moves.) First we pick one of White's possible moves - let's call this Possible Move #1. We consider this move and every possible response to this move by black. After this analysis, we determine that the result of making Possible Move #1 is an even position. Then, we move on and consider another of White's possible moves (Possible Move #2.) When we consider the first possible counter-move by black, we discover that playing this results in black winning a Rook! In this situation, we can safely ignore all of Black's other possible responses to Possible Move #2 because we already know that Possible Move #1 is better. We really don't care ''exactly'' how much worse Possible Move #2 is. Maybe another possible response wins a Queen, but it doesn't matter because we know that we can achieve ''at least'' an even game by playing Possible Move #1. The full analysis of Possible Move #1 gave us a [[Lower Bound|lower bound]]. We know that we can achieve at least that, so anything that is clearly worse can be ignored.

The situation becomes even more complicated, however, when we go to a search [[Depth|depth]] of 3 or greater, because now both players can make choices affecting the game tree. Now we have to maintain both a [[Lower Bound|lower bound]] and an [[Upper Bound|upper bound]] (called [[Alpha]] and [[Beta]].) We maintain a lower bound because if a move is too bad we don't consider it. But we also have to maintain an upper bound because if a move at depth 3 or higher leads to a continuation that is too good, the other player won't allow it, because there was a better move higher up on the game tree that he could have played to avoid this situation. One player's lower bound is the other player's upper bound.

=Savings=
The savings of alpha beta can be considerable. If a standard minimax search tree has '''x''' [[Node|nodes]], an alpha beta tree in a well-written program can have a node count close to the square-root of '''x'''. How many nodes you can actually cut, however, depends on how well ordered your game tree is. If you always search the best possible move first, you eliminate the most of the nodes. Of course, we don't always know what the best move is, or we wouldn't have to search in the first place. Conversely, if we always searched worse moves before the better moves, we wouldn't be able to cut any part of the tree at all! For this reason, good [[Move Ordering|move ordering]] is very important, and is the focus of a lot of the effort of writing a good chess program. As pointed out by [[Michael Levin#Theorem|Levin]] in 1961, assuming constantly '''b''' moves for each node visited and search depth '''n''', the maximal number of leaves in alpha-beta is equivalent to minimax, '''b''' ^ '''n'''. Considering always the best move first, it is '''b''' ^ [https://en.wikipedia.org/wiki/Floor_and_ceiling_functions ceil(n/2)] plus '''b''' ^ [https://en.wikipedia.org/wiki/Floor_and_ceiling_functions floor(n/2)] minus one. The minimal number of [[Leaf Node|leaves]] is shown in following table which also demonstrates the [[Odd-Even Effect|odd-even effect]]:

{| class="wikitable"
|-
! colspan="3"| number of leaves with depth n and b = 40
|-
! depth
! worst case
! best case
|-
! style="text-align:center;" | '''n'''
! style="text-align:center;" | <span style="font-size: 120%;">b</span><span style="vertical-align: super;">n</span>
! style="text-align:center;" | <span style="font-size: 120%;">b</span><span style="vertical-align: super;">&#8968;n/2&#8969;</span> + b<span style="vertical-align: super;">&#8970;n/2&#8971;</span> - 1
|-
! 0
| style="text-align:right;" | 1
| style="text-align:right;" | 1
|-
! 1
| style="text-align:right;" | 40
| style="text-align:right;" | 40
|-
! 2
| style="text-align:right;" | 1,600
| style="text-align:right;" | 79
|-
! 3
| style="text-align:right;" | 64,000
| style="text-align:right;" | 1,639
|-
! 4
| style="text-align:right;" | 2,560,000
| style="text-align:right;" | 3,199
|-
! 5
| style="text-align:right;" | 102,400,000
| style="text-align:right;" | 65,569
|-
! 6
| style="text-align:right;" | 4,096,000,000
| style="text-align:right;" | 127,999
|-
! 7
| style="text-align:right;" | 163,840,000,000
| style="text-align:right;" | 2,623,999
|-
! 8
| style="text-align:right;" | 6,553,600,000,000
| style="text-align:right;" | 5,119,999
|}
<span id="HistoryAlphaBeta"></span>
=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 [[Timeline#1955|1955]] at the [https://en.wikipedia.org/wiki/Dartmouth_Conference Dartmouth Conference] <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]]
* [[Daniel Edwards]] and [[Timothy Hart]], Description in 1961 <ref>[[Daniel Edwards]] and [[Timothy Hart]] ('''1961'''). ''The Alpha-Beta Heuristic'', AIM-030, reprint available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]. Retrieved on 2006-12-21.</ref>
* [[Alexander Brudno]], Description in [[Timeline#1963|1963]]
* [[Samuel Fuller]], [[John Gaschnig]], [[James Gillogly]], Analysis 1973 <ref>[[Samuel Fuller]], [[John Gaschnig]], [[James Gillogly]] ('''1973'''). ''An Analysis of the Alpha-Beta Pruning Algorithm.'' Technical Report, [[Carnegie Mellon University]]</ref>
* [[Donald Knuth]], Analysis in [[Timeline#1975|1975]]
: [http://chessprogramming.wikispaces.com/space/showimage/knuth-alpha-beta.JPG Knuth and Moore's famous Function F2, aka AlphaBeta]
: [http://chessprogramming.wikispaces.com/file/detail/knuth-iterative.JPG Knuth already introduced an iterative solution], see [[Iterative Search]]
: [[Node Types|Knuth's node types]]
* [[Gérard M. Baudet]], Analysis in 1978

=Quotes=
==McCarthy==
{{Quote McCarthy on Alpha-Beta}}
==Ershov and Shura-Bura==
{{Quote Shura-Bura}}
==Knuth==
Quote by [[Donald Knuth|Knuth]] <ref>[[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3</ref> :
It is interesting to convert this [[Recursion|recursive]] procedure to an iterative (non-recursive) form by a sequence of mechanical transformations, and to apply simple optimizations which preserve program correctness. The resulting procedure is surprisingly simple, but not as easy to prove correct as the recursive form.

=Implementation=
<span id="MaxversusMin"></span>
==Max versus Min==
A C-like pseudo code implementation of the alpha-beta algorithm with distinct indirect [[Recursion|recursive]] routines for the max- and min-player, similar to the [[Minimax|minimax]] routines. [[Make Move|Making]] and [[Unmake Move|unmaking]] [[Moves|moves]] is omitted, and should be done before and after the recursive calls. So called [[Beta-Cutoff|beta-cutoffs]] occur for the max-play, alpha-cutoffs for the min-player.
<pre>
int alphaBetaMax( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMin( alpha, beta, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}

int alphaBetaMin( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return -evaluate();
for ( all moves) {
score = alphaBetaMax( alpha, beta, depthleft - 1 );
if( score <= alpha )
return alpha; // fail hard alpha-cutoff
if( score < beta )
beta = score; // beta acts like min in MiniMax
}
return beta;
}
</pre>
With this call from the [[Root]]:
<pre>
score = alphaBetaMax(-oo, +oo, depth);
</pre>

[[FILE:alphabeta.gif|none|border|text-bottom|link=http://cgm.cs.mcgill.ca/~hagha/topic11/topic11.html]]
Alpha-beta search tree with two alpha-cuts at min nodes <ref>[[McGill University]], Winter 1997 Class Notes, [http://cgm.cs.mcgill.ca/~hagha/topic11/topic11.html Topic #11: Game trees. Alpha-beta search], Diagram by Pui Yee Chan</ref>

<span id="Negamax"></span>
==Negamax Framework==
Inside a [[Negamax|negamax]] framework the routine looks simpler, but is not necessarily simpler to understand. Despite negating the returned score of the direct recursion, alpha of the min-player becomes minus beta of the max-player and vice versa, and the term alpha-cutoff or alpha-pruning is somehow diminished.
<pre>
int alphaBeta( int alpha, int beta, int depthleft ) {
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
</pre>
'''Note #1''': Notice the call to quiesce(). This performs a [[Quiescence Search|quiescence search]], which makes the alpha-beta search much more stable.

'''Note #2''': This function only returns the score for the position, not the [[Best Move|best move]]. Normally, a different (but very similar) function is used for searching the [[Root|root node]]. The SearchRoot function calls the alphaBeta function and returns both a score and a best move. Also, most search functions collect the [[principal variation]] not only for display purposes, but for a good guess as the leftmost path of the next iteration inside an [[Iterative Deepening|iterative deepening]] framework.

==Fail hard==
Since alpha and beta act as hard [[Bound|bounds]] of the return value if depth left is greater zero in the above code samples, this is referred to a [[Fail-Hard|fail-hard]]-framework.

==Outside the Bounds==
[[Fail-Soft]] Alpha-Beta <ref>[[John Philip Fishburn]] ('''1983'''). ''[http://portal.acm.org/citation.cfm?id=1056623.1056628&coll=DL&dl=GUIDE&CFID=26266656&CFTOKEN=86225814 Another optimization of alpha-beta search]''. [[ACM#SIG|SIGART Bulletin]], Issue 84</ref> may return scores outside the [[Bound|bounds]], that is either greater than beta or less than alpha. It has to keep track of the best score, which might be below alpha.
<pre>
int alphaBeta( int alpha, int beta, int depthleft ) {
int bestscore = -oo;
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
if( score >= beta )
return score; // fail-soft beta-cutoff
if( score > bestscore ) {
bestscore = score;
if( score > alpha )
alpha = score;
}
}
return bestscore;
}
</pre>

=Enhancements=
The alpha-beta algorithm can also be improved. These enhancements come from the fact that if you restrict the [[Window|window]] of [[Score|scores]] that are interesting, you can achieve more cutoffs. Since [[Move Ordering|move ordering]] is so much important, a technique applied outside of the search for this is [[Iterative Deepening|iterative deepening]] boosted by a [[Transposition Table|transposition table]], and possibly [[Aspiration Windows|aspiration windows]]. Other enhancements, applied within the search function, are further discussed.

==Obligatory==
* [[Transposition Table]]
* [[Iterative Deepening]]
* [[Aspiration Windows]]

==Selectivity==
* [[Quiescence Search]]
* [[Selectivity]]

==Scout and Friends==
* [[Scout]]
* [[NegaScout]]
* [[Principal Variation Search]]

=Alpha-Beta goes Best-First=
* [[Alpha-Beta Conspiracy Search]]
* [[MTD(f)]]
* [[NegaC*]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|SSS* and Dual* as MT]]

=See also=
* [[Alpha]]
* [[Beta]]
* [[Beta-Cutoff]]
* [[Bound]]
* [[CPW-Engine_search]]
* [[Fail-Low]]
* [[Fail-High]]
* [[Ostrich#GammaAlgorithm|Gamma-Algorithm]]
* [[Iterative Search]]
* [[KC Chess]]
* [[MCαβ]]
* [[Minimax]]
* [[Negamax]]
* [[Node Types]]
* [[Odd-Even Effect]]
* [[Parallel Search#ParallelAlphaBeta|Parallel Alpha-Beta]]
: [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta in Cilk]]
* [[Search Explosion]]
* [[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=
==1958 ..==
* [[Allen Newell]], [[Cliff Shaw]], [[Herbert Simon]] ('''1958'''). ''Chess Playing Programs and the Problem of Complexity''. IBM Journal of Research and Development, Vol. 4, No. 2, pp. 320-335. Reprinted (1963) in [http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=6685 Computers and Thought] (eds. [[Edward Feigenbaum|Edward A. Feigenbaum]] and [[Mathematician#JulianFeldman|Julian Feldman]]), pp. 39-70. McGraw-Hill, New York, N.Y., [http://www.research.ibm.com/journal/rd/024/ibmrd0204I.pdf pdf]
* [[Arthur Samuel]] ('''1959'''). ''[http://domino.watson.ibm.com/tchjr/journalindex.nsf/600cc5649e2871db852568150060213c/39a870213169f45685256bfa00683d74%21OpenDocument Some Studies in Machine Learning Using the Game of Checkers]''. IBM Journal July 1959
==1960 ...==
* [[Daniel Edwards]], [[Timothy Hart]] ('''1961'''). ''The Alpha-Beta Heuristic'', AIM-030, reprint available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]. Retrieved on 2006-12-21.
* [[Alexander Brudno]] ('''1963'''). ''Bounds and valuations for shortening the search of estimates''. Problemy Kibernetiki (10) 141–150 and Problems of Cybernetics (10) 225–241
* [[James R. Slagle]] ('''1963'''). ''Game Trees, M & N Minimaxing, and the M & N alpha-beta procedure.'' Artificial Intelligence Group Report 3, UCRL-4671, University of California
* [[James R. Slagle]], [[John K. Dixon]] ('''1969'''). ''Experiments With Some Programs That Search Game Trees''. [[ACM#Journal|Journal of the ACM]], Vol. 16, No. 2: 189-207, [http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf pdf]
==1970 ...==
* [[Samuel Fuller]], [[John Gaschnig]], [[James Gillogly]] ('''1973'''). ''An Analysis of the Alpha-Beta Pruning Algorithm.'' Technical Report, [[Carnegie Mellon University]], [http://shelf2.library.cmu.edu/Tech/17700646.pdf pdf]
* [[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''An Analysis of Alpha-Beta Pruning''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3, [http://www-public.it-sudparis.eu/~gibson/Teaching/CSC4504/ReadingMaterial/KnuthMoore75.pdf pdf]
* [[Arnold K. Griffith]] ('''1976'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5009198 Empirical Exploration of the Performance of the Alpha-Beta Tree-Searching Heuristic]''. [[IEEE#TOC|IEEE Transactions on Computers]], Vol. C-25, No. 1
* [[Gérard M. Baudet]] ('''1978'''). ''An Analysis of the Full Alpha-Beta Pruning Algorithm''. STOC 1978: 296-313
* [[Gérard M. Baudet]] ('''1978'''). ''On the branching factor of the alpha-beta pruning algorithm''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 10
* [[Patrick Winston]] ('''1978'''). ''Dealing with Adversaries''. [[Personal Computing#2_11|Personal Computing, Vol. 2, No. 11]], pp. 30, November 1978 » [[Alpha-Beta]]
* [[Gary Lindstrom]] ('''1979'''). ''Alpha-Beta Pruning on Evolving Game Trees''. Technical Report UUCCS 79-101, [https://en.wikipedia.org/wiki/University_of_Utah University of Utah], [http://content.lib.utah.edu/cdm/ref/collection/uspace/id/498 UScholar Works]
* [[Ward Douglas Maurer]] ('''1979'''). ''[https://archive.org/stream/byte-magazine-1979-11/1979_11_BYTE_04-11_Fun_and_Games#page/n85/mode/2up Alpha-Beta Pruning]''. [[Byte Magazine#BYTE411|BYTE, Vol. 4, No. 11]], pp. 84-96
==1980 ...==
* [[David Levy]] ('''1980'''). ''[http://archive.org/stream/creativecomputing-1980-04/Creative_Computing_v06_n04_1980_Apr#page/n117/mode/2up Intelligent Games]''. [[Creative Computing]], Vol. 6, No. 4, hosted by the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]
* [[Judea Pearl]] ('''1981'''). ''Heuristic search theory: A survey of recent results''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai81.html IJCAI-81], [http://ijcai.org/Past%20Proceedings/IJCAI-81-VOL%201/PDF/100.pdf pdf]
* [[Igor Roizen]] ('''1981'''). ''On the Average Number of Terminal Nodes examined by Alpha-Beta''. Technical Report UCLA-ENG-CSL-8108, [https://en.wikipedia.org/wiki/University_of_California,_Los_Angeles University of California at Los Angeles], Cognitive Systems Laboratory
* [[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
* [[Peter W. Frey]] ('''1983'''). ''The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning''. Computer Game-Playing (ed. [[Max Bramer]]), pp. 285-289. Ellis Horwood Limited
* [[John Philip Fishburn]] ('''1983'''). ''[http://portal.acm.org/citation.cfm?id=1056623.1056628&coll=DL&dl=GUIDE&CFID=26266656&CFTOKEN=86225814 Another optimization of alpha-beta search]''. [[ACM#SIG|SIGART Bulletin]], Issue 84, [https://drive.google.com/file/d/0B2pvWWlf39g-cjJpZkc1cDhfbkk/view pdf] » [[Fail-Soft]]
* [https://en.wikipedia.org/wiki/John_Hughes_%28computer_scientist%29 John Hughes] ('''1984'''). ''Why Functional Programming Matters''. 5 An Example from Artificial Intelligence, [https://en.wikipedia.org/wiki/Chalmers_University_of_Technology Chalmers Tekniska Högskola], [https://en.wikipedia.org/wiki/Gothenburg Göteborg], [http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf pdf],
* [[Stephen F. Wheeler]] ('''1985'''). ''[https://www.researchgate.net/publication/34381496_A_performance_benchmark_of_the_alpha-beta_procedure_on_randomly_ordered_non-uniform_depth-first_game-trees_generated_by_a_chess_program A performance benchmark of the alpha-beta procedure on randomly ordered non-uniform depth-first game-trees generated by a chess program]''. M.Sc. thesis, [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce East Texas State University]
* [[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
==1990 ...==
* [[Ingo Althöfer]], [[Bernhard Balkenhol]] ('''1992'''). ''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]
* [[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 ...==
* [[Matthew L. Ginsberg]], [[Alan Jaffray]] ('''2002'''). ''Alpha-Beta Pruning Under Partial Orders''. in [[Richard J. Nowakowski]] (ed.) ''[http://library.msri.org/books/Book42/ More Games of No Chance]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], [http://library.msri.org/books/Book42/files/ginsberg.pdf pdf]
* [[Todd W. Neller]] ('''2002'''). ''[http://cupola.gettysburg.edu/csfac/11/ Information-Based Alpha-Beta Search and the Homicidal Chauffeur]''. [http://dblp.uni-trier.de/db/conf/hybrid/hscc2002.html#Neller02 HSCC 2002], in [http://people.eecs.berkeley.edu/~tomlin/ Claire J. Tomlin], [https://www.cs.ubc.ca/~mrg/ Mark R. Greenstreet] (eds.) ('''2002'''). ''[http://link.springer.com/book/10.1007/3-540-45873-5 Hybrid Systems: Computation and Control]''. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science] 2289, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer] <ref>[https://en.wikipedia.org/wiki/Homicidal_chauffeur_problem Homicidal chauffeur problem - Wikipedia]</ref>
* [[Jacek Mańdziuk]], [[Daniel Osman]] ('''2004'''). ''Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function''. [[ICGA Journal#27_1|ICGA Journal, Vol. 27, No. 1]], [http://www.mini.pw.edu.pl/~mandziuk/PRACE/ICGA.pdf pdf]
* [[Hendrik Baier]] ('''2006'''). ''Der Alpha-Beta-Algorithmus und Erweiterungen bei Vier Gewinnt''. Bachelor's thesis (German), [[Darmstadt University of Technology|TU Darmstadt]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2006/Baier_Hendrik.pdf pdf]
==2010 ...==
* [[Damjan Strnad]], [[Nikola Guid]] ('''2011'''). ''[http://cit.fer.hr/index.php/CIT/article/view/2029 Parallel Alpha-Beta Algorithm on the GPU]''. [http://cit.fer.hr/index.php/CIT CIT. Journal of Computing and Information Technology], Vol. 19, No. 4 » [[GPU]], [[Parallel Search]], [[Othello|Reversi]]
* [[Abdallah Saffidine]], [[Hilmar Finnsson]], [[Michael Buro]] ('''2012'''). ''Alpha-Beta Pruning for Games with Simultaneous Moves''. [[AAAI|AAAI 2012]]
* [[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 » [[LCZero]]</ref>
* [[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]]

=Forum Posts=
==1993 ...==
* [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/IQO0MduTUjQJ computer chess] by Paul W Celmer, [[Computer Chess Forums|rgc]], September 10, 1993
: [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/CjVUkx-hSQIJ Re: Computer Chess (LONG)] by [[Andy Walker]], [[Computer Chess Forums|rgc]], September 16, 1993
: [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/JLZH-MwDbQoJ Computer Chess and alpha-beta pruning] by Rickard Westman, [[Computer Chess Forums|rgc]], September 21, 1993
: [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/gsXMq42a-FAJ Re: Computer Chess and alpha-beta pruning] by [[Johannes Fürnkranz]], [[Computer Chess Forums|rgc]], September 22, 1993 » [[Iterative Deepening]]
: [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/MiYEhpjTT08J alpha-beta pruning != brute force] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], September 22, 1993 » [[Brute-Force]]
: [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/YqxBGHAlO7AJ Re: Computer Chess and alpha-beta pruning] by [[Robert Hyatt]], [[Computer Chess Forums|rgc]], September 25, 1993
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/b5f847cde3d26fd6 Alpha-beta inconsistencies] by [[Chua Kong Sian]], [[Computer Chess Forums|rgc]], February 19, 1994
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/TSAzRyajwsg/G6Ts2VFXhJcJ Alpha-Beta explained?] by Brian, [[Computer Chess Forums|rgcc]], October 15, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a895e1a5524f8158 New improvement to alpha/beta + TT?] by [[Heiner Marxen]], [[Computer Chess Forums|rgcc]], January 13, 1997 » [[Fail-Soft]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/f81d85c5fa058958 Re: Argument against Alpha-Beta searching] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], March 19, 1997
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/99eec6923b0481db computer chess "oracle" ideas...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 1, 1997 » [[Oracle]]
: [http://groups.google.com/group/rec.games.chess.computer/msg/0df39371422a600c Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 3, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/ccc2546e26d92f88 Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997
* [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=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=102792 A Question on simple Alpha-Beta versus PVS/Negascout] by [[Andrei Fortuna]], [[CCC]], March 21, 2000 » [[Principal Variation Search]], [[NegaScout]]
* [https://www.stmintz.com/ccc/index.php?id=110353 outline for alpha beta] by John Coffey, [[CCC]], May 12, 2000
* [https://www.stmintz.com/ccc/index.php?id=131537 Alpha-Beta explanation on Heinz's book?] by [[Severi Salminen]], [[CCC]], October 05, 2000 <ref>[[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</ref>
* [https://www.stmintz.com/ccc/index.php?id=162573 Who invented the Alpha-Beta-algorithm?] by [[Rafael B. Andrist]], [[CCC]], April 09, 2001
* [https://www.stmintz.com/ccc/index.php?id=183650 The Alpha-Beta search!] by [[Sune Fischer]], [[CCC]], August 14, 2001
* [https://www.stmintz.com/ccc/index.php?id=281522 An Idiot's Guide to Minimax, Alpha/Beta, etc...] by Mike Carter, [[CCC]], February 03, 2003
* [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 Search]]
* [https://www.stmintz.com/ccc/index.php?id=347303 Question for Hyatt about Alpha/Beta] by Bob Durrett, [[CCC]], February 05, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=478627 Iterative alpha-beta search?] by [[Andrew Wagner]], [[CCC]], January 11, 2006 » [[Iterative Search]]
* [https://www.stmintz.com/ccc/index.php?id=487561 Trivial alfa-beta question] by [[Jouni Uski]], [[CCC]], February 18, 2006
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=51491 Dumb question about alpha-beta] by [[Daylen Yang]], [[CCC]], March 04, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55474 Search algorithm in it's simplest forum] by [[Mahmoud Uthman]], [[CCC]], February 25, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55577 Negative alpha/beta windows: Are they useful?] by [[Thomas Dybdahl Ahle]], [[CCC]], March 06, 2015
* [http://www.open-chess.org/viewtopic.php?f=5&t=2931 Stuck on Alphabeta] by kuket15, [[Computer Chess Forums|OpenChess Forum]], December 07, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58923 Alpha-Beta woes, textbook-like resources, etc.] by [[Meni Rosenfeld]], [[CCC]], January 14, 2016
* [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]]

=External Links=
* [https://en.wikipedia.org/wiki/Alpha-beta_pruning Alpha-beta Pruning from Wikipedia]
* [https://en.wikipedia.org/wiki/Branch_and_bound Branch-and-bound from Wikipedia]
* [https://en.wikipedia.org/wiki/Integer_programming Integer programming from Wikipedia] <ref>[http://www2.isye.gatech.edu/~wcook/ William Cook] ('''2009'''). ''Fifty-Plus Years of Combinatorial Integer Programming''. [http://www2.isye.gatech.edu/~wcook/papers/ip50.pdf pdf]</ref>
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p004.htm#index01 The alpha-beta heuristic] from [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
* [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]]
* [http://www.top-5000.nl/authors/rebel/chess840.htm#SEARCH Alpha-Beta] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]]
* [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]
* [http://www.computerhistory.org/chess/main.php?sec=thm-42b86c2029762&sel=thm-42b86c6ab9811 The Minimax Algorithm and Alpha-Beta Pruning] from [[The Computer History Museum]]
* [http://www.emunix.emich.edu/%7Eevett/AI/AlphaBeta_movie/sld001.htm Alpha-Beta Slide Show in 18 steps] by [http://staff.scmb.uq.edu.au/staff/mikael-boden Mikael Bodén]
* [http://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#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]]'''

Navigation menu