killer trees
Posted: Mon Feb 23, 2015 11:32 am
The killer heuristic is a very effective move-ordering device. It provides the first move of the refutation tree of a move B when the refutation is similar to that of a sibbling A of B, which was searched before. And as most moves in all-nodes do basically the same (namely nothing), this happens quite often. But it only provides the first move of the refutation. The 3rd, 5th etc will have to be rediscovered for any continuation on the even moves (which are all-nodes). Once a continuation has been discovered on the deeper odd moves it will of course be communicated to the sibbling moves at that level by the killer heuristic, but not all moves will have the same refutation, so usually several continuations will have to be rediscovered from scratch.
This could be avoided by not just passing a killer move to sibblings, but the entire refutation tree.Then when A is refuted in some non-specific and non-trivial way (i.e. not by gobbling up the piece that was moved, and not by a null move), and sibbling B is an equivalent (read: equally pointless) move, the entire refutation of A can be grafted onto B. The moves of the analogous refutation tree in the corresponding node could be played immediately after the hash move, or even before it: the refutation tree was obtained at the same depth as the current search, while the hash move would be what is left from a previous deepening iteration, which was a search at lower depth.
Of course it sounds very expensive to represent entire trees in killer slots, and then pass them along. But in fact there is no need to to do that, as refutation trees are already stored in the transposition table. All that is needed is to store the hash key of the position after move A in a killer-like slot. So that this could be probed after move B. From this the search can see the hash-key (XOR) difference between the 'killer key' in the slot and its current key. This difference would remain constant in the grafted tree; if A and B were truly equivalent, all nodes of corresponding positions in the refutation tree of A would be obtained by XOR-ing the key for the current node with this 'analogy key'.
So all you have to do is pass along this analogy key through the search of B. So that in any node there the search could not only probe the TT for the position itself (to obtain the hash move), but also the analogous node, to retreive the hash move from there, and use it as 'analogy killer'. The latter probes should be cheap, as the entries were stored recently, during the search of sibbling A, and should still be cached. (Quite unlike the probes for the position itself, which were likely created during the previous iteration, and would have been flushed out of cache, so that they require a DRAM access.)
The same system could also be used for 'level-spanning grafts'. I.e. rather than having analogous positions X and Y (i.e. refutable in essentially the same way) that differ by the move A having been played for one, and its sibbling B for the other, having positions that differ by move B and its reply C having been played to reach Y from X. This addresses the case where B was a pointless delaying tactic, which required counter-measure C, but otherwise did not alter the situation. In general move A from X would now be refutable by the same lines as move A made from Y. Note that in this case the analogy first occurs in all-nodes, rather than cut-nodes. Normally the killer slots in all nodes do not contain meaningful information, as there is nothing to kill there. Positions could still store their hash key in the killer-like table, but marking it as not valid for sibbling-refutation purposes when they turn out to be all-nodes. In the cut-node after B the B-C cases that are likely to be delaying tactics (like attack on a valuable piece, and its subsequent evasion, capturing a valuable piece and its recapture, blocking an attack and subsequent capture of the blocker) can be recognized, and lead to calculation of an analogy key from the XOR difference of the key after C and that in the killer-like slot two ply earlier.
This could be avoided by not just passing a killer move to sibblings, but the entire refutation tree.Then when A is refuted in some non-specific and non-trivial way (i.e. not by gobbling up the piece that was moved, and not by a null move), and sibbling B is an equivalent (read: equally pointless) move, the entire refutation of A can be grafted onto B. The moves of the analogous refutation tree in the corresponding node could be played immediately after the hash move, or even before it: the refutation tree was obtained at the same depth as the current search, while the hash move would be what is left from a previous deepening iteration, which was a search at lower depth.
Of course it sounds very expensive to represent entire trees in killer slots, and then pass them along. But in fact there is no need to to do that, as refutation trees are already stored in the transposition table. All that is needed is to store the hash key of the position after move A in a killer-like slot. So that this could be probed after move B. From this the search can see the hash-key (XOR) difference between the 'killer key' in the slot and its current key. This difference would remain constant in the grafted tree; if A and B were truly equivalent, all nodes of corresponding positions in the refutation tree of A would be obtained by XOR-ing the key for the current node with this 'analogy key'.
So all you have to do is pass along this analogy key through the search of B. So that in any node there the search could not only probe the TT for the position itself (to obtain the hash move), but also the analogous node, to retreive the hash move from there, and use it as 'analogy killer'. The latter probes should be cheap, as the entries were stored recently, during the search of sibbling A, and should still be cached. (Quite unlike the probes for the position itself, which were likely created during the previous iteration, and would have been flushed out of cache, so that they require a DRAM access.)
The same system could also be used for 'level-spanning grafts'. I.e. rather than having analogous positions X and Y (i.e. refutable in essentially the same way) that differ by the move A having been played for one, and its sibbling B for the other, having positions that differ by move B and its reply C having been played to reach Y from X. This addresses the case where B was a pointless delaying tactic, which required counter-measure C, but otherwise did not alter the situation. In general move A from X would now be refutable by the same lines as move A made from Y. Note that in this case the analogy first occurs in all-nodes, rather than cut-nodes. Normally the killer slots in all nodes do not contain meaningful information, as there is nothing to kill there. Positions could still store their hash key in the killer-like table, but marking it as not valid for sibbling-refutation purposes when they turn out to be all-nodes. In the cut-node after B the B-C cases that are likely to be delaying tactics (like attack on a valuable piece, and its subsequent evasion, capturing a valuable piece and its recapture, blocking an attack and subsequent capture of the blocker) can be recognized, and lead to calculation of an analogy key from the XOR difference of the key after C and that in the killer-like slot two ply earlier.