Computer Chess Progress: Stockfish 7 vs Ruffian 1.0.5

[Steve Maughan]

If we look back to the days of Ruffian 1.0 can we ask the question, can we identify the main software improvements?

The three which come to mind are:

1. Late Move Reduction
2. Magic bitboards
3. Better evaluation tuning

What are the other major softawre improvements?

- Steve

[yurikvelo]

1. Late Move Reduction
2. Magic bitboards
3. Better evaluation tuning

What are the other major softawre improvements?

1. time management!!
2. Aspiration windows
3. Move ordering heuristic
4. SMP (YBWC) - cannot apply to old CPU, but its huge improvement
5. More effective Hash implementation (both in terms of CPU/MEM cost and replacement strategies)
6. EG-probing support and better EG knowledge without EGTB
7. support modern CPU features to reduce CPU-cycles for the same job
8. Eval is not simpy better tuned, it is implemented as tapered (phase-wise)
9. Evaluation is not just tuned, it counts many more factors related to king safety, pawn structures, bishop pairs, mobility etc
10. new types of Hashes except Main/Transposition table (pawn structure hash table, evaluation cache, material hash)

[jdart]

Some of your list like aspiration windows has been around a long time.

Re

5. More effective Hash implementation (both in terms of CPU/MEM cost and replacement strategies)

Also, lockless hashing (pioneered by Hyatt).

Hash-based singular extensions (Ippo series, probably from Rybka).

Deep LMR dependent on node type and other factors besides depth/move count (Stockfish).

--Jon

[bob]

1. Late Move Reduction
2. Magic bitboards
3. Better evaluation tuning

What are the other major softawre improvements?

1. time management!!
2. Aspiration windows
3. Move ordering heuristic
4. SMP (YBWC) - cannot apply to old CPU, but its huge improvement
5. More effective Hash implementation (both in terms of CPU/MEM cost and replacement strategies)
6. EG-probing support and better EG knowledge without EGTB
7. support modern CPU features to reduce CPU-cycles for the same job
8. Eval is not simpy better tuned, it is implemented as tapered (phase-wise)
9. Evaluation is not just tuned, it counts many more factors related to king safety, pawn structures, bishop pairs, mobility etc
10. new types of Hashes except Main/Transposition table (pawn structure hash table, evaluation cache, material hash)

Aspiration windows have been around since the 70's. As has parallel search. EGTBs were around in the 80's from Ken Thompson and Steven Edwards, and middle 90's or so from Eugene Nalimov. Pawn hash, eval cache, king safety cache were all around in the 70's as well. And finally, move ordering has hardly changed at all (hash move, captures ordered by SEE, killer moves, counter moves, etc.)

Null move search has evolved from fixed R=1 and R=2 to a dynamic amount, so that is more recent. Reductions are more recent. Even singular extensions were around in the late 80's...

[yurikvelo]

Null move search has evolved from fixed R=1 and R=2 to a dynamic amount, so that is more recent. Reductions are more recent. Even singular extensions were around in the late 80's...

was it in general or for x86 computers?
Deep Thought, Blue obviously was SMP, but Ruffius, Fritz, early Rybka - were not

All mentioned features are not new and were known 20 years ago. Question was: how +600...700 elo was gained on the same hardware

[nionita]

Null move search has evolved from fixed R=1 and R=2 to a dynamic amount, so that is more recent. Reductions are more recent. Even singular extensions were around in the late 80's...

was it in general or for x86 computers?
Deep Thought, Blue obviously was SMP, but Ruffius, Fritz, early Rybka - were not

All mentioned features are not new and were known 20 years ago. Question was: how +600...700 elo was gained on the same hardware

If you can't run ten tousands of test games, you can't discover an improvement of 2-3 elo. Many such improvements add together, very few are probable bigger than 5 elo.

Also the internet added a very high value, together with open source software. You can find papers, you can ask questions, discuss, even copy ideas, get inspired, so I guess much more poeple can contribute. Things that 20 years ago were not possible.

[Angrim]

Also the internet added a very high value, together with open source software. You can find papers, you can ask questions, discuss, even copy ideas, get inspired, so I guess much more poeple can contribute. Things that 20 years ago were not possible.

I remember reading Hyatt's posts on rec.games.computers.chess in 1993, so we can cross that one out as being new. I was at a university, but somewhere around then AOL connected to the internet, so access was fairly widespread.

[fierz]

Dear Steve,

I can hardly imagine magic bitboards being a huge improvement - they may be nice to have and maybe gain a bit of speed but given that a doubling of speed would be around 60 rating points they should be rather low in the list of improvements!?

I would add not only evaluation tuning but also search tuning (lots of parameters in LMR and nullmove and extensions....).

I would also add more emphasis on bug-free code <-> lighter evaluation functions. My feeling is that back in the days where you could only search a few ply deep, there was no hope of solving everything with the search, so people tried to encode all kinds of knowledge in the evaluation function, probably producing lots of bugs/inconsistencies along the way (at least my evaluation function of my essentially-2004-program looks like that...). Fruit showed that you don't need a heave eval at all, but bug-free code instead.

cheers
Martin

[fierz]

Intel CPU history:

You run SF7 at pretty modern CPU (1M L2 cache, FSB400, SSE2)

Techniques which work well on 500-1000 kN/move might not work at 10-30 kn/move

P.S. I have alive PIII-500 (512 SDRAM, Windows XP) and could run some tests if there is interest

Thanks for the detailed CPU list. 2003 doesn't go down as modern in my book though

In fact, the 2003 CPU matches up quite nicely with Ruffian which is from 2002, so hardware/software kind of match.

You also mentioned:

Hypo 1: At old CPU modern engine might slowdown much more than old engine.
If Ruffian is 2x faster than SF7 at modern Centrino CPU, it might be 5x faster at P-I

Hypo 2: Search techniqes which gain ELO at 100+ knodes per move might decrease ELO at 10+ knodes per move

The point of this match was to show that Hypo 3, mentioned by other posters (perhaps not in these words, but in this spirit): Search techniqes which gain ELO at 100+ Mnodes per move might decrease ELO at 1+M nodes per move is wrong. I can't go further back, but I have the extremely strong suspicion that the whole thing wouldn't change even if going back to the old days of 6502 CPUs. If anyone could go back to anything older than I did that would be interesting to see....

cheers
Martin

[jdart]

I did a lot of research in the computer chess literature when I was starting out. But much of it was not very useful, in a practical sense. One of the problems with CS literature is that often papers give a general idea of what the author did but you may not be able to readily reproduce it if all you have is a general description and maybe some pseudocode. Sometimes this is done deliberately because the author has a commercial interest connected with the project (I am speaking generally here, not just about chess).

Before Crafty was published pretty much the only decent open-source program was Gnuchess (4.x), which was interesting and a nice piece of work, but not very strong by today's standards, and not a model of code clarity, either.

--Jon