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.
Big new ideas in chess programming
Moderators: hgm, Rebel, chrisw
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Big new ideas in chess programming
This was also the past. Has always been like this.JohnS wrote: So my question is: Is this the future for strength increases
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Big new ideas in chess programming
There have also been "big ideas" (e.g. nullmove) which gave big elo jumps.This was also the past. Has always been like this.
The question is about whether we have seen the last of such big ideas....
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Big new ideas in chess programming
This is a question that should have been asked 20 years ago. Null move is from late '80 !Michel wrote:There have also been "big ideas" (e.g. nullmove) which gave big elo jumps.This was also the past. Has always been like this.
The question is about whether we have seen the last of such big ideas....
In the last 20 years I don't see anything like that, I only see a very long list of very little tweaks.
-
- Posts: 893
- Joined: Mon Jan 15, 2007 11:23 am
- Location: Warsza
Re: Big new ideas in chess programming
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
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
Pawel Koziol
http://www.pkoziol.cal24.pl/rodent/rodent.htm
http://www.pkoziol.cal24.pl/rodent/rodent.htm
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Big new ideas in chess programming
Surely LMR and particular the very aggressive version pioneered by Rybka is worth a lot of elo too.In the last 20 years I don't see anything like that
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Big new ideas in chess programming
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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Big new ideas in chess programming
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.hgm wrote: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.
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Big new ideas in chess programming
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.
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Big new ideas in chess programming
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.mcostalba wrote:This is a question that should have been asked 20 years ago. Null move is from late '80 !Michel wrote:There have also been "big ideas" (e.g. nullmove) which gave big elo jumps.This was also the past. Has always been like this.
The question is about whether we have seen the last of such big ideas....
In the last 20 years I don't see anything like that, I only see a very long list of very little tweaks.
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!
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.