Lecture Notes in Computer Science, 1999, Volume 1558/1999, 50-73, DOI: 10.1007/3-540-48957-6_4

Optimal Play against Best Defence: Complexity and Heuristics

Ian Frank and David Basin

View Related Documents

Abstract

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 outperform 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 outperform the human experts who produced the model solutions.

Keywords  imperfect information - heuristics - complexity - Bridge

Fulltext Preview

Image of the first page of the fulltext document