Moderator: Ras
Not true. Tee common case is that the ALL node is a daugter of a CUT or PV node, from which IID is controlled anyway. So it will be repeatedly called from that parent node, for gradually increasing depth. So each time the ALL node is called, the fore-last iteration of what is needed now is found in the hash, so only the last iteration (the one you have to do anyway, even if you would not do IID) has to be done.bob wrote:The reason to not do it at ALL nodes is that move ordering is completely irrelevant there, and trying to improve on something that is irrelevant ends up just wasting time...
I have no idea what you are talking about. Ordering at ALL nodes is irrelevant, which makes IID at ALL nodes a complete waste of time since you find what you "think" is the best move and it is then useless. CUT nodes is where you need the best move first, and that is where IID comes into play. Reduced-depth searches to find a best move that will hopefully be best when we finally do the full-depth search.hgm wrote:Not true. Tee common case is that the ALL node is a daugter of a CUT or PV node, from which IID is controlled anyway. So it will be repeatedly called from that parent node, for gradually increasing depth. So each time the ALL node is called, the fore-last iteration of what is needed now is found in the hash, so only the last iteration (the one you have to do anyway, even if you would not do IID) has to be done.bob wrote:The reason to not do it at ALL nodes is that move ordering is completely irrelevant there, and trying to improve on something that is irrelevant ends up just wasting time...
So in fact doing IID from the underlying CUT node is extremely inefficient: it repeatedly calls the search on the ALL node to which its cut-move leads, with no other daughter nodes searched in between. So it will repeatedly generate moves in that ALL node, where a sngle move generation would have sufficed f you had been controlling the deepening from the ALL node, rather tan the CUT node (as in the self-deepening scheme).
And sometimes the guess for the node type was wrong, and the ALL node turns out to be a CUT node. So on the average, it saves time to do IID in suspected ALL nodes...
The problem that I recognized is that PV nodes are _critical_. A wrong move first and the tree explodes. That's why I only do IID there. At ALL/CUT nodes, thanks to null-move reductions, and and LMR-type reductions, the effort expended by IID was more expensive than the savings gained. I have tried this many times, but never got better results than when simply applying IID when there is no hash move on a PV node. PV nodes are the only place where reductions don't apply. The root PV node best move usually takes 90% of the search effort if not more. Getting it right is critical. Ditto for other PV nodes along the left-most edge of the graph. For my tests, IID elsewhere made the tree larger, not smaller. Perhaps if you don't do good captures first (SEE) or killer moves, this might pay off. But at traditional CUT nodes, I get a "good enough move" ordered first 92% of the time or so at no cost in extra searching. IID would need to improve on that while not losing more than it gains, which I don't see happening in my code at least.hgm wrote:The point is that if you could know in adance with 100% certainty which nodes are ALL nodes, searching them would be a waste of time in the first place, with or without IID. The whole tree to get to d=100 would count only a few thousand nodes.
In real life, unfortunately, sometimes a predicted ALL node misbehaves, and fails high. Say this happens in 1% of the cases. Than in 99% of the cases, IID would not help. In 98% of the cases it would involve no work at all, and in 1% of the cases you have to actually do a preliminary iteration, which might mean 10% extra work. So in total, 0.1% extra work.
But in the 1% of cases where a cut-move unexpectedly emerges, you might save a factor 20 on the search at the ultimate depth (starting with the cut move discovered in the IID pilot search, in stead of randomly stumbling on it halfway). So if we call the usual time it takes to search an ALL node at this depth 100%, without IID you would have taken you 50% (cutoff after 20 moves of 40), but with IID it only takes you 2.5% (cutoff after first move of 40) plus 5% for the pilot search (cutoff after 20 moves out of 40). So you save 42.5% on the search time of uch a misclassified ALL node, i.e. 0.4% in total.
So on average the IID in the alleged ALL nodes saves you 0.3%. That might not sound very a important saving, but this is of course because the assumtion that ALL nodes change into CUT nodes on deeper search is unrealistically optimistic.
I do not understand.hgm wrote:The point is that if you could know in adance with 100% certainty which nodes are ALL nodes, searching them would be a waste of time in the first place, with or without IID. The whole tree to get to d=100 would count only a few thousand nodes.
In real life, unfortunately, sometimes a predicted ALL node misbehaves, and fails high. Say this happens in 1% of the cases. Than in 99% of the cases, IID would not help. In 98% of the cases it would involve no work at all, and in 1% of the cases you have to actually do a preliminary iteration, which might mean 10% extra work. So in total, 0.1% extra work.
But in the 1% of cases where a cut-move unexpectedly emerges, you might save a factor 20 on the search at the ultimate depth (starting with the cut move discovered in the IID pilot search, in stead of randomly stumbling on it halfway). So if we call the usual time it takes to search an ALL node at this depth 100%, without IID you would have taken you 50% (cutoff after 20 moves of 40), but with IID it only takes you 2.5% (cutoff after first move of 40) plus 5% for the pilot search (cutoff after 20 moves out of 40). So you save 42.5% on the search time of uch a misclassified ALL node, i.e. 0.4% in total.
So on average the IID in the alleged ALL nodes saves you 0.3%. That might not sound very a important saving, but this is of course because the assumtion that ALL nodes change into CUT nodes on deeper search is unrealistically optimistic.
With reference to PV nodes (which is all I commented on above), assuming good move ordering just predicts that the left side of the tree is composed of pv nodes and that they don't occur elsewhere, which is exactly what I said.Pradu wrote:It is possible when you make the assumption that you have reasonably good move ordering on OPEN and CUT nodes (this is the assumption made when using PVS anyways).xsadar wrote:Another definition of PV node is any node in PVS that does not have a null window. This is because it is expected to be a PV node by the other definition, which you gave above (and would have to be either a PV node or a cut node by that definition if there were no search instability). If you are doing standard alpha-beta instead of PVS then to me, it seems impossible to predict which nodes are PV nodes beyond the left side of the tree.
In a stable search, the ALL node will have been searched before in a previous iteration controlled by a node closer to the root. (This an be the root itself through ID, or IID in the PV node the current branch sprouts from, or IID in the CUT node directly beow the ALL node.) In such a case IID is a no-op:Uri Blass wrote:How can you say that in 98% of the cases iid would involve no work at all?
The flaw is that this is an ALL node, so what point is there in doing a search (IID) that is going to fail low, and when you get back to the current position, you don't know a thing you didn't know before you started the process. Namely that you don't have a best move because there is no best move. If there is a best move, this is not an ALL node. Doing an IID search to the same depth as the current search makes absolutely no sense to me. And, in fact, all my IID searches are limited to a max of depth-2 anyway, but since when I am at a PV node with no hint of a best move, the depth-2 IID search won't have a hash move, and will first do a depth-4 IID search, which will do a depth-6 search, until depth-n is <= 0 where we start to do real searches and then back up the results by storing the best move in the hash table...hgm wrote:In a stable search, the ALL node will have been searched before in a previous iteration controlled by a node closer to the root. (This an be the root itself through ID, or IID in the PV node the current branch sprouts from, or IID in the CUT node directly beow the ALL node.) In such a case IID is a no-op:Uri Blass wrote:How can you say that in 98% of the cases iid would involve no work at all?
The search starts with probing the hash table for this node, gets a hit, and finds that it already has been searched to a depth one step lower then the currently requested depth. There is then no need to redo a search at that depth, or any depth below it. The only 'IID iteration' that is done is the final one, the full-depth search. The fact that the engine does IID in every node does not result in any extra work.
Only when you start searching a node that has not been searched in the previous iteration you can get into a situation where IID would actually have to do pilot searches at reuced depth. This happens when the underlying CUT node now searches a move that it did not search in the previous iteration. It only does this when its previous cut-move now has failed low. Under such conditions it is in fact very likely that the move they try to replace it with will fail low as well (meaning the current 'ALL node' is in fact a CUT node). You did not order that move after the previous cut-move for nothing. It is either a move that you did search (at lower depth) before you found the now-failing cut-move, and which failed low at that time, so you went on searching for another cut-move, or it is a move that was ordered behind the now-failing cut-move because you considerd it less likely to produce a cutoff.
On your last remark:
I do not try any moves at reduced depth (to get hash hits on them) if I know from the hash hit of the current node that these moves have already been searched at this depth (and all failed low).