Color of a Square

From Chessprogramming wiki
Revision as of 19:36, 28 September 2018 by GerdIsenberg (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Home * Chess * Squares * Color of a Square

The Color of a Square of a 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 parity of the combined square index in the 0..63 range. Applications are mostly related square color bounded 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, containing the color of each square index. Alternatively one may use an In-Register Lookup, using a constant Bitboard representing all dark squares.

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 .

Shifting right this bitboard by square index, and masking off the least significant bit, leaves the square color:

enumColor colorOfSquare (enumSquare square) {
   U64 dark = C64(0xAA55AA55AA55AA55);
   return (dark >> square) & 1;
}

On x86 one may use a shorter 32-bit constant and 32-bit shift, since the 32-bit shift is implicitly modulo 32 ... [2]

enumColor colorOfSquare (enumSquare square) {
   return (0xAA55AA55 >> square) & 1; // return (0xAA55AA55 >> (square & 31 )) & 1; 
}

... which also works for 0x88 coordinates, since the In-Register lookup covers one even and odd 16-bit rank.

enumColor colorOfSquare (int x88square) {
   return (0x00AA0055 >> x88square) & 1;
}

By Anti-Diagonal Index

Another approach is based on whether the anti-diagonal index (sum of rank and 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 (black == 1 rather than 0), one additional toggleColor, aka xor with '1' is necessary:

enumColor colorOfSquare (enumSquare square) {
   return toggleColor( ((square >> 3) + square) & 1); // +-^
}

Same applies for the diagonal index as well (difference of rank and files), thus one can replace 'plus' by 'minus' or 'exclusive or', as shown in bitwise arithmetic.

A small transformation may save one register ...

enumColor colorOfSquare (enumSquare square) {
   return (( 9 * square + 8 ) >> 3) & 1;
}

... with following x86 assembly in mind:

  lea  eax, [8*eax + eax + 8]
  shr  eax, 3
  and  eax, 1

A boolean condition even saves the shift, but tests bit 3:

bool isDark (enumSquare square) {
   //return (( 9 * square + 8) & 8) != 0;
   return (( 9 * square) & 8) == 0;
}

... with this assembly in mind:

  lea  eax, [8*eax + eax]
  test eax, 8
  jz   isDark

Same color

The same tricks might be applied to determine two squares have the same color or not. If the sum of both anti-diagonal indices is odd, the color is different. Using xor (sq1 ^= sq2) to 'add' ranks and files simultaneously or SWAR-wise without possible overflows saves one instruction.

bool differentColor (enumSquare sq1, enumSquare sq2) {
   sq1 ^= sq2;
   return ( (sq1 >> 3) ^ sq1) & 1;
}

The mentioned lea-transformation saves one register and shift, if one jumps conditionally anyway...

bool differentColor (enumSquare sq1, enumSquare sq2) {
   return (( 9 * (sq1 ^ sq2)) & 8) != 0;
}

... also for the complement expression:

bool sameColor (enumSquare sq1, enumSquare sq2) {
   return (( 9 * (sq1 ^ sq2)) & 8) == 0;
}

Alternatively, if one has a Knight-Distance 64 x 64 array, one may use the least significant bit, since all even Knight-Distances between squares imply same square color.

See also

References

  1. Josef Albers - One Study for the Homage to the Square Series, Exhibition in Josef Albers Museum Quadrat, Bottrop, Photo by Gerd Isenberg, September 16, 2018
  2. Two small in-register-lookups by Gerd Isenberg, CCC, April 23, 2007

Up one Level