Terms & Conditions

Internet Magazine

Non–US new players
Get five 2+2 books


Order Books
Book Translations
Forum Login
 
 
Expand All   Collapse All

 Two Plus Two 
2+2 Magazine Forum
Special Sklansky Forum
2+2 Pokercast
About the Forums

 General Poker Discussion 
Beginners Questions
Books and Publications
Televised Poker
News, Views, and Gossip
Brick and Mortar
Home Poker
Beats, Brags, and Variance
Poker Theory
Poker Legislation

 Coaching/Training 
StoxPoker
DeucesCracked

 German Forums 
Poker Allgemein
Strategie: Holdem NL cash
Strategie: Sonstige
Internet/Online
BBV
Small Talk
German Poker News

 French Forums 
Forum francophone
Strategie
BBV (French)

 Limit Texas Hold'em 
High Stakes Limit
Medium Stakes Limit
Small Stakes Limit
Micro Stakes Limit
Mid-High Short-handed
Small Stakes Shorthanded
Limit––>NL

 PL/NL Texas Hold'em 
High Stakes
Medium Stakes
Small Stakes
Micro Stakes
Small-High Full Ring
Micro Full Ring

 Tournament Poker 
Small Stakes MTT
High Stakes MTT
MTT Community
STT Strategy
Tournament Circuit

 Other Poker 
Omaha/8
Omaha High
Stud
Heads Up Poker
Other Poker Games

 General Gambling 
Probability
Psychology
Sports Betting
Other Gambling Games
Entertainment Betting

 Internet Gambling 
Internet Gambling
Internet Bonuses
Affiliates/RakeBack
Software

 2+2 Communities 
Other Other Topics
The Lounge: Discussion+Review
El Diablo's General Discussion
BBV4Life

 Other Topics 
Golf
Sporting Events
Politics
Business, Finance, and Investing
Travel
Science, Math, and Philosophy
Health and Fitness
Student Life
Puzzles and Other Games
Video Games
Laughs or Links!
Computer Technical Help
Sponsored Support Forums
RakebackNetwork
RakeReduction.com
Other Links
Books
Authors
Abbreviations
Calendar
Order Books
Books by Others
Favorite Links
Feedback
Advertising Information
Home
Posting Hints
Privacy Notice
Forum Archives

The 2+2 Forums

Before using this Forum, please refer to the Terms and Conditions (Last modified: 2/26/2006)

Be sure to read the   Two Plus Two Internet Magazine

This is an archive. The main forums are here

These forums are read only.


 
UBB.threads™ Groupee, Inc.

General Gambling >> Probability

Pages: 1 | 2 | 3 | >> (show all)
raze
no star


Reged: 11/07/05
Posts: 2561
Inevitable mathematical solving of chess, and Limit / NL hold'em
      #13036526 - 11/19/07 09:13 PM

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...


Post Extras: Print Post   Remind Me!   Notify Moderator  
HP
Carpal \'Tunnel


Reged: 10/22/04
Posts: 2783
Loc: DZ-015
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: raze]
      #13036834 - 11/19/07 09:32 PM

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


Post Extras: Print Post   Remind Me!   Notify Moderator  
Siegmund
Pooh-Bah


Reged: 02/01/05
Posts: 1850
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: HP]
      #13037339 - 11/19/07 10:06 PM

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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
jogsxyz
old hand


Reged: 03/30/05
Posts: 1167
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: Siegmund]
      #13037878 - 11/19/07 10:38 PM

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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
bigpooch
veteran


Reged: 09/17/03
Posts: 1330
Loc: Hong Kong
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: Siegmund]
      #13047688 - 11/20/07 04:19 PM

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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
JacksonTens
old hand


Reged: 05/03/05
Posts: 1169
Loc: Melbourne, Australia
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: HP]
      #13055327 - 11/21/07 01:02 AM

Quote:

chess, not any time soon. Too many combos





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


Post Extras: Print Post   Remind Me!   Notify Moderator  
sixhigh
Pooh-Bah


Reged: 10/23/05
Posts: 1778
Loc: Highway 61
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: JacksonTens]
      #13057684 - 11/21/07 05:57 AM

Quote:

They have the formulas, just not the processing power.




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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
TheGam
stranger


Reged: 07/17/07
Posts: 18
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: sixhigh]
      #13058219 - 11/21/07 07:39 AM

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


Post Extras: Print Post   Remind Me!   Notify Moderator  
DarkMagus
enthusiast


Reged: 07/10/07
Posts: 213
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: TheGam]
      #13059733 - 11/21/07 10:59 AM

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




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


Post Extras: Print Post   Remind Me!   Notify Moderator  
TheGam
stranger


Reged: 07/17/07
Posts: 18
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: DarkMagus]
      #13061309 - 11/21/07 12:55 PM

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.




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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
jesse8888
old hand


Reged: 05/29/07
Posts: 833
Loc: Missing bets with King high
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: TheGam]
      #13062067 - 11/21/07 01:53 PM

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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
jogsxyz
old hand


Reged: 03/30/05
Posts: 1167
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: sixhigh]
      #13063079 - 11/21/07 02:55 PM

Quote:

Quote:

They have the formulas, just not the processing power.




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.




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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
sixhigh
Pooh-Bah


Reged: 10/23/05
Posts: 1778
Loc: Highway 61
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: jogsxyz]
      #13063366 - 11/21/07 03:16 PM

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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
jay_shark
Pooh-Bah


Reged: 09/14/06
Posts: 2277
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: jogsxyz]
      #13063398 - 11/21/07 03:17 PM

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

http://www.cs.ualberta.ca/~games/poker/papers/Papers/johanson.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 .

Edited by jay_shark (11/21/07 03:41 PM)


Post Extras: Print Post   Remind Me!   Notify Moderator  
TheGam
stranger


Reged: 07/17/07
Posts: 18
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: jay_shark]
      #13064085 - 11/21/07 04:03 PM

Quote:

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

http://www.cs.ualberta.ca/~games/poker/papers/Papers/johanson.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 .





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


Post Extras: Print Post   Remind Me!   Notify Moderator  
jesse8888
old hand


Reged: 05/29/07
Posts: 833
Loc: Missing bets with King high
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: jogsxyz]
      #13065307 - 11/21/07 05:27 PM

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.




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.


Post Extras: Print Post   Remind Me!   Notify Moderator  
DarkMagus
enthusiast


Reged: 07/10/07
Posts: 213
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: TheGam]
      #13068830 - 11/21/07 10:33 PM

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.




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.


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

Post Extras: Print Post   Remind Me!   Notify Moderator  
DrVanNostrin
addict


Reged: 09/09/05
Posts: 656
Loc: throwing my cards at the deale...
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: raze]
      #13068916 - 11/21/07 10:40 PM

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.

Post Extras: Print Post   Remind Me!   Notify Moderator  
HP
Carpal \'Tunnel


Reged: 10/22/04
Posts: 2783
Loc: DZ-015
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: JacksonTens]
      #13070282 - 11/22/07 01:10 AM

Quote:

Quote:

chess, not any time soon. Too many combos





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



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


Post Extras: Print Post   Remind Me!   Notify Moderator  
Alan McIntire
stranger


Reged: 10/20/07
Posts: 5
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: TheGam]
      #13204881 - 12/01/07 06:52 PM

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


Post Extras: Print Post   Remind Me!   Notify Moderator  
EmmaDillema
journeyman


Reged: 10/18/07
Posts: 51
Re: Inevitable mathematical solving of chess, and Limit / NL hold'em [Re: Alan McIntire]
      #13207049 - 12/01/07 10:11 PM

chess wont be solved neither will nl

Post Extras: Print Post   Remind Me!   Notify Moderator  
Pages: 1 | 2 | 3 | >> (show all)



Extra information
0 registered and 0 anonymous users are browsing this forum.

Moderator:  Mat Sklansky, BruceZ, Mike Haven 

Print Topic

Forum Permissions
      You cannot start new topics
      You cannot reply to topics
      HTML is disabled
      UBBCode is enabled

Rating:
Topic views: 520

Rate this topic

Jump to

contact us 2+2 Publishing

Powered by UBB.threads™ 6.5.5


Message Boards and Forums Directory

Pages provided by ConJelCo