Debug help - getting bitboard attacks.

[Chan Rasjid]

Hello,

I want to compare the speed of my rotated bitboard attacks with attacks using simple bitwise operation. I did it in the past which showed that it is comparable or a little faster than my rotated bitboards; but this time round I just cannot get the simple functions right! Hope someone can spot the bug.

I have pre-calculated bishop and rook rays for the 4 directions for all 64 squares as bDiag7, bDiag9, bFile, bRank.

Code: Select all

u64 bishop_diag7_attacks(const int sq) {
    u64 d = board[sq]->bDiag7;
    if (d);
    return 0;
    
    u64 b = BB(sq);
    //u low terminal bit
    u64 u = d & (b - 1) & allBits;
    u = u ? BB(lastone(u)) : 1;
    
    //v high terminal bit
    u64 v = d & ~(b - 1) & allBits;
    v = v ? v & - v : 0x8000000000000000UL;
    return  d & ( ((v - 1) | v) ^ (u - 1));  
}

Best Regards,
Rasjid.

[Chan Rasjid]

Hello,

I want to compare the speed of my rotated bitboard attacks with attacks using simple bitwise operation. I did it in the past which showed that it is comparable or a little faster than my rotated bitboards; but this time round I just cannot get the simple functions right! Hope someone can spot the bug.

I have pre-calculated bishop and rook rays for the 4 directions for all 64 squares as bDiag7, bDiag9, bFile, bRank.

Code: Select all

u64 bishop_diag7_attacks(const int sq) {
    u64 d = board[sq]->bDiag7;
    if (d);
    return 0;
    
    u64 b = BB(sq);
    //u low terminal bit
    u64 u = d & (b - 1) & allBits;
    u = u ? BB(lastone(u)) : 1;
    
    //v high terminal bit
    u64 v = d & ~(b - 1) & allBits;
    v = v ? v & - v : 0x8000000000000000UL;
    return  d & ( ((v - 1) | v) ^ (u - 1));  
}

I forgot to mention the 4 rays bDia7,... do no include the bit at the square.

Best Regards,
Rasjid.

[Desperado]

hi Rasjid,

direct computation for bishop offset 7...

Code: Select all

#define HI(SQ) ((ui64_t)(~1) << (SQ))
#define LO(SQ) (((ui64_t)( 1) << (SQ)) - 1)
#define ALLBITS (0xFFFFFFFFFFFFFFFF)

ui64_t bishop_diag7_attacks(const int sq,ui64_t occ) 
{ 
 ui64_t d,b,u,v;

 b = bit(sq); 
 d = DIAGONAL_7(sq)^b;

 //u low terminal bit 
 u = ALLBITS & LO(sq) & occ;
 u = ALLBITS << bsr64(u|1);

 //v high terminal bit 
 v = ALLBITS & HI(sq) & occ;
 v&=-v;

 return ((d) & (2*v+u));
}

now general for each line(rook+bishop)

Code: Select all

static ui64_t attackLine(LINEMASK_T *const lmsk,const ui64_t occ)
{
 ui64_t lo;
 ui64_t hi;

 lo = lmsk->lineLo & occ;
 lo = (ui64_t)(-1) << bsr64(lo|1);

 hi = lmsk->lineHi & occ;
 hi&=-hi;

 return(lmsk->lineEx & (2*hi+lo));
}

hope i dont misunderstood what you are trying to do... so hopefully it helps .

Michael

[Chan Rasjid]

hi Rasjid,

direct computation for bishop offset 7...

Code: Select all

#define HI(SQ) ((ui64_t)(~1) << (SQ))
#define LO(SQ) (((ui64_t)( 1) << (SQ)) - 1)
#define ALLBITS (0xFFFFFFFFFFFFFFFF)

ui64_t bishop_diag7_attacks(const int sq,ui64_t occ) 
{ 
 ui64_t d,b,u,v;

 b = bit(sq); 
 d = DIAGONAL_7(sq)^b;

 //u low terminal bit 
 u = ALLBITS & LO(sq) & occ;
 u = ALLBITS << bsr64(u|1);

 //v high terminal bit 
 v = ALLBITS & HI(sq) & occ;
 v&=-v;

 return ((d) & (2*v+u));
}

now general for each line(rook+bishop)

Code: Select all

static ui64_t attackLine(LINEMASK_T *const lmsk,const ui64_t occ)
{
 ui64_t lo;
 ui64_t hi;

 lo = lmsk->lineLo & occ;
 lo = (ui64_t)(-1) << bsr64(lo|1);

 hi = lmsk->lineHi & occ;
 hi&=-hi;

 return(lmsk->lineEx & (2*hi+lo));
}

hope i dont misunderstood what you are trying to do... so hopefully it helps .

Michael

Thanks Michael,

I don't really understand your codes yet; just tried a rather blind interpretation as follow :

my allBits = _OR_ of all occupied bits on the board and I assume your "occ" means the same.

lastone == bitScanReverse.

But it also dose not work when I plug it into my program.

Code: Select all

#define HI(SQ) ((u64)(~1) << (SQ))
#define LO(SQ) (((u64)( 1) << (SQ)) - 1)
#define ALLBITS (0xFFFFFFFFFFFFFFFF)

u64 attacks_diag7(const int sq)
{
   u64 d,b,u,v;

   b = BB(sq);
   d = board[sq]->bDiag7;

 //u low terminal bit
   u = ALLBITS & LO(sq) & allBits;
   u = ALLBITS << lastone(u|1);

 //v high terminal bit
   v = ALLBITS & HI(sq) & allBits;
   v&=-v;

   return ((d) & (2*v+u));
} 

Rasjid

[Chan Rasjid]

Here are all the codes for the 4 directions.

Just rather strange that the rooks file/rank attacks works when replacing my rook rotated bitboard attacks (played 40+ auto games without any assert failure). The diagonals attacks just don't work.

Code: Select all

u64 attacks_diag7(const int sq) {
   u64 d = board[sq]->bDiag7;
   if (d);
   return 0;

   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}

u64 attacks_diag9(const int sq) {
   u64 d = (board[sq]->bMap ^ board[sq]->bDiag7);
   if (d);
   return 0;

   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}


u64 attacks_file(const int sq) {
   u64 d = board[sq]->rFile;
   assert(d);
   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}

u64 attacks_rank(const int sq) {
   u64 d = (board[sq]->rMap ^ board[sq]->rFile);
   assert(d);

   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}

Rasjid.

[Chan Rasjid]

Sorry for the silly bug.

It is in :
if (d); return 0;
should be:
if (d); else return 0;

The corrected codes basically works, but seem there could be bugs somewhere as after a long game, it could fail whereas my rotated bitboard attacks is sound and never cause any crash. So I cannot compare perfomance yet. Likely the speed difference between rotated bitboard and direct computations don't have significant difference.

Code: Select all

u64 attacks_diag7(const int sq) {
   u64 d = board[sq]->bDiag7;
   
   if (d){
      if (d & allBits); else return d;
   }else return 0;

   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}

u64 attacks_diag9(const int sq) {
   u64 d = (board[sq]->bMap ^ board[sq]->bDiag7);
   
   if (d){
      if (d & allBits); else return d;
   }else return 0;
   

   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}


u64 attacks_file(const int sq) {
   u64 d = board[sq]->rFile;
   assert(d);
   if (d & allBits); else return d;
   
   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}

u64 attacks_rank(const int sq) {
   u64 d = (board[sq]->rMap ^ board[sq]->rFile);
   assert(d);
   if (d & allBits); else return d;

   u64 b = BB(sq);
    //u low terminal bit
   u64 u = d & (b - 1) & allBits;
   u = u ? BB(lastone(u)) : 1;

    //v high terminal bit
   u64 v = d & ~(b - 1)  & allBits;
   v = v ? v & - v : 0x8000000000000000UL;
   return  d & (((v - 1) | v) ^ (u - 1));
}

Best Regards,
Rasjid

[Chan Rasjid]

Hello,

There is no bug in the edited codes I posted earlier; the occasional crash is due to some recent changes I made to my check-evasion codes.

I made some "optimization" to my direct computation codes for B/R attacks. But still my rotated bitboard is faster by about 5-10%.

Code: Select all

u64 attacks_diag7(const int sq) {
   u64 u, d = board[sq]->bDiag7;
   
   if (d){
      if ((u = d & allBits)); else return d;
   }else return 0;
   
   u64 b = BB(sq);
    //v high terminal bit
   u64 v = u & ~(b - 1);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u &= (b - 1);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
}

u64 attacks_diag9(const int sq) {
   u64 u, d = (board[sq]->bMap ^ board[sq]->bDiag7);
   
   if (d){
      if ((u = d & allBits)); else return d;
   }else return 0;
   
   u64 b = BB(sq);
    //v high terminal bit
   u64 v = u & ~(b - 1);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u &= (b - 1);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
   
}


u64 attacks_file(const int sq) {
   u64 u, d = board[sq]->rFile;
   assert(d);
   if ((u = d & allBits)); else return d;
   
   u64 b = BB(sq);
    //v high terminal bit
   u64 v = u & ~(b - 1);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u &= (b - 1);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
   
}

u64 attacks_rank(const int sq) {
   u64 u, d = (board[sq]->rMap ^ board[sq]->rFile);
   assert(d);
   if ((u = d & allBits)); else return d;
   
   u64 b = BB(sq);
    //v high terminal bit
   u64 v = u & ~(b - 1);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u &= (b - 1);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
}

Best Regards,
Rasjid.

[Desperado]

Hi Rasjid,

a full description of the code you can find here...

http://chessprogramming.wikispaces.com/ ... Difference

Code: Select all

#define HI(SQ) ((ui64_t)(~1) << (SQ))
#define LO(SQ) (((ui64_t)( 1) << (SQ)) - 1)
#define ALLBITS (0xFFFFFFFFFFFFFFFF)

//lo  = all bits set below square index
//hi  = all bits set above square index
//occ = occupancy bits(all pieces, or desired(xrayAttacks) piece set)
//bsr = bitscan reverse
//lne = linemask excluding square itself

//hint:
// - use also precomputed masks for LO(),HI() macros (saves some operations)
// - caching computations will speed up further...

Code: Select all

ui64_t lineAttack(const ui64_t lne,const ui64_t occ,const int sq) 
{ 
 ui64_t lo,hi;

 lo  = ALLBITS << bsr64((LO(sq) & occ)|1);
 hi  = (HI(sq) & occ);
 hi &=-hi;

 return ((lne) & (2*hi+lo));
}

Code: Select all

__inline ui64_t bishop(ui64_t occ,int sq)
{return(lineAttack(mask7[sq],occ,sq)|lineAttack(mask9[sq],occ,sq));}

__inline ui64_t rook(ui64_t occ,int sq)
{return(lineAttack(mask8[sq],occ,sq)|lineAttack(mask1[sq],occ,sq));}

__inline ui64_t queen(ui64_t occ,int sq)
{return(bishop(occ,sq)|rook(occ,sq));}

Well, i dont have analyzed your code (yet ), but it doesnt look cheaper
than OD. Simply more operations,branches...
So just again with some more explanations some code snippet

Tomorrow i will have a closer look...

If you adapt this code, i would be interested in the results compared to
rotated bitboards. It can be tuned further...

Michael

[Desperado]

UHHHHHHPS ...

Code: Select all

#define LINE_HI(SQ) (((ui64_t)(~1) << (SQ))  & lne)
#define LINE_LO(SQ) ((((ui64_t)( 1) << (SQ)) - 1)  & lne)

ui64_t lineAttack(const ui64_t lne,const ui64_t occ,const int sq) 
{ 
 ui64_t lo,hi; 

 lo  = ALLBITS << bsr64((LINE_LO(sq) & occ)|1); 
 hi  = (LINE_HI(sq) & occ); 
 hi &=-hi; 

 return ((lne) & (2*hi+lo)); 
} 

hope i can sleep now

Michael

[Chan Rasjid]

Hello,

I don't know yet how lne & (2 * hi +lo) works, but got it working after clearing a bug :-
#define HI(SQ) ((ui64_t)(~1) << (SQ))
should be:
#define HI(SQ) ( ~((ui64_t)1) << (SQ))

I did an analysis for 3 middle game positions and my rotated bitboard is the fastest (by a paltry 1 - 3%) as compared to that of direct bitwise operations. I think my rotated bitboard implementation is ok as I did compare it with that of Crafty's and did all the usual optimization.

//pos 1
//rotated > OD by 1.6%
depth 12 score cp +97 time 132161 msec nodes 54421938 nps 411785 pv 1.g3 Kd8 2.Bd3 Nxf2 3.Kxf2 Qxd5 4.Qg4 Bf8 5.Re4 c5 6.Bf4 d6 7.Qd1
// OD > mybitwise by 1.2%
depth 12 score cp +97 time 134220 msec nodes 54421938 nps 405468 pv 1.g3 Kd8 2.Bd3 Nxf2 3.Kxf2 Qxd5 4.Qg4 Bf8 5.Re4 c5 6.Bf4 d6 7.Qd1
//my bitwise
depth 12 score cp +97 time 135856 msec nodes 54421938 nps 400585 pv 1.g3 Kd8 2.Bd3 Nxf2 3.Kxf2 Qxd5 4.Qg4 Bf8 5.Re4 c5 6.Bf4 d6 7.Qd1

//pos2
//rotated > OD by 1.8%
depth 9 score cp -180 time 117473 msec nodes 44720494 nps 380687 pv 1. ... Rh8 2.Qb2 Ra8 3.Nf3 h6 4.Bd2 Bd7 5.b5 Rg8 6.a4
//OD > mybitwise by 1.6%
depth 9 score cp -180 time 119590 msec nodes 44720494 nps 373948 pv 1. ... Rh8 2.Qb2 Ra8 3.Nf3 h6 4.Bd2 Bd7 5.b5 Rg8 6.a4
//my bitwise
depth 9 score cp -180 time 121469 msec nodes 44720494 nps 368163 pv 1. ... Rh8 2.Qb2 Ra8 3.Nf3 h6 4.Bd2 Bd7 5.b5 Rg8 6.a4


//pos 3
//rotated > OD by 1.1%
depth 10 score cp -133 time 38482 msec nodes 11722337 nps 304618 pv 1.Re1 Be7 2.Nd4 Nxd4 3.cxd4 Qxd4 4.c3 Qd5 5.Qa4+
//OD > mybitwise by 1.1%
depth 10 score cp -133 time 38907 msec nodes 11722337 nps 301291 pv 1.Re1 Be7 2.Nd4 Nxd4 3.cxd4 Qxd4 4.c3 Qd5 5.Qa4+
//my bitwise
depth 10 score cp -133 time 39339 msec nodes 11722337 nps 297982 pv 1.Re1 Be7 2.Nd4 Nxd4 3.cxd4 Qxd4 4.c3 Qd5 5.Qa4+

// Michael's obstruction+difference

Code: Select all

#define HI(SQ) ( ~((u64)1) << (SQ))
#define LO(SQ) (((u64)(1) << (SQ)) - 1)
#define ALLBITS 0xFFFFFFFFFFFFFFFFUL

u64 attacks_diag7(const int sq) {
   u64 lne = board[sq]->bDiag7;
   u64 lo  = ALLBITS << lastone((LO(sq) & lne & allBits)|1);
   u64 hi  = (HI(sq) & lne & allBits);
   hi &=-hi;
   return lne & (2*hi+lo);
}

u64 attacks_diag9(const int sq) {
   u64 lne = (board[sq]->bMap ^ board[sq]->bDiag7);
   u64 lo  = ALLBITS << lastone((LO(sq) & lne & allBits)|1);
   u64 hi  = (HI(sq) & lne & allBits);
   hi &=-hi;
   return lne & (2*hi+lo);
}

u64 attacks_file(const int sq) {
   u64 lne = board[sq]->rFile;
   u64 lo  = ALLBITS << lastone((LO(sq) & lne & allBits)|1);
   u64 hi  = (HI(sq) & lne & allBits);
   hi &=-hi;
   return lne & (2*hi+lo);
}

u64 attacks_rank(const int sq) {
   u64 lne = (board[sq]->rMap ^ board[sq]->rFile);
   u64 lo  = ALLBITS << lastone((LO(sq) & lne & allBits)|1);
   u64 hi  = (HI(sq) & lne & allBits);
   hi &=-hi;
   return lne & (2*hi+lo);
}

// my straightforward bitwise method

Code: Select all

#define HI(SQ) ( ~((u64)1) << (SQ))
#define LO(SQ) (((u64)(1) << (SQ)) - 1)
#define ALLBITS 0xFFFFFFFFFFFFFFFFUL

u64 attacks_diag7(const int sq) {
   u64 u, d = board[sq]->bDiag7;
   if (d);
   else return 0;
    //v high terminal bit
   u64 v = d & allBits & HI(sq);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO(sq);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
}


u64 attacks_diag9(const int sq) {
   u64 u, d = (board[sq]->bMap ^ board[sq]->bDiag7);
   if (d);
   else return 0;
   
    //v high terminal bit
   u64 v = d & allBits & HI(sq);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO(sq);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
}


u64 attacks_file(const int sq) {
   u64 u, d = board[sq]->rFile;
   assert(d);
    //v high terminal bit
   u64 v = d & allBits & HI(sq);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO(sq);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
}

u64 attacks_rank(const int sq) {
   u64 u, d = (board[sq]->rMap ^ board[sq]->rFile);
    //v high terminal bit
   u64 v = d & allBits & HI(sq);
   v = v ? v & - v : 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO(sq);
   u = u ? BB(lastone(u)) : 1;
   return  d & (((v - 1) | v) ^ (u - 1));
}

Best regards,
Rasjid.