25,161
edits
Changes
Created page with "'''Home * Chess * Squares * Color of a Square''' The '''Color of a Square''' of a 8x8 board may be determined by several approaches. Since..."
'''[[Main Page|Home]] * [[Chess]] * [[Squares]] * Color of a Square'''
The '''Color of a Square''' of a [[8x8 Board|8x8 board]] may be determined by several approaches. Since the number of files (and ranks) is even, and black and white colors alternate on consecutive ranks (and files), one can not use the simple [https://en.wikipedia.org/wiki/Parity_%28mathematics%29 parity] of the combined square index in the 0..63 range. Applications are mostly related square color bounded [[Bishop|bishops]], for instance to find the right corners in [[KBNK Endgame]].
=By Lookup=
The obvious approach is a memory lookup of a pre-calculated 64 byte [[Array|array]], containing the color of each square index. Alternatively one may use an In-Register Lookup, using a constant [[Bitboards|Bitboard]] representing all dark squares.
<pre>
0xAA55AA55AA55AA55
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
</pre>
Shifting right this bitboard by square index, and masking off the least significant bit, leaves the square color:
<pre>
enumColor colorOfSquare (enumSquare square) {
U64 dark = C64(0xAA55AA55AA55AA55);
return (dark >> square) & 1;
}
</pre>
On [[x86]] one may use a shorter 32-bit constant and 32-bit shift, since the 32-bit shift is implicitly modulo 32 ... <ref>[http://www.talkchess.com/forum/viewtopic.php?t=13344 Two small in-register-lookups] by [[Gerd Isenberg]], [[CCC]], April 23, 2007</ref>
<pre>
enumColor colorOfSquare (enumSquare square) {
return (0xAA55AA55 >> square) & 1; // return (0xAA55AA55 >> (square & 31 )) & 1;
}
</pre>
... which also works for [[0x88]] coordinates, since the In-Register lookup covers one even and odd 16-bit rank.
<pre>
enumColor colorOfSquare (int x88square) {
return (0x00AA0055 >> x88square) & 1;
}
</pre>
=By Anti-Diagonal Index=
Another approach is based on whether the [[Anti-Diagonals|anti-diagonal]] index (sum of [[Ranks|rank]] and [[Files|files]]) is odd or even. An even index (bit 0 clear) implies a black or dark square, an odd index light or white squares. Since we need to mask off the least significant bit only, we can save masking off the file from square, because upper bits have no influence on bit zero anyway. To be conform with the arbitrary [[Color#Definition|color definition]] (black == 1 rather than 0), one additional toggleColor, aka xor with '1' is necessary:
<pre>
enumColor colorOfSquare (enumSquare square) {
return toggleColor( ((square >> 3) + square) & 1); // +-^
}
</pre>
Same applies for the [[Diagonals|diagonal]] index as well (difference of [[Ranks|rank]] and [[Files|files]]), thus one can replace 'plus' by 'minus' or [[General Setwise Operations#ExclusiveOr|'exclusive or']], as shown in [[Bit#BitwiseArithmetic|bitwise arithmetic]].
A small transformation may save one register ...
<pre>
enumColor colorOfSquare (enumSquare square) {
return (( 9 * square + 8 ) >> 3) & 1;
}
</pre>
... with following [[x86]] assembly in mind:
<pre>
lea eax, [8*eax + eax + 8]
shr eax, 3
and eax, 1
</pre>
A boolean condition even saves the shift, but tests bit 3:
<pre>
bool isDark (enumSquare square) {
//return (( 9 * square + 8) & 8) != 0;
return (( 9 * square) & 8) == 0;
}
</pre>
... with this assembly in mind:
<pre>
lea eax, [8*eax + eax]
test eax, 8
jz isDark
</pre>
<span id="SameColor"></span>
=Same color=
The same tricks might be applied to determine two squares have the same color or not. If the sum of both [[Anti-Diagonals|anti-diagonal]] indices is odd, the color is different. Using xor (sq1 ^= sq2) to 'add' ranks and files simultaneously or [[SIMD and SWAR Techniques#SWAR|SWAR-wise]] without possible overflows saves one instruction.
<pre>
bool differentColor (enumSquare sq1, enumSquare sq2) {
sq1 ^= sq2;
return ( (sq1 >> 3) ^ sq1) & 1;
}
</pre>
The mentioned lea-transformation saves one register and shift, if one jumps conditionally anyway...
<pre>
bool differentColor (enumSquare sq1, enumSquare sq2) {
return (( 9 * (sq1 ^ sq2)) & 8) != 0;
}
</pre>
... also for the complement expression:
<pre>
bool sameColor (enumSquare sq1, enumSquare sq2) {
return (( 9 * (sq1 ^ sq2)) & 8) == 0;
}
</pre>
Alternatively, if one has a [[Knight-Distance]] 64 x 64 [[Array|array]], one may use the least significant bit, since all even Knight-Distances between squares imply same square color.
=See also=
* [[Anti-Diagonals]]
* [[Bishops of Opposite Colors]]
* [[Color]]
* [[Diagonals]]
* [[KBNK Endgame]]
* [[Knight-Distance]]
* [[Wrong color Bishop and Rook Pawn]]
=References=
<references />
'''[[Squares|Up one Level]]'''
The '''Color of a Square''' of a [[8x8 Board|8x8 board]] may be determined by several approaches. Since the number of files (and ranks) is even, and black and white colors alternate on consecutive ranks (and files), one can not use the simple [https://en.wikipedia.org/wiki/Parity_%28mathematics%29 parity] of the combined square index in the 0..63 range. Applications are mostly related square color bounded [[Bishop|bishops]], for instance to find the right corners in [[KBNK Endgame]].
=By Lookup=
The obvious approach is a memory lookup of a pre-calculated 64 byte [[Array|array]], containing the color of each square index. Alternatively one may use an In-Register Lookup, using a constant [[Bitboards|Bitboard]] representing all dark squares.
<pre>
0xAA55AA55AA55AA55
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
. 1 . 1 . 1 . 1
1 . 1 . 1 . 1 .
</pre>
Shifting right this bitboard by square index, and masking off the least significant bit, leaves the square color:
<pre>
enumColor colorOfSquare (enumSquare square) {
U64 dark = C64(0xAA55AA55AA55AA55);
return (dark >> square) & 1;
}
</pre>
On [[x86]] one may use a shorter 32-bit constant and 32-bit shift, since the 32-bit shift is implicitly modulo 32 ... <ref>[http://www.talkchess.com/forum/viewtopic.php?t=13344 Two small in-register-lookups] by [[Gerd Isenberg]], [[CCC]], April 23, 2007</ref>
<pre>
enumColor colorOfSquare (enumSquare square) {
return (0xAA55AA55 >> square) & 1; // return (0xAA55AA55 >> (square & 31 )) & 1;
}
</pre>
... which also works for [[0x88]] coordinates, since the In-Register lookup covers one even and odd 16-bit rank.
<pre>
enumColor colorOfSquare (int x88square) {
return (0x00AA0055 >> x88square) & 1;
}
</pre>
=By Anti-Diagonal Index=
Another approach is based on whether the [[Anti-Diagonals|anti-diagonal]] index (sum of [[Ranks|rank]] and [[Files|files]]) is odd or even. An even index (bit 0 clear) implies a black or dark square, an odd index light or white squares. Since we need to mask off the least significant bit only, we can save masking off the file from square, because upper bits have no influence on bit zero anyway. To be conform with the arbitrary [[Color#Definition|color definition]] (black == 1 rather than 0), one additional toggleColor, aka xor with '1' is necessary:
<pre>
enumColor colorOfSquare (enumSquare square) {
return toggleColor( ((square >> 3) + square) & 1); // +-^
}
</pre>
Same applies for the [[Diagonals|diagonal]] index as well (difference of [[Ranks|rank]] and [[Files|files]]), thus one can replace 'plus' by 'minus' or [[General Setwise Operations#ExclusiveOr|'exclusive or']], as shown in [[Bit#BitwiseArithmetic|bitwise arithmetic]].
A small transformation may save one register ...
<pre>
enumColor colorOfSquare (enumSquare square) {
return (( 9 * square + 8 ) >> 3) & 1;
}
</pre>
... with following [[x86]] assembly in mind:
<pre>
lea eax, [8*eax + eax + 8]
shr eax, 3
and eax, 1
</pre>
A boolean condition even saves the shift, but tests bit 3:
<pre>
bool isDark (enumSquare square) {
//return (( 9 * square + 8) & 8) != 0;
return (( 9 * square) & 8) == 0;
}
</pre>
... with this assembly in mind:
<pre>
lea eax, [8*eax + eax]
test eax, 8
jz isDark
</pre>
<span id="SameColor"></span>
=Same color=
The same tricks might be applied to determine two squares have the same color or not. If the sum of both [[Anti-Diagonals|anti-diagonal]] indices is odd, the color is different. Using xor (sq1 ^= sq2) to 'add' ranks and files simultaneously or [[SIMD and SWAR Techniques#SWAR|SWAR-wise]] without possible overflows saves one instruction.
<pre>
bool differentColor (enumSquare sq1, enumSquare sq2) {
sq1 ^= sq2;
return ( (sq1 >> 3) ^ sq1) & 1;
}
</pre>
The mentioned lea-transformation saves one register and shift, if one jumps conditionally anyway...
<pre>
bool differentColor (enumSquare sq1, enumSquare sq2) {
return (( 9 * (sq1 ^ sq2)) & 8) != 0;
}
</pre>
... also for the complement expression:
<pre>
bool sameColor (enumSquare sq1, enumSquare sq2) {
return (( 9 * (sq1 ^ sq2)) & 8) == 0;
}
</pre>
Alternatively, if one has a [[Knight-Distance]] 64 x 64 [[Array|array]], one may use the least significant bit, since all even Knight-Distances between squares imply same square color.
=See also=
* [[Anti-Diagonals]]
* [[Bishops of Opposite Colors]]
* [[Color]]
* [[Diagonals]]
* [[KBNK Endgame]]
* [[Knight-Distance]]
* [[Wrong color Bishop and Rook Pawn]]
=References=
<references />
'''[[Squares|Up one Level]]'''
