Inevitable mathematical solving of chess, and Limit / NL hold'em

[raze]

I'm sure everybody has heard about checkers being solved mathematically not too long ago. I'm sure we can mostly agree that there are computer programs out there that are sophisticated enough to beat hold'em games in some capacity as well.

I'd like to hear from some math-sharp minds in this forum; is it inevitable that chess will be solved like checkers? Finally, do you think all the possible situations and decisions in NL Hold'em (or even Limit) could be broken down and solved for a perfect strategy? Would your answer change based on 2-handed, or 3-11 handed play, or stack size considerations? I imagine such a program would have to include a database program like Poker Tracker but with more numerous and more sophisticated statistics which can be used to constantly fine-tune the computer's strategy?

Intuitively, chess and hold'em seem like they can and will be completely beatable by programming in the future, but I'm starting to ramble but I'd love to hear from some more mathematically experienced...

[HP]

from what little i know

chess, not any time soon. Too many combos

HU limit holdem with a cap, could be soon. We are only dealing with a trillion or so variables from memory

[Siegmund]

I expect to live to see all of the above.

HU holdem will go first. (Limit vs NL, cap vs no cap, will make a very tiny difference - maybe a few months between one and the other being solved. I wouldn't even speculate whether NL or limit will be solved first.)

Chess will take longer - maybe a lot longer - but more and more endgames are being catalogued, which leaves fewer and fewer midgames left to worry about (all you need is to show one path by which both players can force a draw, from those middle positions) ... then the dust will settle quietly as the remaining variations are sorted out, so that a list of fatal errors vs. harmless deviations can be made.

Three- or more-handed games require assumptions about coalitions to be made. Under the assumption that every player cares only about maximizing his own stack size without collusion, these will only take a few years longer than HU holdem, and probably happen well before chess does.

In the context of numbers of possible positions, HU holdem is among the easiest of as-yet-unsolved games, just a few orders of magnitude simpler than cribbage.

[jogsxyz]

In chess every move is a sub-set of the optimum move.
In poker this isn't true. Every newly dealt card changes
everything. Inferior plays are rewarded everyday, every
hour, and every minute. Playing optimal strategy
guarantees nothing.

[bigpooch]

CHESS
=====

I don't expect a solution to chess for at least a century
even though it is a finite two-person zero-sum game. There
are simply too many legal chess positions. The complete
database for endgames can be estimated below:

3 man Nalimov Tablebase...80 kB (measured)
3+4 man Nalimov Tablebases...30 MB (measured)
3+4+5 man Nalimov Tablebases...7.5 GB (measured)
3+4+5+6 man Nalimov Tablebases...1-2 TB (estimated)
3+4+5+6+7 man Nalimov Tablebases...200-600 TB (estimated)
3+4+5+6+7+8 man Nalimov Tablebase...40-180 PB (estimated)
...
Complete 3+4+5+...+30+31+32 man Nalimov Tatablebases...????


POKER
=====

Draw, 5-stud or draw-like or 5-stud-like games are more
easily solvable than hold'em. I agree that HU LHE is the
first "complex" kind of poker that will be solved and I'm
not sure that anything 3-handed will be solved anytime soon.
Also, there may already be strategies that have been
developed that are balanced (unexploitable) and very close
to the right level of aggression used in practice for HU
NLHE now.

Also, once PL is solved, it may not be big a leap to solve
NL, but again, for 10-handed NLHE, it's very unlikely to be
"solved" in the same way that checkers has been.

[JacksonTens]

[ QUOTE ]
chess, not any time soon. Too many combos


[/ QUOTE ]

Wrong. They have the formulas, just not the processing power. Well civilians dont anyway. Unless the US govt want to solve chess..

[sixhigh]

[ QUOTE ]
They have the formulas, just not the processing power.

[/ QUOTE ]

I guess you underestimate the complexity of chess. There are at least 10^120 possible games that can be played and there are roughly 10^50 possible positions. Even if we assume that by applying algorithms we can reduce those numbers to 10^60 and 10^25 it will remain unsolvable for a pretty long time.
Let's assume a computer this day can solve 10^8 different possible games within one second. I guess this number is way too big, but let's stick with it. Now we can apply Moore's law which states that the performance of computers doubles every 18 months. Then after 219 years a computer will be able to solve 10^52 different possible games within a second, meaning it will take 3 years to solve all 10^60 possibilities.

Those are rough numbers, underestimating the complexity of chess and overestimating the capabilities of computers - but we get the picture: At least two centuries until a complete solution for chess.

[TheGam]

I think I may be missing something here, but surely with any game where by you can see all of your opponents moves and pieces, there is an exact strategie and counter strategie to every move.

In something like Hold 'em whereby cards are hidden, then there is never an exact strategie that a computer can completely solve with the type of examples you have given for Chess and Checkers.

It can work out the likely hood of cards appearing, odds, probabilities, position etc. This just makes it a good micro limit player. If it plays the perfect strategie against even a slightly good player it will get wiped out. Why, cos we will know when it has a good hand or a bad hand.

So therefore it needs to learn how to mix up things up, adjust to peoples play etc. This is nothing like the complete mathmatical solving of Chess.

This requires artificial intelligence, which can be programed with the outcomes of millions of hands and draws its conclusion using weighted decisions. At the moment AI has been very impressive in certain tasks (Travelling Sales man), and absolutely aweful in other seemingly simple tasks for a human.

I have no doubt tho, that it will get to a level withing the near future where it can trade blows with a good player and not get white washed. But do not assume this has anything to do with it ever having solved Poker in a mathmatical sense, it is just playing really good, probabilty sound, variable poker, whilst learning everyone else's habits and tells.

It does not give it cart blanche way to win

[DarkMagus]

[ QUOTE ]
I think I may be missing something here, but surely with any game where by you can see all of your opponents moves and pieces, there is an exact strategie and counter strategie to every move.

In something like Hold 'em whereby cards are hidden, then there is never an exact strategie that a computer can completely solve with the type of examples you have given for Chess and Checkers.

It can work out the likely hood of cards appearing, odds, probabilities, position etc. This just makes it a good micro limit player. If it plays the perfect strategie against even a slightly good player it will get wiped out. Why, cos we will know when it has a good hand or a bad hand.

So therefore it needs to learn how to mix up things up, adjust to peoples play etc. This is nothing like the complete mathmatical solving of Chess.

This requires artificial intelligence, which can be programed with the outcomes of millions of hands and draws its conclusion using weighted decisions. At the moment AI has been very impressive in certain tasks (Travelling Sales man), and absolutely aweful in other seemingly simple tasks for a human.

I have no doubt tho, that it will get to a level withing the near future where it can trade blows with a good player and not get white washed. But do not assume this has anything to do with it ever having solved Poker in a mathmatical sense, it is just playing really good, probabilty sound, variable poker, whilst learning everyone else's habits and tells.

It does not give it cart blanche way to win

[/ QUOTE ]

A perfect strategy, requiring no adjustments to opponents, can guarantee an EV >= 0 game, for heads up matches. This is of course neglecting rake.

[TheGam]

[ QUOTE ]
A perfect strategy, requiring no adjustments to opponents, can guarantee an EV >= 0 game, for heads up matches. This is of course neglecting rake.

[/ QUOTE ]

That depends what a perfect strategie is defined as. A perfect mathmatical strategie will see you get annilated in Heads Up versus a good player. Particually in No limit. It almost tells the you what cards they are holding.

You need to need to play much more than odds to win heads up, even with no rake.