Loading...
Please wait, while we are loading the content...
Analysis of the alpha-beta pruning algorithm
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fuller, Samuel H. Gaschnig, John Gillogly, James J. |
| Copyright Year | 1973 |
| Abstract | Abstract : Many game-playing programs must search very large game trees. Use of the alpha-beta pruning algorithm instead of the simple minimax search reduces by a large factor the number of bottom positions which must be examined in the search. An analytical expression for the expected number of bottom positions examined in a game tree using alpha-beta pruning is derived, subject to the assumptions that the branching factor N and the depth D of the tree are arbitrary but fixed, and the bottom positions are a random permutation of (N sub D) unique values. A simple approximation to the growth rate of the expected number of bottom positions examined is suggested, based on a Monte Carlo simulation for large values of N and D. The behavior of the model is compared with the behavior of the alpha-beta algorithm in a chess playing program and the effects of correlation and non-unique bottom position values in real game trees are examined. (Author) |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www-public.imtbs-tsp.eu/~gibson/Teaching/CSC4504/ReadingMaterial/FullerGaschnigGillogly73.pdf |
| Alternate Webpage(s) | http://www-public.int-evry.fr/~gibson/Teaching/CSC4504/ReadingMaterial/FullerGaschnigGillogly73.pdf |
| Alternate Webpage(s) | http://repository.cmu.edu/cgi/viewcontent.cgi?article=2700&context=compsci |
| Alternate Webpage(s) | http://www-public.tem-tsp.eu/~gibson/Teaching/CSC4504/ReadingMaterial/FullerGaschnigGillogly73.pdf |
| Alternate Webpage(s) | http://shelf2.library.cmu.edu/Tech/17700646.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
