Author: Sune Fischer
Date: 14:46:02 09/13/02
Go up one level in this thread
On September 13, 2002 at 16:56:38, Steffan Westcott wrote:
>On September 13, 2002 at 04:07:55, Sune Fischer wrote:
>
>>#define SHIFTDOWN(b) ((b)>>8)
>>#define SHIFTUP(b) ((b)<<8)
>>#define SHIFTRIGHT(b) ((((b)<<1)&0xFEFEFEFEFEFEFEFE))
>>#define SHIFTLEFT(b) ((((b)>>1)&0x7F7F7F7F7F7F7F7F))
>>#define SHIFTUPLEFT(b) ((((b)<<7)&0x7F7F7F7F7F7F7F7F))
>>#define SHIFTUPRIGHT(b) ((((b)<<9)&0xFEFEFEFEFEFEFEFE))
>>#define SHIFTDOWNLEFT(b) ((((b)>>9)&0x7F7F7F7F7F7F7F7F))
>>#define SHIFTDOWNRIGHT(b) ((((b)>>7)&0xFEFEFEFEFEFEFEFE))
>>
>>//===================================================================
>>
>>int IsLineConnected(BITBOARD path,BITBOARD sq1,BITBOARD sq2) {
>> int n=0;
>>
>> if (!(sq1&=path) || !(sq2&=path))
>> return 0;
>> register BITBOARD old_sq1;
>> while(1) {
>> if (sq1&sq2)
>> return n;
>> n++;
>> old_sq1=sq1;
>> sq1|=SHIFTRIGHT(sq1)|SHIFTLEFT(sq1);
>> sq1&=path;
>> sq1|=SHIFTDOWN(sq1)|SHIFTUP(sq1);
>> sq1&=path;
>> if (sq1==old_sq1)
>> return 0;
>> }
>>}
>>
>>//===================================================================
>>
>>int IsDiagonalConnected(BITBOARD path,BITBOARD sq1,BITBOARD sq2) {
>> int n=0;
>>
>> if (!(sq1&=path) || !(sq2&=path))
>> return 0;
>> register BITBOARD old_sq1;
>> while(1) {
>> if (sq1&sq2)
>> return n;
>> n++;
>> old_sq1=sq1;
>> sq1|=SHIFTUPRIGHT(sq1)|SHIFTUPLEFT(sq1);
>> sq1&=path;
>> sq1|=SHIFTDOWNRIGHT(sq1)|SHIFTDOWNLEFT(sq1);
>> sq1&=path;
>> if (sq1==old_sq1)
>> return 0;
>> }
>>}
>
>
>Sune,
>
>Please allow me to point out a small improvement in your implementation of
>IsDiagonalConnected :
>
>int IsDiagonalConnected(BITBOARD path,BITBOARD sq1,BITBOARD sq2) {
> int n=0;
>
> if (!(sq1&=path) || !(sq2&=path))
> return 0;
> register BITBOARD old_sq1;
> while(1) {
> if (sq1&sq2)
> return n;
> n++;
> old_sq1=sq1;
> sq1|=SHIFTUPRIGHT(sq1)|SHIFTDOWNLEFT(sq1); // Changed here
> sq1&=path;
> sq1|=SHIFTDOWNRIGHT(sq1)|SHIFTUPLEFT(sq1); // Changed here
> sq1&=path;
> if (sq1==old_sq1)
> return 0;
> }
>}
>
>In your version, each set bit in sq1 can fill at most 6 neighbours per
>iteration. With my very slight rearrangement of your code, each set bit in sq1
>can now fill at most 9 neighbours per iteration, with no loss of speed.
You are right, but there are several possibilities yielding different
propagation velocities:
slowest:
sq1|=SHIFTUPRIGHT(sq1)
|SHIFTDOWNLEFT(sq1)
|SHIFTDOWNRIGHT(sq1)
|SHIFTUPLEFT(sq1);
fastest:
sq1|=SHIFTUPRIGHT(sq1);
sq1&=path;
sq1|=SHIFTUPLEFT(sq1);
sq1&=path;
sq1|=SHIFTDOWNLEFT(sq1);
sq1&=path;
sq1|=SHIFTDOWNRIGHT(sq1);
sq1&=path;
Perhaps yours is the best, I'll have to think about it :)
-S.
>In the rather poor diagrams that follow, * marks the single seed square e5 where
>the fill starts and the digits indicate the minimum path length used to reach
>them from *. 'mask' is assumed to be ~0.
>
>Fill progress with your original version looks like this (a sequence of
>concentric hexagons) :
>
>.3.3.3.3.4
>3.2.2.2.3.
>.2.1.1.2.3
>2.1.*.1.2.
>.2.1.1.2.3
>3.2.2.2.3.
>.3.3.3.3.4
>4.4.4.4.4.
>
>... but with my tweak it looks like this instead (a sequence of concentric
>diamonds) :
>
>.3.2.2.3.4
>3.2.1.2.3.
>.2.1.1.2.3
>2.1.*.1.2.
>.2.1.1.2.3
>3.2.1.2.3.
>.3.2.2.3.4
>4.3.2.3.4.
>
>Although not true in this example (aargh!), filling more squares per iteration
>helps decrease the number of iterations required, more so when using non-trivial
>'mask's.
>
>Please also note that the 'n' returned in your routines is a measure of
>proximity along the diagonals, and so ought to be symmetric. For your routine in
>the above example, e7 has proximity 2, but c5 has proximity 1.
>
>There is sadly a bug in both of your routines. You use a return value of 0 to
>indicate if no path exists. However, if (sq1 & sq2) != 0, you return a path
>length of 0 also! When reporting the path length, my routines include the end
>points and so have minimum value of 1 for any valid path.
>
>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.