A question on rotated bitboard

[n_ven]

Hi All,

I am a novice chess programmer started to build a simple chess engine based on bitboards. This query is regarding the rotated bitboard. In almost all the internet pages, I see that we need to have a lookup table represented as rank_attacks[64][256], file_attacks[64][256] for caching the attack table for sliding pieces. My question is why do we need to calculate the attack table for all the 64 squares. i.e Cant we just have rank_attacks[256], file_attacks[256] as this table is going to be the same for all the ranks regardless of the square and when we need to calculate the attack table say, for square 43 with rank state 10011101(157), we can just do

rank_attacks[157]<<8*5 (Square 43 lies on rank 5)

The only drawback I see is the calculation of the rank for a given position requires a division. i.e 43/8 = rank 5

Is my understanding correct or am I missing something here.

Thanks,
Venkatesh N

[khearn]

A factor of 8 definitely matters for the sake of determining where your moving piece is in the occupancy set (you have different legal targets along the first rank from e1 than a1 if say c1 is occupied). You could probably shift it back along the other direction (though instead of multiply and divide/modulus you can use bitwise ands and shifts to extract rank or file from square and multiply/divide by 8). Not sure if it's worth the effort.

If size of tables really concerns you, you can reduce the 256 to 64 though because the outer bits don't matter in the occupied state (there's no square behind them to block). Just shift by 1 bit further to take off the low bit, and mask off the high bit when building your occupancy byte.

[khearn]

Oh and http://chessprogramming.wikispaces.com/ ... ce+Attacks provides a nice collection of the various options available for sliding piece attacks with bitboards. There's a lot of them, and personally i find rotated bitboards the most confusing of them.

[n_ven]

If size of tables really concerns you, you can reduce the 256 to 64 though because the outer bits don't matter in the occupied state (there's no square behind them to block). Just shift by 1 bit further to take off the low bit, and mask off the high bit when building your occupancy byte.

Thanks.. Read that too..

A factor of 8 definitely matters for the sake of determining where your moving piece is in the occupancy set (you have different legal targets along the first rank from e1 than a1 if say c1 is occupied). You could probably shift it back along the other direction (though instead of multiply and divide/modulus you can use bitwise ands and shifts to extract rank or file from square and multiply/divide by 8). Not sure if it's worth the effort.

Thanks. As you said I can use bitwise operation instead of division / multiplication. So in this case can we just have the lookup table as rank_attack[64] or should we have rank_attack[64][64] computed for all the 64 squares. I just want to make sure, If my idea is correct and by not calculating the table for all the 64 squares and keeping it as an extra dimension in the array, I am not missing anything (like introduce bugs, huge performance difference, etc)..

[khearn]

It needs to be rank_attacks[8*64] at the minimum, to distinguish between the 8 files that the moving piece could be on. a1 vs a5 can be distinguished by shifting the result back. but a1 vs e1 are different attack sets for each occupancy set. the opposite is of course the case for file_attacks.

[n_ven]

a1 vs a5 can be distinguished by shifting the result back

Agreed. This is what I need to ensure.

but a1 vs e1 are different attack sets for each occupancy set. the opposite is of course the case for file_attacks.

Can't that be distinguished as one of the 64 states..

Suppose the rook is on a1, and there is one more piece on g1, the state of the rank is "10000010" (I am including the rook in the state)
If the rook is on e1, the rank state is "00001010". Obviously both have different states(rank_attack[130] & rank_attack[10]) and can have different attack sets.

[n_ven]

I think I got the point, In the example above for the rank state "10000010", if we swap the rook and the other piece, the state remains the same and hence the attack set for the rook swapped to g1 would be wrong. So we need a way to distinguish where the rook is and hence there has to be 64*8 states. Thanks khearn.

[hyatt]

Hi All,

I am a novice chess programmer started to build a simple chess engine based on bitboards. This query is regarding the rotated bitboard. In almost all the internet pages, I see that we need to have a lookup table represented as rank_attacks[64][256], file_attacks[64][256] for caching the attack table for sliding pieces. My question is why do we need to calculate the attack table for all the 64 squares. i.e Cant we just have rank_attacks[256], file_attacks[256] as this table is going to be the same for all the ranks regardless of the square and when we need to calculate the attack table say, for square 43 with rank state 10011101(157), we can just do

I don't quite follow your "they will be the same for..." If you put a sliding piece on any one of the 64 square, you have 64 different attack patterns, one for each square. But since the pieces slide, you need that [256] for rooks (actually you can reduce this to 64 since the endpoint on a rank/file/diagonal can be empty or occupied without changing the attacks.)

So for each of 64 squares, there are 256 (since a rank has 8 bits) possible attacks along that rank from that square. You can optimize some of this away if you want. For example, you can't attack the square you are sitting on, so now you only have 7 significant squares. And the endpoints are not needed so you are down to 32. But the addressing becomes tricky. Tricky enough that the extra math will cost more than the larger array.

rank_attacks[157]<<8*5 (Square 43 lies on rank 5)

The only drawback I see is the calculation of the rank for a given position requires a division. i.e 43/8 = rank 5

Is my understanding correct or am I missing something here.

Thanks,
Venkatesh N

[hyatt]

If size of tables really concerns you, you can reduce the 256 to 64 though because the outer bits don't matter in the occupied state (there's no square behind them to block). Just shift by 1 bit further to take off the low bit, and mask off the high bit when building your occupancy byte.

Thanks.. Read that too..

A factor of 8 definitely matters for the sake of determining where your moving piece is in the occupancy set (you have different legal targets along the first rank from e1 than a1 if say c1 is occupied). You could probably shift it back along the other direction (though instead of multiply and divide/modulus you can use bitwise ands and shifts to extract rank or file from square and multiply/divide by 8). Not sure if it's worth the effort.

Thanks. As you said I can use bitwise operation instead of division / multiplication. So in this case can we just have the lookup table as rank_attack[64] or should we have rank_attack[64][64] computed for all the 64 squares. I just want to make sure, If my idea is correct and by not calculating the table for all the 64 squares and keeping it as an extra dimension in the array, I am not missing anything (like introduce bugs, huge performance difference, etc)..

I do not see how you can get away with rank_attacks[64]. You have 64 squares on the board. Each group of 8 of those squares is on a different rank, which means a different set of bits will be 1's. And for each rank, different squares can be occupied, blocking sliding attacks.

How can you reduce that to just 64?

I can see rank_attacks[64][32] if you want to get cute with the rank occupied bits. But I can't see a vector rather than a 2d array.

[n_ven]

Hi Hyatt,

I don't quite follow your "they will be the same for..." If you put a sliding piece on any one of the 64 square, you have 64 different attack patterns, one for each square. But since the pieces slide, you need that [256] for rooks (actually you can reduce this to 64 since the endpoint on a rank/file/diagonal can be empty or occupied without changing the attacks.)

I agree that there would be 64 different attack patterns. But, I would keep only the first 8 of them in a 8*256 table (instead of 64*256) and derive the rest by shifting i.e I would keep the 256 state attack table for each of the 8 rook positions in a file for a base rank i.e rank_attack[8][256] and derive the attack set for the rest of the ranks from the table by bit shifting by 8*(rank - 1).

For e.g, If the rook is on square d1(file 4, rank 1) and if there are 2 pieces on a1 and h1, The attack set(rank_attack[3][129]) would be,

00000000
00000000
00000000
00000000
00000000
00000000
00000000
01101110

And if we want to calculate the attack set for square d2(file 4, rank 2), I would left shift the above state by 8*(rank-1) which is,

(i.e rank_state[3][129]<<8*1)

00000000
00000000
00000000
00000000
00000000
00000000
01101110
00000000

I do not see how you can get away with rank_attacks[64]. You have 64 squares on the board. Each group of 8 of those squares is on a different rank, which means a different set of bits will be 1's. And for each rank, different squares can be occupied, blocking sliding attacks.

How can you reduce that to just 64?

Initially I was confused. Now I understood and agree that we just cant have a 1d rank_attack[64] and we would need the table for each of the rook position in a file i.e rank_attack[8][64].

Thanks,
Venkatesh N