Sounds like something an Athenian might have said.
True or false? Chess will never be solved! why?
Sort:
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.
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
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.
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.
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).
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.
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.
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...
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.
Chess is just for fun!
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.
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.
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?"
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.
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.
I qoute from the Wikipedia article on Bremermann's limit ( http://en.wikipedia.org/wiki/Bremermann's_limit ):
"a computer with the mass of the entire Earth operating at the Bremermann's limit could perform approximately 10^75 mathematical computations per second."
Now, an Earth size super computer can perform 3.15*10^7*10^75 operations in a year. If you calculate a memory of what size has this number of states, you get 275 bits:
http://www.wolframalpha.com/input/?i=log%283.15*10%5E7*10%5E75%29%2Flog%282%29
Even if your lab computer has only 275 bits of memory, its halting problem can only be solved by a super computer of the size of the Earth in one year.
Since your lab computer has much more than 275 bits of memory ( at least Mbytes of memory ), the super computer of the size of the Earth will not be capable of solving its halting problem even during the entire age of the universe.
The age of the universe is 13.8 billion years ( 4.3*10^17 seconds ):
http://en.wikipedia.org/wiki/Age_of_the_universe
An Earth size super computer if it started working at the Big Bang, could finish by now solving the halting problem of a computer with 307 bits of memory:
http://www.wolframalpha.com/input/?i=log%284.3*10%5E17*10%5E75%29%2Flog%282%29
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.