2

I have a implemented a similar version to the example given on the chess programming wiki by Tord Romstad.

I just changed the random generation and stored the magics in an array. I even kept the old count_1s and didn't use any modern instructions.

If I test the magics on a bitboard it always give wrong results. I assume there is some problem with the transform function.

Here is the code :

#include <random>
#include <iostream>
#include <array>
#include <stdlib.h>

std::array<uint64_t, 64> ROOK_MASK, BISHOP_MASK;
std::array<uint64_t, 64> ROOK_MAGIC, BISHOP_MAGIC;
std::array<std::array<uint64_t, 4096>, 64> ROOK_MAGIC_LOOKUP, BISHOP_MAGIC_LOOKUP;

std::random_device rd;
std::uniform_int_distribution<uint64_t> dist(0, UINT64_MAX);

void printBitboard(const uint64_t& bb)
{
    uint64_t mask = 0;
    for (int rank = 7; rank >= 0; rank--) {
        for (int file = 0; file < 8; file++) {
            int square = rank * 8 + file;
            mask = 1ULL << square;
            if (bb & mask) {
                std::cout << '1';
            }
            else {
                std::cout << '0';
            }
        }
        std::cout << std::endl;
    }
    std::cout << "______________" << std::endl << std::endl;
}

uint64_t random_uint64_fewbits()
{
    return dist(rd) & dist(rd) & dist(rd);
}


int count_1s(uint64_t b) {
    int r;
    for (r = 0; b; r++, b &= b - 1);
    return r;
}

const int BitTable[64] = {
  63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
  51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
  26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
  58, 20, 37, 17, 36, 8
};

int pop_1st_bit(uint64_t* bb) {
    uint64_t b = *bb ^ (*bb - 1);
    unsigned int fold = (unsigned)((b & 0xffffffff) ^ (b >> 32));
    *bb &= (*bb - 1);
    return BitTable[(fold * 0x783a9b23) >> 26];
}

uint64_t index_to_uint64(int index, int bits, uint64_t m) {
    int i, j;
    uint64_t result = 0ULL;
    for (i = 0; i < bits; i++) {
        j = pop_1st_bit(&m);
        if (index & (1 << i)) result |= (1ULL << j);
    }
    return result;
}

uint64_t rmask(int sq) {
    uint64_t result = 0ULL;
    int rk = sq / 8, fl = sq % 8, r, f;
    for (r = rk + 1; r <= 6; r++) result |= (1ULL << (fl + r * 8));
    for (r = rk - 1; r >= 1; r--) result |= (1ULL << (fl + r * 8));
    for (f = fl + 1; f <= 6; f++) result |= (1ULL << (f + rk * 8));
    for (f = fl - 1; f >= 1; f--) result |= (1ULL << (f + rk * 8));
    return result;
}

uint64_t bmask(int sq) {
    uint64_t result = 0ULL;
    int rk = sq / 8, fl = sq % 8, r, f;
    for (r = rk + 1, f = fl + 1; r <= 6 && f <= 6; r++, f++) result |= (1ULL << (f + r * 8));
    for (r = rk + 1, f = fl - 1; r <= 6 && f >= 1; r++, f--) result |= (1ULL << (f + r * 8));
    for (r = rk - 1, f = fl + 1; r >= 1 && f <= 6; r--, f++) result |= (1ULL << (f + r * 8));
    for (r = rk - 1, f = fl - 1; r >= 1 && f >= 1; r--, f--) result |= (1ULL << (f + r * 8));
    return result;
}

uint64_t ratt(int sq, uint64_t block) {
    uint64_t result = 0ULL;
    int rk = sq / 8, fl = sq % 8, r, f;
    for (r = rk + 1; r <= 7; r++) {
        result |= (1ULL << (fl + r * 8));
        if (block & (1ULL << (fl + r * 8))) break;
    }
    for (r = rk - 1; r >= 0; r--) {
        result |= (1ULL << (fl + r * 8));
        if (block & (1ULL << (fl + r * 8))) break;
    }
    for (f = fl + 1; f <= 7; f++) {
        result |= (1ULL << (f + rk * 8));
        if (block & (1ULL << (f + rk * 8))) break;
    }
    for (f = fl - 1; f >= 0; f--) {
        result |= (1ULL << (f + rk * 8));
        if (block & (1ULL << (f + rk * 8))) break;
    }
    return result;
}

uint64_t batt(int sq, uint64_t block) {
    uint64_t result = 0ULL;
    int rk = sq / 8, fl = sq % 8, r, f;
    for (r = rk + 1, f = fl + 1; r <= 7 && f <= 7; r++, f++) {
        result |= (1ULL << (f + r * 8));
        if (block & (1ULL << (f + r * 8))) break;
    }
    for (r = rk + 1, f = fl - 1; r <= 7 && f >= 0; r++, f--) {
        result |= (1ULL << (f + r * 8));
        if (block & (1ULL << (f + r * 8))) break;
    }
    for (r = rk - 1, f = fl + 1; r >= 0 && f <= 7; r--, f++) {
        result |= (1ULL << (f + r * 8));
        if (block & (1ULL << (f + r * 8))) break;
    }
    for (r = rk - 1, f = fl - 1; r >= 0 && f >= 0; r--, f--) {
        result |= (1ULL << (f + r * 8));
        if (block & (1ULL << (f + r * 8))) break;
    }
    return result;
}


int transform(uint64_t b, uint64_t magic, int bits) {
    return (int)((b * magic) >> (64 - bits));
}

bool find_magic(int sq, int m, bool bishop) {
    uint64_t mask, b[4096], a[4096], used[4096], magic;
    int i, j, k, n;
    bool fail = false;

    mask = bishop ? bmask(sq) : rmask(sq);
    n = count_1s(mask);

    for (i = 0; i < (1 << n); i++) {
        b[i] = index_to_uint64(i, n, mask);
        a[i] = bishop ? batt(sq, b[i]) : ratt(sq, b[i]);
    }
    for (k = 0; k < 100000000; k++) {
        fail = false;
        magic = random_uint64_fewbits();
        if (count_1s((mask * magic) & 0xFF00000000000000ULL) < 6) continue;
        for (i = 0; i < 4096; i++) used[i] = 0ULL;
        for (i = 0;!fail && i < (1 << n); i++) {
            j = transform(b[i], magic, m);
            if (used[j] == 0ULL) used[j] = a[i];
            else if (used[j] != a[i]) fail = true;
        }
        if (!fail)
        {
            if (bishop)
            {
                BISHOP_MAGIC[sq] = magic;
                std::memcpy(BISHOP_MAGIC_LOOKUP[sq].data(), used, sizeof(used));
            }
            else
            {
                ROOK_MAGIC[sq] = magic;
                std::memcpy(ROOK_MAGIC_LOOKUP[sq].data(), used, sizeof(used));
            }
            
            return true;
        }
            
    }
    return false;
}

int RBits[64] = {
  12, 11, 11, 11, 11, 11, 11, 12,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  12, 11, 11, 11, 11, 11, 11, 12
};

int BBits[64] = {
  6, 5, 5, 5, 5, 5, 5, 6,
  5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 5, 5, 5, 5, 5, 5, 6
};

uint64_t getRookMoves(const uint64_t& allBlockers, const int& square)
{
    std::cout << "All Blockers" << std::endl;
    printBitboard(allBlockers);

    uint64_t maskedBlocker = ROOK_MASK[square] & allBlockers & (~(0b1ULL << square));

    std::cout << "Masked Blocker" << std::endl;
    printBitboard(maskedBlocker);

    int index = transform(maskedBlocker,ROOK_MASK[square], RBits[square]);

    uint64_t attacks = ROOK_MAGIC_LOOKUP[square][index];

    std::cout << "Attacks from Magics" << std::endl;
    printBitboard(attacks);

    std::cout << "Correct Attacks" << std::endl;
    printBitboard(ratt(square, maskedBlocker));
    return attacks;
}



void main()
{
    //fill MASKS
    for (size_t square = 0; square < 64; square++)
    {
        ROOK_MASK[square] = rmask(square);

        BISHOP_MASK[square] = bmask(square);
    }

    //find magics for each square (bishop + rook)
    for (size_t square = 0; square < 64; square++)
    {
        bool r = find_magic(square, RBits[square],false);
        bool b = find_magic(square, BBits[square], true);
        if (!(r && b))
        {
            std::cout << "ERROR FINDING MAGICS"<<std::endl;
        }
    }
    std::cout << "FINISHED FINDING MAGICS" << std::endl;

    //Test for bitboard 0xa07c04000154bc28 on square 0 / a1
    getRookMoves(0xa07c04000154bc28, 0);
}

The only thing changed from the original is the random_uint64_fewbits and the find_magic function.

In the getRookMoves i am testing my results. I test wether the Magic-Generation produces the same output as the ratt function. Example :

Attacks from Magics
00000000
00000000
00000000
10000000
10000000
10000000
10000000
01000000

Correct Attacks
00000000
00000000
00000000
00000000
10000000
10000000
10000000
01110000

They don't match so there is some error, I was not able to find.

If someone has some other resource for finding and testing magic bitboard, please share them with me.

1
  • Two comments on the code itself. First, std::random_device is best used to seed a PRNG, and not as a general purpose generator. See the comment in the example here. Second, nothing in this code needs the extra study that std::endl does. '\n' ends a line. Nov 26 at 23:08

1 Answer 1

2

After some more investigation, if found out that the issue was in the GetRookMoves function. The issue was that i was using the ROOK_MASK as parameter and not the ROOK_MAGIC array.

uint64_t getRookMoves(const uint64_t& allBlockers, const int& square)
{
    std::cout << "All Blockers" << std::endl;
    printBitboard(allBlockers);

    uint64_t maskedBlocker = ROOK_MASK[square] & allBlockers & (~(0b1ULL << square));

    std::cout << "Masked Blocker" << std::endl;
    printBitboard(maskedBlocker);

    int index = transform(maskedBlocker,ROOK_MAGIC[square], RBits[square]);

    uint64_t attacks = ROOK_MAGIC_LOOKUP[square][index];

    std::cout << "Attacks from Magics" << std::endl;
    printBitboard(attacks);

    std::cout << "Correct Attacks" << std::endl;
    printBitboard(ratt(square, maskedBlocker));
    return attacks;
}

This is the new getRookMoves function. I leave the question online beacuse, i think it can be a good example how to use magics.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.