Split Index Super Set Yielding (SISSY) Bitboards

[Mike Sherwin]

I'd like to revisit SISSY bitboards. I think that they can be highly optimised just using C without resorting to assembly. Just considering the bishop for now. Code from the Chess Programming Wiki.

Code: Select all

U64 bss[6][64][64]; // 192 K

U64 bishopAttacks(U64 occ, enumSquare sq) {
  return
    bss[0][sq][(occ >>  9) & 63] &  // 2nd rank
    bss[1][sq][(occ >> 17) & 63] &  
    bss[2][sq][(occ >> 25) & 63] &  
    bss[3][sq][(occ >> 33) & 63] &  
    bss[4][sq][(occ >> 41) & 63] &  
    bss[5][sq][(occ >> 49) & 63] ;  // 7th rank
}    

I agree that is a little expensive. HOWEVER, that can be reduced to only two lookups! First shift the upper 32 bits of the occupancy up by 8 bits. Then and it with the lower 32 bits and then shift the 4th rank down by either 8 or 16 bits depending on the from square. That will produce a split index between the 2nd and third ranks. That is a whole lot of saved shifting and anding. The problem I'm having is the initializing everything into two ranks. I have correct working code that initializes for 6 ranks. Now I just need to do a second level of combining those values into 2 ranks.

Code: Select all

void InitializeB() {
  u08 sq, sqr, i, j, k, l;
  s08 x, dx, y, dy;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      if (i ^ 1) {
        j = i >> 1;
        for (k = 8, l = 0; k <= 48; k += 8, l++) {
          bb = 0;
          b = (u64)i << k;
          for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= ONE << sqr;
            if ((ONE << sqr) & b) break;
          }
          for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= ONE << sqr;
            if ((ONE << sqr) & b) break;
          }
          for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= ONE << sqr;
            if ((ONE << sqr) & b) break;
          }
          for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= ONE << sqr;
            if ((ONE << sqr) & b) break;
          }
          bss[sq][j][l] = bb;
        }
      }
    }
  }
}

And as can be seen the initialisation to 6 ranks is not that long nor very difficult. But further reducing them down to two ranks is giving me too much trouble. Mar showed that SISSY was not that far away from magic to begin with. Isn't it worth further investigation?

The queen is also extremely promising. Here is my code from Bricabrac. Perft numbers are accurate so the accuracy has been verified in Bricabrac and by Mar.

Code: Select all

   case WQ:
    case BQ:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & notme;

As can be seen the code has already been optimised a little by embedding a rank lookup into the existing queen table thus reducing the lookups to 7 instead of the wiki's 8. THEN if the rank is removed and the file is shifted to the a file like in the wiki all that is left is the diagonals that can be manipulated into 2 ranks. That reduces the 7 kind of expensive lookups down to only 3 plus the rank lookup similar to Gerd's Kindergarten bitboards. The Queen was already competitive with magic and maybe even better. The rook also seems promising if handled like the wiki suggest.
https://www.chessprogramming.org/SISSY_Bitboards
Can someone explain to me why there has been no interest in seeing what SISSY bitboards could become? I have to say, I just don't understand.

[mar]

Hi Michael, that's very interesting indeed. As usual you try to come up with new and fresh ideas.

I guess SISSY didn't spark enough interest because they didn't beat magic (yet).
I think that beating queen attacks isn't so interesting either, because mixing magics for bishops/rooks and SISSY for queen would require even more memory for lookups to already a lot (relatively) for magics. I belive Volker (or someone else?) made an effort to compress the LUTs for magics IIRC so there can be some performance gain as well.

So - if you can make SISSY on par (or faster) than magics, I'm pretty sure everybody will switch to SISSY. If anyone can do it, then it's you.

What I like about SISSY is straightforward initialization with smaller LUT. Unfortunately what matters at the end of the day is performance - the only thing SISSY needs is to catch up to fancy magics. Fingers crossed.

Actually if Dany in the other thread has problems with bitboards (performance) - I guess SISSY might be a good starting point for him?

[Mike Sherwin]

Hi Michael, that's very interesting indeed. As usual you try to come up with new and fresh ideas.

I guess SISSY didn't spark enough interest because they didn't beat magic (yet).
I think that beating queen attacks isn't so interesting either, because mixing magics for bishops/rooks and SISSY for queen would require even more memory for lookups to already a lot (relatively) for magics. I belive Volker (or someone else?) made an effort to compress the LUTs for magics IIRC so there can be some performance gain as well.

So - if you can make SISSY on par (or faster) than magics, I'm pretty sure everybody will switch to SISSY. If anyone can do it, then it's you.

What I like about SISSY is straightforward initialization with smaller LUT. Unfortunately what matters at the end of the day is performance - the only thing SISSY needs is to catch up to fancy magics. Fingers crossed.

Actually if Dany in the other thread has problems with bitboards (performance) - I guess SISSY might be a good starting point for him?

I don't think I have it in me to be able to do the initialization for 2 rank storage. It is not as straightforward and my memory problem is getting worse. I just end up in confusion when I try. But, thanks for the vote of confidence. It makes me want to try harder. I was looking at my notes for the rook and once the rank is removed it becomes trivial to fold the file down to one lookup with only 4 shifts to only 6 bits per square. That reduces the rook to only 2 lookups and 1 &&. All I need is the initialization done. I can still do the rest, hopefully.

I would like it if Danny teamed up with me on this. The last couple of times that I responded to him I did not get a reply. He might be upset with me for some reason, idk. However, whomever does the initialization first whether it is me or someone else does it best and will earn full credit for their work.

[Mike Sherwin]

Okay, I just took a short meditative knap. What came to me to go from 6 ranks for the bishop down to three is for every index in rank 2 that has a superset stored find all indexes in rank 5 that also have a superset stored whose bits do not collide with rank 2 bits and combine them with & and store that superset at the new index. Then repeat for ranks (3, 6) and (4, 7). I think that sounds correct? I'll give it a try.

[Mike Sherwin]

Could it really have been this easy all this time and I just could not think of it?

Adding this to the bottom of InitializeBSS() ...

Code: Select all

  for (sq = 0; sq < 64; sq++) {
    for (i = 0; i < 128; i++) {
      for (j = 0; j < 128; j++) {
        if (!(i & j)) {
          bss[sq][i | j][0] = bss[sq][i][0] & bss[sq][j][3];
          bss[sq][i | j][1] = bss[sq][i][1] & bss[sq][j][4];
          bss[sq][i | j][2] = bss[sq][i][2] & bss[sq][j][5];
        }
      }
    }
  }

... looks correct but is it? Time to test!

The complete function.

Code: Select all

void InitializeBSS() {
  u08 sq, sqr, i, j, k, l;
  s08 x, dx, y, dy;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      if (i ^ 1) {
        j = i >> 1;
        for (k = 8, l = 0; k <= 48; k += 8, l++) {
          bb = 0;
          b = (u64)i << k;
          for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          bss[sq][j][l] = bb;
        }
      }
    }
  }

  for (sq = 0; sq < 64; sq++) {
    for (i = 0; i < 128; i++) {
      for (j = 0; j < 128; j++) {
        if (!(i & j)) {
          bss[sq][i | j][0] = bss[sq][i][0] & bss[sq][j][3];
          bss[sq][i | j][1] = bss[sq][i][1] & bss[sq][j][4];
          bss[sq][i | j][2] = bss[sq][i][2] & bss[sq][j][5];
        }
      }
    }
  }

}

[Mike Sherwin]

Could it really have been this easy all this time and I just could not think of it?

Adding this to the bottom of InitializeBSS() ...

Code: Select all

  for (sq = 0; sq < 64; sq++) {
    for (i = 0; i < 128; i++) {
      for (j = 0; j < 128; j++) {
        if (!(i & j)) {
          bss[sq][i | j][0] = bss[sq][i][0] & bss[sq][j][3];
          bss[sq][i | j][1] = bss[sq][i][1] & bss[sq][j][4];
          bss[sq][i | j][2] = bss[sq][i][2] & bss[sq][j][5];
        }
      }
    }
  }

... looks correct but is it? Time to test!

The complete function.

Code: Select all

void InitializeBSS() {
  u08 sq, sqr, i, j, k, l;
  s08 x, dx, y, dy;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      if (i ^ 1) {
        j = i >> 1;
        for (k = 8, l = 0; k <= 48; k += 8, l++) {
          bb = 0;
          b = (u64)i << k;
          for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
            sqr = (((y + dy) << 3) + x + dx);
            bb |= one << sqr;
            if ((one << sqr) & b) break;
          }
          bss[sq][j][l] = bb;
        }
      }
    }
  }

  for (sq = 0; sq < 64; sq++) {
    for (i = 0; i < 128; i++) {
      for (j = 0; j < 128; j++) {
        if (!(i & j)) {
          bss[sq][i | j][0] = bss[sq][i][0] & bss[sq][j][3];
          bss[sq][i | j][1] = bss[sq][i][1] & bss[sq][j][4];
          bss[sq][i | j][2] = bss[sq][i][2] & bss[sq][j][5];
        }
      }
    }
  }

}

Nope, not that simple. The problem is all the pieces contribute to the indexes. Therefore, the simple test for collisions is not correct. A way to fix this that comes to mind is to and the occupancy bits with the empty board bishop bitboard to limit the number of indexes that point to supersets. But, that would add an extra step to both initialization and to generation. And I'm not even sure that I am thinking correctly. So unless someone else steps in with a solution I won't be seen here again unless I can solve it. Bye for now!

[mar]

Code: Select all

U64 bss[6][64][64]; // 192 K

U64 bishopAttacks(U64 occ, enumSquare sq) {
  return
    bss[0][sq][(occ >>  9) & 63] &  // 2nd rank
    bss[1][sq][(occ >> 17) & 63] &  
    bss[2][sq][(occ >> 25) & 63] &  
    bss[3][sq][(occ >> 33) & 63] &  
    bss[4][sq][(occ >> 41) & 63] &  
    bss[5][sq][(occ >> 49) & 63] ;  // 7th rank
}    

hmm, looking at this code, I wonder if one could fuse some the occupancies in a simple way, cutting it down to 3 lookups by using (much) bigger table, say:

Code: Select all

// 6MB!!
uint64_t bss[3][16][64*256];

uint64_t bishopAttacks2(uint64_t occ, uint8_t sq)
{
    const uint64_t tmp = (uint64_t)63;
    const uint64_t mask =
        (tmp << 9) |
        (tmp << 17) |
        (tmp << 25) |
        (tmp << 33) |
        (tmp << 41) |
        (tmp << 49);
    occ &= mask;

    int sqmsb2 = (sq & (3 << 4))*4;
    int sqlsb4 = sq & 15;

  return
    bss[0][sqlsb4][(occ >>  9) + sqmsb2] &  // 2nd&3rd rank
    bss[1][sqlsb4][(occ >>  25) + sqmsb2] &  // 4th&5th rank
    bss[2][sqlsb4][(occ >>  41) + sqmsb2];  // 6th&7th rank
}

the basic idea is to pre-mask and utilize 2 bits of sq to fill gaps in the table
it's very likely that I've made a mistake somewhere as I didn't test this, but the code that gcc produces looks like this:

Code: Select all

bishopAttacks2(unsigned long, unsigned char):
        movabs  rax, 35604928818740736
        lea     rdx, [0+rsi*4]
        and     esi, 15
        and     rdi, rax
        and     edx, 192
        sal     rsi, 14
        mov     rax, rdi
        mov     rcx, rdi
        shr     rdi, 41
        shr     rax, 9
        shr     rcx, 25
        add     rax, rdx
        add     rax, rsi
        add     rsi, rdx
        lea     rdx, [rcx+262144+rsi]
        mov     rax, QWORD PTR pbss[0+rax*8]
        and     rax, QWORD PTR pbss[0+rdx*8]
        lea     rdx, [rsi+524288+rdi]
        and     rax, QWORD PTR pbss[0+rdx*8]
        ret

perhaps more micro-optimizations could be made, like the square setup code, one might lookup a pointer table with sq to fetch the offset table
pointer and so on

I have my doubts though that this would help much (it would likely fry the cache), but who knows... not to mention that this was only the bishops...

I wonder if one might exploit the fact that A&B = B&A is some useful way

[mar]

refining the idea further, simplifying square setup, because it can be precomputed into an offset table:

Code: Select all

uint64_t pbss3_0[16*64*256];
uint64_t pbss3_1[16*64*256];
uint64_t pbss3_2[16*64*256];
uint32_t pbss3ofs[64];

uint64_t bishopAttacks3(uint64_t occ, uint32_t sq)
{
    const uint64_t tmp = (uint64_t)63;
    const uint64_t mask =
        (tmp << 9) |
        (tmp << 17) |
        (tmp << 25) |
        (tmp << 33) |
        (tmp << 41) |
        (tmp << 49);
    occ &= mask;

    uint32_t ofs = pbss3ofs[sq];

  return
    pbss3_0[(occ >>  9) + ofs] &  // 2nd&3rd rank
    pbss3_1[(occ >>  25) + ofs] &  // 4th&5th rank
    pbss3_2[(occ >>  41) + ofs];  // 6th&7th rank
}

Code: Select all

bishopAttacks3(unsigned long, unsigned int):
        movabs  rax, 35604928818740736
        mov     esi, esi
        and     rdi, rax
        mov     edx, DWORD PTR pbss3ofs[0+rsi*4]
        mov     rax, rdi
        mov     rcx, rdi
        shr     rdi, 41
        shr     rax, 9
        shr     rcx, 25
        add     rdi, rdx
        add     rax, rdx
        add     rcx, rdx
        mov     rax, QWORD PTR pbss3_0[0+rax*8]
        and     rax, QWORD PTR pbss3_1[0+rcx*8]
        and     rax, QWORD PTR pbss3_2[0+rdi*8]
        ret

again, no idea if I haven't made a mistake somewhere, but apart from probably frying the cache, the final assembly looks pretty good I think

[mar]

of course I'm stupid, "premasking" won't work, so let's fix it:

Code: Select all

uint64_t pbss4_0[16*64*256];
uint64_t pbss4_1[16*64*256];
uint64_t pbss4_2[16*64*256];
uint32_t pbss4ofs[64];

uint64_t bishopAttacks4(uint64_t occ, uint32_t sq)
{
    const uint32_t mask = 63 + (63 << 8);
    uint32_t ofs = pbss4ofs[sq];

  return
    pbss4_0[((occ >>  9) & mask) + ofs] &  // 2nd&3rd rank
    pbss4_1[((occ >>  25) & mask) + ofs] &  // 4th&5th rank
    pbss4_2[((occ >>  41) & mask) + ofs];  // 6th&7th rank
}

Code: Select all

bishopAttacks4(unsigned long, unsigned int):
        mov     esi, esi
        mov     rax, rdi
        mov     rdx, rdi
        shr     rdi, 41
        mov     ecx, DWORD PTR pbss4ofs[0+rsi*4]
        shr     rax, 9
        shr     rdx, 25
        and     edi, 16191
        and     eax, 16191
        and     edx, 16191
        add     rax, rcx
        add     rdx, rcx
        add     rdi, rcx
        mov     rax, QWORD PTR pbss4_0[0+rax*8]
        and     rax, QWORD PTR pbss4_1[0+rdx*8]
        and     rax, QWORD PTR pbss4_2[0+rdi*8]
        ret

[mar]

and final version, helping the compiler further, baking the offset as pointer into merged table, applying offsets on the go:
(because mov r,[r*8] implies 32-bit displacement anyway)

Code: Select all

uint64_t pbss5_merged[3*16*64*256];
const uint64_t *pbss5ptr[64];

uint64_t bishopAttacks5(uint64_t occ, uint32_t sq)
{
    const uint32_t mask = 63 + (63 << 8);
    const uint64_t *ptr = pbss5ptr[sq];
    const uint32_t ofs = 16*64*256;

  return
    ptr[((occ >>  9) & mask)] &  // 2nd&3rd rank
    ptr[((occ >>  25) & mask) + 1*ofs] &  // 4th&5th rank
    ptr[((occ >>  41) & mask) + 2*ofs];  // 6th&7th rank
}

Code: Select all

bishopAttacks5(unsigned long, unsigned int):
        mov     esi, esi
        mov     rax, rdi
        mov     rcx, rdi
        shr     rdi, 9
        mov     rdx, QWORD PTR pbss5ptr[0+rsi*8]
        shr     rax, 25
        shr     rcx, 41
        and     edi, 16191
        and     eax, 16191
        and     ecx, 16191
        mov     rax, QWORD PTR [rdx+2097152+rax*8]
        and     rax, QWORD PTR [rdx+4194304+rcx*8]
        and     rax, QWORD PTR [rdx+rdi*8]
        ret