General Game Playing with Imperfect Information

Abstract

General Game Playing is a field which allows the researcher to investigate techniques that might eventually be used in an agent capable of Artificial General Intelligence.  Game playing presents a controlled environment in which to evaluate AI techniques, and so we have seen an increase in interest in this field of research.  Games of imperfect information offer the researcher an additional challenge in terms of complexity over games with perfect information.  In this article, we look at imperfect-information games: their expression, their complexity, and the additional demands of their players.  We consider the problems of working with imperfect information and introduce a technique called HyperPlay, for efficiently sampling very large information sets, and present a formalism together with pseudo code so that others may implement it. We examine the design choices for the technique, show its soundness and completeness then provide some experimental results and demonstrate the use of the technique in a variety of imperfect-information games, revealing its strengths, weaknesses, and its efficiency against randomly generating samples.  Improving the technique, we present HyperPlay-II, capable of correctly valuing information-gathering moves.  Again, we provide some experimental results and demonstrate the use of the new technique revealing its strengths, weaknesses and its limitations.