Sunday, April 26, 2015

For the first time, artificial intelligence will play poker against top human players

To the A.I., a simple game of poker is a tree of all possible events. Image from Heads-up Limit Hold’em Poker is Solved by Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin.
Claudico, an artificial intelligence program developed by Professor Tuomas Sandholm at Carnegie Mellon, will be playing heads-up no-limit Texas hold’em against four top human players. 80,000 hands will be played over the course of fourteen days, from April 24th to May 8th, and the matches will be streamed every day on Twitch.tv starting at 11:30am in the morning. The difference between poker and games like chess or checkers is the amount of information available to the players. Poker is a game of imperfect information, where the knowledge of the opponents' hand is unknown and the cards dealt are based on chance. As opposed to chess, a game of perfect information, both players know every single action the opponent has taken against them. Poker has become the basis for imperfect information games because there are already broad skill levels for computers to play against, with the added layer of complexity for interpreting other players' actions while simultaneously hiding your own.

 A solution concept for a game like poker is called the Nash equilibrium. The definition is simple, for non-cooperative games, the strategy each player has chosen to play the game is the best strategy they can employ assuming they know the strategies of others. Players will receive no benefit from changing their strategies as the strategy they already chosen is the best strategy for them. Finding the Nash equilibrium, the best possible way of playing the game, using linear programming takes an exponential amount of time, O(2nk). This is a simpler time complexity than brute forcing a traveling salesman problem (TSP) but still takes an incredible amount of time because it's not polynomial. However, finding the Nash equilibrium does not fall under NP-complete. Nash's theorem concludes that a solution is guaranteed to exist, while it's unclear whether NP-complete problems can have a polynomial solution at all. So instead of being grouped under NP-complete, Nash equilibrium falls under another subclass of NP call PPAD, where solving the problem may be difficult but the solution is guaranteed to exist. This applies for finding the Nash equilibrium on non-cooperative games with k-players, provided k is a finite integer greater or equal to two.

An A.I. plays the game of love. Image courtesy of https://xkcd.com/601/.
The first algorithm to solve imperfect-information games in polynomial time was developed in 2003 and applied to poker in 2005. As of January 2015, heads-up limit Texas hold 'em poker has been declared weakly solved by Bowling et al. (2015). The algorithm can now win or draw against all possible moves the opponent makes from the very beginning. It does so by computing a very good approximation of the Nash equilibrium strategy. With the tournament just beginning, will Claudico follow the footsteps of Deep Blue and Watson and mark the next milestone in artificial intelligence? 

Edit: I mistook exponential as factorial and it has been corrected.

References

The official website for Brains vs Artificial Intelligence 

Bowling, M., Burch, N., Johanson, M., & Tammelin, O. (2015). Heads-up limit hold'em poker is solved. Science, 347(6218), 145-149. doi:http://dx.doi.org/10.1126/science.1259433

Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. (2009). The complexity of computing a nash equilibrium. Association for Computing Machinery.Communications of the ACM, 52(2), 89. Retrieved from http://search.proquest.com/docview/237061886?accountid=14541 

Fortnow, L. (2005, December 15). Computational Complexity. Retrieved April 26, 2015, from http://blog.computationalcomplexity.org/2005/12/what-is-ppad.html 

Osborne, M., & Rubinstein, A. (1994). A course in game theory. Cambridge, Mass.: MIT Press.

Rubin, J., & Watson, I. (2011). Computer poker: A review. Artificial Intelligence, 175(5-6), 958-987. doi:http://dx.doi.org/10.1016/j.artint.2010.12.005

Sandholm, T. (2010). The state of solving large incomplete-information games, and application to poker. AI Magazine, 31(4), 13-32. Retrieved from http://search.proquest.com/docview/847665029?accountid=14541 

von Stengel, B. (2010). Computation of nash equilibria in finite games: Introduction to the symposium. Economic Theory, 42(1), 1-7. doi:http://dx.doi.org/10.1007/s00199-009-0452-2
Posted by at
Labels: , , , , , ,

5 comments:

  1. UnknownApril 26, 2015 at 8:17 PM

    This week's blog post was interesting for me as a Poker player. I'm sure I wouldn't be good enough to play Claudico though haha. But I think its amazing what artificial intelligence can do and I now have a better grasp of why the TSP is an important issue to solve. I think that Claudico definitely has the potential to follow Deep Blue and Watson. It sounds like it is almost there, because even Watson wasn't always perfect when answering the questions on Jeopardy. Of course, Watson still demolished the contestants, but Jeopardy is a bit more easy to program a computer to play than poker, I believe. I will be interested in finding out the results of the poker match!

    ReplyDelete
  2. AnonymousApril 26, 2015 at 9:22 PM

    I have read about Dr. Watson which is an artificially intelligent computer that competed on Jeopardy and won. I had never heard of Claudico until today. I wonder how the algorithms were developed to calculate bluffs from players who are human. One aspect that I think the computer will be better than human is to store data such as different hand samples, cards counting and memorize player’s style of play. I do think humans play with emotion and probably taking more risks. The more risk is the more reward. I will be following this event. The outcome will be very interesting. It does not matter who wins.

    ReplyDelete
    Replies
    1. Alan LiApril 27, 2015 at 1:36 AM

      Funny you should ask about how the A.I. is going to play because the answer is in the name of the A.I. itself. Claudico" is Latin for "limp." Basically it'll just call to get into a hand. Most of the info I got on it is here https://www.cs.cmu.edu/brains-vs-ai#April-24-2015-b

      Delete
  3. UnknownApril 29, 2015 at 11:36 PM

    I find this type of advancements in A.I. interesting because although it seems like it is just for playing a game, such methods of designing and programming A.I.'s like Claudico may lead to greater advancements in other areas of technology such as control systems on board planes or spacecrafts. In fact, my research topic (Re-usable rockets) involves the implementation of complex control systems, which are responsible for the flight and landing of the rocket, that may one day benefit from break through's like Claudico.

    ReplyDelete
  4. UnknownApril 29, 2015 at 11:56 PM

    It's amazing what humans are capable of creating with artificial intelligence. This seems almost like the exact same sort of scenario like in all of the terminator movies where human kind develops artificial intelligence but eventually backfires due to their ability to learn and function on their own. This would be highly unlikely with the poker AI machine since it is only programmed to complete one specific task and that is to calculate the best decision in a turn of poker. Although creating machines to make more practical actions like fixing a car or driving people, it would limit job availability for people everywhere. I think just using these machines for simple things like poker should be left as it is.

    ReplyDelete

Subscribe to: Post Comments (Atom)