Abstract:

Optimal Play Against Best Defence: Complexity and Heuristics

Ian Frank and David Basin



We investigate the best defence model of an imperfect infor- mation game. In particular, we prove that finding 
optimal strategies for this model is NP-complete in the size of the game tree. We then intro- duce two new 
heuristics for this problem and show that they out-perform previous algorithms. We demonstrate the practical 
use and effectiveness of these heuristics by testing them on random game trees and on a hard set of problems 
from the game of Bridge. For the Bridge problem set, our heuristics actually out-perform the human experts 
that produced the model solutions.