The maximum rating?

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. Astonishing! I also noticed that the ratings of the top chess engines have been increasing by an average of 67 ELO per year since 1986. I then began to wonder when this increase would level off.

Surely there is a limit?

I mean, how much better can they get?

Im curious to see what will happen. Please feel free to leave any comments or predictions.

anyone?

just remember - ratings are a measure of RELATIVE strength, not absolute numbers :)

I think the limit for a chess engines rating (as compared to humans, not other engines) would probably be astronomical.

Over 100,000 easily. There's going to be a point where no human will be able to compete with even the weakest computer engine.

There's just no way that would happen.  A player with a rating of 100,000 would have a 92% win record against a player of 90,600 who would have a 92% win record against a player of 90,200, who would win 92% of games against a 89,800, who would then win 92% of games against an 89,400 rating... you get the picture.  Chess just isnt that deep! 

Yes it is.

I think you could even start inventing numbers to accommodate the levels that computer chess engines will reach in comparison to human beings.

There will have to be an entirely seperate elo rating specifically for computers or else the numbers would be totally meaningless.

Of course this would only happen if chess engines and chess computers continue to be interesting to people. However computers have the potential to be so far above humans that rating humans and computers on the same elo system will be absurd.

How much room for improvement do you think there is?

Will it come to a point where a chess engine always plays the perfect move?

"This is how a computer looks at chess. It thinks about it in a world of "all possible moves," and it makes a big tree for all of those moves, like this:

In this tree, there are 20 possible moves for white. There are 20 * 20 = 400 possible moves for black, depending on what white does. Then there are 400 * 20 = 8,000 for white. Then there are 8,000 * 20 = 160,000 for black, and so on. If you were to fully develop the entire tree for all possible chess moves, the total number of board positions is about 1,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000, or 10¹²⁰, give or take a few. That's a very big number. For example, there have only been 10²⁶ nanoseconds since the Big Bang. There are thought to be only 10⁷⁵atoms in the entire universe. When you consider that the Milky Way galaxy contains billions of suns, and there are billions of galaxies, you can see that that's a whole lot of atoms. That number is dwarfed by the number of possible chess moves. Chess is a pretty intricate game!

No computer is ever going to calculate the entire tree."

Probably not, but there's room for nearly infinite computer improvement in the field of chess. Humans are by comparison severely limited.

Sorry for the triple post.

Edit: I posted this before I read Jared's post. Funny how it looks to be a direct response :P.

"No computer is ever going to calculate the entire tree."

No standard computer will, quantum computers don't get the same restriction. 

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.

Well 3200 computers play chess so good that I couldn't imagine it getting beaten by anything consistently at all. Even if a computer could calculate 100 moves ahead it's probably not necessary when the ones now already calculate so well, there's never really a blunder that takes over 20 moves to see the point.

How is computer rating calculated? Does the amount of moves it has have anything to do with it or is it just how much it can win?

That's nice, but irrelevant.  When I commented on your ratings comment I was assuming a complete tablebase of chess, where the engine picked the theoretically best lines for every single move and also those that were most difficult to counter.  The problem is not engine strength, but game depth.  Even a perfect engine would still give away draws to a less than perfect engine. 

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

P.S.

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)

Sure it's possible. All that super-engine has to do is find one winning line against each opening Rybka plays and it'll never lose or draw. Well, assuming that, once out of its opening book, Rybka will always play the exact same move in the exact same positions.

You wouldn't be playing out 10^120 games, you'd be playing out the same fifty or so games over and over again.

Now this argument breaks down when you stop assuming that this super-engine is just gonna play Rybka over and over...

What if Rybka plays the King's indian (from its opening book) and the super engine knows the refutation? Because there could very well be a refutation, just super deep.

well, if you wouldn't allow Rybka to repeat the games it has lost move by move it would eventually either find the one (multiple?) sound line(s) in the king's indian or it would indeed 'conclude' that the King's indian is not sound.

the point is that by the time it has played *every* possible move in the King's Indian it would still be a gazillion moves away from having played 10^120 games. the sound line is out there!

OTHER POINT:

Of course if the 'perfect engine' has solved chess, there are 2 scenario's:

A) Best play is a draw

B) Best play is a win for either colour

Now suppose the game is a win for white, of course it would be unfair nonsense to give the perfect engine white all the time. You would alternate colours.

So in fact if both engines would be perfect the scoresheet would be either

A) 1/2 - 1/2 - 1/2 - 1/2 - 1/2 - 1/2      (overall score 3-3 and counting..)

B) 1 - 0 - 1 - 0 -1 - 0  (overall score 3-3 and counting..)

So what if the other engine was insanely inferior?

Well, it would typically play scores like 0 - 0 - 0 - 0 etc.. But at least once every 10^120 games it must play perfect. In scenario A that means it scores at least 1/2 point every 10^120 games, in scenario B that means it scores 1/2 points every 10^120 games on average. After all, there's a 50 percent chance it had the must-lose side and a 50 percent chance it had the side that wins with best play.

Also, keep in mind that it hardly matters if the inferior engine scores 1, 2 or 0,5 points every 10^120 games. The point is it really must not score more than 1/10^122,5 points (ZEROOOOOHW) if the perfect engine was really rated 100,000...

not really.

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.

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.