Representing large state spaces

Decision Tree Poker

In the previous part we showed that a partially observable card game can be transformed to a POMDP. The assumptions that were necessary are that the opponent is playing a fixed policy and that we know that fixed policy. In this setting we can exactly solve the POMDP, yielding a best-response policy. This approach overcomes one of the identified problems a Nash equilibrium policy exhibits being too conservative. The second problem remains. As mentioned, the POMDP representation described in...

A WA i

a Extensive form game. b POMDP model. Figure 3.2 Conversion from extensive form for 8-card poker left to a POMDP model for the gambler right . The decision nodes for the protagonist agent become states in the POMDP model. The deterministic choices of the opponent become stochastic transitions. The crucial assumption that lies at the foundation of this approach is that the policy of the opponent is fixed and known. For example, estimated from repeated play. Given this assumption we know...

Game theory

As the name implies, game theory is the traditional approach for analyzing games. It is usually divided in two parts cooperative and non-cooperative game theory. The cooperative game theory takes a looser approach and mostly deals with bargaining problems. The non-cooperative game theory is based on exact rules for games, so that solutions can be studied in detail. As the type of games discussed in this thesis are strictly competitive, we will focus on the non-cooperative part and leave the...

MDPs POMDPs

In the previous chapter we outlined the game theoretic approach for solving games like poker and argued that its solution concept, the Nash equilibrium is too conservative for these type of games. In this chapter we switch from the field of game theory to that of decision theoretic planning DTP and artificial intelligence. DTP studies the process of automated sequential decision making, in which the major problem is planning under uncertainty Planning what actions to take in an uncertain...

Bibliography

Michael Szafron

Master s thesis, University of Alberta, 1995. 2 Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Scha-effer, Terence Schauenberg, and Duane Szafron. Approximating game-theoretic optimal strategies for full-scale poker. In Proc. Int. Joint Conf. on Artificial Intelligence, Acapulco, Mexico, August 2003. 3 Darse Billings, Aaron Davidson, Jonathan Schaeffer, and Duane Szafron. The challenge of poker. Artif. Intell., 134 1-2 201-240, 2002. 4 Darse...