Author: Steffan Westcott
Date: 13:56:38 09/13/02
Go up one level in this thread
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.
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.