Finding special magic numbers

[gxchess1]

Hey, I want to try to improve my move generation speed by generating all moves from a picec in a bulk with SIMD instead of loops. What I need to do is map attacks a piece can make to low-order bits (just like magic bitboards and the pext operation). For example, the full set of king attacks in E5 would be (D4, E4, F4, D5, F5, D6, E6, F6) but let's say because some pieces of the same colour the king can only go to a subset of (D6, E6, F6). What I would like to happen is to make a fast function to return me 0b00000111 (like _pext_u64(subset, full_attacks) would return).

However, my cpu has very slow PEXT / PDEP and I would like to use magic numbers to generate the mask. Here is my humble try:

Code: Select all

static uint64_t use_magic(Bitboard bb, uint64_t factor, unsigned bits) {
    return (uint64_t(bb) * factor) >> (64 - bits);
}

[[gnu::hot, gnu::flatten]]
static uint64_t FindKingMagic(Random128& rand, Square sq) {
    const Bitboard attacks = KingAttacks[sq];

    for (;;) {
        const uint64_t factor = rand();
        Bitboard perm = 0;
        unsigned low_mask = 0;
        bool ok = true;
        do {
            if (use_magic(perm, factor, 8) != low_mask) {
                ok = false;
                break;
            }
	    // goes through every 8-bit mask permutation
            ++low_mask;
          // goes through every bitboard permutation
        } while ((perm = perm.permute(attacks)));

        if (ok) {
            return factor;
        }
    }
}

Basically, I generate a random number and endlessly hope that it maps all permutations of the king attacks to the correct 8-bit mask. However, it never returns because probably such number would take years to find.

Does anyone what I can do to find such numbers for each square (A1 to H8)?

[hgm]

Why on earth would you want to do that? The trick of deriving an index from the relevant part of the board occupancy for sliders, to use for a lookup of the moves, is only needed because there is a non-trivial relation between the occupied squares and the blocked moves. For leapers that relation is trivial: if it is occupied by a friendly piece you cannot go there, but no other move suffers. So you simply bulk-generate the moves by allKingMoves[fromSqr] & ~friendlyPieces. What you propose is far slower.

[gxchess1]

Why on earth would you want to do that? The trick of deriving an index from the relevant part of the board occupancy for sliders, to use for a lookup of the moves, is only needed because there is a non-trivial relation between the occupied squares and the blocked moves. For leapers that relation is trivial: if it is occupied by a friendly piece you cannot go there, but no other move suffers. So you simply bulk-generate the moves by allKingMoves[fromSqr] & ~friendlyPieces. What you propose is far slower.

No. The post is about generating the moves, not the attacks. I want an 8-bit mask of the attacks so I can generate (using simd) the moves themselves onto the move array.

[hgm]

Well, I still don't understand what exactly you want to generate. But isn't the magic multiplier for a King on square s (0...63) simply
0x2013<<(54-s)?
Only for s > 54 you would need something else.

[gxchess1]

Well, I still don't understand what exactly you want to generate.

I want an 8-bit mask where each represents if a king can go to one of the squares the king would be able to go to if the board would be empty.

But isn't the magic multiplier for a King on square s (0...63) simply
0x2013<<(54-s)?
Only for s > 54 you would need something else.

I don't understand. How did you get 0x2013 and 54?

I basically want an identical function to

Code: Select all

uint8_t map(uint64_t attacks, square sq) {
	return _pext_u64(attacks, king_attacks[sq]);
}

Without pext, I think at the end it should look something like

Code: Select all

uint8_t map(uint64_t attacks, square sq) {
	// attacks is a subset of king_attacks[sq]
	return (attacks * king_magics[sq]) >> 56; // 56 because 64-56=8 and 8 is the number of maximum king attacks.
}

[dangi12012]

I understand what you are looking for - and have exactly solved this and have the code to generate and test magics very quickly.
I can also verify it's faster - also applicable to knights.

What op is asking is how to find magics that hash the actual 8 move bits (you can include 10bits for castling too). Into an index into a compiletime movelist.

At first I tried random numbers too but I found a nice mathematical way to get much better candidates. (ballpark. Correct or optimal ones it is an np hard problem) but increased performance 100 fold. Due to ongoing research unfortunately I cannot share code at this point in time.

So for you I recommend using a very fast random generator and in parallel hash them on all cores into increasing buffers of power 2. Don't forget the solution will have around 10 bits set so & together 3-4 random integers.

The final formula will be: (attack × magic[square]) >> (64 - N)
Or bitrotate into the corner and go with 1 magic - but 64 differing movelist offsets.

[hgm]

Without pext, I think at the end it should look something like

Code: Select all

uint8_t map(uint64_t attacks, square sq) {
	// attacks is a subset of king_attacks[sq]
	return (attacks * king_magics[sq]) >> 56; // 56 because 64-56=8 and 8 is the number of maximum king attacks.
}

As long as what you return there is supposed to be an index in a table that gives you the thing you really want, that is fine. You would in general not get the same index for a similar patterns of moves, (such as a King that can only move straight forward and backward), though.

As it happens, you would get the same mapping of move patterns to indexes for squares 0...54 with magics[sq] = 0x2013<<(54-sq). Why 2013 and 54? Because 54 is the uppermost square where all 9 squares in the 3x3 area around the King still fit on the board. And 0x2013 is what you need to shift all the bits of that 3x3 area 'into view', i.e. have them contribute to the upper-most 8 bits of a 64-bit word:

Code: Select all

abc00000 d0e00000 fgh00000.... 1x
bc00000d 0e00000f gh00000....  2x
0000d0e0 0000fgh0 0000....     16x
000fgh00 000....               2^13 x
____________________________ +
?????hed dee?????

You see that all bits a-h contribute to the upper 8 bit of the sum. That each index is unique can be seen from the mapping being invertible. The crux is that bit 52 is 0 for all the shifts. So any carry that would result from addition of the fgh for the first 3 shifts would not be able to propagate through it to contaminate the higher bits. So the lowest three bits of the upper byte are uncontaminated d, e and h. The cfg bits just above that are contaminated by the addition of d from the 16x result, though. But since d was known from bit 56, you can subtract it to remove that contamination. That tells you what f, g and c are. Knowing c you can remove its contamination from bit 62 to get b, and knowing b you can remove its contamination in bit 63 to get a. So we must be dealing with a perfect hash.

I guess you could actually use 0x2013 >> 1 = 0x1009 as magics[55]. This would lose you the upper-most (1x) contribution in the sum above, so that a no longer contributes. But there is no a for a King on 55, it is clipped off by the board edge (together with d and f). Similarly 0x2013 >> 2 = 0x804 seems to workas magics[56]. You lose the two upper-most shifts, and thus all contribution from abc. But those now where clipped by the upper board edge. And so on. But I guess it stops at magics[58] = 0x201.For magics[59] you will have to find something else. (Which will be rather easy, because you now only have to map 5 bits into 8, and 0x21 with some left-shift would do that in a non-overlapping way.)

[hgm]

I was thinking: usually the problem with magics is that multiplications cannot shift bits downwards. So it is the squares near the upper end of the baord that cause most problems. Also, with pure shifts, you need different instructions for shifting left and right.

But i386/x64 architecture also has a rotate instruction, which doesn't suffer from that limitation. As rotating N bits right is the same as rotating 64-N bits left. So why not use the rotate instruction first to get the entire King neighborhood in a fixed set of bits, and apply a magic multiplyer on that?

In particular, for a King it seems a good thing to rotate the move set right by the square number, to get the square at the King location itsef into the LSB. That would give you the word

e00000fg h0000000 .... 000000ab c00000d0

The important thing is that the rotate would move squares e-h (which would be off board if the King really was on a1) to the upper end of the word. Now we could bring the squares a-d there as well by multiplying wth 0x2010000000000009ull:

Code: Select all

e00000fg h0000000 .... 000000ab c00000d0 (<< 0)
000fgh00 00000000 .... 000abc00 000d0000 (<< 3)
00abc000 00d00000 .... 00000000 00000000 (<< 52)
0d000000 00000000 .... 00000000 00000000 (<< 61)
___________________________________________ +
ed???hfg h0d00000 ...

We see that the upper part edabc is contaminated by adding fg, (which was needed to get h 'in view'), but since g and h are uncontaminated in the two lowest bits of the upper byte, it would be possible to correct for this contamination, proving uniqueness. The prescription would thus be:

x = kingMoves[sq] & ~friends;
x = x << sq | x >> 64-sq; // this is a single rotate instruction
x *= 0x2010000000000009ull; // magic multiplier
x >>= 56; // bring to lower byte

Note that the magic imultiplier s now the same for every square, so that it doesn't have to be looked up. Presumably the elimination of this load operation would compensate the extra rotate instruction. It also reduces cache pressure by eliminating the magics table. Also note that the mapping between index values and move patterns relative to the King is now also always the same.

It would be nice if C was extended with an operator >< for 'rotate'.

[hgm]

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 ...

[gxchess1]

I understand what you are looking for - and have exactly solved this and have the code to generate and test magics very quickly.
I can also verify it's faster - also applicable to knights.

What op is asking is how to find magics that hash the actual 8 move bits (you can include 10bits for castling too). Into an index into a compiletime movelist.

At first I tried random numbers too but I found a nice mathematical way to get much better candidates. (ballpark. Correct or optimal ones it is an np hard problem) but increased performance 100 fold. Due to ongoing research unfortunately I cannot share code at this point in time.

So for you I recommend using a very fast random generator and in parallel hash them on all cores into increasing buffers of power 2. Don't forget the solution will have around 10 bits set so & together 3-4 random integers.

The final formula will be: (attack × magic[square]) >> (64 - N)
Or bitrotate into the corner and go with 1 magic - but 64 differing movelist offsets.

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

Thanks