Computer Chess Club Archives


Search

Terms

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;
 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.09 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.