Productive collaboration of a Computer Science Professor Tuomas Sandholm and his colleague, graduate student Andrew Gilpin has resulted in creation of a game-theory-based computer program that will soon take party in competition held by the American Association for Artificial Intelligence. This competition known as 揅omputer Poker Competition?will start on Wednesdy, 16 th of July 2008 in Boston.
Tuomas Sandholm, a Carnegie Mellon University computer scientist has cogently demonstrated that one shouldn't necessary need to know a lot about Texas Holdem (basics and theory) in order to create a computer program (they actually call their project 揚oker Robot?, which will be able to play a winning Texas Holdem hand. Poker theory in general and Texas Holdem theory in particular are at the heart of their 揚oker Robot?called GS1. Tuomas Sandholm, director of Carnegie Mellon's Agent-Mediated Electronic Marketplaces Lab and his colleague, graduate student Andrew Gilpin say that no specialized expertise of any of the human Texas Holdem players were applied during creation of GS1.
Though GS1 is not yet the equal to some human Texas Holdem world champions, it had already defeated the two leading 損oker robots?playing heads-up, limit Texas Holdem Poker during tests at Carnegie Mellon Labs, earlier this year. Both these robots were commercially available programs that were based on the expertise of human Texas Holdem players, while GS1, by contrast, develops its decisions and strategy proceeding from automated mathematical analysis of Texas Holdem rules.
Since preliminary testing at Carnegie Mellon's Labs, Tuomas Sandholm and Andrew Gilpin have developed an improved version of their game-theory-based Texas Holdem bot. This version, called GS2 is a candidate to take party in the Computer Poker Competition held by the American Association for Artificial Intelligence that will occur during the 21 st National Conference on Artificial Intelligence this year.
Much as Chess Robots were an early test of AI (Artificial Intelligence), computer Texas Holdem Robots appeared to be even a greater challenge for the developers. 揟exas Holdem is a very complex game? said Tuomas Sandholm, a professor of computer theory and science in Carnegie Mellon's School of Computer Science. 揟exas Holdem Poker Robots truly require sophisticated technology and substandard approach?
Unlike many analytical games, such as chess, where the status of all pieces is known to both opponents, Texas Holdem forces opponents to make decisions based on incomplete information ?you can't see your opponent's hand and you cannot predict the outcomes of the next betting rounds. 揂ctually the sheer number of all possible combinations of the dealt cards plus community cards on the table and bets in a two-player Texas Holdem game is a billion times a billion, which makes it simply impossible even for the fastest computer systems to thoroughly analyze each and every hand? said Tuomas Sandholm.
Both colleagues also stressed that such element of uncertainty as well as the vagaries of luck, inherent in random outcomes of a card deck make Texas Holdem a better test of Artificial Intelligence projects than chess. 揅hess are always clear and Artificial Intelligence must be prepared to face a lot of a real-world situations, which are mostly uncertain and you have to deal with that uncertainty? Tuomas Sandholm said. An algorithm (sequence of analytical decisions and steps) able to play winning Texas Holdem might appear to be very useful in e-commerce software applications and other higher technology industries and markets.
Both e-commerce and higher technology industries are major research focus for Tuomas Sandholm and his junior colleagues. Several years earlier he has developed the fastest matching supply and demand algorithms, which can now be expressed in appreciably more detail than they could be expressed using older technologies before. Tuomas Sandholm is the founder, chairman and chief scientist of CombineNet, a powerful company that helps Fortune 1000 organizations save a lot of money and time on procurement. In fact, $20 billions sourced through CombineNet systems generated more than $2,5 billion in savings for customers.
Toumas Sandholm has also pioneered in Artificial Intelligence techniques that automatically set rules for e-commerce, which is another direction of his research activities. Sandholm's programs generate mechanisms able to govern electronic elections, negotiations and auctions.
The result of his computer Texas Holdem research are 揟exas Holdem Robots?that can predefine strategies for playing the first two betting rounds of Texas Holdem Poker (preflop and the flop), when opponents are dealt with two pocket cards and three community cards are dealt face-up onto the table. During the following betting rounds (the turn and the river), Sandholm's Texas Holdem Robots update the algorithm by correcting the probability of all possible hands based on the revealed cards and betting. The strategy for these rounds is then defined in real-time for the setting at hand.
In order to reduce the computational complexity of both Texas Holdem Robots, GS1 and GS2 are able to automatically recognize strategically equivalent hands. This means that there are 25,989600 different hands are possible during the second round, but just a million of hands are strategically different. However, that's still too many variants to compute, so GS1 and GS2 group strategically hands together and continue calculations based on these groups. As a result there are just 2,465 groups, which is a reasonable number for computing abilities of an average computer to analyze.
Besides of participation in the Computer Poker Competition, Tuomas Sandholm and Andrew Gilpin will present their Texas Holdem Robots during the Artificial Intelligence Conference in Boston.
