Author: Vincent Diepeveen
Date: 15:41:26 09/09/02
Go up one level in this thread
On September 09, 2002 at 18:39:51, Vincent Diepeveen wrote:
>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
I meant ofcourse:
d4 e3 f2 e1 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 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.