Distinguish rook and bishop move efficiently

[tcusr]

It tells you which bits change in the square number. If only the bit representing 16 changes this means the square number must have changed by 16. In general a change of 16 could also alter higher bits; it just so happens that for Pawndoule pushesin Chess it doesn't: the rank umer goes from 1 to 3 (= 001 to 011 in binary) or from 6 to 4 (110 to 100). So given that the move is legal this is a way to detect the double push. Note, however,that 2->0 (010 -> 000) also satisfies the test, and is not legal.

thanks

[tromp]

> is_rook_move = ((from & 7) == (to & 7) or (from & 56) == (to & 56))

Code: Select all

is_rook_move(from, to) {
   int x = from ^ to;
   return !(x/8 & x);
}

is more efficient...

[klx]

> is_rook_move = ((from & 7) == (to & 7) or (from & 56) == (to & 56))

Code: Select all

is_rook_move(from, to) {
   int x = from ^ to;
   return !(x/8 & x);
}

is more efficient...

But not the same though? That method gives:

is_rook_move(0b000'110, 0b100'111) = true

I'd also like to point out that a decent compiler should already do this optimization, and turn the given code to something like:

Code: Select all

is_rook_move(from, to) {
   int x = from ^ to;
   return !(x & 7) | !(x & 56);
}

[tromp]

But not the same though? That method gives:
is_rook_move(0b000'110, 0b100'111) = true

Your example fails the condition "given that the move constituted by that is either a rook or a bishop move".

I'd also like to point out that a decent compiler should already do this optimization, and turn the given code to something like:

Code: Select all

is_rook_move(from, to) {
   int x = from ^ to;
   return !(x & 7) | !(x & 56);
}

The 2nd line should have a logical, not bitwise, or:

Code: Select all

   return !(x & 7) || !(x & 56);

or equivalently, saving one operation:

Code: Select all

   return !( x&7 && x&56 );

I'm not sure if compilers are smart enough to apply de Morgan's law though.
When only distinguishing between rook and bishop moves, the expensive logical-and && can be replaced by a cheaper bitwise-and & between (x&56)>>3 and x&7, and using the fact that from and to are limited to 6 bits, we can replace these operands by x/8 and x.

[hgm]

I'd also like to point out that a decent compiler should already do this optimization, and turn the given code to something like:

Code: Select all

is_rook_move(from, to) {
   int x = from ^ to;
   return !(x & 7) | !(x & 56);
}

Also with Perl?

The 2nd line should have a logical, not bitwise, or:

Code: Select all

   return !(x & 7) || !(x & 56);

or equivalently, saving one operation:

Code: Select all

   return !( x&7 && x&56 );

I'm not sure if compilers are smart enough to apply de Morgan's law though.
When only distinguishing between rook and bishop moves, the expensive logical-and && can be replaced by a cheaper bitwise-and & between (x&56)>>3 and x&7, and using the fact that from and to are limited to 6 bits, we can replace these operands by x/8 and x.

Shouldn't it be the other way around? A || B can always be replaced by A | B (assumming B has no side effects), but A && B is not the same as A & B, e.g. if A=2 and B=4.

I am also not convinced that !(x >> 8 & x) would be faster than kind[x].

[gflohr]

I have just replaced the "or" with an "|" because that avoids branching:

But the "or" is back because benchmarking shows that the boolean operator is slightly faster, probably because it is lazily evaluated, and the bitwise OR is not.

Just for the records: In Perl the "or" has to be replaced by "||" because the "or" operator has the lowest precedence of all operators.

[gflohr]

Perl is an interpreted language, isn't it? In such languages branches are not a concern, as the interpreter typically uses multiple branches to interpret any token of the language.

You are probably right. But I want to port the code back to C later.

But I will try to find a test case that I can benchmark.

[tromp]

Also with Perl?

man perlop

shows perl supporting these bitwise operations as well.

Shouldn't it be the other way around? A || B can always be replaced by A | B (assumming B has no side effects), but A && B is not the same as A & B, e.g. if A=2 and B=4.

Like I said, the replacement while not generally valid, is valid in this specific case because of how bishop moves affect the 6 bit coordinates. In particular, if a bishop moves by d ranks, then if bit i is the least significant set bit in d, both x and y coordinates will change in bit i.

[hgm]

You are probably right. But I want to port the code back to C later.

But then timing the Perl code might be meaningless; what is good for Perl might not be good for C.

[hgm]

Also with Perl?

man perlop

shows perl supporting these bitwise operations as well.

Sure, but the issue was whether the compiler would optimize it in the given way.