from the odds-are-folks-will-like-this-story dept.
Computer program 'perfect at poker'
Scientists have created a computer program they say is the perfect poker player and never makes a mistake. The developers told Science journal they had "solved" the two-player game Fixed-limit Heads-up Texas Hold 'em. And the algorithm had a strategy so close to optimal "It can't be beaten with statistical significance within a lifetime of human poker playing". The poker-ace algorithm is also now available online for people to test, query and even play against.
http://www.bbc.com/news/science-environment-30718558
Program Solves Heads-up Limit Texas Hold ‘em Poker
Artificial Inteligence has used games as a test bed for new ideas for some time. Researchers at the University of Alberta have essentially solved heads-up limit Texas hold ‘em poker.
“Poker has been a challenge[sic] problem for artificial intelligence going back over 40 years, and until now, heads-up limit Texas hold ‘em poker was unsolved,” says Michael Bowling, lead author and professor in the Faculty of Science, whose findings were published Jan. 9 in the journal Science
[Abstract].
Cepheus, created by Bowling, PhD students Neil Burch and Michael Johanson, and Finnish software developer Oskari Tammelin, is the first computer program to play an essentially perfect game of poker. Cepheus accomplished this goal with no human expert help, only being given the rules of the game.
“It was trained against itself, playing the equivalent of more than a billion billion hands of poker,” says Bowling. “With each hand it improved its play, refining itself closer and closer to the perfect solution. The program was trained for two months using more than 4,000 CPUs each considering over six billion hands every second. This is more poker than has been played by the entire human race."
Cepheus marks a milestone for artificial intelligence and game theory. Though many perfect-information games (in which all players are aware of everything that has occurred in the game before they make a decision) have been solved, no nontrivial imperfect-information game played competitively by humans has previously been solved. And although perfect information may be a common property of parlour games, it is far less common in real-world decision-making situations.
“The breakthroughs behind this result are general algorithmic advances that make game-theoretic reasoning in large-scale models of any sort more tractable,” says Bowling.
(Score: 2) by maxwell demon on Monday January 12 2015, @08:52AM
The next game this will be applied to is called Global Thermonuclear War.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 3, Insightful) by sudo rm -rf on Monday January 12 2015, @09:07AM
To me, poker is a very strange game. The only way for me to win is not to play.
(Score: 2) by isostatic on Monday January 12 2015, @11:09AM
The way to win at gambling (Poker, day trading, etc) is to play with someone elses money.
(Score: 2) by bzipitidoo on Monday January 12 2015, @11:30AM
To win against this perfect opponent, you have to reprogram the computer. Break in and change it before the match starts, like Captain Kirk did.
(Score: 2) by hubie on Monday January 12 2015, @12:59PM
I wonder how many people get this reference. You've got to have a certain fogey factor.
(Score: 2) by davester666 on Monday January 12 2015, @07:52PM
they said on the radio they want to use it to 'solve' terrorist scenarios...basically they are going after getting some of the defense budget now...
(Score: 2) by FatPhil on Monday January 12 2015, @10:32AM
"two months using more than 4,000 CPUs each considering over six billion hands every second."
61 * 4000 * 6e9 * 86400 = 126.5e18
I don't consider 126 billion billion to be accurately described as "more than a billion billion"?
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 0) by Anonymous Coward on Monday January 12 2015, @11:17AM
Well, I don't know about you, but I'm pretty sure that 126.5 is larger than 1.
(Score: 0) by Anonymous Coward on Monday January 12 2015, @11:39AM
Well, I don't know about you, but I know what "accurate" means. Perhaps you'd like to enlighten us and tell us how many significant digits the approximation shares with the real value?
(Score: 0) by Anonymous Coward on Monday January 12 2015, @01:03PM
The summary says "more than". It doesn't say "is accurately equivalent to" or "is virtually the same as" or any other sentence that implies equality. I've dug a bit into the analysis and I have found that 126.5 is "more than" 1 in pretty much any base-10 number system I can think of. Are you normally this dense?
(Score: 2) by FatPhil on Monday January 12 2015, @02:32PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Funny) by WizardFusion on Monday January 12 2015, @04:08PM
Obil: http://dilbert.com/strips/comic/2005-11-18/ [dilbert.com]
(Score: 2) by FatPhil on Monday January 12 2015, @05:12PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 5, Interesting) by CirclesInSand on Monday January 12 2015, @01:48PM
Anyone with even a mediocre understanding of game theory will know that the optimal play for each hand/board/round-history/finance will not be a "move", but a distribution of choices. Any algorithm that has a 1-1 correspondence of situation to move will easily be beaten because it gives away too much information.
I have seen lots of articles on this saying that the program finds *the* correct move. I have to hope (or despair?) that the articles are just being dumbed down for the sake of the masses, but I wonder how anyone can claim to "solve" poker without understanding this basic result. Either these summaries are very stupified, or it is just a bunch of coders with no idea what the logical consequence of their software actually is.
(Score: 4, Interesting) by MrGuy on Monday January 12 2015, @02:06PM
I think the question of what "solved" and "optimal" means are problematic, especially in a game like this.
In theory, "perfect" play would always extract the maximum amount of money from every possible opponent, regardless of their playstyle. It's doubtful such a strategy exists - a single strategy is unlike to be optimally successful against both a conservative player AND an aggressive player (AND against a player who plays more randomly).
Journalists get breathless about claims to have "solved" something, and aren't exactly the best at math. As I understand it, the theorists define success NOT as "maximal possible outcome," but rather as the following two conditions:
1.) Playing my strategy never loses to another strategy - i.e. if I play this strategy, there's no other strategy that can systematically defeat me over time.
2.) Two players playing this strategy together will stalemate - the best I can do is play the same strategy and deadlock you.
In other words, I believe they think they have found a Nash Equilibrium in Weakly Dominant Strategies [wikipedia.org] - they've found a strategy that, in theory, cannot be beaten, even if it can't be guaranteed to win (or can only be guaranteed to win slowly). If your opponent uses this strategy, the best you can do is play the same strategy (or possibly some other yet-undiscovered strategy that's equally effective in stalemating this strategy).
They've done so in a very restrictive and highly structured game (limit Hold 'Em has a very ordered, specific, and limited move set for each player - unlike No Limit, it's a MUCH more mathematical game).
(Score: 4, Insightful) by kebes on Monday January 12 2015, @02:59PM
They discuss at length what they mean by "solving" an imperfect-information game like poker:
Of course, what they have solved is the idealized version of a particular poker variant (where all that matters is the cards). If you expand the game to include additional information (such as being able to see the other player, and, e.g., having prior knowledge of their play-style or being able to 'read' their intentions), then one can imagine 'better' strategies (inasmuch as you will extract money from your opponent even more quickly). But, the contention is that if you play against this algorithm, no matter what strategy you use, you will eventually end up losing, on average (or tying, on average). They carefully qualify this result, since in principle a 'truly perfect' strategy would be slightly better than the one they have found. However as they note, the difference between the strategies would be so small that even a lifetime of play wouldn't expose the difference.
So, the researchers have very carefully defined what they mean by 'solved' (they specifically claim "weakly solved").
(Score: 3, Informative) by kebes on Monday January 12 2015, @02:37PM
This paper is pay-walled, which is too bad, since it's quite interesting, and very readable (for a scientific paper). If you're looking for a less-dumbed-down description of the result, maybe read this [preposterousuniverse.com].
The proposed solution does indeed include probabilities. For any given state (known cards and current state of betting history), the algorithm/solution has probabilities for what it will do next (fold, check, raise, ...). So the solution is not deterministic (just as the game itself has an element of randomness); but the associated probabilities have been optimized to be 'near perfect' (of course, the paper goes into great detail about exactly what they mean by this). So, the proposed solution will indeed do things like bluffing (sometimes). This of course also means that the algorithm will not win every single hand. It just means that if you allow it to play enough hands, it will either beat or tie (on average) any other strategy you put it up against.
(Score: 2) by bootsy on Monday January 12 2015, @01:55PM
If this algorithm is so effective have the authors cleaned up by running it against on line Poker sites?
(Score: 2) by ikanreed on Monday January 12 2015, @05:13PM
Online poker sites are illegal in the country this software was made.
Ignoring that might be fine and dandy for private individuals who aren't worried about getting caught, but not something you're gonna drop into a press release for a major organization.
(Score: 2) by hubie on Monday January 12 2015, @02:04PM
If the computer program played itself, how do they know it is the optimal solution instead of just wandering into a local minimum in parameter space?
(Score: 2) by FatPhil on Monday January 12 2015, @05:02PM
Cepheus marks a milestone for artificial intelligence and game theory. Though many perfect-information games have been solved, no nontrivial imperfect-information game played competitively by humans has previously been solved. And although perfect information may be a common property of parlour games, it is far less common in real-world decision-making situations.
"""
Poker has not been "solved", if you're looking for this to be a real milestone in AI. Solving would be a milestone, but this isn't solving, IMHO. They've annealed a presumably mixed strategy (as per Nash's work 6 decades ago) which is not significantly sub-optimal and is a local maximum. That's different from solving a game. For that they'd need to prove that their local maximum was the global maximum, and to keep the mathematicians happy (and Game Theory is a field of mathematics) express that global maximum in a closed form without error bars. (For example, scissors-paper-stone has been so-solved.) Closed form can just include a unimaginably huge table of constants, that wouldn't be a problem for a mathematician, anything that's finite is fine.
Something a bit more complex than scissors-paper-stone, for which I have seen a claim of being solved, is a game called "footsteps". I, two game theory PhD students, and their supervisor, all reviewed the algorithm that generated the tables dictating the mixed strategy, and the bot itself, and everything seemed to agree with the mathematical theory describing an equilibrium mixed strategy. However, when that bot played against humans, it had a less than 50% win rate, even though it was theoretically "perfect". Alas the sample size wasn't big enough to be sure this wasn't just noise. However, it was tempting to say that the humans were able to sucker the bot into investing too much in the first few moves of the game, leaving it more vulnerable at the very end. Which makes no sense, as Nash equilibium is absolute, the bot should be optimal against any opponent. That just remained a mystery. (Of course, "optimal" doens't always mean "never loses in the long run", but in the context of this zero sum game, it should have done.)
But anyway, since that occasions, when I see claims of game-theoretic "solution" I often remain dubious unless I can see a constructive proof. And simulated annealing I do not consider a constructive proof. (However, solution of (perfect-information games) draughts, connect-4, and dots-and-boxes at various sizes I have no issue with, they're good (computer-assisted) maths.)
Anyway, I hope the top poker players are up for the challenge, and give this program a good grilling. Not that it knows how to play more than one opponent at a time - and that's incredibly important for the real game.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 0) by Anonymous Coward on Tuesday January 13 2015, @11:26AM
Yeah.. Card counting isn't allowed in any casino and that "AI/Expert System" is definitely card counting among other things. So it is interesting but not applicable "in-person". On-line gambling however, hmm...
(Score: 2) by CirclesInSand on Thursday January 15 2015, @03:30AM
This is not correct. Courts have ruled that card counting is not cheating: the casino can ask you to leave, but they cannot withhold your winnings.
Furthermore, card counting is a strategy for the game blackjack, and although as a general principle it can apply to other games, "Texas hold em [sic]" is not one of them.