Author: Alvaro Jose Povoa Cardoso
Date: 12:01:05 02/01/02
Go up one level in this thread
On February 01, 2002 at 14:34:28, Sune Fischer wrote:
>On February 01, 2002 at 11:42:05, Alvaro Jose Povoa Cardoso wrote:
>
>Hi :)
>
>>In my checkers (portuguese/spanish version with long jumps) program I use the
>>four bitboard ray technique for the four directions for each of the 32 square
>>for the king jumps (with 32bit bitboards).
>
>Could tell a bit more about this ray technique?
>Preferably every single detail :)
I think it is very basic and even naive.
Suppose you have a rook at E3.
You need to process 4 bitboards:
bbD1 as bits on at E4,E5,E6,E7,E8
bbD2 as bits on at F2,G2,H2
bbD3 as bits on at E2,E1
bbD4 as bits on at D2,C2,B2,A2
Now suppose you have a bitboard called bbAllPieces
For non captures of the 1st bitboard bbD1 you do
while (bbD1) {
to = FirstBit(bbD1) /using BSF
If TestBit(to,bbAllPieces) break;
ClearBit(to,bbD1)
...assemble move using 'to' as the destination square
}
Now you have to do this for the other 3 bitboards.
You have to use LastBit() instead of FirstBit() for bbD2 and bbD3 if you use bit
0 for H1 orientation.
Alvaro Cardoso
>>And then I use the BSF/BSR assembler instructions for finding the moves.
>>Since the PC processor speed is evolving much faster than the memory/FSB speed I
>>would like ask if there is a significant performance diference between this
>>technique and the rotated bitboards with 'large' tables for chess.
>>I did not started yet my chess engine, but I want to start with bitboards so I
>>would like your opinions if this technique is fast enough for the sliding
>>pieces.
>>It seams to me that there is less data needed for these operations and
>>consequentely all this will be on L1 cache most of the time.
>>I also understand this technique better than rotated bitboards.
>
>I tried a few days ago a different technique with reversed bitboards.
>It used very small tables and it could do about 17 million bishop attack boards
>per second. I counted the number of 64 bit operations needed in the rutine, and
>found that one 64-bit operation took an average of 3.3 clock cycles (I ignored
>all '=' which may is also count as 64-bit operations?). I think 3.3 clock cycles
>is pretty good, I think it must be running entirely in L1 cache like yours.
>I have not tested rotated, so I can't compare.
Could you please explain in details your reversed bitboard technique?
>
>Unfortunately reversed boards has one major drawback, they split every attack
>board into two boards, which spells trouble later on.
>I devised a scheme to quickly reverse the board back, but I need to do two
>bitscans and two more 64-bit operations. The slowdown will probably be too much
>to be worth while.
>
>
>>Best regards,
>>Alvaro Cardoso
>
>Cheers,
>Sune.
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.