Move ordering heuristics for captures

[niel5946]

Hi.

Apart from ordering captures with SEE and MVV/LVA, I have seen some of the strongest engines utilize some kind of history heuristic just for captures. This makes sense to me considering that some positions have very thematic captures. Take for example the one below:
[d]rnbq1rk1/pppn1ppp/4p3/3pP3/1b1P4/2NB1N2/PPP2PPP/R1BQK2R w KQ - 5 7
Arising from the french defense. This is a classical position where the greek gift sacrifice occurs after White's move Bxh7!. This is usually possible right after black castles, which means that "remembering" Bxh7 as a good move when searching - before the greek gift is possible - would make an engine find the sacrifice faster and thus play better.
But my problem is: I have tried messing around with quiet move ordering heuristics, used for captures, a couple of times now, but the engine has always lost 20-50 elo by doing it.

Are there any good ways of ordering captures with more heuristics than just SEE and MVV/LVA? Have i misunderstood the assumed "direct" relationship between the quiet and capture histories?

Thanks in advance

[Ras]

But my problem is: I have tried messing around with quiet move ordering heuristics, used for captures, a couple of times now, but the engine has always lost 20-50 elo by doing it.

No wonder. The history heuristic means something like "it's usually a good idea to place this piece on this square". With captures, this doesn't work because they are too specific since a lot depends on whether and how things are protected.

What you do see, in particular with the kind of position you gave, is some hardcoded pattern recognition. Not only with the bishop sacrifice on h7, but also the knight sacrifice via h6xg5 if there is a rook on h1. Or (that's one that I have in my engine) the trapped bishop pattern after Bxa7 b7-b6 when the bishop can't get out anymore.

[niel5946]

With captures, this doesn't work because they are too specific since a lot depends on whether and how things are protected.

That is also what I thought. But then I don't understand how engines like Ethereal and Stockfish use capture histories? It seems - at least in Ethereal's example (https://github.com/AndyGrant/Ethereal/b ... /history.c line 97) - that they update these tables the same way one would with quiet moves. I don't understand how they get it to work...

[chrisw]

With captures, this doesn't work because they are too specific since a lot depends on whether and how things are protected.

That is also what I thought. But then I don't understand how engines like Ethereal and Stockfish use capture histories? It seems - at least in Ethereal's example (https://github.com/AndyGrant/Ethereal/b ... /history.c line 97) - that they update these tables the same way one would with quiet moves. I don't understand how they get it to work...

Conceptually .... as Ras says, a general table of capture statistics doesn’t work too well because captures are highly position specific. What you need is a relatively localised (in time and space, eg depth and more recent parts of the search) where you rate a capture by whether it caused a cutoff or not.
Therefore, table updates should weight the most recent update more heavily. The table needs at least indexing by depth. Using prior move(s) as more index also useful.
So now, a higher score in the capture table indicates that this move has done well, recently, with position reached by same prior move(s).
Maybe you can think of ways to measure, and hence index by, “similar sort of position”.

[Ras]

That is also what I thought. But then I don't understand how engines like Ethereal and Stockfish use capture histories?

Yes, but rather not for "themed" captures. The problem in your position isn't remembering it from history, but finding it in the first place. Any sacrifice is in danger of getting pruned away. That's not a problem in your position because Bxh7 also delivers check, and you don't prune that. The knight sacrifice on g5 doesn't deliver check so that it's harder to spot, hence hard-coded patterns.

What a capture history can do is something else IMO. Consider this position, stripped down to the essentials for the sake of the argument:

[d]8/8/4kn2/7q/8/4K3/7Q/5R2 w - - 0 1
MVV-LVA would pick the most valuable victim first, so Qh2xh5 would be the first thing to try. However, Rf1xf6+ is a lot better because that removes the defender of the black queen, and since it's also check, Black cannot play Qh5xh2 before recapturing the rook. That also works with overloaded pieces, e.g. a piece that at the same time protects another piece and guards against mate:

[d]3q2k1/5ppp/8/8/3r3Q/7P/5PP1/4R1K1 w - - 0 1
Here, MVV-LVA would try Qh4xd8+ first, but that's only draw. Qh4xd4 however wins since the black queen has to guard the back rank and cannot recapture. Btw., pruning is not an issue here because after Qd8xd4, Re1-e8+ delivers check and hence shouldn't be pruned.

In both examples, SEE would not spot this because the point of that motive is to hit somewhere in order to expose or exploit a weakness somewhere else. In the second example, SEE would even conclude that Qh4xd4 is a bad move because it trades a queen for a rook. So when you reach a similar position, a capture history could remember that there's some better capture than going by SEE or MVV-LVA.

[hgm]

All this is still a bit questionable. If you are in QS, it is not only that SEE doesn't see that QxR is better in the last positions; QS would likely not see it either, because the clincher Re8# is a non-capture, and is already the third ply. (While I thought that even QS that do consider checks only do that in the first two ply.) And at higher depth you are likely to have it as a hash move if the QxQ equal trade was not good enough for a cutoff.

Furthermore, such patterns are very rare. Far more common is that you have to give priority to the recapture because the preceding capture did attack a heavy piece. I guess the general lesson is that the value of a piece is not just its material value, but also what it attacks or protects. A Pawn that attacks a Queen after PxP should better be the first thing you try to capture, even if there is a PxN opportunity elsewhere on the board. The forelast position was an example where he Knight is the essential protector of a Queen, which also increases its 'effective value' to Queen proportions.

If you really want to make the right choices here, I think you should make a better effort to analyse the specific situation. That should work far better than any heuristic based on statisics of recent moves. One day I still want to make a version of N.E.G. that does such an analysis, good enough to not make it obvious anymore that it doesn't search ahead. I was thinking of something like this:
1) Count the number of attackers and protectors of each square, and keep track of the lowest-valued attackers of each color. This is pretty much what N.E.G. already does, and what allows to get a SEE approximation for each square. And then it adds the SEE value on the to-square of a move to the SEE value for the opponent on the from-square, because it recognizes moving away as a method for solving a threat.
2) In addition, it can also judge the situation on each square with one fewer attacker or one fewer protector. (To use its simple heuristic to guess SEE this would require also keeping track of what the second-lowest attacker and protector of the square were, in case the lowest one is not allowed to participate.) If that doesn't alter the SEE guess, then fine. If it does, the piece should be marked as essential, and the value put on that the difference of the SEE guesses. This basically adds to the value of the piece. So the Knight in the forelast example would be worth N+Q, as the SEE guess of the black Queen turns from equal to gaining a Queen when the Knight cannot participate there. It would also make it see that you can solve threats by capturing the attacker.
3) It should also judge how the exchanges fare if there was an extra attacker or protector. In particular, it should involve X-ray attacks through pieces of opposit color as if they were real. If the SEE guess changes by this, that oppositly colored piece is (soft-)pinned. That makes the pinned piece essential for the exchange of the piece it is pinned on, not by participating actively in it, but by blocking a potential attacker. Again, a value can be put on this equal to the difference in SEE guess for the piece it was pinned on.
4) when a piece is declared essential for more than one exchange, the 'essentiality' that made the largest difference prevails. The exchange for which it was least essential then has to be recalculated as if that piece was not involved. This could of course have consequences for the essentiality of the other pieces involved in that exchange. Which could then also become overloaded, so that they have to drop their least-essential task, etc. There is no guarantee that this would not make you loop forever, so you just do a finite (small) number of iterations for recalculating exchanges that lost participants due to overloading / pinning in the previous iteration.

Now protecting pieces as a remedy to a threat is a more tricky issue, as it is really a form of thinking ahead: you have to imagine two moves with the same piece. You could think 'backwards' from exchanges with positive SEE guess, though, by recalculating those with an extra protector, and if that improves matters, then mark the board squares where such a piece would have to be to indeed protect. Moves would then get a score (for sorting purposes) equal to the exchange value of the square they capture to (including the essentiality upgrade for the piece they capture), plus the value of the threat against them on the from square, minus their essentiality there (the task they abandon), plus a bonus for going to a square where they protect something.

The example with the mate threat was still more subtle; the Queen there was not essential for blocking or recapture of a capture, but of a mating square. This should be excessively rare, but a 'back-rank mate' like this is a well-known pattern, and easy to detect through a King with a virgin Pawn shield. In the presence of that pattern every move of Q or R to a back-rank square should be treated as if it were a capture of a King combined with a promotion to King (so that it doesn't gain anything of you get captured there).

That might sound very complex, but I don't think it would have to be very costly. The SEE approximations could be done through table lookups. If we count attackers and protectors separately by adding weights P=1, minor=3, R=12, Q=36, K=72 we would have 144 possible combinations. The more populated of those would virtually never occur. (So who cares if you will get it wrong for those, and do a sub-optimal move sort as a consequence?) Presumably you can do a 'magic' lookup SEE[attackersCode*MAGIC1 + protectorsCode*MAGIC2>>54] that makes sure a couple of hundred of the most common situations map to different elements of the SEE array, and store their SEE value there. Acually this is also a good idea for the 'mailbox trials' project. There each piece would automaically have a 32-bit 'attackers set' available for it, where each bit represents an attack / protection by one of the 32 pieces. Perhaps a sufficiently good SEE approximation could be obtained by SEE[attackersSet*MAGIC >> 54].

[Ras]

If you are in QS

I was referring to main search.

And at higher depth you are likely to have it as a hash move

I think the idea was to have a match not only in the same, but also in similar positions - so pretty much like the quiet depth killers, just for captures.

Furthermore, such patterns are very rare.

It's always when the highest ranked capture as per MVV-LVA is not the best capture. I just made up some examples where it's easy to see.

Far more common is that you have to give priority to the recapture because the preceding capture did attack a heavy piece.

Yes, that's also a good example.

If you really want to make the right choices here, I think you should make a better effort to analyse the specific situation. That should work far better than any heuristic based on statisics of recent moves.

Yes, but it also takes more time. Just having a "killer capture" slot doesn't. I'm experimenting with a one slot killer capture indexed by ply depth, so far without useful results however. There is a reason why the normal depth killers don't include captures.

[hgm]

I takes more time, but it does something useful. The stuff that is practically free does more harm than good. Or, if you are very lucky, you have a marginal gain of 2 or 3 Elo. While we know that a really good (but super-expensive) pattern recognizer, such as the policy head of the LC0 NN, can shrink the tree by a factor 1000. The challenge is to design something 100 times cheaper than a NN, that still reduces the tree by a factor, say, 100.

At high remaining search depth nothing is a problem. There are so few of those nodes that you can afford anything. And the matter is usually already decided there, an indicated by the hash move. If not, you start iid at a very low depth.

I don't see how a simple statistics-based heuristic could ever pick out the rare cases where the Q x protected R is good because the protector is overloaded for protecting a mate square. A tree where this occurs is very likely full of positions where black has pushed one of the Pawns, the Rook is on f1, etc. In all these positions capturing the Rook is worse.

What IMO would make sense (but which no one seems to use) is an 'analogy killer', which is the hash move for the 'analogous' position in the sub-tree of an already searched sibbling move somewhere far closer to the root. E.g. in a high-depth all-node you tried move A and B in one iteration, and these were nicely refuted. There refutations will be in the hash. Next iteration you try A again, and, disaster, the envisioned refutation appears not to work at all. The reply C to A fails low rather than high, you never searched any alternatives to C as it has been cut-move from the beginning. But, after much hard work breaking hitherto unvisited ground, you manage to find an alternative C' to C which does fail high. So A still fails low after all, and you get to B. Now what? Suppose you go with the hash move, which happens to also be C (perhaps it was originally even inspired by the refutation of A, passed on as a killer). Because A and B are not essentially different (but just time-wasting moves, as there always are many), C after B runs into the same problem as C after A, and doesn't deliver the desired cutoff. Also here, you never searched any alternative to C. So you have to break new ground, where no hash moves are waiting to guide you. Starting with C' seems logical, and most likely it would be passed to you as a killer too. Intuitively it makes sense to try refuting B in the same way as the way you finally managed to refute A. I.e. with C', but also with the entire sub-tree of moves that followed it. You just want to graft the sub-tree hanging from A-C' onto B-C'. This is possible by not probing for your own hash moves (of which there won't be any) but probing the TT for the hash moves after A-C'. And playing these as primary choice. In fact, even when you did have a hash move (like immediately after B, where you had C), when that is the same move as just didn't work in the latest sibbling node, it seems prodent to switch to C' immediately after B too. I.e. prefer the analogy killer over your own hash move. After all, the analogy killer has been searched to the currently requested depth, while your own hash move is a leftover from the previous iteration, one ply less deep.

That brings me to the concept of 'anti-killers'. The normal killer heuristic doesn't work on captures, because captures typically have refutations that are unique to them. (Usually the recapture.) So you cannot inherit them from a sibblin, they did not exist in most sibblings. But it happens often that you don't try the recapture first, but some pre-existing capture. E.g. a BxR which doesn't work because the B is soft-pinned on your Queen. It is then very likely that the same BxR is also possible in sibbling nodes, and also first in the move ordering, while the Bishop is still pinned. It would help if you were forewarned that this BxR was no good, then you could order it later. This is what an anti-killer heuristic would do: communicate captures (or hash moves) that failed low to sibblings. There must have been a move that failed high in the sibbling where these moves failed low, or you would never get to searching the current node. It seems better to try what worked there first, and you can achieve that by skipping what did not work there. In the example of the analogy killer the failure of C as former hash move to refute A would make it anti-killer. And this could inspire he node after B to ignore C as its own hash move, and directly go for C', the analogy killer.

[lithander]

What IMO would make sense (but which no one seems to use) is an 'analogy killer', which is the hash move for the 'analogous' position in the sub-tree of an already searched sibbling move somewhere far closer to the root.

This is what an anti-killer heuristic would do: communicate captures (or hash moves) that failed low to sibblings.

Both ideas seem to make a lot of sense. Anyone can guess why they aren't implemented in existing engines? Is it too costly to maintain and lookup the necessary datastructures so that in practice it's not a real advantage?