Division of Informatics
Forrest Hill & 80 South Bridge

Research Paper #780
Title:	Search in Games with Incomplete Information: a Case Study Using Bridge Card Play
Authors:	Frank,I; Basin,D
Date:	Jan 1996
Presented:	Submitted to Artificial Intelligence
Keywords:
Abstract:	We examine search algorithms in games with incomplete information. We proceed by adopting the standard game theoretic framework of zero-sum two player games, introducing a reduced form of incomplete information games in which equilibrium point strategies can be identified, and giving an algorithm that finds such strategies. We apply our formalisation to the game of Bridge, for which the reduced form corresponds to the typical model analysed in expert texts. In particular, we examine search algorithms for Bridge that have been proposed by other researchers, countering the optimistic suggestion that the incomplete information in the game can be tackled by an algorithm which considers some statistically significant subset of the possible worlds (card distributions). We use our model to pinpoint why, both in theory and practice, such approaches must lead to suboptimal performance and we generalise the reasons for this failure into two specific and distinct problems. We illustrate these problems and our solution with simple game trees and with actual play situations from Bridge itself.
Download:	POSTSCRIPT COPY

Division of InformaticsForrest Hill & 80 South Bridge