Search or Evaluation?

[bob]

I agree they are the two general purpose major advances although there are other ones that also offer extra Elo, like futility or even eliminating losing captures from the quiescence search. There are also many other search improvements which overlap with 1 & 2 and hence are much less effective, but without 1&2 existing then these other search improvements would be effective.

Also although not a general technique I have found search extensions to be extremely effective and I can see how implementation of search extensions could have another big impact on the strength (or otherwise) of a chess program.

I don't think it is possible to rely on the displayed search depths because some programs don't display their true depths. Additionally as you well know there are many factors, sometimes it is not the iteration depth but the importance of not pruning a critical new line of play that is key.

15 years ago a number of us were guilty of tuning against position test sets which were usually tactical. This was compounded because important publications like CSS used to run features on new programs performing against the BT test or the LCT2 test or ...

So it also became even commercially important to do well in these test sets. Of course there is a very loose relationship between test positions and chess strength in games and I think understanding the reasons for that are very important in understanding where chess strength in games comes from.

It is your last statement where we disagree. It is clear to me that the big + and - in Elo comes from search and the gradual accumulation of rating points comes from eval. I believe the two mentioned search breakthroughs above can be implemented in various different ways and the range of strength improvement is still quite large.

So I think there is plenty of room still to improve chess programs in both search and eval but I believe ultimately more strength comes from the search than it does from the eval.

Hi Mark and Uri,

Our discussion is as old as the birth of computer chess and we should keep it going and redo at times until we are in agreement.

My take, let's evaluate some history:

Richard Lang ruled the mid 80's till about 1992. Richard has admitted that his domination mainly came from his advantage of the better hardware he got from Mephisto. IOW: search dominance.

1991/92: Tasc came with the ChessMachine hardware 2 times faster than his hardware, Richard lost his world-title. Search dominance again.

1993/1994: Intel enters the scene, the Pentium, the end of the dedicated industry. You win the 1993 WCCC in Munich.

1996: Rebel8 tops the SSDF with a +60 elo gap. What was Rebel8 about? Search improvements mainly. Search rules.

1998: Fritz5, the introduction of a new concept, Nullmove. Frans rules the computer chess world for a couple years. Search, search, search...

Eventually other programs catch up, Fritz loses its superiority.

2000/2001: Shredder discovers LMR and tops all rating lists for years to come. Search did the trick again...

But, but, but... and this is crucial, eventually other programs catch up, ending the Shredder hegemony.

We are now living in the Rybka era, nobody yet knows its secret. Search only? The 2 of you seem to suggest it.

I disagree.

Why?

Although (I think) it's a proven fact that search has ruled the computer chess area (see above history) from its early existence till now the tendency can be quite misleading for the future, it certainly can't be automatically assumed as the 2 of you do.

My thesis: while it is certainly true that implementation matters it's wrong to assume this can explain the big difference between Rybka and the other tops. It's like saying Vas is a search genius, the rest is incompetent. I don't buy that, even if it is true eventually others will catch up.

Why claim the success of Rybka is search? There is no proof of that. Maybe your search (and others) is better than Rybka, who can tell?

Nowadays with ease the current tops are searching at 14-16 plies covering about all possible tactics, so what is left? IMHO, asking the question is answering the question.

Food for thought?

Ed

I have one quibble. null-move was not a 1998 thing. Maybe you meant 1988? Beal's paper "Selective Search without tears" was published (I think) around 1986. That was when I started using null-move myself, although not with the aggressiveness we use today...

[ed]

I have one quibble. null-move was not a 1998 thing. Maybe you meant 1988? Beal's paper "Selective Search without tears" was published (I think) around 1986. That was when I started using null-move myself, although not with the aggressiveness we use today...

You are absolute right, in 1986 (Cologne) Don Beal played with a program that used Nullmove in QS only. Beats me why and how, but he did. I was not saying Frans is the father of Nullmove, he isn't, but Frans in 1998 with Fritz-5 implemented Nullmove in such a way he dominated all rating list for a couple of years and the technique became the base for every modern strong chess program.

Ed

[bob]

I have one quibble. null-move was not a 1998 thing. Maybe you meant 1988? Beal's paper "Selective Search without tears" was published (I think) around 1986. That was when I started using null-move myself, although not with the aggressiveness we use today...

You are absolute right, in 1986 (Cologne) Don Beal played with a program that used Nullmove in QS only. Beats me why and how, but he did. I was not saying Frans is the father of Nullmove, he isn't, but Frans in 1998 with Fritz-5 implemented Nullmove in such a way he dominated all rating list for a couple of years and the technique became the base for every modern strong chess program.

Ed

Somewhere in the 1987-1988 time frame, Burton Wendroff (LaChex from Los Alamos National Lab) and I were talking on the phone and he mentioned this idea and sent me Beal's paper. Burt and I both implemented the "classic null-move search" that year with one significant difference from today's implementations... That was we only allowed _one_ null-move in any path. Another minor difference was that we used R=1. In looking at versions of Cray Blitz, somewhere around 1993 or so, we were using recursive null-move, although we were still using R=1. The only difference between that old program's implementation and what I am doing today is the "R" factor. Old = 1 everywhere, today is 2 to 3 depending on depth remaining (3 closer to the root, 2 closer to the tips.) Crafty came about at the end of 1994 after the last official ACM tournament was held (didn't know it was the last at the time. Looking at the comments in main.c, version 1.2 had classic recursive null-move search although with R=1. Before the first version was released somewhere in 1995, we were flipping back and forth between R=1 and R=2 if you read the comments in main.c At the depths back then, on a pentium-133, R=2 had some issues here and there...

That's why the 1998 date seemed wrong. I know that at least Crafty and Ferret were using almost exactly what we use to day, in the tournaments we played in back in 1995/1996, but I don't remember when fritz stormed onto the scene. In 1995, on ICC, genius was the most difficult opponent I recall playing against...

[Uri Blass]

I have one quibble. null-move was not a 1998 thing. Maybe you meant 1988? Beal's paper "Selective Search without tears" was published (I think) around 1986. That was when I started using null-move myself, although not with the aggressiveness we use today...

You are absolute right, in 1986 (Cologne) Don Beal played with a program that used Nullmove in QS only. Beats me why and how, but he did. I was not saying Frans is the father of Nullmove, he isn't, but Frans in 1998 with Fritz-5 implemented Nullmove in such a way he dominated all rating list for a couple of years and the technique became the base for every modern strong chess program.

Ed

I think that claiming that Frans dominated the rating list for a couple of years because of null move is misleading.

I guess that no programmer dominated the rating list because of one trick.
Many other programs also used null move pruning in that time but Fritz probably had better data structure or other tricks to be better.

Let talk about free source programs.
What is the reason that free source toga is strong relative to other programs including Prodeo?

I think that the only way to know is simply to learn the code and you can learn only by writing code that is an hard work.

The idea is to start from an empty project and add parts of toga that you understand to the empty project and give comments in english that explain exactly what the parts are doing.

The parts that you add in one day cannot be big because in that case you cannot fully understand them and the idea is only to add parts that you fully understand.

Understanding is going to take a lot of time but after finishing this job you may understand what toga does right that you do wrong.

Personally I never tried to do this process for toga because toga seemed to me to be too big and it had too many files.

Fortunately I got the source of strelka that has similiar strength to fruit and I am more encouraged psychologically to try to understand strelka because strelka has less files and smaller code than toga.

I did not answer mark to the question who is the programmer of this program(and I only gave analysis to show similiarity with rybka beta) so I can say that
strelka is not a free source code program but the exe is free.
The programmer is Jury Osipov from russia and the code is probably based on taking some tables from the exe of rybka beta and reverse engineering of rybka.

Note that strelka starts by xoring some bitboards arrays with random numbers and the only reason that I can imagine doing it is simply because vasik also xored the bitboards of rybka beta with random numbers at the beginning to make the task of understanding rybka beta by reverese engineering harder.

Uri

[bob]

It is called "obfuscation". "the art of hiding what you are doing".

Just like the bogus node counts, the bogus search depths, now we have bogus tables in Rybka as well. That is a pretty well-known method for obfuscation. Such tricks have been used for _many_ years when companies sell a big software package, and then offer a free 30-day trial or whatever to get you to buy the thing. After 30 days it quits running, and many of us used to spend a lot of time tracking down their date check code to disable it. And the software developers got more and more clever. They would actually "build" the instruction that does the system call to obtain the date, so that you could not find it with a binary-type data search. I used to fox 'em by modifying the operating system to log the PC for every application that did that system call, then I could find out where the system call had been executed, and then find out where the code is that built the instruction and put it there in the first place. Later they came up with the random number trick to hide the code, and then just "unhide" it at run time with xors.

The interesting part of this (to me) is that apparently whatever it is Vas is hiding from everyone is simple enough that he is afraid a careful analysis of real output would reveal the idea. And so he struggles mightily to hide what he has found. But it is just a matter of time...

[Dylan Sharp]

And so he struggles mightily to hide what he has found.

So, the secret of Rybka's success is just a piece of code? And if it was added to all the other chess engines they would do a giant leap in strength?

[bob]

And so he struggles mightily to hide what he has found.

So, the secret of Rybka's success is just a piece of code? And if it was added to all the other chess engines they would do a giant leap in strength?

That is quite possible. It could be a group of things, or it could be a single idea. But I would bet that the "main idea" is not that complicated since it apparently justifies a lot of obfuscation to make it difficult to understand. I don't particularly like the idea of an engine being 'dishonest' in what it reports to the user, but I can see why one might want to do that.

[Dylan Sharp]

Well, Strelka's code is supposed to be the disassembled code of Rybka Beta (As shown with their exactly same PV and other stuff) so since Uri Blass has this code he may be able to tell (Or he may just use the secret to make Movei the #1/#2 engine and keep the secret).

[Uri Blass]

Well, Strelka's code is supposed to be the disassembled code of Rybka Beta (As shown with their exactly same PV and other stuff) so since Uri Blass has this code he may be able to tell (Or he may just use the secret to make Movei the #1/#2 engine and keep the secret).

I can only say that things are not so simple and one of the reasons is that some other programmers also got the code of strelka.

Tord who is probably a better programmer than me also got the code of strelka so there is a bigger probability that glaurung is going to be the #1/#2 engine.

Uri

[Dylan Sharp]

Tord who is probably a better programmer than me also got the code of strelka so there is a bigger probability that glaurung is going to be the #1/#2 engine.

Ah! So you're confirming that there's indeed a secret!? (Otherwise, Strelka's code wouldn't help to make the leap in strength).

[Uri Blass]

Tord who is probably a better programmer than me also got the code of strelka so there is a bigger probability that glaurung is going to be the #1/#2 engine.

Ah! So you're confirming that there's indeed a secret!? (Otherwise, Strelka's code wouldn't help to make the leap in strength).

No
I am not confirming nothing.

1)I still did not understand most of the code of strelka so I do not know if there is a secret.

2)I did not understand most of the code of free source programs so even if I understand strelka I will not know if there is a secret because I am not going to know if the same ideas are not used in other free source programs.

Uri

[Tord Romstad]

The interesting part of this (to me) is that apparently whatever it is Vas is hiding from everyone is simple enough that he is afraid a careful analysis of real output would reveal the idea. And so he struggles mightily to hide what he has found. But it is just a matter of time...

I know nothing about Rybka, but if it is Strelka we are talking about, there is no need to do any sophisticated reverse engineering or careful analysis to reveal the "idea" behind the tables. You can find exactly the same tables in Crafty, and in virtually any other bitboard program. The arrays which are XORed with a random number during program initialization are nothing more than rotated bitboard attack tables, bitboard masks for detecting passed pawns, setting and clearing bits, and so on. There is nothing magic, secret or original about them.

The only lookup tables in Strelka which are not found in any other program I know, and the one people are using as "proof" that Strelka uses parts of Rybka's code (knowing nothing about Rybka, I have no idea whether the claims are true), are a two tables used for king shelter evaluation. These tables are not obfuscated in any way. Also, although these two tables are not seen in most other programs, there is nothing very remarkable about them. Strelka looks at the friendly and enemy pawns in a 3x4 rectangle in front of the king, considers the sets of friendly and enemy pawns in this rectangle as two 12-bit integers, and uses these integers as indices to the two tables. The values of the two tables are added to obtain a score.

Tord

[Tord Romstad]

Ah! So you're confirming that there's indeed a secret!? (Otherwise, Strelka's code wouldn't help to make the leap in strength).

There is no big secret in Strelka. It is a solid, reasonably bug free, well written and well optimized program, nothing more. Because the strength is more or less what you would expect from such a program, I don't really understand why so many people seem to believe there must be some new and super-powerful secret hiding somewhere.

Tord

[Uri Blass]

Ah! So you're confirming that there's indeed a secret!? (Otherwise, Strelka's code wouldn't help to make the leap in strength).

There is no big secret in Strelka. It is a solid, reasonably bug free, well written and well optimized program, nothing more. Because the strength is more or less what you would expect from such a program, I don't really understand why so many people seem to believe there must be some new and super-powerful secret hiding somewhere.

Tord

The facts are that strelka32-bit is stronger than other programs that come with source code except toga that has similiar strength.

I consider strelka to be stronger than toga because it is possible to get significant speed improvement for strelka by 64 bits.

The main question is what is the reason that strelka is stronger espacially when strelka has smaller evaluation than toga and clearly has less knowledge about specific endgames like kBP vs K with blind bishop and more types of specific endgames(this specific endgame knowledge is not very important but it should be worth some elo points for toga and I guess that toga could be 10 elo weaker without this knowledge).

It is clear that most programmers do not know the reason(otherwise they could write a program that is at least as strong as strelka).

Note that I also do not know the reasons that toga is stronger than other free source programs so from my point of view toga also has many secrets but I believe that it can be easier for me to discover the secrets of strelka than discovering the secrets of toga.

You can claim that these are not secrets but from my point of view
everything that I do not know is a secret as long as I do not know it(even if the secret is written in public source code).

Uri

[ricard60]

I allways ask myself how a grandmaster find a solution to problems of chess in seconds that for me takes minutes or even do not find at all. I ask him the following question:

Master how many moves do you see in a position of a game of chess?
the master answer:

I allways see only one

me:but how can this be? how can you win a game of chess only seeing one move?

Master: is simple i always see the best move.

This answer got deep in my mind and from that moment until now i allways believe that chess is more a software problem than a hardware problem and that is why sometimes we see a machine with a big hardware lose to others with smaller ones.
So if we have the best evaluation function we will come up allways with the best move.

Now the problem will be how can we get that function?

Regards
Ricardo