The idea is this: you create an auxiliary table to map the bit number to an index in the move list. E.g. for an MVV/LVA sort you could have a 2d array sortKey[attackerType][victimType], that contains a unique number for each combination (sortKey[PAWN][QUEEN] = 0, sortKey[MINOR][QUEEN]=1, ...).
Code: Select all
uint64_t moveSet = 0;
for(i=0; i<nrOfMoves; i++) {
Move m = moveList[i];
int k = sortKey[m.piece][m.victim];
moveSet |= 1<<k;
ptr[k] = i;
}
Real life is a bit more complex, because when you really do this by piece type you might have multiple moves with the same sortKey. And when you assign all pieces a unique number (like you would do when you use mailbox board + piece list) you would need 16x16 = 256 different sortKeys, so that moveSet no longer fits in a single word.
In the latter approach you could have an array uint64_t moveSet[4], and set the bit through moveSet[k>>6] |= 1ULL<<(k & 63). The bit extraction would then have to occur inside a loop over the four moveSet[] elements.
If there can be multiple moves with the same key (like when you would use this to sort non-captures by history, where you bin the history scores into narrow bins and use the bin number as sort key), you can put the moves into a linked list. I.e. put an extra field m.next in the move struct, which is initialized to an number that is not a valid index into the moveList (e.g. 255). You would then 'sort' the move by
Code: Select all
moveList[i].next = ptr[k];
ptr[k] = i;
Code: Select all
n = ptr[k];
do {
move = moveList[n];
// search move
} while((n = move.next) != 255);
