Null driven IID

[mcostalba]

Null capture is a cut-node detector.

There is a link between the capture that makes your null search failing low and the probability that you are on a cut-node.

Namely, given:

nullValue: The value returned by the null search

threatCapture: the capture that made your null search failing low (nullValue < beta)

SEE: the SEE value of threatCapture calculated just after the null search, before to undo the null move.

If the following relation stands:

Code: Select all

    nullValue + SEE(threatCapture) >= beta  (1)

Then with an high probability you are on a cut-node.

If you still don't have a TT move then this is a very good time to start an IID because you have an high probability to find one.

The rationale, as I had made up for myself, is the following: if a null move fails low due to a capture there is the possibility that this capture is just an artifact due to null move side to move change and that, without the side to move change, the capture would be non-existant (the threatened piece moves away) or even reversed (the threatened piece captures the threatener).

The capture yields to the opponent an additional value of SEE(threatMove), so we can write the value returned by null search (from the opponent side of view) as the sum of two contributes:

Code: Select all

   nullValue = -(EffectivePositionValue + SEE(threatMove))  (2)

Where EffectivePositionValue is the value _without_ considering the capture. From the above relation, adding the SEE part two both members of (2) we have:

Code: Select all

   nullValue + SEE(threatCapture) = (-EffectivePositionValue)

So when relation (1) stands we have:

Code: Select all

   (-EffectivePositionValue) >= beta

And, if the capture is really just an artifact, we can detect that we are in a fail-high position.

I have upload here

http://www.mediafire.com/?sharekey=f197 ... b9a8902bda

Stockfish 1.1a where you can see the actual code. The only difference from Stockfish 1.1 is the Null driven IID logic and the fact that is enabled by default (I am an optimistic guy and can be
set/unset as an UCI parameter.


After more then 500 games at 1'+0 Null driven IID seems better then standard, although not much.

Please note that IID kicks-in only at high depths, currently depth > 6, so on ultra fast games, where average depth is not very high, could be difficult to spot any difference.

I have also done some tests on a set of positions to measure the probability to find a TT move after an IID search in a non-PV node. Just as a note, I remember that to find a TT move it means that the node has failed high.

It seems that we go from 30-35% of cases when considering only the IID margin:

Code: Select all

if (depth > 6 * OnePly && evaluate() > beta -IIDmargin)
   startIID();

To more then 60% when the triggering of the IID is the null move capture as described above.


Marco

[Uri Blass]

Null capture is a cut-node detector.

There is a link between the capture that makes your null search failing low and the probability that you are on a cut-node.

Namely, given:

nullValue: The value returned by the null search

threatCapture: the capture that made your null search failing low (nullValue < beta)

SEE: the SEE value of threatCapture calculated just after the null search, before to undo the null move.

If the following relation stands:

Code: Select all

    nullValue + SEE(threatCapture) >= beta  (1)

Then with an high probability you are on a cut-node.

If you still don't have a TT move then this is a very good time to start an IID because you have an high probability to find one.

The rationale, as I had made up for myself, is the following: if a null move fails low due to a capture there is the possibility that this capture is just an artifact due to null move side to move change and that, without the side to move change, the capture would be non-existant (the threatened piece moves away) or even reversed (the threatened piece captures the threatener).

The capture yields to the opponent an additional value of SEE(threatMove), so we can write the value returned by null search (from the opponent side of view) as the sum of two contributes:

Code: Select all

   nullValue = -(EffectivePositionValue + SEE(threatMove))  (2)

Where EffectivePositionValue is the value _without_ considering the capture. From the above relation, adding the SEE part two both members of (2) we have:

Code: Select all

   nullValue + SEE(threatCapture) = (-EffectivePositionValue)

So when relation (1) stands we have:

Code: Select all

   (-EffectivePositionValue) >= beta

And, if the capture is really just an artifact, we can detect that we are in a fail-high position.

I have upload here

http://www.mediafire.com/?sharekey=f197 ... b9a8902bda

Stockfish 1.1a where you can see the actual code. The only difference from Stockfish 1.1 is the Null driven IID logic and the fact that is enabled by default (I am an optimistic guy and can be
set/unset as an UCI parameter.


After more then 500 games at 1'+0 Null driven IID seems better then standard, although not much.

Please note that IID kicks-in only at high depths, currently depth > 6, so on ultra fast games, where average depth is not very high, could be difficult to spot any difference.

I have also done some tests on a set of positions to measure the probability to find a TT move after an IID search in a non-PV node. Just as a note, I remember that to find a TT move it means that the node has failed high.

It seems that we go from 30-35% of cases when considering only the IID margin:

Code: Select all

if (depth > 6 * OnePly && evaluate() > beta -IIDmargin)
   startIID();

To more then 60% when the triggering of the IID is the null move capture as described above.


Marco

I do not fully understand your post.

In my case I use fail hard and null search is done with minimal window so I can get or beta or beta-1
Do you use fail soft so you can get also smaller values than beta-1

I can add that it is better to give some diagram and example and if I see in some diagram what the terms mean it can help to understand what you mean.

I basically understood that your idea is to do iid when the null move fail low because of a good capture.


Uri

[mcostalba]

I can add that it is better to give some diagram and example and if I see in some diagram what the terms mean it can help to understand what you mean.

Uri

Let's start with the usual simplified position

[d]7k/8/b7/8/8/8/4B3/2K5 w - - 0 1

It is white turn, let's say that beta == 0, so until now we have an even score between white and black.

Now here we go in our search() function.

First thing our search does is to evaluate the null move (no checks pending, so we go with the null search).

The null move changes the side to move and gives the turn to black, the black finds then the winning ..Bxf2, the null search then returns with

nullValue = -300

Let's say that the bishop value is 300.

Because nullValue < beta, with our example numbers -300 < 0, the null move fails low and we need to continue searching this node with a full normal search.

Now enters the null capture stuff, subject of this post.

Before to go with normal search we check the following:

- Is the null failed low? --> Yes it is.

- Do we already have a TT move for this position? Sorry, no we don't.

- Is the treathing move a capture? --> Yes it is, ..Bxf2

- What is the SEE of the capture? ---> it is 300

- Does nullValue + SEE >= beta? ----> Yes, -300 + 300 >= 0 !!!

If all the above is true (and it is) then _perhaps_ although the null failed low we are not in such a bad situation, _perhaps_ the null failed low due to a capture artifact. It smells like this is a cut-node anyway!

Then ? what to do ?

Let's try a cheap IID on this position and see if we can find a TT move.....hey...yes...we have a TT move, it is Bxa6

Oh now that we have a tt move let's start _ANYWAY_ the normal search, but with a precious TT move in our pocket: if the TT move will be good then our normal search will be much faster then without the TT.

Hope is a bit more clear now.

Marco

[Uri Blass]

I understand but the question is why do you need move in the hash tables to search the right move first.

Good captures are searched first even if you have no move in the hash tables to start.

Another point is that you get NullValue=-300 only because you search to small depth.

searching to bigger depth may give line like Bxe2 Kd2 Bd1 Kxd1 when position is equal unless your order of moves is good enough to avoid Bd1 first.

I think that if you look for improvements then maybe improvement in the order of moves by static evaluation in order not to start with bad moves can be a good direction.

Uri

[hgm]

In Joker I would always do IID if the null-move failed low. I would even do IID on the null move itself. And because there are some that claim this is a huge waste of time, I tried to suppress all IID iterations but the first (which basically amounts to enhanced transposition cutoff, and hardly takes any time), but it did not seem to improve playing strength a bit.

Joker does throw a SEE on the null-move refutation, if it is a capture. And if this threat is enough to explain the fail low, according to the condition you describe, I alter the move ordering by increasing the sort key of all captures with the threatened piece and of its lowest-valued attacker with this SEE value. In addition I do sort the first non-capture with the threatened piece to a safe square (i.e. a non-capture with SEE=0) with the captures, (also uppgraded by the threat SEE, as this is also a move with the threatened piece), as in absence of even more profitable captures, this move is usually the best cut-move candidate.

To also give an example diagram:

[D]1k6/1p6/p7/1Q6/6rr/7P/6P1/6K1 w

Here Joker would try, after the null move failed because of PxQ, Qc5 (say) before PxQ. Despite the fact that the PxR has a victim value of 500, because the move Qc5 does have SEE=0 and gets upgraded by 900, for a total of 900 > 500. The move Qxa6 does have a victim value of 100, but, as it is a HxL capture, would be sorted according to SEE, and not victim value. The SEE equals -800 for this move, and the upgrade because it capture the attacker or moves the threatened piece is 900, for a total of +100 < 900. Should the moves Qb4 of Qc6 have been generated before Qc5, they would not have been ranked with the captures, as they have SEE=0.

[mcostalba]

I understand but the question is why do you need move in the hash tables to search the right move first.

Good captures are searched first even if you have no move in the hash tables to start.

Probably my example was not careful chosen, but a TT move doesn't need to be a capture. As example

[d] 4k3/1p2P3/b2P4/8/8/3B4/1K6/8 w - - 0 1


In this case the TT move turns out to be Bg6+, although, also in this case the null search fails low due to ..Bxd3

Another point is that you get NullValue=-300 only because you search to small depth.

searching to bigger depth may give line like Bxe2 Kd2 Bd1 Kxd1 when position is equal unless your order of moves is good enough to avoid Bd1 first.

Yes, of course, that's the reason we do the normal search at the end. The point here is to find a TT move. But you cannot find a TT move if you are not in a cut-node, so when you have some 'trigger' or 'hints' or call as you want that says to you "Hey, this is _probably_ a cut-node" then it's up to you how to handle this information. You can also ignore it, but I would think that, because is a valuable info, although not sure at 100% but only with good probability, we are aimed at finding a way to use it.


Marco

[mcostalba]

In Joker I would always do IID if the null-move failed low. I would even do IID on the null move itself. And because there are some that claim this is a huge waste of time, I tried to suppress all IID iterations but the first (which basically amounts to enhanced transposition cutoff, and hardly takes any time), but it did not seem to improve playing strength a bit.

Also in Stockfish/Glaurung you can set the option to do a IID always when the null-move fails low. BUt you are playing blindly!

The point is it is a total wast of time doing an IID on an ALL node.

IID are useful ONLY on cut-nodes. So null driven IID is a selected IID that enables you to do IID _mostly_ on cut-nodes and not always. Let's say it should increase the efficency of IID because you do not shot blindly anymore.

Joker does throw a SEE on the null-move refutation, if it is a capture. And if this threat is enough to explain the fail low, according to the condition you describe, I alter the move ordering by increasing the sort key of all captures with the threatened piece and of its lowest-valued attacker with this SEE value. In addition I do sort the first non-capture with the threatened piece to a safe square (i.e. a non-capture with SEE=0) with the captures, (also uppgraded by the threat SEE, as this is also a move with the threatened piece), as in absence of even more profitable captures, this move is usually the best cut-move candidate.

We need to separate the two concepts.

One thing is to recongize a node as a cut-node, i.e. a node for which a TT move exsists (and it doesn't need to be a capture BTW).

Another thing is to _find_ the tt move, or best move, as you wish to call it.

These are two different and orthogonal concepts in my scheme. The SEE trick is used only for the first point, not for the second.

It is the IID that has the sole responsability to find the best move.

The SEE just triggers the IID, but do not subsitute it, nor aims to do so.

Marco

[hgm]

The point is it is a total wast of time doing an IID on an ALL node.

I never believed that, and never have been able to verify it in tests. The problem is that you never know with 100% certainty that something is an all node. And even if you are 97% certain, the 3% probability that it is a cut-node after all can make the IID on suspected all-nodes very worthwile, by discovering this early.

IID are useful ONLY on cut-nodes. So null driven IID is a selected IID that enables you to do IID _mostly_ on cut-nodes and not always. Let's say it should increase the efficency of IID because you do not shot blindly anymore.

Joker does throw a SEE on the null-move refutation, if it is a capture. And if this threat is enough to explain the fail low, according to the condition you describe, I alter the move ordering by increasing the sort key of all captures with the threatened piece and of its lowest-valued attacker with this SEE value. In addition I do sort the first non-capture with the threatened piece to a safe square (i.e. a non-capture with SEE=0) with the captures, (also uppgraded by the threat SEE, as this is also a move with the threatened piece), as in absence of even more profitable captures, this move is usually the best cut-move candidate.

We need to separate the two concepts.

One thing is to recongize a node as a cut-node, i.e. a node for which a TT move exsists (and it doesn't need to be a capture BTW).

Another thing is to _find_ the tt move, or best move, as you wish to call it.

These are two different and orthogonal concepts in my scheme. The SEE trick is used only for the first point, not for the second.

It is the IID that has the sole responsability to find the best move.

The SEE just triggers the IID, but do not subsitute it, nor aims to do so.

Marco

Well, even with IID, you have to start with some move. And if you start immediately with a cut-move, you safe time by not having to look at the other moves. In fact, IID is much more waste of effort in a case where it is so easy to find the cut move statically, than it would be in case of a suspected all-node (where a cut-move will always come as a surprise).

Due to the self-deepening implementation of IID in Joker, in practice the IID is delegated entirely to the daughter all-node in case it identifies a cut-move candidate (at non-terminal depth), so there is no overhead. Provided you don't waste any time on searching cut-move candidates first that have no hope to succeed.

[Jim Ablett]

Stockfish 1.1a by Marco Costalba

Windows win32 & x64 pgo compiles.

http://www.mediafire.com/?vumzyeugkmy

Jim.

[mcostalba]

Stockfish 1.1a by Marco Costalba

Windows win32 & x64 pgo compiles.

http://www.mediafire.com/?vumzyeugkmy

Jim.

Thanks Jim!