|
|
|
My Pages at FUN |
|---|
|
|
|
Projects |
|
Optimal Play Against Best Defence: Complexity and Heuristics Ian Frank, David Basin Presented at the First International Conference on Computers and Games, Tsukuba, Japan, 1998. Proceedings published by Springer-Verlag as Volume 1558 in the Lecture Notes in Computer Science Series. The new Springer copyright agreement allows authors (but only authors) to make their papers available in electronic form. The exclusive copyright for this paper is held by Springer.
© Springer-Verlag
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 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. |
