True or false? Chess will never be solved! why?

Sort:
TheGrobe

Bad doesn't necessarily mean losing.  The only way to truly know if you can prune the tree when trying to solve the game, is to solve the subtree -- which means you can't prune.

TheGrobe

Also, reducing the Shannon Number by anything short of quite a number of orders of magnitude won't make it any more manageable a problem.  Reducing it by a quarter doesn't even change the exponent.

x-5058622868

If perfect play is required for the solution, then wouldn't one bad move mean the solution isn't there?

TheGrobe

Sure, prove it's bad.

x-5058622868

Heh, i can't prove it's bad, but logically, those moves offer little to improve the game. Most people would agree, otherwise it would be played more often.

MrDamonSmith

I bet Borislav Ivanov can solve it if everybody would just give him a chance!

waffllemaster
varelse1 wrote:

False!

Saying chess will NEVER be solved is a general statement, bound to be derailed.

Already, we have 6-piece tablebases today (Every possible position solved containing 6 pieces or fewer) . In a few years time, we are expected to have 7-piece tablebases.

And  mankind's computing power will continue to grow exponentially. Barring any sort of cataclysmic disasters sending society back to the caveman days, 32-piece tabebases can be expected within the next 100 years.

Moore's law actually predicts (quite accurately) the number of transistors doubling not the performance of the computer doubling.  Also, this says nothing about how we'd be able to store the information calculated (which would be required for the solution).

There's also the other side of it which is the price of production exponentially rises as well.  So if you expect this to continue for 100 years not only are continued technological breakthroughs required but also we'll have to break the economic trend somehow.

And by the way, an interesting fact, the Bremerhann limit gives the maximum speed of a computer (by size) allowed in the universe.

TheGrobe
Sunshiny wrote:

Heh, i can't prove it's bad, but logically, those moves offer little to improve the game. Most people would agree, otherwise it would be played more often.

But unless you prove that they're losing, or suboptimal anyway, you can't be certain you've solved the game and the only way to prove it is exhaustively.

There are however some positions you can eliminate -- these are logically equivalent positions (such as postions that are reflections of each other along the edge between e/d files, or positions without pawns or castling rights that are reflections fo each other along the edge between the 4/5 ranks).  Solve one, and you've solved both.  I think this was a significant part of the strategy used to solve checkers.

TheGrobe
waffllemaster wrote:

Also, this says nothing about how we'd be able to store the information calculated (which would be required for the solution).

This is the crux of the problem right here.

Ziryab
TheGrobe wrote:
Sunshiny wrote:

Heh, i can't prove it's bad, but logically, those moves offer little to improve the game. Most people would agree, otherwise it would be played more often.

But unless you prove that they're losing, or suboptimal anyway, you can't be certain you've solved the game and the only way to prove it is exhaustively.

There are however some positions you can eliminate -- these are logically equivalent positions (such as postions that are reflections of each other along the edge between e/d files, or positions without pawns or castling rights that are reflections fo each other along the edge between the 4/5 ranks).  Solve one, and you've solved both.  I think this was a significant part of the strategy used to solve checkers.

And tablebases use such mirrors. Nonetheless, most new computers lack a harddrive (1.5 T) that can store the six-piece tablebases and still function.

TheGrobe

I think long diagonal reflections and 90° rotations without pawns or castling should also work.

x-5058622868
TheGrobe wrote:
Sunshiny wrote:

Heh, i can't prove it's bad, but logically, those moves offer little to improve the game. Most people would agree, otherwise it would be played more often.

But unless you prove that they're losing, or suboptimal anyway, you can't be certain you've solved the game and the only way to prove it is exhaustively.

There are however some positions you can eliminate -- these are logically equivalent positions (such as postions that are reflections of each other along the edge between e/d files, or positions without pawns or castling rights that are reflections fo each other along the edge between the 4/5 ranks).  Solve one, and you've solved both.  I think this was a significant part of the strategy used to solve checkers.

True, an exhaustive search would need to be done to completely solve chess. The way i see it is, there are 20 problems and a solution for each. Each of white's possible opening move is a problem to be solved. If white plays a3, the solution would yield either a win or a lose. Now, solving only one problem only partially solves chess. However, since it is white to make that decision, then the game would be considered solved, since the person playing white would always make that move. Knowing this, if a computer was set to solve only one line, 1/20 of the Shannon number, would that put it in a reasonable range to be solved?

Edit: Reasonable being in the range of possible, but nowhere near easy or soon.

edit2: I meant solving one problem that yields a win. If one problem was solved that yielded a win for white, then white would always make that move.

Edit3: By solution, i mean all possible lines would lead to either a win or loss for white.

tmodel66

In my lifetime, there were people who claimed that computers could never outplay the strongest GMs because of the GMs' inate intuitive skills.  Then, Big Blue proved that premise wrong.  In time, I believe chess could be "solved" (i.e.for any given opening move, it could be determined what the forced outcome would be with best play by both sides).

How long that "time" would take is a study in iteslf that could be calcluated/postulated by a mathmetician using Moore's Law.

TheGrobe

Just on a quick semantic note, there's an accepted terminology here:

  • Ultra Weak Solution: The knowlege of whether the game is won, lost or drawn from the starting position without the knowlege of how to accomplish it.
  • Weak Solution: An algorithm or strategy that always secures the best result for both sides from the starting position.  Basically, knowlege of what a game with perfect play from both sides looks like.
  • Strong Solution: An algorithm or strategy that always secures the best result for both sides from any position.  For chess, this is bascially the 32 peice tablebase.

I believe that the only one that we might find within reach (ever in human existence) is an Ultra Weak solution -- and that only on the back of a quantum computing breakthrough.

OnStar

The problem of storing all possible relevant chess positions is not the same as the problem of playing perfect chess (well, at least you could frame the problem that way).  If you could build a machine that could calculate fast enough, it would need to play perfect chess within agreed upon time controls.  Perhaps even a 3 days per move (for correspondence chess) would be allowable and still claim to have solved chess.

If calculations are fast and used, one would not need to store the whole chess evaluation tree.  Merely one line of play at a time.

An interesting question would be how many moves are there in the longest possible chess game.  (Assume one side will always take a draw when the option is available by the 50 move rule or the 3-peat rule.  Also assume both sides would take a checkmate if possible).

It is theoretically possible to fully evaluate a position in chess with only one continueous line of play in storage at any given instant. 

TheGrobe
tmodel66 wrote:

In my lifetime, there were people who claimed that computers could never outplay the strongest GMs because of the GMs' inate intuitive skills.  Then, Big Blue proved that premise wrong.  In time, I believe chess could be "solved" (i.e.for any given opening move, it could be determined what the forced outcome would be with best play by both sides).

How long that "time" would take is a study in iteslf that could be calcluated/postulated by a mathmetician using Moore's Law.

Those limitations were rooted in the imaginations of the claimants.

The limitations on solving chess are physical ones.

FancyKnight
tmodel66 wrote:

In my lifetime, there were people who claimed that computers could never outplay the strongest GMs because of the GMs' inate intuitive skills.  Then, Big Blue proved that premise wrong.  In time, I believe chess could be "solved" (i.e.for any given opening move, it could be determined what the forced outcome would be with best play by both sides).

How long that "time" would take is a study in iteslf that could be calcluated/postulated by a mathmetician using Moore's Law.

Moore's Law can't last forever.

Ziryab
TheGrobe wrote:

Just on a quick semantic note, there's an accepted terminology here:

Ultra Weak Solution: The knowlege of whether the game is won, lost or drawn from the starting position without the knowlege of how to accomplish it. Weak Solution: An algorithm or strategy that always secures the best result for both sides from the starting position.  Basically, knowlege of what a game with perfect play from both sides looks like. Strong Solution: An algorithm or strategy that always secures the best result for both sides from any position.  For chess, this is bascially the 32 peice tablebase.

I believe that the only one that we might find within reach (ever in human existence) is an Ultra Weak solution -- and that only on the back of a quantum computing breakthrough.

François-André Danican Philidor (1726-1795) offered a weak solution concerning gambits: they are drawn. Wilhelm Steinitz (1836-1900) offered a weak one concerning all other openings: again, drawn.

Everyone who has touched a chess piece since has disputed these solutions. 

BrightFuture
[COMMENT DELETED]
OnStar
TheGrobe wrote:

Bad doesn't necessarily mean losing.  The only way to truly know if you can prune the tree when trying to solve the game, is to solve the subtree -- which means you can't prune.

Perhaps you cannot prune any opening moves, but much pruning is possible.  For example, if I am evaluating move "36. Qa4" for white,  black has 12 possible replies.  In the first reply (e.g. "36.... Ra1") I find through thorough analysis leads to black having a mate in 4.  I can rule out move 36. Qa4 for white without evaluating the other 11 legal black replies.