Two Search Techniques for Imperfect Information Games and Application to Hearts
Theodore J. Perkins · 1998
Two techniques for game-tree search in imperfect information games with an arbitrary number of players are described: II-Max_n and MC-Max_n. They use probability computations and Monte Carlo-style sampling to overcome imperfect information problems. We then discuss implementations of both algorithms for the card game Hearts. We describe and empirically evaluate methods for estimating probabilities relevant to card games, and report on the performance of the search procedures. We also compare the Hearts-playing ability of the programs against each other and against a rule based Hearts player.