|From the series "Dogs Playing Poker," (1903) by C.M. Coolidge
Dogs Playing Poker, a series of 16 oil paintings by C.M. Coolidge, originally commissioned in 1903 by Brown & Bigelow to advertise cigars, will forever remain iconic images indelibly imprinted in pop culture.
If Robots Playing Poker ever catches on, then it will owe considerably to innovations being realized in Edmonton.
Helping provide this poker-related leadership is Michael Bowling, a Professor in the Department of Computing Science at the University of Alberta. He is also a principal investigator in the Alberta Innovates Centre for Machine Learning (AICML) and the Department of Computing Science’s Reinforcement Learning and Artificial Intelligence group (RLAI) – both initiatives are funded by AITF.
As part of his work, Michael also leads the Computer Poker Research Group (CPRG). Based at the University of Alberta, the CPRG is “working on creating computer programs that play poker better than any human being as a test bed for doing good science.”
To help further their research, the CPRG started the Annual Computer Poker Competition in 2006. The event attracts competitors, both academics and hobbyists alike, from countries around the world.
|The Computer Poker Research Group (CPRG)
At the eighth-annual competition held at AAAI Conference on Artificial Intelligence this July, the CPRG won three of the six events, with two second-place finishes and a third-place finish in the other three events:
- In Heads-Up No-Limit, the CPRG took first in instant run-off (not losing to any of the other 13 entries), and second in total bankroll.
- In Three-Player Limit, the CPRG took first in both instant run-off and total bankroll
- In Heads-Up Limit, the CPRG took second in instant run-off and third in total bankroll.
This is the premier event for computer poker and there were 19 teams from 14 countries competing. Roughly 50 million hands of poker were played between all of the computer programs!
But what is the connection between computer poker, the Centre for Machine Learning, AITF and everyday Albertans? To find out, we caught up with Michael who was assisted by Neil Burch, a Ph.D. student at the University of Alberta, working in computational game theory. Neil currently co-chairs the ACPC.
What is the Annual Computer Poker Competition?
The Annual Computer Poker Competition (ACPC) is a yearly event where computer programs play poker against other computer programs. Teams from around the world have a chance to submit an agent for three different variants of Texas Hold ‘em poker, which is a popular game for human players. This past year, there were 35 entries submitted by 19 different teams from 14 different countries.
Unlike human poker competitions, the ACPC is interested in science. No one wins, or loses, any money in the ACPC. The goal is to evaluate the skill of the competing agents and the science behind their development.
Winners in human competitions are often determined by considerable amounts of luck playing, at most, a few hundred hands of poker. Human players are also very interested in hiding how they play. If a player folds their hand, then the information about their cards is lost forever. Really, top human players wouldn’t have it any other way.
In the ACPC, instead of playing hundreds of hands, the programs each play tens of thousands of hands against one another. The cards are also dealt in a way which reduces the effects of luck, like in duplicate bridge.
In 2013, the programs played a total of about 50 million hands of poker. After the competition concludes, the ACPC provides a transcript of every hand played, with all of the player's cards revealed. The ACPC was intentionally designed to be ideal environment for researchers who are trying to verify their scientific hypotheses and improve their agents.
Why is the ACPC an important event?
|Please note: the ACPC has no connection to online poker gambling sites
Poker is a great test bed for research because it has many features of real world problems: uncertainty about future events, uncertainty about what other participants will do, uncertainty about information that is not known. In general, a game is just a well-defined problem where a player has to make some decisions to reach the best outcome.
Human games are designed to have an obvious goal, which makes it easy to measure progress during research. The techniques learned for a class of games, like the ones involving various forms of uncertainty to which poker belongs, can often be applied to similar real-world problems where progress might be harder to measure.
For example, auctions, negotiations and national security are applications with strong similarities to poker. Sometimes the scientific ideas can apply even farther afield. This includes automatic deployment of sensors to model ecological phenomenon and making robust personalized policies for Diabetes treatment. These are two areas where research ideas originally explored in poker have been studied further.
The ACPC is the only event that lets Artificial Intelligence researchers and other interested individuals test their ideas against each other in the game of poker. Human competitions aren't designed for computer entries and there is a long history of competitions, ranging from checkers and chess to bridge, that add explicit barriers to computer players.
Even when the barriers to entry are overcome, in the case of poker, human competitions are too short to provide accurate scientific data. A special-purpose computer poker competition like the ACPC is easy to enter and provides the entrants with better evaluation of ideas and more data than can spur further scientific development. Finally, competitions can be a great motivator for graduate students – and faculty I like winning, too.
What challenges or questions does the competition hold for entrants?
|Hungarian-born American John von Neumann was a pioneer in exploring algorithms used in games of chance
Algorithms for choosing good actions in games like poker is an ongoing research question. As noted, poker is primarily about uncertainty and addressing uncertainties requires scientific advances across multiple fields.
Coping with uncertainty in opponent cards, as well as hiding information that would be detrimental to reveal, are two fundamental challenges in computational game theory. Modelling opponents to better respond to their strategies and tendencies is a machine learning challenge with a possible psychology influence. Evaluating the performance of agents is a statistical challenge.
Doing all of this at the massive scale necessary to cope with the immense number of possible decisions a poker player is forced to make is a challenge for high performance computing. Even the smallest game played in the ACPC has 100 million million (or 10,000 billion) possible decision points.
The ACPC offers an additional challenge: any ideas need to be turned into a usable computer player. Any program entered in the ACPC has to reliably play hundreds of thousands of hands, against a variety of opponents, all within human-like time limits. This transition from idea or scientific theory to working program is a non-trivial task. Every year, there are entrants to the ACPC who believe they have a good idea, but end up being unable to produce a program which satisfies the real-world constraints of the competition.
You entered the tournament as part of the Computer Poker Research Group. What is the CPRG?
The Computer Poker Research Group is a research group at the University of Alberta focused on pioneering the next generation of artificial intelligence techniques for coping with the many types of uncertainty faced in human-scale decision-making. As already noted, these types of uncertainties are the very embodiment of the game of poker. The origin of the study of strategic decision-making, called game theory is even linked to the game of poker. The field's pioneer, John von Neumann, played poker and it was one of the games that motivated his ideas.
Our research focuses on addressing the theoretical, computational and practical challenges for computer programs to not only play poker well, but to beat top players. As our approaches do not focus on expert knowledge, but rather reasoning on first principles, our techniques are advancing the state of the art of general strategic decision-making at human scales.
How do the group and competition interrelate to or support work being done at AICML?
|Pro poker player Phil Laak
For 15 years, the CPRG has been at the centre of research in computer poker. We are widely regarded as having the strongest poker-playing programs in the world. In 2007 and 2008, our Polaris program (Editor’s note: Neil is a member of the team that developed Polaris) competed in two Man-Machine Championships in heads-up limit Texas Hold 'em. The opponents were top professional players, including Phil Laak (2007) and Matt "Hoss-TBF" Hawrilenko, who, in 2008, was widely considered the best heads-up limit Texas Hold 'em player in the world.
(Check out this BBC documentary by Simon Singh, The Computer with a Poker Face, which was recorded during the first Man versus Machine poker match in 2007.)
Polaris narrowly lost in 2007, but won in 2008 and became the first computer poker program to beat professional players.
In 2006, we helped create the ACPC. Since its inception, our group has won 20 of the 33 events, including not losing a single match in any event in 2011.
Our technology also was the basis for our collaboration with clinical psychologists at the University of Calgary to study human self-assessment and its relationship to problem gambling. The scientific contributions that have enabled these successes are broad, resulting in more than 15 papers in the last five years in top venues for artificial intelligence research.
Was having a functional background or familiarity with poker a prerequisite to getting involved on the project/team? Do you or any of the team members play poker regularly?
An interest in poker can make our research more attractive to some people, but the general area of research is attractive on its own. A few of the CPRG members have been poker players, but the large majority never played poker before getting involved – and most still don't play.
The poker playing minority, though, has consisted of some good players, including one past member who has a number of strong finishes at the World Series of Poker. From a non-poker-playing perspective, which applies to myself and Neil, working on poker is still great. Many people are familiar with poker, which makes it easier to communicate with people about our work, and to talk about past and future milestones.
In addition to leading the CPRG, I am one of nine principal investigators in the Alberta Innovates Centre for Machine Learning (AICML), which is one of the world's leading centres for machine learning research and commercialization.
Beyond the CPRG, my research interests are very broad. In fact, most of my research under the AICML umbrella is not poker-related at all. However, AICML is a tightknit research community and we share our advances as well as working on many projects jointly. Unsurprisingly, opportunities to apply CPRG technology outside of poker and even commercialize aspects of the technology have arisen between the CPRG and AICML.
In one project supported by AICML, a medical researcher approached us after hearing about our success in defeating top professional poker players for the first time thinking, "If they can conquer poker, then why not diabetes?" This project has led to new results in robust decision-making when working with an uncertain model – which indeed describes both the problem of poker and diabetes – and has involved explicit application of algorithms first pioneered within the CPRG.
Another joint AICML-CPRG project is exploring the automatic detection of collusion, where two or more parties coordinate their behaviour to the detriment of others. This work has commercialization opportunities both inside and outside of poker. So, together, the AICML and CPRG are making both research advances and pursuing avenues for commercialization.
In a larger sense, how will the CPRG's work benefit Alberta's innovation system and the province?
First, the CPRG is making fundamental scientific advancements in understanding decision-making in scenarios with various forms of uncertainty. We have developed algorithms which solve larger problems, by many orders of magnitude, and we have improved techniques for reducing the size of problems.
These advancements can influence applications ranging from economics to security to medical decision-making. These will ultimately impact the real lives of Albertans, whether through advances in personalized medicine, helping realize more efficient markets that are less prone to manipulation and even safer travel. Having the innovation occur in Alberta is also great for our province's reputation as an innovation leader, and for the jobs these innovations create.
Second, the CPRG attracts, trains, and graduates a considerable number of highly qualified personnel. In the past five years, the CPRG has contributed to the training of seven M.Sc. students, five Ph.D. students and two post-doctoral fellows. And these are the very top students. Of the 12 graduate students, 10 are recipients of major graduate scholarships from Natural Sciences and Engineering Research Council of Canada or AITF. Our track record of producing such strong people was a considerable factor in helping Gamesys, a major international online gaming company decide to locate a new development office in Edmonton.
Third, we have explored and continue to look for direct commercialization opportunities. The CPRG has led to the BioTools Inc. spinoff company and we are in discussions with others about commercializing some of our technology.
Based on your ACPC-related success, are any or all of you hitting Vegas anytime soon?
|The Las Vegas Strip, from the south end, looking north
Very unlikely! First, I should be clear that our poker programs do not play online for money. Second, our program's success is the result of scientific advances and not any human knowledge we possess. So, we're not a secret team of elite poker players! And finally, being a top-notch poker player requires a dedication of time and study that our scientific pursuits don’t really allow time for. We leave the playing of poker to the pros ... and our programs!