| TR#: | CIS9703 |
| Class: | CIS |
| Title: | Pruning Algorithms for Multi-model Adversary Search |
| Authors: | David Carmel and Shaul Markovitch |
| CIS9703.pdf | |
| Abstract: | The Multi-model search framework generalizes minimax to allow exploitation of recursive opponent models. In this work we consider adding pruning to multi-model search. We prove a sufficient condition that enables pruning and describe two pruning algorithms, Alpha-Beta* and Alpha-Beta*-1p. We prove correctness and optimality of the algorithms and provide experimental study of their pruning power. We show that for opponent models that are not radically different than the player's strategy, the pruning power of these algorithms is significant. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CIS/CIS9703), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CIS technical reports of 1997
To the main CS technical reports page