Author: Alessandro Damiani
Date: 14:52:43 03/25/02
Go up one level in this thread
Hi Alvaro!
I just replied your email. Since there may be someone interested in my answer I
post here my email.
Alessandro
--- email ----
Hi Alvaro!
I had to smile by looking at what I wrote so many years back. :) The method I
used then is still interesting because of its simplicity. The drawback is the
high cost of the ORs.
bishop: 8 ORs for upper half of the board + 8 ORs for lower half of the board =
16 ORs (+ 1 OR to combine both halves)
17 ORs to get one attack board for the bishop is high.
Ok, back to your question. To get the index of the vertical attacks of a rook we
use the following algorithm (pseudo C):
int s: square of the rook
int file(s): file of square s (= s & 8)
{
b= AllPieces;
b= shiftRight(b, 7-file(s)); // shift the interesting file to the right border
(*)
b= b & FILE_H; // remove all bits except the rightmost file
int index= b & 1; // get the FIRST bit of the vertical attack index
b= shiftRight(b, 8); // go to the next row
index= index | (b & 1); // get the SECOND bit of the vertical attack index
b= shiftRight(b, 8); // go to the next row
index= index | (b & 1); // get the third bit of the vertical attack index
...
b= shiftRight(b, 8); // go to the next row
index= index | (b & 1); // get the 8TH bit of the vertical attack index
// it applies: index is the vertical attack index
}
(*) A8 = 0 in my implementation. Therefore file(s) = s & 8 is seen from left
(file(A8) = 0, file(H8) = 7) and we have to shift 7-file(s) to the right to
place the file to the right border.
For the rook we have 8 ORs for the vertical attack index, which is a high cost.
Don't forget that for a queen we have the rook's cost + the bishop's cost. :-(
I don't use these algorithms anymore because of the high cost of the ORs.
Although memory access is low I guess they are slower than my current
algorithms. My website provider seems to have problems, so I send you the zip
file containing my current algorithms. The file is attached.
Bob Hyatt told me that my algorithms are slightly faster than his rotated
bitboards on a 32bit machine. On a 64bit machine he expects mine to be slower
than his. When he did the test my algorithms were not optimized for chess. The
attached file is a new version containing four substantial optimizations.
I am working on a new release of Fortress. It already contains the four
optimizations. Especially the capture optimization is a big win, since captures
are searched a lot at the horizon.
Please feel free to ask if something I wrote in this email or in the attached
file is unclear.
Ciao ciao,
Alessandro
--- email ---
On March 25, 2002 at 15:44:27, Alvaro Jose Povoa Cardoso wrote:
>Hi,
>you posted an interesting message bak in 1997 at rec.games.chess.computer about
>avoiding rotated bitboards. I understood the bishops case but not the rooks
>case, in particular the vertical attacks of a rook.
>
>Below is the thread I'm referring about.
>This is the part I woul like you to explain:
>
>"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.
>"
>
>Thanks in advance,
>Alvaro Cardoso
>
>
>
>
>
>
>De:Alessandro Damiani (adamiani@g26.ethz.ch)
>Assunto:Re: Rotated bitboards
>Newsgroups:rec.games.chess.computer
>View: Complete Thread (4 articles) | Original Format
>Data:1997/10/31
>
>
>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..
>> ]
>> ]/ garnax@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.
>
>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
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.