FRC / Chess960 -- Some Lessons I Learned

[AndrewGrant]

I've recently gone through the process of adding FRC/Chess960 support to Ethereal. There was some work done by Lucas Braesch that served as a nice starting point, but it took many hours of fighting weird errors to get to the point where I can pass all of my PERFT testing, and play games against Stockfish without crashing or reporting illegal moves.

I'm doing this little write up for two reasons. One, it would have been useful to me to have an idea of what it takes to go from Standard to FRC/Chess960, so perhaps this may have some value to others Two, I generated what I think is a reasonable (and large) set of PERFT tests which others may use in the future.

As for Ethereal, as I write this I am doing the finishing touches on verifying PERFT, as well as playing games against master (non FRC) in order to measure the slow down. Currently the elo loss is around 1 to 2, played at 10+.1s, which I think is quite respectable for the overhead that FRC involves. I'm always scared to push things like this, since something may break no matter how careful I am, but I plan to push this before Version 11.50. Hopefully if there are any bugs, they appear to me before the proper release of V11.50. If you would like to play around with the tentative FRC support, I can always provide binaries.

#1 Move Encoding

In this process I think I came across the answer to the question "Why does Stockfish encode castle moves as King captures Rook". I chose a different route, but I'll write a bit about both.

The benefit, or the reason, that Stockfish encodes using KxR is because at many points in the engine you will need to be able to determine if a given move is a king side or queen side castle. That may sound trivial -- in fact until I was nearly done implementing it I thought I could simply take the starting square of the king and compare it to the ending square. But then you run into the caveat for FRC which is that the King might not even move during the castle. By encoding as King captures Rook, figuring out which side you are castling to is trivial.

I decided instead to set one of the extra bits in the uint16_t that represents moves in Ethereal. That bit says whether or not the castle is king side or queen side. Technically, the bits were open to use, but this was a bit of a hack, and to anyone starting from the ground I would recommend the Stockfish paradigm. One setback to my method is that additional getlsb() & getmsb() calls are needed to locate the rook you are castling to. But as I said above, the elo loss (read: speed loss) is quite minimal, so ... c'est la vie

#2 Apply and Reverting Moves

Assuming you have a working engine for Standard chess, I only have one idea to add here which tripped me up. Namely, the king and rook might not be moved during a given castle move. Additionally, the king may move to the rook's square, or the rook may move to the king's square. This threw out a few assumptions I had in Ethereal. Namely:

For reverting a move, I would do something like this:

Code: Select all

board->squares[from] = board->squares[to]; board->squares[to] = EMPTY

For Standard chess, this moves the King back where it started. But if from == to, then you've just deleted your king. The same applies for rooks. For bitboards, this can crop up again but in a new form:

Code: Select all

board->pieces[KING] ^= (1ull << from) ^ (1ull << to)

This will work for FRC/Standard, but if we instead use a bitwise-or, we will run into the same issue.

Thankfully, this issue is easy to spot. If pieces disappear, especially the King, something is going to crash ASAP

#3 FEN parsing

This one is fairly simple, but Lucas gave me a really good starting point for this. I can see how someone could come up with a very contrived way of doing this. Below is my code for parsing the Castle Rights portion of the FEN. For Ethereal, board->castleRooks is an uint64_t, with a bit set for each rook that has the potential to be castled with. The use of getmsb and getlsb, to play around with king vs queen side appears in many places for me after adding FRC support. This parser handles FEN, X-FEN, and SHREDDER-FEN representations. Also, in Ethereal, bit 0 is A1, and bit 7 is H1, hence the corresponding getlsb() & getmsb() calls.

Code: Select all

while ((ch = *token++)) {
    if (ch == 'K') setBit(&board->castleRooks, getmsb(white & rooks & RANK_1));
    if (ch == 'Q') setBit(&board->castleRooks, getlsb(white & rooks & RANK_1));
    if (ch == 'k') setBit(&board->castleRooks, getmsb(black & rooks & RANK_8));
    if (ch == 'q') setBit(&board->castleRooks, getlsb(black & rooks & RANK_8));
    if ('A' <= ch && ch <= 'H') setBit(&board->castleRooks, square(0, ch - 'A'));
    if ('a' <= ch && ch <= 'h') setBit(&board->castleRooks, square(7, ch - 'a'));
}

#4 Development Process & Testing

If you already have a working engine, the nice starting point is to rewrite your move generation and application functions to be generalized. It should not be too hard to get this done and still have the same game-play from your engine in Standard mode. Once you have that framework, you can start playing with FRC positions which will slowly introduce all the corner cases to deal with.

For PERFT testing, I took all 960 of the positions, piped them into Stockfish and had Stockfish play 8 moves at random. This gives a good spread of opening positions, with castle moves possible without too great a depth. Then I used Stockfish to generate a depth 6 PERFT value. The final test suite can be found here ( If this link dies, then the suite will still exist but just on the master branch of Ethereal )

Additionally I wrote the following in order to automate running those positions. If your engine is xboard, or you have a more proper (read: pedantic) implement ion of UCI then tweaks are needed. ( Again, if this link dies, then this file will still exist but just on the master branch of Ethereal )

[Modern Times]

Great news that you've added Chess960 to Ethereal ! I look forward to running the final version.

[Roland Chastain]

I'm always scared to push things like this, since something may break no matter how careful I am, but I plan to push this before Version 11.50. Hopefully if there are any bugs, they appear to me before the proper release of V11.50. If you would like to play around with the tentative FRC support, I can always provide binaries.

Hello! I would be glad to test it. FRC is also my preoccupation of the moment.

[lucasart]

#1 Move Encoding

In this process I think I came across the answer to the question "Why does Stockfish encode castle moves as King captures Rook". I chose a different route, but I'll write a bit about both.

The benefit, or the reason, that Stockfish encodes using KxR is because at many points in the engine you will need to be able to determine if a given move is a king side or queen side castle. That may sound trivial -- in fact until I was nearly done implementing it I thought I could simply take the starting square of the king and compare it to the ending square. But then you run into the caveat for FRC which is that the King might not even move during the castle. By encoding as King captures Rook, figuring out which side you are castling to is trivial.

I decided instead to set one of the extra bits in the uint16_t that represents moves in Ethereal. That bit says whether or not the castle is king side or queen side. Technically, the bits were open to use, but this was a bit of a hack, and to anyone starting from the ground I would recommend the Stockfish paradigm. One setback to my method is that additional getlsb() & getmsb() calls are needed to locate the rook you are castling to. But as I said above, the elo loss (read: speed loss) is quite minimal, so ... c'est la vie

I know you're very focused on raw speed, so I assume your choice is driven by that. In Demolito (which is reasonably fast but not crazy fast like SF or Ethereal), I chose a minimal move_t representation, and let the rest be deduced by context. My move_t only contains (from, to, prom), where prom = NO_PIECE for quickly testing if a move is a promotion or not (could be deduced from context, ie. relative rank 8 + from contains a pawn, but would be slower for no reason). For detecting castling moves, I deduce from context: if we capture an own piece, it can only be a KxR encoded castling move (put some assert for good measure). And the direction of castling is simply deduced like so: if (to > from) /* right side */ else /* left side */.

#2 Apply and Reverting Moves

Assuming you have a working engine for Standard chess, I only have one idea to add here which tripped me up. Namely, the king and rook might not be moved during a given castle move. Additionally, the king may move to the rook's square, or the rook may move to the king's square. This threw out a few assumptions I had in Ethereal. Namely:

For reverting a move, I would do something like this:

Code: Select all

board->squares[from] = board->squares[to]; board->squares[to] = EMPTY

For Standard chess, this moves the King back where it started. But if from == to, then you've just deleted your king. The same applies for rooks. For bitboards, this can crop up again but in a new form:

Code: Select all

board->pieces[KING] ^= (1ull << from) ^ (1ull << to)

This will work for FRC/Standard, but if we instead use a bitwise-or, we will run into the same issue.

Thankfully, this issue is easy to spot. If pieces disappear, especially the King, something is going to crash ASAP

I didn't have this problem thanks to the set_square() and clear_square() that I use systematically. I *never* allow myself to code directly at the lowest level and manipulate the bitboards, zobrist, etc. Only these 2 functions are allowed to do that, and I hope that LTO + inlining will optimize through the resulting code. This saved me a lot of debugging time when I started. But I tried this in Ethereal and it was slower. So here we have a trade off between simplicity vs. speed, unfortunately.

Move generation
An important difference is that you apply the SF method of generating illegal castling moves, where the king walks through attacked squares, and then you filter it before playing the move, by doing some squareIsAttacked() for each square on the king path. Instead I generate legal castling moves directly, and generally all king moves in Demolito are generated legal directly, while others are generated pseudo-legal. The trick to do that is to pre-compute a bitboard pos->attacked that tells you the squares attacked by the opponent.

This may be a slowdown by itself, but there is some (over?)compensation to consider, which can't be obtained without it:
* pos->checkers is only computed when we know that our king is attacked, which is the rare case, so an average speed-up.
* SEE: you already know if you can skip the recapture loop, if the to square is not attacked, you return immediately.
* King move filtration: When checking legality of pseudo-legal moves, simply if (king move) return true. This saves quite a bit of work in the general case.

Also, spending a bit more time generating legal castling moves is not such a big deal. The overhead is small, and anyway this is the rare case during the game, as most positions searched thoughout an average game do not have any "castleRooks".

Anyway, only testing will tell if that works for you. Happy coding (and debugging)!

[hgm]

I would never recommend KxR encoding in an engine. My favorite encoding scheme uses 13 bits for move encoding; from-square, 1-bit flag to indicate whether the move is special or not, and depending on that the to-square or a table index that indicates all additional info on the special move. (Like promotion piece, board step, e.p. victim, Rook from- and to-square.)

This decodes very fast, because the common case only has to ascertain the flag is not set.

In anotger thread I recently described how you could do with 12 bytes, without much loss in speed (and certainly much faster than KxR).

[Evert]

An advantage of KxR is that you don’t have to look for the rook, since its location is right there in the move. It’s a reasonably elegant solution if this is the only really weird move you have to deal with (of course you also have en-passant and promotionsto consider).

[AndrewGrant]

I would never recommend KxR encoding in an engine. My favorite encoding scheme uses 13 bits for move encoding; from-square, 1-bit flag to indicate whether the move is special or not, and depending on that the to-square or a table index that indicates all additional info on the special move. (Like promotion piece, board step, e.p. victim, Rook from- and to-square.)

This decodes very fast, because the common case only has to ascertain the flag is not set.

In anotger thread I recently described how you could do with 12 bytes, without much loss in speed (and certainly much faster than KxR).

I have the following scheme, which seems to be the fastest I can come up with. Ease of move type detection is worth speed, and its about more then just figuring out how to apply the move, you have to consider all the places in evaluation, movepicking, searching, where move type is needed. Promotion type conversation is just a bitshift of the move as well. To/From are encoded in the lower 12 bits, like everyone else.

Code: Select all

    NORMAL_MOVE = 0 << 12, CASTLE_MOVE    = 1 << 12,
    ENPASS_MOVE = 2 << 12, PROMOTION_MOVE = 3 << 12,

    CASTLE_KING_SIDE  = 0 << 14, CASTLE_QUEEN_SIDE = 1 << 14,

    PROMOTE_TO_KNIGHT = 0 << 14, PROMOTE_TO_BISHOP = 1 << 14,
    PROMOTE_TO_ROOK   = 2 << 14, PROMOTE_TO_QUEEN  = 3 << 14,

    CASTLE_KING_MOVE  = CASTLE_MOVE | CASTLE_KING_SIDE,
    CASTLE_QUEEN_MOVE = CASTLE_MOVE | CASTLE_QUEEN_SIDE,

    KNIGHT_PROMO_MOVE = PROMOTION_MOVE | PROMOTE_TO_KNIGHT,
    BISHOP_PROMO_MOVE = PROMOTION_MOVE | PROMOTE_TO_BISHOP,
    ROOK_PROMO_MOVE   = PROMOTION_MOVE | PROMOTE_TO_ROOK,
    QUEEN_PROMO_MOVE = PROMOTION_MOVE | PROMOTE_TO_QUEEN

[AndrewGrant]

This may be a slowdown by itself, but there is some (over?)compensation to consider, which can't be obtained without it:
* pos->checkers is only computed when we know that our king is attacked, which is the rare case, so an average speed-up.
* SEE: you already know if you can skip the recapture loop, if the to square is not attacked, you return immediately.
* King move filtration: When checking legality of pseudo-legal moves, simply if (king move) return true. This saves quite a bit of work in the general case.

Those are some fair points, which I will certainly keep in mind. There have been a number of times I've wanted to generate all attacks and carry that around between moves, so If I return I will make sure to do these things to gain some speed back. Currently, I do not have a moveIsLegal() function. I apply the move, see if we are still in check, and if so revert it. This sounds very slow, but with some knowledge of king attackers the vast majority of moves tried are legal, so it works out.

Thank you for the work you did about a year ago. It gave me a really solid starting point, even if I had to change some things due to differences in how Demoltio / Ethereal operate under the hood.

Cheers, Andrew Grant

[elcabesa]

thank you for your EPD file,

I'm about to release a version of Vajolet with FRC and I thought that my movegen code was correct, but I was wrong
now a small castle bug has been solved

[D Sceviour]

What would be the final castling positions for this initial FRC position? Is queen side castling allowed?

[d]5rkr/8/8/8/8/8/8/RKR5 w - - 0 1