• View
• Edit
• History
• Print

Introduction

Texas hold'em poker has become an increasingly popular game over the last 10 years, and represents a significant challenge to tackle from a computational perspective. The minimax algorithms which successfully spawned nearly unbeatable chess players break down when applied to poker. In 2007 and 2008 two programs were created (building on the prior work of many other researchers) that attempt to tackle the game of limit heads-up texas hold'em.

About the AI programs

The strategy for Fell Omen 2 and INOT were generated in a similar manner. A Co-evolutionary process called fictitious play was used to create a near optimal solution to the game. Fictitious play is an iterative algorithm that works roughly as follows.

1. First we start with a naive strategy, such as raise call and fold with equal probability in all situations.
2. Then we examine our strategy, and see how its weaknesses can be exploited.
3. We then incorporate those exploitations into our play to create a new strategy.
4. 'b' and 'c' are repeated until there is no way to exploit the strategy

The result is that the strategies of INOT and Fell Omen 2 do not pop out of thin air, but are rather grown by a process of self examination. This may be similar to the way a human might learn a game. Like these bots a human starts off playing poorly, not really getting how good a given poker hand is, and how often to bluff. he/she then examines the way their strategy is exploited, and makes adjustments.

After the learning process is completed, we are left with a robust strategy set that gives raise call and fold probabilities for any given situation. Thus, after the initial learning of the game, no further adjustments are made no matter what type of opponent the program is facing.

Using the term artificial intelligence with these bots is really a misnomer. There is no 'thinking' going on. When playing, they are simply looking up in a table what the appropriate action for a given situation is. So how can something that has no capability for reason know when to bluff?

The answer is that there is nothing inherently human about bluffing. Bluffing isn't reading into the soul of your opponent and knowing when you can run them over. Rather, it is a necessary strategic move, just like raising a good hand. Bluffing is advantageous for two reasons.

1. Expected Value: If we have a truly horrible hand, and the pot is $10, then if we proceed to showdown we have a 0% chance of wining. We lose $5 (our contribution to the pot. On the other hand, if we bet $2 and there is a 25% chance our opponent folds, then on average we lose $4. Not good, but better than losing five, which we would have by not raising
2. Information Hiding: The more information you have about what cards your opponent has, the more you can exploit his play. Thus, in order to minimize exploitation, it is necessary to sometimes raise with an unexpected hand (bluffing). Also, sometimes a good hand should be checked instead of raised (slow playing).

Though not perfect, INOT and Fell Omen play at a very advanced level. They were very successful in eradicating weaknesses, and what is left are robust bots whose play exhibits all of the advanced strategic tools necessary to beat expert humans.

Follow the links below for information about my poker research:

INOT at the AAAI'07 Computer Poker Competition

Fell Omen 2 at theAAAI'08 Computer Poker Competition

Download INOT and Fell Omen

Technical Report

News Update : 8-04-08

    * Press Release from UCSD

Update: 8-11-08

I'm very happy to see all of the interest that has been expressed over these bots (welcome stumblers). I would like to clarify two points which have caused some confusion.

1. These bots only play heads-up limit poker. There is much work to be done in tackling the more difficult problems of full ring poker, and no limit hold'em.
2. Online gambling is not dead (contrary to some quotes that have been attributed to me). I have full confidence that the security teams at the various poker sites would have little trouble adapting their practices to stop those who would use this online.

News Update 8-12-08

An article about my work, and the work of the CPRG at the University of Alberta appeared in the Union tribune today

The Article

One nit picky point: Fell Omen 2 does not "have no weaknesses," as it was clearly beaten by Hyperborean. What I said was that it attempts to make its self unbeatable by leaving no room for exploitation.