Most engines have some method of filtering out pseudo-legal moves from the actual legal ones. However, is there any reason not to keep them? With bit-boards, you can quickly filter out the ones that result in the king landing in the attack mask of the opponent's side when trying a move at search-time. Am I missing something here, or is it faster to filter out before the search?
1 Answer
It is actually!
Some engines have what are known as fully legal move generators, the kind of move generator you're talking about, where only completely legal moves are returned.
This approach is fine, but not every move is actually tested during the search phase, so it's actually (generally) more efficient to test move legality on a move-by-move basis.
This is the approach used in many of the current top chess engines like Stockfish, Etheral, and Koivisto. For example, here's the relevant code in Stockfish that does this, during the search phase:
while ((move = mp.next_move()) != MOVE_NONE)
if (move != excludedMove && pos.legal(move))
{
...
Notice the call to pos.legal
, which tests if a move is legal.
-
Wow, that makes so much more sense! Just wondering though - would it be too slow to test a move's legality by trying it out then checking, or is it worth it to implement the more complex method that stockfish uses?– AAce3Jun 4, 2022 at 17:21
-
1Sure @AAce3, no problem! To answer your question, Stockfish's approach is generally faster; but many engines use the other method you described, including my engine, and it's not unacceptably slow. And further, while move generation speed is important, it actually takes up a relatively small percentage of the total search time, so the method you mentioned isn't particularly penalized either. Jun 4, 2022 at 21:50