Incremental update of attacks, part II
Now we get to the difficult part, when a non-capture occupies a previously empty square. As we had seen in one of the early postings here, updating the view distances requires four ray scans, and some occupant hopping for the higher levels. But we also lack information on what moves attack the newly occupied square (which might have to be blocked if they are sliding moves with a range extending beyond the square). This will have to be reconstructed from scratch too.
So we will have to look in all 8 directions, to test the nearest neighbor there (to which the freshly updated view distance directly points us) for having moves (of sufficient range) in our direction, to add them to the attack-map entry for the freshly occupied square we are building from scratch. And possibly remove attacks on the target in the opposite direction, which is now blocked. And we would have to do the same for Tetrarch attacks, when there is a Tetrarch just behind that nearest neighbor, jumping over it to attack us. (In addition, the nearest piece could be a Tetrarch that attacks us through its ski-slide, rather than a normal slider, so that its attack would have to be flagged by another bit in the attack map. If the nearest neighbor is a jumping sliders its attack would also have to be indicated by a different bit.)
Attacks by direct leaps to the 2nd square, or potential area-move attacks, are supposed to be always indicated in the attack map, even for empty squares. So these should already be there, and we have to do nothing for them (other than keeping them) when occupying the square.
All this is pretty straightforward, and the Tetrarch drudgery can all be put in an if clause that is virtually never executed, (as Tetrarchs are almost never present on the board). The jumping-slider attacks pose a nastier problem, though. They need not come from a neighbor, but can come from behind many other pieces, flying over those. Even if the piece we place is not a jumping slider itself (so that it would never block any such moves), it still exposes itself to such over-flying attacks, which should be recorded in the attack map. We can look in each direction if there are such attacks on the piece there. But because jumping-slider attacks are flagged per piece, rather than per direction, there is no quick way to see where they came from, and if they indeed were passing over the freshly occuppied square. A nearest neighbor could have many jumping-slider attacks on it, none of those passing over the current square. It would be time-wasting to trace the source of all those attacks. (This would go through the chain attack bit -> bit number -> piece -> location -> attack direction.)
We could try to be a bit more selective in what jumping sliders to check. If a jumping slide is attacking the freshly occupied square, it would attack an obstacle down-stream of it in some direction, as all jumping slides have infinite range. We are checking the attacks on all nearest neighbors anyway, for the purpose of blocking normal sliding attacks on them, and we could check for recorded attacks by jumping sliders as well. If no such attacks exist, we don't have to do anything. And it is easy to restrict the tested sliding attacks to pieces that can indeed move along the direction of that nearest neighbor.
The nearest neighbor on our opposite side of the one receiving the jumping-slider attack passing over us, should either receive it too, or be the source of it. As we already do check all our nearest neighbors for having sliding moves towards us (and will be forced to decide if we will put those in the map as normal slides per direction, or jumping slice per source piece), we only need to address the former case. So we can AND the attack-map elements of opposite neighbors (and there are only 4 such pairs!), and only jumping-sliders that attack both would survive that.
Having a jumping-slide attack on both antiposed is still not iron-clad proof that it goes over the intermediate squares, however: a Jumping Queen could attack up to three pieces on a ray along which it can move, from a location not on that ray. For jumping Rooks and Bishops this is not possible: they only have one other direction of attack, perpedicular to the attack ray, which can only intersect it in a single square.
This problem could be solved by indicating attacks by a given Jumping Queen through two different bits, depending on the attack being orthogonal or diagonal. Or, in other words, treat a Jumping Queen as if it is a separate Jumping Rook and a Jumping Bishop, which happen to sit on the same square. Squares on the ray we are investigating attacked by the same Jumping Queen would then be indicated by different bits, and disappear in the ANDing of those attacks. Or, when (say) two different orthogonal moves of the same Jumping Queen would attack both our nearest neighbors on a diagonal (so they survive the ANDing), they would be ignored because they were not diagonal moves, and we are examining a diagonal.
Yet another problem occurs when the placed piece is a jumping slider itself, so that it will block jumping slides that went over the square before. But once we established which jumping slides do attack the placed piece, we are back to the situation of the PutBack() case, where we did have valid set of attacks on the square. So we can use the same method of removing such attacks that we block from all down-stream targets upto its next blocker.
Code: Select all
// Bit assignment in attack-map elements:
#define A_GEN3ORTHO (0x38LL << 44) /* jump-attacks by GG/+RG, per piece (orthogonal) */
#define A_GEN3DIAG (0x07LL << 44) /* jump-attacks by GG/+RG, per piece (diagonal) */
#define A_GENERALS3 (0x3FLL << 44) /* jump-attacks by GG/+RG, 2 per piece (orth/diag) */
#define A_GENERALS2 (0x0ELL << 40) /* jump-attacks by VG/+BG, per piece */
#define A_GEN1ORTHO (0xF0LL << 32) /* jump-attacks by RG/+SE, per piece (orthogonal) */
#define A_GEN1DIAG (0x0FLL << 32) /* jump-attacks by BG/+HF, per piece (diagonal) */
#define A_GENERALS1 (0xFFLL << 32) /* jump-attacks by BG/+HF and RG/+SE, per piece */
#define A_SLIDES (0xFF << 24) /* 8 bits indicating sliding attacks, per direction */
#define A_JUMPS (0xFF << 16) /* 8 bits indicating 2nd-square jumps, per direction */
#define A_OBLIQUES 0xFFFF /* off-ray moves, per piece: */
#define A_HAWKS (0x30 << 8) /* 2 Lion Hawks (LH/+Ln) */
#define A_LIONS (0x0C << 8) /* 2 Lions (Ln,+Kn) */
#define A_KNIGHTS (0x3F << 8) /* 6 Knights-jump attacks (2N, Ln/+Kn, LH/+Ln) */
#define A_TETRARCH (0xF0 << 0) /* 4 ski-slides attacks (4 +CS) */
#define A_VICE (0x03 << 0) /* 3 area-moves potential attacks (VG/+BG) */
#define A_SLIDE (1 << 24) /* slide flag for direction 0 */
#define A_JUMP (1 << 16) /* jump flag for direction 0 */
#define A_LEAPS (A_JUMPS | A_KNIGHTS | A_VICE)
#define A_ORTH (A_GEN3ORTHO | A_GEN1ORTHO)
#define A_DIAG (A_GEN3DIAG | A_GENERALS2 | A_GEN1DIAG)
// Attack-map updating
// The routines Lift, PutBack and Drop deal with square evacuation, undoing of it, and occupying an empty square, respectively
void
PlacePiece (int sqr, int piece, int side)
{
static int64 jumpType[] = { A_ORTO, A_DIAG }; // masks for orthogonal and diagonal jumping-slider attacks
int blockLevel = level[piece];
int f = SQR2FILE(sqr);
int r = 3*SQR2RANK(sqr);
burns[f][stm] += 020 << r; // increment rank count for this rank in the file and its two neighbors
burns[f+1][stm] += 010 << r;
burns[f-1][stm] += 040 << r;
BlockView(sqr, blockLevel); // update view-distances
// discovering slider moves
for(color=0; color<=ASIZE; color+=ASIZE) { // both colors
int csqr = sqr + color;
uint64 att = attacks[csqr] & A_LEAPS; // leaper attacks are already OK
for(d=0; d<8; d++) { // all 8 directions
int vec = step[d];
int dnDist = viewDist[sqr][d];
int64 slide = A_SLIDE << d; // bit indicating normal slide in this direction
int s = sqr + dnDist*vec;
int upDdist = viewDist[sqr][d^4];
int t = sqr - upDist*vec;
int attacker = board[t]; // up-stream piece
int64 dnAttacks = attacks[s+color]; // sliding attacks on down-stream neighbor, which must have passed us
att |= dnAttacks & slide; // so they now attack us
if(nrTetrarchs[color]) { // Tetrarchs on the board! (rare)
int lurker = board[t - vec]; // check out the piece just behind up-stream
if(type[lurker] == T_TETRARCH) { // it is a Tetrarch that jumps over the up-stream piece
if(d & 1 || // diagonal; Tetrarchs have unlimited range
d & 2 && upDist < 3) { // sideway; Tetrarchs have range 3 here
int b = 1 << lurker - tetrarchs[color]; // bit representing this Tetrarch
attacks[s+color] &= ~b; // the attack on down-stream is blocked
att |= b; // as it now hits us
}
}
}
if(dnAttacks & slide) // we blocked a normal slide that reached down-stream
attacks[s+color] = dnAttacks - slide; // remove it down-stream
else { // we could be hit by a slider that did not reach down-stream
int range = ranges[attacker][d]; // how far it moves in our direction
if(type[attacker] == T_TETRARCH) { // the up-stream piece is a Tetrarch (rare)
if(upDist > 1 && // it does not jump over us
d & 1 ||
d & 2 && upDist < 3) {
int b = 1 << attacker - tetrarchs[color]; // bit indicating this Tetrarch in attack map
att |= b; // record attack on current piece
attacks[s+color] &= ~b; // and remove it from down-stream (if there)
} // (for the purpose of the normal slide the Tetrarch has range 1)
} else if(range > X) { // attacker is jumping slider
att |= gen2bit[attacker] & jumpType[d & 1]; // record attack by jumping slider (for the current direction)
} else if(range >= dist) { // move reaches us
att += slide; // add it to our attack map
attacks[s+color] &= ~slide; // and remove it down-stream
}
}
if(d < 4) { // only four direction pairs
int64 upAttacks = attacks[t+color]; // attacks on up-stream obstruction
upAttacks &= jumpType[d & 1]; // jump-slide attacks in current direction set (orth or diag)
upAttacks &= dnAttacks; // keep those that also hit down-stream obstruction
att |= dnAttacks; // these must also attack us
}
} // next direction
attacks[csqr] = att;
if(level[piece]) { // piece is a jumping slider (somewhat expensive, but rare)
int mask = 1;
int l;
if(color == 0) for(l=1; l <= level[piece]; l++)
BlockView(viewDist + l*DSIZE, sqr); // update affected high-level views
att >>= 32; // jumping-slider part of just-determined attacks to 'sqr'
do { // treat in two groups to keep the lowBit[] table small (would not be needed with BSF)
int todo = att & 0x1FF; // first level: jumping Bishops and Rooks
int offs = 0;
while(todo) {
int b = lowBit[todo];
int attacker = bit2gen[b+offs]; // piece-list index
int l = gen2level[attacker]; // level of this attack
int s = location[attacker]; // origin of attack
int d = direction[sqr - s]; // direction of attack
int vec = step[d]; // base step in that direction
int sd = viewDist[s + l*DSIZE].d[d]; // unobstructed down-stream distance (from level-l view distances)
int stop = sqr + sd*vec; // obstruction capable of stopping it
int64 bit = (1LL<<32) << b + offs;
s = sqr; // starting at the evacuated square ...
do { // ... run through all down-stream targets
s += viewDist[s].d[d]*vec; // hop to next target
attacks[s+color] -= bit;
} while(s != stop); // until the level-1 blocker is marked
todo -= 1 << b;
}
att >>= 9; offs += 9;
} while(att);
}
} // other color
AddMoves(piece, side, 1);
}
Note that the bit-assignment of the jumping sliders changed a bit compared to the previous posting, so that I included it again: the level-1 (Jumping Rook and Bishop) and level-3 (Jumping Queen) flags are now split into diagonal and orthogonal attacks. This brings up their total to 17, so that they have to be extracted as two groups of nine rather than eight in the loop that blocks the corresponding attacks down-stream. That should also be done in the LiftPiece() and PutBack() routines. In fact this code of this loop is now exactly the same as in PutBack, and should perhaps be located in a separate sub-routine that both can call.
A consequence of having separate flags for Jumping Queen orthogonal and diagonal attacks means that when we generate attacks of a jumping slider appearing somewhere (in AddMoves()) we cannot simply look up the bit corresponding to its attacks (as there could be two), but will have to make that depend on the direction of the attack. To revisit that code:
Code: Select all
if(range > X) { // this indicates the move is a jumping slide (rare)
int64 bit = gen2bit[piece]; // bit representing this jumping slider in attack map
int l = piece2level[piece]; // level of opacity
int stop = sqr + viewDist[sqr + l*DSIZE].d[d]*vec;
bit <<= range - Y; // adjust Jumping Q orthogonal moves, which have range = Y + 3 <----------- new
int s = sqr;
bit *= sgn; // set up for addition or removal
do { // flag jumping attacks on all down-stream pieces
s += viewDist[s].d[d]*vec;
attacks[s+color] += bit;
} while(s != stop);
} else if(range >= dist) // target is within range
This can be done by defining the range of the orthogonal moves of Jumping Queen in the move-description table to 40 (where normal slides have X=36, and other jumping slides Y=37). Note that all values larger than the board size in principle are equivalent here, and can be used to indicate such distinctions. The gen2bit[] table then lists the bit for the three Jumping Queens their diagonal moves, and the orthogonal moves use a bit 3 places higher up in the attack set.
