Well, perhaps it helps when I give some actual code. For creating an attack map from scratch one could use the following routine. Which is very much like the CaptGen3() I had in the previous mailbox version, except that it generates moves for only one piece, which is known to be present. So there is no loop over the non-captured pieces in the piece list. And it does not flush the captures it geenrates to a move list, but sets the corresponding bits in the attack map:
Code: Select all
//
// Piece encoding EMPTY 16 = WHITE 32 = BLACK 48 = COLOR (edge guard)
// | | | |
// 0...............PPPPPPPPNNBBRRQKppppppppnnbbrrqk#
// (1-15 unused) (16- 23)(24- 31)(32- 39)(40- 47)
//
// Piece data that is never consulted for empty squares have 32 elements, and are indexed by piece-16.
// If we examine the binary representation of piece numbers, the bits have the following function:
//
// MSB LSB nnn = number (implying type for non-Pawns)
// . . B W P n n n P = Pawn if 0, non-Pawn if 1
// W, B: White or Black
//
// Note that the WP bits identify the 'kind' of piece if we know the code represents a piece (and B = !W)
// If the code can also be an edge guard (B = W = 1) or empty square (all 0), we need BWP to identify that
int victim2unit[] = { // unit in summary counters, per piece (extract in MVV order!)
1<<28, 1<<24, 1<<20, 1<<16, 1<<12, 1<<8, 1<<4, 1, // PPPPPPPP
1<<28, 1<<24, 1<<20, 1<<16, 1<<12, 1<<8, 1<<4, 1, // NNBBRRQK
1<<28, 1<<24, 1<<20, 1<<16, 1<<12, 1<<8, 1<<4, 1, // pppppppp
1<<28, 1<<24, 1<<20, 1<<16, 1<<12, 1<<8, 1<<4, 1, // nnbbrrqk
};
int attacker2bit[] = { // flags used to indicate attacker, per piece (extract in LVA order!)
1, 1<<4, 1<<8, 1<<12, 1<<16, 1<<20, 1<<24, 1<<28, // PPPPPPPP
1, 1<<4, 1<<8, 1<<12, 1<<16, 1<<20, 1<<24, 1<<28, // NNBBRRQK
1, 1<<4, 1<<8, 1<<12, 1<<16, 1<<20, 1<<24, 1<<28, // pppppppp
1, 1<<4, 1<<8, 1<<12, 1<<16, 1<<20, 1<<24, 1<<28, // nnbbrrqk
};
/*
The attack map logically is a 32x32 array of bit flags, indicating what attacks what.
It is stored as 128 groups of 8 bits, containing 8 different attackers of the same victim:
attackers
white black
pawns other pawns other
PPPPPPPPNNBBRRQKppppppppnnbbrrqk
P................................
p P................................
a P................................
w P................................
n P................................
w s P********........................ * P protectors of white P #6
h P................................
i P................................
t N................................
e o N................................
t B................................
v h B........................@@@@@@@@ @ piece attackers of white B #2
i e R................................
c r R................................
t Q................................
i K................................
m p................................
s p p........########................ # piece attackers of black P #2
a p................................
w p................................
n p................................
b s p................................
l p................................
a p................................
c n++++++++........................ + summary of white P attacks on black pieces
m o n++++++++........................ each row is summarized by one 4-bit counter
t b++++++++........................
h b++++++++........................
e r++++++++........................
r r++++++++........................
q++++++++........................
k++++++++........................
Its elements ('attackers sets') have the format:
MSB LSB (. = unused bit, always 0)
...K...Q...R...R...B...B...N...N 8 piece attackers
or ...P...P...P...P...P...P...P...P 8 Pawn attackers
Note the assignment of pieces to bits is such that they extract in order of increasing value.
This is done so that attackers sets on different victims can be easily merged by shift and add:
...K...Q...R...R...B...B...N...N 8 piece attackers of Rook #1
...K...Q...R...R...B...B...N...N 8 piece attackers of Rook #2
_________________________________ +
..KK..QQ..RR..RR..BB..BB..NN..NN All captures of Rooks
Such merging preserves the LVA order of the extraction, all NxR and BxR before any RxR, etc.
Each of the 128 attackers sets is 'summarized' as the number of attacks in it, by a 4-bit counter.
Eight such counters are packed into one 32-bit integer.
Counters that summarize attacks by pieces of the same kind on pieces of the same kind go together,
where 'kind' is one of white Pawn, white non-Pawn, black Pawn, black non-Pawn.
So the area marked by + in the diagram above is summarize in one summary word,
which contains one 4-bit counter for each row (so that the counter corresponds to a victim).
The format of the summary elements is:
MSB LSB
(N1)(N2)(B1)(B2)(R1)(R2)( Q)( K)
The assignment of pieces to counters is such that they extract in order of decreasing value.
*/
int attackers[4*32]; // attackers set per victim, for 4 different kinds of attackers (bP, bX, wP, wX)
int summary[4*4]; // (packed) number of attacks on victims of a certain kind, per attacker & victim kind
void AddMoves(int piece, int sqr, int add)
{
int offs = (piece & 030); // offsets: 0 = black P, 8 = black other, 16 = white P, 24 = white other
int *sum = summary + offs; // part of summary[] to use for this kind of attacker
int *atts = attackers + 4*offs - 16; // part of attackers[] to use for this kind of attacker
int attBit = attacker2bit[piece-16]*add;
if(code[piece] & 0200) { // piece is a slider
int d, i = firstSlide[slideOffs[piece-16] + sqr]; // list of directions for this square
while((d = slides[i++]) >= 0) { // loop over directions
int to = neighbor[from].d[d]; // neighbor in this direction
int victim = board[to]; // occupant of the neighbor square
if(victim < COLOR) { // rejects edge guards (cannot be empty!)
int victimKind = victim >> 3; // 2 = wP, 3 = wX, 6 = bP, 7 = bX
sum[victimKind] += victim2unit[victim-16]; // inc/dec nr of attacks on this victim
atts[victim] += attBit; // set or clear flag for this attacker
}
}
} else { // piece is a leaper
int v, i = firstLeap[slideOffs[piece-16] + sqr]; // list of steps it can make from this square
while((v = steps[i++])) { // loop through steps
int to = from + v; // target square
int victim = board[to]; // occupant of the target square
if(victim + 16 & 32) { // this rejects empty (0) / edge guard (48)
int victimKind = victim >> 3 & 3; // 2 = wP, 3 = wX, 0 = bP, 1 = bX
sum[victimKind] += victim2unit[victim-16]; // inc/dec nr of attacks on this victim in summary[]
atts[victim] += attBit; // set or clear flag for this attacker in attackers[]
}
}
}
}
The tricky thing here is to determine where in the array attackers[] the bit flag we have to set resides, and where the 4-bit counter in the summary[] array resides, both in terms of the index and the location within that word. For these locations we have the tables attacker2bit[] and victim2unit[]. The array element in which this goes is determined by the victim and the 'kind' of attacker for the attack map, and the kind of attacker and kind of victim for the summaries.
As mentioned, this routine could build an attack map from scratch, by calling it for all pieces that are present. But we want to update the map incrementally, and then we only have to call it for the piece that moved. But we would have to be able to remove its moves from the old location. For that the routine has a parameter 'add', which can be set to -1, so that the modifications are subtracted rather than added.
As an example of how the map will be used, there is the following move-generation loop:
Code: Select all
unsigned int valueGroup[] = { // masks for selecting the packed counters, per summary bit
0xF, 0xF, 0xF, 0xF, 0xF, 0xF0, 0xF0, 0xF0, 0xF0, // K & Q counter
0xFF00, 0xFF00, 0xFF00, 0xFF00, 0xFF00, 0xFF00, 0xFF00, 0xFF00, // R counters
0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, // B
0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, 0xFFFF0000, // N
};
int bit2unit[] {
1, 1, 1, 1, 1<<4, 1<<4, 1<<4, 1<<4, 1<<8, 1<<8, 1<<8, 1<<8, 1<<12, 1<<12, 1<<12, 1<<12,
1<<16, 1<<16, 1<<16, 1<<16,
};
// capture generation for white
int victims[8]; // victim stack
int victimSP = 0; // victim stack pointer
int captures;
// first do all captures of non-Pawn victims (as MVV ordering prescribes)
int todo = summary[16+1] + summary[24+1]; // attacks by white P (16) and X (24) on black X (1)
while(todo) { // loop over value groups ({K}, {Q}, {R,R}, {B,B,N,N})
int bit = BSF(todo); // locate lowest non-zero counter
int groupMask = valueGroup[bit]; // bits of counters for the group that counter belongs to
// first do the P x non-P captures
int group = groupMask & summary[16+1]; // isolate counters for Pawn attacks on this group
if(group) { // this could be empty (if there are only non-Pawn attackers)
victimSP = 0; // clear victim stack
captures = 0; // to accumulate captures on this group
do { // loop over victims in this group attacked by Pawns
int bit = BSF(group) & ~3; // locate lowest non-zero counter
int counterNr = bit >> 2; // divide by 4 (rounding down), as counters have 4 bits each
int victim = BLACK + 15 - counterNr; // we are working on black non-Pawns, (MVV order!)
captures <<= 1; // shift flags to make room for new
captures += attackers[64 + victim-16];// 64 = white P attackers
victimStack[victimSP++] = victim; // remember victim
group &= ~(15 << bit); // this counter is now treated, so clear
} while(group);
do { // loop over the constructed set of captures
int bit = BSF(captures); // extract next P x X capture (MVV/LVA order)
info.victim = victimStack[bit & 3]; // get victim
info.piece = WHITE + (bit >> 2); // calculate white Pawn number (16-23)
if(SearchMove(&info)) goto cutoff; // search move and minimax score (in info struct)
captures &= captures - 1;
} while(captures);
}
// then do the non-P x non-P captures
... // very similar code as above
todo &= ~groupMask; // all victims of this value are now treated, so clear
}
I have now uploaded the correct one.
That left me face down in the dirt.