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. Rotated bitboards.
2005-10-19 11:33:52  glenpepicelli [View]

1 to 1 of 1