Author: Tony Werten
Date: 13:51:24 09/09/02
Go up one level in this thread
On September 09, 2002 at 16:13:00, Gerd Isenberg wrote:
>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?
I'm not sure this is what you mean, but maybe this will help you on your way.
In XiniX I have a byte with bits set if there are pawns on that line. To check
for isolated pawns I do:
iso:=pawns and not((pawns shl 1) or (pawns shr 1));
If you change the shifts to 8, then take out these isolated pawns from your
bitmap and then do the same with the rotated bitmap it should give you what you
want. ( I think)
Tony
>
>
>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.