Rotated bitboards
Mats Forsén
Hi all,
I've decided to start anew on a chess engine.
This time in win32 so I can use 64 bit integers
and all available memory.. anyway.. my question
is:
I understand bitboards and flipped bitboards, but
how do you put the diagonals in a bitboard?
They do not have fixed widths or lengh.. agh..
/ gar...@texoma.spamela.com (remove .spamela)
Alessandro Damiani
Mats Forsén wrote:
> ]Hi all,
Why do people use rotated bitboards? We can calculate the index to the
table with all possible attack squares in a simpler way:
Consider the bitboard with all pieces on it, we call it ALLPIECES. Now,
we want to generate all attack squares of a bishop which is on square s.
We devide the bitboard at row(s) in an upper and a lower half and look
at them independently:
1.) upper half: extract the upper diagonals at s by and-ing ALLPIECES
and the upper diagonals-bitboard you read from a table. We or all 8 rows
of the resulting bitboard and get so an 8 bit index i. We access the
first table with AttackFromBishop_DiagonalsUp[s,i], and we get the upper
part of the attack squares of a bishop at s.
2.) lower half: same work. Accessing
AttackFromBitshop_DiagonalsDown[s,j], j is the index of the lower
diagonals at s.
3.) We or both results and get all attack squares. Easy, isn`t it?
To get the attack squares of a rook we follow the same procedure, but
here we don`t use an extra table like needed in 1.) and 2.) to extract
lower and upper half: shifting the bitboard is faster.
Bye bye
Alessandro
Urban Koistinen
Fri, 31 Oct 1997 15:20:37 +0100 Alessandro Damiani wrote:
! Mats Forsén wrote:
! > ]Hi all,
! > ]
! > ]I've decided to start anew on a chess engine.
! > ]This time in win32 so I can use 64 bit integers
! > ]and all available memory.. anyway.. my question
! > ]is:
! > ]
! > ]I understand bitboards and flipped bitboards, but
! > ]how do you put the diagonals in a bitboard?
! > ]
! > ]They do not have fixed widths or lengh.. agh..
! > ]
! > ]/ gar...@texoma.spamela.com (remove .spamela)
! Why do people use rotated bitboards? We can calculate the index to the
! table with all possible attack squares in a simpler way:
! Consider the bitboard with all pieces on it, we call it ALLPIECES. Now,
! we want to generate all attack squares of a bishop which is on square s.
! We devide the bitboard at row(s) in an upper and a lower half and look
! at them independently:
! 1.) upper half: extract the upper diagonals at s by and-ing ALLPIECES
! and the upper diagonals-bitboard you read from a table. We or all 8 rows
! of the resulting bitboard and get so an 8 bit index i. We access the
! first table with AttackFromBishop_DiagonalsUp[s,i], and we get the upper
! part of the attack squares of a bishop at s.
That is a twist:
.*.....*
..*...*.
...*.*..
....B...
........
........
........
........
and
........
........
........
....B...
...*.*..
..*...*.
.*.....*
*.......
instead of:
.*......
..*.....
...*....
....B...
.....*..
......*.
.......*
........
and
.......*
......*.
.....*..
....B...
...*....
..*.....
.*......
*.......
! 2.) lower half: same work. Accessing
! AttackFromBitshop_DiagonalsDown[s,j], j is the index of the lower
! diagonals at s.
! 3.) We or both results and get all attack squares. Easy, isn`t it?
Why would upper&lower be faster than upright&downright?
Shorter words?+)
! To get the attack squares of a rook we follow the same procedure, but
! here we don`t use an extra table like needed in 1.) and 2.) to extract
! lower and upper half: shifting the bitboard is faster.
Here is my way of describing what you are doing:
Don't store the rotated bitmaps, instead rotate the bits that
are needed to be rotated when they are needed.
As only one line of bits are needed at a time,
they can be gotten into a byte much cheaper than
when doing a full rotation.
/* for diagonal UR */
b = bm & diagonalURsq[sq];
/* some CPUs should be able to do the shifts real quick */
/* is this one instruction with MMX? */
b |= b>>32;
b |= b>>16;
b |= b>>8;
/* now the wanted bits are in the least 8 significant bits of b */
This is better if you usually don't need the rotated bits.
Urban Koistinen
Robert Hyatt
James Long (wzrd...@fia.net) wrote:
: Alessandro Damiani wrote:
: > We devide the bitboard at row(s) in an upper and a lower half and look
: > at them independently:
: > 1.) upper half: extract the upper diagonals at s by and-ing ALLPIECES
: > and the upper diagonals-bitboard you read from a table. We or all 8 rows
: > of the resulting bitboard and get so an 8 bit index i. We access the
: > first table with AttackFromBishop_DiagonalsUp[s,i], and we get the upper
: > part of the attack squares of a bishop at s.
: So just for the upper attack squares you've done one AND operation,
: and eight ORs.
: >
: >
: > 2.) lower half: same work. Accessing
: > AttackFromBitshop_DiagonalsDown[s,j], j is the index of the lower
: > diagonals at s.
: Same here, another AND and eight ORs. We're up to 2 ANDs/16 ORs.
: >
: >
: > 3.) We or both results and get all attack squares. Easy, isn`t it?
: Another OR. This is a lot of work. With rotated bitboards, it's
: much simpler. Here's my routine for finding bishop moves:
: BITBOARD bmoves(int sq)
: {
: return
: diag_uldr_moves[sq][(Rotated45>>r45_shift[sq]) & r45_mask[sq]] |
: diag_urdl_moves[sq][(Rotated315>>r315_shift[sq]) & r315_mask[sq]];
: }
: As you can see, 2 shifts, 2 ANDs, and 1 OR for ALL bishop moves.
: The only additional work is incrementally updating the rotated boards.
The only drawback is the random memory references for the loads we
do. On a PC this hurts since we fetch 32 bytes in a block, and use
8, with little hope of using the other 24 anytime soon.
But it is *far* better than the anding/oring I did way way back when I
first started this, and this is what led to my post a couple of years
ago describing these things. They are quick and easy, and are much
easier to program than the older way, but you generally don't visualize
this approach until *after*.. :)
: >
: >
: > To get the attack squares of a rook we follow the same procedure, but
: > here we don`t use an extra table like needed in 1.) and 2.) to extract
: > lower and upper half: shifting the bitboard is faster.
: >
: > Bye bye
: >
: > Alessandro
: James
: http://home.fia.net/~wzrdking