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.

Full Threads Oldest First

Showing messages 1 through 2 of 2.

  • Rotated bitboards.
    2005-10-19 11:33:52  glenpepicelli [View]

    Thanks for your input. Rotated bitboards were invented by Robert Hyatt, who no longer does chess research but still maintains crafty. He is here: http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html


    I didn't cover rotated bitboards for a few reasons. However, I made a mistake in not even mentioning them.


    One reason was just space. This isn't a site about chess or AI and we just wanted to introduce Java programmers to these methods and show a real world example. To cover the rotated bitboards in detail would have exploded the size of the article.


    Another reason was the audience the article is intended for. The OnJava readers are mostly corporate programmers, probably only a few write AI and very few are writing chess software. So the article is not meant to be a how-to on writing a chess engine. Care was taken to make sure that it was correct in regards to chess, but it is not complete. In other words, if your writing chess software this could be a good introduction but you want to keep reading.


    While I didn't cover the rotated boards or other chess programming issues they are interesting topics so anyone who like this article might want to check them out.

    • Rotated bitboards.
      2010-05-17 18:52:49  M1k01000101 [View]

      Seems like 50% on chess :p. Are there any books that deal with this sort of thing. I've got knuth and hackers delight. Maybe not a big enough topic for a whole book. Thanks for writting the article.