# Computer Chess Club Archives

## Messages

### Subject: algorithm question

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;
{
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

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;
{
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.1 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.