Analogy killer

[hgm]

I often run into a problem where my engine during analysis sees the PV score plummet at some high depth, and then starts using a lot of time for pushing the score of all other moves below the new PV score. This can take a long time for the second move, because it now needs an improved refutation tree, the cut-moves suggested by the TT being no longer adequate (but still searched first...). Not much we can do about that. (Well, perhaps discard inadequate hash moves...) But what annoys me is that it then takes nearly equally long to refute the other root moves, even those which are basically equivalent to the already refuted moves and could be dealt with through the same refutation. Apart from the first move, which they get as killer, they will have to rediscover the same cut-move improvements as the second move completely from scratch, the hash moves for their own refutation tree still only adequate to push them below the old PV score. History doesn't help much, as it suggests the same moves everywhere, rather than the node-specific cut-moves that are needed.

What I want is to use the entire refutation tree of one non-PV move as a 'template' for constructing a refutation for the sibbling moves. A sort of killer heuristic, but then for entire sub-trees.

The way this can be done, is by probing the TT not only for the current node, but also for the 'analogous' node in the sub-tree of a sibbling searched (and refuted) earlier. This is not very difficult, as there will be a constant difference in hash key between analogous nodes in the sub-tree of sibbling moves A and B. So when a move A fails low, we could remember the hash key after it, XOR it with the hash key after every move B we are going to search, and pass it down the sub-tree of B as an 'analogy key'. Every node in the sub-tree of B can then XOR its own hash key with this analogy key to get the hash key of the analogous position in the refutation tree of A. It could then peek into the TT in cut nodes to see how A was refuted; the move that did that we will call the 'analogy killer'.

It is still a question of how it should use that information. Killers are usually tried only after the tactical moves, because tactical moves are very specific for the previous ply. The move from the analogy probe is specific for the previous ply, though, whether that was tactical or not. So it would still make sense to try it before the captures. If it suggests a capture that would be searched later in the normal move ordering, it was also searched later in the move ordering of the analogous node, and apparently all earlier searched captures failed low there. If the analogy is good, they would also fail low now.

The analogy will probably not be good if move A or B (or both) are tactical; then even the first move of the refutation would likely be different (e.g. the recapture). So this technique is mainly intended for the non-tactical moves, and we should not pass on an analogy key when searching a tactical move, nor try to derive an analogy key from such a move for passing on to other moves. And as soon as an analogy fails, by the suggested move failing low, or because the analogous move is not even pseudo-legal in the current position, we would probably be wise to abandon it altogether; apparently moves A and B were not as similar as we hoped for in that case. That wouldn't of course have to stop us from setting up a new analogy in the node where that happens.

It might even be good to give searching the anallogy killer priority over searching our own hash move, when the latter was 'inadequate'. With that I mean that we do find a hash move for the current position in the TT, but that the score it got (presumably at the depth that satisfied the previous root iteration, and a lower bound) is below the current beta. There is no guarantee that we can give it a score above beta by searching it harder even in that previous iteration, let alone the current one; the fact that the analogy did not use the same move as cut-move suggests that it tried to do that and failed (low...), and finally switched to a better cut move. So it seems likely the same would happen here, and we would like to avoid that mistake, and directly go for the move that has proven to be adequate in the analogous node. If this is a tricky issue, we could put an extra bit flag in the TT entry that would record whether the node creating the entry did switch hash move; if it did, we could be more confident that we have to switch hash move too. If it didn't, and we have a different hash move, this shows that the analogy already broke down in the previous iteration, and we'd better abandon it.

[Desperado]

I often run into a problem where my engine during analysis sees the PV score plummet at some high depth, and then starts using a lot of time for pushing the score of all other moves below the new PV score. This can take a long time for the second move, because it now needs an improved refutation tree, the cut-moves suggested by the TT being no longer adequate (but still searched first...). Not much we can do about that. (Well, perhaps discard inadequate hash moves...) But what annoys me is that it then takes nearly equally long to refute the other root moves, even those which are basically equivalent to the already refuted moves and could be dealt with through the same refutation. Apart from the first move, which they get as killer, they will have to rediscover the same cut-move improvements as the second move completely from scratch, the hash moves for their own refutation tree still only adequate to push them below the old PV score. History doesn't help much, as it suggests the same moves everywhere, rather than the node-specific cut-moves that are needed.

What I want is to use the entire refutation tree of one non-PV move as a 'template' for constructing a refutation for the sibbling moves. A sort of killer heuristic, but then for entire sub-trees.

The way this can be done, is by probing the TT not only for the current node, but also for the 'analogous' node in the sub-tree of a sibbling searched (and refuted) earlier. This is not very difficult, as there will be a constant difference in hash key between analogous nodes in the sub-tree of sibbling moves A and B. So when a move A fails low, we could remember the hash key after it, XOR it with the hash key after every move B we are going to search, and pass it down the sub-tree of B as an 'analogy key'. Every node in the sub-tree of B can then XOR its own hash key with this analogy key to get the hash key of the analogous position in the refutation tree of A. It could then peek into the TT in cut nodes to see how A was refuted; the move that did that we will call the 'analogy killer'.

It is still a question of how it should use that information. Killers are usually tried only after the tactical moves, because tactical moves are very specific for the previous ply. The move from the analogy probe is specific for the previous ply, though, whether that was tactical or not. So it would still make sense to try it before the captures. If it suggests a capture that would be searched later in the normal move ordering, it was also searched later in the move ordering of the analogous node, and apparently all earlier searched captures failed low there. If the analogy is good, they would also fail low now.

The analogy will probably not be good if move A or B (or both) are tactical; then even the first move of the refutation would likely be different (e.g. the recapture). So this technique is mainly intended for the non-tactical moves, and we should not pass on an analogy key when searching a tactical move, nor try to derive an analogy key from such a move for passing on to other moves. And as soon as an analogy fails, by the suggested move failing low, or because the analogous move is not even pseudo-legal in the current position, we would probably be wise to abandon it altogether; apparently moves A and B were not as similar as we hoped for in that case. That wouldn't of course have to stop us from setting up a new analogy in the node where that happens.

It might even be good to give searching the anallogy killer priority over searching our own hash move, when the latter was 'inadequate'. With that I mean that we do find a hash move for the current position in the TT, but that the score it got (presumably at the depth that satisfied the previous root iteration, and a lower bound) is below the current beta. There is no guarantee that we can give it a score above beta by searching it harder even in that previous iteration, let alone the current one; the fact that the analogy did not use the same move as cut-move suggests that it tried to do that and failed (low...), and finally switched to a better cut move. So it seems likely the same would happen here, and we would like to avoid that mistake, and directly go for the move that has proven to be adequate in the analogous node. If this is a tricky issue, we could put an extra bit flag in the TT entry that would record whether the node creating the entry did switch hash move; if it did, we could be more confident that we have to switch hash move too. If it didn't, and we have a different hash move, this shows that the analogy already broke down in the previous iteration, and we'd better abandon it.

Can you create a simple example to make your description a bit more understandable.
For a heuristic the implementation effort seems quite high, especially if the benefit is not clear.

I find it hard to follow your description.

[hgm]

I suppose it would be something like this:

Code: Select all

Search(analogyKey)
{
  refuted = 0;
  if(analogyKey && (a = ProbeTT(hashKey ^ analogyKey)) && a->move) AddMove(a->move);
  if((h = ProbeTT(hashKey)) && h->move) AddMove(h->move);
  MoveGen(); // adds remaining moves in desired order
  for(move = ALL_MOVES) {
    MakeMove(move); // updates hash key
    if(!analogyKey && refuted) analogyKey = refuted ^ hashKey; // set up analogy with refuted move if none defined yet
    score = -Search(analogyKey);
    childKey = hashKey; // remember key of child
    UnMake(move);
    if(score > alpha) {
      ..
    } else if(move == a->move) analogyKey = 0; // analogy broken
    else if(IsNoncapt(move)) refuted = childKey; // remember the key of a refuted noncapture
  }
}