Author: Vincent Diepeveen
Date: 05:01:30 03/26/02
Go up one level in this thread
On March 25, 2002 at 17:52:43, Alessandro Damiani wrote:
We can't wait to see some code regarding the current
implementation of course...
...Show us how you generate bishop moves please
>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.