Mapping of squares for BitBoard.

[Fguy64]

Greetings, I was just looking into this. The standard mapping, which I have seen termed "little endian", starts with the least significant bit mapped to square a1 and the most significant bit mapped to h8. Apparently there is some sort of mathematical advantage to this mapping.

I am wondering if this so called "mathematical advantage" is just a c++ thing, which depends on the way c++ lays out it's arrays.

I have always worked with arrays or strings in java, and I know in java I have always thought of array element (0,0), or just index=0 in the case of a string, as square a8 and array element (7,7) or index=63 as square h1. Which is the same general layout as a fen string.

So the question is whether or not so called optimal bit/square mappings are language dependant.

Thanks.

bit to square is completely irrelevant. But you want to make the LSB bit number 0, the MSB as bit 63, because that is how the BSF/BSR instructions number the bits. So long as you keep the rightmost bit as bit zero, you are set. Doesn't matter whether you map bit 0 to a1, h1, a8 or h8.

In Crafty, when I renumbered things, I went thru a bit of an interesting mapping, as for me, bit 0 is a1, bit 7 is h1, ... bit 56 is a8, bit 63 is h8. If you look at a bitboard and want to visualize it, you have to mentally look at it through a mirror. I don't find this hard at all, although at first it took some concentration.

Indeed. Much more of this kind of thing and in a real chess game I'm gonna have to face away from the board and look into a mirror in order to analyze.

Anyways, thanks, your answer intuitively makes sense. At first I was thinking about the mapping between bit positions and the indexes of an expanded position string, but that is irrelevant for the way things are actually coded.

And here's a thought.. I suppose the most visually intuitive might be to map MSB to a8 and LSB to h1, and if it really doesn't matter from a coding perspective, to my that seems to eliminate the aforementioned mirror effect, I just have to wipe the concept of fen String from my mind.

[Harald]

I suppose the most visually intuitive might be to map MSB to a8 and LSB to h1, ...

That is my mapping in Elephant. I read the hex numbers and can easily
see the bits and pieces on the bitboard. (0=h1, 7=a1, 56=h8, 63=a8)

Many people write about algorithms in chess programming but forget
to mention the bit-square-mapping. Especially in themes like
assembler code or magic multiplication constants. That is annoying.
You always have to be aware of this problem.

Harald

[bob]

bit to square is completely irrelevant. But you want to make the LSB bit number 0, the MSB as bit 63, because that is how the BSF/BSR instructions number the bits.
So long as you keep the rightmost bit as bit zero, you are set.

I think LSB and MSB are defined by their arithmetical significance rather than how bitscan (or leading/trailing zero) count work, and what is first one or last one or left/right top/down. 0 or 2^0 is less significant than 63 or 2^63.

Anyway, you are right that any of the eight possible orthogonal mappings from 6-bit indices to 64 squares is fine and a matter of taste. I use the same mapping than you. Otherwise one may enumerate files a-h from 0..7 or 7..0, ranks from 1-8 -> 0..7 or 7..0, with 4 possible combinations in total. Additionally for the one-dimensional 8*8 array one may use rank or file at the little end, in total eight different orthogonal mappings.

Depends. The Cray computers had a "leadz" instruction rather than a find first 1 or find last 1 instruction. If the leftmost (MSB) was set, it returned a zero. This is why Crafty originally used that mapping of bit location to bit number. Until 22.0 or somewhere in there, bit 0 was MSB. I then changed it _everywhere_ to be the LSB. Huge change. But it eliminated the BSR/BSF kludge where I had to do something like return (63 - BSF(bitboard)); to map BSF/BSR numbers into the crafty numbers.

I chose the more difficult mapping I use as it seems more natural for a=0, b=1, h=7, for the files. Which means everything looks like it is being viewed through a mirror where up and down remain correct, but left and right are reversed. I've made a few mistakes since making this change, but have now gotten used to it and have had no further problems. It was a mind-bending change at first, however.

[bob]

Greetings, I was just looking into this. The standard mapping, which I have seen termed "little endian", starts with the least significant bit mapped to square a1 and the most significant bit mapped to h8. Apparently there is some sort of mathematical advantage to this mapping.

I am wondering if this so called "mathematical advantage" is just a c++ thing, which depends on the way c++ lays out it's arrays.

I have always worked with arrays or strings in java, and I know in java I have always thought of array element (0,0), or just index=0 in the case of a string, as square a8 and array element (7,7) or index=63 as square h1. Which is the same general layout as a fen string.

So the question is whether or not so called optimal bit/square mappings are language dependant.

Thanks.

bit to square is completely irrelevant. But you want to make the LSB bit number 0, the MSB as bit 63, because that is how the BSF/BSR instructions number the bits. So long as you keep the rightmost bit as bit zero, you are set. Doesn't matter whether you map bit 0 to a1, h1, a8 or h8.

In Crafty, when I renumbered things, I went thru a bit of an interesting mapping, as for me, bit 0 is a1, bit 7 is h1, ... bit 56 is a8, bit 63 is h8. If you look at a bitboard and want to visualize it, you have to mentally look at it through a mirror. I don't find this hard at all, although at first it took some concentration.

Indeed. Much more of this kind of thing and in a real chess game I'm gonna have to face away from the board and look into a mirror in order to analyze.

Anyways, thanks, your answer intuitively makes sense. At first I was thinking about the mapping between bit positions and the indexes of an expanded position string, but that is irrelevant for the way things are actually coded.

And here's a thought.. I suppose the most visually intuitive might be to map MSB to a8 and LSB to h1, and if it really doesn't matter from a coding perspective, to my that seems to eliminate the aforementioned mirror effect, I just have to wipe the concept of fen String from my mind.

For all my debugging, I have functions that print the bitboards out in a more "bearable" format so that they match to the normal board. But when designing constants or bitmasks for various things, it is something to do when wide awake, not when drowsy.

The only problem with your scheme is that a=7, h=0, which seems counter-intuitive to me. Not that it is any worse than what I am doing, of course.

[Gerd Isenberg]

I suppose the most visually intuitive might be to map MSB to a8 and LSB to h1, ...

That is my mapping in Elephant. I read the hex numbers and can easily
see the bits and pieces on the bitboard. (0=h1, 7=a1, 56=h8, 63=a8)

Ok, I'll vote to write numbers little-endian wise as well, at least hex or binaries - or alternatively to swap the file enumeration on the chess-board

On little-endian rank-file mapping, I like the "natural" relation - that is a < h and 0 < 7, and not mixing rank- and file-endianess. Anyway I am aware of the problems, and already have a small bitboard calculator, where I can paste number stings via clipboard (even FEN as pure occupancy) to display the bit-board.

Many people write about algorithms in chess programming but forget to mention the bit-square-mapping. Especially in themes like assembler code or magic multiplication constants. That is annoying. You always have to be aware of this problem.

Do you mean cpw? We have the Square Mapping Considerations page, which is often linked from other pages, like Best Magics so far, but probably not often enough. Yes, I miss backlinks from magics and kindergarten, Ok, I will change that. Harald, feel free to correct stuff there as well. It is quite hard to keep all up to date and linked together.

Cheers,
Gerd

[bob]

I suppose the most visually intuitive might be to map MSB to a8 and LSB to h1, ...

That is my mapping in Elephant. I read the hex numbers and can easily
see the bits and pieces on the bitboard. (0=h1, 7=a1, 56=h8, 63=a8)

Ok, I'll vote to write numbers little-endian wise as well, at least hex or binaries - or alternatively to swap the file enumeration on the chess-board

On little-endian rank-file mapping, I like the "natural" relation - that is a < h and 0 < 7, and not mixing rank- and file-endianess. Anyway I am aware of the problems, and already have a small bitboard calculator, where I can paste number stings via clipboard (even FEN as pure occupancy) to display the bit-board.

Many people write about algorithms in chess programming but forget to mention the bit-square-mapping. Especially in themes like assembler code or magic multiplication constants. That is annoying. You always have to be aware of this problem.

Do you mean cpw? We have the Square Mapping Considerations page, which is often linked from other pages, like Best Magics so far, but probably not often enough. Yes, I miss backlinks from magics and kindergarten, Ok, I will change that. Harald, feel free to correct stuff there as well. It is quite hard to keep all up to date and linked together.

Cheers,
Gerd

I use two macros everywhere, File(square) and Rank(square). I wanted to be able to use the normal idea of a file is < c file, f file is > c file, ditto for the ranks. This makes some comparisons (is this an outside passed pawn) and such more logical when reading them. Of course, parsing also makes more sense, since square = file<<3 + rank. and for conversions, charfile = 'a' + File(square) and so forth.

When I made this conversion from the old cray numbering scheme, I gave it a _lot_ of thought before moving forward, because I knew it was going to be more than a little painful since all the masks I had hard-coded would have to be changed. And I wanted this to be the +last+ time I would make a change like this.

[Harald]

Many people write about algorithms in chess programming but forget to mention the bit-square-mapping. Especially in themes like assembler code or magic multiplication constants. That is annoying. You always have to be aware of this problem.

Do you mean cpw? We have the Square Mapping Considerations page, which is often linked from other pages, like Best Magics so far, but probably not often enough. Yes, I miss backlinks from magics and kindergarten, Ok, I will change that. Harald, feel free to correct stuff there as well. It is quite hard to keep all up to date and linked together.

No, that page is pretty good. I like cpw very much. You do very good
work there and I am far too lazy to contribute. Shame on me.

I thought more of some random postings here and there and everywhere
where people are discussing interesting ideas or algorithms, and use
masks or constants without even noticing that these are depending on
square mapping. When I started chess programming i fell into that trap
a few times. I want to warn the novice reader about that fact and want
to encourage each expert to give a little hint when he writes a bigger
portion of his knowledge or if he starts a new thread.

Are magics mapping dependent? Is there a way to re-map or re-order
them or must the magics be re-invented for every mapping?

[Greg Strong]

Here's something else you might want to consider. I posted in another thread a technique to evaluate pawn structures with SSE instructions very quickly and with very few instructions, but it requires the bits of a file to be stored consecutively.

Here's the description...

http://talkchess.com/forum/viewtopic.ph ... =&start=10

[Gerd Isenberg]

Are magics mapping dependent? Is there a way to re-map or re-order them or must the magics be re-invented for every mapping?

No, magics are quite independent from square mapping. Only their indexing and interpretation of pre- and post-masks is square mapping dependent. If we use bitindex 0..63 in the arithmetical sense, but no square coordinates, the table from Best Magics so far is general.

[bob]

Are magics mapping dependent? Is there a way to re-map or re-order them or must the magics be re-invented for every mapping?

No, magics are quite independent from square mapping. Only their indexing and interpretation of pre- and post-masks is square mapping dependent. If we use bitindex 0..63 in the arithmetical sense, but no square coordinates, the table from Best Magics so far is general.

Are there any complete magic tables posted anywhere? IE with the best so far found???