Non-Minimax Search Strategies for Use Against Fallible Opponents

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 3

Search

Most previous research on the use of search for minimax game playing has focused on improving search efficiency rather than on better utilizing available information. In a previous paper we developed models of imperfect opponent play based on a notion we call playing strength. In this paper, we use the insights acquired in our study of imperfect play and ideas expressed in papers by Slagle and Dixon, Ballard, Nau, and Pearl to develop alternatives to the conventional minimax strategy. We demonstrate that, in particular situations, against both perfect and imperfect opponents, our strategy yields an improvement comparable to or exceeding that provided by an additional ply of search.