Calculating TO

[grant]

Gerd thanks very much.

The diagIntersect[64][64] array need only be 1 char because an intersection can never occur at square 0.

Code: Select all

to1 = diagIntersect[from][oppKing];
if (to1)  // intersection point;

Grant

[grant]

Looks like I may just as well use my existing inbetween[][] array for legal bishop checks (my inbetween[][] includes destination square). Discovered checks are handled separately.

Code: Select all

to1 = diagIntersect1[from][oppKing];
if (to1) {
	if (mask[from] & pinned) {
		if (inbetween[ownKing][from] & mask[to1]) {
			if (!((inbetween[from][to1] | inbetween[oppKing][to1]) & AllOccupied))
				*move++ = addMove(from, to1, bishop);
		}
	}
	else if (!((inbetween[from][to1] | inbetween[oppKing][to1]) & AllOccupied))
		*move++ = addMove(from, to1, bishop);
}

Grant

[Gerd Isenberg]

...
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];

Not bad what the good old msvc6 makes out of this...

Code: Select all

/****************************************
 * return: intersection square (if any)
 *          of diagonal of square d
 *          with antidiagonal of square a
 *         -1 if no intersection exists
 ****************************************/
int __fastcall intersectDiaAnt(int d, int a) {
	int sq = 17 * ((a>>3) + (a & 7)) + 15 * ((d>>3) - (d & 7));
	return ((sq>>2) & 56) | ((sq>>1) & 7) | -((sq & 0x0111) != 0);
}

... only three regs used and below one cache-line code, amazing...

Code: Select all

_TEXT	SEGMENT
?intersectDiaAnt@@YIHHH@Z PROC NEAR
; _d$ = ecx
; _a$ = edx
  00000	8b c1		 mov	 eax, ecx
  00002	83 e0 07	 and	 eax, 7
  00005	c1 f9 03	 sar	 ecx, 3
  00008	2b c8		 sub	 ecx, eax
  0000a	8b c2		 mov	 eax, edx
  0000c	6b c9 0f	 imul	 ecx, 15
  0000f	83 e0 07	 and	 eax, 7
  00012	c1 fa 03	 sar	 edx, 3
  00015	03 c2		 add	 eax, edx
  00017	6b c0 11	 imul	 eax, 17
  0001a	03 c8		 add	 ecx, eax
  0001c	8b c1		 mov	 eax, ecx
  0001e	8b d1		 mov	 edx, ecx
  00020	d1 f8		 sar	 eax, 1
  00022	83 e0 70	 and	 eax, 112
  00025	83 e2 0e	 and	 edx, 14
  00028	0b c2		 or	 eax, edx
  0002a	81 e1 11 01 00
	00		 and	 ecx, 273
  00030	d1 f8		 sar	 eax, 1
  00032	f7 d9		 neg	 ecx
  00034	1b c9		 sbb	 ecx, ecx
  00036	f7 d9		 neg	 ecx
  00038	f7 d9		 neg	 ecx
  0003a	0b c1		 or	 eax, ecx
  0003c	c3		 ret	 0
?intersectDiaAnt@@YIHHH@Z ENDP
_TEXT	ENDS

... except the two negates near the end

Gerd

[Gerd Isenberg]

or even better

Code: Select all

/****************************************
 * return: intersection square (if any)
 *          of diagonal of square a
 *          with antidiagonal of square b
 *         -1 if no intersection exists
 ****************************************/
int __fastcall intersectDiaAnt(int d, int a) {
   int s88x2 = 17 * ((a>>3)  + (a & 7)) + 15 * ((d>>3) - (d & 7));
   return (((s88x2>>2)&56) + ((s88x2>>1)&7)) | ( -(s88x2&0x0111) >> 31);
}

Explanation:
With

Code: Select all

square       s 
rank         r
file         f
diagonal     d
antidiagonal a
0x88-square  s88 

We may have following relations

Code: Select all

r  =  s  >> 3  // div 8
f  =  s  &  7  // mod 8

we define diagonal d and antidiagonal a by difference and sum of rank and file:

Code: Select all

d  =  r  -  f  // even are dark squares
a  =  r  +  f  // even are dark squares

that implies

Code: Select all

f  =  r  -  d
f  =  a  -  r

or

Code: Select all

r  =  d  +  f
r  =  a  -  f

and further for same files resp. same ranks

Code: Select all

r  -  d  =  a  -  r  
d  +  f  =  a  -  f  

and finally

Code: Select all

2r =  a  +  d
2f =  a  -  d

with 0x88 coordinates

Code: Select all

s88   = 16  *    r  +   f  // * 2
s88x2 = 16  *   2r  +  2f
s88x2 = 16  * (a+d) + (a-d)
s88x2 = 17a + 15d

If s88x2 is odd, a and d have different square color, otherwise if s88 & 0x88 or s88x2 & 0x110 is true, the square is off the board. In both cases there is no intersection square, which can be combined by test with 0x111. Ff AND 0x111 is false, we convert 0x88 coordinates to ordinary square coordinates, which might be done "speculative".

Code: Select all

?intersectDiaAnt@@YIHHH@Z PROC NEAR
; _d$ = ecx
; _a$ = edx

  00000	8b c1		 mov	 eax, ecx
  00002	83 e0 07	 and	 eax, 7
  00005	c1 f9 03	 sar	 ecx, 3
  00008	2b c8		 sub	 ecx, eax
  0000a	8b c2		 mov	 eax, edx
  0000c	6b c9 0f	 imul	 ecx, 15
  0000f	83 e0 07	 and	 eax, 7
  00012	c1 fa 03	 sar	 edx, 3
  00015	03 c2		 add	 eax, edx
  00017	6b c0 11	 imul	 eax, 17
  0001a	03 c8		 add	 ecx, eax

  0001c	8b c1		 mov	 eax, ecx
  0001e	8b d1		 mov	 edx, ecx
  00020	c1 f8 02	 sar	 eax, 2
  00023	81 e1 11 01 00
	00		 and	 ecx, 273
  00029	d1 fa		 sar	 edx, 1
  0002b	83 e0 38	 and	 eax, 56
  0002e	83 e2 07	 and	 edx, 7
  00031	f7 d9		 neg	 ecx
  00033	03 c2		 add	 eax, edx
  00035	c1 f9 1f	 sar	 ecx, 31
  00038	0b c1		 or	 eax, ecx
  0003a	c3		 ret	 0
?intersectDiaAnt@@YIHHH@Z ENDP

[grant]

So what about queens?

Does this look really too slow, as compared with generating all queen moves from the queen and intersecting with all queen moves from the king?

Code: Select all

TO_bitboard = queenIntersect[from][oppKing];
while (TO_bitboard) {
	to = lsb_clear(TO_bitboard);
	if (!((inbetween[from][to] | inbetween[oppKing][to]) & AllOccupied))
		*move++ = addMove(from, to, queen);
}

Just throwing it out there.

Grant