Author: Robert Hyatt
Date: 06:23:27 09/16/01
Go up one level in this thread
On September 16, 2001 at 05:14:05, Tony Werten wrote:
>On September 15, 2001 at 20:32:38, Robert Hyatt wrote:
>
>>On September 15, 2001 at 11:14:36, Sune Fischer wrote:
>>
>>>Hi
>>>
>>>When I discovered that Crafty had some neat assembler rutines, I decided to test
>>>if they where faster than my humble rutines.
>>>I have up until now used a "raytracing" or boardtracing rutine to find the legal
>>>moves for the sliding pieces. And for the knights, pawns and king I simply check
>>>if the board has an allied piece on that square.
>>>It's a simple way of generating the legal moves.
>>>I still generate the attack bitboards to get the legal king moves though.
>>>
>>>I then tried to find all the moves directly from the bitboards by using one of
>>>Crafty's assember functions.
>>>This part of my program is only a minor part, but none the less it runs a full 8
>>>percent slower than my previous raytracing algorithm!!
>>
>>
>>Two points:
>>
>>1. bitboards are a bit slower on 32 bit hardware. not a lot, but a bit.
>
>What do you think is the reason for this ? Is it because 64bit instruction need
>more time or is it the thrashing of the cache ?
No. Every 64 bit operation requires _two_ 32 bit instructions at least. 64
bit shifts require even more. on a 64 bit machine, this is not an issue.
>
>If I had a way getting the bitboard with more computational effort ( say 4-5
>times ) but in total taking less than 2 Kb, would it be faster then ?
>
>Tony
I don't believe so. This is the principle behind "compact attacks" in Crafty.
Has less data, which makes the cache footprint smaller, but it requires more
instructions to execute.
>
>>On 64 bit hardware, this penalty disappears totally.
>>
>>2. Remember that the majority of positions I generate moves for are
>>capture-only positions (q-search). Compare your raytracer to bitmaps for
>>generating _just_ captures. You will find an advantage to bitboards there.
>>
>>
>>
>>
>>>
>>>This is what I have now:
>>>
>>>void FindMovesQueen(..loads of pointers...)
>>>{
>>> int to_square;
>>> BITBOARD bb=(~allied.occupied) & allied.attack[board.id[from_square]];
>>>
>>> while (bb)
>>> {
>>> to_square=63-FirstOne(bb); // get a bit
>>> bb ^= mask[to_square]; // remove the bit
>>>
>>> movelist[++counter].from=from_square;
>>> movelist[counter].to=to_square;
>>> movelist[counter].piece=QUEEN;
>>> movelist[counter].capturedpiece=enemy.piece[board.id[to_square]];
>>> }
>>> return;
>>>}
>>>
>>>(movelist, counter, from_square etc. are passed in the argument)
>>>
>>>I know why it is slow too.
>>>First I have to form the bb, that's 2 bitboard operations.
>>>Then I need to run an algorithm, FirstOne from crafty, to find the first bit.
>>>Then I need to mask out that found bit.
>>>Both of these run several time pending on the while loop.
>>>Next is 4 lines I always have, no matter how I do it, so we can safely ignore
>>>those.
>>>The while loop is a conditional much like the if's I use when raytracing, so
>>>probably the if's and while almost cancel out.
>>>
>>>All in all I have added a lot of operations to my program, I am not surprized it
>>>is a lot slower. Given that the entire program suffer a slowdown by about 8.1
>>>percent, I estimate that this technique is more than twice as slow as the
>>>raytracing.
>>>The upside of things is that I reduce my code by about 1000 lines or so, but is
>>>this worth 8 percent in speed?
>>>I know the use of 64 bit processors will give a nice boost to this method and I
>>>probably can't expect anything like that for my tracing function, but frankly
>>>I'm not sure it would be enough to catch up.
>>>
>>>Am I mistaken, are the big boys doing something else?
>>>Is there an even faster way?
>>>I need to know :D :D
>>>
>>>Thanks,
>>>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.