Difference between revisions of "Alpha-Beta"

From Chessprogramming wiki
Jump to: navigation, search
 
(9 intermediate revisions by the same user not shown)
Line 60: Line 60:
 
=History=  
 
=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
 
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>
+
* [[John McCarthy]] proposed the idea of Alpha-Beta after the representation of the [[The Bernstein Chess Program|Chess 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_workshop Dartmouth Workshop] 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]], [[Nathaniel Rochester]], [[Claude Shannon]], August 31, '''1955'''</ref>  
 
* [[Allen Newell]] and [[Herbert Simon]] Approximation in [[Timeline#1958|1958]]
 
* [[Allen Newell]] and [[Herbert Simon]] Approximation in [[Timeline#1958|1958]]
 
* [[Arthur Samuel]] Approximation in [[Timeline#1959|1959]]
 
* [[Arthur Samuel]] Approximation in [[Timeline#1959|1959]]
Line 186: Line 186:
 
=See also=  
 
=See also=  
 
* [[Alpha]]
 
* [[Alpha]]
 +
* [[Stephen F. Wheeler#Alpha-Beta Benchmark|Alpha-Beta Benchmark]] by [[Stephen F. Wheeler]]
 
* [[Beta]]
 
* [[Beta]]
 
* [[Beta-Cutoff]]
 
* [[Beta-Cutoff]]
Line 256: Line 257:
 
* [[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]
 
* [[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]]
 
* [[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=  
 
=Forum Posts=  
Line 275: Line 277:
 
* [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=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=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
+
: [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 ...==
 
==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=98141 Another Alpha-Beta algorithm question] by Jeff Anderson, [[CCC]], February 18, 2000
Line 300: Line 303:
 
* [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=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]]
 
* [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=  
 
=External Links=  
 
* [https://en.wikipedia.org/wiki/Alpha-beta_pruning Alpha-beta Pruning from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Alpha-beta_pruning Alpha-beta Pruning from Wikipedia]
Line 308: Line 315:
 
* [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://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://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://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])
* [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]]
+
* [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])
* [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]
+
* [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]] Computer Chess Sites ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
* [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]]
+
* [https://emunix.emich.edu/~mevett/AI/AlphaBeta_movie/sld001.htm Alpha-Beta Slide Show in 18 steps] by [https://scmb.uq.edu.au/profile/321/mikael-boden Mikael Bodén]
* [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://hamedahmadi.com/gametree/ An Introduction to Game Tree Algorithms] by [[Hamed Ahmadi]]
* [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
+
* [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]
 
: 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}}
 
: {{#evu:https://www.youtube.com/watch?v=qhmwTc_MNjM|alignment=left|valignment=top}}
Line 320: Line 327:
 
<references />
 
<references />
 
'''[[Search|Up one level]]'''
 
'''[[Search|Up one level]]'''
 +
[[Category:Quotes]]
 +
[[Category:McCarthy Quotes]]
 
[[Category:Vangelis]]
 
[[Category:Vangelis]]

Latest revision as of 15:20, 1 December 2021

Home * Search * Alpha-Beta

Alpha Beta [1]

The Alpha-Beta algorithm (Alpha-Beta Pruning, Alpha-Beta Heuristic [2] ) is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of the game tree applying a branch-and-bound technique. Remarkably, it does this without any potential of overlooking a better move. If one already has found a quite good move and search for alternatives, one refutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and 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 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. 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 of 3 or greater, because now both players can make choices affecting the game tree. Now we have to maintain both a lower bound and an 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 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 is very important, and is the focus of a lot of the effort of writing a good chess program. As pointed out by 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 ^ ceil(n/2) plus b ^ floor(n/2) minus one. The minimal number of leaves is shown in following table which also demonstrates the odd-even effect:

number of leaves with depth n and b = 40
depth n bn b⌈n/2⌉ + b⌊n/2⌋ - 1
0 1 1
1 40 40
2 1,600 79
3 64,000 1,639
4 2,560,000 3,199
5 102,400,000 65,569
6 4,096,000,000 127,999
7 163,840,000,000 2,623,999
8 6,553,600,000,000 5,119,999

History

Alpha-Beta was invented independently by several researchers and pioneers from the 50s [3], and further research until the 80s, most notable by

Knuth and Moore‘s famous Function F2, aka AlphaBeta
Knuth already introduced an iterative solution, see Iterative Search
Knuth's node types

Quotes

McCarthy

Quote by John McCarthy from Human-Level AI is harder than it seemed in 1955 on the Dartmouth workshop:

Chess programs catch some of the human chess playing abilities but rely on the limited effective branching of the chess move tree. The ideas that work for chess are inadequate for go. Alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers - Turing, Shannon, Pasta and Ulam, and Bernstein. We humans are not very good at identifying the heuristics we ourselves use. Approximations to alpha-beta used by Samuel, Newell and Simon, McCarthy. Proved equivalent to minimax by Hart and Levin, independently by Brudno. Knuth gives details.

Ershov and Shura-Bura

Quote from The Early Development of Programming in the USSR by Andrey Ershov and Mikhail R. Shura-Bura [8]

At the end of the 1950's a group of Moscow mathematicians began a study of computerized chess. Sixteen years later, the studies would lead to victory in the first world chess tournament for computer programs held in Stockholm during the 1974 IFIP Congress. An important component of this success was a deep study of the problems of information organization in computer memory and of various search heuristics. G. M. Adelson-Velsky and E. M. Landis invented the binary search tree ("dichotomic inquiry") and A. L. Brudno, independent of J. McCarthy, discovered the (α,β)-heuristic for reducing search times on a game tree.

Knuth

Quote by Knuth [9] : It is interesting to convert this 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

Max versus Min

A C-like pseudo code implementation of the alpha-beta algorithm with distinct indirect recursive routines for the max- and min-player, similar to the minimax routines. Making and unmaking moves is omitted, and should be done before and after the recursive calls. So called beta-cutoffs occur for the max-play, alpha-cutoffs for the min-player.

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;
}

With this call from the Root:

   score = alphaBetaMax(-oo, +oo, depth);
Alphabeta.gif

Alpha-beta search tree with two alpha-cuts at min nodes [10]

Negamax Framework

Inside a 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.

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;
}

Note #1: Notice the call to quiesce(). This performs a 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. Normally, a different (but very similar) function is used for searching the 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 framework.

Fail hard

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

Outside the Bounds

Fail-Soft Alpha-Beta [11] may return scores outside the 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.

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;
}

Enhancements

The alpha-beta algorithm can also be improved. These enhancements come from the fact that if you restrict the window of scores that are interesting, you can achieve more cutoffs. Since move ordering is so much important, a technique applied outside of the search for this is iterative deepening boosted by a transposition table, and possibly aspiration windows. Other enhancements, applied within the search function, are further discussed.

Obligatory

Selectivity

Scout and Friends

Alpha-Beta goes Best-First

See also

Parallel Alpha-Beta in Cilk

Selected Publications

1958 ..

1960 ...

  • Daniel Edwards, Timothy Hart (1961). The Alpha-Beta Heuristic, AIM-030, reprint available from DSpace at 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. Journal of the ACM, Vol. 16, No. 2: 189-207, pdf

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1993 ...

Re: Computer Chess (LONG) by Andy Walker, rgc, September 16, 1993
Computer Chess and alpha-beta pruning by Rickard Westman, rgc, September 21, 1993
Re: Computer Chess and alpha-beta pruning by Johannes Fürnkranz, rgc, September 22, 1993 » Iterative Deepening
alpha-beta pruning != brute force by Feng-hsiung Hsu, rgc, September 22, 1993 » Brute-Force
Re: Computer Chess and alpha-beta pruning by Robert Hyatt, rgc, September 25, 1993

1995 ...

Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 3, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997
Re: alpha-beta is silly? by Don Dailey, CCC, June 03, 1998

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

External Links

Alpha Beta are Vilma Lado, Vangelis Papathanassiou, Argyris Koulouris and Giorgio Gomelski

References

  1. Alpha Beta - Astral Abuse a look at the music of Vangelis Papathanassiou
  2. Arthur Samuel (1967). Some Studies in Machine Learning. Using the Game of Checkers. II-Recent Progress. pdf, IBM Journal - November 1967, on the name Alpha-Beta Heuristic pp. 602: So named by 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 "branch and bound" technique which was been rediscovered many times and which is currently being exploited in integer programming research.
  3. Jaap van den Herik (2001). Science, Competition and Business. ICGA Journal, Vol. 24, No. 4, pdf
  4. The Dartmouth Workshop--as planned and as it happened
  5. A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence by John McCarthy, Marvin Minsky, Nathaniel Rochester, Claude Shannon, August 31, 1955
  6. Daniel Edwards and Timothy Hart (1961). The Alpha-Beta Heuristic, AIM-030, reprint available from DSpace at MIT. Retrieved on 2006-12-21.
  7. Samuel Fuller, John Gaschnig, James Gillogly (1973). An Analysis of the Alpha-Beta Pruning Algorithm. Technical Report, Carnegie Mellon University
  8. Andrey Ershov, Mikhail R. Shura-Bura (1980). The Early Development of Programming in the USSR. in Nicholas C. Metropolis (ed.) A History of Computing in the Twentieth Century. Academic Press, preprint pp. 44
  9. Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. Reprinted in Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102, ISBN 1-57586-212-3
  10. McGill University, Winter 1997 Class Notes, Topic #11: Game trees. Alpha-beta search, Diagram by Pui Yee Chan
  11. John Philip Fishburn (1983). Another optimization of alpha-beta search. SIGART Bulletin, Issue 84
  12. Homicidal chauffeur problem - Wikipedia
  13. Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » Leela Chess Zero
  14. Ernst A. Heinz (1999). Scalable Search in Computer Chess. Morgan Kaufmann, ISBN 3-528-05732-7
  15. kernel launch latency - CUDA / CUDA Programming and Performance - NVIDIA Developer Forums by LukeCuda, June 18, 2018
  16. William Cook (2009). Fifty-Plus Years of Combinatorial Integer Programming. pdf

Up one level