Pseudo-legal vs. legal move generation for mailbox

[abulmo2]

Switching to a legal move generator by moving the in-check function to the move generator will deteriorate your performance.

Why? Let's say a position has 40 pseudo-legal moves, but 10 of them put you in check. If you put your in-check function in the move generator, all 40 positions will be checked, and you end up with 30 legal moves. Now assume the FIRST position in your list (after sorting) is SO good, that your search function decides that this is it, and it doesn't need anything else. Then you have wasted 39 in-check function executions.

If you don't do this check in the move generator, but in the make_move() function, you only check the positions the search function is actually picking. In the above example, when the search function decides to pick that first move, only that one would be checked, and then the search is already over. So you saved 39 in-check function executions.

Personally I prefer the legal move generator, as it makes the search code clearer (no legal test here). I do not have a function to verify if a move put its own king in check. I just generate differently the move of the pinned pieces, and for the king I just target the not attacked squares. Basically, I do not generate illegal move. The drawback is that I have to compute the pinned pieces after each move, but the cost is negligible. Overall, I do not think the impact on the performance is important.

[Desperado]

I'm currently using a pseudo-legal move generator, followed by legality check (is the king in check, or squares crossed during castle), for my mailbox engine. Does anyone have a good idea of whether I may get a non-trivial performance gain by switching to a legal move generation with a mailbox engine?

I've decided against bitboards for my first engine due to cost/benefit, but I'm willing to put the work into a legal move generator if there's a good chance I'll gain some overall search speed.

Hi,

i suggest that you wait to test the move for legality as long as possible. When the move is picked to be searched then
it is a good moment to check it. Some people even wait until pruning conditions have been checked but that is already an optimization.

As Sven pointed out already there are only a handful cases that need to be considered.

Code: Select all

BOOL Pos::moveIsLegal(pos_t* pos, int move)
{
    if(inCheck(pos) || MoveIsEp(move))
        return executedMoveIsLegal(pos, move);

    if(IsKing(pos->sq[MoveSrc(move)]))
        return !squareIsAttacked(pos, MoveDst(move), FlipColor(pos->stm));

    if(getPins(pos, pos->stm) & Bit64(MoveSrc(move)))
    {
        int king = Bit::getLsbId(pos->bb[WK + pos->stm]);
        return Sharedline(king, MoveSrc(move)) == Sharedline(king, MoveDst(move));
    }

    return TRUE;
}

1. The first point is just laziness to keep my code simple. If in check, i execute the move and test if the square of the king is attacked.
The same for en passent moves. In real games the performance loss can be neglected because the moves are rare compared to standard moves.

2. The second check is when the king moves himself. Of course the destination square must not be attacked too.

3. The third is about absolute pinned pieces (for the side to move) that are only allowed to move along the line of a sliding checker.
You need to invest computing time for the absolute pinned pieces on the board, but you do it only once per node (not for every move!).
In practice you need this information for other purposes too, so you do not loose time when thinking of an advanced engine.

So, in most cases this routine will return a pretty fast "TRUE" because none of the checked conditions will occur.