Updating castling rights

[hgm]

An alternative is to use a lookup table indexed by square:

Code: Select all

state &= table[move.from] & table[move.to]

(I think this works, I haven't tried it.)
The disadvantage of this approach is the additional lookup table, of which only 6 entries are really used.

Why would you worry about that extra table? You don't have to store it by board square, you could square it by piece number in the piece list, which can be smaller than 64 entries.

And even if not: encoding extra bits in the pieces on the board, forces you to take a board of integers. Two tables of 64 characters would be smaller. And fetching operands from memory is often faster on x86 machines than using tonly operands from registers. (Apparently there is only a limited number of ports to the register file, so reading them can become a bottle-neck, so instructions would have to be postponed, where feeding them into the ALU directly from the load unit would have been possible during the same cycle.

[wgarvin]

And even if not: encoding extra bits in the pieces on the board, forces you to take a board of integers. Two tables of 64 characters would be smaller.

Not really. You only need 4 bits to distinguish piece type and side, so there's easily room for 1 flag or perhaps even 2-4 flags in a piece encoding that still fits in a byte.

My objection to adding this stuff in the piece encoding is that you have to do an extra masking step before using the piece type as an index into a table. (Either that, or enlarge the tables). I'd rather represent castling rights in some other way which don't cause some rooks to not look like other rooks, and cause me to have two different kinds of white king... etc.

[hgm]

My objection to adding this stuff in the piece encoding is that you have to do an extra masking step before using the piece type as an index into a table.

That is what I assumed: that teh board would contain the piece numbers, not the piece types. Then you could not do with 4 bits. In most variants you could not do with 4 bits anyway, even for the piece types.

[bob]

My program updates castling rights (4 bits) using masks which are part of the piece encoding:

Code: Select all

state &= board[move.from] & board[move.to] & MASK;

However this requires two types of rook encodings per color, which I don't like and want to remove.

An alternative is to use a lookup table indexed by square:

Code: Select all

state &= table[move.from] & table[move.to]

(I think this works, I haven't tried it.)
The disadvantage of this approach is the additional lookup table, of which only 6 entries are really used.

So can anyone think of yet another approach for simple, branchless castling rights update?

Why not just a 4-bit value, right two bits for white, left two bits for black. Each bit represents a potential castle option. xxx1 = white can play o-o, xx1x = white can play o-o-o. ditto for two black bits. Whenever you move a rook, clear that side's bit for castling to the edge with the rook. If the king moves, clear both bits. No need to over-think this. Any rook move from a1 kills o-o-o forever, any king move kills castling either way forever, etc... the simple test for source = a1 in the MakeMove() code for rook is a branch that will be predicted 100% once you can no longer castle, so it won't hurt a thing.

[hgm]

That is exactly what he does, but with the quirk that the masks deciding which bits to clear are coming from the piece codes themselves, rather than from a separate table.

[Jan Brouwer]

An alternative is to use a lookup table indexed by square:

Code: Select all

state &= table[move.from] & table[move.to]

(I think this works, I haven't tried it.)
The disadvantage of this approach is the additional lookup table, of which only 6 entries are really used.

Why would you worry about that extra table? You don't have to store it by board square, you could square it by piece number in the piece list, which can be smaller than 64 entries.

It's not a big concern, just another item / extra code. Also my piece list is not really smaller than the board, I use a fixed offset per piece type.

And even if not: encoding extra bits in the pieces on the board, forces you to take a board of integers. Two tables of 64 characters would be smaller. And fetching operands from memory is often faster on x86 machines than using tonly operands from registers. (Apparently there is only a limited number of ports to the register file, so reading them can become a bottle-neck, so instructions would have to be postponed, where feeding them into the ALU directly from the load unit would have been possible during the same cycle.

I will try to see if using tables i.o. piece encodings gives a performance boost.

[Jan Brouwer]

My program updates castling rights (4 bits) using masks which are part of the piece encoding:

Code: Select all

state &= board[move.from] & board[move.to] & MASK;

However this requires two types of rook encodings per color, which I don't like and want to remove.

An alternative is to use a lookup table indexed by square:

Code: Select all

state &= table[move.from] & table[move.to]

(I think this works, I haven't tried it.)
The disadvantage of this approach is the additional lookup table, of which only 6 entries are really used.

So can anyone think of yet another approach for simple, branchless castling rights update?

Why not just a 4-bit value, right two bits for white, left two bits for black. Each bit represents a potential castle option. xxx1 = white can play o-o, xx1x = white can play o-o-o. ditto for two black bits. Whenever you move a rook, clear that side's bit for castling to the edge with the rook. If the king moves, clear both bits. No need to over-think this. Any rook move from a1 kills o-o-o forever, any king move kills castling either way forever, etc... the simple test for source = a1 in the MakeMove() code for rook is a branch that will be predicted 100% once you can no longer castle, so it won't hurt a thing.

Like H.G. already mentioned, I do use 4 bits for castling state.
The only code then needed in MakeMove(), by embedding the update mask in the piece value, is something like:

Code: Select all

state &= piece & captured_piece & MASK;

The disadvantage is that you need 3 different rook piece values (one for the rook on A1/A8, one for H1/H8, and one for promoted rooks).

[bob]

That is exactly what he does, but with the quirk that the masks deciding which bits to clear are coming from the piece codes themselves, rather than from a separate table.

Not quite. I don't use anything but the square for this.

I have a separate piece of code for moving pawns, knights, etc...

in the rook move code:

if square == a1 castle&=0x0d;
if square == h1 castle&=0x0e;

in king move code:

castle &= 0xc0;

Of course the three AND masks are different for black and white. And square is the "from" square assuming white is moving, or "to" for black, since capturing either white rook ends castling to that side from here on...

In a typical program, make/unmake is < 10% of total time, so worrying about saving 0.1% of less than 10% is not exactly productively spent time.

[bob]

My program updates castling rights (4 bits) using masks which are part of the piece encoding:

Code: Select all

state &= board[move.from] & board[move.to] & MASK;

However this requires two types of rook encodings per color, which I don't like and want to remove.

An alternative is to use a lookup table indexed by square:

Code: Select all

state &= table[move.from] & table[move.to]

(I think this works, I haven't tried it.)
The disadvantage of this approach is the additional lookup table, of which only 6 entries are really used.

So can anyone think of yet another approach for simple, branchless castling rights update?

Why not just a 4-bit value, right two bits for white, left two bits for black. Each bit represents a potential castle option. xxx1 = white can play o-o, xx1x = white can play o-o-o. ditto for two black bits. Whenever you move a rook, clear that side's bit for castling to the edge with the rook. If the king moves, clear both bits. No need to over-think this. Any rook move from a1 kills o-o-o forever, any king move kills castling either way forever, etc... the simple test for source = a1 in the MakeMove() code for rook is a branch that will be predicted 100% once you can no longer castle, so it won't hurt a thing.

Like H.G. already mentioned, I do use 4 bits for castling state.
The only code then needed in MakeMove(), by embedding the update mask in the piece value, is something like:

Code: Select all

state &= piece & captured_piece & MASK;

The disadvantage is that you need 3 different rook piece values (one for the rook on A1/A8, one for H1/H8, and one for promoted rooks).

Why not just ignore the piece and focus on the _square_? Any move from/to a1 eliminates o-o-o for white permanently. Any move from e1 eliminates o-o/o-o-o permanently. This is such a tiny percentage of a very small part of your program, efficiency is moot.

[wgarvin]

That is exactly what he does, but with the quirk that the masks deciding which bits to clear are coming from the piece codes themselves, rather than from a separate table.

Not quite. I don't use anything but the square for this.

I have a separate piece of code for moving pawns, knights, etc...

in the rook move code:

if square == a1 castle&=0x0d;
if square == h1 castle&=0x0e;

in king move code:

castle &= 0xc0;

Of course the three AND masks are different for black and white. And square is the "from" square assuming white is moving, or "to" for black, since capturing either white rook ends castling to that side from here on...

In a typical program, make/unmake is < 10% of total time, so worrying about saving 0.1% of less than 10% is not exactly productively spent time.

Better if it can be done without if-tests though. Using a table indexed by source square and destination square, to mask off the appropriate rights, is branchless, but it uses a couple L1 cache lines. For bitboard programs, the "bitboard of squares that don't have their castling right" is also branchless and extremely lightweight. When generating the castling moves, you just have to test one byte of the bitboard with a mask containing the two bits (one for a rook, one for a king) and if either of them is set you know the move is not legal anymore. So its cheap in makemove and in the move generation.