Big new ideas in chess programming

[JohnS]

I've been amazed at the rapid strength increase for Stockfish and complement the development team for providing us with a super-strong and free engine. Looking at the development log at abrok.eu/stockfish, it's interesting to see that most changes only involve a few lines of code and give around 2 - 5 Elo increase each.

So my question is: Is this the future for strength increases - extensive testing with small improvements (discounting increases due to hardware speed improvements)? Have we seen the last of the big new ideas in chess programming that could result in major Elo increases (say greater than 50 for a single idea)?

In asking the question I'm in no way trying to downgrade the success of the Stockfish team or any other chess programmer. I have huge respect for all of them for their skills. This is a philosophical question.

[mcostalba]

So my question is: Is this the future for strength increases

This was also the past. Has always been like this.

The top engines always grow bit by bit because they open new roads and this is hard and difficult and with a lot of trials and error involved and because they don't have any reference.

Big jumps in ELO instead are common in engines started from scratch and still under active development, or in engines that can have access at stronger ones. First because there are a lot of well known working ideas that they can implement with almost sure success and also because when an engine has a low/middle ELO rating a good change can bump its ELO much higher than the same change added to a mature engine. The last one is an interesting observation that I did through years, it is not very clear to me why, probably because a top engine is the sum of many ideas/schemes that in some way overlap, so that if you remove one, anyhow the others cover a bit the loss, instead in a simpler engine each idea seems to counts more.

Another observation I did is that a very simple and clean engine gains more from adding a good idea than an equal strength one but very complex and convoluted. And here is where the developer can put is added vaue, trying to keep its engine as simple and efficient as possible without adding cruft and complexity that will hurt in the long term. This is much more easy to say than to do and requires a good experience as a programmer, Typical amateur developers instead tend to add rules/tricks/evaluation terms because they think they help, while instead in the long term they just hurt the engine that becomes very insensible to good ideas: a good idea can help a good engine but do not work on a messed up one.

[Michel]

This was also the past. Has always been like this.

There have also been "big ideas" (e.g. nullmove) which gave big elo jumps.

The question is about whether we have seen the last of such big ideas....

[mcostalba]

This was also the past. Has always been like this.

There have also been "big ideas" (e.g. nullmove) which gave big elo jumps.

The question is about whether we have seen the last of such big ideas....

This is a question that should have been asked 20 years ago. Null move is from late '80 !

In the last 20 years I don't see anything like that, I only see a very long list of very little tweaks.

[PK]

Isn't late move reduction / history reduction approaching the importance of null move?

And there are at least two more candidates for "big ideas of the second order": midgame/endgame interpolation in evaluation and extensive use of material imbalance tables.

One can also argue that extensive use of testing in itself is the big idea, one to rule them all

[Michel]

In the last 20 years I don't see anything like that

Surely LMR and particular the very aggressive version pioneered by Rybka is worth a lot of elo too.

[hgm]

But these 'big ideas' are only 'big ideas' in hindsight. It took for instance a lot of time to get from the first conception of LMR to the polished version that top engines use now. We had to learn which moves to exempt, whether to use history in this decision, how much to reduce as a function of move number, starting at which depth, etc. All that was achieved in tiny steps.

[mcostalba]

But these 'big ideas' are only 'big ideas' in hindsight. It took for instance a lot of time to get from the first conception of LMR to the polished version that top engines use now. We had to learn which moves to exempt, whether to use history in this decision, how much to reduce as a function of move number, starting at which depth, etc. All that was achieved in tiny steps.

Yes, exactly. LMR predates Rybka and so history pruning. Rybka, as many other engines, like Glaurung, contributed to further refine those ideas, but it was a history of many little steps along many years.

Little steps that are still ongoing today, for instance we have applied another very small improvement to LMR only few weeks ago. And I am very confident also in the future someone will find new ways of improving (just a bit) upon the same old ideas: this is how chess engine developing proceeds and, again, has always been like this.

[Daniel Shawul]

The 'standard' LMR version, that reduces all but the first move by 1 ply, can improve search depth almost by the same amount as alpha-beta in the best case O(b^d/2). So that is a very big improvement already. Well I don't know by how much the multi-reduction version improves it further, but it is definitely not such a big jump. And rybka didn't pioneer sh*t , heck I was doing multiple reductions (max=2) and no-history tables since first use. I guess all I am saying is the original 'lets reduce more based on move order' is the big one whoever came up with it.

[Don]

This was also the past. Has always been like this.

There have also been "big ideas" (e.g. nullmove) which gave big elo jumps.

The question is about whether we have seen the last of such big ideas....

This is a question that should have been asked 20 years ago. Null move is from late '80 !

In the last 20 years I don't see anything like that, I only see a very long list of very little tweaks.

LMR is clearly one of the big ideas in chess. It would be hard to define that away but it will come down to peoples opinions and how they categorize things. But anything that gives more than just a handful of ELO is a big idea and LMR is worth over 100 ELO. Refinements of a big idea do not invalidate the idea. Reductions have been done for a very long time in computer chess but I make a distinction, Late Move Reductions is a specific technique. Even though there are infinite variations in how to do it, the basic outline is well understood.

The primary big ideas in computer chess in my opinion are:

1. quies "stand pat" search.
2. hash tables
3. check extensions.
4. futility pruning
5. null move pruning.
6. LMR

You could go back and count things like alpha/beta pruning and other things too and you could include some ideas that are lesser but still impactful, there are many. Futility pruning might not qualify here but I think it was a key insight and it gave a pretty large ELO boost.

There is also the issue of perspective - people won't count these the same because each is coming from a different perspective - we each have a different cognitive model of events and discoveries and how they impacted us. So if anyone tries to suck me into an argument about where LMR (or something else qualifies) I am not going to entertain a debate on it. It's like arguing over whether a given person is good looking or not - it's in the eye of the beholder. Let's just say this is MY list. If you can come up with something else I have forgotten I will add it to the list!