Two Plus Two Newer Archives Inevitable mathematical solving of chess, and Limit / NL hold'em
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#11
11-21-2007, 02:53 PM
 jesse8888 Senior Member Join Date: May 2007 Location: Missing bets with King high Posts: 833
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

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.
#12
11-21-2007, 03:55 PM
 jogsxyz Senior Member Join Date: Mar 2005 Posts: 1,167
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

[ 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.
#13
11-21-2007, 04:16 PM
 sixhigh Senior Member Join Date: Oct 2005 Location: Highway 61 Posts: 1,778
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

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.
#14
11-21-2007, 04:17 PM
 jay_shark Senior Member Join Date: Sep 2006 Posts: 2,277
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

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 .
#15
11-21-2007, 05:03 PM
 TheGam Junior Member Join Date: Jul 2007 Posts: 18
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

[ 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
#16
11-21-2007, 06:27 PM
 jesse8888 Senior Member Join Date: May 2007 Location: Missing bets with King high Posts: 833
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

[ 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.
#17
11-21-2007, 11:33 PM
 DarkMagus Senior Member Join Date: Jul 2007 Posts: 213
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

[ QUOTE ]
[ QUOTE ]
A perfect strategy, requiring no adjustments to opponents, can guarantee an EV &gt;= 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
#18
11-21-2007, 11:40 PM
 DrVanNostrin Senior Member Join Date: Sep 2005 Location: throwing my cards at the dealer Posts: 656
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

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.
#19
11-22-2007, 02:10 AM
 HP Senior Member Join Date: Oct 2004 Location: DZ-015 Posts: 2,783
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

[ 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
#20
12-01-2007, 07:52 PM
 Alan McIntire Junior Member Join Date: Oct 2007 Posts: 5
Re: Inevitable mathematical solving of chess, and Limit / NL hold\'em

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

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Two Plus Two     Two Plus Two Internet Magazine     The Two Plus Two Bonus Program     Special Sklansky Forum     About the Forums     MOD DISCUSSION     Test General Poker Discussion     Beginners Questions     Books and Publications     Televised Poker     News, Views, and Gossip     Brick and Mortar     Home Poker     Poker Beats, Brags, and Variance     Poker Theory     Poker Legislation Coaching/Training     Stoxpoker.com     DeucesCracked.com German Forums     Poker Allgemein: Poker in general     Strategie: Holdem NL cash [German]     Strategie: Sonstige     Internet/Online [German]     BBV [German]     Small Talk [German] French Forums     Forum Francophone     Strategie [French]     BBV [French] Limit Texas Hold'em     Texas Hold'em     High Stakes Limit     Medium Stakes Limit     Small Stakes Limit     Micro Stakes Limit     Mid-High Stakes Shorthanded     Small Stakes Shorthanded     Limit-->NL PL/NL Texas Hold'em     High Stakes     Medium Stakes     Small Stakes     Micro Stakes     Full Ring Tournament Poker     MTT Strategy     High Stakes MTT     MTT Community     STT Strategy     Tournament Circuit/WSOP Other Poker     Omaha/8     Omaha High     Stud     Heads Up Poker     Other Poker Games General Gambling     Probability     Psychology     Sports Betting     Other Gambling Games     Entertainment Betting     Money Making and Other Business Discussion Internet Gambling     Internet Gambling     Internet Bonuses     Affiliates/RakeBack     Software     Poker Site Software, Skins, & Networks 2+2 Communities     Other Other Topics     The Lounge: Discussion+Review     EDF     BBV4Life Other Topics     Sporting Events     Politics     Business, Finance, and Investing     Travel     Science, Math, and Philosophy     Health and Fitness     Student Life     Golf     Video Games     Puzzles and Other Games     Laughs or Links!     Computer Technical Help     Bin Sponsored Support Forums     RakebackNetwork     RakeBackDepot     RakeReduction.com Rakeback     PokerSavvy

All times are GMT -4. The time now is 10:44 AM.