Game theory and AI:
A Unified Approach to Poker Games

Abstract

This thesis focuses on decision making in partially observable card games and, in particular, poker games. An attempt is made to outline both the game theoretic, as an agent-centric approach to such games, analyzing differences and similarities, as well as strong and weaker points and finally proposing a view to make a tradeoff between these.

The game theoretic approach for this type of games would specify a Nash-equilibrium, i.e., a pair of policies that are a best response to each other. Although a policy found in this way guarantees a minimum payoff, it is conservative in the sense that it is unable to exploit any weaknesses the opponent might have.

This motivates an agent-centric perspective, in which we propose modeling a simple poker game as a Partial Observable Markov Decision Process (POMDP) for a player who is playing against a fixed opponent whose policy is known (e.g. by repeated play). The resulting deterministic policy is a best response against the fixed opponent policy. Such a best-response policy does exploit weaknesses in the opponent's policy, thus yielding the maximum payoff attainable.

In order for the results obtained for such a simplified poker game to be of significance for real-life poker games, various methods for dealing with large (PO)MDPs are treated. These could be used to tackle larger games using the best-response approach. We examine the application of one of these methods, model minimization, on poker games in more detail. The result of this examination is that the reduction gained by direct application of model minimization on poker games is bounded and that this bound prevents this method from successfully tackling real-life poker variants.

Finally, in a coevolutionary framework, we try to unify the game theoretic and agent-centric approach by making a tradeoff between the security the former offers and the potential gain of the latter. A secondary goal in this approach is examining efficient calculation of Nash-equilibria.

Download full text

.ps.gz - smaller (1MB) and recommended for printing.
.pdf - larger (2.5MB)

For the original project original decription, see here.

Supervisor: Nikos Vlassis