This computer program can beat anyone at poker

Computers have figured out how to win at chess, checkers, and tic-tac-toe, and now a computer program has taken the game of poker.

A research team led by Michael Bowling, professor of computer science at the University of Alberta in Canada, has developed a computer program that can outperform humans in a game of two-player poker – in particular, the heads. -up limit hold’em. The findings could have far-reaching implications for other situations that require complex decision-making, such as in foreign policy or medical treatment.

Unlike chess or checkers, in poker a player does not always know the past moves of other players. Additionally, a player can win a hand when other players fold. Therefore, in mathematical terms, the game has imperfect information. [Top 10 Revolutionary Computers]

“Chess has a perfect game solution – the answer for any given position is a win for black, a win for white, or a draw,” Bowling said. “Poker is more probabilistic.” In other words, there is no absolutely perfect hand or strategy.

How it works

In the computer-played version of Hold’em Poker, the stakes between two players are fixed and the number of raises is limited. The dealer gives each player two cards, called hole cards. A betting round follows, known as a “pre-flop”. After that, three more cards are laid out on the table, called a “flop”. The flop is a set of community cards, dealt face up, so both players know what they are. Another betting round follows, then a fourth card is put on the table, called the “turn”. After a third round of betting, the last community card is dealt (this is called the “river”), and at this point, players must show their hole cards, assuming a player is not. ‘is not yet lying.

The computer does not calculate all possible hands while playing. Instead, it creates a scoreboard before the game begins. Using some 4000 central processing units for two months, or about 1000 years of computing time, it simulates billions of poker hands. The results table alone took up about 15 terabytes of computer storage, Bowling said. For comparison, a typical desktop backup drive is one terabyte. [10 Technologies That Will Transform Your Life]

The algorithm goes through all the possible hands that an opposing player could have, then counts the results for each tactic – for example, raise, fold or call the bet (i.e. match the opponent ). To get an idea of ​​the scale of the task, there are 13.8 trillion different situations that can arise in the game. To get there, every human being on Earth would have to play close to 4000 hands of poker.

This differs from chess, where a computer can brute force calculate movements as the game progresses to achieve a result good enough to win. (Contrary to popular belief, few computer programs actually go through every permutation, only those that produce the best results.) Instead, imagine if computers playing chess had to search the results of billions of previous games with a specific configuration of pieces on the chess board.

As billions of hands are played, the program offers an optimal strategy, that is, it converges on the best move for a given hand. “The way it works… he’s already played a billion billion hands of poker,” Bowling said.

Master the game

Because poker is not solvable like chess or checkers are, Bowling and his team came up with a different set of requirements to call the game “solved”. In scientific terms, the game is “essentially solved”, which means that there is a way to exploit the strategy used by the computer. The researchers assumed that a person used the computer for 70 years, 365 days a year, 24 hours a day. The program they wrote performed so well that if the big blind – the fixed bet – was 1,000. $, the maximum a perfect player can win is around $ 1 per hand, or 1/1000 of the big blind.

Other experts have worked on poker computers used in casinos, and at least one company claims to have designed a machine learning algorithm that adjusts strategy for the human player. But none have shown that its usability – the ability of a perfect human player to beat the machine – is as small as the program devised by the Bowling team. Neither has solved the game in the same mathematically rigorous way.

But the algorithm has limits. For one thing, it only works with two-handed games. In a three-player game, it is possible for one player to have terrible strategy (for example, the player may tend to raise all the time), and lose less than the second player, who has better strategy, resulting in a victory for the third player.

Another issue is how to fairly test three player games. One experiment could have two humans play the machine, but Bowling said human players can collude against the machine, even unintentionally. Similar problems could arise in experiments with two machine players and a human: even if the two programs didn’t get along, it could look like a human being. “We don’t know how to handle it fairly,” he said.

Bowling said the technology could have a variety of uses, from national security and tracking fare fraud on transit systems to making decisions about medical treatment. For example, the program could help a doctor who has to make a decision about a treatment but is unsure of the possible results. The methods used in the poker program could help physicians identify treatment options with optimal results, or one with the best likelihood of success.

The research was described online today (January 8) in the journal Science.

Follow the science live @sciencelive, Facebook & Google+. Original article on Live Science.

Gordon K. Morehouse