Tracking castling rights

[lojic]

I finally implemented perft. I didn't discover any bugs in move generation (although I should've done perft before I painfully debugged my move generation manually by playing games!!), but I fixed a bunch of bugs in my fen parsing :) One of them was related to my "piece has moved" bit which the fen parser didn't set properly.

This leads me to castling rights. Rather than track castling rights in my game state, I have a "piece has moved" bit in my pieces. When I originally decided to do this, I thought I'd use it for both castling and double pawn pushes, but obviously, it's not needed for the double pawn push, knowing the rank is sufficient - oops :)

I determine castling rights by whether the king or rook has moved. When I generate a move, I store the moving piece in the move, so it's easy to restore that "piece has moved" bit when unmaking a move - I just need to treat the rooks specially when unmaking a castle move, and this is easy since if the rook was involved in a castle, then I know it didn't have the moved bit set before the castle.

It seems like the "normal' way of tracking castling rights is to store it in the game state, but I think you'd need to store it per depth level analogously to tracking the EP square. Any thoughts on the best way to track castling rights?

[mathmoi]

I've always treated castling rights and "pawn that can be taken en passant" part of the position. When I make and unmake move I also update theses values. If a rook moves from the first row (different for black) and columns a or h (may be different in chess360) I reset the appropriate castling right flag. If the king move from it's original position I reset both castling rights.

[eligolf]

This seems a bit flawed since if another piece captures either of your rooks you also lose castling rights. Is this implemented in some other logic in your code?

I use 4 bits for castling rights similar to Maksims tutorial https://www.youtube.com/watch?v=zOWPZ4fuLGg. I think this is a fast way of updating and maintaining the rights. Then I add the rights to my move_log (along with ep square, halfmove clock etc) so that I can resotre it when unmaking a move.

[mvanthoor]

This seems a bit flawed since if another piece captures either of your rooks you also lose castling rights. Is this implemented in some other logic in your code?

It can be done though.

- Check if the king has moved.
- Check if you have the left rook, and if it has moved.
- Check if you have the right rook, and if it has moved.

It's going to work, but it's also going to be slow, because you have to check if you have castling rights, over and over again. In the end you'll come to the conclusion that its much faster to just keep this saved in the game state as 4 bits: 1 for WKS, WQS, BKS, BQS each. You have all castling rights when you start, and disable them when needed.

I can't remember that I saw any engine do this differently apart from some esoteric ones written in a programmaing language that couldn't do bit manipulation...

[hgm]

Well, in principle it hardly matters how slow it is. Because only a small fraction of the moves are castlings, and during most of the game you will not be able to castle at all. In fact, when playing games from opening lines for measuring Elo, changes are good that you never have to think about castling at all, because it already happened in the opening. Then the test 'King has moved' is the only test you would have to do, and it will not be any slower than testing a flag that immediately tells you whether you can castle. Especially since you would have to test two of those.

That being said; I used the system of a 'virgin bit' in each of the pieces also in micro-Max. Both for the castling and for the double Pawn push.

A more common method is to put all virgin flags for the pieces you want to track this for in a single integer variable, and have a board-sized array of similarly formatted 'spoilers', which specifies which virginities are destroyed by a move to or from a given square. The MakeMove can then do something like

rights = oldRights & spoiler[fromSqr] & spoiler[toSqr];

The details depend on whether virginity is indicated by a 0 or a 1 bit. Since in orthodox Chess Rook virginity is only relevant for castling, you could moves to and from the King square also have destroy the virginity of both Rooks, so that they become castling-rights flags rather than pure virginity flags. Then you only have to test a single bit, and you don't even have to test whether the Rook is actually present, because it cannot be absent when the rights still exist. Of course you still have to test plenty of other things (clear path, etc.).

If you would test whether the Rook and King are present, there would be no need to involve spoiler[fromSqr] in MakeMove(), as on occupied squares the spoiler[toSqr] would always have destroyed the rights when the current occupant moved there, and can only exist if no one ever moved there, and the piece on it thus must be the original.

The advantage of mainitainig a word with the lowest 4 bits indicating the castling rights is that you can use it as an index in a 16-entry table of Zobrist keys to include the castling rights in the hash key. The most efficient way of doing this is to keep it out of the incremental update, and only handle the key for the board position incrementally. When probing the hash you can then do

totalKey = boardKey ^ castlingKeys[rights];

before using totalKey in the access. Similarly, you can also keep a table for how much you have to award the possession of various combinations of castling rights in the evaluation. (But it is likely you would want to make that dependent on the quality of the Pawn shield at the destination, and perhaps the 'readiness' for that particular castling (number of pieces that still block it).

[lithander]

I'm not using bitboards and my castling rights are managed like this:

Whenever a move is made the move has a fromIndex identifying the square the move starts from and toIndex, the square the move targets.

Code: Select all

UpdateCastlingRights(move.FromIndex);
UpdateCastlingRights(move.ToIndex);

and I just assume that any move from or to a king or rook squares will negate a castling right:

Code: Select all

        
if (squareIndex == WhiteKingSquare || squareIndex == WhiteQueensideRookSquare)
	SetCastlingRights(CastlingRights.WhiteQueenside, false);
if (squareIndex == WhiteKingSquare || squareIndex == WhiteKingsideRookSquare)
	SetCastlingRights(CastlingRights.WhiteKingside, false);

if (squareIndex == BlackKingSquare || squareIndex == BlackQueensideRookSquare)
	SetCastlingRights(CastlingRights.BlackQueenside, false);
if (squareIndex == BlackKingSquare || squareIndex == BlackKingsideRookSquare)
	SetCastlingRights(CastlingRights.BlackKingside, false);

It's probably not very sophisticated but seems to catch all cases where castling rights should get lost!

[mvanthoor]

I'm not using bitboards and my castling rights are managed like this:

Whenever a move is made the move has a fromIndex identifying the square the move starts from and toIndex, the square the move targets.

....

It's probably not very sophisticated but seems to catch all cases where castling rights should get lost!

Have you also taken into account somewhere that you can lose castling rights when one of the rooks is captured before it has even moved?

Run a perft test using Position 2, Kiwipete

Pawn h3 can capture rook h1 on the 4th ply. It took me some time to realize that I never accounted for lost castling rights due to a rook capture, because I never accounted it over the board, and never seen it in a real game played after 1875 or so.

[lithander]

Have you also taken into account somewhere that you can lose castling rights when one of the rooks is captured before it has even moved?

It can't be captured without a move targeting the rook's square. So for these cases UpdateCastlingRights(move.ToIndex) will revoke the castling rights!

I got the correct Perft 5 result on the position you linked: 193.690.690

[lojic]

This seems a bit flawed since if another piece captures either of your rooks you also lose castling rights. Is this implemented in some other logic in your code?

I'm not sure I understand what you think is flawed. Naturally, to be able to castle, the rook has to exist and not have moved. If it's captured, it not longer exists, so I won't generate a castle move on that side. It works fine, but if doing it the normal way is faster, it's worth changing.

[lojic]

I'm not using bitboards and my castling rights are managed like this:

Whenever a move is made the move has a fromIndex identifying the square the move starts from and toIndex, the square the move targets.

Code: Select all

UpdateCastlingRights(move.FromIndex);
UpdateCastlingRights(move.ToIndex);

and I just assume that any move from or to a king or rook squares will negate a castling right:

Code: Select all

        
if (squareIndex == WhiteKingSquare || squareIndex == WhiteQueensideRookSquare)
	SetCastlingRights(CastlingRights.WhiteQueenside, false);
if (squareIndex == WhiteKingSquare || squareIndex == WhiteKingsideRookSquare)
	SetCastlingRights(CastlingRights.WhiteKingside, false);

if (squareIndex == BlackKingSquare || squareIndex == BlackQueensideRookSquare)
	SetCastlingRights(CastlingRights.BlackQueenside, false);
if (squareIndex == BlackKingSquare || squareIndex == BlackKingsideRookSquare)
	SetCastlingRights(CastlingRights.BlackKingside, false);

It's probably not very sophisticated but seems to catch all cases where castling rights should get lost!

How do you restore castling rights? Are you making a copy of the board state? I'm doing incremental make-move, unmake-move, so if I switch from my current has-moved? approach, I'll need to be able to restore castling rights when unmaking a king or rook move.