25,161
edits
Changes
Created page with "'''Home * Programming * Data * Butterfly Boards''' FILE:EscherSymmetry.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/symmetry-bmp/E70.jp..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * Butterfly Boards'''
[[FILE:EscherSymmetry.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/symmetry-bmp/E70.jpg|[[Arts#Escher|M. C. Escher]], Symmetry <ref>[http://www.mcescher.com/Gallery/gallery-symmetry.htm Picture gallery "Symmetry"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''Butterfly Boards''',<br/>
two-dimensional [[Array|arrays]] (typically of various history counters for each color), indexed by the [[Origin Square|from-]] and [[Target Square|to-square]] coordinates of (valid and likely [[Quiet Moves|quiet]]) [[Moves|moves]], which appear inside the [[Search|search]]. Those counters can then be used for [[Move Ordering|move ordering]] as mentioned in the [[History Heuristic|history heuristic]], or to decide about [[Late Move Reductions|late move reductions]] and [[History Leaf Pruning|history leaf pruning]]. Another application is a kind of [[Killer Heuristic |killer-]] or [[Refutation Table|refutation table]], to store a refutation of a specific move <ref>[[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]</ref>, also base of the [[Countermove Heuristic|countermove heuristic]] <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47953&start=2 Re: History pruning / move ordering question] by [[Don Dailey]], [[CCC]], May 10, 2013</ref>.
=Layout=
The size of the [[Array|array]] is 4K (64 x 64 = 4096) elements for each color, but the density is poor, since most [[Origin Square|from-]] and [[Target Square|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|distance]] one, are ambiguous and may be legal for several [[Pieces|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 Push|pawn pushes]] are subset of rook-moves, while pawn captures and [[En passant|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 [[Late Move Reductions|LMR]], and say that given enough search depth, History counters produce just some random noise <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=163477&t=18345 Re: LMR: history or not?] by [[Robert Hyatt]] from [[Computer Chess Forums|CCC]], December 13, 2007</ref> .
This is how butterfly boards may be declared in [[C]] or [[Cpp|C++]]:
<pre>
counterType arrWhiteButterfly[64][64]; // from, to -> 4K
counterType arrBlackButterfly[64][64]; // from, to -> 4K
</pre>
or
<pre>
counterType arrButterfly[2][64][64]; // color, from, to -> 8K
</pre>
=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".
{| class="wikitable"
|-
! Piece
! covers other pieces
! #
! div (7*16)
|-
! Rook
| style="text-align:left;" | queen, king and pawn pushes
| style="text-align:right;" | 896
| style="text-align:right;" | 8
|-
! Bishop
| style="text-align:left;" | queen, king and pawn captures
| style="text-align:right;" | 560
| style="text-align:right;" | 5
|-
! Knight
| style="text-align:center;" | -
| style="text-align:right;" | 336
| style="text-align:right;" | 3
|-
! colspan="2" | possible from-to move coordinates
| style="text-align:right;" | 1792
| style="text-align:right;" | 16
|}
=The Eponym=
The name Butterfly Boards was proposed by [[Dap Hartmann]] in 1988, when he introduced the [[Butterfly Heuristic]] in the [[ICGA Journal|ICCA Journal]] <ref>[[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]</ref>, and the application of a Butterfly [[Refutation Table|refutation table]] at the [[Advances in Computer Chess 6]] conference in 1990 <ref>[[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]</ref>. Plotting the illegal move coordinates as black cells '''#''' inside a 64*64 sheet, seven [https://en.wikipedia.org/wiki/Butterfly butterfly] shaped pattern appear along the impossible move diagonal (where squares are equal).
=The Butterfly=
==Single Shape==
The [https://en.wikipedia.org/wiki/Thorax 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:
<pre>
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 / | \ ~ # - - - - #
</pre>
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)
<pre>
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 ~ | ~ \ # # # ~ / | \ ~ # - - - - #
</pre>
=C-Code=
Some arbitrary [[C]]-code, to produce the plot:
<pre>
#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;
}
</pre>
=Analogy in Astronomy=
[[Dap Hartmann]] found a nice analogy in astronomy. [https://en.wikipedia.org/wiki/Edward_Walter_Maunder Edward Maunders] was the first astronomer (1904) to plot the distribution in [http://www.answers.com/topic/heliographic-latitude heliographic latitude] of the centers of [http://www.ips.gov.au/Educational/2/2/3 sunspot groups] as a functions of time:
[[FILE:Sunspot-bfly.gif|none|border|800px|text-bottom]]
A modern version of the Mauders' sunspot "butterfly diagram" <ref>[https://en.wikipedia.org/wiki/Edward_Walter_Maunder#Solar_observations 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.)</ref> .
=See also=
* [[Bobby#StrategicQuiescenceSearch|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''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
* [[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|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''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
=External links=
==Wikipedia==
Butterflies from [https://en.wikipedia.org/wiki/Main_Page Wikipedia] <ref>[https://en.wikipedia.org/wiki/Butterfly_%28disambiguation%29 Butterfly (disambiguation) from Wikipedia]</ref>
* [https://en.wikipedia.org/wiki/Butterfly Butterfly insect] of the order [https://en.wikipedia.org/wiki/Lepidoptera Lepidoptera]
* [https://en.wikipedia.org/wiki/Butterfly_%28game%29 Butterfly Game] a [https://en.wikipedia.org/wiki/Abstract_strategy_game two-player abstract strategy game] from [https://en.wikipedia.org/wiki/Mozambique Mozambique]
* [https://en.wikipedia.org/wiki/BBN_Butterfly BBN Butterfly] a massively parallel computer from the 1980s
* [https://en.wikipedia.org/wiki/Butterfly_diagram Butterfly diagram] in the context of [https://en.wikipedia.org/wiki/Fast_Fourier_transform fast Fourier transform] <ref>[http://www.relisoft.com/Science/Physics/fft.html Fast Fourier Transform (FFT)] from [http://www.relisoft.com/index.htm Reliable Software]</ref> algorithms
* [https://en.wikipedia.org/wiki/Zassenhaus_lemma Butterfly or Zassenhaus lemma]
* [http://de.wikipedia.org/wiki/Schmetterlingsgraph Schmetterlingsgraph] (German)
* [https://en.wikipedia.org/wiki/Butterfly_knot Butterfly knot]
* [https://en.wikipedia.org/wiki/Butterfly_theorem Butterfly theorem] in elementary geometry
* [https://en.wikipedia.org/wiki/Butterfly_curve_%28algebraic%29 Butterfly curve (algebraic)]
* [https://en.wikipedia.org/wiki/Butterfly_curve_%28transcendental%29 Butterfly curve (transcendental)]
* [https://en.wikipedia.org/wiki/Butterfly_catastrophe#Butterfly_catastrophe Butterfly catastrophe] Catastrophe theory
* [https://en.wikipedia.org/wiki/Butterfly_%28options%29 Butterfly options] a combination option trade strategy
* [https://en.wikipedia.org/wiki/Iron_Butterfly_Spread Iron Butterfly spread]
* [https://en.wikipedia.org/wiki/Iron_Butterfly Iron Butterfly (band)]
* [https://en.wikipedia.org/wiki/Butterfly_ballot#Design Butterfly ballot]
* [https://en.wikipedia.org/wiki/Butterfly_effect Butterfly effect] in the context of [https://en.wikipedia.org/wiki/Chaos_theory Chaos theory]
* [https://en.wikipedia.org/wiki/The_Butterfly_Effect The Butterfly Effect (Film)]
* [https://en.wikipedia.org/wiki/The_Butterfly_Effect_%28band%29 The Butterfly Effect (band)]
==Misc==
* [[Videos#HerbieHancock|Herbie Hancock]] & [[Videos#TheHeadhunters|The Headhunters]], [https://en.wikipedia.org/wiki/Thrust_%28album%29 Butterfly], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=5knsdyW9OqY|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
[[FILE:EscherSymmetry.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/symmetry-bmp/E70.jpg|[[Arts#Escher|M. C. Escher]], Symmetry <ref>[http://www.mcescher.com/Gallery/gallery-symmetry.htm Picture gallery "Symmetry"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''Butterfly Boards''',<br/>
two-dimensional [[Array|arrays]] (typically of various history counters for each color), indexed by the [[Origin Square|from-]] and [[Target Square|to-square]] coordinates of (valid and likely [[Quiet Moves|quiet]]) [[Moves|moves]], which appear inside the [[Search|search]]. Those counters can then be used for [[Move Ordering|move ordering]] as mentioned in the [[History Heuristic|history heuristic]], or to decide about [[Late Move Reductions|late move reductions]] and [[History Leaf Pruning|history leaf pruning]]. Another application is a kind of [[Killer Heuristic |killer-]] or [[Refutation Table|refutation table]], to store a refutation of a specific move <ref>[[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]</ref>, also base of the [[Countermove Heuristic|countermove heuristic]] <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47953&start=2 Re: History pruning / move ordering question] by [[Don Dailey]], [[CCC]], May 10, 2013</ref>.
=Layout=
The size of the [[Array|array]] is 4K (64 x 64 = 4096) elements for each color, but the density is poor, since most [[Origin Square|from-]] and [[Target Square|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|distance]] one, are ambiguous and may be legal for several [[Pieces|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 Push|pawn pushes]] are subset of rook-moves, while pawn captures and [[En passant|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 [[Late Move Reductions|LMR]], and say that given enough search depth, History counters produce just some random noise <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=163477&t=18345 Re: LMR: history or not?] by [[Robert Hyatt]] from [[Computer Chess Forums|CCC]], December 13, 2007</ref> .
This is how butterfly boards may be declared in [[C]] or [[Cpp|C++]]:
<pre>
counterType arrWhiteButterfly[64][64]; // from, to -> 4K
counterType arrBlackButterfly[64][64]; // from, to -> 4K
</pre>
or
<pre>
counterType arrButterfly[2][64][64]; // color, from, to -> 8K
</pre>
=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".
{| class="wikitable"
|-
! Piece
! covers other pieces
! #
! div (7*16)
|-
! Rook
| style="text-align:left;" | queen, king and pawn pushes
| style="text-align:right;" | 896
| style="text-align:right;" | 8
|-
! Bishop
| style="text-align:left;" | queen, king and pawn captures
| style="text-align:right;" | 560
| style="text-align:right;" | 5
|-
! Knight
| style="text-align:center;" | -
| style="text-align:right;" | 336
| style="text-align:right;" | 3
|-
! colspan="2" | possible from-to move coordinates
| style="text-align:right;" | 1792
| style="text-align:right;" | 16
|}
=The Eponym=
The name Butterfly Boards was proposed by [[Dap Hartmann]] in 1988, when he introduced the [[Butterfly Heuristic]] in the [[ICGA Journal|ICCA Journal]] <ref>[[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]</ref>, and the application of a Butterfly [[Refutation Table|refutation table]] at the [[Advances in Computer Chess 6]] conference in 1990 <ref>[[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]</ref>. Plotting the illegal move coordinates as black cells '''#''' inside a 64*64 sheet, seven [https://en.wikipedia.org/wiki/Butterfly butterfly] shaped pattern appear along the impossible move diagonal (where squares are equal).
=The Butterfly=
==Single Shape==
The [https://en.wikipedia.org/wiki/Thorax 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:
<pre>
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 / | \ ~ # - - - - #
</pre>
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)
<pre>
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 ~ | ~ \ # # # ~ / | \ ~ # - - - - #
</pre>
=C-Code=
Some arbitrary [[C]]-code, to produce the plot:
<pre>
#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;
}
</pre>
=Analogy in Astronomy=
[[Dap Hartmann]] found a nice analogy in astronomy. [https://en.wikipedia.org/wiki/Edward_Walter_Maunder Edward Maunders] was the first astronomer (1904) to plot the distribution in [http://www.answers.com/topic/heliographic-latitude heliographic latitude] of the centers of [http://www.ips.gov.au/Educational/2/2/3 sunspot groups] as a functions of time:
[[FILE:Sunspot-bfly.gif|none|border|800px|text-bottom]]
A modern version of the Mauders' sunspot "butterfly diagram" <ref>[https://en.wikipedia.org/wiki/Edward_Walter_Maunder#Solar_observations 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.)</ref> .
=See also=
* [[Bobby#StrategicQuiescenceSearch|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''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
* [[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|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''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
=External links=
==Wikipedia==
Butterflies from [https://en.wikipedia.org/wiki/Main_Page Wikipedia] <ref>[https://en.wikipedia.org/wiki/Butterfly_%28disambiguation%29 Butterfly (disambiguation) from Wikipedia]</ref>
* [https://en.wikipedia.org/wiki/Butterfly Butterfly insect] of the order [https://en.wikipedia.org/wiki/Lepidoptera Lepidoptera]
* [https://en.wikipedia.org/wiki/Butterfly_%28game%29 Butterfly Game] a [https://en.wikipedia.org/wiki/Abstract_strategy_game two-player abstract strategy game] from [https://en.wikipedia.org/wiki/Mozambique Mozambique]
* [https://en.wikipedia.org/wiki/BBN_Butterfly BBN Butterfly] a massively parallel computer from the 1980s
* [https://en.wikipedia.org/wiki/Butterfly_diagram Butterfly diagram] in the context of [https://en.wikipedia.org/wiki/Fast_Fourier_transform fast Fourier transform] <ref>[http://www.relisoft.com/Science/Physics/fft.html Fast Fourier Transform (FFT)] from [http://www.relisoft.com/index.htm Reliable Software]</ref> algorithms
* [https://en.wikipedia.org/wiki/Zassenhaus_lemma Butterfly or Zassenhaus lemma]
* [http://de.wikipedia.org/wiki/Schmetterlingsgraph Schmetterlingsgraph] (German)
* [https://en.wikipedia.org/wiki/Butterfly_knot Butterfly knot]
* [https://en.wikipedia.org/wiki/Butterfly_theorem Butterfly theorem] in elementary geometry
* [https://en.wikipedia.org/wiki/Butterfly_curve_%28algebraic%29 Butterfly curve (algebraic)]
* [https://en.wikipedia.org/wiki/Butterfly_curve_%28transcendental%29 Butterfly curve (transcendental)]
* [https://en.wikipedia.org/wiki/Butterfly_catastrophe#Butterfly_catastrophe Butterfly catastrophe] Catastrophe theory
* [https://en.wikipedia.org/wiki/Butterfly_%28options%29 Butterfly options] a combination option trade strategy
* [https://en.wikipedia.org/wiki/Iron_Butterfly_Spread Iron Butterfly spread]
* [https://en.wikipedia.org/wiki/Iron_Butterfly Iron Butterfly (band)]
* [https://en.wikipedia.org/wiki/Butterfly_ballot#Design Butterfly ballot]
* [https://en.wikipedia.org/wiki/Butterfly_effect Butterfly effect] in the context of [https://en.wikipedia.org/wiki/Chaos_theory Chaos theory]
* [https://en.wikipedia.org/wiki/The_Butterfly_Effect The Butterfly Effect (Film)]
* [https://en.wikipedia.org/wiki/The_Butterfly_Effect_%28band%29 The Butterfly Effect (band)]
==Misc==
* [[Videos#HerbieHancock|Herbie Hancock]] & [[Videos#TheHeadhunters|The Headhunters]], [https://en.wikipedia.org/wiki/Thrust_%28album%29 Butterfly], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=5knsdyW9OqY|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
