next up previous
Next: Literature Survey Up: Introduction: Why Study Previous: Games with Perfect

Games with Imperfect Information

Beyond this lies the realm of games having imperfect information, where certain relevant details are withheld from the players, or where knowledge is not reliable. Computer science, like mathematics, is based on the processing of perfect information, which tends to separate it from the less well-defined problems that are commonplace in the real world. The study of games like poker and bridge could be highly valuable, since problems involving imperfect information are of fundamental importance to all areas of computer science. Indeed, the difficulties associated with handling incomplete or uncertain information are now receiving an increasing amount of attention in many other computer science research domains.

Surprisingly difficult problems can also arise in games with more than two players. In some cases, an allowable degree of cooperation between players can result in complicated issues of diplomacy, and other complex implications. These interesting questions are only beginning to be addressed [48]. Within the field of computer strategic game playing, it is becoming increasingly popular to investigate games which involve reasoning under conditions of uncertainty [43, 26, 12]. Most of this work has been done in relation to the game of Bridge, where there is imperfect information both in the bidding and in the play of the hand. While some interesting results have been obtained, the overall playing level of current Bridge programs is still very weak compared to human players [22, 56, 102, 57, 55, 44, 97, 26, 12, 83]. This may be due, at least in part, to the logistic complications involved with bidding, interpreting bids, and applying information from the auction to the play of the cards.

Technically, Scrabble is also a game of imperfect information, since each player does not know what tiles are held by another player. However, it appears this property does not have a significant degree of strategic importance, in practice. Other compensating strengths, such as having perfect memory of the complete official dictionary and the ability to search all legal moves, have resulted in programs which are on par with the best human players [84, 100].

The game of poker involves all of the above extensions to traditional studies in computer game playing, being a non-deterministic multi-player zero-sum game with imperfect information. Unlike Scrabble, the imperfect information cannot simply be ignored, since handling this aspect of the game is fundamental to competent play. As noted, poker has well-defined parameters (with much simpler logistics than Bridge), and a wealth of strategic complexity. This favourable combination of good properties suggests that research into poker could be quite fruitful. The potential benefits of studying small, precisely defined questions involving limited degrees of imperfect information are manifest.

Specific features of poker that are not prominent in other games include risk management, the necessity of bluffing, the implications of multiple opponents, discerning deception, and deducing the styles of other players in order to exploit their weaknesses.

Somewhat surprisingly, very little academic research has been done on the game of poker. This seems to be a serious oversight, especially for researchers in the field of computer game playing. This essay will survey the diverse resources that are available for such research, and make some well-informed recommendations on how these investigations might be performed.


next up previous
Next: Literature Survey Up: Introduction: Why Study Previous: Games with Perfect

& Schaeffer
Thu Feb 12 14:00:05 MST 1998