killer trees

[hgm]

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.

[tpetzke]

That's an interesting idea. It competes however a bit with plain killer heuristic that stores killer moves per ply. So you have killers available for the 3rd, 5th ... refutation.

You idea assumes that you have different (at least more than the usual 2) refutations for the moves in the previous ALL node and then it will be superior to plain killers as the two slots are not enough to maintain all the different refutations. Correct ?

What makes me a bit skeptical is that fact the extending the killers to three slots usually does not bring any further gain (even 2 is already a close call) but your idea might still work as it is more specific than the plain killers.

[hgm]

Indeed, I assume that 2 is not enough, and also that it is much less likely that 'grand-cousins' could use the same refutations as sisters. Ippolit even would clear that killer slot when it start a new node at level 2, 4 etc., to prevent grand-cousins would use each other's killers, and I suppose it does that for a reason.

Also note that perhaps 'killer' is a misleading name; I used it because the entire trees are passed to sibblings like killer moves are. But the orthodox killer heuristic is only used for non-captures, as it is a much more unreliable source of cut moves than MVV/LVA captures. The latter are tactics that specifically deals with the preceding move, but searched in a static order not affected by the preceding move (although some engines move recapture up in the list). But this is supposed to be a very reliable source, perhaps even better than the hash move. So it would be searched before the MVV/LVA captures, and thus can also be a capture.

This explains why more than 2 slots could be useful. You don't only want to store the comparatively rare case where a refutation is a non-capture, but also all the capturing refutations of the specific tactical moves. The gain compared to the normal killer should come from the fact that it has become such a reliable source of cut-moves that you can use it earlier in the move sorting. When a normal killer is effective, you only notice it after you have tried all captures in vain, With this, even non-capture cut moves can be tried first, if you have no hash move.

[mcostalba]

All that is needed is to store the hash key of the position after move A in a killer-like slot.

The power of killer moves is that they are _not_ associated to a specific position, so you cannot use a specific position hash key to refer to a killer refutation line.

Killers and position hash keys are two completely different concepts, you should not mix them.

[hgm]

The mix here is that the entire killer tree is not specific, but a general (and thus graftable) refutation against a white variety of non-descript moves A and B. But at the later levels it does very specifically respond to the moves Cn, Cn'. So that they can also deal with the tactical moves in the continuation.

So you really get the best of both worlds. Grafting the trees should only be tried against non-tactical moves, which have a good chance to be sufficiently similar that a normal killer (equivalent to the first move of the killer tree) would work against all of them. But the deeper moves of the killer tree can apply general and specific tactical refutations as needed.

[mcostalba]

The mix here is that the entire killer tree is not specific, but a general (and thus graftable) refutation against a white variety of non-descript moves A and B. But at the later levels it does very specifically respond to the moves Cn, Cn'. So that they can also deal with the tactical moves in the continuation.

So you really get the best of both worlds. Grafting the trees should only be tried against non-tactical moves, which have a good chance to be sufficiently similar that a normal killer (equivalent to the first move of the killer tree) would work against all of them. But the deeper moves of the killer tree can apply general and specific tactical refutations as needed.

Sorry, but I am still not able to understand your idea without some example code.

[hgm]

If I am not mistaken, this should more or less describe it:

Code: Select all

uint64 killerKey[MAXDEPTH];
MOVE killer[MAXDEPTH]; // orthodox killer table

int
Search(..., ply, lastMove, analogyKey)
{
  killer[ply+1] = INVALID;
  killerKey[ply+1] = 0;
  hashMove = Probe(hashKey)->move;
  if(analogyKey) { // we are already replaying the refutation tree to another move
    analogyKiller = Probe(hashKey ^ analogyKey)->move;
    if(!IS_LEGAL(analogyKiller)) analogyKiller = INVALID;
  } else { // see if we can find a suitable refutation to replay
    if(killerKey[ply] && IS_NONCAPTURE(lastMove)) // sibbling non-capt has set killerKey
      analogyKey = killerKey[ply] ^ hashKey;      // define mapping to its refutation
  }
  SortMoves(hashMove, analogyKiller, goodCaptures, killers, other);
  for(ALL_MOVES) {
    MakeMove(move);
    score = -Search(..., ply+1, move, analogyKey);
    UnMake(move);
    ...
    if(score >= beta) {
      if(IS_NONCAPTURE(move)) killer[ply] = move;
      if(IS_NONCAPTURE(lastMove)) killerKey[ply] = hashKey;
      return beta;
    }
  }
}

[tpetzke]

How is the analogy key updated ? Once you have obtained a first analogy key probably at ply 1 it is never changed again. Is this intended ?

[mcostalba]

if(IS_NONCAPTURE(lastMove)) killerKey[ply] = hashKey;

killerKey[ply] is a position, call it A, hash key

analogyKiller = Probe(hashKey ^ analogyKey)->move;

and here you ^ with another position, call it B, hash key

But A ^ B has no meaning becuase a killer move is not a tt move.

As I said before killer moves are not associated to a specific position, so there is in general no strict relation among position A and B in particularly given a killer move M:

hash(A) ^ from_square(M) ^ to_square(M) != hash(B)

The above is true apart for the very specific case in which the killer move is also the TT move.

So I think your idea cannot work, at least this is my understanding.

[hgm]

T = A^B is the difference between position A and position B. It can be used to transorm position B into position A, as

B ^ T = B ^ (A ^ B) = A

But if the same move m transforms A into A' and B into B', as

A' = M ^ A
B' = M ^ B

(where M is the usual Z(piece, from) ^ Z(piece, to) ^ Z(victim, to) ^ Z(stm)).

So T can also be used to transform B' into A', as

B' ^ T = (B ^ M) ^ (A ^ B) = A ^ M = A'

So as long as X = B, B', B"... run through the sub-tree hanging from B, T^X would trace the analogous tree hanging from A, which was searched just before, and is already in the TT. The cut moves of the latter should be excellent guesses for the cut moves in the current search, if the difference between A and B is truly immaterial.