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.
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.
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
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
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.
INOT's successor, Fell Omen 2 places second in the 2008 AAAI Competition
INOT and Fell Omen are now Free Software.