Non-Minimax Search Strategies for Use Against Fallible Opponents

Andrew L. Reibman, Bruce W. Ballard

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.