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

Sort:
Irontiger
KickAssAndGiggle wrote:

What do you mean solved?

Let's say a computer program is eventually invented that achieves a rating of 3500. And no human can ever beat it (I would say if it plays 1,000 games against the top 10 GMs and loses none as black or white, that is proof of its unbeatableness, some may disagree with the 1,000 figure but that's up to an individual: there is a number that realistically constitutes proof).

Then you set it to play itself, and over 1,000 games, it's record is W0, L0, D1000

Is that solved?

It might be solved in that maybe the software will find in any position a move that doesn't change the evaluation. But you have no proof that it is solved.

Such a computer is essentially an oracle - you never caught it wrong, but how do you know it will never be?

watcha

I have never read the Wikipedia article on solving chess. However I have looked at many other sources, in particular those concerning the physical limits of computation. If you read my posts in this thread you can see that I have come to conclusions which are almost identical to that of the Wikipedia article.

Unless there is some unexpected turn in our understanding of physics ( I mean a dramatic development, for example the possibility of hypercomputation ) or we can come up with some magic formula which can predict the outcome of complex and general chess positions with certainty ( none of the above is likely ), the solution remains a tough problem.

Ziryab

"a tough problem"--this year's understatement superiore

SmyslovFan

Chess will be solved. It won't be solved in my lifetime, nor, I suspect, in the lifetimes of any current member's yet-to-be-born grandkids.

bigpoison

Sounds like something an Athenian might have said.

watcha

There is a blindfolded optimism out there that as the capacity of computers keeps growing at some point every computational problem that is finite will become solvable by computers.

I have to nail down that it is far from me to nurture such a blindfolded optimism.

Indeed I believe that there are problems which can never be solved by computers.

For example the below game ( chess on a 20 x 20 board ) is strictly unsolvable by computers:

The reason I believe that chess is solvable comes not from some kind of general optimism, but from the knowledge of the specifics of the problem.

Tapani
pfren wrote:
Tapani wrote:

Already sortof has, it is a forced draw after 75 moves currently. (Which proves your point). So the position with win in 200+ moves can never be legally won. 

Sorry, but this is tottally wrong.

There was an extension of the rule to 75 moves some twenty five years ago, but it did not last for long, and fell back to the normal 50 moves. The current FIDE rule is absolutely clear:

 

9.3

The game is drawn, upon a correct claim by a player having the move, if:

he writes his move, which cannot be changed, on his scoresheet and declares to the arbiter his intention to make this move which will result in the last 50 moves by each player having been made without the movement of any pawn and without any capture, or the last 50 moves by each player have been completed without the movement of any pawn and without any capture.

No I am right, and you are wrong (for a change). The point was to demonstrate that the limit of 50 moves is arbitrary indeed.

From the new 2014 FIDE rules:

9.6
   If one or both of the following occur(s) then the game is drawn: 
(a) the same position has appeared, as in 9.2b, for at least five consecutive alternate moves by each player.
(b) any consecutive series of 75 moves have been completed by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence.

 

A player can claim a draw after 50, and it is a forced draw after 75. Which is what I claimed.

And you are wrong about it being "absolutely clear" :p

Tapani

I think we will see, at least approximative solutions within our lifetimes (50 years).

Approximative meaning, using lots of heuristic like: "quiet position with rook up is a win" etc. 

watcha
Tapani wrote:

I think we will see, at least approximative solutions within our lifetimes (50 years).

Approximative meaning, using lots of heuristic like: "quiet position with rook up is a win" etc. 

You have to be careful about what you call an approximate solution, because Stockfish already fulfills your definition of an approximate solution. Stockfish knows all too well that a quiet position a rook up is a win and applies a bunch of other heuristics as well. So if Stockfish thinks that chess is a draw then chess is a draw in an approximate sense.

Tapani
watcha wrote:
Tapani wrote:

I think we will see, at least approximative solutions within our lifetimes (50 years).

Approximative meaning, using lots of heuristic like: "quiet position with rook up is a win" etc. 

You have to be careful about what you call an approximate solution, because Stockfish already fulfills your definition of an approximate solution. Stockfish knows all too well that a quiet position a rook up is a win and applies a bunch of other heuristics as well. So if Stockfish thinks that chess is a draw then chess is a draw in an approximate sense.

No, since stockfish only works with evaluations (win probabilities of some sort). A solution would be "moves e4, e4, c4, Nf3, g3 draws, other moves lose". Or when asked to demonstrate a win, it would show how to forcefully acheive a position that is heuristically deemed as a win (like a rook up in a quiet position).

watcha
Tapani wrote:

No, since stockfish only works with evaluations (win probabilities of some sort). A solution would be "moves e4, e4, c4, Nf3, g3 draws, other moves lose". Or when asked to demonstrate a win, it would show how to forcefully acheive a position that is heuristically deemed as a win (like a rook up in a quiet position).

It just occured to me that a quiet position with a rook up can be a draw, so if Stockfish knows all too well that it is a win, then Stockfish is wrong.

Stockfish actually happens to think it is a win:

This shows that heuristics can always leak.

Even if I accept that there are unshakable heuristics, these can not reduce the search space in a significant enough way.

watcha

Here are some topics you have to become familiar with if you want to give a long hard think to the solvability of chess:

1) The Turing model of computation

2) Physical limits of computation

3) Tree search with the minimax algorythm

4) Heuristics used to evaluate positions

5) Limitations of heuristics, especially fortress positions

If you don't have a basic understanding of any of the above topics, you have no chance to think about the solvability of chess in any meaningful way.

Tapani
watcha wrote:
Tapani wrote:

No, since stockfish only works with evaluations (win probabilities of some sort). A solution would be "moves e4, e4, c4, Nf3, g3 draws, other moves lose". Or when asked to demonstrate a win, it would show how to forcefully acheive a position that is heuristically deemed as a win (like a rook up in a quiet position).

It just occured to me that a quiet position with a rook up can be a draw, so if Stockfish knows all too well that it is a win, then Stockfish is wrong.

Stockfish actually happens to think it is a win:

 

This shows that heuristics can always leak.

Even if I accept that there are unshakable heuristics, these can not reduce the search space in a significant enough way.

That rook up was just an example. The intuition behind that was: the vast majority of all legal chess positions are "easy wins", even against perfect play. (Well I guess an engine heuristic is as good as perfect play when all moves are losing moves).

One scenario how chess might be solved is: 

Computers will reach human level intelligence one day. Maybe within our lifetime, maybe sometime after. Huge leaps are done in AI right now. Same way computers surpassed humans in chess, humans will be surpassed in _everything_. 

The first things the super-human AIs will do, is to create even smarter AIs. Until we in a short time reach what is the limit of computation. 

Once these super-super-super-human level intelligent computer will bite into a problem like solving chess, it will be the equivalent of billions of Fields medalist mathematician super GMs would spend a billions of years, in perfect cooperation, proving theorems and lemmas about classes of chess positions. Infinite creativity. Remembering every theorem. 

Maybe that is enough to reduce the search space enough to be brute-forceable? 

At least I think they should have a decent chance. I mean checkers was solved by a small team of humans, and a server farm ...

And if not, the AIs just might have a smarter approach... 

Tapani
watcha wrote:

Here are some topics you have to become familiar with if you want to give a long hard think to the solvability of chess:

1) The Turing model of computation

2) Physical limits of computation

3) Tree search with the minimax algorythm

4) Heuristics used to evaluate positions

5) Limitations of heuristics, especially fortress positions

If you don't have a basic understanding of any of the above topics, you have no chance to think about the solvability of chess in any meaningful way.

Points 1,3,4 and 5 are irrelevant. Point number two is relevant only for judging when your approach is even theoretically tractable.

Tyro_UK

Chess is just for fun!

watcha

The main point about computationally irreducible systems is, that you can't predict their state at a future time unless you play out their evolution step by step.

This is a very basic theoretical limitation: no amount of intelligence be it natural or artficial can overcome it.

Even shockingly simple systems, like the Rule 110 cellular automaton can be computationally irreducible.

Rule 110:

If you apply the above rule to create a new generation of cells from existing cells, the outcome is unpredictable and the evolution of the system can be used to perform universal computation ( that is: anything that can be computed, can be computed by a Rule 110 cellular automaton ). This is a relatively new development in science and it will take time for sink in and become common knowledge.

Chess behaves very much like a computationally irreducible system, so there is every reason to be skeptical about proving theorems about it, even if this is done by a very powerful intelligence.

watcha

Why the Turing model of computation is important?

Imagine that one claims that the halting problem can be solved by a powerful enough artificial intelligence. However this powerful artificial intelligence runs on a computer. Since the computer is a Turing machine, and Turing machines can't solve the halting problem of Turing machines, the artificial intelligence running on a Turing machine also can't solve the halting problem of Turing machines, no matter how high its IQ may be.

Tapani
watcha wrote:

Why the Turing model of computation is important?

Imagine that one claims that the halting problem can be solved by a powerful enough artificial intelligence. However this powerful artificial intelligence runs on a computer. Since the computer is a Turing machine, and Turing machines can't solve the halting problem of Turing machines, the artificial intelligence running on a Turing machine also can't solve the halting problem of Turing machines, no matter how high its IQ may be.

And how is this Turing stuff related to solving chess?

How is the "irreducible computation" related to solving chess? I fail to model a computational device on chess. Computation is transaction rules, in chess the players have choices.

Also, it sounds like you have not really understood the theoretical subtelties about Turing machines, computers and the halting problem.

I used to ask my students something like:

"Assume someone claims that a future super-super-computer (still Turing equivalent) will be able to tell you if your latest lab exercise computer program (non-interactive) will hang forever or terminate eventually. Would you believe that the super-super-computer could be able to do so?"

watcha
Tapani wrote: Assume someone claims that a future super-super-computer (still Turing equivalent) will be able to tell you if your latest lab exercise computer program (non-interactive) will hang forever or terminate eventually. Would you believe that the super-super-computer could be able to do so?

No. I don't believe.

Tapani
watcha wrote:
Tapani wrote: Assume someone claims that a future super-super-computer (still Turing equivalent) will be able to tell you if your latest lab exercise computer program (non-interactive) will hang forever or terminate eventually. Would you believe that the super-super-computer could be able to do so?

No. I don't believe.

Your computer is no Turing machine. Turing machine has unbounded amount of memory, while the memory in your computer is limited by n bits. Hence your program can visit at most 2^n states, and if a state ever repeats... it has hung. Otherwise it can run for at most 2^n steps, and will terminate thereafter.