Premium
Empirical results with conspiracy numbers
Author(s) -
KLINGBEIL NORBERT,
SCHAEFFER JONATHAN
Publication year - 1990
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1990.tb00125.x
Subject(s) - minimax , root (linguistics) , value (mathematics) , computer science , mathematics , algorithm , artificial intelligence , statistics , machine learning , mathematical optimization , philosophy , linguistics
McAllester's conspiracy numbers algorithm is an exciting new approach to minimax search that builds trees to variable depth without application‐dependent knowledge. The likelihood of the root taking on a value is expressed by its conspiracy number: the minimum number of leaf nodes that must change their value to cause the root to change to that value. This paper describes experiences with the algorithm, using both random and application‐generated trees. Experiments suggest that more emphasis on breadth, rather than depth, can lead to significant performance improvements. New enhancements to the algorithm are capable of solving 41% more problems than McAllester's original proposal.