Author: Vincent Diepeveen
Date: 15:39:51 09/09/02
Go up one level in this thread
On September 09, 2002 at 16:13:00, Gerd Isenberg wrote:
Hello,
Just to be clear is the next path a legal one:
isconnected(d4,d8) ==>
d4 e3 d1 c1 b2 a3 a4 a5 b6 c6 d6 e6 f7 e8 d8
In short you want something like the internet is doing if i understand
well?
>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.01 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.