0x88 move generation

[Jorma Nieminen]

Is there any quick bit manipulation trick to get the rank and file of a square on a board that is based on 0x88 representation, in other words 128-element array?

thanks,
Jorma

[wgarvin]

Code: Select all

file = square & 7;
rank = square >> 4;

More info can be found at the chessprogramming wiki.

[Jorma Nieminen]

Thanks, there seems to be quite a lot information about 0x88 at that website.

Jorma

[Suji]

Here's another question for you, how and why do those tricks help?

[Edmund]

Here's another question for you, how and why do those tricks help?

Anything else is slower, shifts and logical operations are some of the low level cpu instructions.

How else would you do it?

[Suji]

I'm not sure, and looping through all the squares is intuitively slow.

Where and how do you use the tricks? I'm thinking about looping through the squares in my engine just for simplicity.

[Edmund]

I'm not sure, and looping through all the squares is intuitively slow.

Where and how do you use the tricks? I'm thinking about looping through the squares in my engine just for simplicity.

for 0x88 these bit-twiddling tricks are not much use, it is different with bitboard representation. In your board representation the only alternative to looping through the board would be to keep a separate piece list which might speed up things a little.

However to calculate the row or file given a certain square these tricks do help a lot. The length of a row is 16 squares. In bit representation this takes exactly (log2 16 =) 4 bits to store. This is the lower 4 bits. The 8 rows take exactly (log2 8 =) 3 bits to store. This is the upper 3 bits.

So if you for example take square 18, in bit representation this would be:
0010010

This can now be split up in rows and files. The lower 4 bits (lower bits means the numbers to the right) are 0010. If you convert this to decimal this gives 2. So the square is on file 2. The upper 3 bits are 001, which gives 1 in decimal. So the square is on row 1. Note that files and rows start counting at 0.

this calculation can also be performed by the computer:
to get the file you calculate sq & 7. 7 in bitrepresentation is 0000111. So by calculating & 7 the result only copies the lower 3 bits. Note that the forth bit is not used as it is only 1 if the square is on files 8-15, which is invalid.
to get the row you calculate sq >> 4. This shifts the sq 4 bits to the right. So only the upper 3 bits containing the row remain.

[MattieShoes]

They can be useful in eval -- keeping track of whether there's a pawn in each file, etc.