Author: Sune Fischer
Date: 12:31:45 02/01/02
Go up one level in this thread
On February 01, 2002 at 15:01:05, Alvaro Jose Povoa Cardoso wrote:
>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
Ok, thanks I get the idea. The problem here will be FirstBit which is quite
expensive compared to regular 64-bit "instructions", and the 'if' is also not
exactly speedy.
One other idea I've been testing; simply masking out all the pieces one by one
with a [64][64]-table containing all the rays.
It is really not that slow if there are not too many pieces on the board, it's
what i've been using up till now, but I'm on the lookout for something even
faster ;D
Of cause one thing that is an absolute must, is to check that you _need_ to
update the attack board in the first place. Most moves made will only invalidate
a few of the attack boards, so there is generally no reason to mindlessly update
them all every time.
I don't think any attack algorithm so fast that this test will actually slow
things down. For the non-sliding pieces don't do the check, but for the sliding
pieces I believe it is a sound investment.
>>>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?
Sure, I started a thread about a few days ago:
http://www.icdchess.com/forums/1/message.shtml?210339
The function I posted doesn't really work (a few bugs) but you get the idea I
think :)
I can can post the correct version(s) if you're interested, perhaps you can
improve upon it :)
It is competetive for move generation I think, but the attack boards are also
used for other stuff, for instance in the eval(), so having them split in two is
a real pain.
>>
>>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.