Butterfly Boards
Home * Programming * Data * Butterfly Boards
Butterfly Boards,
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 [2], also base of the countermove heuristic [3] [4].
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++:
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 (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:
A modern version of the Mauders' sunspot "butterfly diagram" [8] .
See also
- Bobby's Strategic Quiescence Search
- Butterfly Heuristic
- Countermove Heuristic
- History Heuristic
- History Leaf Pruning
- Late Move Reductions
- Monarch
- Refutation Table
- Relative History Heuristic
Publications
- Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
- Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
- Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
- Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
External links
Wikipedia
Butterflies from Wikipedia [9]
- Butterfly insect of the order Lepidoptera
- Butterfly Game a two-player abstract strategy game from Mozambique
- BBN Butterfly a massively parallel computer from the 1980s
- Butterfly diagram in the context of fast Fourier transform [10] algorithms
- Butterfly or Zassenhaus lemma
- Schmetterlingsgraph (German)
- Butterfly knot
- Butterfly theorem in elementary geometry
- Butterfly curve (algebraic)
- Butterfly curve (transcendental)
- Butterfly catastrophe Catastrophe theory
- Butterfly options a combination option trade strategy
- Iron Butterfly spread
- Iron Butterfly (band)
- Butterfly ballot
- Butterfly effect in the context of Chaos theory
- The Butterfly Effect (Film)
- The Butterfly Effect (band)
Misc
- Herbie Hancock & The Headhunters, Butterfly, 1974, YouTube Video
References
- ↑ Picture gallery "Symmetry" from The Official M.C. Escher Website
- ↑ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
- ↑ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
- ↑ Re: History pruning / move ordering question by Don Dailey, CCC, May 10, 2013
- ↑ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007
- ↑ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
- ↑ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
- ↑ 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.)
- ↑ Butterfly (disambiguation) from Wikipedia
- ↑ Fast Fourier Transform (FFT) from Reliable Software
