A closer look at chess scalings (into the past)
6paulfchristiano
8Charlie Steiner
1hippke
4gwern
4paulfchristiano
2paulfchristiano
1hippke
3hippke
2paulfchristiano
1hippke
2Bucky
3hippke
1Bartlomiej Lewandowski
1hippke
New Comment
I'm confused about the top end of the graph. Shouldn't SF8 with the reference compute basically match the final datapoints? But it looks like you'd have to scale it up extremely far to get to such a high elo.
We're on SF14 now. Stockfish didn't even have neural net evaluation until SF12 I think.
I just checked, and SF8 is from 2016. So still slightly off, but makes more sense.
Yes, that's correct. It is slightly off because I manually set the year 2022 to match 100,000 kNodes/s. That could be adjusted by one year. To get an engine which begins its journey right in the year 2021, we could perform a similar experiment with SF14. The curve would be virtually identical, just shifted to the right and up.
I was reading about endgame databases and happened to note Thompson discussing a bit scaling of brute force search, and it 'asymptotic' or flattening. Ken Thompson, oral history, February 2005
...
Q: So at that stage how many plies was it [Belle] going and what kind of rating did it have?
Ken Thompson: It was going 8 full plies easily, the other one was probably going 6 and was easily master, probably 2300. I never worked for rating. You can squeeze rating points out by studying your opponents and booking up and taking away---put a punch of trap kind of stuff in. But I wanted to just play nice solid chess, so it was probably 2300.
Q: And I think at some point I recall you talking about the ratings compared to compute power and you had I think extrapolated for and about what kinds of compute power it would take to get certain improvements and ratings
Ken Thompson: Yeah...
Q: I can’t remember when that was, it must have been early ‘80s or something...
Ken Thompson: Yeah it was early ‘80s---It was asymptotic but it was in the high rise part of the asymptote so you can’t really tell whether---where it rolled over. But it would, certainly in that era you were gaining---for every doubling of horsepower you’d gain a hundred points. I came with some really fake-y back of the envelope calculations that said at around 12 or 13 ply you’d be world class. Maybe not---you’d compete for the world title, you may not win it but you’d be comparable.
Q: Presumably the ratings in some sense get a little less accurate at the very top I would think...
Ken Thompson: Yes, yes.
The WP article on Belle notes some of this in more detail and gives two refers, a 1983 and 1997 book. Quoting a bit (both are on Libgen and easy to acccess):
1983 says
Newborn [155] has suggested that if you double the speed of a brute force program, you will gain 100 rating points. If you assume a 5.5 branching factor, then a ply will yield 250 points. In the linear range of P4-P6 (the range observed by Newborn in existing programs) this relation holds. In the extended range of this experiment, ratings do not grow as fast as predicted. Any major conclusions about the experiment we leave up to the reader. Here are some of our observations that may be of help.
From [the book](https://cloudflare-ipfs.com/ipfs/bafykbzacebnknut4q77j4foxnybstbry5w3g5poigcqase47g4cryanhweags?filename=Monty Newborn (auth.) - Kasparov versus Deep Blue_ computer chess comes of age-Springer-Verlag New York (1997).pdf#page=132)
Thompson conducted two experiments in the late 1970s to study this issue. In his first experiment, he had one version of BELLE play a series of twenty games against an identical second version, except that one version, call it BELLE(P), searched to a depth of, say, P levels while the other, BELLE(P + 1), searched to a depth of P + 1 levels. The results of this experiment are presented in Figure 6.24a for 3 <= P <= 8. It shows, for example, that BELLE(3) won four of the twenty points against BELLE(4), and that BELLE(4) won five and a half of twenty points against BELLE(5). His second experiment, carried out shortly thereafter, was more extensive: for 4 <= P, Q <= 9 and for P ≠ Q, BELLE(P) played a twenty-game series against BELLE(Q). The results are presented in Figure 6.24b. Rather than relating rating improvement to the number of positions searched, Thompson related rating improvement to the depth of search, pointing out that an improvement of one hundred points for each doubling of speed was approximately equivalent to an improvement of 250 points for each additional level of search.
The main difference between the curve of ratings shown in Figure 6.23 and Thompson's results is that the relation between ratings and search depth appears to be almost linear to about 2500 while Thompson found that rating improvement drops off from linear at ratings above 2000 points. Certainly, eventually the curve approaches the limit imposed by perfect play but the question is how fast. Thompson evidently did not study deeper search depths because of the large amount of time required to obtain results.
[The next part discusses a different way to try to extrapolate based on differences in tree search choice which reminds me a little of Paul Christiano's counting argument/coincidence in Andy Jone's RL scaling paper.]
The descriptions here of flattening are suspicious, given the economizing on compute. It doesn't look like Thompson ever clearly revisited the topic later on than the '80s, or considered functional forms beyond increasing 1 ply at a time and expecting n ELO points. I would not be surprised if Belle continued scaling the same as Jones, and here again practitioners mistake a log or powerlaw for 'flattening out' (and thus futility compared to Bitter-Lesson-vulnerable-but-more-engineerable approaches).
I'm quite surprised by how far out on the Elo vs compute curve we already are by a million nodes/move. Is this the main "target platform" for stockfish, or are people mostly trying to optimize the performance for significantly smaller node counts?
(I'm wondering whether such strong diminishing returns are fundamental to the domain, or whether people are putting the most work into optimizing performance down at more like 100kNodes/sec.)
In another comment you wrote "In between is the region with ~70 ELO; that's where engines usually operate on present hardware with minutes of think time" which made sense to me, I'm just trying to square that with this graph.
Mhm, good point. I must admit that the "70 ELO per doubling" etc. is forum wisdom that is perhaps not the last word. A similar scaling experiment was done with Houdini 3 (2013) which dropped below 70 ELO per doubling when exceeding 4 MNodes/move. In my experiment, the drop is already around 1 MNode/move. So there is certainly an engine dependence.
OK, I have added the Houdini data from this experiment to the plot:
The baseline ELO is not stated, but likely close to 3200:
| Experiment | kNodes/move | ELO drop | ELO calculated |
| 4k nodes vs 2k nodes | 2 | 303 | 1280 |
| 8k nodes vs 4k nodes | 4 | 280 | 1583 |
| 16k nodes vs 8k nodes | 8 | 237 | 1863 |
| 32k nodes vs 16k nodes | 16 | 208 | 2100 |
| 64k nodes vs 32k nodes | 32 | 179 | 2308 |
| 128k nodes vs 64k nodes | 64 | 156 | 2487 |
| 256k nodes vs 128k nodes | 128 | 136 | 2643 |
| 512k nodes vs 256k nodes | 256 | 134 | 2779 |
| 1024k nodes vs 512k nodes | 512 | 115 | 2913 |
| 2048k nodes vs 1024k nodes | 1024 | 93 | 3028 |
| 4096k nodes vs 2048k nodes | 2048 | 79 | 3121 |
| Baseline | 4096 | 3200 |
The results look quite different for Houdini 3 vs SF8---is this just a matter of Stockfish being much better optimized for small amounts of hardware?
From what I understand about the computer chess community:
- Engines are optimized to win in the competitions, for reputation. There are competitions for many time controls, but most well respected are the CCC with games of 3 to 15 minutes, and TCEC which goes up to 90 minutes. So there is an incentive to tune the engines well into the many-MNodes/move regime.
- On the other hand, most testing during engine development is done at blitz or even bullet level (30s for the whole game for Stockfish). You can't just play thousands of long games after each code commit to test its effect. Instead, many faster games are played. That's in the few MNodes/move regime. So there's some incentive to perform well in that regime.
- Below that, I think that performance is "just what is it", and nobody optimizes for it. However, I think it would be valuable to ask a Stockfish developer about their view.
Is there a story behind the PC results 2008-2011 where they deviate from the fairly straight line?
Nitpick: There’s an issue with Magnus Carlsen’s ratings - he became a GM at 13 in 2003, not 21 in 2011 or in 2009 as shown in the graph (famously he was the second youngest ever GM at the time).
Oh, thank you for the correction about Magnus Carlsen! Indeed, my script to convert the timestamps had an error. I fixed it in the figure.
Regarding the jump in 2008 with Rybka: I think that's an artifact of that particular list. Similar lists don't have it.
Isn't ELO a reference metric that changes with time? I would assume that 2800 ELO in the 90s is a different level to today's 2800. Can we still make the same conclusions with that in mind?
From what I understand about "ELO inflation", it refers to the effect that the Top 100 FIDE players had 2600 ELO in 1970, but 2700 ELO today. It has been argued that simply the level increased, as more very good players entered the field. The ELO number as such should be fair in both eras (after playing infinitely many games...). I don't think that it is an issue for computer chess comparisons. Let me know if you have other data/information!
