Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Bitboard question (very long)

Author: Peter Fendrich

Date: 15:39:53 12/02/98

Go up one level in this thread


On December 02, 1998 at 16:41:35, Inmann Werner wrote:

>Analyzing my program, I found, that it spends most time in the routine detecting
>if the king is in check.
>I think, using Bitboard Representation will speed up a lot, and using Bitboards
>for this at the start will increase my learning.
>After some thinking and reading, I have some nice working routines but one big
>problem.
>
>I have a Bitboard with one Bit set to one, all others to zero. Now I want to
>know the number of the bit, counted from the "right side".
>Example: 64 should be 7 (or 6?) cause its the 7th (or 6th) bit.
>I programmed some routines which are more than bad. Is there a simple, but fast
>routine available? Please help!


Take my test with two bitboard routines as an input!
The routines are GetSqList() that finds all the bits==1 and put each
corresponding square number in a list and CountBits() that counts all bits==1 in
the bitboard. The first one can easly be remade to just pop one bit instead of
finding them all.
All tests are done on a PII 300 Mhz Win95 PC.

GetSqList()
==========
I tested with two types of tables:
  - "Big" table (65536 entries) to lookup the last bit set of 16.
  - "small" table (256 entries) to lookup the last bit set of 8.
For these tables I used two 32-bit register as one solution and a
64-bit register as another soulution.
All the four variants are not listed here but that's not necessary I think...
I also tested a modulus variant. (The code is the best explanation.)
They are all listed in performance order.
Remark: The bitboard is a variable (TheBoard) in my BitBoard class.
        I don't use this approah any more but the algorithm's are
        in principle, the same
--------------------------------------------------------------------
1) "Big" tabell with 2 32-bit register
   This turned out to be the best one for my program.
.................................................................
void getSqList(UINT *s)const {
// Creates a list of squares in *s, found in the bitboard
    register int i=64; register UINT x;
    register UINT BB1=TheBoard.half[a1h4]; //first half of the bitboard
    register UINT BB2=TheBoard.half[a5h8]; //second half

    while (BB2) {
	if ( BB2 & (UINT)0xffff ) {
	    x = LastBit[(unsigned __int16)BB2];
	    i -= x;
	    *s++ = i;
	    BB2 >>= x;
	}else if ( BB2 & (UINT) 0xffff0000 ) {
 	    x = LastBit[(unsigned __int16)(BB2 >>= 16)];
	    i -= (x+16);
	    *s++ = i;
	    BB2 >>= x;
	}else{
	    // Impossible!!!
	    printf("Error1 in getSqList()");
	    exit(31);
	}
    }
    i=32;
    while (BB1) {
	if ( BB1 & (UINT)0xffff ) {
 	    x = LastBit[(unsigned __int16)BB1];
	    i -= x;
	    *s++ = i;
	    BB1 >>= x;
	}else if ( BB1 & (UINT) 0xffff0000 ) {
	    x = LastBit[(unsigned __int16)(BB1 >>= 16)];
	    i -= (x+16);
	    *s++ = i;
	    BB1 >>= x;
	}else{
	    // What!!!
	    printf("Error2 in getSqList()");
	    exit(32);
	}
    }

    *s = 99;
}
.................................................................
2)"Small" Table (256 entries) and a 64 bit register
..............................................
void getSqList(UINT *s)const {
// Creates a list of squares in *s, found in the bitboard

    register int i=64;
    register UINT x;
    register UINT64 BB=TheBoard.all;
    while (BB) {
	if ( BB & (UINT64)0xff ) {
    	    x = LastBit[(BYTE)BB];
	    i -= x;
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff00 ) {
	    x = LastBit[(BYTE)(BB >>= 8)];
	    i -= (x+8);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff0000 ) {
	    x = LastBit[(BYTE)(BB >>= 16)];
	    i -= (x+16);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff000000 ) {
   	    x = LastBit[(BYTE)(BB >>= 24)];
	    i -= (x+24);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff00000000 ) {
	    x = LastBit[(BYTE)(BB >>= 32)];
	    i -= (x+32);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff0000000000 ) {
	    x = LastBit[(BYTE)(BB >>= 40)];
	    i -= (x+40);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff000000000000 ) {
	    x = LastBit[(BYTE)(BB >>= 48)];
	    i -= (x+48);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (UINT64) 0xff00000000000000 ) {
	    x = LastBit[(BYTE)(BB >>= 56)];
	    i -= (x+56);
	    *s++ = i;
	    BB >>= x;
	}else{
	    // Error!!!
	}
    }
    *s = 99;
}

3) "Big" Table (65536 entries) and one 64 bits register
.................................................................
void getSqList(UINT *s)const{
// Creates a list of squares in *s, found in the bitboard
    register int i=64;
    register UINT x;
    register uint64 BB=TheBoard.all;
    while (BB) {
        if ( BB & (uint64)0xffff ) {
  	    x = LastBit[(unsigned __int16)BB];
	    i -= x;
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (uint64) 0xffff0000 ) {
	    x = LastBit[(unsigned __int16)(BB >>= 16)];
	    i -= (x+16);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (uint64) 0xffff00000000 ) {
	    x = LastBit[(unsigned __int16)(BB >>= 32)];
	    i -= (x+32);
	    *s++ = i;
	    BB >>= x;
	}else if ( BB & (uint64) 0xffff000000000000 ) {
	    x = LastBit[(unsigned __int16)(BB >>= 48)];
	    i -= (x+48);
	    *s++ = i;
	    BB >>= x;
	}else{
	    // ERROR!!!
	    printf("Error in getSqList");
	    exit(33);
	}
    }
    *s = 99;
}

4) Modulo version
..................................................
ModuloTab=
{-1, 63, 25, 62, 49, 24, 41, 61, 52, 48,  5, 23, 45, 40, 10,
 60, -1, 51, 54, 47,  2,  4, 36, 22, 34, 44, 13, 39, 20,  9,
 17, 59, 32, -1, 26, 50, 42, 53,  6, 46, 11,  1, 55,  3, 37,
 35, 14, 21, 18, 33, 27, 43,  7, 12, 56, 38, 15, 19, 28,  8,
 57, 16, 29, 58, 30, 31, -1, -1};
void getSqList(UINT *s)const
{
    register uint64 BB=TheBoard.all;
    while (BB) {
	*s++ = ModuloTab[(BB^(BB-1)) % 67];
	BB &= BB-1;   // Clear the bit
    }
    *s = 99;
}


CountBits()
===========

1) This is the best solution for my program. It is also used in Crafty.
...............................................................
	register unsigned __int64 a = TheBoard.all;
	while( a ) {
		c++;
	    a &= a - 1;
	}
	return c;

2) This is a hybrid between the one above and something
   proposed by Bruce some year ago. For my program this is
   not as good as the first one. The idea here is that with a few ( < 6) bits
   set in the bitboard you don't have to loop.
.............................................
    register unsigned __int64 a = TheBoard.all;
    if( !a )
	return( 0 );
    else if( !( a &= a - 1 ) )
	return( 1 );
    else if( !( a &= a - 1 ) )
        return( 2 );
    else if( !( a &= a - 1 ) )
        return( 3 );
    else if( !( a &= a - 1 ) )
        return( 4 );
    else if( !( a &= a - 1 ) )
        return( 5 );
    else
        for( register UINT count = 6;; count++ ) {
	    if( !( a &= a - 1 ) ) return( count );
        }
.................................................

3)This is a quite interesting one. A hackers soulution without loop.
  Also found in DarkThoght's homepage.
  Surprisingly enough, it wasn't so good for my program.
..............................................
#define ONES ((uint64) 0x5555555555555555)
#define TWOS ((uint64) 0x3333333333333333)
#define FOURS ((unsigned __int32) 0x0f0f0f0f)
	register unsigned __int32 n;
    const uint64 a = TheBoard.all - ((TheBoard.all >> 1) & ONES);
    const uint64 c = (a & TWOS) + ((a >> 2) & TWOS);
    n = ((unsigned __int32) c) + ((unsigned __int32) (c >> 32));
    n = (n & FOURS) + ((n >> 4) & FOURS);
    n = (n & 0xFFFF) + (n >> 16);
    n = (n & 0xFF) + (n >> 8);
    return n;
}
..............................................

4) The worst one. Table loookup (you have to imagine the table yourself)
........................................
    c =  Bits::getCount(TheBoard.row[0]);
    c += Bits::getCount(TheBoard.row[1]);
    c += Bits::getCount(TheBoard.row[2]);
    c += Bits::getCount(TheBoard.row[3]);
    c += Bits::getCount(TheBoard.row[4]);
    c += Bits::getCount(TheBoard.row[5]);
    c += Bits::getCount(TheBoard.row[6]);
    c += Bits::getCount(TheBoard.row[7]);
    return c;
...........................................

5) Here is a good one that take advantage of the Pentium architecture.
   The idea is to let the registers work in parallell by accessing them
   independent from each other. The same table lookup as above.
   in fact this algorithm became the second best of them all.
.............................................
  UINT register c; UINT register c1;
  BYTE register byte0 = TheBoard.row[0];
  BYTE register byte1 = TheBoard.row[1];

  c =  Bits::getCount(TheBoard.row[byte0]);
  c1 = Bits::getCount(TheBoard.row[byte1]);

  byte0 = TheBoard.row[2];
  byte1 = TheBoard.row[3];
  c +=  Bits::getCount(TheBoard.row[byte0]);
  c1 += Bits::getCount(TheBoard.row[byte1]);

  byte0 = TheBoard.row[4];
  byte1 = TheBoard.row[5];
  c +=  Bits::getCount(TheBoard.row[byte0]);
  c1 += Bits::getCount(TheBoard.row[byte1]);

  byte0 = TheBoard.row[6];
  byte1 = TheBoard.row[7];
  c +=  Bits::getCount(TheBoard.row[byte0]);
  c1 += Bits::getCount(TheBoard.row[byte1]);
  return (c+c1);

>
>Second question.
>I will work with lookup tables. Cause I do not want to use rotated bitboards (at
>the beginning) I came to a "trick" for sliding figures.
>
>After some ANDs and ORs I know the Position of the king and the "attacking" rook
>for example. Now I have to find, if another figure blocks the attacking. With
>some other ANDs and XORs I have all possible "blockers" in a bitboard. Now I
>"AND" it with an attacktable which is defined as following.
>BITBOARD ATTACKTABLE[64][64]. In it are all BITBOARDS where all possible
>blocking Positions are in between the king and the attacking rook.
>Thats it.
>
>Is this a really bad idea? Any suggestions.

That is what I do, but with rotated bitboards...
With the rotated thing I only have to construct the ATTACKTABLE, you have, for
rows. Much easier, i think, when all the rotating is working!

//Peter



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.