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,
Extract direction (ray) informations from two squares.
Moderators: hgm, Rebel, chrisw
-
- Posts: 286
- Joined: Mon Mar 13, 2006 5:23 pm
- Location: Québec
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Extract direction (ray) informations from two squares.
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.
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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Extract direction (ray) informations from two squares.
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.
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.
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Extract direction (ray) informations from two squares.
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
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
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Extract direction (ray) informations from two squares.
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 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
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Extract direction (ray) informations from two squares.
Having a bitboard stored allows you to do nice things like evaluate all fast interposing moves like following:sje wrote: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 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
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.
-
- Posts: 286
- Joined: Mon Mar 13, 2006 5:23 pm
- Location: Québec
Re: Extract direction (ray) informations from two squares.
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,
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,
Mathieu Pagé
mathieu@mathieupage.com
mathieu@mathieupage.com
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Code fragment form Symbolic's Bitboard class initialization
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 (File file = (File) 0; file < FileLen; IncrFile(file))
{
FileBBVec[file].Reset();
for (Rank rank = (Rank) 0; rank < RankLen; IncrRank(rank))
FileBBVec[file].SetSq(file, rank);
};
for (Rank rank = (Rank) 0; rank < RankLen; IncrRank(rank))
{
RankBBVec[rank].Reset();
for (File file = (File) 0; file < FileLen; IncrFile(file))
RankBBVec[rank].SetSq(file, rank);
};
EdgeBBVec[DirE] = FileBBVec[FileH];
EdgeBBVec[DirN] = RankBBVec[Rank8];
EdgeBBVec[DirW] = FileBBVec[FileA];
EdgeBBVec[DirS] = RankBBVec[Rank1];
EdgeBBVec[DirNE] = EdgeBBVec[DirN] | EdgeBBVec[DirE];
EdgeBBVec[DirNW] = EdgeBBVec[DirN] | EdgeBBVec[DirW];
EdgeBBVec[DirSW] = EdgeBBVec[DirS] | EdgeBBVec[DirW];
EdgeBBVec[DirSE] = EdgeBBVec[DirS] | EdgeBBVec[DirE];
for (Sq sq = (Sq) 0; sq < SqLen; IncrSq(sq))
for (Dir dir = DirSweepStart; dir <= DirSweepStop; IncrDir(dir))
{
Sq nextsq = sq;
OpenRayBBVec[sq][dir].Reset();
while (IsSqNotNil(nextsq = NextSquare[nextsq][dir]))
OpenRayBBVec[sq][dir].SetSq(nextsq);
};
for (Sq frsq = (Sq) 0; frsq < SqLen; IncrSq(frsq))
for (Sq tosq = (Sq) 0; tosq < SqLen; IncrSq(tosq))
{
const Dir dir = SqSqDir[frsq][tosq];
if (IsDirNotNil(dir) && IsDirSweep(dir))
PathwayBBVec[frsq][tosq] =
OpenRayBBVec[frsq][dir] & OpenRayBBVec[tosq][CvDirToOtherDir[dir]];
else
PathwayBBVec[frsq][tosq].Reset();
};
for (Sq frsq = (Sq) 0; frsq < SqLen; IncrSq(frsq))
for (Sq tosq = (Sq) 0; tosq < SqLen; IncrSq(tosq))
{
const Dir dir = SqSqDir[frsq][tosq];
if (IsDirNotNil(dir) && IsDirSweep(dir))
BeyondBBVec[frsq][tosq] = OpenRayBBVec[tosq][dir];
else
BeyondBBVec[frsq][tosq].Reset();
};
for (Sq frsq = (Sq) 0; frsq < SqLen; IncrSq(frsq))
for (Sq tosq = (Sq) 0; tosq < SqLen; IncrSq(tosq))
{
const Dir dir = SqSqDir[frsq][tosq];
if (IsDirNotNil(dir) && IsDirSweep(dir))
ExtendBBVec[frsq][tosq] = OpenRayBBVec[frsq][dir];
else
ExtendBBVec[frsq][tosq].Reset();
};
}
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Extract direction (ray) informations from two squares.
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.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,
http://www.talkchess.com/forum/viewtopic.php?t=46240
If speed is not an issue for you, Pure Calculation is lookupless.