ONJava.com -- The Independent Source for Enterprise Java
oreilly.comSafari Books Online.Conferences.

advertisement

AddThis Social Bookmark Button
Article:
  Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond
Subject:   Rotated bitboards.
Date:   2005-05-15 06:38:38
From:   moott0ripaa
On the second page it is said that for rooks,
bishops or queens are no bit-parallel operations.
Internet is full of programming tips related to
chess and there are some very interesting things
you can do with something called rotating
bitboards.


I don't know if the writer has missed the concept
of rotated bitboards or has he left them out for
some other reason, but anyways:


firsly we need a 2-dim array, named for ex.
rank_attacks[64][256]. The array contains all
possible attack that a rook could do on a rank.
the [64] part is for each square and the [256]
part is the occupansy state of the rank. It's
easiest to make an algorithm that generates the
attacks. For example if a white rook was in e4 and
there is a black pawn on b1 and h1 -> occupansy
state for the rank would look in bit notation:
01001001. Our possible attacks would be:
rank_attacks[e4][73] (73 is the bitnotation in
decimal)=01110111 (in bit notation), a 1 in each
square a rook can attack. Now we just & the
rank_attacks with WHITEPIECES. This was easily
done and took very little time, but unfortunately
we can't do it to a file sraight away because in a
file the bits are separated, but in a rank they
are adjacent. For the file part we need a bitboard
that is rotated 90 degrees, it would look
something like this:


a1,a2,a3,a4,a5,a6,a7,a8,
b1,b2,b3,b4,b5,b6,b7,b8,
c1,c2,c3,c4,c5,c6,c7,c8,
d1,d2,d3,d4,d5,d6,d7,d8,
e1,e2,e3,e4,e5,e6,e7,e8,
f1,f2,f3,f4,f5,f6,f7,f8,
g1,g2,g3,g4,g5,g6,g7,g8,
h1,h2,h3,h4,h5,h6,h7,h8


And the board BEFORE rotation was like this:


h1,g1,f1,e1,d1,c1,b1,a1,
h2,g2,f2,e2,d2,c2,b2,a2,
h3,g3,f3,e3,d3,c3,b3,a3,
h4,g4,f4,e4,d4,c4,b4,a4,
h5,g5,f5,e5,d5,c5,b5,a5,
h6,g6,f6,e6,d6,c6,b6,a6,
h7,g7,f7,e7,d7,c7,b7,a7,
h8,g8,f8,e8,d8,c8,b6,a8


Now we have a rotated bitboard, we just need to
make a new 2-dim array, named
file_attacks[64][256] and do the same thing to it
as we did for the rank_attacks array. After we
have the array we can use it similarly to the
rotated bitboard where the filessquares are
adjacent. Bum! we got our rookattacks.


Bishop's rotated bitboard is a little bit more
abstract, since we need to rotate it 45 degrees to
get the diagonals to be adjacent bits on the
bitboard. But after we have rotated it the
attacksquare calculation goes the same way as for
files and ranks with a minor exception: we need to
know the length of the diagonal since diagonals
can be 1 to 8 squares long. I'm not fullu aware of
the steps related to 45 degree rotated bitboards
but I hope you got the idea and understood it. A
rotated bitboard 45 degrees to left would be like:


a1,
b1,a2,
c1,b2,a3,
d1,c2,b3,a4,
e1,d2,c3,b4,a5,
f1,e2,d3,c4,b5,a6,
g1,f2,e3,d4,c5,b6,a7,
h1,g2,f3,e4,d5,c6,b7,a8,
h2,g3,f4,e5,d6,c7,b8,
h3,g4,f5,e6,d7,c8,
h4,g5,f6,e7,d8,
h5,g6,f7,e8,
h6,g7,f8,
h7,g8,
h8


as you can see (hopefully) all diagonal bits are
adjacent.


This might not be entirely correct, because first
of all my native language is finnish and my
english might be poor on some cases and secondly I
have studied bitboards for few days and am not
fully aware of all that is related to them and
finally I'm a newbie in programming, I introduced
myself to c++ in last january and had done only
visualbasic before.


For more information you can try:


http://www.cis.uab.edu/info/faculty/hyatt/bitmaps.html
http://www.chessbrain.net/beowulf/


those are the locations i've gotten most of my
knowledge about bitboards.


1 to 1 of 1
1 to 1 of 1