All Title Author
Keywords Abstract

Algorithms  2012 

Alpha-Beta Pruning and Alth?fer’s Pathology-Free Negamax Algorithm

DOI: 10.3390/a5040521

Keywords: game tree, search pathology, alpha-beta pruning

Full-Text   Cite this paper   Add to My Lib


The minimax algorithm, also called the negamax algorithm, remains today the most widely used search technique for two-player perfect-information games. However, minimaxing has been shown to be susceptible to game tree pathology, a paradoxical situation in which the accuracy of the search can decrease as the height of the tree increases. Alth?fer’s alternative minimax algorithm has been proven to be invulnerable to pathology. However, it has not been clear whether alpha-beta pruning, a crucial component of practical game programs, could be applied in the context of Alh?fer’s algorithm. In this brief paper, we show how alpha-beta pruning can be adapted to Alth?fer’s algorithm.


comments powered by Disqus

Contact Us


微信:OALib Journal