Deep killers

[hgm]

In the killer heuristic you try the same move as the one that worked in a sibbling position. Which often is good, as many moves in the parent node don't do anything substantial, and thus can be refuted in the same way.

But what if the proper plan to victory requires a number of silent moves in a row? When you are searching the opponent's insubstatial moves, you get the first move of the refutation from the killer, but you would have to figure out the second move each time from scratch. You could try to use a killer left by a distant relative (i.e. if A-b-C-d worked, you can try d after A'-b-C'). But what you need here might depend on C/C' even if A and A' are equally dull moves, and you will have tried many different C (including those that made threats that forced you to withdraw a piece) after A before you get to refute A'. So the chances that you still have the right killer there are not that good.

It might help to transfer a bit more information from one branch to another than just a single move, or a pair of moves. E.g. the killer slot at the tree level where you play b could go accompanied by some 40 slots to store the killer from the grand-child node, one for each move C, C', ...

It would be a bit expensive to do that even deeper, but you could also try to use the hash table for this. Many insubstantial moves could be refuted the same way as the null move. (This is sort of the definition of 'insubstantial'.) So you could set up an analogy between the null-move sub-tree and that of another late move by XOR-ing the key contribution of that late move out of the hash key. And then not only probe the hash table for a move in the current position, but (if you did not get one) also for what the analogous position in the null-move sub-tree did. Or, if the null move was not searched in this node, set up the analogy between the current sub-tree and that of the previous move that was searched. You could abandon the analogy as soon as one of the moves obtained from it would fail to cause a cutoff, so that you would have to try alternatives (which were not searched, or found not to work in the analogy, so that it is not helpful to probe for them). These alternatives would then not use the analogy in their sub-tree.

[Evert]

You can sort-of do this with a counter-move like heuristic, but instead if using the opponent's last move you use your own previous move to index it. That allows you to store a chain of good moves. It's not exactly the same as your suggestion, but it should work as a first approximation and is relatively simple.

[hgm]

Yes, I guess it would be similar to counter move. But when using an analogy in the TT you would graft an entire sub-tree, including all the opponent's possible defenses.

I am trying to combat the problem of deep threats, which occur frequently in Tenjiku Shogi. You have a hash move, and it continues to look good during a number of visits to the node at successive higher depths, due to iterative deepening in the root. Then, at some point, you revisit it and the hash move is punished (usually by a checkmate, because your Fire Demon has been on a plunder raid, and you now have no defence against the jumping generals).

So you start to look for alternatives, but even most good ones suffer from the same problem: initially they look good (usually because they trade something valuable, like Rook Generals), and then you go on the same plunder raid anyway, and you see the mate even 2 ply later, because the trade delayed it. Even non-forcing moves would not look bad initially, because of the postponed plunder raid, but run into the mate at the same depth as where the hash move failed low. So even if I do IID here, it is of little help: all moves suffer from the same problem. The whole sub-tree at the depth before I could see the mate is useless, and as soon as the depth is reached that can see the mate, the node flips from a fail high into a fail low, and requires a completely different tree.

The refutation tree of the hash move at depth N would be a much more useful template for the refutation tree against the alternative than an tree for the move itself at depth N-1 (which would actually not refute it at all). So it would be better to refrain from IID altogether, ignore the hash moves for the positions themselves in the sub-tree of the alternative moves, and play primarily by the hash moves of the analogy.