10 years of Computer Chess

[Uri Blass]

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.

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.

I think that it is harder than you think because drawing moves are not the same and if the random player is unlucky to make a bad drawing move
then in the next moves he is not going to have multiple drawing moves to defend the position.

I also think that it is impossible to force a draw in 60 moves so even if the random player is lucky to have a draw position after 60 moves then it is still probably a loss for the random player.

I believe that the probability of the random player to draw a game against the perfect player is clearly lower than 1/(10^100)

Considering the fact that we have less than 10^8 seconds in a year
you are not going to find a single draw for the random player against the perfect player even after 10^10 years(that means less than 10^20 chess games even when we assume 100 games per second).

[Uri Blass]

By the way, a random legal move playing program cannot be compared to a monkey generating plays. A random perfect game is enormously more likely that even a couple of average sentences of grammatically correct and properly spelled English by random keystrokes.

Note that random perfect game between random players has clearly bigger probability than 1/10^100 because the sides can be lucky to
play into an early repetition but I assume that the perfect player is not going to allow early repetition against the random player because the perfect player does not choose a random perfect move by tablebases but a logical perfect move.

[Don]

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.

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.

I think that it is harder than you think because drawing moves are not the same and if the random player is unlucky to make a bad drawing move
then in the next moves he is not going to have multiple drawing moves to defend the position.

I also think that it is impossible to force a draw in 60 moves so even if the random player is lucky to have a draw position after 60 moves then it is still probably a loss for the random player.

I believe that the probability of the random player to draw a game against the perfect player is clearly lower than 1/(10^100)

Considering the fact that we have less than 10^8 seconds in a year
you are not going to find a single draw for the random player against the perfect player even after 10^10 years(that means less than 10^20 chess games even when we assume 100 games per second).

I was very conservative in assuming there would be 40 moves in every position and only 2 playable moves but I agree that 60 moves is probably not enough. I was trying to make a point however and it is so like you to try to come up with a precise value to refute me when it's not relevant at all to the point being made. It makes no real difference what reasonable assumptions you make, perhaps it adds 10,000 or 20,000 ELO to the calculation but I was not trying to get an exact number. My point is that a random player is not even close to having an infinitely bad ELO rating and that stands no matter how you estimate your numbers.

What I'm trying to illustrate is that very near the extremes of the rating scales (nearly always winning or nearly always losing) there are thousands of ELO points between drawing an extra game very billion years and measuring even a few thousand ELO with any accuracy requires more games that you will ever be able to play.

The principle applies at the scales we are interested in too and that is why I don't like Komodo to play programs hundreds of ELO weaker for rating purposes. A freak loss or draw (or lack of one that is due) has a huge impact on the rating.

Imagine trying to get an accurate rating playing a player 2000 ELO stronger than you but with a published rating. You play 100 games and lose every one which is quite likely. What is your rating? You must play thousands of games just to get a rough idea, where you could get the same rough idea by playing just a few games against a player about the same strength.

[Sven]

Chess is finite and a perfect player cannot have an infinite rating.

I agree on the expectation of diminishing returns "sooner or later". But in theory, yes, a perfect player can have an infinite rating if it is the only perfect player in the world and no other player knows how to draw or win against the perfect player, so all players lose against him. It is clear that this won't happen in practice but it *could* happen.

I think you are thinking of this incorrectly.

The ELO system assigns an ELO difference to 2 players based on their expected results unless you know in advance that one player will never lose you don't really know what that is. It has to be sampled to find out. When the difference is huge, it requires enormous samples before you can even talk about it.

I see nothing incorrect in what I wrote, while I still believe your view about the rating of a player winning 100% of all its games is incorrect. You probably misunderstood my reply. It was directed exactly at your statement "a perfect player cannot have an infinite rating" which is false as I'll show below.

What I meant in my previous post was the following: if we assume to have a "perfect player" which is an engine, let's call it "Houkomobka" , and we further assume that no other human or computer plays perfect chess at that time, and "Houkomobka" plays 10000 games against all the strongest opponents, and those opponents always make very small errors against "Houkomobka" but these are sufficient to lose all their games, then we get these results:

Code: Select all

Houkomobka +10000 =0 -0
StrongOpp1 +0 =0 -2000
StrongOpp2 +0 =0 -2000
StrongOpp3 +0 =0 -2000
StrongOpp4 +0 =0 -2000
StrongOpp5 +0 =0 -2000

I did not test what BayesElo, Ordo or EloStat would produce as ratings but any ratings derived from such results would be incorrect since neither 0% nor 100% results of one player can be mapped to a finite rating for that player. That follows directly from the logistic formula: "D = -ln(1/P - 1)", which is the inverse of "P = 1/(1+e^-D)", is undefined for both P=0 and P=1. (The same applies to the normal distribution as another possible underlying model of rating systems.) Rating calculation software might handle this case by introducing artificial ratings but that does not mean that these are correct.

The number of games does not matter here, it is already the case with +5 =0 -0, even then there is no correct rating. Any finite estimate is wrong. One common "compromise" solution is to add one or more "virtual draws" but this is really a compromise driven by the need to print a number instead of giving the correct answer "<infinite>".

Again: this won't happen in practice. But you, as well as I, were talking about something theoretical when mentioning a "perfect player", unless I misunderstood your statement.

Sven

[Laskos]

Chess is finite and a perfect player cannot have an infinite rating.

I agree on the expectation of diminishing returns "sooner or later". But in theory, yes, a perfect player can have an infinite rating if it is the only perfect player in the world and no other player knows how to draw or win against the perfect player, so all players lose against him. It is clear that this won't happen in practice but it *could* happen.

I think you are thinking of this incorrectly.

The ELO system assigns an ELO difference to 2 players based on their expected results unless you know in advance that one player will never lose you don't really know what that is. It has to be sampled to find out. When the difference is huge, it requires enormous samples before you can even talk about it.

I see nothing incorrect in what I wrote, while I still believe your view about the rating of a player winning 100% of all its games is incorrect. You probably misunderstood my reply. It was directed exactly at your statement "a perfect player cannot have an infinite rating" which is false as I'll show below.

What I meant in my previous post was the following: if we assume to have a "perfect player" which is an engine, let's call it "Houkomobka" , and we further assume that no other human or computer plays perfect chess at that time, and "Houkomobka" plays 10000 games against all the strongest opponents, and those opponents always make very small errors against "Houkomobka" but these are sufficient to lose all their games, then we get these results:

Code: Select all

Houkomobka +10000 =0 -0
StrongOpp1 +0 =0 -2000
StrongOpp2 +0 =0 -2000
StrongOpp3 +0 =0 -2000
StrongOpp4 +0 =0 -2000
StrongOpp5 +0 =0 -2000

I did not test what BayesElo, Ordo or EloStat would produce as ratings but any ratings derived from such results would be incorrect since neither 0% nor 100% results of one player can be mapped to a finite rating for that player. That follows directly from the logistic formula: "D = -ln(1/P - 1)", which is the inverse of "P = 1/(1+e^-D)", is undefined for both P=0 and P=1. (The same applies to the normal distribution as another possible underlying model of rating systems.) Rating calculation software might handle this case by introducing artificial ratings but that does not mean that these are correct.

The number of games does not matter here, it is already the case with +5 =0 -0,

Sven, there are two issues:
1) +5 =0 -0 give expectation values of 75% wins, 12.5% draws, 12.5% losses, and the finite rating accordingly even for +10000 =0 -0
2) It is possible that chess is of such nature that draws occur even in perfect-non-perfect players matches, more so if chess is really a draw.

even then there is no correct rating. Any finite estimate is wrong. One common "compromise" solution is to add one or more "virtual draws" but this is really a compromise driven by the need to print a number instead of giving the correct answer "<infinite>".

Again: this won't happen in practice. But you, as well as I, were talking about something theoretical when mentioning a "perfect player", unless I misunderstood your statement.

Sven

[Sven]

Sven, there are two issues:
1) +5 =0 -0 give expectation values of 75% wins, 12.5% draws, 12.5% losses, and the finite rating accordingly even for +10000 =0 -0

No. That is nonsense. Where did you take that from? Look up what I wrote: rating software computes a rating estimate even from that but the correct value is "undefined", for the reason I gave.

2) It is possible that chess is of such nature that draws occur even in perfect-non-perfect players matches, more so if chess is really a draw.

No objections but again, you did not read carefully what I wrote. I constructed one possible scenario without saying it were the most likely one, or even that others are impossible. You appear to be twisting my words. Don made a statement and I refuted it but not with the words you are suggesting that I used.

Sven

[Laskos]

Sven, there are two issues:
1) +5 =0 -0 give expectation values of 75% wins, 12.5% draws, 12.5% losses, and the finite rating accordingly even for +10000 =0 -0

No. That is nonsense. Where did you take that from?

Let see for binomials (wins and losses), for trinomials it's the same but more complicated. The likelihood of 9 wins and 1 loss (total of 10 games) is p_win^9*(1-p_win)^1. The expectation value of p_win is proportional to integral on p_win of p_win*p_win^9*(1-p_win) and is equal 5/6 and not 9/10. So, after these 10 tries with +9-1 result, you exepct after infinite number of tries to have a score of 5/6 and not 9/10.

Look up what I wrote: rating software computes a rating estimate even from that but the correct value is "undefined", for the reason I gave.

2) It is possible that chess is of such nature that draws occur even in perfect-non-perfect players matches, more so if chess is really a draw.

No objections but again, you did not read carefully what I wrote. I constructed one possible scenario without saying it were the most likely one, or even that others are impossible. You appear to be twisting my words. Don made a statement and I refuted it but not with the words you are suggesting that I used.

Sven

Ok, I though you said it's a must that perfect engine always wins against a non-perfect one.

[Sven]

Sven, there are two issues:
1) +5 =0 -0 give expectation values of 75% wins, 12.5% draws, 12.5% losses, and the finite rating accordingly even for +10000 =0 -0

No. That is nonsense. Where did you take that from?

Let see for binomials (wins and losses), for trinomials it's the same but more complicated. The likelihood of 9 wins and 1 loss (total of 10 games) is p_win^9*(1-p_win)^1. The expectation value of p_win is proportional to integral on p_win of p_win*p_win^9*(1-p_win) and is equal 5/6 and not 9/10. So, after these 10 tries with +9-1 result, you exepct after infinite number of tries to have a score of 5/6 and not 9/10.

We are not talking about the likelihood of a +X =Y -Z result. We are talking about the ELO rating one can derive from a +X =0 -0 result.

Furthermore, the ELO rating system is currently based on the logistic distribution, and was formerly based on the normal distribution, but not on the binomial or trinomial distribution. The latter may be your preferred theoretical model but it is not the base of ELO.

Look up what I wrote: rating software computes a rating estimate even from that but the correct value is "undefined", for the reason I gave.

2) It is possible that chess is of such nature that draws occur even in perfect-non-perfect players matches, more so if chess is really a draw.

No objections but again, you did not read carefully what I wrote. I constructed one possible scenario without saying it were the most likely one, or even that others are impossible. You appear to be twisting my words. Don made a statement and I refuted it but not with the words you are suggesting that I used.

Ok, I though you said it's a must that perfect engine always wins against a non-perfect one.

To be honest, I don't know how you were able to derive that from these words:

if we assume to have a "perfect player" which is an engine, let's call it "Houkomobka" Wink, and we further assume that no other human or computer plays perfect chess at that time, and "Houkomobka" plays 10000 games against all the strongest opponents, and those opponents always make very small errors against "Houkomobka" but these are sufficient to lose all their games, then we get these results:

Sven

[michiguel]

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.

[Don]

My calculation came out as between 30,000 and 50,000, agreeing perfectly with yours. And I believe it's probably a lot closer to 30,000.

It's hard to do more than just crudely estimate the chances a random player will beat a perfect player. We don't really know how many moves are "adequate" to hold the draw (and for this discussion I'm assuming that chess is s draw) on average and how many moves we are talking about for the branching factor. Even though the game may last for many moves those are low branching factor moves where much higher percentages of moves are adequate.

The style of play is important too, does the perfect player try to limit the number of adequate moves? I think for the sake of this discussion I would assume that the perfect player play an "adequate" move at random - with no consideration to style. If the perfect player is clever he can probably increase his rating substantially by playing provocatively of course. An adequate move is a move that wins if a win is possible, or a move that draws if only a draw is possible.

Don

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.