Computer scientists in Edmonton, with an assist from a Finnish software developer, have solved head-up limit hold'em (HULHE) poker, commonly known as Texas Hold'em. Philip Ball of Nature writes about the new algorithm that plays one of the most popular variants of the game "essentially perfectly":
"This is a step beyond a computer program that can beat top human players, as IBM's chess-playing computer Deep Blue famously did in 1997 against Garry Kasparov, at the time the game's world champion. The poker program devised by computer scientist Michael Bowling and his colleagues at the University of Alberta in Edmonton, Canada, along with Finnish software developer Oskari Tammelin, plays perfectly, to all intents and purposes."
Ball describes how the scientists incorporated their poker-playing computer with several key components that helped it become the perfect tactician. These include a "regret value" that allowed the algorithm "to re-evaluate decisions considered to be poor in earlier training rounds." The learning factor, says Ball, made it so the computer could quickly understand the best possible move for any of the 3.16 × 1017 states that HULHE can reach.
Ball also mentions that this achievement was aided by the development of a system that could store all that information -- about 262 terrabytes worth.
"The researchers figured out a data-compression method that reduces the volume to a more manageable 11 terabytes and which adds only 5% to the computation time from the use of disk storage."
While developing a system to solve poker is a great way to start a conversation at a bar, Ball explains that there are other uses for an algorithm like this. That's because solving poker means solving a game that relies on making deft decisions despite not having perfect information at your disposal. This is what separates a perfect poker computer from a perfect chess computer. In chess, everything you need to know about the game is splayed out on the board. In poker, there's no way to know what cards your opponent has outside of cheating.
"The class of games with imperfect information is especially interesting to economists and game theorists, because it includes practical problems such as finding optimal strategies for auctions and negotiations."
So once the algorithm is done schooling us humans in poker it can move onto things like auctions, negotiations, medical decision-making, and portfolio management.
Read more at Nature
Read the scientific paper at Science