An undetected bug for 10 years

[hgm]

Interesting you do the |7. I always do the &070.

If the from- and to-square numbers were packed in bytes in the same integer to begin with, as part of a move from the move list, you could do the |7 and addition SIMD-wise, to end up with 256*t88 + f88. If you would multiply that by -255 << 16 = (-256 + 1) << 16 you would get (-256*256*t88 + 256*(t88-f88) + f88) << 16. and the first term would have been shifted out of the word. Since f88 would be positive, it would not contaminate the higher bytes with its sign extension, and you would get rid of it entirely by shifting 24 bits to the right:

return table[(((move | 0x707) + move)*0xFF010000 >> 24) + 120];

I suppose in modern C standards this might be undefined behavior, so you would have to do some casting so that the overflowing multiply is an unsigned, but the right-shift is a signed int. Or perhaps you should rely on the whole thing being unsigned, mapping negative differences 256 entries higher. You would then not need the +120. (Which was free anyway. You could also have eliminated that add from your code, adding it to the array address at compile time.)

[Gerd Isenberg]

A branchless trial without lookup:

Code: Select all

int direction(int sq1, int  sq2) {
  int deltR =  (sq2>> 3) - (sq1>> 3);
  int deltF =  (sq2 & 7) - (sq1 & 7);
  int sameF = deltR == 0;
  int sameR = deltF == 0;
  int sameD = deltF == deltR;
  int sameA = deltF ==-deltR;
  return 8*(sameF + 2*sameR + 4*sameD + 8*sameA);
}

x86-64 gcc 10.2 -O3

Code: Select all

direction(int, int):
        mov     edx, esi
        mov     eax, edi
        and     esi, 7
        and     edi, 7
        sar     edx, 3
        sar     eax, 3
        xor     r8d, r8d
        sub     esi, edi
        mov     edi, edx
        sete    r8b
        xor     ecx, ecx
        sub     edi, eax
        sete    cl
        cmp     edi, esi
        sete    dil
        sub     eax, edx
        lea     ecx, [rcx+r8*2]
        cmp     eax, esi
        movzx   edi, dil
        sete    al
        lea     ecx, [rcx+rdi*4]
        movzx   eax, al
        lea     eax, [rcx+rax*8]
        sal     eax, 3
        ret

[Gerd Isenberg]

Smart compiler still needs some hint:

Code: Select all

int direction(int sq1, int sq2) {
  int deltR =(sq2>> 3) - (sq1>> 3);
  int deltF =(sq2 & 7) - (sq1 & 7);
  int sameF = deltR == 0;
  int sameR = deltF == 0;
  int sameD =(deltF - deltR) == 0;
  int sameA =(deltF + deltR) == 0;
  return 8*(sameF + 2*sameR + 4*sameD + 8*sameA);
}

x86-64 gcc 10.2 -O3 https://gcc.godbolt.org/

Code: Select all

direction(int, int):
        mov     eax, esi
        mov     edx, edi
        and     esi, 7
        and     edi, 7
        sar     edx, 3
        sar     eax, 3
        xor     ecx, ecx
        sub     esi, edi
        sete    cl
        sub     eax, edx
        sete    dl
        movzx   edx, dl
        lea     edx, [rdx+rcx*2]
        xor     ecx, ecx
        cmp     eax, esi
        sete    cl
        add     eax, esi
        sete    al
        lea     edx, [rdx+rcx*4]
        movzx   eax, al
        lea     eax, [rdx+rax*8]
        sal     eax, 3
        ret

[OliverBr]

Code like this lights all the red flags upon code review. It is way too clever to be trusted. If it's not obvious, it can't be trusted, and must be tested (leaving a unit test to allow later modifications of the codebase).

Do you trust the code a little more, when I show you one usage of this function?

Code: Select all

 b = pin & (pieceb[ROOK] | pieceb[BISHOP] | pieceb[QUEEN]);
 while (b) {
        int f = pullLsb(&b);
        int p = identPiece(f);
        int t = p | getDir(f, kingpos[c]);
        if ((t & 10) == 10) regMoves(PREMOVE(f, p), RMOVE1(f), ml, mn, 0);
        if ((t & 18) == 18) regMoves(PREMOVE(f, p), RMOVE2(f), ml, mn, 0);
        if ((t & 33) == 33) regMoves(PREMOVE(f, p), BMOVE3(f), ml, mn, 0);
        if ((t & 65) == 65) regMoves(PREMOVE(f, p), BMOVE4(f), ml, mn, 0);
}

It's about pinned sliders. They can move, but only in the direction of their King...

[AndrewGrant]

Code like this lights all the red flags upon code review. It is way too clever to be trusted. If it's not obvious, it can't be trusted, and must be tested (leaving a unit test to allow later modifications of the codebase).

Do you trust the code a little more, when I show you one usage of this function?

Code: Select all

 b = pin & (pieceb[ROOK] | pieceb[BISHOP] | pieceb[QUEEN]);
 while (b) {
        int f = pullLsb(&b);
        int p = identPiece(f);
        int t = p | getDir(f, kingpos[c]);
        if ((t & 10) == 10) regMoves(PREMOVE(f, p), RMOVE1(f), ml, mn, 0);
        if ((t & 18) == 18) regMoves(PREMOVE(f, p), RMOVE2(f), ml, mn, 0);
        if ((t & 33) == 33) regMoves(PREMOVE(f, p), BMOVE3(f), ml, mn, 0);
        if ((t & 65) == 65) regMoves(PREMOVE(f, p), BMOVE4(f), ml, mn, 0);
}

It's about pinned sliders. They can move, but only in the direction of their King...

Agree with Lucas. Document "tricks". Otherwise, they are hacks that benefit no one. Not even your future self.

[OliverBr]

Smart compiler still needs some hint:

Code: Select all

int direction(int sq1, int sq2) {
  int deltR =(sq2>> 3) - (sq1>> 3);
  int deltF =(sq2 & 7) - (sq1 & 7);
  int sameF = deltR == 0;
  int sameR = deltF == 0;
  int sameD =(deltF - deltR) == 0;
  int sameA =(deltF + deltR) == 0;
  return 8*(sameF + 2*sameR + 4*sameD + 8*sameA);
}

This is very nice, unfortunately doesn't bring any win:
(On a MacOSX64, gcc -O3) With your function:

Code: Select all

./olithink -sd 16 "6k1/5p1p/P1pb1nq1/6p1/3P4/1BP2PP1/1P1Nb2P/R1B3K1 b - - 9 9 bm g6d3"
 1   221      0        55  f6d5 
 2   137      0       255  f6d5 a6a7 
 3   106      0      4988  g6d3 a6a7 d3e3 g1g2 
 4   -93      0      9319  f6d5 a6a7 d5b6 a7a8q b6a8 a1a8 g8g7 
 5  -139      0     18009  e2a6 a1a6 f6d5 d2e4 d6e7 
 6  -149      1     33994  d6b8 a6a7 b8a7 a1a7 f6d5 d2e4 
 7  -157      1     49935  d6b8 a6a7 b8a7 a1a7 f6d5 a7a8 g8g7 d2e4 
 8  -120      3    119937  d6b8 a6a7 b8a7 a1a7 f6d5 a7a8 g8g7 d2e4 h7h6 
 9  -149     10    340662  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 a7a8 g8g7 d2e4 
10  -100     18    665419  d6b8 a6a7 b8a7 a1a7 f6d5 a7d7 g6e6 d7d8 g8g7 d2e4 h7h6 
11  -108     27   1043853  d6b8 a6a7 b8a7 a1a7 f6d5 a7d7 g6e6 d7d8 g8g7 d2e4 f7f6 e4c5 
12  -107     64   2529963  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 b3c4 h7h5 c4d3 g6d3 d2e4 
13  -108    124   5210000  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 b3c4 h7h5 a7a6 g5g4 f3g4 g6f6 f2e1 
14   -82    222   9666952  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 d2e4 g6h5 a7a8 g8g7 f2g2 g5g4 b3d1 f7f5 
15   -97    526  24563743  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 c3c4 d5b6 c4c5 b6d5 d2c4 g6h5 a7a8 g8g7 h2h3 
16   274   3132 162239850  g6d3 g1f2 e2f3 d2f3 f6e4 f2e1 e4c3 b2c3 d3c3 e1f2 c3a1 c1g5 a1a6 g5f4 d6f4 g3f4 a6d3 b3a2 
move g6d3

Original:

Code: Select all

./olithink -sd 16 "6k1/5p1p/P1pb1nq1/6p1/3P4/1BP2PP1/1P1Nb2P/R1B3K1 b - - 9 9 bm g6d3"
 1   221      0        55  f6d5 
 2   137      0       255  f6d5 a6a7 
 3   106      0      4988  g6d3 a6a7 d3e3 g1g2 
 4   -93      0      9319  f6d5 a6a7 d5b6 a7a8q b6a8 a1a8 g8g7 
 5  -139      0     18009  e2a6 a1a6 f6d5 d2e4 d6e7 
 6  -149      1     33994  d6b8 a6a7 b8a7 a1a7 f6d5 d2e4 
 7  -157      1     49935  d6b8 a6a7 b8a7 a1a7 f6d5 a7a8 g8g7 d2e4 
 8  -120      3    119937  d6b8 a6a7 b8a7 a1a7 f6d5 a7a8 g8g7 d2e4 h7h6 
 9  -149     10    340662  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 a7a8 g8g7 d2e4 
10  -100     19    665419  d6b8 a6a7 b8a7 a1a7 f6d5 a7d7 g6e6 d7d8 g8g7 d2e4 h7h6 
11  -108     30   1043853  d6b8 a6a7 b8a7 a1a7 f6d5 a7d7 g6e6 d7d8 g8g7 d2e4 f7f6 e4c5 
12  -107     65   2529963  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 b3c4 h7h5 c4d3 g6d3 d2e4 
13  -108    127   5210000  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 b3c4 h7h5 a7a6 g5g4 f3g4 g6f6 f2e1 
14   -82    223   9666952  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 d2e4 g6h5 a7a8 g8g7 f2g2 g5g4 b3d1 f7f5 
15   -97    527  24563743  d6b8 g1f2 e2d3 a6a7 b8a7 a1a7 f6d5 c3c4 d5b6 c4c5 b6d5 d2c4 g6h5 a7a8 g8g7 h2h3 
16   274   3109 162239850  g6d3 g1f2 e2f3 d2f3 f6e4 f2e1 e4c3 b2c3 d3c3 e1f2 c3a1 c1g5 a1a6 g5f4 d6f4 g3f4 a6d3 b3a2 
move g6d3

The position of one of my favorite position. They say, this move (Qd3) is invisible for chess engines... he is not the only one.

[Gerd Isenberg]

This is very nice, unfortunately doesn't bring any win:

That is fine, seems the branch prediction works quite well. Your code is bit-twiddling as its best, and imho requires some comments (despite square mapping dependency) to immediately become understandable and possibly some asserts for the precondition. I guess if it gains a few Elo, even Stockfish would take it. Testing divisibility by 7 fails due to 7x9 = 63

Code: Select all

// precondition f and t are on common rank, file, diagonal or antidiagonal
int getDir(int f, int t) {
  if (((f ^ t) & 56) == 0) return 8;     // rank delta zero -> common rank
  if (((f ^ t) & 7) == 0) return 16;     // file delta zero -> common file
  return (((f - t) % 9) == 0) ? 32 : 64; // delta divisible by 9 -> common diagonal, otherwise antidia
}

https://gcc.godbolt.org/

Code: Select all

getDir(int, int):
        mov     edx, edi
        mov     eax, 8
        xor     edx, esi
        test    dl, 56
        je      .L1
        and     edx, 7
        mov     eax, 16
        je      .L1
        sub     edi, esi
        imul    edi, edi, 954437177
        add     edi, 238609294
        cmp     edi, 477218589
        sbb     eax, eax
        and     eax, -32
        add     eax, 64
.L1:
        ret

[Gerd Isenberg]

or better ...

Code: Select all

bool squaresOnSameFile(int sq1, int sq2) {return ((sq1 ^ sq2) & 7) == 0;}
bool squaresOnSameRank(int sq1, int sq2) {return ((sq1 ^ sq2) & 56) == 0;}
bool squaresOnSameDiagonal(int sq1, int sq2) {return ((sq2 - sq1) % 9) == 0;}

// precondition f and t are on common rank, file, diagonal or antidiagonal
int getDir(int f, int t) {
  if (squaresOnSameRank(f,t)) return 8;
  if (squaresOnSameFile(f,t)) return 16;
  return squaresOnSameDiagonal(f,t) ? 32 : 64;
}

with same assembly:

Code: Select all

getDir(int, int):
        mov     edx, edi
        mov     eax, 8
        xor     edx, esi
        test    dl, 56
        je      .L5
        and     edx, 7
        mov     eax, 16
        je      .L5
        sub     esi, edi
        imul    esi, esi, 954437177
        add     esi, 238609294
        cmp     esi, 477218589
        sbb     eax, eax
        and     eax, -32
        add     eax, 64
.L5:
        ret

[OliverBr]

That is fine, seems the branch prediction works quite well. Your code is bit-twiddling as its best, and imho requires some comments (despite square mapping dependency) to immediately become understandable and possibly some asserts for the precondition. I guess if it gains a few Elo, even Stockfish would take it. Testing divisibility by 7 fails due to 7x9 = 63

You are right, of course. It is quite sparsely commented. It should be more.

My idea was to look a the movement from square f (0...63) when adding some numbers:

Code: Select all

f+1 : same rank, next file.
f+7 : next rank, previous file.
f+8 : next rank, same file.
f+9 : next rank, next file.

This bug where I dismissed the fact that field 63 is dividable by both 7 and 9 came from the fact, that the perft numbers were already perfect for every position it tried. That's because only very strange positions with B/Q/K on the black corners fail, like this one:

[d]7K/8/8/4Q3/3q4/8/8/k7 b - - 0 1

This is correct:

Code: Select all

./oliperft103 6 "7K/8/8/4Q3/3q4/8/8/k7 b - - 0 1" => 3370175
./oliperft103 6 "K7/8/8/3Q4/4q3/8/8/7k b - - 0 1" => 3370175

This is with the bug:

Code: Select all

./oliperft102 6 "7K/8/8/4Q3/3q4/8/8/k7 b - - 0 1" => 3369945
./oliperft102 6 "K7/8/8/3Q4/4q3/8/8/7k b - - 0 1" => 3370175