About MeI recently defended my Ph.D. at the University of Alberta in the Department of Computing Science in Edmonton, Canada. I study artificial intelligence and machine learning, applied to the types of problems that humans find challenging and intriguing, such as competitive games of skill. I find ways to program (or more accurately, train) computers to perform as well or better than the best human experts. Human experts can spend years studying a game like poker or chess and play the game at a high level of skill, and the clearly defined rules and goals allow us to make computer programs that can compete against them. By pitting human intelligence against artificial intelligence, we can directly measure the progress of our research towards producing computer agents that make good decisions.
Since 2006, I have been a member of the University of Alberta Computer Poker Research Group, and have developed techniques for creating world-class poker agents. This work is largely driven by the Counterfactual Regret Minimization (CFR) algorithm, which is a self-play technique. Instead of directly programming the computer how to act in each situation, we instead set the computer up to repeatedly play games against itself. At each decision, it estimates the value of taking each action, and then improves its strategy a little by choosing better actions more often in future games. Over billions of games (which takes days or weeks), the program improves and tries to limit how much it can lose against a perfect adversary. We can then use its strategy to play against human experts, as we did in our 2007 and 2008 Man-vs-Machine Poker Competitions. In 2008, our program Polaris defeated a team of top human experts in a game of Heads-Up Limit Texas Hold'em, marking the first time that a computer program defeated human professionals in a meaningful poker match.
In January 2015, we used a new algorithm called CFR+ to solve the game of heads-up limit Texas hold'em, and our program Cepheus is now essentially unbeatable by any human or computer opponent: even a perfect adversary who has a copy of Cepheus' strategy and unlimited computation. This was the first human-scale imperfect information game to be solved, and the result was published in Science.
Copies of my research papers and short summaries can be found on my Publications page. If you're looking for one good summary paper of our work, I'd suggest my PhD thesis [PDF] from 2016. This paper-based thesis covers seven core papers that took us from our Polaris agent in 2008 that beat human pros in the Second Man-vs-Machine Poker Championship, to our Cepheus agent that solved heads-up limit Texas hold'em in 2015. If you'd like to keep up-to-date with our group's progress, use our Twitter feed: Follow @PolarisPoker, or follow me on Twitter: Follow @mikebjohanson
January 02016: PhD defended!
I defended my PhD this afternoon (January 14th)! Details and thesis are here: [HTML].
October 02015: Thesis complete!
My PhD thesis is off to committee, and the preliminary defence date is January 14th.
May 02015: CFR+ paper is online
We have a paper to appear IJCAI 2015 that is a companion to the Science paper about solving heads-up limit. While the Science paper is about the milestone of solving the first imperfect information game played competitively by humans, the new IJCAI paper focusses on the algorithm, CFR+, that made the result possible. It includes theoretical convergence proofs, empirical results in smaller games comparing CFR and CFR+, and engineering details on the distributed solver and compressor that we used to handle the size and time challenges. Here's a link.
January 02015: Heads-up Limit Texas Hold'em Poker is Solved!
In a paper published in Science, we (Oskari Tammelin, Michael Bowling, Neil Burch and myself) have just announced that we have solved Heads-up Limit Texas Hold'em Poker. This is the first time anyone has solved a real (nontrivial, played by humans) game that includes imperfect information, and is among the first solved games that include random chance.