iid and singular extensions

[Daniel Shawul]

I have been using IID at every node (including _ALL_ nodes) with a fairly
good reduced depth. I had used reduction of only 2 plies while using it at every node.
And this was actually working for me even though my move ordering was a good one with 90+% cutoff
rate in the first few moves. But later I abondened the intensive IIDing and started using
halved depths for non-pv nodes. Also this is done only at big depths of 7 or more.

Now I wanted to try out singular extensions, I thought maybe I could use the intensive IIDing
I used before (It was a win earlier but kind of no-loss later on). The advantage is that I get a move
to be tested for singularity at _every_ node. One can exclude _ALL_ nodes from IID and singularity
if need be. If we just check for a move in TT to be tested for singularity, for one it might not be
there and for another it might not be good enough (could be from very shallow search). The IID basically
takes care of these weakness (gets us a good enough move).

So I now do IID at PV/CUT nodes when I don't have a good enough hash move,
with a reduction of 2 for PV and 3 for CUT nodes. Then the test for singularity is
done by searching the rest of the moves with a further reduction of depth 2
(ofcourse with adjusted alpah-beta windows and such).

The point I am trying to make here is that instead of looking at IID as something to
improve move ordering , why not look at it as something to get a move to be tested for singularity
and make some adjustements ? Note that we also get a better move ordering in the latter case.
My implementation of these two shallow searches is very similar in many ways.
What do you think ?


Daniel

[bob]

I have been using IID at every node (including _ALL_ nodes) with a fairly
good reduced depth. I had used reduction of only 2 plies while using it at every node.
And this was actually working for me even though my move ordering was a good one with 90+% cutoff
rate in the first few moves. But later I abondened the intensive IIDing and started using
halved depths for non-pv nodes. Also this is done only at big depths of 7 or more.

Now I wanted to try out singular extensions, I thought maybe I could use the intensive IIDing
I used before (It was a win earlier but kind of no-loss later on). The advantage is that I get a move
to be tested for singularity at _every_ node. One can exclude _ALL_ nodes from IID and singularity
if need be. If we just check for a move in TT to be tested for singularity, for one it might not be
there and for another it might not be good enough (could be from very shallow search). The IID basically
takes care of these weakness (gets us a good enough move).

So I now do IID at PV/CUT nodes when I don't have a good enough hash move,
with a reduction of 2 for PV and 3 for CUT nodes. Then the test for singularity is
done by searching the rest of the moves with a further reduction of depth 2
(ofcourse with adjusted alpah-beta windows and such).

The point I am trying to make here is that instead of looking at IID as something to
improve move ordering , why not look at it as something to get a move to be tested for singularity
and make some adjustements ? Note that we also get a better move ordering in the latter case.
My implementation of these two shallow searches is very similar in many ways.
What do you think ?


Daniel

I don't follow the definition of "singular" you are using. The original definition (Hsu, Campbell) was that if you have a set of moves, and all but one fail low on a search of alpha-s, beta-s, and just one fails high on alpha, beta, then that move is singular and should be extended. Not sure how IID would be useful for that test...

[Daniel Shawul]

The test for singularity is done as you say.I am interested in the search done to find a move to be tested for singularity. Some engines test singularity of only the hash table move, which I think can be improved by using IID here. Most use very restriced form (depth/2,at PV nodes) or not at all.. The reason being the shallow search is too expensive if done for the sole purpose of move ordering. If you are going to use singular extensions,do also a heavy IID, so that you get the additional benefit of getting good enough moves at every node to test for singularity. IIRC the original proposal was to do a shallow search first to get the singular move,then search all but the proposed singular move with reduced depth and offseted windows. Some pseudo code to make things clearer

Code: Select all

 if(depth >= 4 && !hash_move) {
      hash_move = search(alpha,beta,depth - 3)
 } 
 if(hash_move && hash_move_depth - depth >= 3) {
      search(alpha - 50,alpha - 49,depth - 3 - 2);
 }

Now that I thought about it, it may not be a big deal.

[Aleks Peshkov]

Using IID it may be more easier to reduce (partially skip iteration) of all the rest non singular moves.

Voluntary changing zero-window looks like MTD methods... So smart TT subsystem became important to not lose extra information.

[Daniel Shawul]

Agreed. The potentially non-singular moves are searched twice with different windows (during IID & proof of singularity), so smart TT should help.
The fact that they are searched with different windows could sometimes result in completely different tree.

Code: Select all

if(depth >= 4 && !hash_move && PV_NODE ) {
      hash_move = search(alpha,beta,depth - IID_RED)      ...(1)
 }
 if(depth >= 6 && !ALL_NODE) {
      hash_move = search(alpha,beta,depth - SING_RED)     ...(2)
      search(alpha - 50,alpha - 49,depth - 5, Exclude hash_move);
 }

Basically what I am saying is to make search (1) and (2) same so that we use (1) only. Use IID_RED = SING_RED , do them at !ALL_NODE etc..
So with this it becomes

Code: Select all

if(depth >= 4 && !hash_move && !ALL_NODE ) {
      hash_move = search(alpha,beta,depth - IID_RED)
 }
 if(depth >= 6 && hash_move && !ALL_NODE) {
      search(alpha - 50,alpha - 49,depth - 5, Exclude hash_move);
 }

[Mangar]

If singular extension search is a good thing to do (I am not quite sure it is) then having a plan to use it on plys without hash move should be good too.

I saw the implementation of stockfish to use the hash move for a singular extension prediction. But I do not understand why stockfish does it.

Can´t you just wait for a move getting above alpha and then test all the others with a margin below alpha if they are able to reach that score? If there is none, just research the move above alpha with higher depth.

Greetings Volker

[mcostalba]

Can´t you just wait for a move getting above alpha and then test all the others with a margin below alpha if they are able to reach that score? If there is none, just research the move above alpha with higher depth.

If you search for all the other moves when you get a fail high and not when you need that info at the next iteration you end up with a lot of unuseful searches because in many cases you will not visit that position again in the future so it is absolutely wasted time (in many cases) to verify for singular extension condition so early, as soon as I get a cut off.

I have not tested this, so again, this is my just guess.

[Daniel Shawul]

I don't really understand why you do it that way, may be you can explain better. What I do is to set a flag during TT probe which tells me if a move is good for given alpha-beta window. This is basically for all hash cutoffs except upper bound (this cutoff is made because the move is worthless)

Code: Select all

if&#40;depth - 4 * UNITDEPTH <= h_depth
				&& &#40;flags == EXACT && score > alpha&#41; 
				|| &#40;flags == LOWER && score >= beta&#41;)
				return HASH_GOOD;

I know the flags=EXACT case is executed at PV nodes only and it rarely triggers, so ignoring it is probably is not that much of a difference. But why don't you check if score >= beta for LOWER bound ? A move found out to be good with much lower window than what we have now, is not necessarily good now. So your way actually does more singularity test if I am not mistaken. In other words if you have a move which failed high with (-30,-29) but now you are doing a (40,41) windows search, your method still tests for singularity.

Also the IID and search to prove singularity are really cheap and I don't believe that is the problem. What kills search depth is when I start extending all the singular moves I find. If I just do the test for singularity and not extend I barely see a difference during search to a fixed depth.
The singularity test is done with depth - 5 ( i see you do it depth/2) , so very cheap I say. Another doubt I have in relation to this is what depth to use for the IID and singularity test. For the "potentially singular move" a larger depth is used and for the rest using shallow depths may not be safe. Can anyone confirm that it is only the window that gets shifted (keeping the depth the same for the rest of the moves) ?

Another observation I made during my test, most of the singular moves with bigger singular margin windows are captures,singular evasions and rarely non-capture forks.. I have a !capture case for the singular test to to filter those out because I heard singular extension are not done for recaptures in the original proposal by Hsu et al.

Like Volker, I am yet to prove they work at all. I previously did the test at relatively fast time controls so maybe I will get surprised at longer tc.

[Harald]

Code: Select all

if&#40;depth - 4 * UNITDEPTH <= h_depth
				&& &#40;flags == EXACT && score > alpha&#41; 
				|| &#40;flags == LOWER && score >= beta&#41;)
				return HASH_GOOD;

If you really mean it than the layout is misleading. It should be written as

Code: Select all

if ( &#40;flags == EXACT && score > alpha&#41; && &#40;depth - 4 * UNITDEPTH <= h_depth&#41;
  || &#40;flags == LOWER && score >= beta&#41; )
    return HASH_GOOD;

Or do you mean this:

Code: Select all

if ( &#40;depth - 4 * UNITDEPTH <= h_depth&#41;
  && ( &#40;flags == EXACT && score > alpha&#41; 
    || &#40;flags == LOWER && score >= beta&#41;
   ) )
    return HASH_GOOD;

?

[Daniel Shawul]

Oops you just spotted a bug. This is the second time this week I found a bug due to forgetting stupid braces. I just learned my smart HT replacement was not working at all due to a missing brace after a year. Thanks! Yes I meant what you corrected of course. Lets see if I get an improvement...