The "Secret" TT-move Singular Extension

[edwardyu]

I found from the chess programming wiki that this "secret" should not be discussed because it may be coming from RYBKA. However the STOCKFISH team has implemented this in their open-source engine.

I wish to know if this TT-move Singular Extension helps and for how much ELO.

Below is the implementation in my Xiangqi engine :-

Code: Select all

//Relaxed Singular extension
if (depth >= 6  //pv singular ext depth
&& tempmove.table.move==this_pv_move // this is hashmove
&& nSingular == 1
&& depth - nBetaDepth <= 3 // recent hash entry
&& newdepth < depth // not yet Ext   
&& abs&#40;nBetaVal&#41; < WIN_VALUE  
)
&#123;
	/*
	int b = nBetaVal - SINGULAR_MARGIN;
	int v = AlphaBeta&#40;sstack, b-1, depth/2, NULL_NO&#41;;
	if &#40;v < b&#41;
	*/
	int sing_size, sing_ncapsize, sing_val, sing_beta, sing_best; 
	MoveTabStruct sing_tempmove;
	sing_ncapsize = 0;
	sing_best = -INFINITY;
	sing_beta = nBetaVal - SINGULAR_MARGIN;
	
	sing_size=board.GenCap&#40;&movetab&#91;0&#93;, &ncapmovetab&#91;0&#93;, sing_ncapsize&#41;;
  memcpy&#40;&movetab&#91;sing_size&#93;, &ncapmovetab&#91;0&#93;, sing_ncapsize * 4&#41;;
  sing_size += sing_ncapsize;
 
  sing_ncapsize=board.GenNonCap&#40;&movetab&#91;sing_size&#93;);
  sing_size += sing_ncapsize;
  
	for &#40;int i = 0; i < sing_size; i++)
	&#123;
		sing_tempmove.tabentry = movetab&#91;i&#93;.tabentry;
		if &#40;sing_tempmove.table.move == this_pv_move&#41;
			 continue;	// skip hashmove
		if &#40;makemove<1>&#40;sing_tempmove.table&#41; < 0&#41;
			 continue; // skip illegal move	
		sing_val = -quiesCheck<0>(-sing_beta, -&#40;sing_beta-1&#41;, 0, qcheck_depth&#41;;
		unmakemove&#40;); 
		if &#40;sing_val > sing_best&#41;
		&#123;
			sing_best = sing_val;
		&#125;
	&#125;	//next i			
			
	if &#40;sing_best != -INFINITY && sing_best < sing_beta&#41;
	&#123;	
	//printf&#40;"info relaxed singular extension at pv, newdepth=%d, depth=%d, nBetaDepth=%d\n", newdepth, depth, nBetaDepth&#41;;
	//fflush&#40;stdout&#41;;
	pv_singular_cnt ++;
	newdepth = depth; //relaxed singleext 1 ply
  &#125;
&#125;	   

Note: nSingular is a bit I keep in TT. It is set to 1 if the difference between the best score and the 2nd best score is >= SINGULAR_MARGIN:-

Code: Select all

//  val >= best >= val >= best2nd >= val 
        if &#40;val <= best&#41;
        &#123;
        		if &#40;val > best2nd&#41;
        			best2nd = val;
        &#125;		
        else	  
        //if &#40;val > best&#41; 
        &#123;
            best2nd = best;
            
            best = val;
            if &#40;val >= beta&#41;
            &#123;                
                if &#40;nSingular == 0&#41;
                &#123;	
                	if &#40;best - best2nd >= SINGULAR_MARGIN&#41; // && best2nd != -INFINITY&#41; //64
                		nSingular = 1;
                &#125;
                else
                &#123;
                	nSingular = 0; //reset
                &#125;			
                RecordHash&#40;HASH_BETA, depth, val, tempmove.table.move, nSingular&#41;;

What is your comment on my implementation? Am I disclose the "secret" too much?

[Mangar]

Hi,

there has been some discussion here regarding this feature. If its helpful seems to depend from the chess engine. Some tried it wihout elo gain, some gained about 10-20 elo.

Greetings Volker

[bob]

I found from the chess programming wiki that this "secret" should not be discussed because it may be coming from RYBKA. However the STOCKFISH team has implemented this in their open-source engine.

I wish to know if this TT-move Singular Extension helps and for how much ELO.

Below is the implementation in my Xiangqi engine :-

Code: Select all

//Relaxed Singular extension
if (depth >= 6  //pv singular ext depth
&& tempmove.table.move==this_pv_move // this is hashmove
&& nSingular == 1
&& depth - nBetaDepth <= 3 // recent hash entry
&& newdepth < depth // not yet Ext   
&& abs&#40;nBetaVal&#41; < WIN_VALUE  
)
&#123;
	/*
	int b = nBetaVal - SINGULAR_MARGIN;
	int v = AlphaBeta&#40;sstack, b-1, depth/2, NULL_NO&#41;;
	if &#40;v < b&#41;
	*/
	int sing_size, sing_ncapsize, sing_val, sing_beta, sing_best; 
	MoveTabStruct sing_tempmove;
	sing_ncapsize = 0;
	sing_best = -INFINITY;
	sing_beta = nBetaVal - SINGULAR_MARGIN;
	
	sing_size=board.GenCap&#40;&movetab&#91;0&#93;, &ncapmovetab&#91;0&#93;, sing_ncapsize&#41;;
  memcpy&#40;&movetab&#91;sing_size&#93;, &ncapmovetab&#91;0&#93;, sing_ncapsize * 4&#41;;
  sing_size += sing_ncapsize;
 
  sing_ncapsize=board.GenNonCap&#40;&movetab&#91;sing_size&#93;);
  sing_size += sing_ncapsize;
  
	for &#40;int i = 0; i < sing_size; i++)
	&#123;
		sing_tempmove.tabentry = movetab&#91;i&#93;.tabentry;
		if &#40;sing_tempmove.table.move == this_pv_move&#41;
			 continue;	// skip hashmove
		if &#40;makemove<1>&#40;sing_tempmove.table&#41; < 0&#41;
			 continue; // skip illegal move	
		sing_val = -quiesCheck<0>(-sing_beta, -&#40;sing_beta-1&#41;, 0, qcheck_depth&#41;;
		unmakemove&#40;); 
		if &#40;sing_val > sing_best&#41;
		&#123;
			sing_best = sing_val;
		&#125;
	&#125;	//next i			
			
	if &#40;sing_best != -INFINITY && sing_best < sing_beta&#41;
	&#123;	
	//printf&#40;"info relaxed singular extension at pv, newdepth=%d, depth=%d, nBetaDepth=%d\n", newdepth, depth, nBetaDepth&#41;;
	//fflush&#40;stdout&#41;;
	pv_singular_cnt ++;
	newdepth = depth; //relaxed singleext 1 ply
  &#125;
&#125;	   

Note: nSingular is a bit I keep in TT. It is set to 1 if the difference between the best score and the 2nd best score is >= SINGULAR_MARGIN:-

Code: Select all

//  val >= best >= val >= best2nd >= val 
        if &#40;val <= best&#41;
        &#123;
        		if &#40;val > best2nd&#41;
        			best2nd = val;
        &#125;		
        else	  
        //if &#40;val > best&#41; 
        &#123;
            best2nd = best;
            
            best = val;
            if &#40;val >= beta&#41;
            &#123;                
                if &#40;nSingular == 0&#41;
                &#123;	
                	if &#40;best - best2nd >= SINGULAR_MARGIN&#41; // && best2nd != -INFINITY&#41; //64
                		nSingular = 1;
                &#125;
                else
                &#123;
                	nSingular = 0; //reset
                &#125;			
                RecordHash&#40;HASH_BETA, depth, val, tempmove.table.move, nSingular&#41;;

What is your comment on my implementation? Am I disclose the "secret" too much?

It is not a secret. In fact, I tested this a while back in Crafty and found no gain. I disabled it in stockfish and found no change either. It might be worth some tiny Elo gain, but it is not a significant change...

The idea is really not a very good one. Why would you only extend moves that survive in a hash entry for a while? This makes the extension sensitive to hash implementation, replacement strategy, hash size. And at best, in the middlegame, you might reach 10-20% hash hits, and only some of those will have a best move. What about the _rest_ of the tree???

[Don]

It is not a secret. In fact, I tested this a while back in Crafty and found no gain. I disabled it in stockfish and found no change either. It might be worth some tiny Elo gain, but it is not a significant change...

The idea is really not a very good one. Why would you only extend moves that survive in a hash entry for a while? This makes the extension sensitive to hash implementation, replacement strategy, hash size. And at best, in the middlegame, you might reach 10-20% hash hits, and only some of those will have a best move. What about the _rest_ of the tree???

I don't like it either. However, I tried to get rid of it and found that we cannot live without it. It's really quite helpful in Komodo and it's not a close call either.

When doch went to komodo and started getting really strong, this was one of the really big elo gains and it really surprised us. I don't really understand how things like this work so well on one program and not another. It may be a function of the other moves that get extended and perhaps it can be too redundant. Or another possibility is that you can tune your program around it such that if it's removed it hurts the program, but if you had never done it you would do several other things differently. I don't really know.

If anyone really wants to know I will make a version of komodo that allows you to switch this off if they will agree to run a statistically significant number of games. I have heard that in stockfish it only make a very small difference but I don't know first-hand.

Don

[mcostalba]

I have heard that in stockfish it only make a very small difference but I don't know first-hand.

We are now doing a test with exclusion search disabled. This is done for an unrelated aim, but it happens match is ongoing just in these days

So we could provide our test results as soon test finishes.

Regarding point raisen by Bob, I agree that is not fully clear to us why SE works, but it works. It seems we are much more careful then Bob on the assumption: "If I don't understand why it should work then it does not work" but actually he has also much more experience then us.

Anyhow, just to come back to something practical, the argument of the 20% of TT hits is bogus because we should consider only the hit rate for nodes elegible for SE, and so for high depth nodes (in SF 8 plyes and higher).

[bob]

I have heard that in stockfish it only make a very small difference but I don't know first-hand.

We are now doing a test with exclusion search disabled. This is done for an unrelated aim, but it happens match is ongoing just in these days

So we could provide our test results as soon test finishes.

Regarding point raisen by Bob, I agree that is not fully clear to us why SE works, but it works. It seems we are much more careful then Bob on the assumption: "If I don't understand why it should work then it does not work" but actually he has also much more experience then us.

Anyhow, just to come back to something practical, the argument of the 20% of TT hits is bogus because we should consider only the hit rate for nodes elegible for SE, and so for high depth nodes (in SF 8 plyes and higher).

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

In Hsu's implementation, which I mirrored (with great difficulty and effort) in the last two years of Cray Blitz, he took great pains to avoid being inconsistent about when a move is extended and when it is not. This approach (tt-extension) totally ignores any semblance of "fairness" about what gets extended vs what is not vs what can never be extended (if it isn't in the table at all).

[Don]

I have heard that in stockfish it only make a very small difference but I don't know first-hand.

We are now doing a test with exclusion search disabled. This is done for an unrelated aim, but it happens match is ongoing just in these days

So we could provide our test results as soon test finishes.

Regarding point raisen by Bob, I agree that is not fully clear to us why SE works, but it works. It seems we are much more careful then Bob on the assumption: "If I don't understand why it should work then it does not work" but actually he has also much more experience then us.

Anyhow, just to come back to something practical, the argument of the 20% of TT hits is bogus because we should consider only the hit rate for nodes elegible for SE, and so for high depth nodes (in SF 8 plyes and higher).

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

In Hsu's implementation, which I mirrored (with great difficulty and effort) in the last two years of Cray Blitz, he took great pains to avoid being inconsistent about when a move is extended and when it is not. This approach (tt-extension) totally ignores any semblance of "fairness" about what gets extended vs what is not vs what can never be extended (if it isn't in the table at all).

Bob, I think you are too anal about this. Every extension in any program is arbitrary. And so is the margin Hsu uses to test for singularity. I could use your same argument and say that it doesn't make sense to extend a move just because it happens to be 50 points better than the others, but not extend it if it's 49 points better - it seems rather arbitrary but some value has to be chosen.

There is also the point that the same move in the same position may get extended on this iteration but not on the next. Or not when it occurs in another part of the tree. I don't have an a pirori reason to believe that is a bad thing. If I can extend only 20% of the moves that really need to be extended that is better than zero percent isn't it?

I don't believe you can build a strong chess program that is "correct." You can solve the GHI problem, but at the expense of a much weaker program. If you want a "correct" program then you cannot use LMR either, because the first move might change, and the move ordering can be arbitrary from node to node and the window can change after any move.

I don't see any problem with this, unless of course it just doesn't test well for you which seems to be the case. I'm more interested in why it works for some and not others.

[mcostalba]

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

I meant to say another thing: As long as you go up with depths you have more tt hits.

I have done a quick statistics searching at fixed depth 15 on a bunch of positions.

TT hits _with_ TT move are of 27% in general, but if I consider only nodes at depth >= 8 plies then the TT hit rate with corresponding exsisting TT move jumps to 80% !!

[bob]

I have heard that in stockfish it only make a very small difference but I don't know first-hand.

We are now doing a test with exclusion search disabled. This is done for an unrelated aim, but it happens match is ongoing just in these days

So we could provide our test results as soon test finishes.

Regarding point raisen by Bob, I agree that is not fully clear to us why SE works, but it works. It seems we are much more careful then Bob on the assumption: "If I don't understand why it should work then it does not work" but actually he has also much more experience then us.

Anyhow, just to come back to something practical, the argument of the 20% of TT hits is bogus because we should consider only the hit rate for nodes elegible for SE, and so for high depth nodes (in SF 8 plyes and higher).

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

In Hsu's implementation, which I mirrored (with great difficulty and effort) in the last two years of Cray Blitz, he took great pains to avoid being inconsistent about when a move is extended and when it is not. This approach (tt-extension) totally ignores any semblance of "fairness" about what gets extended vs what is not vs what can never be extended (if it isn't in the table at all).

Bob, I think you are too anal about this. Every extension in any program is arbitrary. And so is the margin Hsu uses to test for singularity. I could use your same argument and say that it doesn't make sense to extend a move just because it happens to be 50 points better than the others, but not extend it if it's 49 points better - it seems rather arbitrary but some value has to be chosen.

There is also the point that the same move in the same position may get extended on this iteration but not on the next. Or not when it occurs in another part of the tree. I don't have an a pirori reason to believe that is a bad thing. If I can extend only 20% of the moves that really need to be extended that is better than zero percent isn't it?

I don't believe you can build a strong chess program that is "correct." You can solve the GHI problem, but at the expense of a much weaker program. If you want a "correct" program then you cannot use LMR either, because the first move might change, and the move ordering can be arbitrary from node to node and the window can change after any move.

I don't see any problem with this, unless of course it just doesn't test well for you which seems to be the case. I'm more interested in why it works for some and not others.

This is not about being "anal". It is about being consistent. Any reasonable criterion could work for selecting moves to extend or reduce. But what about a random one?

Nobody says everything has to be correct, but when you extend checks, do you extend them all, or just the ones that were TT hits? I don't extend 'em all, but I am consistent in why (SEE score). But something tells me that it would be much less effective to extend a random check here and there as opposed to extending some consistent set of checks (possibly all). Extending random checks might provide some very small benefit, or it might hurt in the cases where you extend a bad one and don't extend an important one...

That was my point. What is found in the TT is pretty random. That certainly doesn't seem like a reasonable way to select a set of positions for potential extension.

Again, an opinion based on testing, with some supporting results, but still just an opinion, not a statement of fact. It might work for some. It didn't do anything for Crafty (didn't hurt, but didn't help). Was a minimal improvement for stockfish. Not much else I can say...

[bob]

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

I meant to say another thing: As long as you go up with depths you have more tt hits.

I have done a quick statistics searching at fixed depth 15 on a bunch of positions.

TT hits _with_ TT move are of 27% in general, but if I consider only nodes at depth >= 8 plies then the TT hit rate with corresponding exsisting TT move jumps to 80% !!

Sounds badly wrong to me. 80% of your nodes are therefore "cut" nodes as opposed to "all" nodes (which have no best move)??? Also this would be more interesting with much longer searches to match the potential for large TT size...