How is legality of castling usually determined?

[evert823]

Castling is illegal if any square between the King's initial and final square is attacked by an opponent's piece.
But my question is about how to determine this in a given position.

My current thought is that this is part of 2 plies deep calculation. If we call the current position P0: If any opponent's responses, to any of our moves, targets any square between the King's initial and final square, then castling is illegal in P0.

Since any attempt to implement this rule, inevitably leads to doing some calculation work, I would say that this is the only efficient way to do it.

My question is, is this the right way of thinking?

[chrisw]

No and no.

Assuming not incheck, king-rook moved status allows and inbetween squares are vacant:

For the inbetween squares use three precomputed constants to mask KNP positions which would attack any inbetween.
For each inbetween square test if diagonal piece on precomputed 2-diagonal mask, for each found test if inbetween squares vacant -> illegal
For each inbetween square test if manhattan piece on precomputed 1-file mask, and test inbetween vacant

[osvitashev]

Using move generation / searching 2 plies deep to check castling rights is wrong.
It is slow, but more importantly it would give incorrect results in some cases.
Consider this:
[d]2k5/8/8/8/2b5/8/6PP/2R1K2R w K - 0 1

White is not allowed to castle, even though c4f1 is not a legal move!

For check detection, you might already have something like

Code: Select all

bool isSquareAttackedBy(int sq, int pieceType, int side)

And then for castling, you could call it for every square which determines castling rights.
It is not very fast, but intuitive. If you want to do it faster, you can use precalculated masks like chrisw suggested. This is slightly more tricky to implement, though.

[Mike Sherwin]

If you are looking for a speedy alternative and your engine has pseudo-legal move generation you can put 3 kings on the board for the next move generation and if any of the kings are captured then castling was illegal. I do it this way in Carnivor. I read once that HGM does it that way in at least one of his engines, iirc.

[evert823]

Using move generation / searching 2 plies deep to check castling rights is wrong.
It is slow, but more importantly it would give incorrect results in some cases.
Consider this:
[d]2k5/8/8/8/2b5/8/6PP/2R1K2R w K - 0 1

White is not allowed to castle, even though c4f1 is not a legal move!

For check detection, you might already have something like

Code: Select all

bool isSquareAttackedBy(int sq, int pieceType, int side)

And then for castling, you could call it for every square which determines castling rights.
It is not very fast, but intuitive. If you want to do it faster, you can use precalculated masks like chrisw suggested. This is slightly more tricky to implement, though.

That makes sense. This is what I decided to do. Thanks everybody for the responses.

[evert823]

If you are looking for a speedy alternative and your engine has pseudo-legal move generation you can put 3 kings on the board for the next move generation and if any of the kings are captured then castling was illegal. I do it this way in Carnivor. I read once that HGM does it that way in at least one of his engines, iirc.

This question about legality of castling can also aksed about how to determine mate and stalemate. Do we let it come from calculations that we're going to do anyways, or do we implement it specifically? The first option means we generate pseudo-legal moves.
I also read once that HGM does it that way.

[syzygy]

If you are looking for a speedy alternative and your engine has pseudo-legal move generation you can put 3 kings on the board for the next move generation and if any of the kings are captured then castling was illegal. I do it this way in Carnivor. I read once that HGM does it that way in at least one of his engines, iirc.

This question about legality of castling can also aksed about how to determine mate and stalemate. Do we let it come from calculations that we're going to do anyways, or do we implement it specifically? The first option means we generate pseudo-legal moves.
I also read once that HGM does it that way.

Since you mention generating pseudo-legal moves, I think you are really asking about checking move legality rather than mate and stalemate?

Some engines generate legal moves only. A legal move generator can still be quite fast, and it simplifies the rest of the engine, but ultimately it is a loss once your search starts to have a low effective branching factor. You end up checking legality for too many moves that the search never even looks at. So it is better to generate pseudo-legal moves and leave the legality checking for later. (When generating check evasions you might want to generate only legal moves or at least filter out most non-legal moves during generation.)

I don't think any chess engine attempts to detect mate and stalemate without generating moves.

[syzygy]

So it is better to generate pseudo-legal moves and leave the legality checking for later.

So I mean "better" only because ultimately it should be slightly faster. There are certainly very good arguments for sacrificing a tiny bit of speed in return for the elegance and simplicity of legal move generation.

[Uri Blass]

If you are looking for a speedy alternative and your engine has pseudo-legal move generation you can put 3 kings on the board for the next move generation and if any of the kings are captured then castling was illegal. I do it this way in Carnivor. I read once that HGM does it that way in at least one of his engines, iirc.

This question about legality of castling can also aksed about how to determine mate and stalemate. Do we let it come from calculations that we're going to do anyways, or do we implement it specifically? The first option means we generate pseudo-legal moves.
I also read once that HGM does it that way.

Since you mention generating pseudo-legal moves, I think you are really asking about checking move legality rather than mate and stalemate?

Some engines generate legal moves only. A legal move generator can still be quite fast, and it simplifies the rest of the engine, but ultimately it is a loss once your search starts to have a low effective branching factor. You end up checking legality for too many moves that the search never even looks at. So it is better to generate pseudo-legal moves and leave the legality checking for later. (When generating check evasions you might want to generate only legal moves or at least filter out most non-legal moves during generation.)

I don't think any chess engine attempts to detect mate and stalemate without generating moves.

A legal move generator does not work by checking legality of every pseudo legal move.
Movei has a legal move generator and when it detects that the knight is pinned it does not need to generate moves for the knight.

I do not claim that pseuso legal move generation is not faster but only that there are places when you save time by legal move generator.

Movei also detect mate and stalemate without generating moves(assuming that there is a mate or stalemate)
Trying to generate legal moves and generating 0 moves is not what I consider generating moves.

[syzygy]

A legal move generator does not work by checking legality of every pseudo legal move.
Movei has a legal move generator and when it detects that the knight is pinned it does not need to generate moves for the knight.

True, my wording was not optimal. But the point is still that you do extra work.

I do not claim that pseuso legal move generation is not faster but only that there are places when you save time by legal move generator.

When I implemented legal move generation in my own (weak) engine, it was a speed up. When I converted Stockfish to legal move generation, it was a loss. The reason is that SF does much more pruning than my weak engine.

If you just want to calculate perft, then legal move generation will be a win.

Movei also detect mate and stalemate without generating moves(assuming that there is a mate or stalemate)
Trying to generate legal moves and generating 0 moves is not what I consider generating moves.

Well, I call that generating (legal) moves.
The OP wrote this:

This question about legality of castling can also aksed about how to determine mate and stalemate. Do we let it come from calculations that we're going to do anyways, or do we implement it specifically?

If we do it by generating legal moves and concluding from no moves being generated that the position is mate or stalemate, then "we let it come from calculating that we're going to do anyways". If legal moves are generated, you will of course use them, i.e. it was a calculation that you were going to do anyway.

Anyway, both legal move generation and pseudo-legal move generation are good options. I don't think legal move generation can be a win in a program with a Stockfish-like search, but when done right it won't be a design choice that will hold the engine back. (And I would be happy to be proved wrong and see Stockfish converted to legal move generation.)