My name is Richard Gibson and I am a PhD student and member of the Computer Poker Research Group (CPRG) at the University of Alberta. Each year, our group competes in the Annual Computer Poker Competition (ACPC) that pits poker-playing computer program against one another in a number of different formats of Texas Hold ‘Em.
This is the first in a short series of blogs about the ACPC and the CPRG’s entries into this year competition. These blogs will lead up to the announcement of the competition results on July 23 at the AAAI conference in Toronto. In this first part, I'll describe the history and the current state of the competition.
In the past two decades there have been tremendous advances in game-playing computer programs: from Deep Blue beating the human world chess champion, Garry Kasparov, to the solving of checkers with the unbeatable computer checkers program, Chinook. Chess and checkers are examples of deterministic games with perfect information: Players know the exact state of the game at any time and the future state resulting from taking a legal action.
Poker, on the other hand, is a stochastic game with imperfect information because card deals are random and players do not see the private cards held by the other players. Because of these complications, computer decision-making strategies that work well in chess and checkers programs, like alpha-beta search, are not applicable to poker. Dealing with these complications is non-trivial and many real-world problems, such as on-line trading markets, face similar complications. This makes computer poker an exciting domain for research.
To help drive the research, the ACPC was formed in 2006. The first competition was quite small, where the only game played was heads-up (two-player) limit (fixed bet sizes) Texas Hold ‘Em and consisted of only four entrants. Now in 2012, there are three different games played in the competition, heads-up limit, heads-up no limit, and three-player limit Texas Hold ‘Em. The competition has grown significantly. In 2011, researchers submitted 21 programs for heads-up limit, 8 programs for heads-up no limit, and 10 programs for three-player limit. In the future, more games will likely be introduced as recommended by competitors and the competition’s steering committee.
One of the main intents of the ACPC is to produce statistically significant results—a tricky issue, because the luck of the cards can greatly impact the outcome of a single hand. In the two-player games, several 3000-hand matches are played between every pair of programs in a round-robin format, with each program’s memory being wiped clean before each match. To further reduce variance, the matches are run in duplicate, meaning that the entirety of every match is repeated with the exact same card deals, except the programs exchange hands. (In the three-player format, 1000-hand matches are played between each combination of three programs.) In order to complete such a large number of matches in a reasonable time, programs are only allowed an average of seven seconds per hand to act.
After millions of hands of poker have been played amongst the programs, two different mechanisms are used to determine the winner in each of the three games. In the “total bankroll” mechanism, the winner is simply the program that wins the most chips against all of its opponents combined. Thus, winning often relies on the ability for a program to recognize the weaknesses of its opponents and exploit them for as many chips as possible.
In contrast, the “bankroll instant-runoff” mechanism for determining winners sequentially eliminates the player that earned the fewest chips against the remaining non-eliminated players. The last player standing is then declared the winner. Here, it is more important to defend one’s chip stack than it is to exploit an opponent’s tendencies.
With the three games in the current competition and two winner-determination rules per game, the ACPC currently has a total of six divisions. Because the success of a program may significantly differ depending on how a winner is determined, teams may submit one program per division.
In the next blog in this short series, I will discuss the CPRG’s and other team’s entries in past competitions and provide insight into the programs that we submitted to this year’s ACPC.
Photo: Getty Images
