Pseudo-legal vs. legal move generation for mailbox

[lojic]

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.

[mvanthoor]

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.

[lojic]

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.

Your reasoning seems sound :) Maybe the statements I read about legal move generation being more efficient were either about bitboard implementations, or they were simply wrong.

[mvanthoor]

Your reasoning seems sound Maybe the statements I read about legal move generation being more efficient were either about bitboard implementations, or they were simply wrong.

This is the same for bitboards or mailbox; checking move legality in the move generator is slower. (There are other ways of making a legal move generator that are actually somewhat faster, but they are also more complex.)

In a mailbox engine this can be more detrimental than in a bitboard engine.

If you don't keep incrementally which square is attacked by what piece, you'd have to loop over pieces and squares. This takes a lot of time. Much more time than a bitboard engine takes, where square_attacked() boils down to one massive "OR"-statement, after the compiler is done with it...

Code: Select all

pub fn square_attacked(&self, board: &Board, attacker: Side, square: Square) -> bool {
        let attackers = board.bb_pieces[attacker];

        // Use the super-piece method: get the moves for each piece,
        // starting from the given square. This provides the sqaures where
        // a piece has to be, to be able to reach the given square.
        let occupancy = board.occupancy();
        let bb_king = self.get_non_slider_attacks(Pieces::KING, square);
        let bb_rook = self.get_slider_attacks(Pieces::ROOK, square, occupancy);
        let bb_bishop = self.get_slider_attacks(Pieces::BISHOP, square, occupancy);
        let bb_knight = self.get_non_slider_attacks(Pieces::KNIGHT, square);
        let bb_pawns = self.get_pawn_attacks(attacker ^ 1, square);
        let bb_queen = bb_rook | bb_bishop;

        // Then determine if such a piece is actually there: see if a rook
        // is on one of the squares a rook has to be to reach the given
        // square. Same for the queen, knight, etc... As soon as one is
        // found, the square is attacked.
        (bb_king & attackers[Pieces::KING] > 0)
            || (bb_rook & attackers[Pieces::ROOK] > 0)
            || (bb_queen & attackers[Pieces::QUEEN] > 0)
            || (bb_bishop & attackers[Pieces::BISHOP] > 0)
            || (bb_knight & attackers[Pieces::KNIGHT] > 0)
            || (bb_pawns & attackers[Pieces::PAWN] > 0)
    }

[hgm]

I think legal move generation is universally bad. Effort you spend on legality testing on a move that turns out to be legal was a waste of time, as now you will have to try the move anyway. And the large majority of the moves will be legal. So it is much better to do some unnecessary work on moves that happen to be illegal. If you just assume all moves are legal, you haven't done that much extra compared to a check test by the time you discover that you can capture a King. Better to take that overhead on the small fraction of illegal moves that somewhat less overhead (per move) on all moves.

There is one caveat, though: testing moves for legality after their generation is a waste of time, but refraining from generating illegal moves in the first place is a time saver! And it is not so difficult to at least prevent moving away pinned pieces so they expose your King. In Chess there are only 5 pieces that can pin anything, and if your engine uses a piece list, you know where they are. It is relatively easy to test whether they are aligned with the King such that they could in principle pin anything, and most of the time they are not, and then you are immediately done with them. When they are properly aligned, you have to scan the board from your King to their location, to see if there is only a single piece of your own blocking their attack. If there is, that piece is pinned, and you should not generate moves with it that go in another direction as you have just been scanning.

That only leaves the possiblilty for King moves to be illegal, when they stuble into check, reducing the fraction of illegal moves even further.

[lithander]

I think legal move generation is universally bad. Effort you spend on legality testing on a move that turns out to be legal was a waste of time, as now you will have to try the move anyway. And the large majority of the moves will be legal. So it is much better to do some unnecessary work on moves that happen to be illegal. If you just assume all moves are legal, you haven't done that much extra compared to a check test by the time you discover that you can capture a King.

But with leaf nodes I have to check if they are legal because I'm not going to play their child-moves and discover that one of them threatens the king, right?
Or are there no such leaf nodes once quiescence search is implemented because all attacks are explored and so a captured king would be discovered down the tree?

[lojic]

I think legal move generation is universally bad. Effort you spend on legality testing on a move that turns out to be legal was a waste of time, as now you will have to try the move anyway. And the large majority of the moves will be legal. So it is much better to do some unnecessary work on moves that happen to be illegal. If you just assume all moves are legal, you haven't done that much extra compared to a check test by the time you discover that you can capture a King.

But with leaf nodes I have to check if they are legal because I'm not going to play their child-moves and discover that one of them threatens the king, right?
Or are there no such leaf nodes once quiescence search is implemented because all attacks are explored and so a captured king would be discovered down the tree?

I won't speak for H.G., but from my perspective, I was assuming that legality would be checked before descending in the search. For one thing, it's not just the king being in check, but squares crossed during a castle move. So, I'll generate all my pseudo-legal moves, but the search will make the move, and if it's not legal, it will ignore it, unmake the move, and proceed to the next move.

[Sven]

When not being in check, a pseudo-legal is almost always legal, with the following exceptions:
1) a king moving into check (including castling),
2) a king castling through check,
3) a pinned piece not moving along the pin direction,
4) a pawn capturing en passant while being pinned horizontally together with the enemy pawn being just captured.

When being in check, you need to add
5) all moves that do not escape from check properly, i.e. that neither capture the checking piece nor interpose nor move the king.

2) can be handled by not generating such castling moves at all. 4) could be seen as a special case of 3) but since ep is very rare the additional complexity might not pay off. 5) can be handled by either providing a special check evasion generator or by simply putting all moves under suspicion when being in check (or a combination of both).

In Jumbo I have a function like "move can be illegal" that returns true if "in check" or "king move" or "ep move" or "is pinned". The move generator only adds a move to the move list if that function returns false or the legality check (make - king left in check? - unmake) does not reject the move. Furthermore the current set of pins (a 64-bit number) is already considered during move generation. That way I have a "legal move generator" that simplifies search considerably and only has a very small performance penalty.

[hgm]

But with leaf nodes I have to check if they are legal because I'm not going to play their child-moves and discover that one of them threatens the king, right?

But why would you want to know whether moves you are not going to play are legal?

Or are there no such leaf nodes once quiescence search is implemented because all attacks are explored and so a captured king would be discovered down the tree?

Normally all leaf nodes would be QS nodes, where you would only have tried captures if you had any. (Or, in a more advanced design, only captures that capture enough to stand a chance to raise the score above alpha (futility pruning), and which don't seem pointless sacrifices (SEE >= 0).) There might be no captures at all, or none of the captures is worth trying, and then you get a leaf node.

There is a theoretical possibility that you are stalemated in this position. (Like a one-in-a-million event...) If you were checkmated, you would be in check, and normally you would know that, and the check extension would then upgrade the node to d=1, and you would search all evasions, not just the captures. And the QS reply would notice the King capture after illegal ones. An additional consideration is that in QS you will only search moves if the static evaluation (symbolizing the expected score for the best non-capture) did not already cause a beta cutoff. If that is not the case, the entire node will fail low if it cannot find a capture to raise the score. And it makes no difference whether you fail low because the eval was not high enough, or because you are checkmated; a fail low is a fail low.

To guard against a stalemate you would have to prove that you have at least one legal move. This would make a difference if you are ahead and eval >= beta, so that you would take a stand-pat cutoff (fail high), while in fact you are stalemated and have score 0, which would make you fail low. So you could never take the stand-pat opportunity in QS, but would always have to generatese moves (both captures and non-captures), and keep testing them for legality until you found a legal one. And you would only ever benefit from all that effort when the search happens to hit a position where the player that is ahead gets stalemated.

[hgm]

I won't speak for H.G., but from my perspective, I was assuming that legality would be checked before descending in the search. For one thing, it's not just the king being in check, but squares crossed during a castle move. So, I'll generate all my pseudo-legal moves, but the search will make the move, and if it's not legal, it will ignore it, unmake the move, and proceed to the next move.

Castling through check is a different matter. Castlings are rare in the tree, so the speed with which you handle them is hardly relevant. One could even argue that the ability to castle brings zero Elo, as Elo is measured by playing from positions where the players have already castled, so that you might as well omit it.

But, like legality testing, it usually simplifies as well as speeds up the engine when you defer testing its legality to the child node. Again, presumably your engine knows when it is in check, so you can simply refrain from generation of any castlings in that case. Castling into check can be treated like any move that exposes your King. So the only thing special here is the castling through check.

If your move generator already tests for King capture on the captures it generates (and aborts returning an error code when it finds one), there is a very cheap kludge to detect castling through check: when the previous move was a castling, replace the involved Rook by a second King, generate the moves for the other player, and change it back into a Rook. The same test that detects King capture will then also detect the passing through check. For orthodox Chess this will work (as the King will only pass through one square). You could even write your MakeMove castling code such that it will always 'promote' the Rook to King, and leave it to the child node to finish the castling by demoting it back to a Rook, after move generation.