ISBN:  Unavailable

Category: Unavailable

Page count: 25

Abstract: "An information set in a game tree is a set of nodes from which the rules of the game require that the same alternative (i.e., move) be selected. Thus the nodes in an information set are indistinguishable to the player moving from that set, thereby reflecting imperfect information, that is, information hidden from that player. Information sets arise naturally in (for example) card games like poker. We show two related fundamental results for one-player games with imperfect information. First, we prove that in general solving such games is NP- hard. Second, we give an algorithm that computes a strategy for such games, in time linear in the size of the search tree. We prove that the strategy produced by this algorithm is an optimal strategy, if the game has a certain natural condition called perfect recall