Black magic bitboards

[Volker Annuss]

In my engines I use magic bitboards with a fixed shift of 12 bits for rooks and 9 bits for bishops. The lookup tables for each square have many unused entries. To save space, they are all combined overlapping in one big table. So the lookup tables for one square can use the unused entries of the lookup table from other squares.

Normal (white) magic bitboards work like

Code: Select all

index = ((occ & mask) * magic) >> (64-n);

Black magic bitboards work like

Code: Select all

index = ((occ | black_mask) * black_magic) >> (64-n);

with black_mask == ~mask . The mask is inverted and ored with the occupied squares turning the unused bits to the name giving black ;-)

With black magics there is always something nonzero to multiply with, which has two advantages for getting more compact lookup tables than with white magics.
- It is easy to see, that with white magics index == 0 is always used for the empty board. Black magics make it possible to get lookup tables with unused entries at the beginning.
- More bits from the magic factor contribute to the calculated index, giving more magic factors to chose from.

Here the best black magics so far. I think there are still some bytes to squeeze out. The position field is where to place index == 0 for that factor in the global lookup_table. This may be an unused entry.

Code: Select all

uint64_t lookup_table[88507];

struct
{
	uint64_t factor;
	int position;
}
bishop_magics[64] =
{
	{ 0x107ac08050500bffull,  66157 },
	{ 0x7fffdfdfd823fffdull,  71730 },
	{ 0x0400c00fe8000200ull,  37781 },
	{ 0x103f802004000000ull,  21015 },
	{ 0xc03fe00100000000ull,  47590 },
	{ 0x24c00bffff400000ull,    835 },
	{ 0x0808101f40007f04ull,  23592 },
	{ 0x100808201ec00080ull,  30599 },
	{ 0xffa2feffbfefb7ffull,  68776 },
	{ 0x083e3ee040080801ull,  19959 },
	{ 0x040180bff7e80080ull,  21783 },
	{ 0x0440007fe0031000ull,  64836 },
	{ 0x2010007ffc000000ull,  23417 },
	{ 0x1079ffe000ff8000ull,  66724 },
	{ 0x7f83ffdfc03fff80ull,  74542 },
	{ 0x080614080fa00040ull,  67266 },
	{ 0x7ffe7fff817fcff9ull,  26575 },
	{ 0x7ffebfffa01027fdull,  67543 },
	{ 0x20018000c00f3c01ull,  24409 },
	{ 0x407e0001000ffb8aull,  30779 },
	{ 0x201fe000fff80010ull,  17384 },
	{ 0xffdfefffde39ffefull,  18778 },
	{ 0x7ffff800203fbfffull,  65109 },
	{ 0x7ff7fbfff8203fffull,  20184 },
	{ 0x000000fe04004070ull,  38240 },
	{ 0x7fff7f9fffc0eff9ull,  16459 },
	{ 0x7ffeff7f7f01f7fdull,  17432 },
	{ 0x3f6efbbf9efbffffull,  81040 },
	{ 0x0410008f01003ffdull,  84946 },
	{ 0x20002038001c8010ull,  18276 },
	{ 0x087ff038000fc001ull,   8512 },
	{ 0x00080c0c00083007ull,  78544 },
	{ 0x00000080fc82c040ull,  19974 },
	{ 0x000000407e416020ull,  23850 },
	{ 0x00600203f8008020ull,  11056 },
	{ 0xd003fefe04404080ull,  68019 },
	{ 0x100020801800304aull,  85965 },
	{ 0x7fbffe700bffe800ull,  80524 },
	{ 0x107ff00fe4000f90ull,  38221 },
	{ 0x7f8fffcff1d007f8ull,  64647 },
	{ 0x0000004100f88080ull,  61320 },
	{ 0x00000020807c4040ull,  67281 },
	{ 0x00000041018700c0ull,  79076 },
	{ 0x0010000080fc4080ull,  17115 },
	{ 0x1000003c80180030ull,  50718 },
	{ 0x2006001cf00c0018ull,  24659 },
	{ 0xffffffbfeff80fdcull,  38291 },
	{ 0x000000101003f812ull,  30605 },
	{ 0x0800001f40808200ull,  37759 },
	{ 0x084000101f3fd208ull,   4639 },
	{ 0x080000000f808081ull,  21759 },
	{ 0x0004000008003f80ull,  67799 },
	{ 0x08000001001fe040ull,  22841 },
	{ 0x085f7d8000200a00ull,  66689 },
	{ 0xfffffeffbfeff81dull,  62548 },
	{ 0xffbfffefefdff70full,  66597 },
	{ 0x100000101ec10082ull,  86749 },
	{ 0x7fbaffffefe0c02full,  69558 },
	{ 0x7f83fffffff07f7full,  61589 },
	{ 0xfff1fffffff7ffc1ull,  62533 },
	{ 0x0878040000ffe01full,  64387 },
	{ 0x005d00000120200aull,  26581 },
	{ 0x0840800080200fdaull,  76355 },
	{ 0x100000c05f582008ull,  11140 }
},

rook_magics[64] =
{
	{ 0x80280013ff84ffffull,  10890 },
	{ 0x5ffbfefdfef67fffull,  56054 },
	{ 0xffeffaffeffdffffull,  67495 },
	{ 0x003000900300008aull,  72797 },
	{ 0x0030018003500030ull,  17179 },
	{ 0x0020012120a00020ull,  63978 },
	{ 0x0030006000c00030ull,  56650 },
	{ 0xffa8008dff09fff8ull,  15929 },
	{ 0x7fbff7fbfbeafffcull,  55905 },
	{ 0x0000140081050002ull,  26301 },
	{ 0x0000180043800048ull,  78100 },
	{ 0x7fffe800021fffb8ull,  86245 },
	{ 0xffffcffe7fcfffafull,  75228 },
	{ 0x00001800c0180060ull,  31661 },
	{ 0xffffe7ff8fbfffe8ull,  38053 },
	{ 0x0000180030620018ull,  37433 },
	{ 0x00300018010c0003ull,  74747 },
	{ 0x0003000c0085ffffull,  53847 },
	{ 0xfffdfff7fbfefff7ull,  70952 },
	{ 0x7fc1ffdffc001fffull,  49447 },
	{ 0xfffeffdffdffdfffull,  62629 },
	{ 0x7c108007befff81full,  58996 },
	{ 0x20408007bfe00810ull,  36009 },
	{ 0x0400800558604100ull,  21230 },
	{ 0x0040200010080008ull,  51882 },
	{ 0x0010020008040004ull,  11841 },
	{ 0xfffdfefff7fbfff7ull,  25794 },
	{ 0xfebf7dfff8fefff9ull,  49689 },
	{ 0xc00000ffe001ffe0ull,  63400 },
	{ 0x2008208007004007ull,  33958 },
	{ 0xbffbfafffb683f7full,  21991 },
	{ 0x0807f67ffa102040ull,  45618 },
	{ 0x200008e800300030ull,  70134 },
	{ 0x0000008780180018ull,  75944 },
	{ 0x0000010300180018ull,  68392 },
	{ 0x4000008180180018ull,  66472 },
	{ 0x008080310005fffaull,  23236 },
	{ 0x4000188100060006ull,  19067 },
	{ 0xffffff7fffbfbfffull,      0 },
	{ 0x0000802000200040ull,  43566 },
	{ 0x20000202ec002800ull,  29810 },
	{ 0xfffff9ff7cfff3ffull,  65558 },
	{ 0x000000404b801800ull,  77684 },
	{ 0x2000002fe03fd000ull,  73350 },
	{ 0xffffff6ffe7fcffdull,  61765 },
	{ 0xbff7efffbfc00fffull,  49282 },
	{ 0x000000100800a804ull,  78840 },
	{ 0xfffbffefa7ffa7feull,  82904 },
	{ 0x0000052800140028ull,  24594 },
	{ 0x00000085008a0014ull,   9513 },
	{ 0x8000002b00408028ull,  29012 },
	{ 0x4000002040790028ull,  27684 },
	{ 0x7800002010288028ull,  27901 },
	{ 0x0000001800e08018ull,  61477 },
	{ 0x1890000810580050ull,  25719 },
	{ 0x2003d80000500028ull,  50020 },
	{ 0xfffff37eefefdfbeull,  41547 },
	{ 0x40000280090013c1ull,   4750 },
	{ 0xbf7ffeffbffaf71full,   6014 },
	{ 0xfffdffff777b7d6eull,  41529 },
	{ 0xeeffffeff0080bfeull,  84192 },
	{ 0xafe0000fff780402ull,  33433 },
	{ 0xee73fffbffbb77feull,   8555 },
	{ 0x0002000308482882ull,   1009 }
};

[Gerd Isenberg]

Very interesting Volker, thanks for sharing. But I don't understand what is superior with black magics?!

Since the difference between (occ | ~mask ) and (occ & mask) is ~mask, and

Code: Select all

index = ( (occ | ~mask)          * magic) >> (64-n);
      = (((occ &  mask) + ~mask) * magic) >> (64-n);

... so basically compared to white magics

Code: Select all

index = ( (occ &  mask)          * magic) >> (64-n);

... you add a constant (per square) to a factor, or factored out, to the product

Code: Select all

      = ( (occ &  mask)          * magic   + ~mask * magic ) >> (64-n);
      = ( (occ &  mask)          * magic   + C ) >> (64-n);

So I don't understand what is different whether you have index == 0 or index == c for the empty board, beside other offsets for the overlapping square arrays anyway? Also I don't understand why you have more magic factors to chose from!?

[Volker Annuss]

Also I don't understand why you have more magic factors to chose from!?

I was wrong with this. I verified that the hit rate for testing random numbers for beeing black or white magics is about the same. Nevertheless black magics give more compact lookup tables than white ones. I'll give more details tomorrow.

[BeyondCritics]

So I don't understand what is different whether you have index == 0 or index == c for the empty board, beside other offsets for the overlapping square arrays anyway?

The higher 64-n Bits of the constant C==~mask * magic are certainly insignificant, in the sense that they don't change the set of colliding indices {(occ_i,occ_j) | 0<=i<j}. But the lower n bits could make a difference, i believe.
To be precise, do you know, if for a given parameter magic, there is a corresponding parameter magic', so that you would replace black magic hashing and parameter magic with magic hashing and parameter magic'?
I fail to see that. Black magic is just a different formula.

[AlvaroBegue]

Let's see. The difference between (occ & mask) and (occ & ~mask) is precisely ~mask. So the traditional formula is `(occ & mask) * magic' and the new one is `((occ & mask) + Constant) * black_magic'. I believe any magic multiplier will work as a black_magic multiplier and vice versa.

So there is virtually no difference with the traditional magics, as far as I can tell.

[BeyondCritics]

Let's see. The difference between (occ & mask) and (occ & ~mask) is precisely ~mask. So the traditional formula is `(occ & mask) * magic' and the new one is `((occ & mask) + Constant) * black_magic'. I believe any magic multiplier will work as a black_magic multiplier and vice versa.

So there is virtually no difference with the traditional magics, as far as I can tell.

You are using the wrong formula. Magic hashing is 'occ & mask * magic >> 64-n' and black magic hashing is `((occ & mask) + Constant) * black_magic >> 64-n'
This difference is significant. Here is an worked example. Let magic = 1 and assume that occ & mask == Constant == 1 << (64-n-1). Then
(occ & mask) * magic >> 64-n == 0, but
((occ & mask) + Constant) * black_magic == 1.
Hence not any magic multiplier will work as a black_magic multiplier.

[AlvaroBegue]

Let's see. The difference between (occ & mask) and (occ & ~mask) is precisely ~mask. So the traditional formula is `(occ & mask) * magic' and the new one is `((occ & mask) + Constant) * black_magic'. I believe any magic multiplier will work as a black_magic multiplier and vice versa.

So there is virtually no difference with the traditional magics, as far as I can tell.

You are using the wrong formula. Magic hashing is 'occ & mask * magic >> 64-n' and black magic hashing is `((occ & mask) + Constant) * black_magic >> 64-n'
This difference is significant. Here is an worked example. Let magic = 1 and assume that occ & mask == Constant == 1 << (64-n-1). Then
(occ & mask) * magic >> 64-n == 0, but
((occ & mask) + Constant) * black_magic == 1.
Hence not any magic multiplier will work as a black_magic multiplier.

I understand you only care about the highest n bits. There might be some issue with exactly how adding a constant affects the highest-order bits, but that can't change things very much.

Let me make a statement that I can prove.

Old formula: ((occ & mask) * magic) >> (64 - n)

New formula is equivalent to: ((occ & mask) * magic + (~mask) * magic) >> (64 - n)

The difference between the two formulas can be seen as adding some constant before extracting the top n bits. I am not saying that you will get the same bits out, but the new formula is going to in general be no more powerful than the old one in producing different values in the top n bits. To the extent that the constant being added might change the carry bit from the lower bits, it might not exactly be true that the same magic multipliers will work, but it's going to be close.

Anyway, do you have any concrete case where your black magics work better than traditional magics?

[BeyondCritics]

No, i have no examples. It is up to the inventor, to show that his invention gives any real benefit.
I agree, from the outside it looks not very different, but that was not my point here.

[AlvaroBegue]

No, i have no examples. It is up to the inventor, to show that his invention gives any real benefit.
I agree, from the outside it looks not very different, but that was not my point here.

Sorry, I didn't word that correctly. I meant to ask if any examples were known, not specifically from you. My bad.

[BeyondCritics]

Volker has promised to discuss more details soon:
http://www.talkchess.com/forum/viewtopi ... 99&t=64790