What do you mean by 'truncating'? The captured piece will in general not be the last in the list, it will be somewhere in the middle. Compacting the list to squeeze out the piece, (requiring assigning new numbers to the pieces on the board!), and re-expanding it on UnMake, would be very expensive. In QS you would have to do it all the time, and there might not be enough nodes downstream to earn it back by not having to skip that one piece. In the root I of course repack the lists, so that you start every search with a hole-free list.
If you don;t want any overhead from skipping, you should accompany the piece list by a 'presence' mask. You can then clear bits in that mask that correspond to pieces that are captured. E.g. add in MakeMove():
Code: Select all
present &= ~list[victim].bit; // bit flag corresponding to piece
and in UnMake you set it again (or restore from the saved value). You could already store the complemented bit in the piece-list field to save a complement operation.
You can then loop over the non-captured pieces by extracting the 1 bits from the word with the usual bit-scan techniques, and skipping the captured ones takes no extra time and no branches. If you want to loop over a section of the piece list you just mask out that section, e.g.
Code: Select all
int todo = present & WHITE & SLIDERS;
while(todo) {
int next = todo & -todo;
int piece = BSF(next);
...
todo -= next;
}
[Edit] Oh, I see that they just re-assign one piece number, remapping the last piece into the created hole. But that would only work if all pieces are the same type, if you want the order to have any meaning. (And I want them in order of value, to automatically generate captures in MVV/LVA order).
Having only one typeof piece in a list means that you need many lists, one for each piece type. This just moves the problem of the holes to the holes between the lists. You would get the overhead of setting up a new loop over a list that contains 0, 1 or 2 pieces many times. It doesn't sound like a competative method at all.
An alternative would be to organize the piece list as a doubly linked list, so that you could remove the captured pieces from the list, and looping through it would automatically skip the captured pieces:
Code: Select all
list[list[victim].pred].succ = list[victim].succ;
list[list[victim].succ].pred = list[victim].pred;
and during UnMake:
Code: Select all
list[list[victim].pred].succ = victim;
list[list[victim].succ].pred = victim;
I tried that in qperft, but following the links creates a long-latency dependency chain in the (in generally tight) loops, and it was slower.
