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&#40;SQ&#41; (&#40;ui64_t&#41;(~1&#41; << &#40;SQ&#41;)
#define LO&#40;SQ&#41; ((&#40;ui64_t&#41;( 1&#41; << &#40;SQ&#41;) - 1&#41;
#define ALLBITS &#40;0xFFFFFFFFFFFFFFFF&#41;

ui64_t bishop_diag7_attacks&#40;const int sq,ui64_t occ&#41; 
&#123; 
 ui64_t d,b,u,v;

 b = bit&#40;sq&#41;; 
 d = DIAGONAL_7&#40;sq&#41;^b;

 //u low terminal bit 
 u = ALLBITS & LO&#40;sq&#41; & occ;
 u = ALLBITS << bsr64&#40;u|1&#41;;

 //v high terminal bit 
 v = ALLBITS & HI&#40;sq&#41; & occ;
 v&=-v;

 return (&#40;d&#41; & &#40;2*v+u&#41;);
&#125;

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 = &#40;ui64_t&#41;(-1&#41; << bsr64&#40;lo|1&#41;;

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

 return&#40;lmsk->lineEx & &#40;2*hi+lo&#41;);
&#125;

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&#40;SQ&#41; (&#40;ui64_t&#41;(~1&#41; << &#40;SQ&#41;)
#define LO&#40;SQ&#41; ((&#40;ui64_t&#41;( 1&#41; << &#40;SQ&#41;) - 1&#41;
#define ALLBITS &#40;0xFFFFFFFFFFFFFFFF&#41;

ui64_t bishop_diag7_attacks&#40;const int sq,ui64_t occ&#41; 
&#123; 
 ui64_t d,b,u,v;

 b = bit&#40;sq&#41;; 
 d = DIAGONAL_7&#40;sq&#41;^b;

 //u low terminal bit 
 u = ALLBITS & LO&#40;sq&#41; & occ;
 u = ALLBITS << bsr64&#40;u|1&#41;;

 //v high terminal bit 
 v = ALLBITS & HI&#40;sq&#41; & occ;
 v&=-v;

 return (&#40;d&#41; & &#40;2*v+u&#41;);
&#125;

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 = &#40;ui64_t&#41;(-1&#41; << bsr64&#40;lo|1&#41;;

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

 return&#40;lmsk->lineEx & &#40;2*hi+lo&#41;);
&#125;

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&#40;SQ&#41; (&#40;u64&#41;(~1&#41; << &#40;SQ&#41;)
#define LO&#40;SQ&#41; ((&#40;u64&#41;( 1&#41; << &#40;SQ&#41;) - 1&#41;
#define ALLBITS &#40;0xFFFFFFFFFFFFFFFF&#41;

u64 attacks_diag7&#40;const int sq&#41;
&#123;
   u64 d,b,u,v;

   b = BB&#40;sq&#41;;
   d = board&#91;sq&#93;->bDiag7;

 //u low terminal bit
   u = ALLBITS & LO&#40;sq&#41; & allBits;
   u = ALLBITS << lastone&#40;u|1&#41;;

 //v high terminal bit
   v = ALLBITS & HI&#40;sq&#41; & allBits;
   v&=-v;

   return (&#40;d&#41; & &#40;2*v+u&#41;);
&#125; 

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&#40;SQ&#41; (&#40;ui64_t&#41;(~1&#41; << &#40;SQ&#41;)
#define LO&#40;SQ&#41; ((&#40;ui64_t&#41;( 1&#41; << &#40;SQ&#41;) - 1&#41;
#define ALLBITS &#40;0xFFFFFFFFFFFFFFFF&#41;

//lo  = all bits set below square index
//hi  = all bits set above square index
//occ = occupancy bits&#40;all pieces, or desired&#40;xrayAttacks&#41; piece set&#41;
//bsr = bitscan reverse
//lne = linemask excluding square itself

//hint&#58;
// - use also precomputed masks for LO&#40;),HI&#40;) macros &#40;saves some operations&#41;
// - 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&#40;&#40;LO&#40;sq&#41; & occ&#41;|1&#41;;
 hi  = &#40;HI&#40;sq&#41; & occ&#41;;
 hi &=-hi;

 return (&#40;lne&#41; & &#40;2*hi+lo&#41;);
&#125;

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&#40;SQ&#41; ((&#40;ui64_t&#41;(~1&#41; << &#40;SQ&#41;)  & lne&#41;
#define LINE_LO&#40;SQ&#41; (((&#40;ui64_t&#41;( 1&#41; << &#40;SQ&#41;) - 1&#41;  & lne&#41;

ui64_t lineAttack&#40;const ui64_t lne,const ui64_t occ,const int sq&#41; 
&#123; 
 ui64_t lo,hi; 

 lo  = ALLBITS << bsr64&#40;&#40;LINE_LO&#40;sq&#41; & occ&#41;|1&#41;; 
 hi  = &#40;LINE_HI&#40;sq&#41; & occ&#41;; 
 hi &=-hi; 

 return (&#40;lne&#41; & &#40;2*hi+lo&#41;); 
&#125; 

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&#40;SQ&#41; ( ~(&#40;u64&#41;1&#41; << &#40;SQ&#41;)
#define LO&#40;SQ&#41; ((&#40;u64&#41;&#40;1&#41; << &#40;SQ&#41;) - 1&#41;
#define ALLBITS 0xFFFFFFFFFFFFFFFFUL

u64 attacks_diag7&#40;const int sq&#41; &#123;
   u64 lne = board&#91;sq&#93;->bDiag7;
   u64 lo  = ALLBITS << lastone&#40;&#40;LO&#40;sq&#41; & lne & allBits&#41;|1&#41;;
   u64 hi  = &#40;HI&#40;sq&#41; & lne & allBits&#41;;
   hi &=-hi;
   return lne & &#40;2*hi+lo&#41;;
&#125;

u64 attacks_diag9&#40;const int sq&#41; &#123;
   u64 lne = &#40;board&#91;sq&#93;->bMap ^ board&#91;sq&#93;->bDiag7&#41;;
   u64 lo  = ALLBITS << lastone&#40;&#40;LO&#40;sq&#41; & lne & allBits&#41;|1&#41;;
   u64 hi  = &#40;HI&#40;sq&#41; & lne & allBits&#41;;
   hi &=-hi;
   return lne & &#40;2*hi+lo&#41;;
&#125;

u64 attacks_file&#40;const int sq&#41; &#123;
   u64 lne = board&#91;sq&#93;->rFile;
   u64 lo  = ALLBITS << lastone&#40;&#40;LO&#40;sq&#41; & lne & allBits&#41;|1&#41;;
   u64 hi  = &#40;HI&#40;sq&#41; & lne & allBits&#41;;
   hi &=-hi;
   return lne & &#40;2*hi+lo&#41;;
&#125;

u64 attacks_rank&#40;const int sq&#41; &#123;
   u64 lne = &#40;board&#91;sq&#93;->rMap ^ board&#91;sq&#93;->rFile&#41;;
   u64 lo  = ALLBITS << lastone&#40;&#40;LO&#40;sq&#41; & lne & allBits&#41;|1&#41;;
   u64 hi  = &#40;HI&#40;sq&#41; & lne & allBits&#41;;
   hi &=-hi;
   return lne & &#40;2*hi+lo&#41;;
&#125;

// my straightforward bitwise method

Code: Select all

#define HI&#40;SQ&#41; ( ~(&#40;u64&#41;1&#41; << &#40;SQ&#41;)
#define LO&#40;SQ&#41; ((&#40;u64&#41;&#40;1&#41; << &#40;SQ&#41;) - 1&#41;
#define ALLBITS 0xFFFFFFFFFFFFFFFFUL

u64 attacks_diag7&#40;const int sq&#41; &#123;
   u64 u, d = board&#91;sq&#93;->bDiag7;
   if &#40;d&#41;;
   else return 0;
    //v high terminal bit
   u64 v = d & allBits & HI&#40;sq&#41;;
   v = v ? v & - v &#58; 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO&#40;sq&#41;;
   u = u ? BB&#40;lastone&#40;u&#41;) &#58; 1;
   return  d & ((&#40;v - 1&#41; | v&#41; ^ &#40;u - 1&#41;);
&#125;


u64 attacks_diag9&#40;const int sq&#41; &#123;
   u64 u, d = &#40;board&#91;sq&#93;->bMap ^ board&#91;sq&#93;->bDiag7&#41;;
   if &#40;d&#41;;
   else return 0;
   
    //v high terminal bit
   u64 v = d & allBits & HI&#40;sq&#41;;
   v = v ? v & - v &#58; 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO&#40;sq&#41;;
   u = u ? BB&#40;lastone&#40;u&#41;) &#58; 1;
   return  d & ((&#40;v - 1&#41; | v&#41; ^ &#40;u - 1&#41;);
&#125;


u64 attacks_file&#40;const int sq&#41; &#123;
   u64 u, d = board&#91;sq&#93;->rFile;
   assert&#40;d&#41;;
    //v high terminal bit
   u64 v = d & allBits & HI&#40;sq&#41;;
   v = v ? v & - v &#58; 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO&#40;sq&#41;;
   u = u ? BB&#40;lastone&#40;u&#41;) &#58; 1;
   return  d & ((&#40;v - 1&#41; | v&#41; ^ &#40;u - 1&#41;);
&#125;

u64 attacks_rank&#40;const int sq&#41; &#123;
   u64 u, d = &#40;board&#91;sq&#93;->rMap ^ board&#91;sq&#93;->rFile&#41;;
    //v high terminal bit
   u64 v = d & allBits & HI&#40;sq&#41;;
   v = v ? v & - v &#58; 0x8000000000000000UL;
    //u low terminal bit
   u = d & allBits & LO&#40;sq&#41;;
   u = u ? BB&#40;lastone&#40;u&#41;) &#58; 1;
   return  d & ((&#40;v - 1&#41; | v&#41; ^ &#40;u - 1&#41;);
&#125;

Best regards,
Rasjid.