Chess vs. Poker vs. Computer

[AlienBoy]

From the early days of computing, the ability of a computer to play chess has been held as a milestone event. And as we know, a few years ago a purpose designed computer from IBM indeed bested a best living human chess player in a match.

But is chess really the important milestone? It was considered the important computing milestone as chess was/is thought of as a deeply intellectual game - and indeed it is. However, it is a game of complete information, and thus it can be played by a computer using brute force, which is essentially what DeepBlue did in winning the match.

http://www.research.ibm.com/deepblue/home/html/b.html


But what about poker? Can a computer compete effectively against a human in a game of deception and incomplete information?

I don't think so. Even with an algorithm using game theory, I don't think there is enough information for a computer to make a brute force analysis that is ultimately +EV. Any skilled human playing this computer should be able to outplay it through manipulating pot odds, randomizing play, and exploiting the computer's plays.

Having said that - could the computer's play be randomized in such a way that the human is placed in a lose-lose situation? But then, wouldn't the human recognize that and place the computer in a lose-lose situation?

And I should mention that I speak mainly of NL - I think a computer could be +EV in a limit game for a number of reasons. But I think programing a computer to play NL effectively is an enormous challenge, and possibly more difficult than the challenge of beating Kasparov at chess.


Thoughts?


AB

[CityFan]

A computer could THEORETICALLY be programmed to play poker in a game-theoretically optimal way. That is, there would be no strategy that could beat it in the long run, <caveats>.

I say theoretically, because the amount of calculation involved might be enormous.

[almostbusto]

computers will be able to crush humans shortly. at both poker and chess. if they can't already (in chess it looks like computers have a slight edge right now).

computers might be lagging behind in poker because it isn't a hot research field. chess isn't so hot either but it used to be.

[George Rice]

Of course it's not the "computers" that are lagging, it's the people programming them. Very few people understand poker well enough to be qualified to write the software.

Backgammon, which is also a game of chance and very complex, has been programmed well enough to play at a world class level.

[gull]

Computers cannot play Go well. Yet computers are better than even the best Scrabble players in the world. It depends more on the game, and also how humans can quantify strategy.

[rubix]

Another important factor to consider is that poker is multiway. Not all multiway games have game-theoretic optima. It is likely that given any multi-player poker strategy S, there exists a set of (colluding) counter-strategies for which S has -EV.

[alphatmw]

[ QUOTE ]
Computers cannot play Go well. Yet computers are better than even the best Scrabble players in the world. It depends more on the game, and also how humans can quantify strategy.

[/ QUOTE ] that's because a computer can see every possible play whereas humans can only evaluate the plays they can find. this is different in poker, where every possible play is already known and can be analyzed.

[PantsOnFire]

My thought is that a computer program would need artificial intelligence to compete against a competent human poker player.

Limit holdem would be a lot easier to program into a computer than NL. I honestly can't imagine what it would take to "teach" a computer program to effectively play a NL holdem game.

I'm betting that we're a long way off at achieving anything close at this time. A whole facet of poker is reading the players. I don't see how a computer can do that given the current technology.

[rubix]

[ QUOTE ]

I'm betting that we're a long way off at achieving anything close at this time. A whole facet of poker is reading the players. I don't see how a computer can do that given the current technology.

[/ QUOTE ]

Actually, we've made some decent progress. For HU limit, the University of Alberta Computer Poker Research Group has created a program that can compete with expert humans. It is simply an enormous look-up table that represents an approximation to the game theoretic optimum. The look-up table reads something like, "If you hold XX, and the betting action thus far has been YYY, and the board is ZZ, then fold with probability f, call with probability c, and raise with probability r..."

Unfortunately, this approach does not extend to non-HU games. Also, for NL games, the look-up table size becomes unmanagable, making the problem intractable.

For non-HU games, the most promising AI architecture is roughly the following: maintain a belief state of the hidden information, update this belief state in response to opponent actions by Bayesian inference, and make decisions by approximating EV through Monte Carlo simulation. Poki uses this basic structure with modest results. Maven, the famous Scrabble program that beats world class humans, also uses this basic architecture, but the crucial difference between Scrabble and poker is the relative importance of the hidden information in making decisions.

I personally believe expert-level poker AI will be coming in the next decade.

[wazz]

Well there are bots succesfully making money (albeit small amounts) from pushbotting $22 and $33 turbos. As it stands most people who grind the lower limits full ring are very much playing mechanically, using basic reads, waiting for good hands then betting, and their opponents are generally so poor that this is a very +EV strategy, and there is no reason why a computer can't achieve this.

I think, though, you're wondering whether a computer would be able to beat the best players in the world. Right not, I don't think it's possible, and not for quite a while, though I'm pretty sure there is a branch of AI study that is incorporating game theory and as such could start beating the best in a short time.

However I'm pretty sure that is possible to succeed at a fairly high level without this, even now. With the amount of data out there, a computer could analyse all of the hands you've ever played and given any situation tell you what you've got to a certain amount of accuracy, and this would not be based on 'intuition' but raw data. As such a computer could play fairly optimally against you. Allow the computer to learn from it's mistakes..... you've got trouble. Allow the computer plenty of opportunity to randomize it's play.... I think the best players in the world would be able to beat such a computer but only through constantly (i.e. hand to hand) changing up styles, rotating through weak-passive, weak-tight, loose-passive, loose-aggressive on a completely random basis.