Calculating TO

[hgm]

I just thought of trying a quick calculation to get my TO square in my generate checks function, which also does not require magics.

I considered adding a function to selectively generate checks. The idea was to tabulate the squares where a piece of a certain type could deliver check, (what you call TO square), relative to King square, as a function of the current piece position (relative to King square). For sliders it would then have to be checked for each target if the rays King-TO and piece-TO were not blocked.

I grew less enthousiastic for this idea as I realized that a Queen can have 12 possible TO squares, while in the middle-game Queens often has less than 12 moves. So for a Queen it is probably more efficient to just generate the moves, and test if they check.

Now I think it is more efficient, in the process of King-safety determination, to differentially maintain a table where checks are possible (taken the Pawn shield into account). With good King safety, as the engine would maintain in most of the tree in the middle-game, there should be no non-capture slider checks amongst this, except on the back rank. So the problem would be reduced in most cases to figure out if there are Queen or Rook moves to the back rank, which is comparatively cheap to figure out by normal move generation for forward moves of these 3 pieces only.

[bob]

I just thought of trying a quick calculation to get my TO square in my generate checks function, which also does not require magics.

I considered adding a function to selectively generate checks. The idea was to tabulate the squares where a piece of a certain type could deliver check, (what you call TO square), relative to King square, as a function of the current piece position (relative to King square). For sliders it would then have to be checked for each target if the rays King-TO and piece-TO were not blocked.

I grew less enthousiastic for this idea as I realized that a Queen can have 12 possible TO squares, while in the middle-game Queens often has less than 12 moves. So for a Queen it is probably more efficient to just generate the moves, and test if they check.

Now I think it is more efficient, in the process of King-safety determination, to differentially maintain a table where checks are possible (taken the Pawn shield into account). With good King safety, as the engine would maintain in most of the tree in the middle-game, there should be no non-capture slider checks amongst this, except on the back rank. So the problem would be reduced in most cases to figure out if there are Queen or Rook moves to the back rank, which is comparatively cheap to figure out by normal move generation for forward moves of these 3 pieces only.

It is easier than that if you use bitboards.

First, generate all possible queen moves from the square of the enemy king. Then generate all possible queen moves for your queen. And the two together. If it is non-zero, the bits that are set are squares where the queen can move to and give check to the enemy king.

I did a GenerateChecks() function for recent Crafty that does a similar trick for discovered checks as well, so it gets direct and discovered checks and never has to check to see if they really check the opponent.

[hgm]

It is easier than that if you use bitboards.

I know. But bitboards are slow as the area of the board, which scales quadratically with linear size, and I don't like that. Ray scans only scale as the linear size of the board.

So the purpose was to find the fastest way to do this for a mailbox board.

[grant]

Bob

Yes, this is what I did in my previous GenerateChecks(), but I seem to have gone off the magics idea and only use them in GenerateCaptures(). Ironically.

For the queen, I let the GenerateCaptures() know when to save the attacks bitboard (certain plys in QS) which saves duplicating the calculation, though I may have to use magic to generate queen moves from the king to get my intersections here since this is not calculated anywhere else in the program.

Grant

[Sven]

For queen the same but there you may get up to four squares.

That's actually 12.

Oops, true of course
Sven

[Sven]

Sven

That is exactly what I was trying to avoid.

For rooks giving check, I simply lookup the bitboard containing all the squares the rook has to pass over to capture the king (if you see what I mean), and AND it with ALLOccupied. If the result is zero, a non-capture check is possible and the TO square can be calculated (as above).

Same with bishops but at the moment I have to use intersecting bitboards to get my TO squares.

Grant

What about storing the bishop intersection squares of all pairs of squares in two arrays, one for each way of a bishop to go from A to B?

Code: Select all

int diagIntersect1[64][64];
int diagIntersect2[64][64];
int to1, to2;
//
if ((allBishopTargetsFrom[oppKing] & allOccupied) == 0) {
    to1 = diagIntersect1[from][oppKing];
    to2 = diagIntersect2[from][oppKing];
}

Just as a quick idea. It takes some additional 32k of RAM and costs some memory accesses but should be quicker than the calculation mentioned above which requires branches.

Sven

[Gerd Isenberg]

so in short:
TO = (9*(sqA>>3 + sqA&7)+7*(sqB>>3 - sqB&7))/2

but be aware that TO has to be checked for 0 <= TO <= 63
and sqA and sqB must be on equal colored squares ((sqA+sqB) & 1) == 0

Interesting, but you need to check too much, range and different color, which is by the way

Code: Select all

diffColor = ((sqA >> 3) + sqA + (sqB >> 3) + sqB) & 1;

or the parity of the sum of the diagonal plus antidiagonal indices, which does not change after multiplying each with odd numbers.

The 0x88 trick seems to work, since 0x88 * 2 == 0x110, the parity of the diagonal indices is covered by 0x1, in total only one AND with 0x111:

Code: Select all

ra   = sqA >> 3;
rb   = sqB >> 3;
fa   = sqA  & 7;
fb   = sqB  & 7;

sq1 = 17*(ra + fa) + 15*(rb - fb);
sq2 = 17*(rb + fb) + 15*(ra - fa);

if ( (sq1 & 0x111) == 0)
  *to++ = ((sq1 >> 2) & 56) | ((sq1 >> 1) & 7);

if ( (sq2 & 0x111) == 0)
  *to++ = ((sq2 >> 2) & 56) | ((sq2 >> 1) & 7);

still quite expensive, compared to the set-wise approach for the same purpose:

Code: Select all

toSet1 = diagonal[sqB] & antiDiagonal[sqA];
toSet2 = diagonal[sqA] & antiDiagonal[sqB];

[grant]

Sven

Yes, but they need to be done separately which is what I am setting up at the moment.

Code: Select all

int diagIntersect1[64][64]; 
int diagIntersect2[64][64]; 
int to1, to2; 
// 
if (!(allBishopTargets_1[from][oppKing] & allOccupied))
    to1 = diagIntersect1[from][oppKing];
if (!(allBishopTargets_2[from][oppKing] & allOccupied))
    to2 = diagIntersect2[from][oppKing];

I might also try the calculation method in asm.

Grant

[grant]

Gerd

If the bishop was not on the same colour square as the opponents king, then the first test would fail since the allBishopTargets bitboard would be set to 0xFFFFFFFFFFFFFFFF.

Grant

[Gerd Isenberg]

Gerd

If the bishop was not on the same colour square as the opponents king, then the first test would fail since the allBishopTargets bitboard would be set to 0xFFFFFFFFFFFFFFFF.

Grant

Not sure you replied to me? I was referring to Edmund's post.

I don't understand the first condition at all ?!
If you like to waste 8KByte, why not immediately lookup 64*64 short or two byte arrays, where 0..63 per byte indicate valid intersection points, but 0xff or upper bits, no intersection.

Code: Select all

to1 = diagIntersect[from][oppKing];
if ((to1 & ~63) == 0 ) intersection point;

Gerd