Distinguish rook and bishop move efficiently

[gflohr]

Given a starting square (0 to 63) and a destination square (0 to 63) and given that the move constituted by that is either a rook or a bishop move, what is the most efficient way to distinguish rook from bishop moves?

Using the distance is not very helpful because there is an ambiguity for the distance of 56 resp. -56.

I think, in C, the answer is clear. I precompute a lookup table and then do something like:

Code: Select all

is_rook_move = rook_moves[from << 6 | to]

But I want to use a scripting language and would like to avoid the potentially expensive array lookup. Does the combination of to and from have any fancy properties that can be used instead?

[RubiChess]

Assuming your script language can do bitwise operation you can use

Code: Select all

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

[lithander]

Assuming your script language can do bitwise operation you can use

Code: Select all

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

And this is how that code works:

The first 3 bits of the square encode the file. The next 3 bits encode the rank. To catch only those bits you mask with either 7 (000111) or 56 (111000).

The bishop can not move without changing both the rank and the file, so when the file has not changed OR the rank has not changed it must be a Rook.

[amanjpro]

Given a starting square (0 to 63) and a destination square (0 to 63) and given that the move constituted by that is either a rook or a bishop move, what is the most efficient way to distinguish rook from bishop moves?

Using the distance is not very helpful because there is an ambiguity for the distance of 56 resp. -56.

I think, in C, the answer is clear. I precompute a lookup table and then do something like:

Code: Select all

is_rook_move = rook_moves[from << 6 | to]

But I want to use a scripting language and would like to avoid the potentially expensive array lookup. Does the combination of to and from have any fancy properties that can be used instead?

Bishop moves will always change the file and rank. Rook will either maintain the file but changes the rank, or the other way around.

Now it really depends on the way you represent the move to check the above properties

[R. Tomasi]

Assuming your script language can do bitwise operation you can use

Code: Select all

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

And this is how that code works:

The first 3 bits of the square encode the file. The next 3 bits encode the rank. To catch only those bits you mask with either 7 (000111) or 56 (111000).

The bishop can not move without changing both the rank and the file, so when the file has not changed OR the rank has not changed it must be a Rook.

If your scripting language does not support bitwise & operations you can replace these by division and modulo operations (which may be costly, though). There is a subtlety concerning how you encode the squares of the board (rank or file in the lower bits?), however in that particular case it does not make a difference, since you are interesed in detecting if both change.

[gflohr]

Cool! That works!

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

Code: Select all

(((from & 7) == (to & 7)) | ((from & 56) == (to & 56)))

The scripting language is Perl and it supports all the bitwise operations that C has.

[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.

[hgm]

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.

Otherwise I would go for kind[from^to], where kind[] is a 64-element array of Booleans. The expression from^to is not ambiguous, as diagonal moves must always changes both the rank and file (and thus from^to will always have some non-zero bits in the file bits as well as the rank bits). While orthogonal moves will always have either the rank change or the file change zero.

[tcusr]

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.

Otherwise I would go for kind[from^to], where kind[] is a 64-element array of Booleans. The expression from^to is not ambiguous, as diagonal moves must always changes both the rank and file (and thus from^to will always have some non-zero bits in the file bits as well as the rank bits). While orthogonal moves will always have either the rank change or the file change zero.

sorry for the stupid question but what kind of correlation between f and t does f^t give?
for example i've seen it to detect pawn double pushes ((f ^ t) == 16) but i don't understand it

[hgm]

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.