idea: null-move analogy
Posted: Wed Mar 06, 2019 2:16 pm
Sometimes, in a superficially good position (i.e. eval > beta) the null move fails, because of some deep, hard-to-find threat. Many other moves are effectively null moves too, doing nothing useful, but also not giving something obvious away. These then likely have to be refuted in the same way as the null move.
But the search will have to rediscover that threat time after time. It is possibly a bit helped on the first ply of the refutation by the killer, which it inherits from its sibblings, but deeper down in the refutation tree it is on its own, and has to rediscover the thing from scratch. Only after many moves have been refuted in the same way the history heuristic might start to pick up the pattern. This problem is especially apparent in large variants with many pieces, (many hidden deep in their own camp), such as Chu Shogi or Tenjiku Shogi.
So what is needed is not just a cut-move hint on the first ply, (i.e. killer), but for the entire refutation tree. Now fortunately the tree that refuted the null move will be remembered in the hash table. All we have to do in the sub-tree of a useless move is probe the hash for the analogous position in the null-move refutation tree (i.e. that positions with the uselessly moved piece still in the original location). This position will have a hash key that always differs from the key of the current position by the mutation brought about by the alledgedly useless move we try to refute.
So what we could do is, after a null-move fail low, pass along to the sub-tree after any other move the mutation in board key that these moves cause. When this 'analogy key' is non-null the nodes in this sub-tree can use it as a secondary hash move; if the ordinary hash move doesn't work, or does not exist, they can probe the analogous position, and see if that can provide a hash move. This way it tries to copy the entire refutation tree, and if the original null-move alternative indeed had no effect at all, it would find the refutation in a perfectly efficient way. (Presumably the null-move reduction is matched by the LMR of such moves.)
Of course even when there is an anlogy key available, the node can still start by searching a null move. It will then pass that analogy key on to the null-move search, which will presumably benefit from it by making the refutation fast. This leads to a new refuted null move, which would define a new analogy key for the alternative moves. This new key will be preferred over the old one, as the difference of the analogous positions reached through this key will be smaller. So a refuted null-move search will possibly replace an existing analogy by a newer one.
But the search will have to rediscover that threat time after time. It is possibly a bit helped on the first ply of the refutation by the killer, which it inherits from its sibblings, but deeper down in the refutation tree it is on its own, and has to rediscover the thing from scratch. Only after many moves have been refuted in the same way the history heuristic might start to pick up the pattern. This problem is especially apparent in large variants with many pieces, (many hidden deep in their own camp), such as Chu Shogi or Tenjiku Shogi.
So what is needed is not just a cut-move hint on the first ply, (i.e. killer), but for the entire refutation tree. Now fortunately the tree that refuted the null move will be remembered in the hash table. All we have to do in the sub-tree of a useless move is probe the hash for the analogous position in the null-move refutation tree (i.e. that positions with the uselessly moved piece still in the original location). This position will have a hash key that always differs from the key of the current position by the mutation brought about by the alledgedly useless move we try to refute.
So what we could do is, after a null-move fail low, pass along to the sub-tree after any other move the mutation in board key that these moves cause. When this 'analogy key' is non-null the nodes in this sub-tree can use it as a secondary hash move; if the ordinary hash move doesn't work, or does not exist, they can probe the analogous position, and see if that can provide a hash move. This way it tries to copy the entire refutation tree, and if the original null-move alternative indeed had no effect at all, it would find the refutation in a perfectly efficient way. (Presumably the null-move reduction is matched by the LMR of such moves.)
Of course even when there is an anlogy key available, the node can still start by searching a null move. It will then pass that analogy key on to the null-move search, which will presumably benefit from it by making the refutation fast. This leads to a new refuted null move, which would define a new analogy key for the alternative moves. This new key will be preferred over the old one, as the difference of the analogous positions reached through this key will be smaller. So a refuted null-move search will possibly replace an existing analogy by a newer one.
