Some questions from a beginner

[Gerd Isenberg]

The attack getting code looks correct, so it seems there goes something wrong with your initialization. Is your square mapping consistent? First check whether occupy-index zero (empty board) leaves the full attack on the otherwise empty board. Then calculate the &*>> bishop occupied index (occ) of the d4-bishop, and put a temporary condition inside the initialization code when storing attacks to that square, occupy-index, to inspect what goes wrong. May be it is a good idea to start sliding piece attacks with something simpler, with same interface, such as Classical Approach, see Hiding the Implementation.

[The_Algebraist]

Hello Gerd,

thank you very much for your reply! I was trying to fix it all day but couldn't get it to work.

With

Code: Select all

printBitboard(bishopAttacks(0, Square(0)));

I get

Code: Select all

.  .  .  .  .  .  .  x
.  .  .  .  .  .  x  .
.  .  .  .  .  x  .  .
.  .  .  .  x  .  .  .
.  .  .  x  .  .  .  .
.  .  x  .  .  .  .  .
.  x  .  .  .  .  .  .
.  .  .  .  .  .  .  .

which is correct I think.



I can inspect the index, but I don't get much information from that (it's 484 in this case), because I precomputed the arrays using the method suggested in the wiki:
http://chessprogramming.wikispaces.com/ ... for+Magics

I guess this is where something went wrong.

The bishop magics look like this: http://pastebin.com/ZUDePNy6

Is there any method I can verify these?

Maybe I really try another approach.
Is there an approach that is good to implement but not too slow?

How is the the classical variant compared to the hyperbola quintessence?


Edit:

My square-representation is just an enum:

Code: Select all

enum Square {
    // Little endian rank-file (LERF) mapping
    SQ_A1, SQ_B1, SQ_C1, SQ_D1, SQ_E1, SQ_F1, SQ_G1, SQ_H1,
    SQ_A2, SQ_B2, SQ_C2, SQ_D2, SQ_E2, SQ_F2, SQ_G2, SQ_H2,
    SQ_A3, SQ_B3, SQ_C3, SQ_D3, SQ_E3, SQ_F3, SQ_G3, SQ_H3,
    SQ_A4, SQ_B4, SQ_C4, SQ_D4, SQ_E4, SQ_F4, SQ_G4, SQ_H4,
    SQ_A5, SQ_B5, SQ_C5, SQ_D5, SQ_E5, SQ_F5, SQ_G5, SQ_H5,
    SQ_A6, SQ_B6, SQ_C6, SQ_D6, SQ_E6, SQ_F6, SQ_G6, SQ_H6,
    SQ_A7, SQ_B7, SQ_C7, SQ_D7, SQ_E7, SQ_F7, SQ_G7, SQ_H7,
    SQ_A8, SQ_B8, SQ_C8, SQ_D8, SQ_E8, SQ_F8, SQ_G8, SQ_H8,

    SQ_None = 64
};

[kbhearn]

the classical approach gerd linked is not so slow as to be the biggest problem your beginning program will have and since it shares the same function prototype (a square and an occupied bitboard as parameters), at the point when you have to worry about the speedup changing it just involves changing that function, not the rest of the code.

[Sven]

Is there a way to test the precomputed magics? [...]

Code: Select all

inline U64 bishopAttacks(U64 occ, Square sq) {
   U64* aptr = bishopTbl[sq].ptr;
   occ      &= bishopTbl[sq].mask;
   occ      *= bishopTbl[sq].magic;
   occ     >>= bishopTbl[sq].shift;
   return aptr[occ];
}
 
inline U64 rookAttacks(U64 occ, Square sq) {
   U64* aptr = rookTbl[sq].ptr;
   occ      &= rookTbl[sq].mask;
   occ      *= rookTbl[sq].magic;
   occ     >>= rookTbl[sq].shift;
   return aptr[occ];
}

Could you please have look over my code and give me a hint how I can best find the error?

I would add assertions into the code above to ensure that all involved values are inside the allowed ranges. Test 'sq', 'shift', 'aptr', and 'occ' (after shifting) at least. In most cases 'shift' should be between (64-5) and (64-9) for bishops and between (64-10) and (64-12) for rooks.

This is kind of a late test of your initialization code so of course it would be even better to put assertions there directly.

The generated magic numbers themselves will most probably be correct since you have obviously written generation code similar to the one described on the CPW page to which you linked above, and that code contains a test whether the magic number "works" for the given square (in fact this is part of the algorithm). But your other code that maintains all the data could still have a problem.

[Sven]

My current guess is that there is indeed something wrong with your generated magic numbers. This part of the original generator code from Tord Romstad (in function find_magic()):

Code: Select all

    for&#40;i = 0; i < 4096; i++) used&#91;i&#93; = 0ULL;
    for&#40;i = 0, fail = 0; !fail && i < &#40;1 << n&#41;; i++) &#123;
      j = transform&#40;b&#91;i&#93;, magic, m&#41;;
      if&#40;used&#91;j&#93; == 0ULL&#41; used&#91;j&#93; = a&#91;i&#93;;
      else if&#40;used&#91;j&#93; != a&#91;i&#93;) fail = 1;
    &#125;
    if&#40;!fail&#41; return magic;

does the check that I mentioned above. If you have not implemented such a check, or if there is some error in your implementation of it, then it can cause the effect that you see. The check ensures that the mapping of each occupancy to the corresponding "occupancy index" ("j", or "occ" in the using code) is unique.

[Gerd Isenberg]

OK, occupancy index 0 should be fine for all squares, attacks on the otherwise empty board. But 484 contains the wrong attack for that occupancy from d4! Why? What happens during initialization?

Code: Select all

uint64 find_magic(int sq, int m, int bishop) {
  uint64 mask, b[4096], a[4096], used[4096], magic;
  int i, j, k, n, fail;
 
  mask = bishop? bmask(sq) : rmask(sq);
  n = count_1s(mask);
 
  for&#40;i = 0; i < &#40;1 << n&#41;; i++) &#123;
    b&#91;i&#93; = index_to_uint64&#40;i, n, mask&#41;;
    a&#91;i&#93; = bishop? batt&#40;sq, b&#91;i&#93;) &#58; ratt&#40;sq, b&#91;i&#93;);
  &#125;
  for&#40;k = 0; k < 100000000; k++) &#123;
    magic = random_uint64_fewbits&#40;);
    if&#40;count_1s&#40;&#40;mask * magic&#41; & 0xFF00000000000000ULL&#41; < 6&#41; continue;
    for&#40;i = 0; i < 4096; i++) used&#91;i&#93; = 0ULL;
    for&#40;i = 0, fail = 0; !fail && i < &#40;1 << n&#41;; i++) &#123;
      j = transform&#40;b&#91;i&#93;, magic, m&#41;;
      if&#40;used&#91;j&#93; == 0ULL&#41; used&#91;j&#93; = a&#91;i&#93;;
      else if&#40;used&#91;j&#93; != a&#91;i&#93;) fail = 1;
#if _DEBUG
      if ( !fail && bishop && sq == SQ_D4 && j == 484 )
         printBitboard&#40;a&#91;i&#93;); // is this the right attack set?
#endif
    &#125;
    if&#40;!fail&#41; return magic;
  &#125;
  printf&#40;"***Failed***\n");
  return 0ULL;
&#125;

[The_Algebraist]

Thank you for your great help Gerd, Sven and Kevin!

Gerd: I can't exactly tell what happens during initialization, because I precomputed the magics, and when I recompute them, they change.

That is another learning point I took from this, when I implement the magics the next time, I won't precompute them but generate them on startup. Then I can just have a constant seed and will end up with the same magics every time.


I followed the advice and implemented the classical approach for now. It works very good, but I still need to implement castling until I can start Perft-testing and see how it does in respect to performance .

But these magic bitboards keep sticking in my head!

I thought about it some more and will definitely come back and try to implement it again, better sooner than later.

One question I came up with when thinking about it:

In the article: http://chessprogramming.wikispaces.com/ ... for+Magics
I think I understand most of the algorithm that is suggested. But one thing is unclear to me, what is the point of this function:

Code: Select all

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for&#40;i = 0; i < bits; i++) &#123;
    j = pop_1st_bit&#40;&m&#41;;
    if&#40;index & &#40;1 << i&#41;) result |= &#40;1ULL << j&#41;;
  &#125;
  return result;
&#125;

It is called here:

Code: Select all

uint64 find_magic(int sq, int m, int bishop) {
  uint64 mask, b[4096], a[4096], used[4096], magic;
  int i, j, k, n, fail;
 
  mask = bishop? bmask(sq) : rmask(sq);
  n = count_1s(mask);
 
  for&#40;i = 0; i < &#40;1 << n&#41;; i++) &#123;
    b&#91;i&#93; = index_to_uint64&#40;i, n, mask&#41;;
    a&#91;i&#93; = bishop? batt&#40;sq, b&#91;i&#93;) &#58; ratt&#40;sq, b&#91;i&#93;);
  &#125;
  for&#40;k = 0; k < 100000000; k++) &#123;
    magic = random_uint64_fewbits&#40;);
    if&#40;count_1s&#40;&#40;mask * magic&#41; & 0xFF00000000000000ULL&#41; < 6&#41; continue;
    for&#40;i = 0; i < 4096; i++) used&#91;i&#93; = 0ULL;
    for&#40;i = 0, fail = 0; !fail && i < &#40;1 << n&#41;; i++) &#123;
      j = transform&#40;b&#91;i&#93;, magic, m&#41;;
      if&#40;used&#91;j&#93; == 0ULL&#41; used&#91;j&#93; = a&#91;i&#93;;
      else if&#40;used&#91;j&#93; != a&#91;i&#93;) fail = 1;
    &#125;
    if&#40;!fail&#41; return magic;
  &#125;
  printf&#40;"***Failed***\n");
  return 0ULL;
&#125;

and I assume describes the blockers. Anyways I don't quite understand how the function 'index_to_uint64' is connected with the computation of the blockers or the rest of the algorithm?

[Sven]

One question I came up with when thinking about it:

In the article: http://chessprogramming.wikispaces.com/ ... for+Magics
I think I understand most of the algorithm that is suggested. But one thing is unclear to me, what is the point of this function:

Code: Select all

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for&#40;i = 0; i < bits; i++) &#123;
    j = pop_1st_bit&#40;&m&#41;;
    if&#40;index & &#40;1 << i&#41;) result |= &#40;1ULL << j&#41;;
  &#125;
  return result;
&#125;

It is called here:

Code: Select all

uint64 find_magic(int sq, int m, int bishop) {
  uint64 mask, b[4096], a[4096], used[4096], magic;
  int i, j, k, n, fail;
 
  mask = bishop? bmask(sq) : rmask(sq);
  n = count_1s(mask);
 
  for&#40;i = 0; i < &#40;1 << n&#41;; i++) &#123;
    b&#91;i&#93; = index_to_uint64&#40;i, n, mask&#41;;
    a&#91;i&#93; = bishop? batt&#40;sq, b&#91;i&#93;) &#58; ratt&#40;sq, b&#91;i&#93;);
  &#125;
  for&#40;k = 0; k < 100000000; k++) &#123;
    magic = random_uint64_fewbits&#40;);
    if&#40;count_1s&#40;&#40;mask * magic&#41; & 0xFF00000000000000ULL&#41; < 6&#41; continue;
    for&#40;i = 0; i < 4096; i++) used&#91;i&#93; = 0ULL;
    for&#40;i = 0, fail = 0; !fail && i < &#40;1 << n&#41;; i++) &#123;
      j = transform&#40;b&#91;i&#93;, magic, m&#41;;
      if&#40;used&#91;j&#93; == 0ULL&#41; used&#91;j&#93; = a&#91;i&#93;;
      else if&#40;used&#91;j&#93; != a&#91;i&#93;) fail = 1;
    &#125;
    if&#40;!fail&#41; return magic;
  &#125;
  printf&#40;"***Failed***\n");
  return 0ULL;
&#125;

and I assume describes the blockers. Anyways I don't quite understand how the function 'index_to_uint64' is connected with the computation of the blockers or the rest of the algorithm?

index_to_uint64() calculates the "blockers". For a given square and piece type (bishop/rook) there may be two or more different occupancies sharing the same set of blockers. E.g. a bishop on d1 does not attack g4 if there is a piece on e2, regardless whether f3 is occupied as well or not. Same blockers must imply same attack set. The check that is built-in into the generation algorithm verifies that the current magic number fulfills this last condition by checking that the transformation (i.e., magic multiplication + shift) of the obtained "blockers" bitboard returns a unique attack set index. If this is not the case then the current magic number is rejected.

[Gerd Isenberg]

Ok, first there are n = 5..12 relevant occupancy bits pers square for bishops / rooks, thus 2^n (1 << n), max 4096 possible relevant occupancy states. The first step per square in Tord's find magic routine is to initialize the b[] and a[] arrays with all possible occupancies (b[]) and slowly computed attacks (a[], batt, ratt) by square and occupancy b.

Code: Select all

  mask = bishop? bmask(sq) : rmask(sq);
  n = count_1s(mask);
 
  for&#40;i = 0; i < &#40;1 << n&#41;; i++) &#123;
    b&#91;i&#93; = index_to_uint64&#40;i, n, mask&#41;;
    a&#91;i&#93; = bishop? batt&#40;sq, b&#91;i&#93;) &#58; ratt&#40;sq, b&#91;i&#93;);
  &#125;

index_to_uint64 (may be a better name is index_to_occupancy) is responsible to compute all occupancies for that square by mask, and n (popcnt of mask), and an enumerator index, from 0 to 2^n -1.

Code: Select all

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for&#40;i = 0; i < bits; i++) &#123;
    j = pop_1st_bit&#40;&m&#41;;
    if&#40;index & &#40;1 << i&#41;) result |= &#40;1ULL << j&#41;;
  &#125;
  return result;
&#125;

The routine starts with occupancy result of zero.

Code: Select all

  uint64 result = 0ULL;

And loops over all possible occupancy bits (5 ... 12) ...

Code: Select all

  for&#40;i = 0; i < bits; i++) &#123;

and gets the next set bit-index from the mask (bitscan forward with reset)

Code: Select all

    j = pop_1st_bit(&m);

It then sets the corresponding bit (2^j, 1 << j) inside the result, if the index (0..2^n-1, max 4095) has bit i set.

Code: Select all

    if&#40;index & &#40;1 << i&#41;) result |= &#40;1ULL << j&#41;;

This is how all possible occupancies are computed by all possible indices. Note that there are far less attack sets than occupancies, since bits behind the first blocker don't affect the attacks. Thus, while all b are different, many a are equal for different i.

===

The next step is to find a magic factor, chosen randomly by trial and error (up to 100000000 trials).

Code: Select all

  for&#40;k = 0; k < 100000000; k++) &#123;
    magic = random_uint64_fewbits&#40;);

The next line is some empirical optimization (I guess), since it turned out that "good" magics to try require at least six bit set in the upper byte of a 64-bit product:

Code: Select all

    if&#40;count_1s&#40;&#40;mask * magic&#41; & 0xFF00000000000000ULL&#41; < 6&#41; continue;

The used[] is cleared to check for collisions ...

Code: Select all

    for&#40;i = 0; i < 4096; i++) used&#91;i&#93; = 0ULL;

Looping over all occupancies again so long there is no destructive collission ...

Code: Select all

    for&#40;i = 0, fail = 0; !fail && i < &#40;1 << n&#41;; i++) &#123;

calculate the occupancy index, using precalculated b[] again (see above) ...

Code: Select all

      j = transform(b[i], magic, m);

if not used yet, store attacks

Code: Select all

      if(used[j] == 0ULL) used[j] = a[i];

if used, we have a collission, but may be a (desired) constructive one, if different occupancies share same attacks due to different occupancy bits "behind" first blocker. That is why we store attacks in used, and magic only fails, if attacks are different too.

Code: Select all

      else if(used[j] != a[i]) fail = 1;

otherwise we have found a destructive collission free magic factor ...

Code: Select all

    if(!fail) return magic;

And yes, you can compute the magics on the fly while startup ...

[Sven]

One question I came up with when thinking about it:

In the article: http://chessprogramming.wikispaces.com/ ... for+Magics
I think I understand most of the algorithm that is suggested. But one thing is unclear to me, what is the point of this function:

Code: Select all

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for&#40;i = 0; i < bits; i++) &#123;
    j = pop_1st_bit&#40;&m&#41;;
    if&#40;index & &#40;1 << i&#41;) result |= &#40;1ULL << j&#41;;
  &#125;
  return result;
&#125;

It is called here:

Code: Select all

uint64 find_magic(int sq, int m, int bishop) {
  uint64 mask, b[4096], a[4096], used[4096], magic;
  int i, j, k, n, fail;
 
  mask = bishop? bmask(sq) : rmask(sq);
  n = count_1s(mask);
 
  for&#40;i = 0; i < &#40;1 << n&#41;; i++) &#123;
    b&#91;i&#93; = index_to_uint64&#40;i, n, mask&#41;;
    a&#91;i&#93; = bishop? batt&#40;sq, b&#91;i&#93;) &#58; ratt&#40;sq, b&#91;i&#93;);
  &#125;
  for&#40;k = 0; k < 100000000; k++) &#123;
    magic = random_uint64_fewbits&#40;);
    if&#40;count_1s&#40;&#40;mask * magic&#41; & 0xFF00000000000000ULL&#41; < 6&#41; continue;
    for&#40;i = 0; i < 4096; i++) used&#91;i&#93; = 0ULL;
    for&#40;i = 0, fail = 0; !fail && i < &#40;1 << n&#41;; i++) &#123;
      j = transform&#40;b&#91;i&#93;, magic, m&#41;;
      if&#40;used&#91;j&#93; == 0ULL&#41; used&#91;j&#93; = a&#91;i&#93;;
      else if&#40;used&#91;j&#93; != a&#91;i&#93;) fail = 1;
    &#125;
    if&#40;!fail&#41; return magic;
  &#125;
  printf&#40;"***Failed***\n");
  return 0ULL;
&#125;

and I assume describes the blockers. Anyways I don't quite understand how the function 'index_to_uint64' is connected with the computation of the blockers or the rest of the algorithm?

index_to_uint64() calculates the "blockers". For a given square and piece type (bishop/rook) there may be two or more different occupancies sharing the same set of blockers. E.g. a bishop on d1 does not attack g4 if there is a piece on e2, regardless whether f3 is occupied as well or not. Same blockers must imply same attack set. The check that is built-in into the generation algorithm verifies that the current magic number fulfills this last condition by checking that the transformation (i.e., magic multiplication + shift) of the obtained "blockers" bitboard returns a unique attack set index. If this is not the case then the current magic number is rejected.

Sorry, I got something wrong, forget this post above, please. Gerd is right, b[] is the occupancy bitboard, not the "blockers" bitboard. Therefore I also deleted my short reply to Gerd's post which had been visible for a while.

So a better wording would be:

index_to_uint64() calculates the occupancy bitboard. The check that is built-in into the generation algorithm verifies that the current magic number fulfills the condition that the transformation (i.e., magic multiplication + shift) of the occupancy bitboard returns a unique attack set index. If this is not the case then the current magic number is rejected.