It is again difficult to make this look a bit decent. Black and white will need different code for capture generation, because the attackers set contain the white attackers in the even bits (0x55555555 pattern), and the black attackers in the odd bits (0xAAAAAAAA). So for merging the sets of two victims, we either have to use
mergedSet = whiteSet1 + 2*whiteSet2;
or
mergedSet = blackSet1 >> 1 | blackSet2;
Because I don't want to maintain two lengthy code sections that are essentially duplicates except for this detail, I wrote the code as a preprocessor macro, which gets the operator to use for merging passed as an argument. This can then be inserted into the code twice, once for expanding to the white code, once for the black code.
Code: Select all
#define MERGE(A, OP, B) capts = (A & oppoPresence) OP (B & oppoPresence)
The Search routine then contains a switch on the MVV piece number (determined earlier), which decides whether it will jump into the white or the black code, and starting at what piece:
Code: Select all
{ // capture section
unsigned int capts, capturesN, capturesB, capturesP, capturesA;
int oppoPresence = presenceMask[stm]; // note stm is already flipped here
switch(u->mvv) {
CAPT_CASES(WHITE, BLACK, >>1| ) // white captures black
break;
CAPT_CASES(BLACK, WHITE, +2* ) // black captures white
case 0:
}
}
if(u->depth <= 0 || u->gap > 0) goto cutoff;
GenNoncapts(); genCnt++;
In principle there is a case for each of the possible 32 MVVs, plus case 0 for nothing being attacked at all. At the moment I treat all MVVs belonging to the same value group the same. I.e. if the MVV is a Pawn, it tries to generate captures of all Pawns. This could be optimized by treating all cases differently, at the expense of getting even more code. I am not sure how much can be earned there, though, as it only applies to the treatment of the value group of the MVV. If, say, the MVV was the second Rook, you could save you the trouble of merging its attackers with that of the first Rook. But when you then fall through to the case of the minors, you would still have to merge all the attackers of N and B, because you have no clue which of those has attackers. You would only have some clue about that when the MVV was a minor. And merging the attackers sets is not very expensive: apart from the necessary loads in only requires two AND operations, a shift and an OR.
The cases that go into the switch look like:
Code: Select all
#define CAPT_CASES(ACOL, VCOL, OP) \
/* ACOL = WHITE or BLACK (attacker color) */\
/* VCOL = BLACK or WHITE (victim color) */\
/* OP = "+ 2*" (for black victim) and ">>1 |" (white victim) */\
case VCOL+14: /* Queen */ \
capts = attackers[VCOL+14] & oppoPresence; \
EXTRACT_AND_PLAY(bit2attacker[bit], Qvictim[bit]) \
if(undo.parentAlpha > u->pstEval + ROOKVALUE) goto cutoff; \
case VCOL+13: /* Rooks */ \
case VCOL+12: \
capts = MERGE(attackers[VCOL+12], OP, attackers[VCOL+13]); \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+12+(bit&1)) \
if(undo.parentAlpha > u->pstEval + MINORVALUE) goto cutoff; \
case VCOL+11: /* Bishops */ \
case VCOL+10: \
case VCOL+9: /* Knights */ \
case VCOL+8: \
capts = MERGE(attackers[VCOL+10], OP, attackers[VCOL+11]); \
capturesB = capts; capts &= 0xFFFF; /* 8 PxN */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+10++(bit&1)) \
capts = MERGE(attackers[VCOL+10], OP, attackers[VCOL+11]); \
capturesN = capts; capts &= 0xFFFF; /* 8 PxN */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+8++(bit&1)) \
capts = capturesB & 0xFF0000; /* 4 NxB, 4 BxB */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+10++(bit&1)) \
capts = capturesN & 0xFF0000; /* 4 NxN, 4 BxN */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+8++(bit&1)) \
capts = capturesB & 0xFF000000; /* 2 RxB, QxB, KxN */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+10++(bit&1)) \
capts = capturesN & 0xFF000000; /* 2 RxN, QxN, KxN */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+8++(bit&1)) \
if(undo.parentAlpha > u->pstEval + PAWNVALUE) goto cutoff; \
case VCOL+7: /* Pawns */ \
case VCOL+6: \
case VCOL+5: \
case VCOL+4: \
case VCOL+3: \
case VCOL+2: \
case VCOL+1: \
case VCOL: \
capts = MERGE(attackers[VCOL+6], OP, attackers[VCOL+7]); \
capturesA = capts; capts &= 0xFFFF; /* 8 PxP */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+6+(bit&1)) \
capts = MERGE(attackers[VCOL+4], OP, attackers[VCOL+5]); \
capturesB = capts; capts &= 0xFFFF; /* 8 PxP */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+4+(bit&1)) \
capts = MERGE(attackers[VCOL+2], OP, attackers[VCOL+3]); \
capturesP = capts; capts &= 0xFFFF; /* 8 PxP */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+2+(bit&1)) \
capts = MERGE(attackers[VCOL], OP, attackers[VCOL+1]); \
capturesN = capts; capts &= 0xFFFF; /* 8 PxP */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL + (bit&1)) \
capturesA = capts; capts &= 0xFFFF; /* 8 PxP */ \
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+6+(bit&1)) \
capts = capturesA & 0xFFFF0000; /* 4NxP 4BxP 4RxP 2QxP 2KxP */\
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+6+(bit&1)) \
capts = capturesB & 0xFFFF0000; /* 4NxP 4BxP 4RxP 2QxP 2KxP */\
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+4+(bit&1)) \
capts = capturesP & 0xFFFF0000; /* 4NxP 4BxP 4RxP 2QxP 2KxP */\
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL+2+(bit&1)) \
capts = capturesN & 0xFFFF0000; /* 4NxP 4BxP 4RxP 2QxP 2KxP */\
EXTRACT_AND_PLAY(ACOL+(bit>>1), VCOL + (bit&1)) \
Still quite awful, I would say. The cases for the Rooks just merge the two sets of attackers of the right color on them, and then extracts all the attackers in LVA order to search the corresponding captures. Then it tests whether it should go on with the minors, or whether this is futile. So that is straightforward.
For the minors the problem is now that the pattern for storing the attackers only allows interleaving of two sets. So it makes combined sets for attackers of Bishops and for attackers of Knights. For each of those sets the attacks are in LVA order, but to keep overall MVV/LVA order, we have to alternate the value groups between the sets: first PxB, and then PxN before continuing with NxB. So the EXTRACT_AND_PLAY loops are put to work only on part of the set, masking away the attackers whose turn is to come later. We can always immediately do the Pawn attackers. (If a PxB gives a cutoff, we don't have to bother merging teh Knight attackers.) The code above splits the sets into 3 parts: Pawns, minors and higher, and alternates between those. This gives the order:
(PxB), (PxN), (NxB, BxB), (NxN, BxN), (RxB, QxB, KxB), (RxN, QxN, KxN)
(Where I put parentheses around captures handled in a single extraction loop.) For the HxL captures this violates MVV/LVA order, as QxB goes before RxN. Now my intuition is that this doesn't matter much, as these captures are usually bad unless the victim is unprotected, and in the latter case the value of the attacker is irrelevant. At which point you try captures with a King is never very important, as captures of a protected piece with a King are illegal. Which is detected almost immediately. So these are never really searched unless the victim was unprotected. Strict MVV/LVA ordering could of course be enforced by splitting the extraction into separate loops for R and K+Q as well.
But it can be expected to be much better to split the HxL on the basis of protection. That would not be very hard either: just test for each of the N and B victims whether their attackers sets are empty, and mask all their attackers out of a combined set when it isn't. (And you only have to do that when the set was not empty to start with.)
Code: Select all
capts = capturesB & 0xFF000000; /* R, K and Q attackers */
int protB = 0;
if(capts) { // there are HxL captures on Bishops
if(attackers[VCOL+11] & presence[xstm]) // Bishop2 is protected
protB = 0xAA000000;
if(attackers[VCOL+10] & presence[xstm] // Bishop 1 is protected
protB |= 0x55000000;
capts &= ~protB; // keep the unprotected Bishops
EXTRACT_AND_PLAY(...)
}
... // same for Knights
capts = capturesB & protB; // extract the H x protected L
EXTRACT_AND_PLAY(...)
... // same for Knights
The Pawn case uses the same strategy as for the minors, but here it is even simpler: the sets are split into two. Only the PxP captures are not HxL. So the combined attackers sets of a pair of Pawns is used immediately to search the PxP captures. After all the PxP captures on all pairs have been searched, we do the HxL, pair by pair. Again, the assumption is that these can only be any good for unprotected Pawns, and that the chances a Pawn is unprotected are not any better for those attacked by a Knight than for those attacked by a Queen. To get an improvement we also would have to split into protected/unprotected victims here.
For completeness, the EXTRACT_AND_PLAY loop that occurs in so many copies is given by the macro
Code: Select all
#define EXTRACT_AND_PLAY(FRIEND, FOE) \
while(capts) { \
int bit = BSF(captures); \
undo.victim = FOE; \
undo.piece = FRIEND; \
if(SearchCapture(&undo)) goto cutoff; \
capts &= capts - 1; \
} \
So this is a pretty simple loop, consisting of only few instruction. The FOE and FRIEND arguments tell how the piece numbers are to be calculated from the bit number. Which can be different for every instance of the loop, especially for the FOE argument.
To make it easier to implement this without bugs, I will initially omit the MVV determination (and thus the overkill detection), and simply set u->mvv = stm + 14 (opponent Queen). This will make the Search() routine itself responsible for determining the true MVV, by running through all the cases. With as a possible outcome (in apparenly 36% of the cases) that nothing had to be done at all, and just return for an UnMake() of a wasted MakeMove() that did a wasted attack-map update. And the attack-map 'update' will initially be done by from-scratch generation. Once that works as intended, I can start working on making it fast. By doing the update incrementally, and by implementing the overkill detection.
Note that copy-make here might be a competative strategy to handle the attack map, as it now consists of only 32 ints (128 bytes). A memcpy of this area could very well be cheaper than doing the detailed reversal of all applied changes. (Which, for a powerful piece like Queen, might very well require change of a large fraction of the map: you would have to remove 8 attacks from the old location, and add 8 from the new location (if none hit the board edge), so that would be 16 changes already!)