Split Index Super Set Yielding (SISSY) Bitboards

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Thu Feb 13, 2020 9:22 pm

This is the result of over a decade of on again, off again attempts to make a fast bitboard sliding piece move generator.

It uses bitboard supersets anded together to form the attack bitboard.

Bishop on e4 Example:
8 _ _ _ _ _ _ _ _
7 _ _ _ _ _ _ _ x
6 _ _ x _ _ _ _ _
5 _ _ _ _ _ _ _ _
4 _ _ _ _ b _ _ _
3 _ _ _ x _ _ _ _
2 _ _ _ _ _ _ _ _
1 _ _ _ _ _ _ _ _
_ a b c d e f g h

If only the blocker on d3 was present the b_attacks would be:
8 x _ _ _ _ _ _ _
7 _ x _ _ _ _ _ x
6 _ _ x _ _ _ x _
5 _ _ _ x _ x _ _
4 _ _ _ _ _ _ _ _
3 _ _ _ x _ x _ _
2 _ _ _ _ _ _ x _
1 _ _ _ _ _ _ _ x
_ a b c d e f g h

if only the blocker on c6 ... :
8 _ _ _ _ _ _ _ _
7 _ _ _ _ _ _ _ x
6 _ _ x _ _ _ x _
5 _ _ _ x _ x _ _
4 _ _ _ _ _ _ _ _
3 _ _ _ x _ x _ _
2 _ _ x _ _ _ x _
1 _ x _ _ _ _ _ x
_ a b c d e f g h

if only the blocker on h7 ... :
8 x _ _ _ _ _ _ _
7 _ x _ _ _ _ _ x
6 _ _ x _ _ _ x _
5 _ _ _ x _ x _ _
4 _ _ _ _ _ _ _ _
3 _ _ _ x _ x _ _
2 _ _ x _ _ _ x _
1 _ x _ _ _ _ _ x
_ a b c d e f g h

Each one of these bitboards is a superset of the true attack bitboard, hence the Super Set part of the name.
When anded together they form the true attack bitboard.
8 _ _ _ _ _ _ _ _
7 _ _ _ _ _ _ _ x
6 _ _ x _ _ _ x _
5 _ _ _ x _ x _ _
4 _ _ _ _ _ _ _ _
3 _ _ _ x _ x _ _
2 _ _ _ _ _ _ x _
1 _ _ _ _ _ _ _ x
_ a b c d e f g h

Code: Select all

struct bbs {
  u08 rank1;
  u08 rank2;
  u08 rank3;
  u08 rank4;
  u08 rank5;
  u08 rank6;
  u08 rank7;
  u08 rank8;  
};

union bbu {
  bbs b08;
  u64 b64;
};
 
void Initialize() {
  u08 sq, sqr, i, j, k, l;
  s08 x, dx, y, dy;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) { // for every square
    y = sq >> 3; // decompose sq into x and y coordinates
    x = sq & 7;
    j = 0; // j as index, bss[64][j][6]
    for (i = 0; i < 128; i++) { // for every rank of blockers
      if (i ^ 1) { // only care if no bit zro blocker
        bb = 0; // accumulator
        for (k = 8, l = 0; k <= 48; k += 8, l++) { // for every rank of blockers, l as index
          b = (u64)i << k; // shift blockers into position
          for (dx = +1, dy = +1; x + dx < +8, y + dy < +8; dx++, dy++) { // progress along diagonal
            sqr = (((y + dy) << 3) + x + dx); // compose square number
            bb |= ONE << sqr; // accumulate bit
            if (ONE << sqr & b) break; // if blocker then done with diagonal
          }
          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; // store the superset
        j++; // next index
      }
    }
  }
}  

u64 BishopAttacks(u08 sq, bbu occ) {
  occ.b64 = (occ.b64 << 1) & 0x00f3f3f3f3f3f300;
  return
    bss[sq][occ.b08.rank2][0] &
    bss[sq][occ.b08.rank3][1] &
    bss[sq][occ.b08.rank4][2] &
    bss[sq][occ.b08.rank5][3] &
    bss[sq][occ.b08.rank6][4] &
    bss[sq][occ.b08.rank7][5];
}
Memory usage for the bishop is 64 * 64 * 6 * 8 = 196,608 bytes
Shared, rank table, between rook and queen 64 * 64 * 8 = 32768 bytes
rss[64][64][2], 64 * 64 * 8 = 65536 bytes
qss same as bishop 196,608 bytes
total = 196,608 + 32,768 + 65536 + 196,608 = 491,520 bytes

Queen:

Code: Select all

u64 QueenAttacks(u08 sq, bbu occ) {
  u64 bb = rnk[sq][occ.b64 >> ((sq & 56) + 1) & 63];
  occ.b64 = occ.b64 >> 1 & 0x00f3f3f3f3f3f300;
  return bb &
    qss[sq][occ.b08.rank2][0] &
    qss[sq][occ.b08.rank3][1] &
    qss[sq][occ.b08.rank4][2] &
    qss[sq][occ.b08.rank5][3] &
    qss[sq][occ.b08.rank6][4] &
    qss[sq][occ.b08.rank7][5];
};
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Thu Feb 13, 2020 11:08 pm

One tricky detail concerning the queen and rook. I thought the queen code was broken because the rank bits in qss[sq][index] are seen for the rank the queen is on. All it means though is that in the initialization every Superset qss[sq][index][rank] needs to be set to 0xffffffffffffffff so when it is anded in it make no change to the accumulated bit board. The same would need to be done for the rook on square. So if a rook was on b2 it's bit is set in occ. Therefore when it is shifted to bit 8 the lookup rss[sq][0 or 1][rank] needs to return 0xffffffffffffffff for the same reason.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Fri Feb 14, 2020 3:29 am

Trying to debug the bishop initialization two bugs were found.
Corrected (more correct) code:

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;
    j = 0;
    for (i = 0; i < 128; i++) {
      if (i ^ 1) {
        bb = 0;
        for (k = 8, l = 0; k <= 48; k += 8, l++) {
          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;
        }
        j++;
      }
    }
  }
}
It does put in values that look like bishop bitboards but I have no clue if the values are correct. Let's try to find the example of a bishop on e4 given in the original post.

The from square is 28 which is 0x1c. Let's check the d3 square. So we will look at the index 8 and then index 2, bss[28][8][2] therefore should have the bitboard for only the d3 blocker being present.

0x0182442800284482:
8 1 _ _ _ _ _ _ _
7 _ 2 _ _ _ _ _ 8
6 _ _ 4 _ _ _ 4 _
5 _ _ _ 8 _ 2 _ _
4 _ _ _ _ b _ _ _
3 _ _ _ 8 _ 2 _ _
2 _ _ 4 _ _ _ 4 _
1 _ 2 _ _ _ _ _ 8
_ a b c d e f g h

So no it is not the correct bitboard. Am I interpreting the indexes correctly? Am I not detecting the blocker correctly?
Okay, I have to try to stop the debugger at exactly the right spot.
1. when sq = 28
2. when i = 8 - found problem, j = 7, j should = 4 - fixing, j is now correct
3. when k = 16 and l = 1
4. b should be 0x0000000000080000 and it is
5. the dx-- and dy-- should break out
6. sqr = 19 and that is d3 which is correct
7. since -1 -1 direction is last then bb should have the correct bitboard, it does not, bb = 0; in wrong spot - fixing
8. bb = 0x1824428004080:
8 1 _ _ _ _ _ _ _
7 _ 2 _ _ _ _ _ 8
6 _ _ 4 _ _ _ 4 _
5 _ _ _ 8 _ 2 _ _
4 _ _ _ _ b _ _ _
3 _ _ _ 8 _ 2 _ _
2 _ _ _ _ _ _ 4 _
1 _ _ _ _ _ _ _ 8
_ a b c d e f g h

OMG! it has the correct superset. Time to walk to the convenience store and get myself a scooby snack. :D

Corrected code:

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;
        }
      }
    }
  }
}
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Gerd Isenberg » Fri Feb 14, 2020 8:23 am

A have a vague idea now. Small performance killer seems the bb-union. Via 64-bit register each b08 access requires shift/and 63 (which makes the occ.b64 = (occ.b64 >> 1) & 0x003F3F3F3F3F3F00 redundant). Otherwise, writing 64-bit to read partial bytes (movzx reg, byte ptr mem) via memory isn't the way you like to profile. I don''t get the dimension of your qss array - isn't square index and 6-bit rank occupancy enough?

Code: Select all

u64 rnk[64][64];
u64 qss[64][64];

u64 queenAttacks(u08 sq, u64 occ) {
  u64 bb = rnk[sq][occ >> ((sq & 56) + 1) & 63]; // has all bits set outside the rank
  return bb &
    qss[sq][(occ >>  9) & 63] & // has all bits set on the rank, cuts along the relevant diagonals and file
    qss[sq][(occ >> 17) & 63] &
    qss[sq][(occ >> 25) & 63] &
    qss[sq][(occ >> 33) & 63] &
    qss[sq][(occ >> 41) & 63] &
    qss[sq][(occ >> 49) & 63];
}; 
Oups, to handle outer files we need the full 8-bit rank occupancy as index?

Code: Select all

u64 rnk[64][64];
u64 qss[64][256];

u64 queenAttacks(u08 sq, u64 occ) {
  u64 bb = rnk[sq][occ >> ((sq & 56) + 1) & 63]; // has all bits set outside the rank
  return bb &
    qss[sq][(occ >>  8) & 255] & // has all bits set on the rank, cuts along the relevant diagonals and file
    qss[sq][(occ >> 16) & 255] &
    qss[sq][(occ >> 24) & 255] &
    qss[sq][(occ >> 32) & 255] &
    qss[sq][(occ >> 40) & 255] &
    qss[sq][(occ >> 48) & 255];
}; 

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Fri Feb 14, 2020 5:03 pm

Gerd Isenberg wrote:
Fri Feb 14, 2020 8:23 am
A have a vague idea now. Small performance killer seems the bb-union. Via 64-bit register each b08 access requires shift/and 63 (which makes the occ.b64 = (occ.b64 >> 1) & 0x003F3F3F3F3F3F00 redundant). Otherwise, writing 64-bit to read partial bytes (movzx reg, byte ptr mem) via memory isn't the way you like to profile. I don''t get the dimension of your qss array - isn't square index and 6-bit rank occupancy enough?

Code: Select all

u64 rnk[64][64];
u64 qss[64][64];

u64 queenAttacks(u08 sq, u64 occ) {
  u64 bb = rnk[sq][occ >> ((sq & 56) + 1) & 63]; // has all bits set outside the rank
  return bb &
    qss[sq][(occ >>  9) & 63] & // has all bits set on the rank, cuts along the relevant diagonals and file
    qss[sq][(occ >> 17) & 63] &
    qss[sq][(occ >> 25) & 63] &
    qss[sq][(occ >> 33) & 63] &
    qss[sq][(occ >> 41) & 63] &
    qss[sq][(occ >> 49) & 63];
}; 
Oups, to handle outer files we need the full 8-bit rank occupancy as index?

Code: Select all

u64 rnk[64][64];
u64 qss[64][256];

u64 queenAttacks(u08 sq, u64 occ) {
  u64 bb = rnk[sq][occ >> ((sq & 56) + 1) & 63]; // has all bits set outside the rank
  return bb &
    qss[sq][(occ >>  8) & 255] & // has all bits set on the rank, cuts along the relevant diagonals and file
    qss[sq][(occ >> 16) & 255] &
    qss[sq][(occ >> 24) & 255] &
    qss[sq][(occ >> 32) & 255] &
    qss[sq][(occ >> 40) & 255] &
    qss[sq][(occ >> 48) & 255];
}; 
Hi Gerd, I thought the x86 64 processor can use 8 bit registers as indexes. So a union would allow that simple adaptation to be used. Am I wrong about that. Or is the problem that it would have to load a register each time instead of simply shifting one 64 bit register several times. I guess that is it. Yes, I see now, once again, that the outer bits are a problem for the queen. It is just my memory problem. I forget things almost as fast as I lean them. Has anyone ever seen the movie Memento? My memory is not that bad but I do need to make lots of notes. The problem is I need notes to remember where my notes are, lol. Anyway, without someone else's help, like Harald gave to my other idea and like your giving, SISSY Bitboards may never get a fair chance. Thanks!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Gerd Isenberg » Fri Feb 14, 2020 5:10 pm

Of course one needs to pass the rank of the occupancy as well! My bad.

Code: Select all

u64 rnk[64][64];
u64 qss[64][256][6]; // 768K

u64 queenAttacks(u08 sq, u64 occ) {
  u64 bb = rnk[sq][occ >> ((sq & 56) + 1) & 63]; // has all bits set outside the rank
  return bb &
    qss[sq][(occ >>  8) & 255][0] & // has all bits set on the rank, cuts along the relevant diagonals and file
    qss[sq][(occ >> 16) & 255][1] &
    qss[sq][(occ >> 24) & 255][2] &
    qss[sq][(occ >> 32) & 255][3] &
    qss[sq][(occ >> 40) & 255][4] &
    qss[sq][(occ >> 48) & 255][5];
};
 

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Fri Feb 14, 2020 5:51 pm

Gerd Isenberg wrote:
Fri Feb 14, 2020 5:10 pm
Of course one needs to pass the rank of the occupancy as well! My bad.

Code: Select all

u64 rnk[64][64];
u64 qss[64][256][6]; // 768K

u64 queenAttacks(u08 sq, u64 occ) {
  u64 bb = rnk[sq][occ >> ((sq & 56) + 1) & 63]; // has all bits set outside the rank
  return bb &
    qss[sq][(occ >>  8) & 255][0] & // has all bits set on the rank, cuts along the relevant diagonals and file
    qss[sq][(occ >> 16) & 255][1] &
    qss[sq][(occ >> 24) & 255][2] &
    qss[sq][(occ >> 32) & 255][3] &
    qss[sq][(occ >> 40) & 255][4] &
    qss[sq][(occ >> 48) & 255][5];
};
 
Just to get it working all that is needed is the Queen Attacks function as extracting the bishop or rook moves is just one more step. Then later the bishop and rook can be added if it would be worthwhile.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Sat Feb 15, 2020 12:24 am

IT WORKS!
Programming is becoming more difficult for me. I felt a little bit of desperation just to get something working. So I made the SISSY queen code as simple as possible just so I could get it working and have proof of concept. I have been testing it now for a couple of hours. Just the white queen to start with. But that is good enough for proof of concept! :D

If someone else wants to give it a try here is the initialization.

Code: Select all

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

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    bob[sq] = 0;
    rob[sq] = 0;
    for (i = 0; i < 256; i++) {
      for (k = 0, l = 0; k <= 56; 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;
          bob[sq] |= 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;
          bob[sq] |= 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;
          bob[sq] |= 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;
          bob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dx = -1; x + dx > -1; dx--) {
          sqr = (y << 3) + x + dx;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dx = +1; x + dx < +8; dx++) {
          sqr = (y << 3) + x + dx;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dy = +1; y + dy < +8; dy++) {
          sqr = ((y + dy) << 3) + x;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dy = -1; y + dy > -1; dy--) {
          sqr = (y << 3) + x + dx;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        qss[sq][i][l] = bb;
      }
    }
  }
}


And here is my implementation in my engine RomiChess. Notice that I simplified it to just process all 8 ranks the same way. If someone test it please let me know what you think. Thanks!!

Code: Select all

       case WQUEEN:
/*        h->moves[id] = ((ray7p[fs] & belowInc[FirstBit(ray7p[fs] & aPieces)])
                     |  (ray9p[fs] & belowInc[FirstBit(ray9p[fs] & aPieces)])
                     |  (ray7m[fs] & aboveInc[LastBit(ray7m[fs] & aPieces)])
                     |  (ray9m[fs] & aboveInc[LastBit(ray9m[fs] & aPieces)])
                     |  (ray8p[fs] & belowInc[FirstBit(ray8p[fs] & aPieces)])
                     |  (ray1p[fs] & belowInc[FirstBit(ray1p[fs] & aPieces)])
                     |  (ray8m[fs] & aboveInc[LastBit(ray8m[fs] & aPieces)])
                     |  (ray1m[fs] & aboveInc[LastBit(ray1m[fs] & aPieces)]));*/
        h->moves[id] = qss[fs][aPieces & 255][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]
                     & qss[fs][(aPieces >> 56) & 255][7];
        h->attacked |= h->moves[id];
        h->moves[id] &= notMe;
        continue;
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Sat Feb 15, 2020 1:27 am

It works when the correct init is posted. Somehow I posted the init before the last bug fix. :? Here is the correct init. Sorry bout that!

Code: Select all

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

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    bob[sq] = 0;
    rob[sq] = 0;
    for (i = 0; i < 256; i++) {
      for (k = 0, l = 0; k <= 56; 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;
          bob[sq] |= 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;
          bob[sq] |= 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;
          bob[sq] |= 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;
          bob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dx = -1; x + dx > -1; dx--) {
          sqr = (y << 3) + x + dx;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dx = +1; x + dx < +8; dx++) {
          sqr = (y << 3) + x + dx;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dy = +1; y + dy < +8; dy++) {
          sqr = ((y + dy) << 3) + x;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        for (dy = -1; y + dy > -1; dy--) {
          sqr = ((y + dy) << 3) + x;
          bb |= ONE << sqr;
          rob[sq] |= ONE << sqr;
          if ((ONE << sqr) & b) break;
        }
        qss[sq][i][l] = bb;
      }
    }
  }
}
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Split Index Super Set Yielding (SISSY) Bitboards

Post by Michael Sherwin » Sat Feb 15, 2020 2:18 am

I have now replaced the queen code for white and black for both regular move gen and captures only move gen. It is running flawlessly. Some crude speed comparisons is showing a range of performance increase of from 75,000 to 330,000 nodes per second (Romi on my PC searches over 6 million nodes per second normally) depending on the position. The more open the position the bigger the increase. Next report will have the rooks and bishops added using the queen code and extracting the proper bits using bob and rob. Won't be as efficient as writing the bishop and rook specific code but it is a start. :D
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Post Reply