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)
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:
A modern version of the Mauders' sunspot "butterfly diagram" [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.)
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].
Table of Contents
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++:
or
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".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
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: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:See also
Publications
External links
Wikipedia
Butterflies from Wikipedia [9]Musicvideo
References
What links here?
Up one Level