This notion is completely and utterly false. In fact, it is _spectacularly_ wrong.
The strongest checkers playing entity in the world is the program Chinook -- vastly stronger than any human that has ever lived. It was written by my supervisor, Jonathan Schaeffer, who is a mediocre checkers player, at best.
The Othello program Logistello *crushed* the human world champion 6-0 in a 1997 match. It's author, my friend Michael Buro, claims to be a weak Othello player.
For the game of Lines of Action (LoA), I wrote a program called Mona that won the de facto world championship in 2000, and has won every game it has ever played against the world's best human players. I don't play LoA at all. (More than once I questioned a choice of Mona's, only to discover that my preferred move was, in fact, illegal.:)
I know a lot about poker, but that could actually be a hindrance to writing a world-beater program. Finding the best algorithmic solutions to a problem is not based solely on the personal knowledge the programmer has about the domain.
Actually, we did the multi-player game about eight years ago, and eventually produced a program that is better than an average human player (it has won consistently against humans on our online server for tens of millions of games). It's not nearly as good as the best human players though (and won't be any time soon). The program is available as part of the poker training software "Poker Academy" (http://www.poker-academy.com/poker-software/).
Although the multi-player game is harder in theory, in practice the heads-up game turns out to be tougher, because the amount of tricky play (bluffing and trapping) is much higher for 1-on-1.
There will likely be a multi-player tournament as part of next year's AAAI competition. There might also be a competition for heads-up No Limit Hold'em (or it might be added in 2008).
The article did not explain this part of the competition very well. The bots did not have access to any hidden information. The opponent's cards were only revealed at a showdown.
Here's how it works. A mini-match (1000 games) was played, with all of the cards recorded. Then a completely separate mini-match was played with the same cards, but with the positions reversed. This is possible because fresh copies of the programs can be started with a clean slate, having no memory of the previous match. (In fact, the two halves of the mini-match aren't even played on the same computer). Many of these duplicate matches were then played (40 for the fast competition, 12 for the slow competition) between each pair of players.
It is essential to run the matches in duplicate, in order to equalize the opportunities each side gets. The natural fluctation (variance) due to luck is huge in poker, making it very difficult to separate the signal from the noise. The problem is much worse than most people imagine, making accurate measurement of performance a sticky problem. The duplicate matches go a long way toward reducing that variance, and revealing the true long-term expectation.
[On a related note, I created a technique for direct assessment of poker decisions, which cuts away much of the noise. It is described in detail in my PhD thesis, which should be available from the CPRG website (http://games.cs.ualberta.ca/poker/) in September. A detailed analysis of the AAAI matches will also be available.]
Incidentally, there are a lot of incorrect statements being made in this thread. See the post titled "Some Actual Factual Information" for links to some of the original sources.
Yes, that comment is cracked. It was made by one of the "skeptics", but they are either clueless, or they're in denial. (Perhaps it is the official position of one of the major online poker rooms, who want the whole discussion to quietly go away [and cigarettes don't hurt people, either -- Philip Morris]).
Writing an interface to play online is not especially difficult. I'm sure dozens of people have done it independently, if not hundreds.
Writing an AI that can win enough to beat the rake is a lot tougher. A sharp programmer with some knowledge of poker could probably do it, but her efforts might be spent a lot more profitably on something completely legit, that brings value to many people.
- Darse. (hey look moderators, it's the guy in the story!:)
Here is an excerpt of my e-mail exchange with Mike Brunker (the author of the MSNBC article) prior to our phone interview. It might provide some interesting information on the topic.
- Darse.
[begin excerpt]
(1) It is not easy to write a good poker-playing program.
It took us (the Computer Poker Research Group at the U of A, http://games.cs.ualberta.ca/poker/) a few years to develop a program that could win consistently in higher-level games against opponents who took the game seriously. It has been successful against human players of average skill for many years now, but it is the only known program that can make that claim.
We operate a free poker server where people can play against our bots. Hobbyist programmers can also have their programs connect to the server and play in those games, and more than a hundred programs have participated over the past few years. None of them has come close to being a winning player, so it is clearly not a trivial task.
(2) Is it *possible* to write a very strong poker program?
Absolutely.
Poker is a challenging and rewarding field for research in Artificial Intelligence (AI). There are many aspects of the game that make it more difficult and more interesting than games like chess and checkers.
It isn't simply a matter of computing probabilities and other numbers. A good program has to *think* about the game in the right way. Master-level poker requires an understanding of how each opponent plays the game -- you must observe and adapt as you play, and that turns out to be a rather difficult learning problem.
Nevertheless, these problems will be solved eventually, and the technology will become available for others to use. It took more than 20 years for chess programs to finally become a serious threat to the best players. It won't take that long before we see elite poker-playing programs, but it still might be a number of years before they participate in online games.
Of course, a practical program doesn't have to be as good as the best players -- it only needs to beat a game with average players in order to win money.
(3) Are bots playing in online games now?
I expect there are a few now, yes. Perhaps more than a few. But are they a threat? Probably not. Many of them will be losing players, at least for a while. Their authors will either lose interest, or have to invest a lot of time and effort to improve their programs.
If someone does succeed in writing a program that can grind out a small win, what difference should it make? It will be like any other solid player -- playing a conservative style (only good cards and good situations), and slowly extracting a tax from the weak players.
Look at it this way. Most people who play online poker lose money. That's an unavoidable mathematical fact. Considering the house cut (the rake), perhaps 30% of players can stay in the black, maybe less. Many of the losing players will lose slowly, so the cost is a fair trade-off for the entertainment value they receive. Some will lose much more rapidly, and they really shouldn't be playing at all (unless they happen to be independently wealthy).
Of the players on the winning side, most will only eek out a small win rate. A winning poker bot would just be another solid player at the table. Probably less than 10% of all players have enough knowledge and skill to win a significant amount of money, and I doubt there will be any poker programs in that category for quite some time.
Will the existence of good bots radically change online poker? I doubt it. Look at casinos (real and online) that offer the traditional gambling games like craps and roulette. Those games cannot be beaten -- there is no skill that can be applied to avoid losing in the long run. But that fact doesn't seem to harm the popularity of their business.
Instead of fearing bots, people should use them to help learn more about the game. Our research program is com
Why do you geeks keep crushing my webpages? :-)
on
Geeks and Poker?
·
· Score: 5, Informative
Yes, poker is a game for mathematically-oriented geeks. In fact, the game is undergoing a revolution, with the savvy young players overthrowing the old guard, because they simply have better tools in their toolbox. Understanding how the other player thinks is still absolutely essential to playing at the top level, but there are also many mathematical concepts (beyond simple probabilities) that are very important to poker strategy.
In the old days of the Internet (before AOL), the newsgroup rec.gambling.poker had an incredibly high signal to noise ratio. Good players shared their insights, and many of them went on to be major stars in the poker world. I was just down at the WSoP and met with several of them (old friends and new acquaintances, many world champions among them).
Television has suddenly made poker into a spectacle, and the growth in popularity has been spectacular. Online poker is also booming, with thousands of geeks fleecing the millions of players who have less knowledge about the game.
If you want to learn more about this great game, visit some of the links on the The University of Alberta Computer Poker Research Group home page. You will need to read a lot (especially the books by Sklansky and Malmuth), and practice a lot before you become a good player.
One good tool for providing endless hours of practice is the commercial version of our research programs, Poki's Poker Academy.
Now is a great time to have fun and augment your income playing poker.
A trivial upper bound on the number of chess positions is 64! / 32! = 4.82 x 10^53, but that ignores the fact that some pieces are the same (ie. indistinguishable from each other).
The old estimate used to be O(10^50), but that was later refined to O(10^44) [possibly by Victor Allis, but I'm not positive]. I looked at the counting problem for a few minutes, and 10^44 looks like it is in the right ballpark.
One estimate of the number of subatomic particles in the observable universe is O(10^85).
The estimated number of legal Go positions is O(10^170). A proof tree that requires only the square root of this number of positions would still be the size of the entire universe, even with a magical encoding of one position per subatomic particle.
Chess would be a lot easier, with an upper bound on the order of O(10^44) positions.
Go-Moku was solved several years ago. See: http://www.ics.uci.edu/~eppstein/cgt/gomoku. html
Go-Moku also has a large search space, but the first player can force a win with a series of direct threats. This is not the case for Go or chess.
Thanks for the mention. Poki probably plays better than the average casino player, but it still has a long way to go to compete with the best in the world.
You can now play against Poki (and other humans) on our web applet. Just go to the University of Alberta GAMES group web page and click on the red "Play Online" button in the Poker section. Have fun.
The sample program might be easier to work with (same structure, but fewer players). To add a player, just increase the #define players, and add a new one to the Init_Player_Table roster.
A few people have told me they had some ideas that might beat The Matrix. I guess I should have had it score 1001 out of 1000, just to drive the point home.:)
Slashdot Mirror
This notion is completely and utterly false. In fact, it is _spectacularly_ wrong.
:)
The strongest checkers playing entity in the world is the program Chinook -- vastly stronger than any human that has ever lived. It was written by my supervisor, Jonathan Schaeffer, who is a mediocre checkers player, at best.
The Othello program Logistello *crushed* the human world champion 6-0 in a 1997 match. It's author, my friend Michael Buro, claims to be a weak Othello player.
For the game of Lines of Action (LoA), I wrote a program called Mona that won the de facto world championship in 2000, and has won every game it has ever played against the world's best human players. I don't play LoA at all. (More than once I questioned a choice of Mona's, only to discover that my preferred move was, in fact, illegal.
I know a lot about poker, but that could actually be a hindrance to writing a world-beater program. Finding the best algorithmic solutions to a problem is not based solely on the personal knowledge the programmer has about the domain.
- Darse.
http://games.cs.ualberta.ca/poker/
Actually, we did the multi-player game about eight years ago, and eventually produced a program that is better than an average human player (it has won consistently against humans on our online server for tens of millions of games). It's not nearly as good as the best human players though (and won't be any time soon). The program is available as part of the poker training software "Poker Academy" (http://www.poker-academy.com/poker-software/).
Although the multi-player game is harder in theory, in practice the heads-up game turns out to be tougher, because the amount of tricky play (bluffing and trapping) is much higher for 1-on-1.
There will likely be a multi-player tournament as part of next year's AAAI competition. There might also be a competition for heads-up No Limit Hold'em (or it might be added in 2008).
- Darse.
http://games.cs.ualberta.ca/poker/
I am a member of the Alberta team.
The article did not explain this part of the competition very well. The bots did not have access to any hidden information. The opponent's cards were only revealed at a showdown.
Here's how it works. A mini-match (1000 games) was played, with all of the cards recorded. Then a completely separate mini-match was played with the same cards, but with the positions reversed. This is possible because fresh copies of the programs can be started with a clean slate, having no memory of the previous match. (In fact, the two halves of the mini-match aren't even played on the same computer). Many of these duplicate matches were then played (40 for the fast competition, 12 for the slow competition) between each pair of players.
It is essential to run the matches in duplicate, in order to equalize the opportunities each side gets. The natural fluctation (variance) due to luck is huge in poker, making it very difficult to separate the signal from the noise. The problem is much worse than most people imagine, making accurate measurement of performance a sticky problem. The duplicate matches go a long way toward reducing that variance, and revealing the true long-term expectation.
[On a related note, I created a technique for direct assessment of poker decisions, which cuts away much of the noise. It is described in detail in my PhD thesis, which should be available from the CPRG website (http://games.cs.ualberta.ca/poker/) in September. A detailed analysis of the AAAI matches will also be available.]
Incidentally, there are a lot of incorrect statements being made in this thread. See the post titled "Some Actual Factual Information" for links to some of the original sources.
- Darse.
Yes, that comment is cracked. It was made by one of the "skeptics", but they are either clueless, or they're in denial. (Perhaps it is the official position of one of the major online poker rooms, who want the whole discussion to quietly go away [and cigarettes don't hurt people, either -- Philip Morris]).
Writing an interface to play online is not especially difficult. I'm sure dozens of people have done it independently, if not hundreds.
Writing an AI that can win enough to beat the rake is a lot tougher. A sharp programmer with some knowledge of poker could probably do it, but her efforts might be spent a lot more profitably on something completely legit, that brings value to many people.
- Darse. (hey look moderators, it's the guy in the story!:)
Here is an excerpt of my e-mail exchange with Mike Brunker (the author of the MSNBC article) prior to our phone interview. It might provide some interesting information on the topic.
- Darse.
[begin excerpt]
(1) It is not easy to write a good poker-playing program.
It took us (the Computer Poker Research Group at the U of A, http://games.cs.ualberta.ca/poker/) a few years to develop a program that could win consistently in higher-level games against opponents who took the game seriously. It has been successful against human players of average skill for many years now, but it is the only known program that can make that claim.
We operate a free poker server where people can play against our bots. Hobbyist programmers can also have their programs connect to the server and play in those games, and more than a hundred programs have participated over the past few years. None of them has come close to being a winning player, so it is clearly not a trivial task.
(2) Is it *possible* to write a very strong poker program?
Absolutely.
Poker is a challenging and rewarding field for research in Artificial Intelligence (AI). There are many aspects of the game that make it more difficult and more interesting than games like chess and checkers.
It isn't simply a matter of computing probabilities and other numbers. A good program has to *think* about the game in the right way. Master-level poker requires an understanding of how each opponent plays the game -- you must observe and adapt as you play, and that turns out to be a rather difficult learning problem.
Nevertheless, these problems will be solved eventually, and the technology will become available for others to use. It took more than 20 years for chess programs to finally become a serious threat to the best players. It won't take that long before we see elite poker-playing programs, but it still might be a number of years before they participate in online games.
Of course, a practical program doesn't have to be as good as the best players -- it only needs to beat a game with average players in order to win money.
(3) Are bots playing in online games now?
I expect there are a few now, yes. Perhaps more than a few. But are they a threat? Probably not. Many of them will be losing players, at least for a while. Their authors will either lose interest, or have to invest a lot of time and effort to improve their programs.
If someone does succeed in writing a program that can grind out a small win, what difference should it make? It will be like any other solid player -- playing a conservative style (only good cards and good situations), and slowly extracting a tax from the weak players.
Look at it this way. Most people who play online poker lose money. That's an unavoidable mathematical fact. Considering the house cut (the rake), perhaps 30% of players can stay in the black, maybe less. Many of the losing players will lose slowly, so the cost is a fair trade-off for the entertainment value they receive. Some will lose much more rapidly, and they really shouldn't be playing at all (unless they happen to be independently wealthy).
Of the players on the winning side, most will only eek out a small win rate. A winning poker bot would just be another solid player at the table. Probably less than 10% of all players have enough knowledge and skill to win a significant amount of money, and I doubt there will be any poker programs in that category for quite some time.
Will the existence of good bots radically change online poker? I doubt it. Look at casinos (real and online) that offer the traditional gambling games like craps and roulette. Those games cannot be beaten -- there is no skill that can be applied to avoid losing in the long run. But that fact doesn't seem to harm the popularity of their business.
Instead of fearing bots, people should use them to help learn more about the game. Our research program is com
Yes, poker is a game for mathematically-oriented geeks. In fact, the game is undergoing a revolution, with the savvy young players overthrowing the old guard, because they simply have better tools in their toolbox. Understanding how the other player thinks is still absolutely essential to playing at the top level, but there are also many mathematical concepts (beyond simple probabilities) that are very important to poker strategy.
In the old days of the Internet (before AOL), the newsgroup rec.gambling.poker had an incredibly high signal to noise ratio. Good players shared their insights, and many of them went on to be major stars in the poker world. I was just down at the WSoP and met with several of them (old friends and new acquaintances, many world champions among them).
Television has suddenly made poker into a spectacle, and the growth in popularity has been spectacular. Online poker is also booming, with thousands of geeks fleecing the millions of players who have less knowledge about the game.
If you want to learn more about this great game, visit some of the links on the The University of Alberta Computer Poker Research Group home page. You will need to read a lot (especially the books by Sklansky and Malmuth), and practice a lot before you become a good player.
One good tool for providing endless hours of practice is the commercial version of our research programs, Poki's Poker Academy.
Now is a great time to have fun and augment your income playing poker.
- Darse.
( hey look moderators! it's the actual guy! :)
You heard wrong.
A trivial upper bound on the number of chess
positions is 64! / 32! = 4.82 x 10^53, but that
ignores the fact that some pieces are the same
(ie. indistinguishable from each other).
The old estimate used to be O(10^50), but that
was later refined to O(10^44) [possibly by
Victor Allis, but I'm not positive]. I looked
at the counting problem for a few minutes, and
10^44 looks like it is in the right ballpark.
- Darse.
It is unlikely that 19x19 Go will ever be solved.
. html
One estimate of the number of subatomic particles
in the observable universe is O(10^85).
The estimated number of legal Go positions is
O(10^170). A proof tree that requires only the
square root of this number of positions would
still be the size of the entire universe, even
with a magical encoding of one position per
subatomic particle.
Chess would be a lot easier, with an upper bound
on the order of O(10^44) positions.
Go-Moku was solved several years ago. See:
http://www.ics.uci.edu/~eppstein/cgt/gomoku
Go-Moku also has a large search space, but the
first player can force a win with a series of
direct threats. This is not the case for Go or
chess.
- Darse.
You can now play against Poki (and other humans) on our web applet. Just go to the University of Alberta GAMES group web page and click on the red "Play Online" button in the Poker section. Have fun.
- Darse.
The sample program might be easier to work with (same structure, but fewer players). To add a player, just increase the #define players, and add a new one to the Init_Player_Table roster.
A few people have told me they had some ideas that might beat The Matrix. I guess I should have had it score 1001 out of 1000, just to drive the point home. :)