Taboo moves

[hgm]

I keep coming back to this problem, because it is so incredibly annoying, predictable and stupid: the engine thinks a particular move is best, e.g. capturing a Queen. At some high depth D the Queen turns out to be poisoned, and the score drops dramatically. In the remainder of the same iteration the engine now will come up with totally non-sensical sacrifices, like R x protected N. Because it figures that when the opponent recaptures, he will gain a Queen through the same sequence of moves that has already shown to lead to disaster in the root, because it has only D-2 ply left to search it. And from the experience in the root we already know that at D-2 there was a large but illusory gain. And it is of course very happy to sacrifice an exchange to gain a Queen. And when the opponent does not recapture, but does something to rescue the Queen instead... Well, then we have at least gained a Knight. But in fact you have given away the exchange for nothing.

The nonsense move it arrives at will still look best in the next (D+1) iteration, and only at D+2 it will have enough ply to see that the opponent can both defend his Queen and grab the exchange. If you are lucky it then finds a reasonable move, but often it just replaces the large sacrfice by a number of smaller ones, like attacking an opponnent piece with a Pawn on an unsafe square. That only gives away a Pawn, but gains the piece when he doesn't react. And if you do it before the line that started with throwing away the exchange, as that line now plays the same role as the illusory Queen gain, dropping dramatically in score at D+2 ply, needing a D+2 ply search to expose its evil nature.

I guess this is what they call 'classical horizon effect'. Strong Chess engines do not seem to suffer from this very much anymore. But I am interested in games on far larger boards with many more pieces. There the chances that one move will interfere with a deep tactical combination elsewhere on the board is pretty small, and there are often many unrelated places where you can make minor sacrifices. So it is a big problem.

If you think about it, you would have to be crazy to trust a (D-2)-ply search of a move in a node somewere in the tree when the same move in the root turned out to give a completely wrong score at D-2 ply (or at least one that was completely different from the resutl of a D-ply search). You would much more often be right when you assumed it would give the same improvement (compared to the node's static eval) as it would in the root according to the D-ply search. Which means that when you managed to make the static eval drop in the preceding plies, the move will not be competitive. You should either search it to D ply, to almost always prove that it is not competitive, on the off-chance that it occasionally is, because the preceding sacrifices miraculously had some positive effect. That means you would do an enormous amount of search effort (a double extension!) almost always just to discover you did it in vain. The alternative would be to prune the move. That at least would safe search effort, and perhaps that effort, applied elsewhere, would on the average have more positive effect than the detrimental effect that you would sometimes overlook a brilliant sacrifice.

So my idea was to maintain a list of 'taboo moves', defined as PV moves that dramatically dropped in score in the root at some depth, together with the depth at which this happened, and the score it has (relative to the static eval). If deeper in the tree you encounter that same move, and the remaining search depth is smaller than the recorded 'failure depth', you would not search it (at a depth you know will be inadequate to prove anything), but instead just assume it would gain or lose you as much as it did in the root at the failure depth. That would suppress sacrifices being inserted before a failing PV move in the same or the next iteration, and only at D+2 ply the remaining depth after a sacrifice should be able to find the score drop on its own steam, and establish if the preceding sacrifice miraculously cured it.

Since basically every PV node is the root of its own sub-tree, perhaps you could have deeper PV nodes also add moves to this taboo list (and then remove them again when they return).

[Dann Corbit]

It is an interesting idea. Sort of "anti-killer" moves.

[mvanthoor]

First thing that comes to mind for me was the term "reverse transposition table"; instead of using the transposition table to save on calculation by trying good moves first, you're now trying to save effort by NOT trying bad moves.

[hgm]

I don't think 'transposition table' is a good analogy. The TT stores good moves per positions. Here you want to inherit info about bad moves from other positions. 'Killer' also doesn't have quite the right ring, because killers are inherited from sibling nodes, and here you inherit from (possibly distant) grand-parents.

I do intend to try a generalized killer analogy, that would make siblings inherit a complete refutation tree from each other, rather than just the first move of the refutation. The idea is to use a killer-like table (indexed by ply) where a cut-move would store its hash key rather than the cut-move. A sibling node would then calculate the difference of that with its own hash key, and pass that to its offspring as an 'analogy key'. Nodes in the sub-tree below it would use this analogy key to do a 'backup hash probe': if they get a hash miss for their own position, they would XOR their own key with the analogy key, and probe there. This would make them probe in the tree of the just searched sibling move, in the hope that they can refute the current move the same way as the sibling was refuted. They should probably also do that when they get a hash hit, when the score that comes with the given hash move is wildly inadequate for the current search window.

The idea here is also that when a PV line at high depth drops very much in score due to a deep tactical threat, most other moves will probably not solve that threat, and in any case would need a totally different refutation to push them much lower as what was done in the previous iteration. The necessary tree is not likely to have been searched before. IID would not help much, because at lower depth you would not be able to see the threat. But the sibling has already seen it; it was searched at the current depth.