Bitboard of squares between

[Onno Garms]

I offten need a bitboard of squares between two squares. Ideally, this is
- the connecting segment (diagonal, row, or column), if one exists
- empty when the squares differ by a knight's move
- all 64 bit in all other cases

Currently I have a lookup table for this. But as the table is quite large (32k) compared to the complexity of its content, I think it might be better to calculate online.

However, I have not yet found a fast way to do that. Any ideas?

[Pradu]

I offten need a bitboard of squares between two squares. Ideally, this is
- the connecting segment (diagonal, row, or column), if one exists
- empty when the squares differ by a knight's move
- all 64 bit in all other cases

Currently I have a lookup table for this. But as the table is quite large (32k) compared to the complexity of its content, I think it might be better to calculate online.

However, I have not yet found a fast way to do that. Any ideas?

Gerd's Routine:
http://www.vpittlik.org/wbforum/viewtop ... 9887#29887

[Chan Rasjid]

Hello,

I have the following related to what you want.
I presently don't test my codes for efficiency.

Code: Select all

My actual board is similar to this:
struct
{
u64 bb;//bit of sq
u64 bMap;//bishop map w/o center
u64 rMap;
//....

} board[64];

//test if sq x, y along a bishop path and free of blocking bits
__inline int xyBishopAttack(board_t * board, int x, int y, u64 blocks){
   //may pass a depleted blocks
   assert(x != y);
   i64 u;
   //(u - ((u & - u) << 1) gets in-between bits of a bitboard  with 2 bits
   return board->brd[x].bMap & board->brd[y].bb &&
      !(u - ((u & -(u = board->brd[x].bb | board->brd[y].bb)) << 1)
         & board->brd[x].bMap & board->brd[y].bMap & blocks);
}
 


Best Regards,
Rasjid

[Onno Garms]

This was one variant I also thought of. Unfortunately this does not work for qMap (queen). Maybe I should have separate implementations for bishops and rooks like you have.

Why do you OR the two single bits? Isn't

Code: Select all

(board->brd[x].bb - 1) ^ (board->brd[y].bb -1)


faster?

BTW, AFAIK the C standard does not guarantee that

Code: Select all

u = board->brd[x].bb | board->brd[y].bb


gets evaluated before

Code: Select all

u

[Chan Rasjid]

Hello,

Why do you OR the two single bits? Isn't
Code:

(board->brd[x].bb - 1) ^ (board->brd[y].bb -1)

faster?

Thanks for the tips. It should be better.

BTW, AFAIK the C standard does not guarantee that
Code:
u = board->brd[x].bb | board->brd[y].bb
gets evaluated before
Code:
u

My C syntax is vague. Does not the parenthesis force the order of evaluation? The codes pass the relevant asserts.

Thanks,
Rasjid

[Onno Garms]

My C syntax is vague. Does not the parenthesis force the order of evaluation?

It only groups what is inside the parenthesis. It does not determine which side of & gets evaluated first. The compiler may make its own decision.

See what I got with gcc 4:

Code: Select all

> cat order.cpp
#include <iostream>
int main ()
{
  int u;
  std::cout << u - ((u & -(u = 1)) << 1);
}

> g++ -Wall order.cpp
order.cpp: In function 'int main()':
order.cpp:5: warning: operation on 'u' may be undefined
order.cpp:5: warning: operation on 'u' may be undefined


The codes pass the relevant asserts.

If you change the compiler or optimization setting, it might fail.

[Chan Rasjid]

Hello,

Quote:
My C syntax is vague. Does not the parenthesis force the order of evaluation?

It only groups what is inside the parenthesis. It does not determine which side of & gets evaluated first. The compiler may make its own decision.

I googled and got this under "Order of evaluation" -

When parentheses are used to group the subexpressions, they alter the precedence and also the order in which the expression is evaluated, as shown in Figure 4.2.

I work all alone and for a long time could not resolve my confusion about associativity and precedence of operators, "... order of evaluation of subexpression in an expression is not guaranteed...". My current understanding is precedence of operators mean the order of evaluation. The article seems to mean this.

Code: Select all

#include <stdio.h>
#include <conio.h>

int main ()
{
  int u, v;
  v = u - ( (u & -(u = 1)) << 1);
   printf("%d", v);
   //v = -1
   getch();
  return 1;
}


The above builds in Visual C++ 4.0 without error or warning and prints -1. It seems the parenthesis in (u = 1) cause the assignment to have the highest precedence(order of evaluation) and therefore u is determined.

Best Regards,
Rasjid

[Onno Garms]

The above builds in Visual C++ 4.0 without error or warning and prints

Not every compiler prints warnings on every potential problem. For example, Visual Studio also prints no warnings
- when order in initialization list of constructor differs from the order of the member variables
- when a class has virtual functions but no virtual constructor.
The absence of a warning in a particular compiler does not mean that the code is OK.

BTW, consider a free upgrade to Visual Studio 2005 express edition.

[Chan Rasjid]

Hello,

Not every compiler prints warnings on every potential problem. For example, Visual Studio also prints no warnings
- when order in initialization list of constructor differs from the order of the member variables
- when a class has virtual functions but no virtual constructor.
The absence of a warning in a particular compiler does not mean that the code is OK.

I think you are correct. The compiler may not warn of all things undefined or indeterminate.

I sometimes just like to do things in a certain way. In the case metioned, I was aware of my uncertainty. I may need to have more restrain in this manner.

Best Regards,
Rasjid

[Ron Murawski]

The above builds in Visual C++ 4.0 without error or warning and prints

Not every compiler prints warnings on every potential problem. For example, Visual Studio also prints no warnings
- when order in initialization list of constructor differs from the order of the member variables
- when a class has virtual functions but no virtual constructor.
The absence of a warning in a particular compiler does not mean that the code is OK.

BTW, consider a free upgrade to Visual Studio 2005 express edition.

I periodically run my code through 5 different compilers with error message warnings set to max. You can shake out some subtle bugs that way.

Ron

[Chan Rasjid]

Hello Onno,

Code: Select all

int main ()
{
  int u, v;
  v = u - ( (u & -(u = 1)) << 1);//A
   printf("%d", v);
   //v = -1
   getch();
  return 1;
}

Please do not take it that I am just to prove myself right, but to learn.

I think the line A above may be syntactically correct. I was unsure earlier. The reason may be unary (-) has the highest precedence and it's operand will be the first to be evaluated. That is provided precedence means order of evaluation ?

I re-read my reference manual and got something like... order of evaluation is determined by precedence and grouping of operands ... the order of evaluation of operands of an operator is undefined...

Best Regards,
Rasjid

[Onno Garms]

You got a private message. I think discussion about operator precidence is not interesting for the majority of the people here.

[Sven Schüle]

Code: Select all

v = u - ( (u & -(u = 1)) << 1);//A

Hi,

after reading http://www.cppreference.com/operator_precedence.html, especially the comments at the very bottom of that page, you might want to avoid using code like this in the future because it is stated that the result depends on the compiler implementation.

Note also the operator precedence rules listed there.

Sven

[Gerd Isenberg]

I offten need a bitboard of squares between two squares. Ideally, this is
- the connecting segment (diagonal, row, or column), if one exists
- empty when the squares differ by a knight's move
- all 64 bit in all other cases

Currently I have a lookup table for this. But as the table is quite large (32k) compared to the complexity of its content, I think it might be better to calculate online.

However, I have not yet found a fast way to do that. Any ideas?

The 0x88-difference lookup plus 64-bit rotate looks like a competetive memory size versus computation tradeoff - specially if you already have 0x88 coordinates...

Code: Select all

u64 inbetweenBy0x88Diff[240];

u64 inBetween(u32 sq1, u32 sq2)
{
    return _rotl64(inbetweenBySigned0x88Diff[sq2+(sq2&56)-sq1-(sq1&56)+120], sq1);
}


For initialization purposes - or if you have to wait for some memory reads anyway. It leaves empty sets for all other than sliding directions. What do you intend with all bits set (-1) for none slidings and knight distances btw? Also, empty sets occur not only for knight distances but regulary for neighboared squares.

Code: Select all

u64 inBetweenWithoutLookup(u32 sq1, u32 sq2)
{
    const u64 o = 1, m1 = -o;
    const u64 a2a7 = 0x0001010101010100;
    const u64 b7h1 = 0x0002040810204080;
    const u64 b2h8 = 0x8040201008040200;
    u64 btwnbits, raybits;
    u32 rankDiff, fileDiff, antiDiff, diaxDiff;   

    btwnbits  = (o<<sq1) -  o;
    btwnbits ^= (o<<sq2) -  o;
    rankDiff  =((sq2 |7) -  sq1)>>3;
    fileDiff  = (sq2 &7) - (sq1 &7);
    antiDiff  = rankDiff + fileDiff;
    rankDiff  = rankDiff &  15;
    fileDiff  = fileDiff &  15;
    antiDiff  = antiDiff &  15;
    diaxDiff  = rankDiff ^ fileDiff;
    raybits   =((rankDiff-1)>>26)*2;
    raybits  |= (m1+fileDiff)& a2a7;
    raybits  |= (m1+antiDiff)& b7h1;
    raybits  |= (m1+diaxDiff)& b2h8;
    raybits  *= btwnbits &-btwnbits;
    return      raybits  & btwnbits;
}


Gerd

[Onno Garms]

What do you intend with all bits set (-1) for none slidings and knight distances btw?

I'm not sure if I really need this. This is only the current content of my lookup table.

The idea was that there exists a piece that can move from sq1 to sq2, if and only if between(sq1,sq2) & occupied_bb != 0.

[Gerd Isenberg]

What do you intend with all bits set (-1) for none slidings and knight distances btw?

I'm not sure if I really need this. This is only the current content of my lookup table.

The idea was that there exists a piece that can move from sq1 to sq2, if and only if between(sq1,sq2) & occupied_bb != 0.

I understand your intention - you don't have to bother with a special case for eventually wrong move coordinates, since inbetween(sq1,sq2) & occ != 0 is always true for them. But you will not need it - to check whether a move is (pseudo) legal, one has to consider piece types anyway. I would use the inbetween-call only with a sliding piece on a from-square with an appropriate to-square direction.

Gerd

[Onno Garms]

to check whether a move is (pseudo) legal, one has to consider piece types anyway.

That's why I think now (having seen that squares between are difficult) that Chan's approach (with the required fixes) might be the best. In my code, queen attacks are created as rook attacks and bishop attacks anyway.

[bob]

This is simply a bad programming practice. The key word is "evaluated". When you have x + (expression) then the (expression) has to be evaluated _before_ the addition can be done. But nothing says that X can't be read from memory before the (expression) is evaluated. That's the key point that is being misunderstood. This is a subtle form of Russian Roulette where the outcome will eventually be bad if you pull the trigger enough times.

[Onno Garms]

This is simply a bad programming practice.

The assignment order is of course one of the things to be fixed. The inefficient computation of bits between another.

I mean that one should have a function for bishop squares between and another for rook squares between. They can be implemented with about the same number of operations like Chan did. At first glance this looks faster than Gerds approaches, which however produce bishop squares OR rook sqares between

[Chan Rasjid]

Hello,

I just joined / subscribed to usenet comp.lang.c.
They are a bunch of fairly alert and informed people and they cleared all my confusion.
The following is from my "official" Reference Manual, in C++, Bjarne Stroustrup. (C++ as at May 1991 ) :-
"the order of evaluation of subexpression is determined by the precedence and grouping of operators."
They told me it was wrong ,C Reference manual wrong!
Use the golden rule of Zero Connection -
"There is zero connection between precedence of operators and order of evaluation"

Also partly my fault. They told me ".... your official reference was no more official as it was outdated about a decade ago and replaced by ..."

I think most of us should easily know this is perfectly safe :-

If (exprA && (w = bitboard1 | bitboard2)){
if (w & bb ){
....
}
}

But if we know the Zero Connection Rule,
then anything like this should stop us a little :-
a = b + (b = 1);//undefined
a = b + (c = c + 1);//ok
a = b + (c = c++);//undefined

Onno's reason given to me for the undefined did not score full points, maybe some. The reason I now know (latest C++ spec ) is that between two sequence points, an object may be modified at most once and if it is modified the prior value may only be used to determine the new valued to be stored. Almost restricting to only forms of x = x + 1 whenever x is modified.
y = a + (x = x + 10);//ok
y = 2 * x + (x = x + 1);//NOT ok

Rasjid