Author: Gerd Isenberg
Date: 13:13:00 09/09/02
Hi all,
specially algorithm freaks,
I'm currently looking for an efficient algorithm to determine whether two bits
in a bitboard are connected by "ones". Actually i use following recursive one,
but isn't there something smarter?
bool isConnected(BitBoard &theBB, int from, int to)
{
BitBoard adjacentBB = KingAttacks(from) & theBB;
theBB &= ~adjacentBB;
while (adjacentBB)
{
int sq = findLSBAndReset(adjacentBB);
if (sq == to) return true;
if ( isConnected(theBB, sq, to) ) return true;
}
return false;
}
One, but not the only source for my interest, is this position posted by allan
johnson:
[D]B7/p1p5/kb1p4/p3p3/P1N2p2/6p1/7p/K7 w - - 0 1
http://www.talkchess.com/forums/1/message.html?250804
Thanks in advance,
Gerd
// MSC example - copy, paste and try
#include <stdio.h>
typedef __int64 BitBoard;
BitBoard sKingAtta[64];
#define LOWBOARD(bb) (*((int*)&(bb)))
#define HIGHBOARD(bb) (*(((int*)&(bb))+1))
__forceinline int findLSBAndReset(BitBoard &bb)
{
register BitBoard lsbb = bb & (-bb);
bb ^= lsbb;
int lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
^((lsb & 0xffff0000)!=0))<<1)
^((lsb & 0xff00ff00)!=0))<<1)
^((lsb & 0xf0f0f0f0)!=0))<<1)
^((lsb & 0xcccccccc)!=0))<<1)
^((lsb & 0xaaaaaaaa)!=0);
}
int n;
bool isConnected(BitBoard &theBB, int from, int to)
{
if (n++ == 0 ) printf(" n fr to\n");
printf("%02d %02d %02d\n", n, from, to);
BitBoard adjacentBB = sKingAtta[from] & theBB;
theBB &= ~adjacentBB;
while (adjacentBB)
{
int sq = findLSBAndReset(adjacentBB);
if (sq == to) return true;
if ( isConnected(theBB, sq, to) ) return true;
}
return false;
}
// to initialize the king attack array
void InitC3Atta (BitBoard AttackArray[64], BitBoard FromC3)
{
for (int file = 0; file < 8; ++file)
{
BitBoard Atta = FromC3;
for (int f = file; f < 2; ++f)
Atta = (Atta>>1) & ~0x8080808080808080;
for (f = 2; f < file; ++f)
Atta = (Atta<<1) & ~0x0101010101010101;
for (int rank = 0; rank < 8; ++rank)
{
int square = file + (rank << 3);
AttackArray[square] = Atta;
for (int r = rank; r < 2; ++r)
AttackArray[square] >>= 8;
for (r = 2; r < rank; ++r)
AttackArray[square] <<= 8;
}
}
}
/*
some testbitboards (a0 is lsb)
0 1 1 1 1 1 1 1 fe
0 0 0 1 1 1 1 1 f8
0 0 0 0 1 1 1 1 f0
0 0 0 0 0 1 1 1 e0
0 0 0 0 0 0 1 1 c0
1 1 1 1 0 0 0 1 8f
1 1 1 1 1 0 1 0 5f (1f)
1 1 1 1 1 1 0 1 bf
1 1 1 1 1 1 1 1 ff
1 0 0 0 0 0 0 0 01
1 1 1 1 1 1 1 1 ff
0 0 0 0 0 0 0 1 80
1 1 1 1 1 1 1 1 ff
1 0 0 0 0 0 0 0 01
1 0 0 0 0 0 0 1 81
1 1 1 1 1 1 0 1 ff
*/
BitBoard test1 = 0xfef8f0e0c08f5fbf;
//BitBoard test1 = 0xfef8f0e0c08f1fbf; // no connection
BitBoard test2 = 0xff01ff80ff0181ff;
int main()
{
InitC3Atta (sKingAtta, 0x0e0a0e00); // king attacks from c3
BitBoard traverse = test1;
n = 0;
if (isConnected (traverse, 0, 57) )
printf("a1 b8 is connected\n\n");
else
printf("a1 b8 is not connected\n\n");
traverse = test1;
n = 0;
if (isConnected (traverse, 57, 0) )
printf("b8 a1 is connected\n\n");
else
printf("b8 a1 is not connected\n\n");
traverse = test2;
n = 0;
if (isConnected (traverse, 15, 63) )
printf("h2 h8 is connected\n\n");
else
printf("h2 h8 is not connected\n\n");
traverse = test2;
n = 0;
if (isConnected (traverse, 63, 15) )
printf("h8 h2 is connected\n\n");
else
printf("h8 h2 is not connected\n\n");
getchar();
return 0;
}
This page took 0.06 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.