Author: Alessandro Damiani
Date: 12:41:13 03/26/02
Go up one level in this thread
On March 26, 2002 at 08:01:30, Vincent Diepeveen wrote:
>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
>
It is not new. I posted it here some time back. New are the optimizations and
some more description. I have added a link to my homepage. It is in the first
section: "Chess programming: Bitboards in Fortress". The zip-file is about
3kByte large.
http://freeweb.econophone.ch/fortress/
Alessandro
>>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.