TalkChess.com

Posted: **Wed Feb 12, 2020 2:44 am**

It has been quite a while since I have tried to come up with something new. I used to do this just for fun. This one I believe may be an improvement on "Sherwin Bitboards" as demonstrated by Harold Luben on the Chess Programming Wiki. It combines a few different ideas. Just consider the code pseudo code because I probably do not remember the C syntax.

It uses the super set idea:
A single bit of an occupancy has an attack bb. If two bits are in the occupancy then the attack = ss[bit1] & ss[bit2].

It uses the split index idea:
Simply put split inexes requires less storage.

It should be dual pipeline friendly. Maybe it would have to be written differently for that though?

Anyway, this is just for fun because life is boring at times, lol. Still I'd appreciate some thoughts.

Code: Select all

struct ranks {
  u08 rank0;
  u08 rank1;
  u08 rank2;
  u08 rank3;
  u08 rank4;
  u08 rank5;
  u08 rank6;
  u08 rank7;
};

union bbu {
  ranks;
  u64;
}; 

bbu occ;

u64 RookAttacks(int sq, bbu occ) {
  int x = sq & 7;
  return   ss1[sq][(occ >> ((sq >> 3) << 3)) & 7]
         & ss2[sq][0][(occ.rank1 >> x) & 1] 
         & ss2[sq][1][(occ.rank2 >> x) & 1] 
         & ss2[sq][2][(occ.rank3 >> x) & 1] 
         & ss2[sq][3][(occ.rank4 >> x) & 1] 
         & ss2[sq][4][(occ.rank5 >> x) & 1] 
         & ss2[sq][5][(occ.rank6 >> x) & 1]; 
}

Edit: Occ should only need shifted once before the anding process so eaxh line may be "& ss2[sq][#][occ.rank# & 1].

Posted: **Wed Feb 12, 2020 4:46 am**

After relearning the C syntax I have come up with this.

Code: Select all

typedef unsigned char u08;
typedef unsigned long long u64;

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

union bbu {
  bbs b08;
  u64 b64;
};

bbu bb;

u64 ss1[64][64];
u64 ss2[64][6][2];

u64 RookAttacks(u08 sq, bbu occ) {
  u64 bb = ss1[sq][(occ.b64 >> (((sq >> 3 << 3) + 1) & 7))];
  occ.b64 >>= (sq & 7) & 0x0001010101010100;
  bb &= ss2[sq][0][occ.b08.rank1];
  bb &= ss2[sq][1][occ.b08.rank2];
  bb &= ss2[sq][2][occ.b08.rank3];
  bb &= ss2[sq][3][occ.b08.rank4];
  bb &= ss2[sq][4][occ.b08.rank5];
  bb &= ss2[sq][5][occ.b08.rank6];
  return bb;
}

Posted: **Wed Feb 12, 2020 7:07 am**

This is my first try at initialization. I think it looks correct. But I'm having a hard time keeping it in my head. Can someone please look it over?

Code: Select all

void InitRookAttacks() {
  u08 sq, i, j, x, y, dx, dy;
  u32 b;
  u64 bb;
  
  for (sq = 0; sq <= 63; sq++) {
    x = sq & 7;
    y = sq >> 3;

    for (i = 0; i < 128; i++) { // i = blocking pattern
      if (i ^ 1) { // only when bit zero is not set
        j = i >> 1; // turn i into 6 bit index
        ss1[sq][j] = 0x0000000000000000;
        bb = i << ((sq >> 3) << 3); // bb is now actual blocking pattern
        for (dy = -1; y + dy > -1; ss1[sq][j]|= 1ull << (sq + dy << 3), dy--); // for [sq][j] add ssy bits
        for (dy = +1; y + dy < +8; ss1[sq][j]|= 1ull << (sq + dy << 3), dy++); // no blocking bits for the y direction
        do { 
          b = 0; // b remains zero the first time through so no problem
          _BitScanForward64(&b, bb); // for each bit in the index we accumulate the ss bits into ss1[sq][j]
          for (dx = -1; x + dx > -1; ss1[sq][j] |= 1ull << (sq + dx), dx--) {
            if (sq + dx == b) break; // stop adding ss bits if we find a blocker
          }
          for (dx = +1; x + dx < +8; ss1[sq][j] |= 1ull << (sq + dx), dx++) {
            if (sq + dx == b) break;
          }
        } while (bb);
      }
    }

    for (i = 0; i < 6; i++) {
      ss2[sq][i][0] = 0xffffffffffffffff;
      ss2[sq][i][1] = 0x0000000000000000;
      b = ((i + 1) * 8) + (sq & 7);
      for (dx = -1; x + dx > -1; ss2[sq][i][1] |= 1ull << (sq + dx), dx--);
      for (dx = +1; x + dx < +8; ss2[sq][i][1] |= 1ull << (sq + dx), dx++);
      for (dy = -1; y + dy > -1; ss2[sq][i][1] |= 1ull << (sq + dy << 3), dy--) {
        if (sq + dy << 3 == b) break;}
      for (dy = +1; y + dy < +8; ss2[sq][i][1] |= 1ull << (sq + dy << 3), dy++) {
        if (sq + dy << 3 == b) break;}
    }
  }
}

Tomorrow I will try to work up some code to test this.

Posted: **Wed Feb 12, 2020 8:46 pm**

Hi Michael I am Harald Lüßen -- or if you do not like ü and ß -- Harald Luessen.

Code: Select all

I read this 
  u64 bb = ss1[sq][(occ.b64 >> (((sq >> 3 << 3) + 1) & 7))];
as
  u64 bb = ss1[sq][(occ.b64 >> (((sq & 0xc8) + 1) & 7))];
or
  u64 bb = ss1[sq][(occ.b64 >> (((sq & 56) + 1) & 7))];
and then it is 
  u64 bb = ss1[sq][(occ.b64 >> ((00sss000_binary + 1) & 7))];
and then it is 
  u64 bb = ss1[sq][(occ.b64 >> ((00sss001_binary) & 00000111_binary))];
and then it is 
  u64 bb = ss1[sq][(occ.b64 >> (1))];
or
  u64 bb = ss1[sq][occ.b64 >> 1];
That is the occupancy shifted by one file. With underflows from one rank to the next at the a and h file.

I read this 
  occ.b64 >>= (sq & 7) & 0x0001010101010100; // (file number of square) & 0x...00
as
  occ.b64 >>= 0;

Can you explain if that was intended. And if so why so complicated?
But I may be wrong because it is late and I am tired.
I did not read further.

Posted: **Wed Feb 12, 2020 11:16 pm**

Harald wrote: ↑Wed Feb 12, 2020 8:46 pm Hi Michael I am Harald Lüßen -- or if you do not like ü and ß -- Harald Luessen.

Code: Select all

I read this 
  u64 bb = ss1[sq][(occ.b64 >> (((sq >> 3 << 3) + 1) & 7))];
as
  u64 bb = ss1[sq][(occ.b64 >> (((sq & 0xc8) + 1) & 7))];
or
  u64 bb = ss1[sq][(occ.b64 >> (((sq & 56) + 1) & 7))];
and then it is 
  u64 bb = ss1[sq][(occ.b64 >> ((00sss000_binary + 1) & 7))];
and then it is 
  u64 bb = ss1[sq][(occ.b64 >> ((00sss001_binary) & 00000111_binary))];
and then it is 
  u64 bb = ss1[sq][(occ.b64 >> (1))];
or
  u64 bb = ss1[sq][occ.b64 >> 1];
That is the occupancy shifted by one file. With underflows from one rank to the next at the a and h file.

I read this 
  occ.b64 >>= (sq & 7) & 0x0001010101010100; // (file number of square) & 0x...00
as
  occ.b64 >>= 0;

Can you explain if that was intended. And if so why so complicated?
But I may be wrong because it is late and I am tired.
I did not read further.

Hi Harald, I remember the last time we worked on my idea. You did almost all the work. I will always acknowledge that fact!

I do not think that is what I meant. If a square is >> 3 it divides it by 8 and then << 8 multiplies by 8 to get the shift number to shift the rank bits to bits 1 to 6 then the >> 1 moves it to bits 0 to 5 to be used as an index. Maybe it does not work as intended. All I want to do is move the rank bits to bits 0 to 5.

Oh I see my final & 7 is wrong. It should be & 63. I guess that I was a bit tired too, lol.

Posted: **Thu Feb 13, 2020 12:13 am**

I made the correction.Probably not the last.

Code: Select all

u64 RookAttacks(u08 sq, bbu occ) {
  u64 bb = ss1[sq][(occ.b64 >> ((((sq >> 3) << 3) + 1) & 63))];
  occ.b64 >>= (sq & 7) & 0x0001010101010100;
  bb &= ss2[sq][0][occ.b08.rank1];
  bb &= ss2[sq][1][occ.b08.rank2];
  bb &= ss2[sq][2][occ.b08.rank3];
  bb &= ss2[sq][3][occ.b08.rank4];
  bb &= ss2[sq][4][occ.b08.rank5];
  bb &= ss2[sq][5][occ.b08.rank6];
  return bb;

I'll just pick a square at random, 57. Okay not quite random as that was the year I was born.
[(occ.b64 >> ((((sq >> 3) << 3) + 1) & 63))]
All I want is the rank occupancy as an index. So 57 >> 3 = 7. Then 7 << 3 = 56 + 1 = 57. Hmm, not the best example to start with but I guess it works. Okay let's do square 35 the year my mom was born. 35 >> 3 = 4. Then 4 << 3 = 32 + 1 = 33. So if occ is shifted down by 33 then the blocker on 34 if there is one will be at bit zero. Then & 63 results in an index to access the ss1[sq][index] for a bb allowed by the rank blockers.
occ.b64 >>= (sq & 7) & 0x0001010101010100;
Now all we want are the file bits as an index of 0 or 1. Therefore we shift all the file bits to file1 and mask everything else away. If a bit accessed by rank is 0 then 0xffffffffffffffff is anded because it does not limit the squares that can be moved to. If the index is a 1 then the move set that bit allows is anded. When all the possible bit sets have been anded together what is left should be the rook attacks.

EDIT:
57 = 0b111001 & 0b111000 = 111000 = 56 + 1 = 57
35 = 0b100011 & 0b111000 = 100000 = 32 + 1 = 33 Okay, they both work. Let's try a couple more.
63 = 0b111111 & 0b111000 = 111000 = 56 + 1 = 57 Cool!
01 = 0b000001 & 0b111000 = 000000 = 0 + 1 = 1 !
That then simplifies the code to.
u64 bb = ss1[sq][(occ.b64 >> ((sq & 56) + 1) & 63];

Code: Select all

u64 RookAttacks(u08 sq, bbu occ) {
  u64 bb = ss1[sq][occ.b64 >> ((sq & 56) + 1)];
  occ.b64 >>= (sq & 7) & 0x0001010101010100;
  bb &= ss2[sq][0][occ.b08.rank1];
  bb &= ss2[sq][1][occ.b08.rank2];
  bb &= ss2[sq][2][occ.b08.rank3];
  bb &= ss2[sq][3][occ.b08.rank4];
  bb &= ss2[sq][4][occ.b08.rank5];
  bb &= ss2[sq][5][occ.b08.rank6];
  return bb;

Does this make more sense now?

Posted: **Thu Feb 13, 2020 12:46 am**

I'm having a difficult time.

Code: Select all

u64 RookAttacks(u08 sq, bbu occ) {
  u64 bb = ss1[sq][(occ.b64 >> ((sq & 56) + 1)) & 63];
  occ.b64 >>= (sq & 7) & 0x0001010101010100;
  bb &= ss2[sq][0][occ.b08.rank1];
  bb &= ss2[sq][1][occ.b08.rank2];
  bb &= ss2[sq][2][occ.b08.rank3];
  bb &= ss2[sq][3][occ.b08.rank4];
  bb &= ss2[sq][4][occ.b08.rank5];
  bb &= ss2[sq][5][occ.b08.rank6];
  return bb;

Posted: **Thu Feb 13, 2020 9:15 am**

The queen would be the biggest benefactor of this method.

Code: Select all

u64 QueenAttacks(u08 sq, bbu occ) {
  occ.b64 >>= 1 & 0x00f3f3f3f3f3f300;
  return qss[sq][0][occ.b08.rank1]
    & qss[sq][1][occ.b08.rank2]
    & qss[sq][2][occ.b08.rank3]
    & qss[sq][3][occ.b08.rank4]
    & qss[sq][4][occ.b08.rank5]
    & qss[sq][5][occ.b08.rank6];
 }

The memory usage would be, 64 * 64 * 8 * 6 = 196,608 bytes. If I'm thinking correctly. And this has to be faster than magic for the queen! Right? Or am I hallucinating?

Posted: **Thu Feb 13, 2020 9:28 am**

And I guess that I had better give them a name before someone beats me to it.

Split Index Super Set Yield Bitboards.

Or Sissy Bitboards!

Posted: **Thu Feb 13, 2020 10:37 am**

Ten years ago this kind of thing because of my learning disability was just beyond my ability. I just can't remember everything. I just can't keep it all in my head. Of course the queen on the edge of the board means that the queen has to be handled like the rook, but just requiring more memory . But I believe it will still be a big win. We will see.

TalkChess.com

New RookAttacks() - possibly

New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly

Re: New RookAttacks() - possibly