Perhaps there can also be substantial gains in the way you process the move targets once you got them. The conventional method is to join these with the from-square and write those in a move list. And then you have to assign sort keys, and sort that list later.
There is one difference between extracting targets from a bitboard and reading them from the neighbor table: with the bitboard you would by definition only have on-board targets, and can limit those through a single AND operation to squares occupied by enemies. This has an advantage as well as a disadvantage: the disadvantage is that the number of iterations in the extraction loop is variable, leading to a frequent mispredict for terminating a loop that on average has few iterations. With the neighbor table you would always have 4 neighbors, (so a fixed number of iterations), but you would have to discriminate the actual captures from the off-board and friendly pieces for each of those separately. Something like
Code: Select all
int victim = board[toSqr]; // occupant of the to-square
moveList[lastMove] = toSqr + 256*fromSqr; // pack move & store at end of move list
lastMove += (victim & opponent) != 0; // expand move list by one if victim is opponent
But you would still have to loop through the move list afterwards (but only the accepted moves) to assign sort keys, and then again several times to sort it.
So how about doing away with the move list (for captures) and instead use an attack map for a little speedup?
Use two static tables for mapping pieces on bits, victimBit[] and attackerBit[]. (You could also do those mappings on the fly, through something like 1<<piece, but tabulating is more flexible.) In each node, use an array attackers[] in stead of a move list. Each element of that array corresponds to a victim. Each bit in such an element corresponds to a piece, and gets set when that piece attacks the victim in question. So after your move generator produces a move (fromSqr, toSqr) of a given 'piece', you do
Code: Select all
int victim = board[toSqr];
attackers[victim] |= attackerBit[piece]; // mark the victim as attacked by piece
This can be done unconditionally, whether victim is a friend or foe, or even when it is empty or off board (assuming the board has some boundary guard there). The attackerBit[piece] is the same for all toSqr of a piece, and is loaded in a register before the loop over to-squares. So after production of toSqr this is just two loads, an OR and a store.
After the entire move generation, instead of messing with a move list, you can then loop through attackers[victim] in MVV order, and for every victim then over the attackers in LVA order. That latter loop can be done through bit extraction, if you assign the bits in the proper way. No assignment of sort keys, no sorting, just two nested loops.
There is a practical problem, though: with the given code you would have to clear the entire attackers[] array before you start move generation. (Or at least the elements you are going to use, for the opponent victims.) To avoid that, you can use a scalar variable 'attacked' where each bit corresponds to a victim, and flags whether the attackers[] element for that victim was already used before, or is still undefined. You can clear that variable in a single instruction, declaring all attackers[] elements invalid. And if an invalid element is then used later, it is cleared first, and marked as valid.
Code: Select all
int victim = board[toSqr];
int b = victimBit[victim];
int a = (b & attacked ? attackers[victim] : 0); // assume 0 if not used before
attacked |= b; // mark as used
attackers[victim] = a | attackerBit[piece];
(3 loads, a bit test, a conditioal move, 2 OR and a store = 8 instructions. For 4 targets that makes 32 instructions.) As a side effect the variable 'attacked' will now indicate which pieces are attacked after all move generation is done. If we assign the bits such that they would extract in MVV order, we can use it to restrict looping over victims to looping over attacked victims only, by using bit extraction. For each attacked victim we then loop through the attackers, and for each attacker we have a move ready to be searched.
