Nodes type clarification.

[hgm]

OK, thanks for the clarification. So it includes the hash move, but not the null move.

I am still doubting, then, that this number has any bearing on the usefulness of IID. Above, you wrote this:

But you are missing the _key_ point. At a node where we are going to fail high, as opposed to a node where we will search all moves, when we fail high, we do so 90+% of the time on the _first_ move searched. Without using IID at all. So you have 10% (or less) to make an improvement in. Not much room. IID is not free.

When I do IID, I also do it on the null move. Even if I would have a 100% probability that I would always pick the correct cut move, if there is one, from amongst the real moves, I still could benifit from IID by abandoning the null move at lower depth when it turns out to be no good. This seems to falsify your statement above.

In the second place, including the hash move in the count makes the percentage rather meaningless for calculating if IID could help, as one typically does not do IID if a hash move is available. Most of the time (when the search is stable, and your 92% is valid and has not dropped to a lower value of a root fail) the hash move would be the best move from a one-less-deep search, and there would be nothing to iterate: the only 'iteration' not yet done is the final one.

The question was: "would it be useful to do IID in nodes where no hash move or hash depth is available?" If the overwhelming majority of the nodes included in the statistic you give could never trigger IID, I don't see how the number could tell us anything about the cost/benifit of IID. What is relevant is how the chances for a quick cut move without IID are in cases where you would actually do IID. I.e where the node was not searched before at any depth, so no hash move, and you till had to decide if you were going to try a real move or a null move.

[bob]

OK, thanks for the clarification. So it includes the hash move, but not the null move.

I am still doubting, then, that this number has any bearing on the usefulness of IID. Above, you wrote this:

But you are missing the _key_ point. At a node where we are going to fail high, as opposed to a node where we will search all moves, when we fail high, we do so 90+% of the time on the _first_ move searched. Without using IID at all. So you have 10% (or less) to make an improvement in. Not much room. IID is not free.

When I do IID, I also do it on the null move. Even if I would have a 100% probability that I would always pick the correct cut move, if there is one, from amongst the real moves, I still could benifit from IID by abandoning the null move at lower depth when it turns out to be no good. This seems to falsify your statement above.

In the second place, including the hash move in the count makes the percentage rather meaningless for calculating if IID could help, as one typically does not do IID if a hash move is available. Most of the time (when the search is stable, and your 92% is valid and has not dropped to a lower value of a root fail) the hash move would be the best move from a one-less-deep search, and there would be nothing to iterate: the only 'iteration' not yet done is the final one.

The question was: "would it be useful to do IID in nodes where no hash move or hash depth is available?" If the overwhelming majority of the nodes included in the statistic you give could never trigger IID, I don't see how the number could tell us anything about the cost/benifit of IID. What is relevant is how the chances for a quick cut move without IID are in cases where you would actually do IID. I.e where the node was not searched before at any depth, so no hash move, and you till had to decide if you were going to try a real move or a null move.

I ran some tests on this using Crafty, when I had some free cluster time and nothing else to do. Default IID only fires when I have no hash move and the alpha/beta window is as set at the root (PV nodes). I modified it to fire if there was no hash move period. Huge performance hit. 100 Elo down before I aborted the test, because it slows things down too much. I twiddled with as many alternatives as I could think of, and in my code at least, IID at anything but pure PV nodes hurts. Turning it off was surprising in that it made very little measurable difference (roughly 1 elo over 32K games, although the error range for with and without are +/- 4 so I just concluded "equal" and let it go. I have seen positions where it helps, but they might not be as frequent as I thought based on testing.

[hgm]

100 Elo corresponds to approximately a factor 3 slowdown in most engines. Doesn't it strike you very suspicious that you woud lose such a large factor in terms of speed?

If the effective branching ratio of your engine is 3-4, and you deepen in steps of 2 ply, it should multiply the work in every node by 1.11-1.06 (i.e. multiply the branching ratio with that factor). You would pretty much have to do that in every node to triple your search time at d=16.

How many of your (d>=2) nodes have no hash move? It can't be that many, or you might as well not hash at all!

You were not by any chance doing IID in every all-node because you don't store a hash move in nodes that fail low? If you can see in the hash that the node failed low before at nearly (but not quite) the same depth as is requeted now, IID would of coure be a waste of time, as you would simply be re-doing what the hash table already told you.

[bob]

100 Elo corresponds to approximately a factor 3 slowdown in most engines. Doesn't it strike you very suspicious that you woud lose such a large factor in terms of speed?

No. Too many IID searches. Remember I tried it at any node where I had no hash move, which is something on the order of 90% of all nodes I search. I reduced that by restricting it to nodes where I might possibly fail high based on a null-search value, or on a shallow-draft hash move, or whatever. And each restriction improved the result until I returned to the "only at PV nodes" where I am now...

At an ALL node, IID is a 100% waste of time. At many CUT nodes a capture will do the trick quite well, without a search to find the move to search first. That was my original point. I already fail high on the first move 92% of the time typically, so IID could only help on the other 8% (or maybe even less as some moves are not obvious until searched to full depth so IID has no hope).




[/quote]

If the effective branching ratio of your engine is 3-4, and you deepen in steps of 2 ply, it should multiply the work in every node by 1.11-1.06 (i.e. multiply the branching ratio with that factor). You would pretty much have to do that in every node to triple your search time at d=16.

How many of your (d>=2) nodes have no hash move? It can't be that many, or you might as well not hash at all![/quote]

I have not measured this in several years and it would be worthwhile to do so. I used to expect 10% hits. I probably have the instrumentation in Crafty, I will look for som old data to see...

You were not by any chance doing IID in every all-node because you don't store a hash move in nodes that fail low? If you can see in the hash that the node failed low before at nearly (but not quite) the same depth as is requeted now, IID would of coure be a waste of time, as you would simply be re-doing what the hash table already told you.

I added that limit in fact, but in middlegame, there are not that many hash hits, so many (most) positions have no hint from the hash table as to what happened the last time around...