What's Strelka's Secret Sauce?

[Harald Johnsen]

...
Strelka in the qsearch does not generate all the captures but only captures of pieces that are heavy enough(for example pawn captures are not generated if the evaluation is smaller than alpha-margin-pawn_value).

I wonder if this idea is used by another chess program with free source code.

Uri

Yes, Gerbil has that in the source.

Code: Select all

	//
	//	In captures-only mode I'm going to do some pruning I haven't heard
	//	described along with MVV/LVA.  If a capture can't possibly drive the
	//	material score to within 100 centipawns of alpha, prune it out.
	//
#ifdef	QUIESCENT_PRUNING
	valMin = (fCapsOnly) ? pste->valAlpha - (pste->valPcUs + pste->valPnUs -
		pste->valPcThem - pste->valPnThem) - 100 : 0;
#endif

...

Code: Select all

		case pcKNIGHT:	// No "break" statement above.
			//
			//	Knight is a non-sliding piece.  The king also drops into this
			//	code when it gets done messing around with castling.
			//
			for (pvec = s_argpvecPiece[ppiFrom->pc]; *pvec; pvec++)
				if (!((isqTo = isqFrom + *pvec) & 0x88))
					if ((ppiTo = pcon->argsq[isqTo].ppi) == NULL) {
						if (!fCapsOnly) {
							pcm->isqFrom = isqFrom;
							pcm->isqTo = isqTo;
							pcm->cmk = cmkNONE;
							pcm++->cmf = cmfNONE;
						}
#ifdef	QUIESCENT_PRUNING
					} else if ((ppiTo->co != ppiFrom->co) &&
						(ppiTo->val >= valMin)) {
#else
					} else if (ppiTo->co != ppiFrom->co) {
#endif
						pcm->isqFrom = isqFrom;
						pcm->isqTo = isqTo;
						pcm->cmk = cmkCAPTURE | (ppiTo->val - ppiFrom->pc);
						pcm++->cmf = cmfCAPTURE;
					}
			break;

HJ.

[Tord Romstad]

Strelka in the qsearch does not generate all the captures but only captures of pieces that are heavy enough(for example pawn captures are not generated if the evaluation is smaller than alpha-margin-pawn_value).

I wonder if this idea is used by another chess program with free source code.

I don't know, but it would surprise me very much if it isn't. It's an extremely obvious idea in a bitboard engine. I have played with it a few times in the past, but have decided that I don't like it, because I want to seach captures of pieces which are not heavy enough in the case that the capturing move is a check. Generating these moves in addition to the captures of sufficiently heavy pieces would be possible, but a bit too messy to be worth it for such a tiny speed improvement.

Tord

[FrancoisK]

>Strelka in the qsearch does not generate all the captures but only captures of pieces that are heavy enough(for example pawn captures are not generated if the evaluation is smaller than alpha-margin-pawn_value).

Yes, I also found the idea interesting and tried it in BugChess2 (after reading Strelka'source).
Unfortunately for me the gain is so small that I decided to remove it, it's not just worth the added complexity.
Using the evaluation mobility computation to check if i should enter the capture generation (this is not in strelka) was a bigger gain - not a very big one though.

François

[Uri Blass]

>Strelka in the qsearch does not generate all the captures but only captures of pieces that are heavy enough(for example pawn captures are not generated if the evaluation is smaller than alpha-margin-pawn_value).

Yes, I also found the idea interesting and tried it in BugChess2 (after reading Strelka'source).
Unfortunately for me the gain is so small that I decided to remove it, it's not just worth the added complexity.
Using the evaluation mobility computation to check if i should enter the capture generation (this is not in strelka) was a bigger gain - not a very big one though.

François

I did not try it in movei because I plan to do rewrite in any case.


Movei is clearly non optimized and it even has no function to generate only quiet moves(it generates only captures in the last stage of the qsearch and generate all moves in other cases including the first plies of the qsearch when checks are generated)

Uri

[mjlef]

Strelka in the qsearch does not generate all the captures but only captures of pieces that are heavy enough(for example pawn captures are not generated if the evaluation is smaller than alpha-margin-pawn_value).

I wonder if this idea is used by another chess program with free source code.

I don't know, but it would surprise me very much if it isn't. It's an extremely obvious idea in a bitboard engine. I have played with it a few times in the past, but have decided that I don't like it, because I want to seach captures of pieces which are not heavy enough in the case that the capturing move is a check. Generating these moves in addition to the captures of sufficiently heavy pieces would be possible, but a bit too messy to be worth it for such a tiny speed improvement.

Tord

In bitboard programs, it is pretty easy. You XOR off the bits of pieces that are too small for a capture value to get the score back up above alpha. Then if all captures fail, and at this node you want to generate checks as well, flip the bits in the mask and generate check moves only to those squares. This will includ generating capture checks that were not "big enough". Of course, this is only a gain when a likely capture move will fail high anyway and so prevent the need for the checking move generation.

[bob]

Rajlich stated lot of things
What you see in Strelka about pruning is what is in R1.0

Can you post the reference (link...) of what you say?

No, I can not
You can believe me or not, but there is nothing interesting in R1.0 that is not already in Strelka

I'm not asm expert and I can't tell you anything about eval, but search calls is very easy to spot...

I disagree about it.

I believe that there are clearly interesting things in rybka that are not in strelka.
significant name of variables may be one of them.

Less ugly code when you replace many magic numbers by constants may be another one of them.

I think that if Vasik release the code of rybka1.0 he can lose from it not because of the fact that there are new things that are not in strelka but because it is going to be easier for people to understand the code and use the ideas.

I also think that the main secret of strelka or rybka is simply understanding fruit.

There are certainly original ideas in strelka but I think that thinking of original good ideas is an easier task relative to the task of understanding the code of other people.

The lesson from strelka is that people should not underestimate the value of understanding the source of other programs.

Last note about strelka is that I discovered more than one bug in strelka but I think that it is a bad idea to tell the public what are the bugs.

It is better to use the bugs to help to detect strelka clones in the future.

Uri

Yes, you are right about names. Also, lot of function in strelka are inlined, but in rybka source they are probably not (repetition detection, HT probes, etc.). But, I think that most interesting stuff are in eval, not in the search. Search is clear, fruit/glaurung search + 2-3 tricks. When I said that there is nothing new it was concerning search and pruning and I think it is obvious from strelka source.

I think that both are interesting.
I will mention one idea that is new for me and I wonder if it is used by fruit glaurung crafty or another engine with free source.

Strelka in the qsearch does not generate all the captures but only captures of pieces that are heavy enough(for example pawn captures are not generated if the evaluation is smaller than alpha-margin-pawn_value).

I wonder if this idea is used by another chess program with free source code.

Uri

I tried this years ago, but found that it didn't help in my case. Adding the special-case testing at every node in the q-search, to screen out captures of pieces that can't get the score above alpha had a bigger cost than just generating all captures, and screening out the ones that are not good enough (what some have labeled "delta pruning" because I used the variable "delta" in Crafty).

Whether or not it works for others probably depends on a lot of implementation factors in their engines. Since so many q-search nodes end up with zero captures, I don't get any overhead there, whereas I did when eliminating captures that could not be made in the first place...

[Eelco de Groot]

Rajlich stated lot of things
What you see in Strelka about pruning is what is in R1.0

Can you post the reference (link...) of what you say?

No, I can not
You can believe me or not, but there is nothing interesting in R1.0 that is not already in Strelka

I'm not asm expert and I can't tell you anything about eval, but search calls is very easy to spot...

I disagree about it.

I believe that there are clearly interesting things in rybka that are not in strelka.
significant name of variables may be one of them.

Less ugly code when you replace many magic numbers by constants may be another one of them.

I think that if Vasik release the code of rybka1.0 he can lose from it not because of the fact that there are new things that are not in strelka but because it is going to be easier for people to understand the code and use the ideas.

I also think that the main secret of strelka or rybka is simply understanding fruit.

There are certainly original ideas in strelka but I think that thinking of original good ideas is an easier task relative to the task of understanding the code of other people.

The lesson from strelka is that people should not underestimate the value of understanding the source of other programs.

Last note about strelka is that I discovered more than one bug in strelka but I think that it is a bad idea to tell the public what are the bugs.

It is better to use the bugs to help to detect strelka clones in the future.

Uri

Yes, you are right about names. Also, lot of function in strelka are inlined, but in rybka source they are probably not (repetition detection, HT probes, etc.). But, I think that most interesting stuff are in eval, not in the search. Search is clear, fruit/glaurung search + 2-3 tricks. When I said that there is nothing new it was concerning search and pruning and I think it is obvious from strelka source.

Apparently this is not in Strelka sources then or I thought Uri or somebody else would have found it by now?

By lkaufman Date 2008-02-20 01:20 Suppose that the first iteration in a hypothetical program was 1 ply with no quiescence search, the second allowed 1 ply of capture, the third allowed 2, the fourth 3, the fifth 4, the sixth 5, and the seventh unlimited (or whatever maximum might be used). Then the eighth iteration would be 2 ply with full quiescence etc. This is a crude approximation to the situation with Rybka. Currently we would call the seventh iteration "1 ply" in this hypothetical program. You would call the very first (or perhaps second) one "1 ply". Your solution might be technically "correct", but it would hardly be consistent with standard industry practice. I say that the first iteration to count is the first one that plays at some relatively minimal level, maybe 1200 or 1300 Elo. That means for Rybka 3 probably starting two levels of quiescence earlier than we do now.

By BB Date 2008-02-20 02:25 > Currently we would call the seventh iteration "1 ply" in this hypothetical program.


I would probably use fractional ply to describe the situation between iteration 1 and iteration 7 in this case (it is not clear to me if the term "iterative deepening" should apply for these first iterations, as it could be argued that they use substantively dissimilar methodologies). Perhaps 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 1.0, 2.0, though the decimals would be place-holders rather than connoting any arithmetic meaning. Alternatively, the UCI-variable seldepth could give some notion of this. Or, if you use various qsearch-es throughout the search, two "depths" could be returned at any time: the horizon-distance (from the root), and the qsearch-thoroughness. In any event, with your example, I would hope that the 7th iteration (1 ply + full q) and the 8th (2 ply + full q) would have depths that differ by 1. As I indicate above, without the rigidity of the iterative deepening framework (which I realise is perhaps too strong an assumption to have broad validity in modern chess engines), the particularities of the labelling of iterations vis-a-vis depth becomes much less clear. On the other hand, I can't say that I have great sentiment toward re-construing "depth" merely to conform to the numerology of previous times. [I am reminded of the "rated speed" of various processors, which was supposed to ease comparisons for consumers, but didn't always deliver such a result].

I think the question is, if Rybka's and Vasik's first implementation of this is not cloned by Osipov in Strelka then is it really helping much, else Strelka would have a lower rating - of course the Strelka 1.0 clone certainly had a much lower rating than Rybka 1.0 - , and the second question is; whether iterative deepening in Quiescence Search was tried before in the past and found to be not feasible if you don't make some changes to normal iterative deepening? It seems like a signicant search idea though to me, I have never heard of it before. I realize normal QS has by its nature very varying depth so this statement by Larry probably has to be read with caution

Eelco

[Karlo Bala]

Rajlich stated lot of things
What you see in Strelka about pruning is what is in R1.0

Can you post the reference (link...) of what you say?

No, I can not
You can believe me or not, but there is nothing interesting in R1.0 that is not already in Strelka

I'm not asm expert and I can't tell you anything about eval, but search calls is very easy to spot...

I disagree about it.

I believe that there are clearly interesting things in rybka that are not in strelka.
significant name of variables may be one of them.

Less ugly code when you replace many magic numbers by constants may be another one of them.

I think that if Vasik release the code of rybka1.0 he can lose from it not because of the fact that there are new things that are not in strelka but because it is going to be easier for people to understand the code and use the ideas.

I also think that the main secret of strelka or rybka is simply understanding fruit.

There are certainly original ideas in strelka but I think that thinking of original good ideas is an easier task relative to the task of understanding the code of other people.

The lesson from strelka is that people should not underestimate the value of understanding the source of other programs.

Last note about strelka is that I discovered more than one bug in strelka but I think that it is a bad idea to tell the public what are the bugs.

It is better to use the bugs to help to detect strelka clones in the future.

Uri

Yes, you are right about names. Also, lot of function in strelka are inlined, but in rybka source they are probably not (repetition detection, HT probes, etc.). But, I think that most interesting stuff are in eval, not in the search. Search is clear, fruit/glaurung search + 2-3 tricks. When I said that there is nothing new it was concerning search and pruning and I think it is obvious from strelka source.

Apparently this is not in Strelka sources then or I thought Uri or somebody else would have found it by now?

By lkaufman Date 2008-02-20 01:20 Suppose that the first iteration in a hypothetical program was 1 ply with no quiescence search, the second allowed 1 ply of capture, the third allowed 2, the fourth 3, the fifth 4, the sixth 5, and the seventh unlimited (or whatever maximum might be used). Then the eighth iteration would be 2 ply with full quiescence etc. This is a crude approximation to the situation with Rybka. Currently we would call the seventh iteration "1 ply" in this hypothetical program. You would call the very first (or perhaps second) one "1 ply". Your solution might be technically "correct", but it would hardly be consistent with standard industry practice. I say that the first iteration to count is the first one that plays at some relatively minimal level, maybe 1200 or 1300 Elo. That means for Rybka 3 probably starting two levels of quiescence earlier than we do now.

By BB Date 2008-02-20 02:25 > Currently we would call the seventh iteration "1 ply" in this hypothetical program.


I would probably use fractional ply to describe the situation between iteration 1 and iteration 7 in this case (it is not clear to me if the term "iterative deepening" should apply for these first iterations, as it could be argued that they use substantively dissimilar methodologies). Perhaps 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 1.0, 2.0, though the decimals would be place-holders rather than connoting any arithmetic meaning. Alternatively, the UCI-variable seldepth could give some notion of this. Or, if you use various qsearch-es throughout the search, two "depths" could be returned at any time: the horizon-distance (from the root), and the qsearch-thoroughness. In any event, with your example, I would hope that the 7th iteration (1 ply + full q) and the 8th (2 ply + full q) would have depths that differ by 1. As I indicate above, without the rigidity of the iterative deepening framework (which I realise is perhaps too strong an assumption to have broad validity in modern chess engines), the particularities of the labelling of iterations vis-a-vis depth becomes much less clear. On the other hand, I can't say that I have great sentiment toward re-construing "depth" merely to conform to the numerology of previous times. [I am reminded of the "rated speed" of various processors, which was supposed to ease comparisons for consumers, but didn't always deliver such a result].

I think the question is, if Rybka's and Vasik's first implementation of this is not cloned by Osipov in Strelka then is it really helping much, else Strelka would have a lower rating - of course the Strelka 1.0 clone certainly had a much lower rating than Rybka 1.0 - , and the second question is; whether iterative deepening in Quiescence Search was tried before in the past and found to be not feasible if you don't make some changes to normal iterative deepening? It seems like a signicant search idea though to me, I have never heard of it before. I realize normal QS has by its nature very varying depth so this statement by Larry probably has to be read with caution

Eelco

It could be interesting to do iterative QS. I thought about it but didn't have enough time to try. Maybe Rebel has some similar tricks inside, but I'm sure that lot of people try this idea before (maybe prof. Hyatt, etc.). Lot of nice tricks are forgotten because of todays very fast computers. Anyway there is not such thing in R1.0

[Tony]

Rajlich stated lot of things
What you see in Strelka about pruning is what is in R1.0

Can you post the reference (link...) of what you say?

No, I can not
You can believe me or not, but there is nothing interesting in R1.0 that is not already in Strelka

I'm not asm expert and I can't tell you anything about eval, but search calls is very easy to spot...

I disagree about it.

I believe that there are clearly interesting things in rybka that are not in strelka.
significant name of variables may be one of them.

Less ugly code when you replace many magic numbers by constants may be another one of them.

I think that if Vasik release the code of rybka1.0 he can lose from it not because of the fact that there are new things that are not in strelka but because it is going to be easier for people to understand the code and use the ideas.

I also think that the main secret of strelka or rybka is simply understanding fruit.

There are certainly original ideas in strelka but I think that thinking of original good ideas is an easier task relative to the task of understanding the code of other people.

The lesson from strelka is that people should not underestimate the value of understanding the source of other programs.

Last note about strelka is that I discovered more than one bug in strelka but I think that it is a bad idea to tell the public what are the bugs.

It is better to use the bugs to help to detect strelka clones in the future.

Uri

Yes, you are right about names. Also, lot of function in strelka are inlined, but in rybka source they are probably not (repetition detection, HT probes, etc.). But, I think that most interesting stuff are in eval, not in the search. Search is clear, fruit/glaurung search + 2-3 tricks. When I said that there is nothing new it was concerning search and pruning and I think it is obvious from strelka source.

Apparently this is not in Strelka sources then or I thought Uri or somebody else would have found it by now?

By lkaufman Date 2008-02-20 01:20 Suppose that the first iteration in a hypothetical program was 1 ply with no quiescence search, the second allowed 1 ply of capture, the third allowed 2, the fourth 3, the fifth 4, the sixth 5, and the seventh unlimited (or whatever maximum might be used). Then the eighth iteration would be 2 ply with full quiescence etc. This is a crude approximation to the situation with Rybka. Currently we would call the seventh iteration "1 ply" in this hypothetical program. You would call the very first (or perhaps second) one "1 ply". Your solution might be technically "correct", but it would hardly be consistent with standard industry practice. I say that the first iteration to count is the first one that plays at some relatively minimal level, maybe 1200 or 1300 Elo. That means for Rybka 3 probably starting two levels of quiescence earlier than we do now.

By BB Date 2008-02-20 02:25 > Currently we would call the seventh iteration "1 ply" in this hypothetical program.


I would probably use fractional ply to describe the situation between iteration 1 and iteration 7 in this case (it is not clear to me if the term "iterative deepening" should apply for these first iterations, as it could be argued that they use substantively dissimilar methodologies). Perhaps 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 1.0, 2.0, though the decimals would be place-holders rather than connoting any arithmetic meaning. Alternatively, the UCI-variable seldepth could give some notion of this. Or, if you use various qsearch-es throughout the search, two "depths" could be returned at any time: the horizon-distance (from the root), and the qsearch-thoroughness. In any event, with your example, I would hope that the 7th iteration (1 ply + full q) and the 8th (2 ply + full q) would have depths that differ by 1. As I indicate above, without the rigidity of the iterative deepening framework (which I realise is perhaps too strong an assumption to have broad validity in modern chess engines), the particularities of the labelling of iterations vis-a-vis depth becomes much less clear. On the other hand, I can't say that I have great sentiment toward re-construing "depth" merely to conform to the numerology of previous times. [I am reminded of the "rated speed" of various processors, which was supposed to ease comparisons for consumers, but didn't always deliver such a result].

I think the question is, if Rybka's and Vasik's first implementation of this is not cloned by Osipov in Strelka then is it really helping much, else Strelka would have a lower rating - of course the Strelka 1.0 clone certainly had a much lower rating than Rybka 1.0 - , and the second question is; whether iterative deepening in Quiescence Search was tried before in the past and found to be not feasible if you don't make some changes to normal iterative deepening? It seems like a signicant search idea though to me, I have never heard of it before. I realize normal QS has by its nature very varying depth so this statement by Larry probably has to be read with caution

Eelco

Sounds to me like an idea from someone without (or little) experience. I really see no way how destabelizing qsearch would gain anything.

Most of the time qsearch is very shallow, so searching 2,4,7 ply deeper wouldn't mean anything.

When qsearch is deeper, cutting off a recapture would be pretty bad.

Besides that, researching the same line several times isn't very efficient either.

What I can imagine however is a search between normal and qsearch, where several promising moves are tried (where promising is depth related) besides captures.

Tony

[Karlo Bala]

Rajlich stated lot of things
What you see in Strelka about pruning is what is in R1.0

Can you post the reference (link...) of what you say?

No, I can not
You can believe me or not, but there is nothing interesting in R1.0 that is not already in Strelka

I'm not asm expert and I can't tell you anything about eval, but search calls is very easy to spot...

I disagree about it.

I believe that there are clearly interesting things in rybka that are not in strelka.
significant name of variables may be one of them.

Less ugly code when you replace many magic numbers by constants may be another one of them.

I think that if Vasik release the code of rybka1.0 he can lose from it not because of the fact that there are new things that are not in strelka but because it is going to be easier for people to understand the code and use the ideas.

I also think that the main secret of strelka or rybka is simply understanding fruit.

There are certainly original ideas in strelka but I think that thinking of original good ideas is an easier task relative to the task of understanding the code of other people.

The lesson from strelka is that people should not underestimate the value of understanding the source of other programs.

Last note about strelka is that I discovered more than one bug in strelka but I think that it is a bad idea to tell the public what are the bugs.

It is better to use the bugs to help to detect strelka clones in the future.

Uri

Yes, you are right about names. Also, lot of function in strelka are inlined, but in rybka source they are probably not (repetition detection, HT probes, etc.). But, I think that most interesting stuff are in eval, not in the search. Search is clear, fruit/glaurung search + 2-3 tricks. When I said that there is nothing new it was concerning search and pruning and I think it is obvious from strelka source.

Apparently this is not in Strelka sources then or I thought Uri or somebody else would have found it by now?

By lkaufman Date 2008-02-20 01:20 Suppose that the first iteration in a hypothetical program was 1 ply with no quiescence search, the second allowed 1 ply of capture, the third allowed 2, the fourth 3, the fifth 4, the sixth 5, and the seventh unlimited (or whatever maximum might be used). Then the eighth iteration would be 2 ply with full quiescence etc. This is a crude approximation to the situation with Rybka. Currently we would call the seventh iteration "1 ply" in this hypothetical program. You would call the very first (or perhaps second) one "1 ply". Your solution might be technically "correct", but it would hardly be consistent with standard industry practice. I say that the first iteration to count is the first one that plays at some relatively minimal level, maybe 1200 or 1300 Elo. That means for Rybka 3 probably starting two levels of quiescence earlier than we do now.

By BB Date 2008-02-20 02:25 > Currently we would call the seventh iteration "1 ply" in this hypothetical program.


I would probably use fractional ply to describe the situation between iteration 1 and iteration 7 in this case (it is not clear to me if the term "iterative deepening" should apply for these first iterations, as it could be argued that they use substantively dissimilar methodologies). Perhaps 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 1.0, 2.0, though the decimals would be place-holders rather than connoting any arithmetic meaning. Alternatively, the UCI-variable seldepth could give some notion of this. Or, if you use various qsearch-es throughout the search, two "depths" could be returned at any time: the horizon-distance (from the root), and the qsearch-thoroughness. In any event, with your example, I would hope that the 7th iteration (1 ply + full q) and the 8th (2 ply + full q) would have depths that differ by 1. As I indicate above, without the rigidity of the iterative deepening framework (which I realise is perhaps too strong an assumption to have broad validity in modern chess engines), the particularities of the labelling of iterations vis-a-vis depth becomes much less clear. On the other hand, I can't say that I have great sentiment toward re-construing "depth" merely to conform to the numerology of previous times. [I am reminded of the "rated speed" of various processors, which was supposed to ease comparisons for consumers, but didn't always deliver such a result].

I think the question is, if Rybka's and Vasik's first implementation of this is not cloned by Osipov in Strelka then is it really helping much, else Strelka would have a lower rating - of course the Strelka 1.0 clone certainly had a much lower rating than Rybka 1.0 - , and the second question is; whether iterative deepening in Quiescence Search was tried before in the past and found to be not feasible if you don't make some changes to normal iterative deepening? It seems like a signicant search idea though to me, I have never heard of it before. I realize normal QS has by its nature very varying depth so this statement by Larry probably has to be read with caution

Eelco

Sounds to me like an idea from someone without (or little) experience. I really see no way how destabelizing qsearch would gain anything.

Most of the time qsearch is very shallow, so searching 2,4,7 ply deeper wouldn't mean anything.

When qsearch is deeper, cutting off a recapture would be pretty bad.

Besides that, researching the same line several times isn't very efficient either.

What I can imagine however is a search between normal and qsearch, where several promising moves are tried (where promising is depth related) besides captures.

Tony

Eelco probably had something similar in mind. Also, researching is very inefficient without hashing, and with hashing it is not pure QS.
To be honest, one must be very naive to believe that someone who already have strongest engine in the World will open his secrets. I think it is just try to guide young (perspective) programmers in wrong direction (it wouldn't be the first time).