10 years of Computer Chess

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

User avatar
Laskos
Posts: 10948
Joined: Wed Jul 26, 2006 10:21 pm
Full name: Kai Laskos

Re: 10 years of Computer Chess

Post by Laskos »

michiguel wrote:
Don wrote:
carldaman wrote:
Random moves are much stronger than losing move because a random player will draw once in a while even against a perfect player.
Hi Don,
the above statement doesn't make sense, as random moves are more likely to be bad, leading to a loss sooner rather than later, even if some random moves may actually be good along the way.

Interesting idea about calibrating to zero based on random moves, though.

Regards,
CL
I don't understand your difficulty. A random move might be the best move on the board and thus 2 random moves in a row have a chance to be two best moves in a row. 3 is even less likely but still possible and so on. Therefore it is theoretically possible for a random player to play a perfect game, i.e. every move is best. I never claimed it was likely, but the context of the argument was about playing infinitely bad and that is almost impossible to do unless you simply resign on every move.

Chances are that a random player will play horribly but due to the laws of probability it will occasionally play good enough to draw even a perfect player.
Of course I understand how rare this is, but it's not impossible.
Exactly. In fact, we can make some extreme estimations to show it.

The probability to win is

Code: Select all

p = 1/(1+exp(-D/S)) 
where D is the delta elo, and S a constant that is about 180 to represent the scale we know.

So, given a probability we can calculate the ELO difference

Code: Select all

D = S * ln (p /(1-p))
But if the probability to win is veeeeery small, the above simplifies to

Code: Select all

D = S * ln(p)   or

D = 2.3 * S * log(p)  [Equation 1]
If one of the players play perfect, the probability to draw for the other is to play good enough moves every single time. If an average game lasts N moves and the average probability for "good enough" is "g", then

Code: Select all

p = g^N [Equation 2]
Let's ignore that g^N is the probability to score half a point rather than win, it won't make a big difference.

Combining Eq 1 and 2 we get

Code: Select all

D = 2.3 * S * log(g^N)

D = 2.3 * S * N * log(g)
since S = 180

Code: Select all

D = 414 * N * log(g)
So, if we have to make a perfect move out of 40 (g = 1/40) for N=100 moves,

we get that the maximum ELO compared to a random player is ~66,000 and that is very extreme.

A less extreme number could be g = 1/20 and N = 60 which would give a maximum ELO of ~32,000

Bigger number than those ballpark number obtained by "back in the envelope calculations" are impossible.

Miguel


Most people have a backwards model of how chess strength works. It has nothing to do with you, it's all about your opponent. You cannot "go after" the half point, you have to wait for your opponent to give it to you while not making a blunder yourself.

There is really no such thing as a "great" move. You are never in a losing position and muster so much brain power that you create a win. You hear language like that in chess books that romanticize chess sometimes, especially the older book that fawn over the old masters. But that is not how it works.

So for a random player to play a "good" game we really mean that it is "lucky" enough to avoid all the game theoretical half or full point losses.

I think a lot of positions have multiple moves that are (theoretically) the same so it's not quite so hard as having to find 1 move out of 40 for 50 or 60 moves in row. In some endings you are shuffling pieces and there are few bad moves - most of the moves are adequate. But in many position there is only 1 move that must be played to avoid throwing away the win or draw.

One theoretical truth here is that if you are losing, you cannot play a bad move - unless you define ALL moves as bad of course.

So the rule is that you don't play good chess even though we often say that. What we really mean is that you play less bad moves that other guy.
Yes, from the simplified logistic Delta = 400*log(g^N) = 400*N*log(g). For average game N=60, g=20 and Delta ~ 30,000 Elo points, the distance from the perfect player to a random mover. And another similar quantity from a random mover to a perfect loser.

Kai
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: 10 years of Computer Chess

Post by Sven »

michiguel wrote:A less extreme number could be g = 1/20 and N = 60
So how many games on average would the random player need to draw once against the perfect player, based on your g^N assumption?

And do you agree that in practice it is extremely likely that the perfect player will win all games against the random player, implying that the perfect player does not get a finite rating due to the 100% result?

The next question would be: what happens if you replace the random player by a "strong" player? You may choose a new value for "g". Is it 0.99? 0.9? 0.8? Do we know that even remotely? If I guess "0.8" then, with your N=60, chances for a draw are ~ 1.5e-06, so one draw in 666,666 games. If you guess "0.99" then it's 0.55, so one draw in two games. That's quite a difference. But we can't say that "0.8" (which is an arbitrary example of course, not my well-founded guess!) is impossible, so I still believe that a "perfect player" could in practice win all games even against strong opponents. Note that there are certainly many cases where a theoretical draw is insufficient for the non-perfect player since he almost never finds the correct way to draw, and that low practical drawing possibility affects your average value of "g".

But even if ~30000 ELO really were the maximum possible ELO rating for chess (which I doubt) then it would take ~540 years until that goal were reached with an improvement rate of 50 ELO per year.

Sven
User avatar
Laskos
Posts: 10948
Joined: Wed Jul 26, 2006 10:21 pm
Full name: Kai Laskos

Re: 10 years of Computer Chess

Post by Laskos »

Sven Schüle wrote:
But even if ~30000 ELO really were the maximum possible ELO rating for chess (which I doubt) then it would take ~540 years until that goal were reached with an improvement rate of 50 ELO per year.

Sven
You seem to be confused. Houdini's rating is about 28,237 Elo points, therefore it's not so far from 30,000 points of the perfect engine.

Kai
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: 10 years of Computer Chess

Post by Don »

Sven Schüle wrote:
michiguel wrote:A less extreme number could be g = 1/20 and N = 60
So how many games on average would the random player need to draw once against the perfect player, based on your g^N assumption?
1 / g^N is the odds, so g^N is the number of games on average.

And do you agree that in practice it is extremely likely that the perfect player will win all games against the random player, implying that the perfect player does not get a finite rating due to the 100% result?
No, we just showed you why a perfect player cannot win every game, and as rare as a draw is (and it's incredibly rare) it is enough to prevent the perfect player from being able to sustain a rating much over 30 or 40 thousand.

The next question would be: what happens if you replace the random player by a "strong" player?
Not much. A perfect player is probably only a few hundred ELO stronger than a top modern chess program - so the numbers won't change much. It will still be exceedingly rare that a random player will draw him.

You may choose a new value for "g". Is it 0.99? 0.9? 0.8? Do we know that even remotely?
Yes. 'g' is at least 1 / BF where BF is the branching factor. The BF is rarely over 40 and for most of the game, especially in view of the fact that we expect these games to be very long it will be much less. So a good estimate is 1/40 or 2/40. I think 2/40 is way more likely that 1/40 because in most positions there are a couple of playable moves. There are exceptions, in positions where one or both players are forced (such as recaptures, answers to checks and such) but there are many exception the other way where there are SEVERAL playable moves. So I believe 2/40 is a reasonable guess for the average and it's probably higher. That comes out to be 0.05 or 1 - 0.05 which is 0.95 which is I think what Miguel is looking for.

The point is that this doesn't change much of anything whether it's 0.05 or 0.07 or whatever, it still only means a few thousand rating points.


If I guess "0.8" then, with your N=60, chances for a draw are ~ 1.5e-06, so one draw in 666,666 games. If you guess "0.99" then it's 0.55, so one draw in two games. That's quite a difference. But we can't say that "0.8" (which is an arbitrary example of course, not my well-founded guess!) is impossible, so I still believe that a "perfect player" could in practice win all games even against strong opponents. Note that there are certainly many cases where a theoretical draw is insufficient for the non-perfect player since he almost never finds the correct way to draw, and that low practical drawing possibility affects your average value of "g".

But even if ~30000 ELO really were the maximum possible ELO rating for chess (which I doubt) then it would take ~540 years until that goal were reached with an improvement rate of 50 ELO per year.

Sven
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
Uri Blass
Posts: 10269
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: 10 years of Computer Chess

Post by Uri Blass »

Don wrote:
Sven Schüle wrote:

And do you agree that in practice it is extremely likely that the perfect player will win all games against the random player, implying that the perfect player does not get a finite rating due to the 100% result?
No, we just showed you why a perfect player cannot win every game, and as rare as a draw is (and it's incredibly rare) it is enough to prevent the perfect player from being able to sustain a rating much over 30 or 40 thousand.
What you showed is something that happens in theory.
The point is that practically humans are not going to live long enough to see the random player draw against the perfect player
and practically the result from their point of view is going to be 0% for the random player even after many millions of games.
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: 10 years of Computer Chess

Post by Sven »

Don wrote:
Sven Schüle wrote:
michiguel wrote:A less extreme number could be g = 1/20 and N = 60
So how many games on average would the random player need to draw once against the perfect player, based on your g^N assumption?
1 / g^N is the odds, so g^N is the number of games on average.
g = 1/20 => g^N = (1/20) ^ 60 = 8.7e-79
is the odds for the random player to draw against the perfect player. So one draw in 8.7e79 games.
Don wrote:
Sven Schüle wrote:And do you agree that in practice it is extremely likely that the perfect player will win all games against the random player, implying that the perfect player does not get a finite rating due to the 100% result?
No, we just showed you why a perfect player cannot win every game, and as rare as a draw is (and it's incredibly rare) it is enough to prevent the perfect player from being able to sustain a rating much over 30 or 40 thousand.
The perfect player cannot win every game out of 1.0e100 games. But he can win every game when given a realistic time frame of, say, one year. I don't say "he will" but "he can". You seem to imply that were impossible.
Don wrote:
Sven Schüle wrote:The next question would be: what happens if you replace the random player by a "strong" player?
Not much. A perfect player is probably only a few hundred ELO stronger than a top modern chess program - so the numbers won't change much. It will still be exceedingly rare that a random player will draw him.
Read again ... I wrote "replace the random player by a 'strong' player", you understood "replace the perfect player ...".

Sven
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: 10 years of Computer Chess

Post by Sven »

Laskos wrote:
Sven Schüle wrote:
But even if ~30000 ELO really were the maximum possible ELO rating for chess (which I doubt) then it would take ~540 years until that goal were reached with an improvement rate of 50 ELO per year.

Sven
You seem to be confused. Houdini's rating is about 28,237 Elo points, therefore it's not so far from 30,000 points of the perfect engine.

Kai
Are you kidding?
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: 10 years of Computer Chess

Post by Don »

Uri Blass wrote:
Don wrote:
Sven Schüle wrote:

And do you agree that in practice it is extremely likely that the perfect player will win all games against the random player, implying that the perfect player does not get a finite rating due to the 100% result?
No, we just showed you why a perfect player cannot win every game, and as rare as a draw is (and it's incredibly rare) it is enough to prevent the perfect player from being able to sustain a rating much over 30 or 40 thousand.
What you showed is something that happens in theory.
This isn't theory - it's fact.
The point is that practically humans are not going to live long enough to see the random player draw against the perfect player ....
That's not the point at all. The point is that you WILL draw (and this is not theoretical) once in a while and thus your rating is not only not infinite, it is not even that large (unless 30,000 is a big number for you.)

You seem to think the point is that you will never see such a draw in your lifetime and that is true but has nothing to do with this discussion. You have simply decided that it's a relevant point when in fact it's just some random fact that is irrelevant to this discussion.
and practically the result from their point of view is going to be 0% for the random player even after many millions of games.
Yes, after many millions of games there will almost certainly be no draws. I said right from the start that draws would be exceedingly rare so why is this so important to you?
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
User avatar
Laskos
Posts: 10948
Joined: Wed Jul 26, 2006 10:21 pm
Full name: Kai Laskos

Re: 10 years of Computer Chess

Post by Laskos »

Sven Schüle wrote:
Laskos wrote:
Sven Schüle wrote:
But even if ~30000 ELO really were the maximum possible ELO rating for chess (which I doubt) then it would take ~540 years until that goal were reached with an improvement rate of 50 ELO per year.

Sven
You seem to be confused. Houdini's rating is about 28,237 Elo points, therefore it's not so far from 30,000 points of the perfect engine.

Kai
Are you kidding?
Not quite, if 0 Elo points is the rating of the random mover, and 30,000 Elo points is the rating of the perfect engine, then the engines like Crafty or Houdini are at say 28,000 Elo points (maybe 25,000 or maybe 29,000, but let's assume 28,000). Just setting the material values and the goal that more material is better, together with one ply search, is giving a rating of maybe 25,000 Elo points, and the last 60 years were about getting the rating from 25,000 to 28,000 Elo points, with 30,000 Elo points being the strength of the perfect engine and 0 Elo points being the strength of the random mover.

Kai
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: 10 years of Computer Chess

Post by Don »

Laskos wrote:
Sven Schüle wrote:
Laskos wrote:
Sven Schüle wrote:
But even if ~30000 ELO really were the maximum possible ELO rating for chess (which I doubt) then it would take ~540 years until that goal were reached with an improvement rate of 50 ELO per year.

Sven
You seem to be confused. Houdini's rating is about 28,237 Elo points, therefore it's not so far from 30,000 points of the perfect engine.

Kai
Are you kidding?
Not quite, if 0 Elo points is the rating of the random mover, and 30,000 Elo points is the rating of the perfect engine, then the engines like Crafty or Houdini are at say 28,000 Elo points (maybe 25,000 or maybe 29,000, but let's assume 28,000). Just setting the material values and the goal that more material is better is giving a rating of maybe 24,000 Elo points, and the last 60 years were about getting the rating from 24,000 to 28,000 Elo points, with 30,000 Elo points being the strength of the perfect engine and 0 Elo points being the strength of the random mover.

Kai
zero is probably way too high for the random mover. But there is a way to perhaps get a rough idea of what this would give us.

We can build a random mover hybrid and then make versions of intermediate strength and rate them.

Here is a simple scheme to do exactly that:


To make a make, first score all the 1 ply moves and then add a random number between 0 and N-1 to each moves score and play the higher scoring one after doing this. If N is really large it's very close to random. if N is 1 it will play the same strength as a real 1 ply search.

So we can start with N = 1 and fine out how much we have to add to N to get 200 ELO for example. Let's say it turns out to be 40. The we repeat and try to construct a sequence of versions between random and fully non-random. If there is 30,000 ELO between them we would have to make an impractically large number of versions.

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.