Extract direction (ray) informations from two squares.

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
mathmoi
Posts: 265
Joined: Mon Mar 13, 2006 4:23 pm
Location: Québec
Contact:

Extract direction (ray) informations from two squares.

Post by mathmoi » Tue Jun 18, 2013 3:44 am

Hi,

While parsing SAN move to square t I sometimes find that the piece on square f is pinned to the king on square k. However if the direction (ray) defined by k-f is the same as the one defined by k-t, it means the pieces moves along the ray between it's king and the pinning piece (possibly capturing this piece) and the move is still valid.

Is there a way, maybe by doing some magic with the 0x88 difference of k-t and k-f to verify if theses two directions are the sames?

Basically what I would need is a way to extract one of the 4 directions (Horizontal, vertical, diagonal and anti-diagonal) of a 0x88 difference so I could compare the two.

Thanks,

User avatar
hgm
Posts: 23152
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Extract direction (ray) informations from two squares.

Post by hgm » Tue Jun 18, 2013 7:37 am

I don't think any magics are required. You just tabulate the direction (encoded 1-8, say) as a function of the 0x88 square difference, look them up for k-f and k-t, and test if they are the same. In my mailbox engines, where I usually have tables for the 0x88 test, there is always a table of the 'unit step' in the sought direction, and I can use that for this purpose. I use that, for instance, to test if a move blocks an existing check: remember the unit step of the check direction, and for every pseudo-legal move then test if unitStep[king-to] equals the check direction, and if it does, whether distance[king-to] <= distance[checker-to].

With bitboards it would be more 'in the spirit' to tabulate the pin ray emanating from the King (pinRay[direction][kingSquare], where 'direction' is one of the 4 major directions, and intersect that board with the bitboard of move targets for the piece.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Extract direction (ray) informations from two squares.

Post by sje » Tue Jun 18, 2013 9:05 am

I use a bitboard array BeyondBBVec[64][64] indexed by [frsq][tosq]. Each element is the bitboard or squares that are on the line from frsq to tosq beyond tosq. This can be quite useful.

Also, there is the bitboard array BeamBBVec[64][64], each element having the squares along the line from the first to second squares starting after the first square.

Then there's SqSqDir[64][64] which gives the direction from the first square to the second square.

And then there's PathwayBBVec[64][64], bitboards giving the squares between two squares.

Also, OpenRayBBVec[64][8] giving the open ray squares from a square along a direction.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Extract direction (ray) informations from two squares.

Post by xmas79 » Tue Jun 18, 2013 10:39 am

I use different tables:

unsigned char SquareRaysSquare[64][64];
bitboard SquaresToBeFreeToSquareAttacksSquare[64][64];
bitboard SquaresBehindSquareFromSquare[64][64];

The first tells me if square1 is "connected" to square2 and in which direction.
The second tells me what squares must be free for one square to attack another square (supposed they are in a ray in any direction)
The third tells me what squares are behind the second square starting from the first square.

Typical use are:
table 1: check if a piece can be pinned.
table 2: interposition of a piece during check escapes
table 3: remove invalid destination squares of king moves in the attacking ray direction

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Extract direction (ray) informations from two squares.

Post by sje » Tue Jun 18, 2013 12:49 pm

xmas79 wrote:I use different tables:

unsigned char SquareRaysSquare[64][64];
bitboard SquaresToBeFreeToSquareAttacksSquare[64][64];
bitboard SquaresBehindSquareFromSquare[64][64];

The first tells me if square1 is "connected" to square2 and in which direction.
The second tells me what squares must be free for one square to attack another square (supposed they are in a ray in any direction)
The third tells me what squares are behind the second square starting from the first square.

Typical use are:
table 1: check if a piece can be pinned.
table 2: interposition of a piece during check escapes
table 3: remove invalid destination squares of king moves in the attacking ray direction
I have something like your SquaresBehindSquareFromSquare, but instead of storing a bitboard, each element is only a single square (scalar, may be nil). It's called Sq ShadowSquareVec[64][64];

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Extract direction (ray) informations from two squares.

Post by xmas79 » Tue Jun 18, 2013 1:08 pm

sje wrote:
xmas79 wrote:I use different tables:

unsigned char SquareRaysSquare[64][64];
bitboard SquaresToBeFreeToSquareAttacksSquare[64][64];
bitboard SquaresBehindSquareFromSquare[64][64];

The first tells me if square1 is "connected" to square2 and in which direction.
The second tells me what squares must be free for one square to attack another square (supposed they are in a ray in any direction)
The third tells me what squares are behind the second square starting from the first square.

Typical use are:
table 1: check if a piece can be pinned.
table 2: interposition of a piece during check escapes
table 3: remove invalid destination squares of king moves in the attacking ray direction
I have something like your SquaresBehindSquareFromSquare, but instead of storing a bitboard, each element is only a single square (scalar, may be nil). It's called Sq ShadowSquareVec[64][64];
Having a bitboard stored allows you to do nice things like evaluate all fast interposing moves like following:
1) take attacker's square and king's square and probel that table
2) or thi value with the attacker
3) the result are all interposing (and capture) squares you can use.

Very fast. If you do square by square, you have to loop and have to know the ray direction.

edit: I overlooked the table name (I wrongly read "SquaresToBeFreeToSquareAttacksSquare"...) That table ("SquaresBehindSquareFromSquare") allows me to evaluate xrays pieces in a very fast way.

mathmoi
Posts: 265
Joined: Mon Mar 13, 2006 4:23 pm
Location: Québec
Contact:

Re: Extract direction (ray) informations from two squares.

Post by mathmoi » Tue Jun 18, 2013 1:39 pm

Hi,

Lookup table it is then. I just wanted to make sure there was not an efficient/clever way to calculate this from the coordinates alone.

Thanks,

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Code fragment form Symbolic's Bitboard class initialization

Post by sje » Wed Jun 19, 2013 6:02 am

Code fragment form Symbolic's Bitboard class initialization:

Code: Select all

Bitboard Bitboard&#58;&#58;FileBBVec&#91;FileLen&#93;;
Bitboard Bitboard&#58;&#58;RankBBVec&#91;RankLen&#93;;
Bitboard Bitboard&#58;&#58;EdgeBBVec&#91;DirSweepLen&#93;;

Bitboard Bitboard&#58;&#58;OpenRayBBVec&#91;SqLen&#93;&#91;DirSweepLen&#93;;
Bitboard Bitboard&#58;&#58;PathwayBBVec&#91;SqLen&#93;&#91;SqLen&#93;;
Bitboard Bitboard&#58;&#58;BeyondBBVec&#91;SqLen&#93;&#91;SqLen&#93;;
Bitboard Bitboard&#58;&#58;ExtendBBVec&#91;SqLen&#93;&#91;SqLen&#93;;

Code: Select all

void Bitboard&#58;&#58;ClassInit&#40;void&#41;
&#123;
  for &#40;File file = &#40;File&#41; 0; file < FileLen; IncrFile&#40;file&#41;)
  &#123;
    FileBBVec&#91;file&#93;.Reset&#40;);
    for &#40;Rank rank = &#40;Rank&#41; 0; rank < RankLen; IncrRank&#40;rank&#41;)
      FileBBVec&#91;file&#93;.SetSq&#40;file, rank&#41;;
  &#125;;

  for &#40;Rank rank = &#40;Rank&#41; 0; rank < RankLen; IncrRank&#40;rank&#41;)
  &#123;
    RankBBVec&#91;rank&#93;.Reset&#40;);
    for &#40;File file = &#40;File&#41; 0; file < FileLen; IncrFile&#40;file&#41;)
      RankBBVec&#91;rank&#93;.SetSq&#40;file, rank&#41;;
  &#125;;
  
  EdgeBBVec&#91;DirE&#93; = FileBBVec&#91;FileH&#93;;
  EdgeBBVec&#91;DirN&#93; = RankBBVec&#91;Rank8&#93;;
  EdgeBBVec&#91;DirW&#93; = FileBBVec&#91;FileA&#93;;
  EdgeBBVec&#91;DirS&#93; = RankBBVec&#91;Rank1&#93;;
  
  EdgeBBVec&#91;DirNE&#93; = EdgeBBVec&#91;DirN&#93; | EdgeBBVec&#91;DirE&#93;;
  EdgeBBVec&#91;DirNW&#93; = EdgeBBVec&#91;DirN&#93; | EdgeBBVec&#91;DirW&#93;;
  EdgeBBVec&#91;DirSW&#93; = EdgeBBVec&#91;DirS&#93; | EdgeBBVec&#91;DirW&#93;;
  EdgeBBVec&#91;DirSE&#93; = EdgeBBVec&#91;DirS&#93; | EdgeBBVec&#91;DirE&#93;;

  for &#40;Sq sq = &#40;Sq&#41; 0; sq < SqLen; IncrSq&#40;sq&#41;)
    for &#40;Dir dir = DirSweepStart; dir <= DirSweepStop; IncrDir&#40;dir&#41;)
    &#123;
      Sq nextsq = sq;
      
      OpenRayBBVec&#91;sq&#93;&#91;dir&#93;.Reset&#40;);
      while &#40;IsSqNotNil&#40;nextsq = NextSquare&#91;nextsq&#93;&#91;dir&#93;))
        OpenRayBBVec&#91;sq&#93;&#91;dir&#93;.SetSq&#40;nextsq&#41;;
    &#125;;
  
  for &#40;Sq frsq = &#40;Sq&#41; 0; frsq < SqLen; IncrSq&#40;frsq&#41;)
    for &#40;Sq tosq = &#40;Sq&#41; 0; tosq < SqLen; IncrSq&#40;tosq&#41;)
    &#123;
      const Dir dir = SqSqDir&#91;frsq&#93;&#91;tosq&#93;;
      
      if &#40;IsDirNotNil&#40;dir&#41; && IsDirSweep&#40;dir&#41;)
        PathwayBBVec&#91;frsq&#93;&#91;tosq&#93; =
          OpenRayBBVec&#91;frsq&#93;&#91;dir&#93; & OpenRayBBVec&#91;tosq&#93;&#91;CvDirToOtherDir&#91;dir&#93;&#93;;
      else
        PathwayBBVec&#91;frsq&#93;&#91;tosq&#93;.Reset&#40;);
    &#125;;
  
  for &#40;Sq frsq = &#40;Sq&#41; 0; frsq < SqLen; IncrSq&#40;frsq&#41;)
    for &#40;Sq tosq = &#40;Sq&#41; 0; tosq < SqLen; IncrSq&#40;tosq&#41;)
    &#123;
      const Dir dir = SqSqDir&#91;frsq&#93;&#91;tosq&#93;;
      
      if &#40;IsDirNotNil&#40;dir&#41; && IsDirSweep&#40;dir&#41;)
        BeyondBBVec&#91;frsq&#93;&#91;tosq&#93; = OpenRayBBVec&#91;tosq&#93;&#91;dir&#93;;
      else
        BeyondBBVec&#91;frsq&#93;&#91;tosq&#93;.Reset&#40;);
    &#125;;
  
  for &#40;Sq frsq = &#40;Sq&#41; 0; frsq < SqLen; IncrSq&#40;frsq&#41;)
    for &#40;Sq tosq = &#40;Sq&#41; 0; tosq < SqLen; IncrSq&#40;tosq&#41;)
    &#123;
      const Dir dir = SqSqDir&#91;frsq&#93;&#91;tosq&#93;;
      
      if &#40;IsDirNotNil&#40;dir&#41; && IsDirSweep&#40;dir&#41;)
        ExtendBBVec&#91;frsq&#93;&#91;tosq&#93; = OpenRayBBVec&#91;frsq&#93;&#91;dir&#93;;
      else
        ExtendBBVec&#91;frsq&#93;&#91;tosq&#93;.Reset&#40;);
    &#125;;
&#125;

Gerd Isenberg
Posts: 2113
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Extract direction (ray) informations from two squares.

Post by Gerd Isenberg » Wed Jun 19, 2013 8:07 am

mathmoi wrote:Hi,

Lookup table it is then. I just wanted to make sure there was not an efficient/clever way to calculate this from the coordinates alone.

Thanks,
Recently, Don Dailey tried the denser 240 sized table with rotated inbetween sets indexed by 0x88 difference, instead of 64x64 tables, and reported a slowdown.
http://www.talkchess.com/forum/viewtopic.php?t=46240

If speed is not an issue for you, Pure Calculation is lookupless.

Post Reply