1

For context: https://www.chessprogramming.org/Looking_for_Magics are the magic numbers I am talking about

Hey, I would like to map availabilty of king attacks to low order 8 bits. For example, king's attack's on A1 would be (B1, A2, B2). Suppose I have a bitboard of only (A2, B2) I want to map it to 0b110. So it is really simple to do with PEXT instruction:

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

But I want to support cpu's without pext. Here is my humble try:

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


static uint64_t FindKingMagic(Random& rand, Square sq) {

    const Bitboard attacks = KingAttacks[sq];

    for (;;) {
        const uint64_t factor = rand();
        uint8_t low_mask = 0;
        Bitboard perm = 0;
        bool ok = true;
        do {
            if (use_magic(perm, factor, 8) != low_mask) {
                ok = false;
                break;
            }
            // permute the 8-bit mask
            ++low_mask;
        // hover the bitboard to the next attack permutation
        } while ((perm = perm.permute(attacks)));

        if (ok) {
            return factor;
        }
    }

}

So for every loop iteration I generate a magic number and test if it generates the correct 8-bit mask for every permutation. If so, I succeded.

The problem is no matter how much time I give it, it never succedes, anyone got an idea?

Very possible is try to vectorize the function and make threads that work on it. But I heard that people generate magic numbers in fractions of a second, and this doesn't generate even in a minute, so I assume this is not correct.

Basically, I have 64 uint64_ts, would I would like to have a fast function to emulate PEXT. Anyone got an idea?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • Maybe `rand()` isn't good enough? Some implementations only return 15 bits, and those may not be very random. – Gene Oct 28 '22 at 17:46
  • @Gene `rand` is actually a function parameter to a random object which internally uses Xoshiro128+ –  Oct 28 '22 at 19:32
  • Well, that's why the help says provide a complete, running minimal code. – Gene Oct 29 '22 at 01:45
  • @njuffa I am looking for something with a couple CPU instructions, not a whole big loop –  Oct 29 '22 at 08:56
  • It’s an interesting idea, I’ll have a think about it, although I’m not entirely sure why you want to do this. The magic bitboard technique is use for sliding piece attacks, a much more difficult problem than “jumping” pieces like kings and knights. Wouldn’t it be faster to just generate the attack bitboards for every square and store them in an array. Then you can scan the bitboard for the kings square (either with an intrinsic or a fast LSB finding algorithm) and use the position of the bit to get the attack bitboard out of the table? You can even compute the table at compile time – 44stonelions Jan 30 '23 at 21:43

0 Answers0