Extract direction (ray) informations from two squares.

[mathmoi]

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,

[hgm]

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.

[sje]

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]

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

[sje]

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]

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]

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,

[sje]

Code fragment form Symbolic's Bitboard class initialization:

Code: Select all

Bitboard Bitboard::FileBBVec[FileLen];
Bitboard Bitboard::RankBBVec[RankLen];
Bitboard Bitboard::EdgeBBVec[DirSweepLen];

Bitboard Bitboard::OpenRayBBVec[SqLen][DirSweepLen];
Bitboard Bitboard::PathwayBBVec[SqLen][SqLen];
Bitboard Bitboard::BeyondBBVec[SqLen][SqLen];
Bitboard Bitboard::ExtendBBVec[SqLen][SqLen];

Code: Select all

void Bitboard::ClassInit(void)
{
  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]

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.