Perhaps running ahead of myself, I will already specify some details of how the attack map in the 'ultimate design' should work.
Pieces will be encoded by numbers, 16-31 for the white pieces, 32-47 for the black pieces. Empty squares will be 0. For simplicity all piece lists will have 48 elements. (No matter what info about the piece they contain; I suppose some infos would never be used for an empty square, and in principle the lists for these could be reduced to 32 elements, and accessed as table[pieceNr-16].) The entries 1-15 would never be used, but treating 0 as a piece makes that we don't really have to make a distinction between captures and non-captures in MakeMove(). We just give the empty square a piece value 0, and a PST and Zobrist table of all zeros. That saves if-statements to test for captures, and most moves will be captures anyway.
The attack map attackers[80] will consist of 64-bit integers. The attackers of piece number n will be stored in attackers[n], its protectors in attackers[n+32]. The reason for using the same array for this is that it is then easier to indicate which members of the attack map have been changed, and how (to facilitate unmake). When piece A captures piece B, it inherits the attackers and protectors of the latter (apart from itself), but swaps those.
The bits representing the attackers are layed out in the word as COMB = 0x1111111111111111. The least-significant of these are the Pawns, the most-significant is the King, so the bits will extract in LVA order. The remaing bits are unused, and will always be 0. Sliders can be isolated by ANDing with 0x0FFFFF0000000000, which kills King, Knights and Pawns.
There is a slight inconvenience: piece sets representing victims cannot have the same layout as piece sets representing attackers. This because we want the bits to extract in opposit order: MVV vs LVA. There are no sets of victims in the attack map, but the attackedMask associates a bit with each victim, for indicating whether the relevant part of the attack map for that victim is non-zero. (Where 'relevant' means attacker rather than protector, and currently not captured.) Since the format cannot be the same, there is also no need to make the attackedMask 64 bits; a normal 32-bit integer suffices for the 2x16 pieces.
During move generation the attackers of the victims in a certain value group will have to be combined, and the protectors removed, before extracting the attackers in the (combined) LVA order. This explains the COMB pattern: it makes it easy to interleave the attackers of up to 4 pieces. (The value group for Pawns has 8 of those, so there we need a different trick.) We can use the attackedMask to loop through the attacked opponent pieces, and add it to the combined attack set after left-shifting it by an amount (0, 1, 2 or 3) determined by the victim, until we get to the next value group. Then we can extract the captures from the combined attackers sets in LVA order to get the captures before we continue. Somewhat like
Code: Select all
int victimSet = attackedMask & playerMask[xstm]; // opponent pieces with attacks on them
int oldg = -1; // invalid group number
uint64_t attackerSet = 0; // collects the attackers for a value group
while(victimSet) {
int v = NrOfTrailingZeros(victims);
int victim = bit2victim[v]; // next attacked piece
int g = group[victim]; // value group it belongs in
if(g != oldg) { // we got to a new value group; flush the old one
Flush(attackerSet); // generate all captures for this value group of victims in MVV/LVA order
oldg = g; // remember last group we did. Note that attackerSet is again empty at this point
}
attackerSet |= attackers[victim] << shift[victim]; // merge the attacks on this victim with the total set
victimSet &= victimSet - 1;
}
Flush(attackerSet); // generate captures of final value group of victims
void Flush(uint64_t attackerSet)
{
while(attackerSet) { // first time this is still zero
int a = NrOfTrailingZeros(todo); // extract a capture (MVV/LVA order)
int piece = bit2attacker[a]; // attacker
int victim = capt2victim[a] + oldg; // victim
int fromSqr = location[piece];
int toSqr = location[victim];
SearchMove(fromSqr, toSqr, piece, victim); // process the move
attackerSet &= attackerSet - 1; // remove this capture
}
}
