Gerd Isenberg had the of "magically" hashing the attack masks to a precomputed movelist (see this). Here's the source code he provided:
Code: Select all
moveTarget = KingAttacks[sq] & ~(ownPieces | attackedSquares);
idx = (moveTarget * kingMagic[sq]) >> kingShift[sq]);
movelists = kingMoveLists[sq];
movelist = movelists[idx];
moveCpy(target, movelist, movelist->n);
Here is the pseudo-code:
Code: Select all
struct MoveList {
move_t moves[MaxMoves]; // MaxMoves = 8 for Knight, 13 for Bishop etc.
char size; // Number of moves stored in this movelist
};
void add_moves(square from, bitboard attacks, piece p) {
//while (attacks)
// *end++ = make_move(from, pop_1st_bit(&attacks));
MoveList* MList = &MListTable[p][sq][mlist_magic_index(p, sq, attacks)];
move_lists[total_move_lists] = &(MList->moves[0]);
move_list_count[total_move_lists] = MList->size;
total_move_lists++;
}
Results
---
This (lazy) implementation is 10-14% faster than my implementation of fancy bitboard magics even when all the pieces are on the board! It gets even faster when there are less pawns on the board. I have provided the source code, and I strongly recommend you to test it for yourself.
Besides speed, total stack needed for move generation is reduced almost by a factor of 2 for 64-bits, and even more for 32-bits.
The bad part
---
It takes huge tables to store the movelists for sliders. The movelist tables for rooks are ~56MB in size(!), for bishops around 2MB, and *just* 96kB for Knights. It is possible to get the rook tables down to 28MB by finding optimal 14-bit magics, but well, that's still a lot. Note that I haven't used tables for kings (out of laziness).
Future work
---
There is a lot of scope for improvement. With a little bit of clever work, the whole thing can be made faster and more feasible. Here are some ideas currently floating in my head:
1. Use "variable" MaxMoves in the MoveList struct (see above). This can drastically bring down table sizes.
2. Magic Pawns: Although theoretically possible, see if it is feasible to use separate tables for single pushes, promotions, double promotions, and captures. If you manage to do this, then you don't need to use two movestacks, which means lot more speed, lot less stack needed.
3. There might be a better approach to store and use pointers to movelists, especially in perft routine.
Binaries and Source Code
---
Here you go: https://sites.google.com/site/sydfhd/projects/yaka
Download the file "YakaMoveListExperiment.zip", there are some similarly named files so beware (or check the date).
Postscript
---
Be alarmed people, there's something faster than magic bitboards in town!