Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: All shortest paths & other flood-fill based algorithms

Author: Sune Fischer

Date: 05:11:46 09/14/02

Go up one level in this thread


On September 14, 2002 at 07:27:17, Steffan Westcott wrote:

>On September 14, 2002 at 04:33:40, Sune Fischer wrote:
>
>>On September 14, 2002 at 04:10:46, Sune Fischer wrote:
>>
>>>I just thought of another application on the passed pawns.
>>>This way one doesn't need a 8x64 byte table or calls to firstone().
>>>I can't say if it's faster than the lookup though, I'll probably
>>>use it anyway.
>>>
>>>//===================================================================
>>>// find the passed and semi-passed pawns:
>>>
>>>BITBOARD WhitePassedPawns(BITBOARD w_pawns,BITBOARD b_pawns) {
>>>   BITBOARD passed=0,tempA,tempB;
>>>   int i=0;
>>>
>>>   tempA=(w_pawns<<8)&~b_pawns;
>>>   while (tempA) {
>>>      tempB=tempA&rank8;
>>>      i+=8;
>>>      if (tempB)            // a pawn has reached the 8th rank
>>>	passed|=tempB>>i;   // shift it back to where it originally came from
>>>      tempA=(tempA<<8)&~b_pawns;
>>>   }
>>>   return passed;
>>>}
>>
>>Actually this may be faster, on 64 bit chips anyway:
>>
>>  while (tempA) {
>>      passed|=(tempA&rank8)>>(i+=8);
>>      tempA=(tempA<<8)&~b_pawns;
>>   }
>
>
>Sune,
>
>Somewhat simpler and faster still (!) is this approach :
>
>
>---- CUT HERE ----
>
>BitBoard FillDown(BitBoard b)
>{
>    // Uses Kogge-Stone parallel prefix algorithm
>           b |= b >>  8;
>           b |= b >> 16;
>    return b |= b >> 32;
>}
>
>
>BitBoard WhiteSemiPassedPawns(BitBoard w_pawns, BitBoard b_pawns)
>{
>    return w_pawns & ~FillDown(b_pawns);
>}
>
>
>BitBoard WhitePassedPawns(BitBoard w_pawns, BitBoard b_pawns)
>{
>    return w_pawns & ~FillDown(                 b_pawns
>                               | ShiftDownLeft (b_pawns)
>                               | ShiftDownRight(b_pawns));
>}
>
>---- CUT HERE ----
>
>
>FillDown is an example of a simple flood fill, which 'smears' set bits in just
>one direction.

Yes, that's why I considered it to be a flood filler :)
Of course by semi-passed you also include the fully passed,
guess one have to mask them out to get the 'true semi-passed'.

>Instead of using a normal fill loop, I've borrowed an idea
>normally found in fast adder hardware. This sort of fill is great for things
>like attack or move generator bitboards.

Yes, the jumps double each time, pretty clever :)
Perhaps my proposal (running the whites instead of the blacks) could also be
optimized to take advantage of that, but your code seem pretty close to perfect
as it is :)

-S.

>Cheers,
>Steffan



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.