SquareAttackedBy

[Desperado]

was just reading a little bit

http://chessprogramming.wikispaces.com/ ... tackBySide

where i found this...

Code: Select all

Pure Calculation
A branch-less solution without any lookups and some parallel gain is likely too expensive on the fly and may at most used for initialization purposes:


U64 obstructed(enumSquare sq1, enumSquare sq2)
{
   const U64 m1   = C64(-1);
   const U64 a2a7 = C64(0x0001010101010100);
   const U64 b2g7 = C64(0x0040201008040200);
   const U64 g2b7 = C64(0x0002040810204000);
   U64 btwn, line, rank, file;
 
   btwn  = &#40;m1 << sq1&#41; ^ &#40;m1 << sq2&#41;;
   file  =   &#40;sq2 & 7&#41; - &#40;sq1   & 7&#41;;
   rank  =  (&#40;sq2 | 7&#41; -  sq1&#41; >> 3 ;
   line  =      (   &#40;file  & 0xff&#41; - 1&#41; & a2a7; // a2a7 if same file
   line += 2 * ((   &#40;rank  & 0xff&#41; - 1&#41; >> 58&#41;; // b1g1 if same rank
   line += ((&#40;rank - file&#41; & 0xff&#41; - 1&#41; & b2g7; // b2g7 if same diagonal
   line += ((&#40;rank + file&#41; & 0xff&#41; - 1&#41; & g2b7; // g2b7 if same antidiag
   return    &#40;line * &#40;btwn & -btwn&#41;)    & btwn; // mul acts like shift by smaller square
&#125;

which i think, can much easier be handled with the _idea_ of
obstrutionDifference

Code: Select all

UI_64 obstructed(UI_64 lineMask,SQR_T loSq,SQR_T hiSq)
{
 UI_64 lo = &#40;UI_64&#41; 1 << loSq;
 UI_64 hi = &#40;UI_64&#41; 1 << hiSq;
 return&#40;lineMask & &#40;hi-2*lo&#41;);
&#125;

The only difference to original OD is not including the hiSquare with mul of 2 , but excluding the loSquare with mul 2.
if something is wrong with this, let me know (only tested for some examples).

i further think this is a very fast on the fly solution, with no memory
issues to think about, because file,rank,diag,anti masks are given
anyway in bitboard progs.

Michael

[Desperado]

PS:
=====

Thinking about this some more minutes, i just want to add:

including/excluding squares in question:

(2*hi-2*lo) inc/exc
(2*hi- lo) inc/inc
( hi-2*lo) exc/exc
( hi- lo) exc/inc

(untested, but seems to be logic).

Michael

[Zach Wegner]

was just reading a little bit

http://chessprogramming.wikispaces.com/ ... tackBySide

where i found this...

Code: Select all

Pure Calculation
A branch-less solution without any lookups and some parallel gain is likely too expensive on the fly and may at most used for initialization purposes:


U64 obstructed(enumSquare sq1, enumSquare sq2)
{
   const U64 m1   = C64(-1);
   const U64 a2a7 = C64(0x0001010101010100);
   const U64 b2g7 = C64(0x0040201008040200);
   const U64 g2b7 = C64(0x0002040810204000);
   U64 btwn, line, rank, file;
 
   btwn  = &#40;m1 << sq1&#41; ^ &#40;m1 << sq2&#41;;
   file  =   &#40;sq2 & 7&#41; - &#40;sq1   & 7&#41;;
   rank  =  (&#40;sq2 | 7&#41; -  sq1&#41; >> 3 ;
   line  =      (   &#40;file  & 0xff&#41; - 1&#41; & a2a7; // a2a7 if same file
   line += 2 * ((   &#40;rank  & 0xff&#41; - 1&#41; >> 58&#41;; // b1g1 if same rank
   line += ((&#40;rank - file&#41; & 0xff&#41; - 1&#41; & b2g7; // b2g7 if same diagonal
   line += ((&#40;rank + file&#41; & 0xff&#41; - 1&#41; & g2b7; // g2b7 if same antidiag
   return    &#40;line * &#40;btwn & -btwn&#41;)    & btwn; // mul acts like shift by smaller square
&#125;

which i think, can much easier be handled with the _idea_ of
obstrutionDifference

Code: Select all

UI_64 obstructed(UI_64 lineMask,SQR_T loSq,SQR_T hiSq)
{
 UI_64 lo = &#40;UI_64&#41; 1 << loSq;
 UI_64 hi = &#40;UI_64&#41; 1 << hiSq;
 return&#40;lineMask & &#40;hi-2*lo&#41;);
&#125;

The only difference to original OD is not including the hiSquare with mul of 2 , but excluding the loSquare with mul 2.
if something is wrong with this, let me know (only tested for some examples).

i further think this is a very fast on the fly solution, with no memory
issues to think about, because file,rank,diag,anti masks are given
anyway in bitboard progs.

Michael

Two problems I see:

--Where does lineMask come from? The bulk of the calculations in Gerd's version are for creating this mask. Also, the lineMask has to already extend from one of the squares, since you don't have anything like lineMask<<loSq.

--How do you get the low square into loSq? Most of the time you don't know which square is lower, so you'd have to do a swap for this to work. Gerd's code has this:

Code: Select all

   btwn  = &#40;m1 << sq1&#41; ^ &#40;m1 << sq2&#41;;

...which is rather similar to your idea, but doesn't differentiate between high and low, and thus wouldn't require a test/swap.

[Gerd Isenberg]

You didn't consider the precondition of this routine, you only have two squares, no linemask (that would be too easy), and also no idea which square is lower or higher (no condition allowed!).

Determining the inbetween set by xor difference of the universal set shifted left by the two squares each looks quite cheap:.

Code: Select all

const U64 m1 = C64(-1);
btwn  = &#40;m1 << sq1&#41; ^ &#40;m1 << sq2&#41;; 

This excludes higher and includes lower, which is what I further need, no matter whether sq1 < sq2 or not.

As mentioned the main problem is, how do you get the linemask of any two squares without lookup and branches? Might be a common file, rank, diagonal, anti-diagonal or even no line at all.

[Desperado]

ok. i understand.

well, i didnt thought in such _theoretical_ terms, which means.

1. i considered linemask(not as _lookup_) _allowed_, because i think
each bitboard-engine has such data at hand.
ex: filemask[ID64]...
rankmask[ID64]...

2. lo/hi square really needs a simple test like
lo = sq1<sq2 ? sq1 : sq2;

(but also no _practical_ problem)

3. including/excluding squares

i posted before:

(2*hi-2*lo) inc/exc
(2*hi- lo) inc/inc
( hi-2*lo) exc/exc
( hi- lo) exc/inc

btwn = (m1 << sq1) ^ (m1 << sq2); (elegant!)

4. conclusion, you are both right of course _theoretically_ spoken.

But if i think of a practical solution, this is doing the job (onTheFly)
quickly.(no additionally lookups aside the linemasks, already at hand).

So, for the moment i keep saying, there is a fast onTheFly solution
in practise. !?

(isnt it ?)

Michael

[Gerd Isenberg]

ok. i understand.

So, for the moment i keep saying, there is a fast onTheFly solution
in practise. !?

(isnt it ?)

Michael

Yes, as mentioned on the wiki page:

Code: Select all

U64 arrObstructed[64][64]; // 4096*8 = 32KByte
 
U64 obstructed(int from, int to) {
   return arrObstructed[from][to];
}

or with less memory but more computation if you don't have 0x88 coordinates handy:

Code: Select all

U64 obstructedBy0x88Diff[240]; // 1920 bytes, 2KByte - 128 Byte
 
unsigned int x88diff(int f, int t) {
   return t - f + (t|7) - (f|7) + 120;
}
 
U64 obstructed(int from, int to) {
   return rotateLeft(obstructedBy0x88Diff[x88diff(from,to)], from);
}

[Gerd Isenberg]

4. conclusion, you are both right of course _theoretically_ spoken.

But if i think of a practical solution, this is doing the job (onTheFly)
quickly.(no additionally lookups aside the linemasks, already at hand).

You have two squares of a move from hash you like to test for legality. Where do you get the line mask from? Which line? May be a knight. Of course there are zillions of solutions with various branches and/or lookups. One may also code the line direction enum inside the moves ...

[Desperado]

ok. i understand.

So, for the moment i keep saying, there is a fast onTheFly solution
in practise. !?

(isnt it ?)

Michael

Yes, as mentioned on the wiki page:

Code: Select all

U64 arrObstructed[64][64]; // 4096*8 = 32KByte
 
U64 obstructed(int from, int to) {
   return arrObstructed[from][to];
}

or with less memory but more computation if you don't have 0x88 coordinates handy:

Code: Select all

U64 obstructedBy0x88Diff[240]; // 1920 bytes, 2KByte - 128 Byte
 
unsigned int x88diff(int f, int t) {
   return t - f + (t|7) - (f|7) + 120;
}
 
U64 obstructed(int from, int to) {
   return rotateLeft(obstructedBy0x88Diff[x88diff(from,to)], from);
}

Well, that is the point for me. This looks like a _lookupApproach_
to me.(surely fast, but with additional memory usage beside
the linemasks).

That s the reason for my proposal. It doesnt need an _additional_
lookup and can be computed (about) the same speed (or faster,i dont know yet) i think.

ok, assuming a bitboardEngine has linemask at hand already.
(high chance it has, or not?)

thx gerd for reply

Michael

[Desperado]

4. conclusion, you are both right of course _theoretically_ spoken.

But if i think of a practical solution, this is doing the job (onTheFly)
quickly.(no additionally lookups aside the linemasks, already at hand).

You have two squares of a move from hash you like to test for legality. Where do you get the line mask from? Which line? May be a knight. Of course there are zillions of solutions with various branches and/or lookups. One may also code the line direction enum inside the moves ...

ahhh, i got it now ,what your point is.

[Desperado]

Hello again,

last time it was just curiosity, thinking about this topic.
Now i want to have a solution for implementation.

So i started today thinking about it again.

So here is a simple try, and i would be curious
if this is competetive with the _x88_Lookup_approach.

of course, as ever there is room for other ideas and improvements.

thoughts:

- assuming sq0!=sq1 we can simply return(tmp)
- but the _switchDirectionPart_ maybe improved
because there will always be only one direction...
- well, at least this is branchless code without any
lookups.So my hope is, it is good enough for practical
use(beside the zillion of other approaches )

Code: Select all

//--------inBetween---------------------
//--------------------------------------

BTB_T inBetween(SQR_T sq0,SQR_T sq1)
	{
	 const BTB_T m = (BTB_T) -1;

	 BTB_T tmp = 0;

	 //switchDirection
	 tmp = fileMask(sq0) & fileMask(sq1);
	 tmp|= rankMask(sq0) & rankMask(sq1);
	 tmp|= diagMask(sq0) & diagMask(sq1);
	 tmp|= antiMask(sq0) & antiMask(sq1);

	 //innerBits
	 tmp&= &#40;m<<sq0&#41; ^ &#40;m<<sq1&#41;;
	 tmp&= tmp - 1;

	 return&#40;sq0==sq1 ? 0 &#58; tmp&#41;;
	&#125;

Code: Select all

	mov	QWORD PTR [rsp+8], rbx
	movzx	r11d, cl
	lea	rcx, OFFSET FLAT:__ImageBase
	movzx	ebx, dl
	mov	r10, QWORD PTR aMask[rcx+rbx*8]
	mov	rax, QWORD PTR dMask[rcx+rbx*8]
	or	rdx, -1
	and	rax, QWORD PTR dMask[rcx+r11*8]
	and	r10, QWORD PTR aMask[rcx+r11*8]
	mov	r8, rdx
	or	r10, rax
	mov	rax, QWORD PTR rMask[rcx+rbx*8]
	and	rax, QWORD PTR rMask[rcx+r11*8]
	or	r10, rax
	mov	rax, QWORD PTR fMask[rcx+rbx*8]
	and	rax, QWORD PTR fMask[rcx+r11*8]
	movzx	ecx, r11b
	or	r10, rax
	shl	r8, cl
	movzx	ecx, bl
	shl	rdx, cl
	xor	eax, eax
	xor	r8, rdx
	and	r10, r8
	lea	rcx, QWORD PTR [r10-1]
	and	r10, rcx
	cmp	r11b, bl
	mov	rbx, QWORD PTR [rsp+8]
	cmove	r10, rax
	mov	rax, r10
	ret	0

Michael

PS: whishing everyone a happy new year