11

Suppose we have an extremely strong engine that happens to win every game it participates in even against the most powerful engines and players. If it continues to win every game, its rating (for example ELO) will grow indefinitely. But we do not have an infinite amount of time, so we will have to stop evaluating sometimes with some rating R. On the other hand, it feels wrong to stop at rating R because it is likely our engine will win its next game and get a rating R' > R. Moreover, we cannot give this engine a rating of infinity, because in theory it can draw or lose, it just hasn't yet faced such an opponent.

How would you find a rating approximation for such an engine?

2
  • 4
    If, as you say, rating will grow indefinitely, there's something wrong in the rating method. Once the gap in rating between the players becomes too large, all that can be said is that the winner has a rating that is ... 600+ (?) rating points higher. (I think Elo's rating method has 600). You should follow the recommended method of the rating method, whatever it, especially if there are requirements of minimum number of games with minimum number of different players. That is, I consider the premise of your question to be incorrect: you should not invent any new approximation methods.
    – user30536
    Jan 4 at 7:06
  • 3
    Similar, much simpler problem from statistics: you have a biased coin with an unknown parameter p, that lands on Heads with proba p and on Tails with proba 1-p. You want to estimate p by flipping the coin repeatedly. If p is close to 50%, then this is quickly going to give a very good estimation. But if p is close to 0 or to 1, ie if the coin almost-always lands on Heads or almost-always lands on tails, then estimating p precisely is going to be very difficult.
    – Stef
    Jan 4 at 13:08

5 Answers 5

7

I'd treat this as a Bayesian inverse probability problem. Per Laplace's rule-of-succession solution of the sunrise problem (see https://en.wikipedia.org/wiki/Rule_of_succession and https://en.wikipedia.org/wiki/Sunrise_problem), it follows that if an engine wins n out of n games, its rating should be estimated as if it played n+3 games, winning n+1, drawing one, and losing one - playing, of course, against the same pool of opponents. (A point of note: a chess game differs from a sunrise in that there are three possible outcomes, rather than just two. For the sake of simplicity, we'll assume the number of games with black and white pieces is equal.)

Using the example provided above, the rule-of-succession method returns an estimate of 2230 (1000 games), 3330 (1M games), and 3450 (2M games) - not that far off from Bayeselo. I'm not familiar with the method employed by Bayeselo and cannot say how mathematically sound it is, but in the end this is a kind of problem that doesn't have a "correct" solution because it hinges on one's choice of prior probability. In Laplace's approach, it is posited that, if we knew nothing about the history of sunrises, we should assume that the probability of Sun rising tomorrow is uniformly distributed between 0 and 1. Whether that assumption is applicable to a chess game between two players about whom we know nothing is anyone's guess.

(Additional note: I'm assuming here that the question is how to estimate Elo once n games have already been played, rather than when to stop playing more games. The answer to the latter question is significantly more complex as it obviously depends on additional factors.)

11

There're a few ways to do it:

  • Add 400 rating to the top opponent and take that as an approximation (used by USCF)
  • Add a draw for the engine against itself
  • Assign an infinite rating
  • Use linear approximation

By the way "win every game against the most powerful engines and players" is realistically not happening, because chess is a draw** and top engines on strong hardware guided by a human are already so close to perfect play that the great majority of all correspondence chess games are drawn.

**It's not proven that chess is a draw, but you won't find any top player seriously disagreeing with this assessment. See also this answer illustrating what things are like at the top level of play (world correspondence chess championship, which is stronger than both engines and humans alone).

6
  • 1
    We cannot know if (current engine + human) are close to perfect play, right? "Perfect play" is usually a term we define based on what the engine says, so with a drastically improved engine, it's entirely possible that the new engine would win every game. Jan 4 at 13:16
  • "Chess is a draw" is not a mathematically precise argument. In a hypothetical scenario, if the game of chess is solved then the side equipped with the winning algorithm will have the ultimate power assumed in the question.
    – polfosol
    Jan 4 at 13:39
  • "The side with the winning algorithm" doesn't exist if perfect play leads to a draw, though. And current indications are that, once solved, chess will be in that class. Jan 4 at 13:41
  • 10
    @polfosol: "Chess is a draw" is precise. That's not the problem. Game Theory says the exact same thing for Tic Tac Toe. The difference is that for Tic Tac Toe, there's proof. For chess, it's an unproven assertion, but it's an unambiguous assertion
    – MSalters
    Jan 4 at 13:41
  • @NathanMerrill engines are at the point where bookless games (i.e. games played from the opening position) on strong hardware at long time controls are almost always drawn. See e.g. this game: White (Leela) has a 300-elo rating advantage and is playing against an opponent with 30% of their time, and the game is still drawn. tcec-chess.com/#div=sft&game=12&season=21
    – Allure
    Jan 5 at 3:02
2

While there will be no concrete answer to this, there are few methods of approximation. We can play it against a 7 man tablebase, and for the sake of ELO rating we can assume that its strength in the middlegame or the opening is the same as the endgame. The number of losses that an endgame tablebase delivers to it (giving the borderline winning side to the tablebase and a blessed loss to the engine) determines its strength.

Another method we can use is the number of moves it takes to defeat the opposing engine. While not always correct, the general rule is that the more moves it takes to defeat the opponent, the weaker the player.

2
  • 3
    Presumably the super-strong engine is itself using an endgame tablebase internally. The assumption "We can play it against a 7 man tablebase, and for the sake of ELO rating we can assume that its strength in the middlegame or the opening is the same as the endgame." is inherently flawed, because the endgame is a solved problem, whereas the opening is an open problem.
    – Stef
    Jan 4 at 13:13
  • 1
    If the source code is known for the super strong engine, then you don't need to approximate at all. You can modify it to be weaker and play it against its weaker version. Keep on doing that and creating weaker versions until they match the next strongest engine.
    – birdo39
    Jan 4 at 19:44
2

According to bayeselo program if the best wins 1k games without loses and draws and setting the opponent rating to 1000, it will get 2092.

Rank Name:   Elo    +    - games score oppo. draws   win  loss  draw
   1 best:  2092  170   83  1000  100%  1000    0%  1000     0     0
   2 p1  :  1000   83  170  1000    0%  2092    0%     0  1000     0

1M games:

Rank Name:   Elo    +    - games score oppo. draws   win  loss  draw
   1 best:  3203  167   82 1e+06  100%  1000    0% 1e+06     0     0
   2 p1  :  1000   82  167 1e+06    0%  3203    0%     0 1e+06     0

2M games:

Rank Name:   Elo    +    - games score oppo. draws   win  loss  draw
   1 best:  3314  161   83 2e+06  100%  1000    0% 2e+06     0     0
   2 p1  :  1000   83  161 2e+06    0%  3314    0%     0 2e+06     0
0

You could let the engine play with a handicap (e.g. rook down).

Then, you need to calibrate how much rating delta a missing rook means. I saw some numbers that estimated one point of material to be a delta of 100 points.

This calibration could be done through self-play. Let the engine play against itself and see how much a rook is worth.

A downside of this handicap method is that it changes the game dynamics. Engines are not optimized for starting the game in an unusual position with a massive disadvantage. This can throw off some heuristics.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.