thankshgm wrote: ↑Tue Sep 14, 2021 5:50 pm 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.
Distinguish rook and bishop move efficiently
Moderators: hgm, Rebel, chrisw
-
- Posts: 323
- Joined: Tue Aug 31, 2021 10:32 pm
- Full name: tcusr
Re: Distinguish rook and bishop move efficiently
-
- Posts: 35
- Joined: Sun May 02, 2021 10:23 pm
- Full name: John Tromp
Re: Distinguish rook and bishop move efficiently
> is_rook_move = ((from & 7) == (to & 7) or (from & 56) == (to & 56))
is more efficient...
Code: Select all
is_rook_move(from, to) {
int x = from ^ to;
return !(x/8 & x);
}
-
- Posts: 179
- Joined: Tue Jun 15, 2021 8:11 pm
- Full name: Emanuel Torres
Re: Distinguish rook and bishop move efficiently
But not the same though? That method gives:tromp wrote: ↑Tue Sep 14, 2021 11:45 pm > is_rook_move = ((from & 7) == (to & 7) or (from & 56) == (to & 56))
is more efficient...Code: Select all
is_rook_move(from, to) { int x = from ^ to; return !(x/8 & x); }
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);
}
[Moderation warning] This signature violated the rule against commercial exhortations.
-
- Posts: 35
- Joined: Sun May 02, 2021 10:23 pm
- Full name: John Tromp
Re: Distinguish rook and bishop move efficiently
Your example fails the condition "given that the move constituted by that is either a rook or a bishop move".But not the same though? That method gives:
is_rook_move(0b000'110, 0b100'111) = true
The 2nd line should have a logical, not bitwise, or: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); }
Code: Select all
return !(x & 7) || !(x & 56);
Code: Select all
return !( x&7 && x&56 );
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.
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Distinguish rook and bishop move efficiently
Also with Perl?klx wrote: ↑Wed Sep 15, 2021 3:13 am 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); }
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.tromp wrote: ↑Wed Sep 15, 2021 9:05 amThe 2nd line should have a logical, not bitwise, or: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.Code: Select all
return !( x&7 && x&56 );
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.
I am also not convinced that !(x >> 8 & x) would be faster than kind[x].
-
- Posts: 57
- Joined: Fri Jul 23, 2021 5:24 pm
- Location: Elin Pelin
- Full name: Guido Flohr
Re: Distinguish rook and bishop move efficiently
Just for the records: In Perl the "or" has to be replaced by "||" because the "or" operator has the lowest precedence of all operators.
-
- Posts: 57
- Joined: Fri Jul 23, 2021 5:24 pm
- Location: Elin Pelin
- Full name: Guido Flohr
Re: Distinguish rook and bishop move efficiently
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.
-
- Posts: 35
- Joined: Sun May 02, 2021 10:23 pm
- Full name: John Tromp
Re: Distinguish rook and bishop move efficiently
man perlop
shows perl supporting these bitwise operations as well.
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.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.
Last edited by tromp on Wed Sep 15, 2021 10:35 am, edited 2 times in total.
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller