• View
• Edit
• History
• Print

August, 2007 -

This past summer I took part in an artificial intelligence (AI) competition hosted by the Association for the Advancement of Artificial Intelligence's 2007 conference (AAAI '07). The competition focused on a very interesting game that combines many of the difficult challenges facing decision makers in the real world.

Texas Hold'em poker has exploded in popularity over the past few years. This popularity has extended to academic researchers, who are intrigued by the deep problems that players face when playing. Unlike chess, poker is a game of chance. Players do not know what cards they will be dealt, or what cards will be dealt to the board. While difference adds an interesting dimension to the game, techniques for dealing with chance have been well established in the context of other games such as backgammon. What really sets poker apart is that it is a game of imperfect information. In both chess and backgammon both players have identical information about the state of the game. In chess the board is completely visible, and thus both players see the entire state of the game. In backgammon, both players do not know what the dice are going to roll until they are thrown and the position of each piece is known, thus each player has the same information about the gamestate. In poker, on the other hand, each player knows only their own cards, and the common board cards. This private information breaks the usual methods (game tree search) used to solve chess and backgammon.

My creation INOT BOT took part in the two player limit Texas Hold'em competition.

The Rivals:

There was a VERY competitive field at this years competition. There were 16 programs submitted from universities and countries around the world, including two research groups that placed in last years competition.

• The University of Alberta's Hyperborean06 took first place last year, and a new and improved version was entered this year (Hyerborean07). The University of Alberta's computer poker research group has been the leading figure in poker AI for the last 19 years. There are currently 10 researchers associated with the group. check out their web page at: http://www.cs.ualberta.ca/%7Egames/poker/ . Hyperborean07 is the culmination of their many years of research. It was programmed by Martin Zinkevich (PhD), Darse Billings (PhD), and Morgan Kan (MS).
• Carnegie Mellon University Came in third in last years competition with their bot (GS2). They are back this year with a greatly improved GS3. It was written by Tuomas Sandholm (PhD), Troels Sorensen (PhD), and Andrew Gilpin (PhD Candidate). They have been working on the problem of poker for 3 1/2 years, the result of which is an extremely robust poker player. Here is a link to a news paper article about their work (written after last years competition): http://www.post-gazette.com/pg/06200/706689-96.stm .

In addition to these contenders there were entries from individuals and universities around the world. Including:

University : University of Minnesota
Authors : Brett Borghetti

University : Gomel State University, Belarus \\ Authors : Igor Korshunov

University : University of North Carolina, Charlotte
Authors : Peigang Zhang

University : Monash University, Australia
Authors : Kevin Korb, Ann Nicholson and Steven Mascaro

University : Politecnico di Milano, Italy \\ Authors : Mario Quaresimale,Alessandro Lazaric, Mario Lozza, and Marco Restelli

University : Sequel, INRIA Futurs, France
Authors : Jeremie Mary, Remi Munos, and Maitrepierre Raphael

Results:

INOT BOT (my entry) performed very well. It squeezed out Carnegie Mellon to place 2nd.

Rank                              Team                      Win rate against INOT*
First Place:            Univerity of Albetra                       $21.00/hour
Second Place:           Ian Fellows                                 $0.00/hour
Third Place:            Carnegie Mellon                            -$4.00/hour
Fourth Place:           University of Minnesota                  -$129.05/hour
*Assuming 5/10 blinds, and 100 hands per hour

About INOT

The final product was submitted to the competition was not the final result of my research, but rather the starting point. Due to time constraints, I submitted the first working prototype that I developed, which did not benefit from the extensive refinements/improvements that I have planned. None the less, it performed admirably against its opponents. Below is a brief description of the bot:

INOT (In the Nick Of Time) BOT is a prototype limit computer poker player. It plays a fixed randomized strategy that is an approximation of a pseudo-optimal strategy. This strategy is generated by creating an abstraction of the game of poker, and then having both players (big blind and small blind) evolve their strategy by incorporating into their play the best response to their opponents play. Over many iterations this converges to a near pseudo-optimal set of strategies. Both post, and pre-flop are considered together.

Due to time constraints, INOT BOT was sent to competition before it had fully converged, and with some questions about the accuracy of the abstracted game. In the abstracted game, the best response to INOT BOT wins .0259 sb/h

Acknowledgments: Many thanks to John Riesenberg, whose kind help made it possible for this bot to join the competition.

Update 1:

INOT's successor, Fell Omen 2 places second in the 2008 AAAI Competition

Update 2:

INOT and Fell Omen are now Free Software.