Alpha-Beta Pruning Algorithm

From GM-RKB
Jump to navigation Jump to search

An Alpha-Beta Pruning Algorithm is a tree search algorithm that reduces the computation time of a minimax search algorithm by decreasing the number of branches in the game tree that need to be evaluted.



References

2021a

  • (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Alpha–beta_pruning Retrieved:2021-12-15.
    • Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.[1]
  1. Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (3rd ed.). Upper Saddle River, New Jersey: Pearson Education, Inc. p. 167. ISBN 978-0-13-604259-4.

2021b

  1. 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.

2021c

1959