Home * Programming * Data * Butterfly Boards
Symmetry.jpg

Butterfly Boards
are two-dimensional arrays (typically of various history counters for each color), indexed by the from- and to-square coordinates of (valid and likely quiet) moves, which appear inside the search. Those counters can then be used for move ordering as mentioned in the history heuristic, or to decide about late move reductions and history leaf pruning. Another application is a kind of killer- or refutation table, to store a refutation of a specific move [1], also base of the countermove heuristic [2] [3].
M. C. Escher, Symmetry [4]

Layout

The size of the array is 4K (64 x 64 = 4096) elements for each color, but the density is poor, since most from- and to-square combinations are illegal moves by the rules of chess. Thus, most entries inside the Butterfly boards are not used. Also, as an additional drawback, from-to coordinates, specially those with distance one, are ambiguous and may be legal for several pieces. For instance e2-e3 might be a rook-, queen-, king- or white pawn-move. However, knight-, rook- and bishop moves are disjoint, queen moves are the superset from rook- and bishop-moves, king-moves the one-distance subset of queen moves, and pawn pushes are subset of rook-moves, while pawn captures and en passant (if stored at all) are subset of bishop-moves.

Therefor some programmers omit the origin from-square, but use piece-type instead for denser 12 x 64 tables with only 3/4K entries - or exclude not only captures, but also pawn pushes and/or king moves. Other programmers have abandoned hashing moves for History Heuristic and LMR, and say that given enough search depth, History counters produce just some random noise [5] .

This is how butterfly boards may be declared in C or C++:
counterType arrWhiteButterfly[64][64]; // from, to -> 4K
counterType arrBlackButterfly[64][64]; // from, to -> 4K
or
counterType arrButterfly[2][64][64]; // color, from, to -> 8K

Valid Entries

As mentioned in Influence Quantity of Pieces, there are only 1792 (7/16 of 4K) possible valid moves coordinates, 9/16 of the space in the Butterfly boards is "wasted".
Piece
covers other pieces
#
div 112 (7*16)
Rook
queen, king and pawn pushes
896
8
Bishop
queen, king and pawn captures
560
5
Knight
-
336
3
possible from-to move coordinates
1792
16

The Eponym

The name Butterfly Boards was proposed by Dap Hartmann in 1988, when he introduced the Butterfly Heuristic in the ICCA Journal [6], and the application of a Butterfly refutation table at the Advances in Computer Chess 6 conference in 1990 [7]. Plotting the illegal move coordinates as black cells # inside a 64*64 sheet, seven butterfly shaped pattern appear along the impossible move diagonal (where squares are equal).

The Butterfly

Single Shape

The thorax of the Butterfly is centered by the wraps from one rank (or dependent on the Square Mapping Considerations, one file) to the next one. With 'a1' as square null mapping, and 'd1' as square 3, 'e2' is square 12, the shape indexed by square coordinates looks as follows, covering two wrapped rank "halfs" including their center files, e.g. d1 - e2:
d e f g h a b c d e        d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2        1 1 1 1 1 2 2 2 2 2
#         #           d1   # - - - - # ~ \ | /
  #       # #         e1   - # - - - # # ~ \ |
    #     # # #       f1   - - # - - # # # ~ \
      #   # # # #     g1   - - - # - # # # # ~
        # # # # # #   h1   - - - - # # # # # #
# # # # # #           a2   # # # # # # - - - -
  # # # #   #         b2   ~ # # # # - # - - -
    # # #     #       c2   \ ~ # # # - - # - -
      # #       #     d2   | \ ~ # # - - - # -
        #         #   e2   / | \ ~ # - - - - #
That is why Dap Hartmann called it Butterfly Boards.

Connected Shapes

  • one butterfly spans a 10 square range
  • n butterflies span an 8*n + 2 square range
  • seven butterflies span 58 square range, from 3 (d1) to 60 (e8)
d e f g h a b c d e f g h a b c d e       d e f g h a b c d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3       1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3
#         #                          d1   # - - - - # ~ \ | / ~ # # # \ ~ | ~
  #       # #                        e1   - # - - - # # ~ \ | / ~ # # # \ ~ |
    #     # # #                      f1   - - # - - # # # ~ \ | / ~ # # # \ ~
      #   # # # #                    g1   - - - # - # # # # ~ \ | / # # # # \
        # # # # # #                  h1   - - - - # # # # # # ~ \ | # # # # #
# # # # # #                          a2   # # # # # # - - - - - - - | / ~ # #
  # # # #   #                        b2   ~ # # # # - # - - - - - - \ | / ~ #
    # # #     #                      c2   \ ~ # # # - - # - - - - - ~ \ | / ~
      # #       #         #          d2   | \ ~ # # - - - # - - - - # ~ \ | /
        #         #       # #        e2   / | \ ~ # - - - - # - - - # # ~ \ |
                    #     # # #      f2   ~ / | \ ~ - - - - - # - - # # # ~ \
                      #   # # # #    g2   # ~ / | \ - - - - - - # - # # # # ~
                        # # # # # #  h2   # # ~ / | - - - - - - - # # # # # #
                # # # # # #          a3   # # # # # | \ ~ # # # # # # - - - -
                  # # # #   #        b3   \ # # # # / | \ ~ # # # # - # - - -
                    # # #     #      c3   ~ \ # # # ~ / | \ ~ # # # - - # - -
                      # #       #    d3   | ~ \ # # # ~ / | \ ~ # # - - - # -
                        #         #  e3   ~ | ~ \ # # # ~ / | \ ~ # - - - - #

C-Code

Some arbitrary C-code, to produce the plot:
#include "stdafx.h"
#include <math.h>
 
void butterflyBoard(int from, int to) {
   int sq1, sq2, f1, f2, r1, r2, df, dr;
   int nr = 0, nb = 0, nn = 0;
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%c", (sq2 % 10) ? ' ' : '0' + (sq2/10) );
   printf("\n");
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%1d", sq2 % 10 );
   printf("\n");
   for (sq1 = from; sq1 <= to; sq1++) {
      for (sq2 = from; sq2 <= to; sq2++) {
         if ( sq1 != sq2 ) {
            r1 = sq1 >> 3;
            r2 = sq2 >> 3;
            if (r1 == r2) { // same rank
               nr++;
               printf("-");
               continue;
            }
            f1 = sq1 & 7;
            f2 = sq2 & 7;
            if ( f1 == f2 ) { // same file
               nr++;
               printf("|");
               continue;
            }
            if  (f1 - r1 == f2 - r2) { // same diagonal
               nb++;
               printf("/");
               continue;
            }
            if  (f1 + r1 == f2 + r2) { // same anti-diagonal
               nb++;
               printf("\\");
               continue;
            }
            df = abs (f2 - f1);
            dr = abs (r2 - r1);
            if ( df + dr == 3 )    { // knight distance
               nn++;
               printf("~");
               continue;
            }
         }
         printf("#"); // invalid
      }
      printf(" %2d\n", sq1);
   }
   printf("rook   moves %4d\n", nr);
   printf("bishop moves %4d\n", nb);
   printf("knight moves %4d\n", nn);
   printf("total  moves %4d\n", nr + nb + nn);
}
 
int main(int argc, char* argv[])
{
   butterflyBoard(3, 20); // 0, 63
   return 0;
}

Analogy in Astronomy

Dap Hartmann found a nice analogy in astronomy. Edward Maunders was the first astronomer (1904) to plot the distribution in heliographic latitude of the centers of sunspot groups as a functions of time:
Sunspot-bfly.gif
A modern version of the Mauders' sunspot "butterfly diagram" [8] .

See also


Publications


External links

Wikipedia

Butterflies from Wikipedia [9]

Musicvideo


References

  1. ^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
  2. ^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
  3. ^ Re: History pruning / move ordering question by Don Dailey, CCC, May 10, 2013
  4. ^ Picture gallery "Symmetry" from The Official M.C. Escher Website
  5. ^ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007
  6. ^ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
  7. ^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
  8. ^ Edward Walter Maunder, Solar observations A modern version of the Mauders' sunspot "butterfly diagram". (This version from the solar group at NASA Marshall Space Flight Center.)
  9. ^ Butterfly (disambiguation) from Wikipedia
  10. ^ Fast Fourier Transform (FFT) from Reliable Software

What links here?


Up one Level