Technical Report CIS9703

TR#:CIS9703
Class:CIS
Title: Pruning Algorithms for Multi-model Adversary Search
Authors: David Carmel and Shaul Markovitch
PDFCIS9703.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.
CopyrightThe 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

Computer science department, Technion
admin