New idea for Rook magic moves storage

[Kempelen]

Hello,

Making my own magic move generator, I have lead to a new idea I want to share. It could be promising. It is about rooks moves.

The idea is simple: why to have moves[64][4096] slots? all move information are at A1 and H8 squares combined. Each one store two real directions. So I have moves[2][4096] where first entry is for A1 and second one for H8. Information for both is calculated as normal

The idea is to shift (<<) original occupancy bitboard to A1, get moves and then _or_ with the result of shift to H8 (>>). This way, it could take only aprox. double cpu instructions than normal one, but memory is reduced considerably.

There is a key issue, the result of shift must have the left and right edges of the board into accound, so 'or' bit borders, and if original square is at COL(8) or COL(1) we must remove resulting moves. There is no need to do nothing for top or down bordes as they are "lose" when shifting.

The code is like this:

Code: Select all

struct {
        BITBOARD magic;
        BITBOARD mask;
        BITBOARD moves[4096];
        int despl;
} Rmagic_info[64];


BITBOARD Rmagic(const int sq, const BITBOARD oc) {
        BITBOARD moves, moves2, index;
        BITBOARD oc2 = oc;

        // First we move ocupancy Bitboard to A1 and set the border
        oc2 >>= sq;
        setBit1(oc2, 7-COL(sq)); // (*) see later

        // Now we search for a normal magic at A1
        index = oc2 & Rmagic_info[0].mask;
        index *= Rmagic_info[0].magic;
        index >>= Rmagic_info[0].despl;
        moves = Rmagic_info[0].moves[index];
	
        // We must remove moves if square was at a border, as (*) did not propertly set
        if (COL(sq)==7) moves &= st_columna[0];

        // Shift moves to correct square 
        moves <<= sq; 
		
        // In a simpler manner, we repeat for H8 two get the other two directions
        oc2 = oc;
        oc2 <<= &#40;63-sq&#41;;
        setBit1&#40;oc2, 56 + &#40;7-COL&#40;sq&#41;));
        index = oc2 & Rmagic_info&#91;1&#93;.mask;
        index *= Rmagic_info&#91;1&#93;.magic;
        index >>= Rmagic_info&#91;1&#93;.despl;
        moves2 = Rmagic_info&#91;1&#93;.moves&#91;index&#93;;
        if &#40;COL&#40;sq&#41;==0&#41; moves2 &= st_columna&#91;7&#93;;
        moves2 >>= &#40;63-sq&#41;;

        // Return the combined move searchs
        return moves | moves2;
&#125;

At the moment, the above code run perfectly. I have only test how fast is with my move generator. The above idea result in a 2% slower, but I have plans to test it with real games during next week, as been so less memory could improve cache use during full games.

I have been thinking on bishops also, but this could be harder as there are no one square that store full two direcions. Maybe for bishop this idea would work with four square like A1, H8, A7 and G1 for one bishop and H1, A8, B1, H7 for the other.

Hope you find this interesenting, or have any idea to improve it.

Regards
Fermin

[Gerd Isenberg]

Hi Fermin,

Nice idea, always interested in new attack getters

I think handling disjoint rank and file attacks aka Kindergarten BBs is simpler and cheaper in number of instructions as well in memory size used. Roughly 6+8+1 = 15 instructions, 8.5 KByte lookup memory in one of zillions space-time tradeoffs:

Code: Select all

U64 rankMaskEx[64];
U64 fillUpAttacks[8][64];  // 4 KByte shared by ranks and diagonals
U64 aFileAttacks [8][64];  // 4 KByte

const U64 aFile = C64(0x0101010101010101);
const U64 bFile = C64(0x0202020202020202);
const U64 diac2h7 = C64(0x0080402010080400);

U64 rankAttacks(U64 occ, enumSquare sq) {
   occ = (rankMaskEx[sq] & occ) * bFile >> 58; // 3
   return rankMaskEx[sq] & fillUpAttacks[sq&7][occ]; // 3
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   occ = aFile  & (occ >> (sq&7)); // 3
   occ = (diac2h7 * occ ) >> 58;   // 2
   return aFileAttacks&#91;sq>>3&#93;&#91;occ&#93; << &#40;sq&7&#41;; //  3
&#125;

U64 rookAttacks&#40;U64 occ, enumSquare sq&#41; &#123;
   return fileAttacks&#40;occ, sq&#41; | rankAttacks&#40;occ, sq&#41;; // 1
&#125;

Regards,
Gerd