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 <<= (63-sq);
setBit1(oc2, 56 + (7-COL(sq)));
index = oc2 & Rmagic_info[1].mask;
index *= Rmagic_info[1].magic;
index >>= Rmagic_info[1].despl;
moves2 = Rmagic_info[1].moves[index];
if (COL(sq)==0) moves2 &= st_columna[7];
moves2 >>= (63-sq);
// Return the combined move searchs
return moves | moves2;
}
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