Attack table initialization with magic bitboards

[gcahilly]

I'm currently coding a chess engine in C++, and have run into a bit of trouble with my magic bitboard implementation.

So far, I have a function that calculates blockerBoards (all the possible pieces that can block the rook or the bishop).

From there, I have the following code to take these blockerBoards and convert them into attack tables:

Code: Select all

bitset<M> mBishopAttacks[64][512]; // 256 K
bitset<M> mRookAttacks[64][4096]; // 2048K

bitset<M> bishopAttacks(bitset<M> blockerBoard, int sq) {
    unsigned long long index = blockerBoard.to_ullong();
    index *= bishopMagics[sq];
    index >>= 64-9
    return mBishopAttacks[sq][newOccupied]; //outputs corresponding attack board
}

Note that I got the array of magic numbers, bishopMagics[64], from somewhere on the web.

How do I initialize these attack tables, mBishopAttacks and mRookAttacks? Currently, they are empty. Do I simply have to calculate the attack tables for each possible permutation of blockers?

Thank you all.

-Glen

[emadsen]

You need to generate the move destinations (To square) for each occupancy. I do that by consulting a mailbox array of pieces. In a loop, move along a directional ray until a piece or edge of the board (Engine.Square.Illegal in my code) is encountered. Set a bit for each reachable To square.

See this code. The actual move generation happens in this line:

Code: Select all

var movesMask = Board.CreateMoveDestinationsMask(square, occupancy, directions);

See Board.CreateMoveDestinationsMask code. You'll see it consults a _neighborSquares jagged array to move from a square to the next square in a given direction. The direction is an int enum that holds the array offset to move North, NorthEast, South, etc in an int[64] mailbox array.

[gcahilly]

Thank you.

My plan is to do the following: for a rook on a1, calculate an attackTable (possible move destinations) for each of the 2^12 permutations. It's easy to calculate this attackTable, by, as you said, just a mailbox ray sort of method. Then, store this attackTable in mRookAttacks[a1][????]. Is this second index (where I put "????"), just the permutation*magicNumber?

Does this sound like an ok plan, or am I horribly off?

[emadsen]

Then, store this attackTable in mRookAttacks[a1][????]. Is this second index (where I put "????"), just the permutation*magicNumber?

Does this sound like an ok plan, or am I horribly off?

Hey Glen. I had to consult my code because I haven't done this in a while. Once my move generator passed all my perft tests, I retained an understanding of the general concept of magic bitboards but forgot the particulars. OK, here goes...

Create a jagged array:

Code: Select all

ulong[][] _bishopMoveMasks; // [Square][Index]

Loop through each of the board's 64 squares and all possible occupancies of the bishop rays from that square. Place the move masks for square, occupancy at:

Code: Select all

var occupancy = Occupancy & _bishopRelevantOccupancyMasks[Square];
var index = GetIndex(occupancy, _bishopMagicMultipliers[Square], _bishopShifts[Square]);
_bishopMoveMasks[Square][index] = OccupancyToMovesMask[occupancy]; // Dictionary maps ulong occupancy to ulong move masks.

The GetIndex function is:

Code: Select all

int GetIndex(ulong Occupancy, ulong MagicMultiplier, int Shift) => (int) ((Occupancy * MagicMultiplier) >> Shift);

The code above answers your direct question about "this second index (where I put "????")."

Same idea for rooks. The relevantOccupancyMasks simplifies the occupancy by removing bits representing squares where the presence or absence of a piece at that location doesn't affect the pseudo-legal moves. For example, a rook on c3 with a clear path to c8 doesn't care whether a piece occupies c8. It can move to c8 whether it's occupied or not and the occupancy of that square doesn't affect the list of pseudo-legal moves for the c3 rook. A piece on c8 is not blocking access to c9. There is no c9 square.

Note the possibility of capturing one's own piece on c8. That's prevented not here in the pre-calculated magic move code but later in the move generation code that looks up pre-calculated moves. Take the pre-calculated moves you just looked up and mask it with unoccupied or enemy-occupied squares. Like this:

Code: Select all

var bishopDestinations = MoveGeneration switch
{
    MoveGeneration.AllMoves => Board.PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & unOrEnemyOccupiedSquares & ToSquareMask,
    MoveGeneration.OnlyCaptures => Board.PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & enemyOccupiedSquares & ToSquareMask,
    MoveGeneration.OnlyNonCaptures => Board.PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & ~Occupancy & ToSquareMask,
    _ => throw new Exception($"{MoveGeneration} move generation not supported.")
};

I wrote the GetRelevantOccupancy function literally because a) I was getting my head around the concept of magic move generation and explicit code helped me understand it and b) it's calculated at engine startup so I didn't care much about performance or being clever. Once it's calculated further use of the information is done via a simple array lookup.

A "move mask" is an unsigned long with a bit set at each destination (To square). It's what you created above using the mailbox ray and _neighborSquares technique.

Hopefully that helps you grok the idea. It's difficult to explain without referencing a lot of code. Explaining how magic bitboards work without referencing code is like explaining physics without using math. Code and math are the natural languages of the concepts.

[niel5946]

I'm currently coding a chess engine in C++, and have run into a bit of trouble with my magic bitboard implementation.

So far, I have a function that calculates blockerBoards (all the possible pieces that can block the rook or the bishop).

From there, I have the following code to take these blockerBoards and convert them into attack tables:

Code: Select all

bitset<M> mBishopAttacks[64][512]; // 256 K
bitset<M> mRookAttacks[64][4096]; // 2048K

bitset<M> bishopAttacks(bitset<M> blockerBoard, int sq) {
    unsigned long long index = blockerBoard.to_ullong();
    index *= bishopMagics[sq];
    index >>= 64-9
    return mBishopAttacks[sq][newOccupied]; //outputs corresponding attack board
}

Note that I got the array of magic numbers, bishopMagics[64], from somewhere on the web.

How do I initialize these attack tables, mBishopAttacks and mRookAttacks? Currently, they are empty. Do I simply have to calculate the attack tables for each possible permutation of blockers?

Thank you all.

-Glen

This might come off as a bit pedantic, but I see that you are using std::bitset. When I coded my first chess engine, I also started out with using this, but when I switched to uint64_t, I saw a massive speedup (on the order of 10x). This is because std::bitset is just a specialized vector that only stores boolean values instead of a real 64-bit word.
Therefore I will advice you to switch from std::bitset to uint64_t, if you're looking for a speedup. But I should note: Real 64-bit numbers are harder to work with than std::bitset.

I hope this will help you!

[Kotlov]

Here is my code for magic, maybe it helps ...

Code: Select all

#define POPCNT      __builtin_popcountll                // popcount
#define SWAP        __builtin_bswap64                   // swap BB
#define LB          __builtin_ctzll                     // minor bit index ((b)&(-(b)))
#define MB(_b)      (0x3F^__builtin_clzll(_b))          // major bit index
#define CL(_b)      _b&=_b-1                            // clear bit
#define EJECT(_b)   LB(_b);CL(_b);                      // eject bit
//#define ROLW(_w)    __asm("rolw $8,%0":"+r"(_w)::"cc"); // roll word
#define ROLL(_w)     __asm("rol $16,%0":"+r"(_w)::"cc");// roll word
#define SWITCH_S(_w) __asm("rol $16,%0":"+r"(_w)::"cc");// roll word
#define SET1(_a,_i) _a|=xx[_i];                         // set bit
#define SET0(_a,_i) _a&=~xx[_i];                        // unset bit


const U64 r_magic[64]=
{
    0xd1800040008053ea,0xd48020004000f383,0xd700084020013500,0xd600084022007292,
    0xd500080003009331,0xd600020008049b50,0xd50001000400fa00,0xd10000810000d3e6,
    0xd64c80004000a39b,0xda03004000806f01,0xd802001022004b80,0xd802001020408e00,
    0xd81880430a087ffe,0xd82900080c00ab00,0xd844000d6802afb4,0xd60200006ce6b3f6,
    0xd44000800064bbde,0xd8200040100067c3,0xd820008010006b81,0xd84202001020c3f8,
    0xd9600e000a00c6e0,0xd862008004008680,0xd80144000208e310,0xd4080200038303f4,
    0xd400800100210bc1,0xd8201000400027c7,0xd820010100102bc0,0xd803402a000ee600,
    0xd94a003a00128aa0,0xdb0400808004ea00,0xda008dac0002ef58,0xd40100010000cbb2,
    0xd4008040008014e0,0xd810002000400fcc,0xd810080020200403,0xd805001001001ffd,
    0xda9300a801002ffd,0xd802001400804e80,0xd802000802007b7c,0xd6e7000081003bc2,
    0xd7ffe7fed9fe300b,0xd806010080420064,0xd8a0020400301001,0xd850008100080800,
    0xdafffdfefff02020,0xdbffffbe5fde6008,0xd812408002008100,0xd7ffffdbeb7a4012,
    0xd5fffa7fffdf43f0,0xdbfffbf7ffd323f0,0xdbffffeea7ff27e0,0xdb9ffdbfcbdb2be0,
    0xdb3fff9f6feb2fe0,0xdbffff3bdffd33e0,0xdaefffdfbf733fe0,0xd65fffffbeff4bf0,
    0xd3ffffd77fff13ef,0xd44e8100400163f9,0xd7ffffdfffbf6bf7,0xd7ffff9dffbf73fa,
    0xd7ffffd7ffaf7bfd,0xd7cffffefff783ff,0xd77fffff77ed8bfd,0xd3228785022553fe
};

const U64 b_magic[64]=
{
    0xe858a9ebe999f09f,0xec1090011101ecdf,0xec0848030061ecff,0xed2806004041ed1f,
    0xec0403084001ed3f,0xec05040a4001ed5f,0xee011808040ded7f,0xe885040100a9f0df,
    0xee2840020d05eabf,0xec0a021c1801eadf,0xec2028080101ed9f,0xec8251050201edbf,
    0xed0404102801eddf,0xec0082080405edff,0xec860094515bee1f,0xee8d088c0145ee3f,
    0xec2005684215ea7f,0xed1404878489eaff,0xe428033000cff21b,0xe42401180141f29f,
    0xe7eefeb7eebff31f,0xe4226092d015ebb2,0xee0092040245ee5f,0xec820009b201ee7f,
    0xef7840035911ee9f,0xed100a4c7041ea5f,0xe50370004483f380,0xde04080004012410,
    0xdc02040002018213,0xe40802000991b41f,0xecae008001dfef1f,0xee04e20642c1ea3f,
    0xec65a0300c89ef3f,0xed4c0c8c06c7ef5f,0xe463080802750b3f,0xde12200800010811,
    0xdc3006020011e018,0xe592411200010782,0xec0a1a120803ea97,0xed7df1f23a85eebf,
    0xec1108084001eedf,0xee0402121001eeff,0xe402004a0801e69c,0xe69816012401e60a,
    0xe42010020201f194,0xe7bfb7e7fb5dec3f,0xeca0180102c1e71f,0xee180b21a185ea1f,
    0xec0108080209ef7f,0xec1104018443ef9f,0xec8520e18831efbf,0xee572ca9f5fdefdf,
    0xec00a06aa303efff,0xec0418100c81f01f,0xec4004082201f03f,0xec0850010601f05f,
    0xeb0104010495f11f,0xec0500440181f07f,0xedd27463f5b7ecbf,0xef48054001e40727,
    0xeea3d65ffdd74753,0xec9c7e9c4dc1e77f,0xec0060600e03eb1f,0xe9900c100401f15f
};

BB bat[5248];
BB rat[102400];
bb64 bm;
bb64 rm;

#define R_ADDR_MASK 0x000000000001fc00ull
#define B_ADDR_MASK 0x0000000000001fe0ull
#define R_MAGIC_ADDR (magic&R_ADDR_MASK)
#define B_MAGIC_ADDR (magic&B_ADDR_MASK)
#define SHIFT_CONST 58
#define MAGIC_SHIFT (magic>>SHIFT_CONST)
#define MAGIC_OFFSET ((occ*magic)>>MAGIC_SHIFT)

BB grm(SQ sq,BB a)
{
    a^=xx[sq];
    return((file_m[7]>>63-LB(*file_m<<sq&(a|rank_m[7]))&*file_m<<MB(file_m[7]>>63-sq&(a|*rank_m)))|
           (rank_m[7]>>63-LB(*rank_m<<sq&(a|file_m[7]))&*rank_m<<MB(rank_m[7]>>63-sq&(a|*file_m))))^xx[sq];
}

BB gbm(SQ sq,BB a)
{
    a^=xx[sq];
    BB x=diag_m[7]|*xx|xx[63];
    return(((diag_m[23]>>63-LB(diag_m[23]<<sq&(a|file_m[7]|rank_m[7])))&(diag_m[23]<<MB(diag_m[23]>>63-sq&(a|*file_m|*rank_m))))|
           ((x>>63-LB(x<<sq&(a|*file_m|rank_m[7])))&(x<<MB(x>>63-sq&(a|file_m[7]|*rank_m)))))^xx[sq];
}

BB index64(int index,int num_bits,BB mask)
{
    BB result=0ull;
    for(int i=num_bits; i--;)
        {
            int s=EJECT(mask);
            if(index&xx[i])result|=xx[s];
        }
    return result;
}

void write_att(SQ sq,int is_bishop)
{
    BB magic=is_bishop?b_magic[sq]:r_magic[sq];
    for(int i=xx[64-MAGIC_SHIFT]; i--;)
        {
            BB bb=index64(i,64-MAGIC_SHIFT,is_bishop?bm[sq]:rm[sq]);
            BB offset=bb*magic>>MAGIC_SHIFT;
            if(is_bishop)
                bat[B_MAGIC_ADDR+offset]=gbm(sq,xx[sq]|bb);
            else
                rat[R_MAGIC_ADDR+offset]=grm(sq,xx[sq]|bb);
        }
}


void initialize_magic()
{
    memset(bat,0,sizeof(bat));
    memset(rat,0,sizeof(rat));
    for(int i=64; i--;)
        {
            BB z=0x007E7E7E7E7E7E00ull;
            z|=xx[i]&rank_m[7]?rank_m[7]:0ull;
            z|=xx[i]&rank_m[0]?rank_m[0]:0ull;
            z|=xx[i]&file_m[7]?file_m[7]:0ull;
            z|=xx[i]&file_m[0]?file_m[0]:0ull;
            rm[i]=rook_m[i]&z&0x7EFFFFFFFFFFFF7Eull;
            bm[i]=bishop_m[i]&z;
            write_att(i,0);
            write_att(i,1);
        }
}

BB r_attacks(SQ sq,BB occ)
{
    BB magic=r_magic[sq];
    occ&=rm[sq];
    return rat[R_MAGIC_ADDR+MAGIC_OFFSET];
}

BB b_attacks(SQ sq,BB occ)
{
    BB magic=b_magic[sq];
    occ&=bm[sq];
    return bat[B_MAGIC_ADDR+MAGIC_OFFSET];
}

BB q_attacks(SQ sq,BB occ)
{
    return ROOK_ATTACKS(sq,occ)|BISHOP_ATTACKS(sq,occ);
}

[gcahilly]

I'm currently coding a chess engine in C++, and have run into a bit of trouble with my magic bitboard implementation.

So far, I have a function that calculates blockerBoards (all the possible pieces that can block the rook or the bishop).

From there, I have the following code to take these blockerBoards and convert them into attack tables:

Code: Select all

bitset<M> mBishopAttacks[64][512]; // 256 K
bitset<M> mRookAttacks[64][4096]; // 2048K

bitset<M> bishopAttacks(bitset<M> blockerBoard, int sq) {
    unsigned long long index = blockerBoard.to_ullong();
    index *= bishopMagics[sq];
    index >>= 64-9
    return mBishopAttacks[sq][newOccupied]; //outputs corresponding attack board
}

Note that I got the array of magic numbers, bishopMagics[64], from somewhere on the web.

How do I initialize these attack tables, mBishopAttacks and mRookAttacks? Currently, they are empty. Do I simply have to calculate the attack tables for each possible permutation of blockers?

Thank you all.

-Glen

This might come off as a bit pedantic, but I see that you are using std::bitset. When I coded my first chess engine, I also started out with using this, but when I switched to uint64_t, I saw a massive speedup (on the order of 10x). This is because std::bitset is just a specialized vector that only stores boolean values instead of a real 64-bit word.
Therefore I will advice you to switch from std::bitset to uint64_t, if you're looking for a speedup. But I should note: Real 64-bit numbers are harder to work with than std::bitset.

I hope this will help you!

Yeah, I realized that last night after I posted. As I do not have too much code thus far, it was quite easy to convert from bitsets to 64-bit numbers. The hard part is, as you said, working with integers instead of subscriptable objects.

Again, thank you everyone for your thoughts, I really appreciate it!