Not to mention the fact that a proof of chess would have to disprove any other options. If you are going to say why line A is the only way to win, or its just a draw, you still have to show why every other possible line is not.
A proof of chess requires brute force. This only happens with quantum computing.
Things are not that simple :)
Quantum Computing is not proven to be superior to Classical Computing. The most likely (and the only known for sure) benefit is a square root speedup, not enough to solve chess :)
Regarding maximum Elo, it doesn't really matter, as Erik pointed out it is the Elo differences which matter. It doesn't measure the absolute strength, even comparing Elo ratings from different eras is rather tenuous because of inflation.
chess will be solved by computers within 15 years, not by calculating all the possible positions, but by having AI strong enough to use fast calculation to understand positional chess and how to slowly build up advantages
I think that the sentence "chess will be solved" means that we will know the result of the game from every possible position, with the best play of course. And that can't be done by positional play, but by calculating every line right to the checkmate or draw in every possible position. What I'm trying to say is that they probably will make an engine that will know what a knight outpost is and similar things. But solving chess is something else that can't be done by positional play.
Wikipedia is a poor source, but anyway: http://en.wikipedia.org/wiki/Solved_game
Quote: "The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on one or both sides."
See also: http://en.wikipedia.org/wiki/First-move_advantage_in_chess#Solving_chess
Quote: "It is thus theoretically possible to "solve" chess, determining with certainty whether a perfectly played game should end in a win for White, a draw, or even a win for Black. However, according to Shannon the time frame required puts this possibility beyond the limits of any feasible technology."
This is what I had in mind and I think this is the original meaning of the sentence "this game is solved".
But I agree with you in a way you are thinking about it. Until engines only calculate lines and look at the material advantage, there will probably always exist some positions (closed in particular) that will give an engine small winning chances against top players.
Computers' extremely good calculation sometimes gives the illusion that they have plans. But their "plans" are based on if they can get some advantage by a certain sequence of moves 15 moves later. Besisdes, teaching them positional chess would contradict their calculation so it wouldn't know what to rely on, but it may not even be possible to teach it positional chess.
I'm not really sure what makes you think it is only a square root speedup when it is exponential. Which is enough to solve chess.
The other day I was looking at the top chess engine ratings in awe. 3238, Deep Rybka 3's rating as of September 26, 2008
Kasparov was in awe twelve years ago whats taken you so long, I guess the only restriction is the method of grading calculation, chess.com beat a patzer add a point, well the rating would be infinite, adding 200 for the fide to uscf conversion hardly seems of significance, has anyone beaten one of the major software programs in the last few years I've long since stopped trying.
Exponential would be enough to solve chess, but quantum computing doesn't provide an exponential speedup.
ok to be more concise in order to avoid derailing the thread, some quick facts:
1) The root speedup has been proven to be possible in Grover's Algorithm.
2) Quantum Computing cannot solve a single problem, which is known (proven) to be exponentially hard (or even for a class of problems where it is unknown if the optimal solution is exponential or polynomial)
3) The only case where QC has provided an exponential speedup is factoring, Shor's algorithm. Saying that QC provides exponential speedup is however rather tenuous mainly because factoring is not proven to be a hard problem, it may well be the case that we haven't found an efficient classical algorithm for it yet and the problem itself is not an inherently hard problem (*).
4) There exist tasks which QC cannot tackle as good as classical systems do.
(*) There even exist "hints" that factoring may be efficient in principle and just no public algorithm exists.
So TLDR: QC is not an exponential boost of the classical model. In most cases it can offer something more (like a root speedup) but it cannot solve problems which are proven to be exponentially hard. The right way to pose this, is that QC has its own complexity structure, which in some cases can offer (root) speedups BUT it in this structure "hard" classical problems are not collapsed into something which is efficient.
if you want to learn more on QC, PM me, I'll be happy to help.
hess will be solved by computers within 15 years, not by calculating all the possible positions, but by having AI strong enough to use fast calculation to understand positional chess and how to slowly build up advantages
As of today, chess engines don't 'understand' chess at all.
All they do in a given position is sift through the game tree from there to find the best position. They decide which positions is best on the basis of an evaluation function. That function is entirely pre-programmed by humans.
Its the evaluation function (among some other things) that makes rybka 3 so incredibly strong. But it has nothing to do with the chess engine 'understanding' the position. It just applies the same evaluation function given by humans on every position at the end of its search tree.
The reason that chess can't be solved by a good evaluation function (which is the closest thing to 'positional understanding' built into chess engines) is that the evaluation function is bound to be imperfect. Not only is it man-made, it is also the same for every position while there will always be exceptional positions where common rules don't hold.
For example, there could be one perfect game where the side with the doubled pawns and the knight on the rim has the perfectly winning endgame. But if the chess program reaches that position at the end of its search tree, it will conclude that the position is bad and it will not play for it.
The computer could only know such positions are good if it actually calculated all the way through. And that is not feasonable on practical grounds.
Learn to read. I said that AI would make computers actually understand positions, just like AI is going to let computers understand a lot of other things.
I read your post. I just wasn't prepared to meet someone who makes up his own dictionary. There is a very clear definition of what a 'solved' game is, you can read it following the links of other people here who have been less lazy than you in their use of terminology.
Following commonly accepted terminology:
Any 'understanding' of chess that leads to best play for every positions in the gametree must be a summary of the gametree, otherwise you simply can't know that you are playing best moves always. So Chess would have been solved by calculating everything possible game.
If your 'understanding' could potentially ever lead to imperfect play in even only one situation, your understanding is imperfect. You haven't 'solved' Chess.
Following your personal terminology:
"i consider chess to be solved when it is impossible for a human to draw against a computer"
What are you saying? Impossible means it can't be done ever.
So that would still mean the engine would have to play best moves always (which can only be guaranteed if it all possible games have been calculated, still disqualifying ´understanding´ as a solution over ´brute calculation´.)
Even if the engine played best moves always, I still think humans could draw against it:
A) Chess is a draw with best play - the human can always potentially draw in every game.
B) Chess is 1-0 or 0-1 with best play - Assuming perfect play the human can never draw from the losing colour. The human can potentially win from the other side. (and likely draw, since it seems unlikely that every possible non-winning move during the game must be a loss.)
So basically, humans can always draw against even a perfect engine, unless chess isn´t a drawn game and the human never gets the winning side (highly unfair and nonsensical) or chess isn´t a drawn game but the winning side can´t force a draw with perfect play (highly unplausible)
Just how are chess engines rated? Do they have 2600 players play against it and see that Rybka performs with the same destruction as 1000 vs. 1600? or is it some other way? thx
if im not mistaken, chess engines are rated like any other chess playing thing. It plays other engines/humans and the result of the game with the factor of the opponents ELO determines their rating
I think the comp rating people just play the top 8 or so against each other. There are much weaker engines/hardware in the rating pool but they are long-retired.
That is my take from browsing their sites.
i consider chess to be solved when it is impossible for a human to draw against a computer
You are grossly misusing the word solved.
The sample area of chess is so big that even brute force by quantum computing is not going to solve it . the only way to solve it is just by some clever alogorithm.
By the way RC_Woods has given absoutely correct statistics.
Computers will solve Chess one day, soon. Fritz 55 or something. Whatever that means to the player I don't know. I'm guessing all it means is that you will not be able to win against a computer, even if your world champion, your only hope of taking points would be to play the perfect game as white to a complete draw. I'm not sure of the math involved in this or what the overall rating of such software would be. I'd guestimate it would be a nice big round figure like 10000.
I'm not sure of the math involved in this or what the overall rating of such software would be. I'd guestimate it would be a nice big round figure like 10000.
Rating of a software that can solve a game from any position would be infinite. Rating is a number that shows where you are compared to the others and such software would never lose to a human, if we assume that every game is drawn with perfect play. Actually, there is no point of putting this software on a rating list as they do with today's engines, because it can't compete with anyone, it is only a "game explorer" or "database" with sure game results instead of result percantages.
Even if another such software would appear (but they wouldn't play only each other), ratings of both of them would just go up infinitely. It may take them 500 years to get to 4000 rating points because of the draws, but they would probably win at least one out of n-games (who knows, maybe white has a forced mate in 518 moves after 1.e4 c5), so rating would just go up and up...
It's entirely possible that, even if chess were "solved", there would be no solution simple enough to be learnt by a human. You might be able to have a computer able to win (or draw) every game, but then what would be the point of playing against it ?
Kupov, you must be wrong.
A rating of 100,000 can't be real, which is not so hard to demonstrate.
I accept your premise that there are about ~ 10^120 possible games (actually you said 'board positions' but you must mean games since there are far fewer possible board positions). If Rybka played an engine rated 100,000 it should win only once every 10^242 games (!)* That this makes no sense at all should be pretty clear: if there are 'only' 10^120 possible games to play, rybka couldn't help herself but play a perfect game at least once every 10^120 games. (statistically speaking)
Actually, even a MONKEY making random but legal moves couldn't help itself but play a perfect game once every 10^120 games. And then we are assuming that there is only one way to play perfectly, or to say it differently: every move played was an only move.
So to conclude: Kupov, if you stick a rating of 100,000 on your wundah engine, math dictates that even a lobotomized playmate couldn't help herself but play at a rating of at least 52,000. And that, dear friend, is nonsense.
Chess isn´t that deep, and the world isn´t that crazy
The elo rating formula is as follows:
E(a) is the expected score of player A against player B. (for example 0,5 would mean you'd expect player A to win 5 in 10 games)
R(a) and R(b) are the ratings of both players. If Rybka has a rating of 3000 and Kupov's wundahkind engine has a rating of 100,000 then the rating difference is 97,000.
Therefore, the formula reads:
E(a) = 1 / 1+10^(97,000/4000) = 1 / 1+10^242,5 = ~ 1 / 10^242,5
Since even a monkey is forced to play at least one perfect game every 1 in 10^120 games, the very worst possible expected score would be something 1 / 10^120 which leads to a maximum rating difference of about 48,000. (which I think is still way to high to be realistic)
No I clearly meant board positions. Legal or illegal.
I think engines will reach their limit when they will be able to calculate every line right to the checkmate or draw. They will "solve" chess. But I think we won't live to see this happen. Technology is developing fast though.
I agree that engines will make chess a "solvable game", like tic-tac-toe. However, I disagree that we won't live to see this happen. I believe that in the next 20 years or so, engines will always make the correct move. I don't know about the 100,000 rating, however.