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

[jesse8888]

Solving the entire game tree for chess is impossible, or rather cannot be done in less time than the currently accepted age of the universe. This was explained to me in college by a pretty smart professor, and I'll try and see if I can simulate his numbers...or better yet, look it up on Wikipedia:

http://en.wikipedia.org/wiki/Shannon_number

Basically, there are 10^80 or so atoms in the universe, and the game tree for chess has around 10^120 possibilities. If you converted every atom in the universe to a supercomputer, each would have to solve 10^40 combinations. If it could perform 10^15 combinations per second, you would still need 10^25 seconds to solve chess. 10^25 seconds is 3.17 * 10^17 years. The universe is only about 10,000,000,000 (10^9) years old, so we're still off by a factor of a billion or so.

[jogsxyz]

[ QUOTE ]
[ 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.

[/ QUOTE ]

The program doesn't need to solve all those games. 90% and maybe over 99% of the continuations not illogical. Ignore those games. Only need to solve the lines which are in doubt.

[sixhigh]

Reducing complexity by the factor 100 doesn't change much. I reduced the number of 10^120 games by very much more, 10^60 for my argument. And even with this bold assumption and the even bolder assumption that Moore's law will hold for so long, we see it takes at least two centuries. Fwiw, I believe chess will never be solved completely for the reasons Jesse stated. I.e. we will never be able to give an optimal strategy for every position for both players.

And it's difficult to judge what a 'logical' continuation for a certain position is. For example Kieseritzky might have found most moves white made during the Immortal Game quite illogical, but still lost it.

[jay_shark]

They already have an approximate game theoretical solution to the limit hold em heads up player .

http://www.cs.ualberta.ca/~games/pok...hanson.msc.pdf

The University of Alberta has come up with "Spartan" which plays a tough game of limit hold em . After several thousand hands played , I'm slightly on the negative side and I consider myself to be a strong heads up player .

On the other hand , I can beat the nl hold em bots without looking at my cards; well , almost . There is a lot more work to be done for the nl hold em bots but I'm certain within a few years , the AI's will be able to compete with the upper echelon of players .

[TheGam]

[ QUOTE ]
They already have an approximate game theoretical solution to the limit hold em heads up player .

http://www.cs.ualberta.ca/~games/pok...hanson.msc.pdf

The University of Alberta has come up with "Spartan" which plays a tough game of limit hold em . After several thousand hands played , I'm slightly on the negative side and I consider myself to be a strong heads up player .

On the other hand , I can beat the nl hold em bots without looking at my cards; well , almost . There is a lot more work to be done for the nl hold em bots but I'm certain within a few years , the AI's will be able to compete with the upper echelon of players .

[/ QUOTE ]


Because by limiting yhe amount you can raise / bluff, it amplifies the importance of the cards you hold. Therefore the real odds and probabilites are much closer to there real value.

The richest players have mastered No Limit as it is no where near as reliant on the cards you are dealt. Which means you can still make money against poor player with no cards.

This is where computers will have real problems, but AI is moving on and it won't be long before there are very good CPU players. But it is not a complete logical solution like Chess or Checkers.

I personally believe that the things that require sheer power, like cracking encryption or solving chess, may not be solved as we know it. I believe either quantom physics or bioloigical computers may hld the answer. It will be the typical thing where every bosy goes WOW. If we keep the current computer model, we won't solve chess or strong encryption anytime soon

[jesse8888]

[ QUOTE ]

The program doesn't need to solve all those games. 90% and maybe over 99% of the continuations not illogical. Ignore those games. Only need to solve the lines which are in doubt.

[/ QUOTE ]

If 99.9% of the routes are illogical, then there are still 10^117 possibilities. Now we're off by a factor of one million instead of a billion. And remember, we've already turned every atom in the universe into a supercomputer and let the machines work for 10 billion years.

[DarkMagus]

[ QUOTE ]
[ 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.

[/ QUOTE ]http://en.wikipedia.org/wiki/Nash_equilibrium

[DrVanNostrin]

If HU limit hold'em with a cap was solved would people continue to play it (assuming it's well known that a solution exists)? It seems to me that this would ruin the game.

[HP]

[ QUOTE ]
[ 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..

[/ QUOTE ]
I'm aware there is a relatively simple algorithm to solve it. Too many combos to compute is what I meant, the govt does not have anywhere close the the computational power to solve it now

[Alan McIntire]

Years ago I read a relatively simple book on strategy, "The Compleat Strategyst", by John Davis Williams. I was disappointed to find that in most 2*2 games, and in a lot of other relatively simple games, your "best" strategy not only guarantees a minimum expected win rate, but this result is also guaranteed that same result to your opponent regardless of how poorly he played. In contrast, games like chess allow plenty of sub-optimum strategies for your opponent to pick and go wrong.

I don't know if there is a perfect strategy for a multiple player game. Such a strategy assumes that your opponents don't make bad plays, but several could act together, in effect colluding in their stupidity, to make a good play bad. Dan Harrington gave such an example in one of his books, where the top 4 finishers win an equal prize. 4 are tied at $4000 and 2 are tied at $1000.00.

A perfect mixed strategy for heads up Hold'Em poker must exist. I wonder if it would do better than break even against an expert, or your perfect strategy would make the game a coin flip. Are there any plays you should NEVER make which are sometimes employed by experts? This would be the only way you could have a positive expectancy.- A. McIntire