Optimal Play against Best Defence: Complexity and Heuristics

We investigate the best defence model of an imperfect information game. In particular, we prove that finding optimal strategies for this model is NP-complete in the size of the game tree. We then introduce 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