Finding special magic numbers

[gxchess1]

For a Knight it would be even easier,: the magic multiplier 0x0000080200002020ull would map each bit to the upper byte, without contaminating any of those:

Code: Select all

00000e00 0f0000g0 h0000000 00000000 000000a0 b0000c00 0d000000 00000000 (moves for knight at LSB)
e000f000 0g0h0000 00000000 00000000 0a0b0000 c000d000 00000000 00000000 (<< 5)
0g0h0000 00000000 00000000 0a0b0000 c000d000 00000000 00000000 00000000 (<< 13)
00000a0b 0000c000 d0000000 00000000 00000000 00000000 00000000 00000000 (<< 33)
00c000d0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 (<< 43)
____________________________________________________________________ +
egchfadb ??0hcg? ?0000000 ...

Sorry but I still don't understand. So am I correct by saying your idea is using the magic number to getting an 8-bit index into a database into which we will index and get the correct 8-bit mask?

[hgm]

Yes, that is correct.

[gxchess1]

Yes, that is correct.

But then for example the bitboard 0x0000000000000302 and square A1 would have the same 'index' as 0x0000000000060400 and square B2.

Or am I missing something? I think you are up to something.

[dangi12012]

What do you mean by parallel hash them on all cores into increasing buffers of power 2?
Thanks

Same way the slider magics were derived:

You want to find 64 magic numbers that have this property:

Code: Select all

Movelist[32768] //no overlaps like fancy magic since a movelist also contains extra information about the moves (from square etc.)
int movelist_index = offset[square] + (magic[square] * attacks) >> 56;

Movelist will contain all your moves.

So what you do is look at squares 0..63 independently - and enumerate all possible attack configurations (by bitscattering).
You will have a maximum of 512 uint64_t per square that need to be condensed with above formula.

It may be impossible to find a candidate for squares that do that so you need to go to 1024 per square.
Generally finding a magic number is pretty easy.

Code: Select all

uint64_t candidate = random() & random() & random();
int* slots = new int[512]();
for(auto config : configurations) //configurations is all 2^8 possibilities for the king attacks of a particular square
{
    int index = (candidate  * config) >> 56;
    if (slots[index] != 0) break;
    else slots[index] = 1;
}
//Clear slots and retry with a new candidate until this square is solved. Repeat for all 64 squares. You get 64 magics 

For this it would be overkill but I recommend two tricks. Using an ultra fast random number generator + doing this search in parallel.
For sliders these 64 tables are also offset into each other in a way that many intersections are produced but that is not possible or needed when indexing into a movelist.
Also the random() & random() & random() is not a typo - you expect on average to find a certain bitpattern which can be predicted somewhat.

I am wondering why no one has not posted the solution yet. If thats not the case I can post it wednesday. I am sick currently.

[dangi12012]

KingAttacks (not the solution)

Code: Select all

static constexpr uint64_t KingAttacks[] = {
0x0000000000000302, 0x0000000000000705, 0x0000000000000E0A, 0x0000000000001C14, 0x0000000000003828, 0x0000000000007050, 0x000000000000E0A0, 0x000000000000C040,
0x0000000000030203, 0x0000000000070507, 0x00000000000E0A0E, 0x00000000001C141C, 0x0000000000382838, 0x0000000000705070, 0x0000000000E0A0E0, 0x0000000000C040C0,
0x0000000003020300, 0x0000000007050700, 0x000000000E0A0E00, 0x000000001C141C00, 0x0000000038283800, 0x0000000070507000, 0x00000000E0A0E000, 0x00000000C040C000,
0x0000000302030000, 0x0000000705070000, 0x0000000E0A0E0000, 0x0000001C141C0000, 0x0000003828380000, 0x0000007050700000, 0x000000E0A0E00000, 0x000000C040C00000,
0x0000030203000000, 0x0000070507000000, 0x00000E0A0E000000, 0x00001C141C000000, 0x0000382838000000, 0x0000705070000000, 0x0000E0A0E0000000, 0x0000C040C0000000,
0x0003020300000000, 0x0007050700000000, 0x000E0A0E00000000, 0x001C141C00000000, 0x0038283800000000, 0x0070507000000000, 0x00E0A0E000000000, 0x00C040C000000000,
0x0302030000000000, 0x0705070000000000, 0x0E0A0E0000000000, 0x1C141C0000000000, 0x3828380000000000, 0x7050700000000000, 0xE0A0E00000000000, 0xC040C00000000000,
0x0203000000000000, 0x0507000000000000, 0x0A0E000000000000, 0x141C000000000000, 0x2838000000000000, 0x5070000000000000, 0xA0E0000000000000, 0x40C0000000000000,
};

Code: Select all

uint64_t moves = KingAttacks[square] & ~SeenByEnemy & EnemyOrEmpty;
//Todo: Hash into index

Aaaah you know what? I see i never did this because I condensed all possible moves into a uniform buffer. So sliders and knights and kings are hashed with the same number.
No seperate king magic - BUT: all pieces get the same magic but differing offsets. Has the advantage of keeping everything in cache + only one codepath for all pieces.

[hgm]

Yes, that is correct.

But then for example the bitboard 0x0000000000000302 and square A1 would have the same 'index' as 0x0000000000060400 and square B2.

Sure, but that is how magics work. They have the same index, but the index is used in a different table. Each square should have its own table. What is in the table already makes this necessary: a table containing King moves from g7 would not contain anything useful for a King on b2.

[Chessnut1071]

Yes, that is correct.

But then for example the bitboard 0x0000000000000302 and square A1 would have the same 'index' as 0x0000000000060400 and square B2.

Sure, but that is how magics work. They have the same index, but the index is used in a different table. Each square should have its own table. What is in the table already makes this necessary: a table containing King moves from g7 would not contain anything useful for a King on b2.

Trying to follow this objective is causing my head to ache. Here's what I don't understand: even if you find the perfect magic numbers and can generate all the moves simultaneously, don't you still have to take the positional information-me 16-variables-asynchronously? If so, where's the benefit?

[dangi12012]

Trying to follow this objective is causing my head to ache. Here's what I don't understand: even if you find the perfect magic numbers and can generate all the moves simultaneously, don't you still have to take the positional information-me 16-variables-asynchronously? If so, where's the benefit?

With hashing into a Bitboards intersections are okay. With hashing into the movelists it is not. Magics are the seed for the hash function and "hashing" is the evaluation of it.

You don't need to generate 16 variables on the fly - the movelist already contains the info. If you need to differentiate taking moves from silent ones this can be achieved too by hashing atk & enemy and atk &~enemy.
Zero will hash into an index to an empty movelist

[gxchess1]

Trying to follow this objective is causing my head to ache. Here's what I don't understand: even if you find the perfect magic numbers and can generate all the moves simultaneously, don't you still have to take the positional information-me 16-variables-asynchronously? If so, where's the benefit?

With hashing into a Bitboards intersections are okay. With hashing into the movelists it is not. Magics are the seed for the hash function and "hashing" is the evaluation of it.

You don't need to generate 16 variables on the fly - the movelist already contains the info. If you need to differentiate taking moves from silent ones this can be achieved too by hashing atk & enemy and atk &~enemy.
Zero will hash into an index to an empty movelist

I can't seem to generate the numbers. I tried the fastest generator I could find, 3 of those so the CPU can generate in parallel, still nothing.

[WinPooh]

GreKo has its own magic numbers generator. See functions starting with Find- in file bitboards.cpp (FindMultB, FindMaskR etc.).
Generation was pretty fast, as I remember - less than 1 min. for the whole board set.
I hope this can be useful to someone.