@Article{	  frank.ea:theoretical:2001,
  abstract	= {We examine search algorithms for games with imperfect
		  information.We first investigate Monte Carlo sampling,
		  showing that for verysimple game trees the chance of
		  finding an optimal strategy rapidlyapproaches zero as size
		  of the tree increases. We identify thereasons for this
		  sub-optimality, and show that the same problemsoccur in
		  Bridge, a popular real-world imperfect information game.We
		  then analyse the complexity of the underlying problem,
		  proving itto be NP-complete and describing several
		  polynomial time heuristics.We evaluate these heuristics
		  theoretically and experimentally,demonstrating that they
		  significantly out-perform Monte Carlosampling. Indeed, on a
		  set of Bridge problems drawn from adefinitive expert text,
		  our heuristics consistently identifystrategies as good as,
		  or superior to, the expert solutions - thefirst time a
		  game-general tree search algorithm has been capable ofsuch
		  performance.},
  author	= {Ian Frank and David Basin},
  journal	= {Theoretical Computer Science},
  month		= {February},
  language	= {USenglish},
  number	= {1-2},
  pages		= {217--256},
  ps		= {papers/2001/tcs-search.ps.gz},
  title		= {A Theoretical and Empirical Investigation of Search in
		  Imperfect Information Games},
  volume	= 252,
  year		= 2001
}