Fast capture sorting

[hgm]

The order was just an example. The method is the point. Did you not notice I gave an example that the order could be changed. That means the order can be any order one wants.

Well, in the method I described it would not be easy to change the order arbitrarily. Because the bitmap of the captures is stored per victim, and the bits indicating the attackers are all in the same order for each of the victims. So the word in which you vind the capture is determined only by the victim, and the bit only by the attacker. This is why the captures can be recorded as

attackers[victim] |= attackBit[piece];

For an arbitrary order the bit could be in any word of the attackers set, and it could be any bit in that word. So you would have to record the attacks as

attackers[word[piece][victim]] |= bit[piece][victim];

Which would be a lot more expensive, even when word[piece] and bit[piece] could be set outside the loop of moves for a given piece. But I suppose it could be done.

Fortunately MVV/LVA order is programmer-friendly. The cases where it is better to deviate from it are probably better handled by a two-pass system, where for each victim value group you mask away the suspect capture (with a victim-dependent mask). Treatment of such captures superior to MVV/LVA unavoidably require that you generate moves for the opponent too, though. This could be done by an IsSquareAttacked() method, which is expensive per square, in the hope that you don't have to subject many squares to it. Or by total capture generation, which is cheaper per square, but in total much more expensive than IsSquareAttacked() for a single square. Of course you could be lazy, and use the attackers[] array from the parent node, in the hope the true attacks it weren't changed too much by the preceding move, so that it is on average still better to use that than make a blind guess. (If you set up the move generation to also record 'friendly fire'.)

The 'attacked' mask can easily accomodate bits for all 32 pieces, and would allow you to test which vitims in the value group are protected. Depending on that you could look up a mask that would mask out the H x protected L captures for that value group, and postpone this to a second pass through all victims.

[hgm]

I still doubt that this is an area where much improvement can be had because it doesn't take much time in the first place, which is why so many engines use this approach - even Stockfish if I'm reading the SF15 move picker code correctly. So how much speedup did you actually measure when putting that idea into one of your engines?

I don't have such information, because I have never done that. I have super-fast engines that have used this method from the beginning, and I have very simple engines that are slow.

And I can only repeat, when a certain task "doesn't take much time", this is just another way of saying the rest of the engine is too slow. The main task of an engine is to conclude there are no captures it wants to search. (Because this is what it does in leaf nodes, and there are more of those than any others.) For which it must generate moves, extract the captures, and conclude they are all bad or futile.