Wikispaces : chessprogramming - items matching description

Bad bishop

GerdIsenberg — Mon, 22 Jun 2015 13:18:28 GMT

Home * Evaluation * Evaluation of Pieces * Bad bishop

Bad bishop is a bishop whose Mobility is restricted by own pawns. As opposed to normal mobility problems, this situation is semi-permanent (more so if the position is blocked), which fact justifies singling it out as another evaluation term. Bad bishop is not such a liability if it is placed outside the pawn chain (Bf5 in the Slav). For that reason some programs, like Crafty, score a bishop as bad only if its forward mobility is impaired.

For a bitboard-based program a feasible approach would be to create an array of 64 bitboards, indexed by a Bishop's position, and marking the pawn positions which would make our bishop bad.

Publications

Matej Guid, Martin Možina, Jana Krivec, Aleksander Sadikov, Ivan Bratko (2008). Learning Positional Features for Annotating Chess Games: A Case Study. CG 2008, pdf

Forum Posts

Evaluating bad bishops by Tord Romstad, Winboard Programming Forum, May 15, 2006
Bad/good bishops in R3 and IPPOLIT/IvanHoe by Mark Watkins, Open Chess Programming Forum, November 30, 2010

External Links

Good bishop and bad bishop from Wikipedia
How Bad is a Bad Bishop? by Iryna Zenyuk, February 27, 2019, Chess.com
The Bishow's Show: Bad Bishop by Iryna Zenyuk, March 09, 2012, Chess.com

What links here?

Page	Date Edited
Amundsen	Sep 3, 2013
Bad bishop	Jun 22, 2015
Bishops of Opposite Colors	Aug 22, 2012
Chester	Feb 15, 2014
Comet	Jan 8, 2016
Dreamer	Aug 5, 2015
Evaluation of Pieces	Jan 8, 2018
Exacto	Oct 3, 2015
Gambit Fruit	Mar 29, 2013
Middlegame	Sep 6, 2016
Murka	Nov 11, 2016
Pawn Rams (Bitboards)	Nov 11, 2017
Pawn Structure	Oct 2, 2017
PolarChess	May 15, 2017
Sayuri	Oct 1, 2017
Shield	May 17, 2017
Snitch	Apr 7, 2016
Zeus	Jan 3, 2018

Up one Level

Bishop

GerdIsenberg — Fri, 05 Nov 2010 17:07:26 GMT

Home * Chess * Pieces * Bishop

CPW Pages with the tag "bishop"

What links here?

Page	Date Edited
More Links
Algebraic Chess Notation	Sep 25, 2017
Amyan	Dec 10, 2013
Arimaa	Jan 4, 2017
Battery	Jan 29, 2017
Bishop	Nov 5, 2010
Bishop Pair	Sep 10, 2017
Bishop versus knight	May 17, 2016
Blockade of Stop	Oct 11, 2016
Color of a Square	May 24, 2015
Color Weakness	Nov 24, 2017
Denis Onneweer	Oct 3, 2012
Development	Jan 17, 2018
Elephant	Sep 19, 2016
Endgame	Sep 18, 2017
Fianchetto	Feb 18, 2015
Fill Algorithms	Nov 6, 2013
Fischerle	Aug 21, 2017
Gambit Fruit	Mar 29, 2013
General Setwise Operations	Feb 25, 2018
Hash Table	Jan 1, 2018
Influence Quantity of Pieces	Jul 21, 2017
Initial Position	Apr 14, 2018
Joanna	Dec 9, 2014
KBNK Endgame	Nov 26, 2016
Komodo	Mar 6, 2018
MicroChess	Jul 14, 2015
Middlegame	Sep 6, 2016
Mobility	Jan 17, 2018
Mop-up Evaluation	Nov 26, 2016
MVV-LVA	Oct 26, 2017
Najib Nakad	Oct 22, 2014
Pieces	Feb 19, 2018
Pin	Mar 7, 2017
Point Value	Mar 31, 2018
Promotions	Jun 6, 2017
Scidlet	May 31, 2014
Scorpio	Mar 28, 2018
SEE - The Swap Algorithm	Jun 5, 2017
Shatranj	Jul 26, 2017
Simona Tancig	Nov 7, 2012

Up one Level

Bishop Pair

GerdIsenberg — Sun, 10 Sep 2017 16:10:08 GMT

Home * Evaluation * of Pieces * Bishop Pair

Since in the initial position bishops stand on the squares of different color, throughout the game they control a disjoint sets of squares. This means that their power will never be wasted for carrying out the same tasks. On the other hand, lack of one bishop may introduce a color weakness. Taking all those considerations into account, one might conclude that possessing both bishops is a desirable thing. The question is, however, how much they are worth.

Larry Kaufman proposed the value of half a pawn ^[1]. It must be stressed, however, that this number is a part of a broader system, in which knights are stronger with many pawns on the board.

Publications

Gennady Timoshchenko (1993). Bishop or Knight? ICCA Journal, Vol. 16, No. 4
Mark Sturman (1995). Beware The Bishop Pair. Computer Chess Reports, Vol. 5, No. 2, pp.58 ^[2]
Mark Sturman (1996). Beware the Bishop Pair. ICCA Journal, Vol. 19, No. 2
Larry Kaufman (1999). The Evaluation of Material Imbalances. (first published in Chess Life March 1999, online version edited by Dan Heisman)

Forum Posts

Question about Crafty and Bishop Pair by Renze Steenhuisen, CCC, July 13, 2004 » Crafty
Testing of Kaufman Material Values by Mark Lefler, CCC, April 25, 2009 » Material
Rook Pair Penalty, Knight Pair Penalty, Having a Pawn Bonus by Mark Lefler, CCC, May 11, 2009

External Links

Bishop pair from Wikipedia

References

^ Larry Kaufman (1999). The Evaluation of Material Imbalances. (first published in Chess Life March 1999, online version edited by Dan Heisman)
^ Looking for Mark Sturman by Mark Lefler, rec.games.chess, July 02, 1995

What links here?

Page	Date Edited
Alarm	Jun 7, 2017
Battery	Jan 29, 2017
BigLion	Sep 28, 2016
Bishop Pair	Sep 10, 2017
Bishop versus knight	May 17, 2016
Bismark	Apr 22, 2015
chess22k	Apr 23, 2018
Coiled	Mar 12, 2017
Crafty	Jan 28, 2018
Demolito	Mar 1, 2018
Diablo	May 17, 2016
Djinn	Feb 8, 2016
Dorpsgek	Apr 2, 2018
Draw Evaluation	Mar 12, 2018
Evaluation of Pieces	Jan 8, 2018
Exacto	Oct 3, 2015
Fischerle	Aug 21, 2017
Garbochess	Sep 23, 2017
Gibbon	Dec 23, 2014
Gogobello	Jul 30, 2017
HeavyChess	Feb 14, 2014
ISA	Apr 2, 2018
Jan Renze Steenhuisen	Sep 10, 2017
Kaissa	Apr 9, 2018
Mark Sturman	May 17, 2016
Marvin	Feb 10, 2018
Material	Mar 31, 2018
Much	Jun 7, 2016
PolarChess	May 15, 2017
Quantifying Evaluation features	Jun 6, 2012
RattateChess	Dec 2, 2014
RuyDos	Feb 17, 2018
Sharper	Jun 6, 2017
Shield	May 17, 2017
Stockfish	Apr 7, 2018
Teki	Mar 29, 2018
Wing	Oct 26, 2017
Winglet	Apr 26, 2015
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018

Up one Level

Bishop versus knight

GerdIsenberg — Tue, 17 May 2016 18:33:35 GMT

Endgame Considerations

Home * Evaluation * of Pieces * Bishop versus Knight

Bishop versus Knight,
is an often debated topic of the two pieces of similar relative strengths. Traditional thinking has been that the bishop is slighly better in open positions while the knight is better in closed positions ^[1]. However, the bishop pair versus knight and bishop or even more versus two knights yields an extra advantage as demonstrated in the winning percentages of the C, D, E rows of several material configurations 1 - 6 in Mark Sturman's table.

Endgame Considerations

In a minor piece endgame featuring bishop versus knight a couple of special considerations should be taken into account:

bishop becomes stronger if there are pawns on both wings
the side with a knight can defend by the means of blockade on the squares that are out of reach for the enemy bishop
if the side with a knight has a compact pawn mass, then it should place pawns on the squares controlled by enemy bishop to restrict its mobility.

Winning Percentages

of the bishop side as given by Mark Sturman, mining a database of over 350,000 games. Only results with at least 50 games have been recorded ^[2] :

		Piece Configurations	Number of pawns on each side
			1	2	3	4	5	6	7
1	A	B vs. N	51.2	50.6	50.3	49.5	48.6	45.7	43.6
	B	BN vs. NN	*	47.2	51.6	51.4	50.1	48.4	46.8
	C	BB vs. NB	58.2	65.9	66.1	67.6	65.2	62.4	58.1
	D	BB vs. NN	*	*	68.6	67.8	69.7	66.6	63.7
	E	BBN vs. NNB	*	*	66.9	64.3	63.6	62.1	59.1
2	A	BR vs. NR	48.6	51.5	51.3	51.4	50.7	48.8	46.6
	B	BNR vs. NNR	*	44.7	48.1	49.6	50.1	48.6	46.5
	C	BBR vs. NBR	*	62.7	64.0	64.9	63.8	61.6	60.8
	D	BBR vs. NNR	*	*	62.3	67.1	66.0	65.0	62.8
	E	BBNR vs. NNBR	*	*	62.0	63.5	62.3	58.1	56.6
3	A	BRR vs. NRR	*	48.3	50.4	51.2	50.1	48.6	46.2
	B	BNRR vs. NNRR	*	*	54.7	50.4	50.3	49.5	48.8
	C	BBRR vs. NBRR	*	*	62.3	63.0	61.9	59.1	56.0
	D	BBRR vs. NNRR	*	*	*	70.7	62.3	58.3	58.9
	E	BBNRR vs. NNBRR	*	*	61.2	61.9	60.5	56.0	53.9
4	A	BQ vs. NQ	*	49.7	49.9	48.2	48.9	47.8	45.4
	B	BNQ vs. NNQ	*	*	*	51.2	50.9	51.9	51.0
	C	BBQ vs. NBQ	*	*	55.6	60.5	59.3	58.7	54.5
	D	BBQ vs. NNQ	*	*	*	70.8	63.1	55.5	54.8
	E	BBNQ vs. NNBQ	*	*	*	56.4	56.9	56.6	59.5
5	A	BQR vs. NQR	*	53.6	50.9	50.8	51.1	50.3	48.4
	B	BNQR vs. NNQR	*	*	53.8	52.0	52.1	51.9	51.4
	C	BBQR vs. NBQR	*	*	58.0	57.4	58.2	57.1	55.5
	D	BBQR vs. NNQR	*	*	*	63.6	60.6	58.5	60.1
	E	BBNQR vs. NNBQR	*	*	69.6	57.9	56.1	54.7	56.5
6	A	BQRR vs. NQRR	*	*	53.0	51.8	51.1	49.3	48.4
	B	BNQRR vs. NNQRR	*	*	50.5	55.0	50.6	49.5	48.6
	C	BBQRR vs. NBQRR	*	*	62.5	58.8	57.0	54.8	53.1
	D	BBQRR vs. NNQRR	*	*	*	63.4	59.7	54.6	54.7
	E	BBNQRR vs. NNBQRR	*	*	60.2	57.0	55.0	53.0	52.3

* = Insufficient data

Publications

Gennady Timoshchenko (1993). Bishop or Knight? ICCA Journal, Vol. 16, No. 4
Mark Sturman (1995). Beware The Bishop Pair. Computer Chess Reports, Vol. 5, No. 2, pp.58 ^[3]
Mark Sturman (1996). Beware the Bishop Pair. ICCA Journal, Vol. 19, No. 2
Steve Mayer (1997). Bishop Versus Knight: The verdict. Batsford, amazon.com

References

^ Steve Mayer (1997). Bishop Versus Knight: The verdict. Batsford, amazon.com
^ Mark Sturman (1996). Beware the Bishop Pair. ICCA Journal, Vol. 19, No. 2, pp. 88
^ Looking for Mark Sturman by Mark Lefler, rec.games.chess, July 02, 1995

What links here?

Page	Date Edited
Bishop Pair	Sep 10, 2017
Bishop versus knight	May 17, 2016
Endgame	Sep 18, 2017
Evaluation of Pieces	Jan 8, 2018
Mark Sturman	May 17, 2016
Match Statistics	Mar 31, 2018
Pawn Advantage, Win Percentage, and Elo	Dec 20, 2017
Strategic Test Suite	Dec 19, 2016
Triangulation	Apr 4, 2013

Up one Level

Bishops of Opposite Colors

GerdIsenberg — Wed, 22 Aug 2012 15:59:25 GMT

Home * Evaluation * Game Phases * Endgame * Bishops of Opposite Colors

The endgame in which both sides posses only pawns and bishops of opposite colors is notorious difficult to win, as the weaker side is likely to create a blockade on the squares controlled by its own bishop. One pawn advantage is usually not enough to force the win. The chances for that exist either when the stronger side has either passed pawns on both wings or connected passed pawns. In the latter case the winning method is to advance pawns in such a manner that they are placed on the squares controlled by enemy bishop, since it makes blockade impossible.

Scaling down

A good idea for the evaluation function is to scale down the material value when the pure bishop of opposite colors ending is encountered. If some more pieces beside the bishops are present on the board, winning the endgame is easier, but requires complex strategy, based rather on zugzwang and attacking possibilities than on simply advancing passed pawns.

Forum Posts

Deep Thought.. What's this rules of Bishops? by Aravind Anumala, rgc, April 11, 1995
Hossa - Crafty : bishop endgame by Steffen A. Jakob, CCC, October 27, 1999 » Hossa, Crafty
Opposite Color Bishop Ending by Howard Exner, CCC, November 29, 1999
Test position (opposite colour bishop)..very hard for chess engines by Masros Tukiran, CCC, September 08, 2005

External Links

What links here?

Page	Date Edited
Bad bishop	Jun 22, 2015
Bishops of Opposite Colors	Aug 22, 2012
Color of a Square	May 24, 2015
Djinn	Feb 8, 2016
Endgame	Sep 18, 2017
Fortress	Feb 1, 2018
Gibbon	Dec 23, 2014
Hossa	Jan 7, 2016
Murka	Nov 11, 2016

Up one Level

Butterfly Boards

GerdIsenberg — Tue, 27 Jan 2015 19:02:19 GMT

Home * Programming * Data * Butterfly Boards

		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

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:

A modern version of the Mauders' sunspot "butterfly diagram" ^[8] .

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

AVR Butterfly Board from Asuro Wiki (German)

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)

Musicvideo

Herbie Hancock & The Headhunters, Butterfly, 1974, YouTube Video

References

^ 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
^ Picture gallery "Symmetry" from The Official M.C. Escher Website
^ 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

What links here?

Page	Date Edited
Array	Dec 1, 2016
Bobby	Jan 7, 2016
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Countermove Heuristic	Oct 1, 2017
Dap Hartmann	Jun 10, 2017
Dappet	Dec 12, 2016
Data	Nov 26, 2017
Dictionary	Aug 24, 2017
Direction	Oct 6, 2016
Encoding Moves	Mar 27, 2016
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
ICGA Journal	Dec 21, 2017
Influence Quantity of Pieces	Jul 21, 2017
Last Best Reply	Jul 6, 2013
Mathematician	Apr 9, 2018
Moves	Feb 19, 2018
Neural MoveMap Heuristic	Sep 24, 2015
Relative History Heuristic	Jun 8, 2015
Squares	Feb 15, 2015
Table-driven Move Generation	Feb 19, 2017
Vector Attacks	Dec 15, 2017

Up one Level

Color Weakness

GerdIsenberg — Fri, 24 Nov 2017 10:01:57 GMT

Home * Evaluation * of Pieces * Color Weakness

Color weakness denotes a situation in which one of the players does not have sufficient control over the squares of a certain color. This is usually caused by the lack of a bishop of that color, coupled with the unfortunate pawn structure. In such situations, the opponent may use squares of that color to penetrate the opponent's position. Hans Kmoch defines insufficient occupation of the dark respectively light squares by pawns and bishop as black poverty or Melanpenie respectively white poverty or Leukopenie ^[1].

Examples

Typical examples of a color weakness are:

positions after the exchange of a fianchettoed bishop (this is especially painful when it was a defender of the castled king)
black exchanging a dark squared bishop in the French, the Slav or the Caro-Kann defences
white exchanging a light-squared bishop in the Queen's Gambit Declined or in the Colle
white exchanging a dark-squared bishop in the King's Indian, most notably in Sämisch

External Links

Color blindness from Wikipedia
Bob Berg & Mike Stern Band - Chromazone, YouTube Video
with Dennis Chambers and Lincoln Goines, The Bottom Line, New York City, February 25, 1990

References

^ Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. ISBN 0-486-26486-6, Google Books

What links here?

Page	Date Edited
Bad bishop	Jun 22, 2015
Bishop Pair	Sep 10, 2017
Bishops of Opposite Colors	Aug 22, 2012
Color	Mar 12, 2014
Color Weakness	Nov 24, 2017
Evaluation of Pieces	Jan 8, 2018
Fianchetto	Feb 18, 2015
Gogobello	Jul 30, 2017
Hans Kmoch	Nov 11, 2017
Pawn Structure	Oct 2, 2017
Square Control	Sep 15, 2016

Up one Level

Congruent Modulo Bitboards

GerdIsenberg — Wed, 26 Jun 2013 18:26:44 GMT

Modulo vs. Multiplication

Modulo

Congruence relation

Casting out 255

Reciprocal Multiplication

Multiplication

Fenner's and Levene's conclusion

Home * Board Representation * Bitboards * Sliding Piece Attacks * Congruent Modulo Bitboards

Congruent Modulo Bitboards was introduced by Trevor Fenner and Mark Levene in the ICGA Journal, Vol. 31, No. 1 in 2008 ^[1]. While their Perfect Hashing approach provides great mathematical insights in Congruent Modulo arithmetic, their final conclusion in comparison with Hashing Dictionaries, Rotated Bitboards and Magic Bitboards was criticized by the obvious comparison with Kindergarten Bitboards ^[2].

Modulo vs. Multiplication

BitScan broaches the issue of Perfect Hashing with Modulo versus Multiplication as well:

So does the SWAR-Popcount, when it is about to finally add byte-wise populations:

Modulo

Congruence relation

Fenner and Levene use masked lines (not necessarily excluding the sliding piece), that is bitboards with N=8 active bits with k={7,8,9} bits apart, starting with bit zero

$A_{kN} = \{0, k, 2k, ...,(N-1)k\}$

Based on Congruence relation

$b \equiv c \pmod{m}$

or equivalently

$b \mod{m} = c \mod{m}$

they deduced two general perfect hashing functions. The case N <= k with

$h_{1}(a) = a \mod (2^k + 2)$

and the case N <= k + 1

$h_{2}(a) = a \mod (2^{k+1} + 1)$

This results in modulo 514 for diagonals, modulo 257 for anti-diagonals, and modulo 258 for files, to calculate the occupied index. Tables could made denser by storing indices, but that would require a second indirection. While Fenner and Levene used a Matlab 32-bit implementation to conclude their approach might be competitive, this is how it may be implemented in C by looking up pre-calculated attack-bitboards:

U64 arrCmodDiaAttacks [514][64];  // 257 K
U64 arrCmodAntiAttacks[257][64];
U64 arrCmodFileAttacks[258][64];
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   const U64 aDia = C64(0x8040201008040201);
   occ = ( (occ >> diashift[sq]) & aDia) % 514;
   return arrCmodDiaAttacks[occ][sq];
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   const U64 aAntiDiaShr7 = C64(0x0002040810204081);
   occ = ( (occ >> antishift[sq]) & aAntiDiaShr7 ) % 257;
   return arrCmodAntiAttacks[occ][sq];
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   const U64 aFile = C64(0x0101010101010101);
   occ = ( (occ >> (sq&7)) & aFile) % 258;
   return arrCmodFileAttacks[occ][sq];
}

Casting out 255

For ranks, diagonals or anti-diagonals, where the occupancy mask excludes the sliding piece, and the rank-or byte-wise sum of disjoint bits is therefor less than 255, Casting out 256-1 works as well, without any shifts required, and with more space saving options for the lookup table, i. e. similar to Kindergarten Bitboards with shared multiples of first rank attacks and an trailing post-mask with the same line ^[3].

masked occupany  %  256-1            =  A-H    
. . . . . . . H     . . . . . . . .     . . . . . . . .
. . . . . . G .     . . . . . . . .     . . . . . . . . 
. . . . . F . .     . . . . . . . .     . . . . . . . . 
. . . . E . . .     . . . . . . . .     . . . . . . . . 
. . . . . . . .  %  . . . . . . . .  =  . . . . . . . . 
. . C . . . . .     . . . . . . . .     . . . . . . . . 
. B . . . . . .     . . . . . . . .     . . . . . . . . 
A . . . . . . .     1 1 1 1 1 1 1 1     A B C . E F G H

Reciprocal Multiplication

The 64-bit modulo by a constant can be done most efficiently by reciprocal fixed point multiplication, this is how Microsoft Visual C++ 2005 compiler implements the mod constant for x86-64 processors. One 64*64=128 bit multiplication, one shift, one further 32-bit multiplication , one subtraction. Of course using 64-bit division to get the remainder burns even more cycles.

Code:
% 514
 mov    r11d, r10 ; masked diagonal
 mov    rax, ff00ff00ff00ff01H
 mul    r10
 shr    rdx, 9
 imul   edx, 514 ; 00000202H
 sub    r11d, edx
 
% 257
 mov    r11d, r10 ; masked diagonal
 mov    rax, ff00ff00ff00ff01H
 mul    r10
 shr    rdx, 8
 imul   edx, 257 ; 00000101H
 sub    r11d, edx

Multiplication

A Kindergarten like approach might look like this (not considering inner six bits):

U64 arrDiagonalAttacks[256][64];  // 128 K
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   occ = (diagonalMask[sq] & occ) * C64(0x0101010101010101) >> 56;
   return arrDiagonalAttacks[occ][sq];
}

and uses one 64*64=64-bit multiplication, with this x86-64 assembly for calculating an eight-bit occupied index:

 mov    rax, 0101010101010101H
 imul   rdx, rax
 shr    rdx, 56

Even Kindergarten File-Attacks are cheaper and faster, not to mention Magic Bitboards, which covers two lines of a rook or bishop in one run.

Fenner's and Levene's conclusion

Quote from their paper pp 11
3.5. Comparison with other Methods

As reported in Hyatt (2007), the rotated and magic bitboard methods are of comparable performance, and Tannous (2007) claims just a small improvement of the direct lookup method over rotated bitboards. It is easy to see that, in terms of the number of computer operations, the efficiency of our method will be similar to that of direct lookup. Thus we are justified in claiming that the computational efficiency of our method is comparable to the others.

Their conclusion was based on following statement of Robert Hyatt ^[4] ...

I had reported this earlier. Magic was no faster than rotated. I switched because of two things...

1. Magic is simpler, and simpler is better as I get older.
2. Magic gives you the opportunity to update the occupied_squares and then generate moves easily.

To do this with rotated bitboards first requires that all rotated bitboards be updated in addition to the normal occupied_squares bitboard. This is faster, if you use the feature (I don't yet, but well might at times).

... and this claim of Sam Tannous ^[5]:

The results shown indicate that directly looking up the attacking moves for sliding pieces in hash tables improves the move generation speeds from 10% to 15% depending on computer architecture. Further efficiencies can be expected in a full implementation where the overhead of maintaining rotated bitboards is eliminated. The implementation and test code is made available in an Open-Source, interactive, chess programming module called “Shatranj” (Tannous, 2006).

Publications

Zbigniew J. Czech, George Havas, Bohdan S. Majewski (1997). Perfect Hashing. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-143
Trevor Fenner, Mark Levene (2008). Move Generation with Perfect Hashing Functions. ICGA Journal, Vol. 31, No. 1, pp. 3-12. pdf

Forum Posts

Nice Math - Strange Conclusions by Gerd Isenberg, CCC, April 29, 2008
Low memory usage attack bitboard generation by crystalclear, Winboard Forum, October 06, 2011

External Links

References

^ Trevor Fenner, Mark Levene (2008). Move Generation with Perfect Hashing Functions. ICGA Journal, Vol. 31, No. 1, pp. 3-12. pdf
^ Nice Math - Strange Conclusions by Gerd Isenberg, CCC, April 29, 2008
^ Low memory usage attack bitboard generation by crystalclear, Winboard Forum, October 06, 2011
^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Robert Hyatt, CCC August 25, 2007
^ Sam Tannous (2007). Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pp. 85-91, pdf

What links here?

Page	Date Edited
Congruent Modulo Bitboards	Jun 26, 2013
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
General Setwise Operations	Feb 25, 2018
Hash Table	Jan 1, 2018
ICGA Journal	Dec 21, 2017
Mark Levene	Jun 2, 2015
Sliding Piece Attacks	May 27, 2016
Trevor Fenner	Jun 2, 2015

Up one Level

Evaluation of Pieces

GerdIsenberg — Mon, 08 Jan 2018 21:52:17 GMT

Home * Evaluation * of Pieces

This page serves as a quick reference for those who look for ideas about evaluating different kinds of pieces.

Pawn

Pawn Structure
Pawn Center
Blockade of Stop
penalty for "d" and "e" pawns blocked on their initial squares

Knight

Decreasing value as pawns disappear
Outposts
Knight trapped on A8/H8/A7/H7 or A1/H1/A2/H2 - see Trapped Pieces
Penalty for blocking a "c" pawn in closed openings (Crafty defines it as follows: white knight on c3, white pawns on c2 and d4, no white pawn on e4)
When calculating knight mobility, it is advisable to omit squares controlled by enemy pawns
Marginal bonus for a knight defended by a pawn
Penalty for an undefended minor piece (Stockfish)

Bishop

Bad Bishop
Bishop Pair
Bishop versus Knight
Color Weakness
Fianchetto
Returning Bishop
Bishop trapped by enemy pawns on A2/H2/A7/H7 or on A3/H3/A6/H6, see Trapped Pieces
Penalty for an undefended minor piece (Stockfish)

Rook

Increasing value as pawns disappear
Rook on open file
Rook on seventh (possibly also eigth) rank
Tarrasch Rule (Rook behind Passed Pawn)
Penalty for a Rook blocked by an uncastled King
Small bonus for a rook with enemy queen on the same file (doesn't matter if it's open or not)
Rooks defending each other (Rebel uses a piece/square table for that, making suppoeted rook on 7th rank even more valuable)

Queen

Penalty for early development ^[1]
Some programs do not evaluate queen mobility
Some versions of Fruit replace queen mobility by king tropism
If king safety evaluation relies on king tropism, queen tends to get somewhat higher bonus

King

King safety in the middlegame
King centralization in the endgame
Mate at a Glance
Penalty for standing on a wing with no pawns present in the endgame
Pins/X-ray
Castling Rights

Forum Posts

Knight Evaluation by Jonathan Rosenthal, CCC, February 24, 2015
eval pieces by Daniel Anulliero, CCC, June 15, 2015

References

^ Queen wandering, was: Crafty 14,9 by Roland Pfister, CCC, May 11, 1998

What links here?

Page	Date Edited
Bad bishop	Jun 22, 2015
Betsabe	Jul 23, 2017
BigLion	Sep 28, 2016
Bishop Pair	Sep 10, 2017
Bishop versus knight	May 17, 2016
Blockade of Stop	Oct 11, 2016
Chenard	Sep 5, 2015
Clarabit	Nov 3, 2011
Coiled	Mar 12, 2017
Color Weakness	Nov 24, 2017
Demolito	Mar 1, 2018
Evaluation	Feb 1, 2018
Evaluation of Pieces	Jan 8, 2018
Exacto	Oct 3, 2015
Faile	May 27, 2014
Genie	Feb 7, 2016
Gk	Oct 9, 2017
Ifrit	Feb 7, 2016
Influence Quantity of Pieces	Jul 21, 2017
Jabba	Sep 10, 2016
KnockOut	Sep 20, 2016
MadChess	Jul 4, 2017
Monsoon	Feb 8, 2015
Pawn Center	Feb 12, 2015
Piece-Square Tables	Mar 31, 2018
Pieces	Feb 19, 2018
Returning Bishop	Mar 16, 2013
Rival	Jul 30, 2017
Robocide	May 11, 2016
Rook on Open File	Apr 24, 2017
Rook On Seventh	May 24, 2009
Sayuri	Oct 1, 2017
Scidlet	May 31, 2014
Simplex	Mar 6, 2016
Slow Chess	May 17, 2016
Tarrasch Rule	Jun 2, 2014
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Y!	Sep 10, 2017

Up one Level

Exploding Bitboards

PsyMar — Mon, 09 Mar 2015 12:29:50 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Exploding Bitboards

The expanding or exploding bitboards were created by Harald Lüßen with some help from other people in CCC ^[1] . The idea is to generate the attacks of a sliding piece from its square outside on all its rays in parallel like the waves of a stone thrown into water. This is done in some steps with multiplications and shifts like in the kindergarten bitboards. At each step or distance from the original square the rays can be expanded or stopped by other pieces from an occupied bitboard. There are some nasty overflow problems at the border of the board that must be solved. This approach is slower than other techniques. The code below is taken from the chess engine Elephant which is known for some bitboard comparisons but not for playing strength.

In the example this big-endian file-mapping is used:

    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+
 
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h

The general trick of chasing and pushing around the bits on the board is this: First shift down and sideways far enough to get a good start. Then multiply with 2 to shift one square to the side (left in this mapping) and multiply with 2^8 = 0x100 to move the bit upwards. Use any power of 2 that helps you. Build the sum of all the multiplication factors of all moves for all bits and multiply with that number. There will probably be more bits in the result than there should be because the multiplication works on all original bits. Use a mask to get rid of all the bad bits.

Bishops

For each square there is an ignition of the explosion.

/*
First expanding step (explosion) for a bishop
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . 1 . 1 . . .
 . . .sq . . . .
 . . 1 . 1 . . .
 . . . . . . . .
 . . . . . . . .
*/
Bitboard initB[64];
void makeInitB()
{
    for ( int sq = 0; sq < 64; ++sq )
    {
        Bitboard bb = C64(1) << sq;
        initB[sq]  = (bb >> 9) & C64(0x7f7f7f7f7f7f7f7f);
        initB[sq] |= (bb >> 7) & C64(0xfefefefefefefefe);
        initB[sq] |= (bb << 9) & C64(0xfefefefefefefefe);
        initB[sq] |= (bb << 7) & C64(0x7f7f7f7f7f7f7f7f);
    }
}

The explosion is only allowed along the rays.

/*
Mask for bishop attack rays
 . . . . . . . 1
 1 . . . . . 1 .
 . 1 . . . 1 . .
 . . 1 . 1 . . .
 . . .sq . . . .
 . . 1 . 1 . . .
 . 1 . . . 1 . .
 1 . . . . . 1 .
*/
Bitboard maskB[64];
void makeMaskB()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        maskB[sq] = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
            maskB[sq] |= C64(1) << i;
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
            maskB[sq] |= C64(1) << i;
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
            maskB[sq] |= C64(1) << i;
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
            maskB[sq] |= C64(1) << i;
    }
}

For each square there is a maximum number of steps to take.

/*
Number of expanding steps (explosions) for a bishop
*/
const int repsB[64] =
{
    6, 5, 4, 3, 3, 4, 5, 6,
    5, 5, 4, 3, 3, 4, 5, 5,
    4, 4, 4, 3, 3, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3,
    3, 3, 3, 3, 3, 3, 3, 3,
    4, 4, 4, 3, 3, 4, 4, 4,
    5, 5, 4, 3, 3, 4, 5, 5,
    6, 5, 4, 3, 3, 4, 5, 6,
};

This does one step of the explosion.

/*
= init               >>= 9               *= 0x5005          &= mask            at |= bb
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . 1 1 . . 1 . .    . 1 . . . 1 . .    . 1 . . . 1 . .
 . . 1 . 1 . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . 1 . 1 . . .
 . . . s . . . .     . . . 1 . 1 . .     1 1 . . 1 . . .    . . . s . . . .    . . . s . . . .
 . . 1 . 1 . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . 1 . 1 . . .
 . . . . . . . .     . . . 1 . 1 . .     . 1 1 . . 1 . .    . 1 . . . 1 . .    . 1 . . . 1 . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
*/
Bitboard bishopAttacks( int sq, const Bitboard &free )
{
    Bitboard msk = maskB[sq];
    Bitboard bb  = initB[sq];
    Bitboard at  = bb;
    bb &= free;
    switch ( repsB[sq] )
    {
      case 6:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
      case 5:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
      case 4:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
      case 3:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb;
    }
    return at;
}

There are some possible optimisations when the repsB[] array is modified in the corners during
the game or search. Some numbers 7, 8, 9 combined with additional switch cases can work
as a shortcut for bishops in the corners behind pawns.

Rooks

For each square there is an ignition of the explosion.

/*
First expanding step (explosion) for a rook
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . 1 . . . .
 . . 1sq 1 . . .
 . . . 1 . . . .
 . . . . . . . .
 . . . . . . . .
*/
Bitboard initR[64];
void makeInitR()
{
    for ( int sq = 0; sq < 64; ++sq )
    {
        Bitboard bb = C64(1) << sq;
        initR[sq]  = (bb >> 8);
        initR[sq] |= (bb >> 1) & C64(0x7f7f7f7f7f7f7f7f);
        initR[sq] |= (bb << 1) & C64(0xfefefefefefefefe);
        initR[sq] |= (bb << 8);
        //logf << "initR[sq] " << sq << endl;
        //logf << initR[sq].txt8lines() << endl;
    }
}

The explosion is only allowed along the rays.

/*
Mask for rook attack rays
 . . . 1 . . . .
 . . . 1 . . . .
 . . . 1 . . . .
 . . . 1 . . . .
 1 1 1sq 1 1 1 1
 . . . 1 . . . .
 . . . 1 . . . .
 . . . 1 . . . .
*/
Bitboard maskR[64];
void makeMaskR()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        maskR[sq] = 0;
        int i;
        for ( i = sq - 8; i >= 0; i -= 8 )
            maskR[sq] |= C64(1) << i;
        for ( i = sq - 1; i >= 0 && (i & 7) != 7; --i )
            maskR[sq] |= C64(1) << i;
        for ( i = sq + 1; i < 64 && (i & 7) != 0; ++i )
            maskR[sq] |= C64(1) << i;
        for ( i = sq + 8; i < 64; i += 8 )
            maskR[sq] |= C64(1) << i;
    }
}

For each square there is a maximum number of steps to take. The number 8 is just a variant of the 7th step.

/**
Number of expanding steps (explosions) for a rook
*/
const int repsR[64] =
{
    7, 6, 6, 6, 6, 6, 6, 8,
    7, 5, 5, 5, 5, 5, 5, 8,
    7, 5, 4, 4, 4, 4, 5, 8,
    7, 5, 4, 3, 3, 4, 5, 8,
    7, 5, 4, 3, 3, 4, 5, 8,
    7, 5, 4, 4, 4, 4, 5, 8,
    7, 5, 5, 5, 5, 5, 5, 8,
    7, 6, 6, 6, 6, 6, 6, 8,
};

This does one step of the explosion.
We have a lot of work to avoid overflows, wrap around the unwanted bits.

/*
= init               >>= 8               *= 0x10281         &= mask            at |= bb
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . . . 1 . . . .    . . . 1 . . . .    . . . 1 . . . .
 . . . 1 . . . .     . . . . . . . .     . . 1 . 1 . . .    . . . . . . . .    . . . 1 . . . .
 . . 1 s 1 . . .     . . . 1 . . . .     . 1 . 1 . 1 . .    . 1 . s . 1 . .    . 1 1 s 1 1 . .
 . . . 1 . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .    . . . . . . . .    . . . 1 . . . .
 . . . . . . . .     . . . 1 . . . .     . . . 1 . . . .    . . . 1 . . . .    . . . 1 . . . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
                                       and nasty overflows
*/
Bitboard rookAttacks( int sq, const Bitboard &free )
{
    Bitboard msk = maskR[sq];   // The mask kills scattered bits
    Bitboard bb  = initR[sq];   // This drives the expansion/explosion. Here is the start.
    Bitboard at  = bb;          // Collecting the resulting attacks
    Bitboard cl  = at;          // Clears some intermediate overflows
    Bitboard ov;                // A nasty overflow bit when 4 directions in first step are possible.
                                // Not nessessary on left side of board for repsR[sq] = 4 or 5.
                                // Invent new numbers?
    // Perhaps it would be easier and faster to use rankR[][] on all ranks.
    // But I like the 'explosive' algorithm. And I want to show that it works.
int repsLeft = 0; // will be overwritten
    bb &= free;
    bb >>= 8;
    switch ( repsR[sq] )
    {
      case 8:
        bb *= 0x00010081;
        repsLeft = 5;
        break;
      case 7:
        bb *= 0x00010201;
        repsLeft = 5;
        break;
      case 6:
        bb *= 0x00010281;
        bb &= ~(C64(1) << (sq - 6));      // Clears for b-squares a nasty overflow from south-west-first-step to h file
        repsLeft = 5;
        break;
      case 5:
        bb *= 0x00010281;
        ov = (C64(1) << (sq + 3));
        bb |= (bb & ov) >> 1;
        bb &= ~ov;
        bb &= ~(C64(1) << (sq - 6));      // Clears for b-squares a nasty overflow from south-west-first-step to h file
        repsLeft = 4;
        break;
      case 4:
        bb *= 0x00010281;
        ov = (C64(1) << (sq + 3));
        bb |= (bb & ov) >> 1;
        bb &= ~ov;
        repsLeft = 3;
        break;
      case 3:
        bb *= 0x00010281;
        ov = (C64(1) << (sq + 3));
        bb |= (bb & ov) >> 1;
        bb &= ~ov;
        repsLeft = 2;
        break;
      }
      default:
      /* reaching here is an error */
      break;
    }
    bb &= msk; at |= bb;
    while(repsLeft-- > 0)
    {
        bb &= free; bb &= ~cl;
        cl = at;
        bb >>= 8; bb *= 0x00010281; bb &= msk; at |= bb;
    }
    if ( sq < 8 ) // or do this before the switch
    {
        int a1a8 = free ;
        at |= rankR[sq][a1a8 & 0x7e];
    }
    return at;
}

There are some possible optimisations when the repsR[] array is modified in the corners during
the game or search. Some numbers 9, 10, 11 combined with additional switch cases can work
as a shortcut for rooks in the corners behind pawns.

In the function rookAttacks() rankR is the well know simple lookup table from other bitboard algorithms.

int rankR[8][128];
void makeRankR()
{
    for ( int sq = 0; sq < 8; ++sq )
    {
        for ( int i = 0; i < 128; i += 2 )
        {
            int rr = 0;
            int j;
            for ( j = sq - 1; j >= 0; --j )
            {
                rr |= (1 << j);
                if ( !(i & (1 << j)) )  // the 1 bits are the free squares
                    break;
            }
            for ( j = sq + 1; j < 8; ++j )
            {
                rr |= (1 << j);
                if ( !(i & (1 << j)) )  // the 1 bits are the free squares
                    break;
            }
            rankR[sq][i  ] = rr;
            rankR[sq][i+1] = rr;
        }
    }
}

Results

The results can be masked or combined just like in other attack bitboards.

/*
Get a bitboard with all positions set to 1 which can be attacked
from a rook or queen on the square.
*/
Bitboard Board::orthogonal_attacks( byte square ) const
{
    Bitboard free = ~(wpieces_ | bpieces_); // from the board representation in the board class
    Bitboard result = rookAttacks( square, free );
    return result;
}
 
/*
Get a bitboard with all positions set to 1 which can be attacked
from a bishop or queen on the square.
*/
Bitboard Board::diagonal_attacks( byte square ) const
{
    Bitboard free = ~(wpieces_ | bpieces_); // from the board representation in the board class
    Bitboard result = bishopAttacks( square, free );
    return result;
}

Another usage requires masks

const Bitboard dirMaskRight[8] =
{
    // 0, line_h, line_gh, line_fh, line_eh, line_dh, line_ch, line_bh,
    0, C64(0x0101010101010101), C64(0x0303030303030303), C64(0x0707070707070707), C64(0x0f0f0f0f0f0f0f0f),
    C64(0x1f1f1f1f1f1f1f1f), C64(0x3f3f3f3f3f3f3f3f), C64(0x7f7f7f7f7f7f7f7f)
};
 
const Bitboard dirMaskLeft[8] =
{
    // line_ag, line_af, line_ae, line_ad, line_ac, line_ab, line_a, 0,
    C64(0xfefefefefefefefe), C64(0xfcfcfcfcfcfcfcfc), C64(0xf8f8f8f8f8f8f8f8), C64(0xf0f0f0f0f0f0f0f0),
    C64(0xe0e0e0e0e0e0e0e0), C64(0xc0c0c0c0c0c0c0c0), C64(0x8080808080808080), 0
};
 
const Bitboard dirMaskUp[8] =
{
    // row_28, row_38, row_48, row_58, row_68, row_78, row_8, 0,
    C64(0xffffffffffffff00), C64(0xffffffffffff0000), C64(0xffffffffff000000), C64(0xffffffff00000000),
    C64(0xffffff0000000000), C64(0xffff000000000000), C64(0xff00000000000000), 0
};
 
const Bitboard dirMaskDown[8] =
{
    // 0, row_1, row_12, row_13, row_14, row_15, row_16, row_17,
    0, C64(0x00000000000000ff), C64(0x000000000000ffff), C64(0x0000000000ffffff), C64(0x00000000ffffffff),
    C64(0x000000ffffffffff), C64(0x0000ffffffffffff), C64(0x00ffffffffffffff)
};

to generate attacks in one direction.

/*
Get a bitboard with all positions set to 1 which can be attacked
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board::direction_attacks( byte square, byte dir ) const
{
    Bitboard result;
    Bitboard free = ~(wpieces_ | bpieces_); // from the board representation in the board class
    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    {
      case 1:
        result = rookAttacks( square, free );
        result &= dirMaskRight[square & 7];
        break;
      case 5:
        result = rookAttacks( square, free );
        result &= dirMaskLeft[square & 7];
        break;
      case 7:
        result = rookAttacks( square, free );
        result &= dirMaskDown[square >> 3];
        break;
      case 3:
        result = rookAttacks( square, free );
        result &= dirMaskUp[square >> 3];
        break;
      case 8:
        result = bishopAttacks( square, free );
        result &= dirMaskRight[square & 7];
        result &= dirMaskDown[square >> 3];
        break;
      case 4:
        result = bishopAttacks( square, free );
        result &= dirMaskLeft[square & 7];
        result &= dirMaskUp[square >> 3];
        break;
      case 2:
        result = bishopAttacks( square, free );
        result &= dirMaskRight[square & 7];
        result &= dirMaskUp[square >> 3];
        break;
      case 6:
        result = bishopAttacks( square, free );
        result &= dirMaskLeft[square & 7];
        result &= dirMaskDown[square >> 3];
        break;
      default:
        result = 0;
        break;
    }
    return result;
}

References

^ Re: Compact Bitboard Attacks by Harald Lüßen, Winboard Forum, September 13, 2006

What links here?

Page	Date Edited
Elephant	Sep 19, 2016
Exploding Bitboards	Mar 9, 2015
Harald Lüßen	Mar 20, 2013
Sherwin Bitboards	Mar 20, 2013
Sliding Piece Attacks	May 27, 2016

Up one Level

Hashing Dictionaries

GerdIsenberg — Sat, 01 Mar 2014 13:31:56 GMT

Avoiding Rotated Bitboards with Direct Lookup

Home * Board Representation * Bitboards * Sliding Piece Attacks * Hashing Dictionaries

This approach using associate arrays or hash tables was introduced in the ICGA Journal (June 2007) by Sam Tannous ^[1]. Like other occupancy lookup approaches it works line-wise for ranks, files, diagonals and anti-diagonals. It uses hash arrays from an interpreted, high level language, Python:

Many high level programming languages (notably Python (van Rossum, 1993)) have useful predefined data structures (e.g. associative arrays) which are dynamically resizable hash tables that resolve collisions by probing techniques. The basic lookup function used in Python is based on Algorithm D: Open Addressing with Double Hashing from Section 6.4 in Knuth ^[2].

Avoiding Rotated Bitboards with Direct Lookup

Sam Tannous compared this approach to a Rotated Bitboards implementation in Python and found direct lookup favorable for move generation. In languages like C, targeting 64-bit cpus like x86-64, or even in Java, it is likely another story if one compares Open Addressing with Double Hashing with rotated or perfect hashing techniques like Kindergarten or even Magic Bitboards.

Abstract

Quoted from Avoiding Rotated Bitboards with Direct Lookup:

This paper describes an approach for obtaining direct access to the attacked squares of sliding pieces without resorting to rotated bitboards. The technique involves creating four hash tables using the built in hash arrays from an interpreted, high level language. The rank, file, and diagonal occupancy are first isolated by masking the desired portion of the board. The attacked squares are then directly retrieved from the hash tables. Maintaining incrementally updated rotated bitboards becomes unnecessary as does all the updating, mapping and shifting required to access the attacked squares. Finally, rotated bitboard move generation speed is compared with that of the direct hash table lookup method.

External Links

Sam Tannous homepage

Class Libraries

References

^ Sam Tannous (2007). Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pdf
^ Donald Knuth (1998). The Art of Computer Programming. Volume 3, Sorting and Searching. Addison Wesley. ISBN 0201896850

What links here?

Page	Date Edited
Congruent Modulo Bitboards	Jun 26, 2013
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Hash Table	Jan 1, 2018
Hashing Dictionaries	Mar 1, 2014
Mark Levene	Jun 2, 2015
Python	Jan 31, 2018
Sam Tannous	Mar 1, 2014
Shatranj (toolkit)	May 16, 2015
Sliding Piece Attacks	May 27, 2016
Trevor Fenner	Jun 2, 2015

Up one Level

Hyperbola Quintessence

camleon — Sat, 25 Mar 2017 14:31:28 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Hyperbola Quintessence

Hyperbola Quintessence applies the o^(o-2r)-trick also for vertical or diagonal negative Rays - by reversing the bit-order of up to one bit per rank or byte with a vertical flip aka x86-64 bswap ^[1] . It is somehow a resurrection of the reverse bitboards idea of Ryan Mack's Hyperbola Project on the fly, and was created by Gerd Isenberg. Improvements by Aleks Peshkov ^[2] made it applicable and competitive.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

Samuel Bak - Reflexion, 1990 ^[3]

Reverse Math

Source Code

Generalized set-wise attacks

x86-64 assembly

Java

AMD's SIMD Future in 2011

Reverse Math

Assume following masked occupancy on a file, diagonal or anti-diagonal - for simplicity as a flat byte (in a real bitboard with masked files or diagonals you have 6..8 scratch-bits between the bits of this byte). Thus, vertical flip reverses the bits of this byte.

o' = reverse(o)
r' = reverse(r)
 
       normal    reversed
 o     11010101  10101011 o' occupancy including slider
 r     00010000  00001000 r' slider
 o-r   11000101  10100011 o'-r'  1. sub clears the slider
 o-2r  10110101  10011011 o'-2r' 2. sub borrows "one" from next blocker
       |......|  \....../
normal 10110101   \..../
       11011001 <--XXXX   re-reverse
single
xor    01101100 -> to get the attack set

The first subtraction of (o-2r) is done implicitly by masking off the line, removing the slider from the occupied set. The second subtraction borrows a "one" from the next nearest blocker in msb-direction, falling through all unset bits outside the line. Of course, if no blocker is available, it borrows a "one" in usual arithmetical manner from the hidden 2^N. Only the changed bits (from original o, o') are the appropriate sliding attacks, including the blocker but excluding the slider. The result finally needs to be intersected with the same line mask as previously the occupancy, to clear the wrapped borrow one bits outside the file or diagonal. The fine optimization by Aleks Peshkov covers the final union of positive and negative ray-attacks. Since opposed ray-directions are always disjoint sets, using xor instead of bitwise or safes two instructions per line-attack. That is because bit-reversal or any mirroring or flipping is own inverse and distributive over xor.

reverse(a ^ b) == reverse (a) ^ reverse(b)

thus

lineAttacks = o^(o-2r) ^ reverse((o'-2r')^o')
lineAttacks = o^(o-2r) ^ reverse( o'-2r') ^ reverse(o')
lineAttacks = o^(o-2r) ^ reverse( o'-2r') ^ o

and finally

lineAttacks =   (o-2r) ^ reverse( o'-2r')

Beside shorter code this reduces register pressure - and clearly outperforms kindergarten bitboards - ipc-wise, in code size and memory requirements.

Source Code

C

The three C-routines only differ by the line-mask applied:

U64 diagonalAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward = occ & smsk[sq].diagonalMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].diagonalMaskEx;
   return forward;
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].antidiagMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].antidiagMaskEx;
   return forward;
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].fileMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].fileMaskEx;
   return forward;
}
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return diagonalAttacks (occ, sq)
        + antiDiagAttacks (occ, sq);
}

For better locality of the line-attacks on the otherwise empty board, we may use an properly aligned array of structs.

struct
{
   U64 bitMask;         // 1 << sq for convenience
   U64 diagonalMaskEx;
   U64 antidiagMaskEx;
   U64 fileMaskEx;
} smsk[64]; // 2 KByte

Using x86-64 bswap makes it quite competitive for bishops and files, on AMD K8 or K10 it has a latency of one cycle with a throughput of 1/3, like other cheap instructions. However, Intel is tad slower - while the recent Core 2 duo processors perform 128-bit SIMD-instructions with 128-bit alus, that is bitwise logical instructions with a latency of one cycle and throughput of 1/3, the general purpose bswap-instruction takes four cycles with a throughput of one. In Intel 64 and IA32 Architectures Optimization Reference Manual ^[4] , it is therefor recommend (5.6.5. endian conversion) to use the SSSE3 pshufb instruction to swap bytes, available through intrinsic ^[5] , see SSSE3 Hyperbola Quintessence for bishop attacks.

As long there is no fast bit reversal instruction, there is no general solution for all four lines, and the rook attack-getter still needs some standard technique for the rank-attacks. Tim Cooijmans proposed to map the rank to the main diagonal before applying HQ, and to re-map the calculated attacks back to the original rank ^[6] .

Generalized set-wise attacks

Hyperbola quintessence can be generalized to work on whole sets of sliding pieces instead on individual pieces, whose ranks to be masked. The problem arising, when not masking the rank of the piece is that attacks wrap around the board during subtraction. This is shown below:

     ........       ........                            11111111
     ........       ........                            11111111
     ........       ........                            11111111
 r = ........ , o = ........ this leads to   o - 2*r =  11111111
     ........       ........                            11111111
     ........       ........                            11111111
     ....1...       ....1...                            11111...
     ........       ........                            ........
 
instead of
 
........
........
........
........
........
........
11111...
........

This is not the intended result. It can be avioded, by bitwise adding an overflow barrier on the right-hand side. Afterwards this barrier needs to be removed from the attack set:

u64 right = 0x0101010101010101ULL;
 
     ......1.      1..1..1.                              1...1111
     ....1...      1...1...                              .1111..1
     ......1.      11....1.                              1.111111
r =  .....1..  o = .11..1..   now: ((o | right) - 2*r) = .1.111.1
     ........      ........                              ........
     ......1.      ......1.                              1111111.
     .......1      .......1                              1111111.
     1.......      1.......                              1......1
 
Note, that the 4th rank was not flooded by the subtraction! Next, the blockers are removed as usual:
 
                          ...111.1
                          1111...1
                          .11111.1
o ^ ((o | right) - 2*r) = ..111..1
                          ........
                          111111..
                          11111111
                          .......1
 
The last step is to remove the barrier at the right side that became visible after the last operation.
 
                                     ...111..
                                     1111...
                                     .11111..
(o ^ ((o | right) - 2*r) & ~right =  ..111...
                                     ........
                                     111111..
                                     1111111.
                                     ........
 
This is the correct attack set for the left direction.

the complete algorithm for the left direction is therefore:

const u64 right = 0x0101010101010101ULL;
 
u64 leftAttacks = ((o ^ ((o | right) - 2*r) & ~right);

For the right-hand direction, the bits need to be reversed rank-wise.

x86-64 assembly

The VC2005 generated x86-64 assembly of bishopAttacks indicates what ipc-monster Hyperbola Quintessence is:

occ$ = 16
sq$ = 24
?bishopAttacks@@YA_K_KI@Z PROC
  00000   40 53                push    rbx
  00002   8b c2                mov    eax, edx
  00004   4c 8d 15 00 00 00 00 lea    r10, OFFSET FLAT:?smsk
  0000b   48 c1 e0 05          shl    rax, 5
  0000f   4a 8b 5c 10 08       mov    rbx, QWORD PTR [rax+r10+8]  ; diagonalMaskEx
  00014   4e 8b 4c 10 10       mov    r9,  QWORD PTR [rax+r10+16] ; antidiagMaskEx
  00019   4e 8b 14 10          mov    r10, QWORD PTR [rax+r10]    ; r := 1 << sq
  0001d   4c 8b db             mov    r11, rbx                    ; diagonalMaskEx
  00020   49 8b d1             mov    rdx, r9                     ; antidiagMaskEx
  00023   4d 8b c2             mov    r8, r10                     ; r := 1 << sq
  00026   48 23 d1             and    rdx, rcx                    ; anti & occ
  00029   4c 23 d9             and    r11, rcx                    ; dia  & occ
  0002c   49 0f c8             bswap  r8                          ; r'
  0002f   48 8b c2             mov    rax, rdx                    ; ant
  00032   49 8b cb             mov    rcx, r11                    ; dia
  00035   49 2b d2             sub    rdx, r10                    ; ant - r
  00038   48 0f c8             bswap  rax                         ; ant'
  0003b   48 0f c9             bswap  rcx                         ; dia'
  0003e   4d 2b da             sub    r11, r10                    ; dia - r
  00041   49 2b c0             sub    rax, r8                     ; ant' - r'
  00044   49 2b c8             sub    rcx, r8                     ; dia' - r'
  00047   48 0f c8             bswap  rax                         ;(ant' - r')'
  0004a   48 0f c9             bswap  rcx                         ;(dia' - r')'
  0004d   48 33 c2             xor    rax, rdx                    ; ant := (ant' - r')' ^ (ant - r)
  00050   49 33 cb             xor    rcx, r11                    ; dia := (dia' - r')' ^ (dia - r)
  00053   49 23 c1             and    rax, r9                     ; ant &= antidiagMaskEx
  00056   48 23 cb             and    rcx, rbx                    ; dia &= diagonalMaskEx
  00059   48 03 c1             add    rax, rcx                    ; attacks := dia + ant
  0005c   5b                   pop    rbx
  0005d   c3                   ret    0
?bishopAttacks@@YA_K_KI@Z ENDP

Java

Java programmer may try Long.reverseBytes:

    static private final long[] bitMask = {
        0x0000000000000001, 0x0000000000000002, 0x0000000000000004, 0x0000000000000008,
        0x0000000000000010, 0x0000000000000020, 0x0000000000000040, 0x0000000000000080,
        ...
    };
 
    static private final long[] diagonalMaskEx = {
        0x8040201008040200, 0x0080402010080400, 0x0000804020100800, 0x0000008040201000,
        0x0000000080402000, 0x0000000000804000, 0x0000000000008000, 0x0000000000000000,
        ...
    };
 
    /**
     * @param occ - occupancy
     *        sq  - from square
     * @return diagonal attacks from sq with occupancy occ
     */
    static public long diagonalAttacks(long occ, int sq)
    {
       long forward = occ & diagonalMaskEx[sq];
       long reverse = Long.reverseBytes(forward);
       forward -= bitMask[sq];
       reverse -= bitMask[sq^56];
       forward ^= Long.reverseBytes(reverse);
       forward &= diagonalMaskEx[sq];
       return forward;
    }

Long.reverse for a generalized attack getter even for ranks is too expensive, except a JVM can use a machine instruction rather than a bit-reversal routine:

    /**
     * @param occ  - occupancy
     *        line - {0..3} {rank, file, diagonal, antidiagonal}
     *        sq   - from square
     * @return attacks from sq on line with occupancy occ
     */
    static public long attacks(long occ, int line, int sq)
    {
       long forward = occ & maskEx[sq][line];
       long reverse = Long.reverse(forward);
       forward -= bitMask[sq];
       reverse -= bitMask[sq^63];
       forward ^= Long.reverse(reverse);
       forward &= maskEx[sq][line];
       return forward;
    }

AMD's SIMD Future in 2011

In 2007 AMD announced the hypothetical SSE5 instruction set ^[7] with a PPERM instruction ^[8] , which would be able to reverse vectors of two bitboards. In May 2009 AMD revised SSE5, to become more compatible with Intel's Advanced Vector Extensions, and also expanding the SIMD-register width from 128 to 256-bit, the renamed XOP instruction set ^[9] . However, the successor of the planned PPERM SSE5-instruction is now called VPPERM, but still works on 128-bit XMM registers ^[10] . VPPERM instruction requires four operands (xmm-registers):

 VPPERM dest, src1, src2, selector

For each of 16 destination bytes the corresponding selector-byte addresses one of 32 input bytes (from src1, src2) and a logical operation including bit-reversal:

char src[32];   // src2:src1
char select[16];
char dest[16];
for (int i = 0; i < 16; i++) {
   char opera = select[i] >>> 5; // unsigned shift
   char idx32 = select[i] & 31;
 
   switch ( opera ) {
      case 0: dest[i] =  src[idx32]; break;
      case 1: dest[i] = ~src[idx32]; break;
      case 2: dest[i] =  bitreverse( src[idx32]); break;
      case 3: dest[i] = ~bitreverse( src[idx32]); break;
      case 4: dest[i] = 0x00; break;
      case 5: dest[i] = 0xFF; break;
      case 6: dest[i] =  src[idx32] >> 7;  break; // signed shift
      case 7: dest[i] = ~src[idx32] >> 7;  break; // signed shift
   }
}

Since VPPERM can simultaneously reverse bits and bytes, it can for instance reverse two bitboards in one run, even from different sources, to make Hyperbola Quintessence work for all four lines.

Forum Posts

Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Aleks Peshkov, CCC, August 25, 2007
Hyperbola Quiesscene: hardly any improvement by trojanfoe, CCC, January 13, 2009
Comparison of bitboard attack-getter variants by Sven Schüle, CCC, January 04, 2016
Re: The wrong way by Aleks Peshkov, CCC, January 05, 2016 » SSSE3 Hyperbola Quintessence

External Links

Sliding Pieces (Part 1) - Advanced Java Chess Engine Tutorial 8 by Jonathan Warkentin
Hyperbola Quintessence for rooks along ranks by Tim Cooijmans, April 6, 2014 ^[11]

Hyperbola

Quintessence

Misc

Focus - Hocus Pocus, Pinkpop Festival 1972, Geleen, YouTube Video

References

^ _byteswap_uint64 Visual C++ Developer Center - Run-Time Library Reference
^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Aleks Peshkov, CCC, August 25, 2007
^ The Game of War from Samuel Bak - represented by Pucker Gallery since 1969
^ Intel 64 and IA32 Architectures Optimization Reference Manual (pdf)
^ _mm_shuffle_epi8 Visual C++ Developer Center - Run-Time Library Reference
^ Hyperbola Quintessence for rooks along ranks by Tim Cooijmans, April 6, 2014
^ 128-Bit SSE5 Instruction Set from AMD Developer Central
^ SSE5 permutations
^ XOP instruction set from Wikipedia
^ Volume 6: 128-Bit and 256-Bit XOP, FMA4 and CVT16 Instructions (pdf), see VPPERM pg. 221
^ Re: Comparison of bitboard attack-getter variants by Matthew R. Brades, CCC, January 04, 2016

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
Amoeba	Mar 19, 2018
Dumb	Mar 10, 2018
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Endianness	Jan 25, 2015
Fill Algorithms	Nov 6, 2013
First Rank Attacks	Aug 28, 2010
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Java	Feb 25, 2018
Jonathan Warkentin	Jun 29, 2014
Karlo Bala Jr.	Feb 19, 2017
Kindergarten Bitboards	Aug 1, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Parallel Prefix Algorithms	Jun 22, 2016
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
SBAMG	Dec 4, 2016
SIMD techniques	Nov 26, 2017
Sliding Piece Attacks	May 27, 2016
SSSE3	Aug 8, 2017
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Syed Fahad	Jan 1, 2017
XOP	Aug 8, 2017

Up one Level

Kindergarten Bitboards

GerdIsenberg — Tue, 01 Aug 2017 19:55:05 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Kindergarten Bitboards

		Kindergarten bitboards ^[1] was a kind of interactive forum development ^[2] with a lot of meanders ^[3] . There were two issues involved - first to calculate the occupancy of any line from the occupied bitboard ^[4] - and second, compact and dense lookup tables. As a quintessence Gerd Isenberg came up with this nomination. It relies on fast 64-bit multiplication, but is otherwise quite resource friendly and a compromise between calculation and table-size.
Paul Klee, Group of Masks, 1939 ^[5]

Ranks and Diagonals

Ranks and diagonals - that is their appropriate line-mask by square-index - are first intersected by the occupancy of the whole board. Doesn't matter whether the slider itself is cleared or not - it is redundant anyway, considered by the pre-calculated lookup-table.

Since there is only up to one bit per file, the north-fill multiplication by the A-file maps the diagonal to the 8th rank. Or - since we only need the inner six bits, we combine the required shift left one by multiplying with the B-file. Shifting right the product by 58 (64-6) leaves the six-bit occupancy-index in the 0..63 range. For instance the diagonal-attacks of a bishop on d4. 'A'-'H' represent the masked occupied bits along this diagonal, which are either zero or one.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

We need 'B'-'G' as six bit number:

masked line      *  B-File           =  B-G upper six       occupancy 6 bit
. . . . . . . H     . 1 . . . . . .     . A[B C . E F G]    . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . A B C . E F G     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . A B C . E F .     . . . . . . . .
. . . . E . . .     . 1 . . . . . .     . A B C . E . .  >> . . . . . . . .
. . . . . . . .  *  . 1 . . . . . .  =  . A B C . . . .  58 . . . . . . . .
. . C . . . . .     . 1 . . . . . .     . A B C . . . .     . . . . . . . .
. B . . . . . .     . 1 . . . . . .     . A B . . . . .     . . . . . . . .
A . . . . . . .     . 1 . . . . . .     . A . . . . . .    [B C . E F G]. .

The pre-calculated lookup-table contains the attacks of the first rank - but eight copies in each rank or byte. It is indexed by the six bit occupied-state ('B'-'G') and the file of the slider's square. It needs to be intersected with the same line-mask as formerly the occupancy - to map the first rank attack bits to the appropriate line - that's all. Appropriate pre-calculated attack bits are represented by 'a'-'h':

8 copies of rank      the attack set
attacks & l-mask  ->  of this line
a b c . e f g h       . . . . . . . h
a b c . e f g h       . . . . . . g .
a b c . e f g h       . . . . . f . .
a b c . e f g h       . . . . e . . .
a b c . e f g h       . . . . . . . .
a b c . e f g h       . . c . . . . .
a b c . e f g h       . b . . . . . .
a b c . e f g h       a . . . . . . .

Since all ranks, diagonals and anti-diagonals are properly file-aligned, it works perfectly with some redundant occupied bits for shorter diagonals as well, like here the outer bit 'B':

masked line      *  B-File           =  B-G upper six       occupancy 6 bit
. . . . . . . .     . 1 . . . . . .     H .[B C . E F G]    . . . . . . . .
. . . . . . . H     . 1 . . . . . .     . . B C . E F G     . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . . B C . E F G     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . . B C . E F .  >> . . . . . . . .
. . . . E . . .  *  . 1 . . . . . .  =  . . B C . E . .  58 . . . . . . . .
. . . . . . . .     . 1 . . . . . .     . . B C . . . .     . . . . . . . .
. . C . . . . .     . 1 . . . . . .     . . B C . . . .     . . . . . . . .
. B . . . . . .     . 1 . . . . . .     . . B . . . . .    [B C . E F G]. .

Appropriate pre-calculated attack bits are represented by 'b'-'h' here:

8 copies of rank      the attack set   or  the attack set
attacks & l-mask  ->  of this line     ->  of the shorter diagonal
a b c . e f g h       . . . . . . . h      . . . . . . . .
a b c . e f g h       . . . . . . g .      . . . . . . . h
a b c . e f g h       . . . . . f . .      . . . . . . g .
a b c . e f g h       . . . . e . . .      . . . . . f . .
a b c . e f g h       . . . . . . . .      . . . . e . . .
a b c . e f g h       . . c . . . . .      . . . . . . . .
a b c . e f g h       . b . . . . . .      . . c . . . . .
a b c . e f g h       a . . . . . . .      . b . . . . . .

Wasn't that simple? That is why it is called kindergarten bitboards!

The trick is to share one 4KByte table by three line-directions by re-using the mask for a final intersection. Of course one may use the calculated occupied state to index rotated bitboards like tables of 32KByte each. But dividing the table size by 3*8 on the cost of that additional 'and' (and keeping the mask inside a register) is tempting. Of course - like always with computation versus memory issues - it depends on the cache- and memory using and footprint inside a particular chess program and the hardware architecture, which solution is preferable. So far L1 Cache is a rare resource, Translation Lookaside Buffer als well.

Like other none rotated approaches, namely magic bitboards or hyperbola quintessence, the nice thing is that one can hide the implementation details behind a stateless interface. In C /C++ one may use header files with exclusive, conditional compiled inlined routines, as combinations and variations of the mentioned approaches.

The three routines only differ by the line-mask applied. As pointed out by Aleks Peshkov, it is smarter to index by file, occupancy, since fillUpAttacks[sq&7] may be shared by two (bishop) or three (queen) line-attack getters.

U64 fillUpAttacks[8][64];  // 4 KByte
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   const U64 bFile = C64(0x0202020202020202);
   occ = (diagonalMaskEx[sq] & occ) * bFile >> 58;
   return diagonalMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   const U64 bFile = C64(0x0202020202020202);
   occ = (antidiagMaskEx[sq] & occ) * bFile >> 58;
   return antidiagMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
 
U64 rankAttacks(U64 occ, enumSquare sq) {
   const U64 bFile = C64(0x0202020202020202);
   occ = (rankMaskEx[sq] & occ) * bFile >> 58;
   return rankMaskEx[sq] & fillUpAttacks[sq&7][occ];
}

One may use similar structs for the line-masks than the hyperbola quintessence.

File-Attacks

Files need tad more work. Shift the board left (arithmetical right!) to the A-file to mask it. To get the inner six bits, a flip-multiplication by the c2-h7 diagonal is applied with further shift right 58. The lookup-table contains the A-file attacks, which are shifted "back" to the original file.

U64 aFileAttacks [8][64];  // 4 KByte
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   const U64 aFile   = C64(0x0101010101010101);
   const U64 diac2h7 = C64(0x0080402010080400);
   occ = aFile  & (occ >> (sq&7));
   occ = (diac2h7 *  occ ) >> 58;
   return aFileAttacks[sq>>3][occ] << (sq&7);
}

This is how it works:

masked A-file    *  c2-h7 Diagonal    =  occupancy
H . . . . . . .     . . . . . . . .     . .[G F E D C B]    . . . . . . . .
G . . . . . . .     . . . . . . . 1     . . F E D C B A     . . . . . . . .
F . . . . . . .     . . . . . . 1 .     . . E D C B A .     . . . . . . . .
E . . . . . . .     . . . . . 1 . .     . . D C B A . .  >> . . . . . . . .
D . . . . . . .  *  . . . . 1 . . .  =  . . C B A . . .  58 . . . . . . . .
C . . . . . . .     . . . 1 . . . .     . . B A . . . .     . . . . . . . .
B . . . . . . .     . . 1 . . . . .     . . A . . . . .     . . . . . . . .
A . . . . . . .     . . . . . . . .     . . . . . . . .    [G F E D C B]. .

Note that the six inner bit occupancy is reversed - considered in the pre-calculated aFileAttacks array. This reversed lookup was justified to share first rank-attacks by all directions - with a dense lookup of 512 Byte. But the 4KByte tables outperform the additional multiplications and shift of the dense version - and one may alternatively multiply with the flipped diagonal, the c7-h2 anti-diagonal:

masked A-file    *  c7-h2 AntiDiag   =  occupancy
H . . . . . . .     . . . . . . . .     . .[B C D E F G]    . . . . . . . .
G . . . . . . .     . . 1 . . . . .     . . A B C D E F     . . . . . . . .
F . . . . . . .     . . . 1 . . . .     . . . A B C D E     . . . . . . . .
E . . . . . . .     . . . . 1 . . .     . . . . A B C D  >> . . . . . . . .
D . . . . . . .  *  . . . . . 1 . .  =  . . . . . A B C  58 . . . . . . . .
C . . . . . . .     . . . . . . 1 .     . . . . . . A B     . . . . . . . .
B . . . . . . .     . . . . . . . 1     . . . . . . . A     . . . . . . . .
A . . . . . . .     . . . . . . . .     . . . . . . . .    [B C D E F G]. .

Shared Rank Lookup

As often, computation versus memory size. One may share a 512Byte Lookup of the first rank by all lines with some trailing computation. Multiplying with the A-file (fill north) for ranks and diagonals, and multiplying with the diagonal for the file. Likely the additional multiplication don't pays off.

const BYTE firstRankAttacks[8][64];
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   const U64 aFile   = C64(0x0101010101010101);
   const U64 hFile   = C64(0x8080808080808080);
   const U64 diaa1h8 = C64(0x8040201008040201);
   const U64 diac2h7 = C64(0x0080402010080400);
 
   unsigned int f = sq & 7;
   occ =   aFile   & (occ   >>  f);
   occ = ( diac2h7 *  occ ) >> 58;
   occ =   diaa1h8 * firstRankAttacks[(sq^56)>>3][occ];
   return ( hFile  &  occ ) >> (f^7);
}
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   const U64 aFile = C64(0x0101010101010101);
   const U64 bFile = C64(0x0202020202020202);
 
   unsigned int f = sq & 7;
   occ  =  diagonalMaskEx[sq] & occ;
   occ  = (bFile * occ ) >> 58;
   occ  =  aFile *  firstRankAttacks[f][occ];
   return  diagonalMaskEx[sq] & occ;
}

32-bit Versions

One other variation of the memory versus computation theme was encouraged by 32-bit mode. 64-bit multiplication is quite expensive in 32-bit mode - a call using three imuls. Thus, it is more efficient to use shift-or plus 32-bit multiplication, which might in fact be used in 64-bit mode as well. Piotr Cichy proposed a multiplication less parallel prefix shift approach similar to Occupancy of any Line ^[6] , which is a good alternative for processors with slow multiplication.

An efficient and tricky file-approach was introduced by Zach Wegner ^[7], using a 32KByte, rotated like lookup-table:
It is quite strange, yes, but it is an out of order mapping. There are only 5 bits because each bit in the factor maps more than one bit. The trick here is the odd shift 29, so that the multiply does not overflow individual bits. I have since found that 25 and 27 will work with the same magic:

occ
. . . . . . . .
a . . . . . . .
b . . . . . . .    occ | occ >> 29    * 0x01041041 with the index bracketed
c . . . . . . .    ...\               ...\               ...\
d . . . . . . .    d . . . . . . .    1 . . . . . . .    d a[f c e b d a]
e . . . . . . .    e . . a . . . .    . . 1 . . . . .    e b . a f c e b
f . . . . . . .    f . . b . . . .    . . . . 1 . . .    f c . b . . f c
. . . . . . . .    . . . c . . . .    1 . . . . . 1 .    . . . c . . . .

The interesting thing is that this works for any masked file. In fact if it was shifted to the a-file, you could get away with the 3-bit factor 0x00041040 (but using a shift of 23).

U64 arrFileAttacks[64][64]; // [sq][occ64] 32KByte
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   occ &= fileMask[sq];
   U32 fold  = (U32)occ | (U32)(occ >> 29);
   U32 occ64 = fold * 0x01041041 >> 26;
   return arrFileAttacks[sq][occ64];
}

Ranks and diagonals are trivial, this version favors rotated like memory size for less computation and same operations than file-attacks. One may therefor generalize the routine by a line-direction parameter:

U64 arrDiagonalAttacks[64][64]; // [sq][occ64] 32KByte
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   occ &= diagonalMaskEx[sq];
   U32 fold  = (U32)occ | (U32)(occ >> 32);
   U32 occ64 = fold * 0x02020202 >> 26;
   return arrDiagonalAttacks[sq][occ64];
}

A similar approach was proposed by Andrew Fan in 2009, been active in his own engine for a few years (2006 earliest recorded file time) ^[8].

Magic Compression

So far Kindergarten bitboards performs a perfect hashing of the up to six relevant and scattered occupied bits of any line to a six-bit index - which is a bijective mapping of 64 different occupancies per line to 64 indices for the precalculated attack sets.

If we have a closer look to the attack sets, say of a rook on the a-file, we enumerate far less disjoint sets. A rook on a1 (a8) has seven different attack-sets on that file, depending on the occupancy of a2-a7. On a2 (a7) there is even one attack set less, on a3 (a6) 2 times 5 and on a4 (a5) 3 times 4 attack-sets. Thus, there are {7, 6, 10, 12, 12, 10, 6, 7} disjoint attack-sets per square on line, or 70 in total over all eight squares.

While kindergarten bitboards apply a minimal perfect mapping of scattered bits to a six-bit index, the mapping of the attack-sets is surjective, since each of the 64 occupancies maps only up to 12 distinct sets. Of course that is because occupancies "behind" the first blocker are redundant and map the same attack.

Grant Osborne came up with the idea, derived from magic bitboards - to use different "magic" factors per square (rank), where multiplication may produce carries and enough so called constructive collisions to gain only five or even four bit indices and therefor denser tables. Since different squares may have different table sizes (16 or 32 entries), a Java-like array is used for the attacks, in C implemented as array of pointers to the arbitrary sized attack tables. The variable right shift by either 60 or 59 is encoded inside the otherwise redundant upper six bits of the magic factor, as mentioned in incorporating the shift of magic bitboards.

Grant's proposal, so far with {5,4,4,5,5,4,4,5} bit ranges for the lookups per square for vertical rook attacks, results in a 1.5 KByte array instead the 4KByte of the initial Kindergarten file attack getter ^[9] . Whether the effort of the rank-indexed magic-factor plus additional pointer indirection pays off the memory saving is another question, and should be tried inside a concrete chess program with its individual cache- and memory footprint.

U64 aFileAttacks[4*32+4*16]; // 1.5KByte
U64 aPtrFileAttacks[8]; // points to appropriate aFileAttacks
U64 fileMagic[8] = {
   0xEFFFA39DB01B23A3, // 5-bit
   0xF024691A3227FF42, // 4-bit
   0xF2808817CAD6FF0C, // 4-bit see below
   0xED6EDFBE467977D5, // 5-bit
   0xEC87CB0D961EC43A, // 5-bit
   0xF2FF594E14D8801C, // 4-bit
   0xF2FF5D69D4E3E7D6, // 4-bit
   0xEE404B349599FF88  // 5-bit
};
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rank = sq >> 3;
 
   occ =  0x0001010101010100 & (occ >> file);
   occ = (fileMagic[rank] * occ) >> (fileMagic[rank] >> 58);  // four&five bit index
   return *(aPtrFileAttacks[rank] + occ) << file;
}

occupancy (A-File)	product	index 0..15	attack set
o - outer squares don't care x - empty or any piece . - empty b - Blocker - any piece R - Rook	occupancy * 0xF2808817CAD6FF0C	upper nibble in product	1 attacked . not attacked
o x x x b R b o	1. attack-set		. . . . 1 . 1 .
0x0000010101000100	0x3A28F9D5E2FF0C00	3	0x0000000001000100
0x0001010101000100	0x3934F9D5E2FF0C00	3	0x0000000001000100
0x0000000101000100	0x6329EDD5E2FF0C00	6	0x0000000001000100
0x0000010001000100	0x6F51FAC9E2FF0C00	6	0x0000000001000100
0x0001000101000100	0x6235EDD5E2FF0C00	6	0x0000000001000100
0x0001010001000100	0x6E5DFAC9E2FF0C00	6	0x0000000001000100
0x0000000001000100	0x9852EEC9E2FF0C00	9	0x0000000001000100
0x0001000001000100	0x975EEEC9E2FF0C00	9	0x0000000001000100
o x x x b R . o	2. attack set		. . . . 1 . 1 1
0x0000000001000000	0x17CAD6FF0C000000	1	0x0000000001000101
0x0001000001000000	0x16D6D6FF0C000000	1	0x0000000001000101
0x0000010101000000	0xB9A0E20B0C000000	11	0x0000000001000101
0x0001010101000000	0xB8ACE20B0C000000	11	0x0000000001000101
0x0000000101000000	0xE2A1D60B0C000000	14	0x0000000001000101
0x0000010001000000	0xEEC9E2FF0C000000	14	0x0000000001000101
0x0001000101000000	0xE1ADD60B0C000000	14	0x0000000001000101
0x0001010001000000	0xEDD5E2FF0C000000	14	0x0000000001000101
o x x b . R b o	3. attack set		. . . 1 1 . 1 .
0x0001010100000100	0x216A22D6D6FF0C00	2	0x0000000101000100
0x0000010100000100	0x225E22D6D6FF0C00	2	0x0000000101000100
0x0000000100000100	0x4B5F16D6D6FF0C00	4	0x0000000101000100
0x0001000100000100	0x4A6B16D6D6FF0C00	4	0x0000000101000100
o x x b . R . o	4. attack set		. . . 1 1 . 1 1
0x0000010100000000	0xA1D60B0C00000000	10	0x0000000101000101
0x0001010100000000	0xA0E20B0C00000000	10	0x0000000101000101
0x0000000100000000	0xCAD6FF0C00000000	12	0x0000000101000101
0x0001000100000000	0xC9E2FF0C00000000	12	0x0000000101000101
o x b . . R b o	5. attack set		. . 1 1 1 . 1 .
0x0000010000000100	0x578723CAD6FF0C00	5	0x0000010101000100
0x0001010000000100	0x569323CAD6FF0C00	5	0x0000010101000100
o x b . . R . o	6. attack set		. . 1 1 1 . 1 1
0x0000010000000000	0xD6FF0C0000000000	13	0x0000010101000101
0x0001010000000000	0xD60B0C0000000000	13	0x0000010101000101
o b . . . R b o	7. attack set		. 1 1 1 1 . 1 .
0x0001000000000100	0x7F9417CAD6FF0C00	7	0x0001010101000100
o b . . . R . o	8. attack set		. 1 1 1 1 . 1 1
0x0001000000000000	0xFF0C000000000000	15	0x0001010101000101
o . . . . R b o	9. attack set		1 1 1 1 1 . 1 .
0x0000000000000100	0x808817CAD6FF0C00	8	0x0101010101000100
o . . . . R . o	10. attack set, no blocker		1 1 1 1 1 . 1 1
0x0000000000000000	0x0000000000000000	0	0x0101010101000101

The table demonstrates how it works for file-attack of the a3 rook with a four bit range only five relevant occupied bits, since a3 is member of the inner six bits. The empirical determined factor is 0xF2808817CAD6FF0C, six upper bits contain the right shift for the product, for this square shift 60:
occupancy (A-File) product index 0..15 attack set o - outer squares don't care x - empty or any piece . - empty b - Blocker - any piece R - Rook occupancy * 0xF2808817CAD6FF0C upper nibble in product 1 attacked . not attacked o x x x b R b o 1. attack-set . . . . 1 . 1 . 0x0000010101000100 0x3A28F9D5E2FF0C00 3 0x0000000001000100 0x0001010101000100 0x3934F9D5E2FF0C00 3 0x0000000001000100 0x0000000101000100 0x6329EDD5E2FF0C00 6 0x0000000001000100 0x0000010001000100 0x6F51FAC9E2FF0C00 6 0x0000000001000100 0x0001000101000100 0x6235EDD5E2FF0C00 6 0x0000000001000100 0x0001010001000100 0x6E5DFAC9E2FF0C00 6 0x0000000001000100 0x0000000001000100 0x9852EEC9E2FF0C00 9 0x0000000001000100 0x0001000001000100 0x975EEEC9E2FF0C00 9 0x0000000001000100 o x x x b R . o 2. attack set . . . . 1 . 1 1 0x0000000001000000 0x17CAD6FF0C000000 1 0x0000000001000101 0x0001000001000000 0x16D6D6FF0C000000 1 0x0000000001000101 0x0000010101000000 0xB9A0E20B0C000000 11 0x0000000001000101 0x0001010101000000 0xB8ACE20B0C000000 11 0x0000000001000101 0x0000000101000000 0xE2A1D60B0C000000 14 0x0000000001000101 0x0000010001000000 0xEEC9E2FF0C000000 14 0x0000000001000101 0x0001000101000000 0xE1ADD60B0C000000 14 0x0000000001000101 0x0001010001000000 0xEDD5E2FF0C000000 14 0x0000000001000101 o x x b . R b o 3. attack set . . . 1 1 . 1 . 0x0001010100000100 0x216A22D6D6FF0C00 2 0x0000000101000100 0x0000010100000100 0x225E22D6D6FF0C00 2 0x0000000101000100 0x0000000100000100 0x4B5F16D6D6FF0C00 4 0x0000000101000100 0x0001000100000100 0x4A6B16D6D6FF0C00 4 0x0000000101000100 o x x b . R . o 4. attack set . . . 1 1 . 1 1 0x0000010100000000 0xA1D60B0C00000000 10 0x0000000101000101 0x0001010100000000 0xA0E20B0C00000000 10 0x0000000101000101 0x0000000100000000 0xCAD6FF0C00000000 12 0x0000000101000101 0x0001000100000000 0xC9E2FF0C00000000 12 0x0000000101000101 o x b . . R b o 5. attack set . . 1 1 1 . 1 . 0x0000010000000100 0x578723CAD6FF0C00 5 0x0000010101000100 0x0001010000000100 0x569323CAD6FF0C00 5 0x0000010101000100 o x b . . R . o 6. attack set . . 1 1 1 . 1 1 0x0000010000000000 0xD6FF0C0000000000 13 0x0000010101000101 0x0001010000000000 0xD60B0C0000000000 13 0x0000010101000101 o b . . . R b o 7. attack set . 1 1 1 1 . 1 . 0x0001000000000100 0x7F9417CAD6FF0C00 7 0x0001010101000100 o b . . . R . o 8. attack set . 1 1 1 1 . 1 1 0x0001000000000000 0xFF0C000000000000 15 0x0001010101000101 o . . . . R b o 9. attack set 1 1 1 1 1 . 1 . 0x0000000000000100 0x808817CAD6FF0C00 8 0x0101010101000100 o . . . . R . o 10. attack set, no blocker 1 1 1 1 1 . 1 1 0x0000000000000000 0x0000000000000000 0 0x0101010101000101

Forum Posts

Re: Rotated bitboards by Urban Koistinen, rgcc, October 31, 1997 » Collapsed files, Collapsed ranks
rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
Compact Bitboard Attacks by Tom Likens, Winboard Forum, March 14, 2006
Zach's tricky 32-bit approach by Zach Wegner, Winboard Forum, August 22, 2006
Magic Bitboards Explained! by Michael Sherwin, Winboard Forum, December 04, 2006
Kindergarten Bitboard Approach by Gerd Isenberg by Edsel Apostol, CCC, November 05, 2008 » OliThink
Kindergarten bitboards without multiplying by Piotr Cichy, CCC, August 07, 2009
Kindergarten Bitboard help by Gregory Strong, CCC, November 22, 2009
32-bit Magic experiments by Andrew Fan, Winboard Forum, December 03, 2009 » Magic Bitboards
Kindergarten bitboards and Xiangqi move genaration? by Han Chengye, CCC, December 30, 2009 » Chinese Chess

External Links

Kindergarten from Wikipedia
George Benson - This Masquerade, 1976, YouTube Video
Pat Metheny and friends - This Masquerade, Jazz Baltica, July 6, 2003, YouTube Video
Nils Landgren, Lars Danielsson, Wolfgang Haffner, Esbjörn Svensson, Pat Metheny, Michael Brecker

References

^ Magic Bitboards Explained! by Michael Sherwin and reply by Gerd Isenberg to call it Kindergarten Bitboards, Winboard Forum, December 4, 2006
^ Compact Bitboard Attacks by Tom Likens, Winboard Forum, March 14, 2006
^ rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
^ Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
^ IMAGINE - The Israel Museum's searchable collections database
^ Kindergarten bitboards without multiplying by Piotr Cichy, CCC, August 07, 2009
^ Zach's tricky 32-bit approach by Zach Wegner, Winboard Forum, August 22, 2006
^ 32-bit Magic experiments by Andrew Fan, Winboard Forum, December 03, 2009
^ Re: How to reduce the "bits" used in a magic number by Grant Osborne, CCC, July 04, 2008

What links here?

Page	Date Edited
More Links
Andreas Guettinger	Aug 14, 2013
Andrew Fan	Jul 30, 2017
Array	Dec 1, 2016
Bitboard Serialization	Dec 24, 2014
BMI2	Mar 6, 2018
Chinese Chess	Jan 16, 2018
Chiron	Sep 24, 2017
Congruent Modulo Bitboards	Jun 26, 2013
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Exploding Bitboards	Mar 9, 2015
Firefly	Oct 23, 2017
First Rank Attacks	Aug 28, 2010
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
Grant Osborne	Dec 2, 2011
Gregory Strong	Apr 24, 2017
Hash Table	Jan 1, 2018
Hashing Dictionaries	Mar 1, 2014
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Jazz	Oct 4, 2017
Kindergarten Bitboards	Aug 1, 2017
Kurt	Apr 20, 2014
Magic Bitboards	Apr 13, 2018
Mark Levene	Jun 2, 2015
Occupancy of any Line	Sep 16, 2016
OliThink	May 19, 2017
Protector	Oct 12, 2017
Rodent	Jan 11, 2018
Rotated Bitboards	Mar 7, 2017
SIMD techniques	Nov 26, 2017
Simplex	Mar 6, 2016
Sjaak (Glebbeek)	Oct 4, 2017
Sliding Piece Attacks	May 27, 2016
Space-Time Tradeoff	Jun 17, 2015
Sungorus	Apr 11, 2014
Tigran	Aug 16, 2015
Tom Likens	Mar 7, 2017
Trevor Fenner	Jun 2, 2015
Vajolet	Jan 25, 2018

Up one Level

Magic Bitboards

GerdIsenberg — Fri, 13 Apr 2018 13:09:31 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Magic Bitboards

		Magic bitboards, a multiply-right-shift perfect hashing algorithm to index an attack bitboard database - which leaves both line-attacks of bishop or rook in one run. Thanks to the fast 64-bit multiplication and fast and huge caches of recent processors, Magic Bitboards has become a de facto standard of modern bitboard engines, as used for instance in Crafty, Arasan, Stockfish and Houdini. While Robert Hyatt reported no immediate speed gain over Rotated Bitboards in Crafty ^[1] , Jon Dart mentioned a 20-25% speedup ^[2] in Arasan over rotated.
Samuel Bak - Auspicious Moon, 2001 ^[3]

History

The magic bitboard approach was motivated by Gerd Isenberg's multi-direction hashing technique kindergarten bitboards and probably by Gerd's and Tony van Roon-Werten's early trials to map line-wise occupancies by De Bruijn- or random number multiplication ^[4] . Lasse Hansen had the idea to hash the up to twelve relevant occupied bits of both directions of a rook- or bishop movement simultaneously ^[5] .

Pradu Kannan's improvements to Lasse Hansen's initial approach was to introduce a Java-like, two-dimensional array with individual size for each square and all it's relevant occupancies ^[6] . Big savings in table-size - since many squares on either orthogonal or diagonal lines require less bits than others, especially considering the inner six bits. While center squares are more dense for rooks, it is the opposite for bishops ^[7] .

Recently, Robert Purves coined the names Plain and Fancy Magics ^[8] , and found Hansen's initial Plain Magics with 2 MiB table for rooks and 256 KiB for bishops nearly indistinguishable from Fancy (about 800 KiB and 38 KiB) on his Intel i5 with huge L3 smart cache, see plain versus fancy source code. In the same CCC forum thread, Robert Houdart proposed a byte lookup per square for further table reductions.

How it works

A magic move-bitboard generation technique consists of four key steps:

Mask the relevant occupancy bits to form a key. For example if you had a rook on a1, the relevant occupancy bits will be from a2-a7 and b1-g1.
Multiply the key by a "magic number" to obtain an index mapping. This magic number can be generated by brute-force trial and error quite easily although it isn't 100% certain that the magic number is the best possible (see step 3).
Right shift the index mapping by 64-n bits to create an index, where n is the number of bits in the index. A better magic number will have less bits required in the index.
Use the index to reference a preinitialized move database.

The following illustration should give an impression, how magic bitboards work. All masked relevant occupied bits are perfectly hashed to the consecutive occupied state to index the pre-calculated attack-sets. Constructive collisions, where different occupancies map same attack-sets - since different bits are outer redundant bits "behind" the first blocker, are desired and even necessary to apply a perfect hashing with N bits.

                                        any consecutive
relevant occupancy                      combination of
bishop b1, 5 bits                       the masked bits
. . . . . . . .     . . . . . . . .     . . .[C D E F G]
. . . . . . . .     . 1 . . . . . .     . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . . . . . . . .
. . . . E . . .  *  . 1 . . . . . .  =  . . garbage . .    >> (64- 5)
. . . D . . . .     . 1 . . . . . .     . . . . . . . .
. . C . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
bishop d4, 9 bits                       the masked bits
. . . . . . . .     . . . . . . . .     2 4 5 B C E F G]
. . . . . . G .     . . .some . . .     . . . . . . .[1
. 5 . . . F . .     . . . . . . . .     . . . . . . . .
. . 4 . E . . .     . . .magic. . .     . . . . . . . .
. . . . . . . .  *  . . . . . . . .  =  . . garbage . .    >> (64- 9)
. . C . 2 . . .     . . .bits . . .     . . . . . . . .
. B . . . 1 . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
rook d4, 10 bits                        the masked bits
. . . . . . . .     . . . . . . . .     4 5 6 B C E F G]
. . . 6 . . . .     . . .some . . .     . . . . . .[1 2
. . . 5 . . . .     . . . . . . . .     . . . . . . . .
. . . 4 . . . .     . . .magic. . .     . . . . . . . .
. B C . E F G .  *  . . . . . . . .  =  . . garbage . .    >> (64-10)
. . . 2 . . . .     . . .bits . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
rook a1, 12 bits                        the masked bits
. . . . . . . .     . . . . . . . .     5 6 B C D E F G]
6 . . . . . . .     . . .some . . .     . . . .[1 2 3 4
5 . . . . . . .     . . . . . . . .     . . . . . . . .
4 . . . . . . .     . . .magic. . .     . . . . . . . .
3 . . . . . . .  *  . . . . . . . .  =  . . garbage . .    >> (64-12)
2 . . . . . . .     . . .bits . . .     . . . . . . . .
1 . . . . . . .     . . . . . . . .     . . . . . . . .
. B C D E F G .     . . . . . . . .     . . . . . . . .

The above illustration is correct for the b1 bishop, since it has only one ray and one bit per file and works kindergarten like. In general a one to one mapping of N scattered occupied bits to N consecutive bits is not always possible due to overflows. A perfect mapping of N scattered bits to N consecutive bits is likely not minimal for most squares. It requires one or two gaps inside the consecutive N bits, to avoid collisions, blowing up the table size.

But the purpose is to perfectly hash attack-sets rather than consecutive occupied bits. The number of distinct attack-sets is much smaller than the relevant occupancies. Thus, with the help of constructive collisions, some initial guess how to map the bits, and/or trial and error, using exactly N bits is always possible. If one tries hard enough to maximize constructive collisions - even less. There are some N-1 ones reported at Best Magics so far, which will half the individual table size for some squares in the widespread Fancy Magic Bitboards approach.

Perfect Hashing

Magic bitboards applies perfect hashing. A surjective function, to map the vector of all relevant occupancies to a range of attack-sets per square. The less bits the attack-set - the closer the blockers, the more those attack-sets are shared by occupancies with different, but redundant outer squares.

The cardinality of all relevant occupancies is determined by the number of bits to map, varying from five to twelve - thus, the cardinality is the power of two the number of bits, varying from 32 to 4096.
The cardinality of distinct attack-sets is determined by the product of the length of each of the max four direction rays greater than zero (or one). The rook on d4 has 3*4*3*4 = 144 distinct attack-sets, a bishop on a8 has only 7.

The ratio of both cardinalities, that is all relevant occupancies versus the all distinct attack-sets is illustrated below: As a quarter of a board - due to the symmetry, the other squares may deduced by flipping and mirroring. Noticeable is the huge 4096/49 ratio of 2^12 occupied states versus 7 times 7 attack-sets of the edge rooks - 12 bits instead of 6. Those "expensive" squares make constructive collisions very desirable. To become more "minimal" by saving an index bit - to halve down the table for one square or the other.

	bishop on square				rook on square
	A	B	C	D		A	B	C	D
8	64/7	32/6	32/10	32/ 12	8	4096/49	2048/42	2048/ 70	2048/ 84
7	32/6	32/6	32/10	32/ 12	7	2048/42	1024/36	1024/ 60	1024/ 72
6	32/10	32/10	128/40	128/ 48	6	2048/70	1024/60	1024/100	1024/120
5	32/12	32/12	128/48	512/108	5	2048/84	1024/72	1024/120	1024/144

	bishop on square				rook on square
	A	B	C	D		A	B	C	D
8	9.14	5.33	3.20	2.67	8	83.59	48.76	29.26	24.38
7	5.33	5.33	3.20	2.67	7	48.76	28.44	17.07	14.22
6	3.20	3.20	3.20	2.67	6	29.26	17.07	10.24	8.53
5	2.67	2.67	2.67	4.74	5	24.38	14.22	8.53	7.11

The idea to implement minimal perfect hashing by an additional 16-bit indirection turned out to be slower (see conditional compiles in Pradu Kannan's source ^[9] ).

Recent table sizes were about 38 KiB for the bishop attacks, but still about 800 KiB for rook attacks (Fancy). That sounds huge, considering L1 and L2 (L3) cache-sizes and number of cachelines and pages needed - we likely fetch distinct cachelines for each different square or occupancy. On the other hand caches and pages become larger in future processors. And occupancy and squares of the lookups don't change that randomly inside a search that we can still expect a lot of L1-hits. Unfortunately changes in occupancy outside the blockers and therefor not affecting the attack-set will introduce some more cache misses.

Wishing Dreams

Since there are 1428/4900 distinct attack sets for the bishop/rook attacks, we can use 11(2048 > 1428)/13(8196 > 4900) index bits for all bishop/rook attack bitboards. The table size will be 16KB for the bishop attacks and 64KB for rook attacks. To make it possible, we must find a group of magics (one per square and dependent each other). All the magics in the group must hash its all relevant occupancies into the same 11/13 bit index without any collision with others (anyhow for each square, different occupancies can hash to the same attack sets).

U64 bishopAttacks[2048]; // 16KB
U64 rookAttacks[8196]; // 64KB
 
struct GMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares) and include sliding piece itself
   U64 magic; // magic 64-bit factor
};
 
GMagic mBishopTbl[64]; //1KB
GMagic mRookTbl[64]; //1KB
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-11;  //fixed shift
   return bishopAttacks[occ]; //no offset
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   occ &= mRookTbl[sq].mask;
   occ *= mRookTbl[sq].magic;
   occ >>= 64-13;
   return rookAttacks[occ];
}

But the idea seems like a wishing dream. Can we find ONE of the magic group of magics? Does it exist in theory? If not, can we use more bits to reach the condition? If yes, can we find a good magic group? A good magic group means that all the hash value <=n, so we can reduce the table size to n, until it reach to 1428/4900. Enough? If all hash values are grouped by square, can we think about using the Sharing Attacks method?

Implementations

Despite its huge table size, register usage and code size are important issues as well - and here Magic Bitboards are unbeatable. There are enough variations of space-time tradeoff and implementation details of that theme for all who like to play the optimization game. C-source code with various precompiler options is available from Pradu Kannan's site. MINIMIZE_MAGIC is about Plain versus Fancy ^[10] , while PERFECT_MAGIC_HASH enables an additional indirection via 16-bit indices. As always, with space-time tradeoffs - it depends on the individual cache- and memory footprint inside a particular chess program and the hardware architecture, which solution is preferable.

Fancy

Fancy Magic Bitboards is the main stream implementation as proposed by Pradu Kannan with individual table sizes for each square. It requires an individual shift, to leave that many index bits remaining as determined by the population of relevant occupancies. As mentioned, if one tries hard enough to maximize constructive collisions while looking for magics, one may half the size for several individual squares, see Best Magics so far.

U64 attack_table[...]; // ~840 KiB all rook and bishop attacks, less with constructive collisions optimization
 
struct SMagic {
   U64* ptr;  // pointer to attack_table for each particular square
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
   int shift; // shift right
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   occ      &= mBishopTbl[sq].mask;
   occ      *= mBishopTbl[sq].magic;
   occ     >>= mBishopTbl[sq].shift;
   return aptr[occ];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].mask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= mRookTbl[sq].shift;
   return aptr[occ];
}

Plain

Plain Magic Bitboards, Lasse Hansen's initial approach, takes much more memory for homogeneous two-dimensional attack arrays. 32 KiB per rook square, 4 KiB for each bishop square. It does not need a variable shift and therefor needs one processor register less to further reduce register pressure, despite shorter code. Unfortunately, so far, there are two rook corner squares (0 and 7), which prohibit dividing the rook table size by two.

U64 mBishopAttacks[64] [512]; // 256 K
U64 mRookAttacks  [64][4096]; // 2048K
 
struct SMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl  [64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-9;
   return mBishopAttacks[sq][occ];
}

Fixed shift Fancy

A fancy fixed shift variation was introduced by Onno Garms, looking for magics producing factors with appropriate reduced value ranges. That is, leave 12 bit rook indices for all squares, but with upper bit(s) clear for all possible occupancies for all the squares with less than 12 relevant bits, so that it efficiently becomes a less 12 bit index. Onno believes that it is possible to find magic factors with that property for most of those squares, to come close to the fancy table size with the advantage of a fixed shift ^[11] . Even an "overlapping" of square arrays is feasible, if they contain accordant unused slot gaps on both ends. Volker Annuss came up with a fixed shift solution of only 800 KiB and below ^[12] ^[13], and more recently even innovated with Black Magic Bitboards.

U64 attack_table[...]; // > 800 KiB  - 1.x MiB  - depending on the effort on looking for magics
 
struct SMagic {
   U64* ptr;  // pointer to attack_table for each particular square
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].mask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= 64-12;
   return aptr[occ];
}

Black Magic Bitboards

Volker Annuss' most recent innovation and further improvement of his already dense 700 KiB fixed shift fancy reference implementation is called Black Magic Bitboards, introduced in CCC in August 2017 ^[14]. Instead of intersection with a mask to clear the not relevant occupancy bits, he used the union with the complement of mask to set all not relevant occupancy bits.

  and mask[d4]  vs.   or ~mask[d4]
. . . . . . . .     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
. 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

This trick, which basically adds a huge constant to the occupancy factor, enables to find Black Magics yielding in even smaller array sizes per square, determined by maximum and minimum index - the latter no longer zero for the empty occupancy! Unfortunately so far, the individual savings with denser square arrays don't completely advance to the size of the combined overlapping table, since overlapping became harder due to smaller gaps ^[15] . However, 692 KiB for the complete rook and bishop attack table is the new fixed shift reference. Black Magic Bitboards are now used in Volker's engine Arminius ^[16] ^[17]:

U64 attack_table[88507]; // 692 KiB for published black magics by Volker Annuss (new size 88316 aka 690 KiB) 
 
struct SBlackMagic {
   U64* ptr;  // pointer to attack_table for each particular square
   U64 notmask;  // to mask relevant squares of both lines (no outer squares)
   U64 blackmagic; // black magic 64-bit factor
};
 
SBlackMagic mBishopTbl[64];
SBlackMagic mRookTbl[64];
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      |= mRookTbl[sq].notmask;
   occ      *= mRookTbl[sq].blackmagic;
   occ     >>= 64-12;
   return aptr[occ];
}

Byte Lookup

Since there are only up to 144 different attack sets per square, Robert Houdart proposed to lookup bytes by square and hashed occupancy for a minimal perfect hashing with an additional indirection via an offset per square, which is successfully used in his engine Houdini ^[18] . Following sample code uses the Plain fixed shift method, while it may also applied for the dense Fancy one.

byte mBishopAttacks[64] [512]; // 32 K
byte mRookAttacks  [64][4096]; // 256 K
 
U64 mRookLookup[4900];  // 39 K
U64 mBishopLookup[1428];  // 11 K
 
struct SMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
   int offset;   // offset into lookup table
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl  [64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-9;
   return mBishopLookup[mBishopTbl[sq].offset + mBishopAttack[sq][occ]];
}

32-bit Magics

Optimizations are possible for 32-bit systems, as proposed by Grant Osborne ^[19] . Instead of letting the compiler split up a 64-bit multiply, two 32-bit multiplications can be manually implemented. Multiply the low bits of the magic with the low bits of the key and add it with the product of the high bits of the magic and the high bits of the key and use the upper bits of the sum to index the move database. For the bishops one may try only one 32-bit multiplication after xoring the masked high and low half.

struct {
  unsigned int rookMaskLo;
  unsigned int rookMaskHi;
  unsigned int rookMagicLo;
  unsigned int rookMagicHi;
  unsigned int rookShift;
  U64 *pRookAttacks;
} sm[64];
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   unsigned int lo = (int) occ;
   unsigned int hi = (int)(occ >> 32);
   lo &= sm[sq].rookMaskLo;
   hi &= sm[sq].rookMaskHi;
   lo *= sm[sq].rookMagicLo;
   hi *= sm[sq].rookMagicHi;
   lo  = (lo ^ hi) >> sm[sq].rookShift;
   return sm[sq].pRookAttacks[lo];
}

Sharing Attacks

The development has not finished. Lasse Hansen came up with another stunning idea ^[20] , to use a final intersection by attacks on an empty board, to share tables by two (rooks) or even four (bishops) squares. Bishop sharing is simple to understand, since there are light and dark colored bishops with disjoint attacks-sets, able to share the pre-calculated union of two square-attacks.

The trick is to share even equal colored bishops and rooks where both attack-sets are not disjoint - but all members of the intersection are always set, since they are direct neighbors of both sliders. This is how rooks and bishops may share union-attack-sets by two resp. four squares:

int rookSharing[64] = {
   0,  1,  2,  3,  4,  5,  6,  7,
   1,  0,  3,  2,  5,  4,  7,  6,
   8,  9, 10, 11, 12, 13, 14, 15,
   9,  8, 11, 10, 13, 12, 15, 14,
  16, 17, 18, 19, 20, 21, 22, 23,
  17, 16, 19, 18, 21, 20, 23, 22,
  24, 25, 26, 27, 28, 29, 30, 31,
  25, 24, 27, 26, 29, 28, 31, 30,
};
 
int bishopSharing[64] = {
   0,  2,  4,  4,  4,  4, 12, 14,
   0,  2,  5,  5,  5,  5, 12, 14,
   0,  2,  6,  6,  6,  6, 12, 14,
   0,  2,  7,  7,  7,  7, 12, 14,
   1,  3,  8,  8,  8,  8, 13, 15,
   1,  3,  9,  9,  9,  9, 13, 15,
   1,  3, 10, 10, 10, 10, 13, 15,
   1,  3, 11, 11, 11, 11, 13, 15,
};

On the cost of one additional and-instruction, post-masking has the potential to almost halve the rook tables - and even better for the already small bishop tables. Additionally, four union attack bitboards can be shared by eight rook- and six bishop-squares.

R 1 1 1 1 1 1 1    1 R 1 1 1 1 1 1    1 1 R 1 1 1 1 1    1 1 1 R 1 1 1 1
B R 1 1 1 1 1 1    R B 1 1 1 1 1 1    1 1 B R 1 1 1 1    1 1 R B 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 1 . 1 . .
1 1 . 1 1 . 1 .    1 1 . . 1 . . .    . . 1 1 . 1 1 .    1 . 1 1 . . 1 .
1 1 . . 1 B . .    1 1 . . . 1 . .    . . 1 1 . . 1 B    . . 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 . . . .

If the additional post-mask becomes member of a structure, it exceeds 32 byte in 64-bit mode. A structure of arrays may be preferable than an array of structures.

U64 attack_table[...]; // ~400K Byte for all rook and (shared) bishop attacks
 
struct SMagic {
   U64* ptr;      // pointer to attack_table for each particular square
   U64 magic;     // magic 64-bit factor
   U64 premask;   // to mask relevant squares of both lines (no outer squares)
   U64 postmask;  // attacks on the otherwise empty board
   int shift;     // shift right
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   occ      &= mBishopTbl[sq].premask;
   occ      *= mBishopTbl[sq].magic;
   occ     >>= mBishopTbl[sq].shift;
   return      mBishopTbl[sq].postmask & aptr[occ];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].premask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= mRookTbl[sq].shift;
   return      mRookTbl[sq].postmask & aptr[occ];
}

Incorporating the Shift

Another possible improvement was introduced by Grant Osborne ^[21] - to don't store the variable right shift inside an own array or structure element, but to use the almost redundant upper six bit of the magic factor instead - incorporating the shift into the magic number. While using a structure for pre-, postmask, magic and pointer, it's size is 4*8 = 32-byte or - if properly aligned - the half of one cache line. The additional effort for the right shift 58 to extract the variable shift is likely hidden by the latency of the independent multiplication, improving ipc.

U64 attack_table[...]; // ~400K Byte for all rook and (shared) bishop attacks
 
struct SMagic {
   U64* ptr;      // pointer to attack_table for each particular square
   U64 magic;     // magic 64-bit factor, including upper six bits as shift amount
   U64 premask;   // to mask relevant squares of both lines (no outer squares)
   U64 postmask;  // attacks on the otherwise empty board
}; // 32 Byte with 64-bit pointer!
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   int shift = mBishopTbl[sq].magic >> 58;
   occ      &= mBishopTbl[sq].premask;
   occ      *= mBishopTbl[sq].magic;
   return      mBishopTbl[sq].postmask & aptr[occ >> shift];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   int shift = mRookTbl[sq].magic >> 58;
   occ      &= mRookTbl[sq].premask;
   occ      *= mRookTbl[sq].magic;
   return      mRookTbl[sq].postmask & aptr[occ >> shift];
}

Incorporating Offset

A similar idea as in Incorporating the Shift in the domain fixed shift magics was proposed by Eugene Kotlov concerning the indirection to the stored attack array, using the 16 lower bits of the magic factor as offset ^[22].

Initalization

Looking for Magics

The main issue is to find 64 magic factors for each rook and bishop square, to ensure they are free of collisions.

Looking for Magics

Magic Records

You may try to find your own magics - to possibly contribute to the record table for most dense fancy or plain tables. So far, there were no magics found for the expensive rook squares a1 and h1 (0, 7) with less than 12 bits, which would allow to half the plain table size. Is there any prove they don't exist - even with Black Magic?

Best Magics so far

Publications

Pradu Kannan (2007). Magic Move-Bitboard Generation in Computer Chess, as pdf
Fritz Reul (2009). New Architectures in Computer Chess, Ph.D. Thesis, Chapter 3, Magic Hash Functions for Bitboards, pdf
Maurizio Monge (2011). On perfect hashing of numbers with sparse digit representation via multiplication by a constant. Discrete Applied Mathematics, Vol. 159, No. 11

Forum Posts

2006

Fast(er) bitboard move generator by Lasse Hansen, Winboard Forum, June 14, 2006
List of magics for bitboard move generation by Pradu Kannan, Winboard Forum, August 23, 2006
Fastest Magic Move Bitboard Generator ready to use by Pradu Kannan, Winboard Forum, August 25, 2006
A Faster Magic Move Bitboard Generator? by Grant Osborne, Winboard Forum, December 15, 2006

2007

SEE with magic bitboards by Pradu Kannan, Winboard Forum, January 24, 2007 » Static Exchange Evaluation
Magic bitboards, Java by Sargon, CCC, August 19, 2007 » Java
BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Brian Richardson, CCC, August 24, 2007 ^[23]
Magic and precomputation by Onno Garms, Winboard Forum, September 23, 2007

2008

Magic Move Generation by Colin, CCC, February 18, 2008
How to reduce the "bits" used in a magic number by Charlie Brune, CCC, May 24, 2008
magic move - bitboard orientation by Frank Phillips, CCC, June 01, 2008
Incorporating the shift into the magic number by Grant Osborne, CCC, June 18, 2008

2009

Magics revisited by Richard Pijl, CCC, January 04, 2009
Magic with fixed shift by Onno Garms, Winboard Forum, March 18, 2009
Paradigm shifts by Gian-Carlo Pascutto, CCC, November 14, 2009
32-bit Magic experiments by Andrew Fan, Winboard Forum, December 03, 2009 » Kindergarten Bitboards

2010 ...

Plain and fancy magic on modern hardware by Robert Purves, CCC, August 22, 2010
Fixed shift magics with 800KB lookup table by Volker Annuss, Winboard Forum, September, 05, 2010
Build magics on the fly by Marco Costalba, CCC, June 07, 2011
Magic Multiplier Fundamentals by Cheney Nattress, CCC, January 03, 2013
Occupancy Variations by CDaley11, OpenChess Forum, January 25, 2013
Magic bitboards: Cache issues and state of the art? by Samuel Siltanen, CCC, March 22, 2013
Understanding Magic Bitboards by Jaco van Niekerk, Winboard Forum, April 03, 2013

2015 ...

question about magic keys generation time by Fermin Serrano, CCC, March 19, 2015 » Looking for Magics
Fancy magic bitboards question by Eric VanderHelm, CCC, September 22, 2015
M42 - A C++ library for Bitboard attack mask generation by Syed Fahad, CCC, April 30, 2016 ^[24]
understanding fixed shift fancy magic bitboard generation by Kalyankumar Ramaseshan, CCC, May 05, 2016
Re: understanding fixed shift fancy magic bitboard generation by Volker Annuss, CCC, May 06, 2016
Why should magic bitboards be sparse? by Alessandro Power, CCC, December 21, 2016
Looking for dense magics by Lucas Braesch, CCC, July 11, 2017
Black magic bitboards by Volker Annuss, CCC, August 03, 2017 » Black Magic Bitboards
Disproving the existence of some magics by Niklas Fiekas, CCC, September 16, 2017 » Looking for Magics
magic number comprising offset by Eugene Kotlov, CCC, February 07, 2018
No bishop magics with fixed shift 8 by Niklas Fiekas, CCC, April 09, 2018 » Looking for Magics

External Links

Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of Pradu Kannan's magic Move Generator
Rival Chess Engine - Magic Bitboards by Russell Newman and Chris Moreton » Rival
Chess Programming | Generating Magic Multipliers by Steve Maughan » Looking for Magics
chess - Sliding move generation using magic bitboard - Stack Overflow, June 4, 2013
M42 by Syed Fahad ^[25]
GitHub - goutham/magic-bits: Magic-bitboards for Chess by Goutham Bhat

Other Magic Stuff

Magic from Wikipedia
Magic (illusion) from Wikipedia
Magic (paranormal) from Wikipedia
Magic (cryptography) from Wikipedia
Magic number from Wikipedia
Magic constant from Wikipedia
Magic square from Wikipedia
Magic hypercube from Wikipedia
Five Senses - Magic Constant, Christmas Jazz Festival, Tallinn, December 10, 2011, YouTube Video
line-up: Nguyên Lê, Claudio Puntin, Steffen Schorn, Kristjan Randalu, Bodek Janke
Youn Sun Nah - Momento Magico (2013), YouTube Video
Youn Sun Nah, Ulf Wakenius, Lars Danielsson, Vincent Peirani

References

^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Robert Hyatt, CCC, August 25, 2007
^ Arasan Blog - Aug 26, 2008 by Jon Dart
^ Major Works from Samuel Bak - represented by Pucker Gallery since 1969
^ rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
^ Fast(er) bitboard move generator by Lasse Hansen, Winboard Forum, June 14, 2006, Initial idea
^ Pradu Kannan (2007). Magic Move-Bitboard Generation in Computer Chess, as pdf
^ List of magics for bitboard move generation by Pradu Kannan, Winboard Forum, August 23, 2006
^ Plain and fancy magic on modern hardware by Robert Purves, CCC, August 22, 2010
^ Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of Pradu Kannan's magic Move Generator, PERFECT_MAGIC_HASH
^ Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of Pradu Kannan's magic Move Generator, MINIMIZE_MAGIC
^ Magic with fixed shift by Onno Garms, Winboard Forum, March 18, 2009
^ Fixed shift magics with 800KB lookup table by Volker Annuss, Winboard Forum, September, 05, 2010
^ Re: understanding fixed shift fancy magic bitboard generation by Volker Annuss, CCC, May 06, 2016
^ Black magic bitboards by Volker Annuss, CCC, August 03, 2017
^ Re: Black magic bitboards by Volker Annuss, CCC, August 04, 2017
^ Re: Black magic bitboards by Volker Annuss, CCC, August 04, 2017
^ source code according to the fixed shift fancy sample - array size from Volker's posting, also containing black magics and arrayoffsets, see Black magic bitboards by Volker Annuss, CCC, August 03, 2017
^ Re: Plain and fancy magic on modern hardware by Robert Houdart, CCC, August 26, 2010
^ A Faster Magic Move Bitboard Generator? by Grant Osborne, Winboard Forum, December 15, 2006
^ Lasse Hansen's postmask trick, Winboard Forum, May 09, 2008
^ Incorporating the shift into the magic number by Grant Osborne, CCC, June 18, 2008
^ magic number comprising offset by Eugene Kotlov, CCC, February 07, 2018
^ Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed by Brian Richardson, CCC, April 24, 2000
^ M42 by Syed Fahad
^ M42 - A C++ library for Bitboard attack mask generation by Syed Fahad, CCC, April 30, 2016

What links here?

Page	Date Edited
Abbess	Jun 10, 2017
Abulafia	Oct 4, 2017
Alberto Sanjuan	Nov 3, 2014
AMD	Mar 9, 2018
Andreas Guettinger	Aug 14, 2013
Andrew Fan	Jul 30, 2017
Andscacs	Jan 16, 2018
Arasan	Apr 8, 2018
Arminius	Aug 5, 2017
Array	Dec 1, 2016
Atlas (ESP)	Jan 28, 2018
Backtracking	Dec 16, 2017
Barbarossa	Dec 20, 2016
BBChess (SI)	Jan 12, 2015
Best Magics so far	Apr 13, 2018
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
BMI2	Mar 6, 2018
Bobcat	Jun 27, 2017
Brutus NL	Aug 22, 2016
Buzz	Jun 22, 2016
Carballo	Oct 2, 2016
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
chess22k	Apr 23, 2018
chess4j	Jan 1, 2018
Chiron	Sep 24, 2017
Clarabit	Nov 3, 2011
Congruent Modulo Bitboards	Jun 26, 2013
Counter	Nov 13, 2017
Crafty	Jan 28, 2018
CuckooChess	Jan 17, 2017
Defenchess	Mar 18, 2018
Demolito	Mar 1, 2018
DiscoCheck	Jun 23, 2017
Djinn	Feb 8, 2016
Don Dailey	Dec 7, 2016
Donna	Aug 17, 2017
Edsel Apostol	Nov 2, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Eric Marathée	Dec 27, 2014
Ethereal	Mar 20, 2018
Exacto	Oct 3, 2015
Fire	Oct 12, 2017
Firefly	Oct 23, 2017
Fridolin	Jun 27, 2017
Galjoen	Mar 19, 2018
Garbochess	Sep 23, 2017
General Setwise Operations	Feb 25, 2018
Gerd Isenberg	Apr 4, 2016
Gibbon	Dec 23, 2014
Ginkgo	Jul 13, 2016
Giraffe	Jan 8, 2018
Glaurung	Mar 14, 2017
Godot	Apr 28, 2015
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Grant Osborne	Dec 2, 2011
Greko	Feb 27, 2018
GullChess	Jun 27, 2017
Hakkapeliitta	Apr 26, 2016
Hash Table	Jan 1, 2018
Hashing Dictionaries	Mar 1, 2014
Hedgehog	Feb 18, 2018
Hermann	Dec 7, 2017
Hiding the Implementation	Feb 3, 2011
Home	Jul 2, 2018
Houdini	Apr 14, 2018
iCE	Jan 4, 2016
Ifrit	Feb 7, 2016
Java	Feb 25, 2018
JFresh	Mar 2, 2016
Kholin	Jan 3, 2018
Kindergarten Bitboards	Aug 1, 2017
Laser	Dec 27, 2017
Lasse Hansen	Sep 1, 2015
Looking for Magics	Apr 13, 2018
Loop (Program)	Mar 14, 2017
Magic Bitboards	Apr 13, 2018
Marco Costalba	Feb 28, 2018
Mark Levene	Jun 2, 2015
Marvin	Feb 10, 2018
Maurizio Monge	Nov 27, 2015
Maverick	Jan 7, 2016
MinkoChess	Sep 5, 2013
Move Generation	Jan 29, 2018
Murka	Nov 11, 2016
Napoleon	Jun 25, 2017
Nemorino	Dec 21, 2017
NoraGrace	Nov 23, 2014
Occupancy	Sep 19, 2016
Octochess	Aug 15, 2017
Onno	Jul 19, 2013
Onno Garms	Jul 19, 2013
Orion	Oct 15, 2017
Paladin	Jan 29, 2017
Pawn Hash Table	Feb 1, 2018
Pawny	Jun 17, 2015
Pedone	Jan 16, 2018
Pradu Kannan	Aug 3, 2015
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
RedQueen	Nov 13, 2017
Rhetoric	Nov 15, 2017
Rival	Jul 30, 2017
Robert Houdart	Dec 8, 2017
Robert Hyatt	Dec 25, 2017
Robert Pope	Jun 10, 2017
Robocide	May 11, 2016
Rodent	Jan 11, 2018
Rodin	Feb 7, 2016
RuyDos	Feb 17, 2018
Rybka	Mar 27, 2017
Schooner	Feb 2, 2018
Scorpio	Mar 28, 2018
Searcher	Sep 26, 2016
SEE - The Swap Algorithm	Jun 5, 2017
Senpai	Nov 10, 2017
Shield	May 17, 2017
Sliding Piece Attacks	May 27, 2016
Sloppy	Sep 17, 2016
SmarThink	Feb 2, 2018
SnailChess	Nov 26, 2014
Space-Time Tradeoff	Jun 17, 2015
Static Exchange Evaluation	Dec 14, 2017
Stockfish	Apr 7, 2018
Syed Fahad	Jan 1, 2017
Takuya Obata	Jan 7, 2017
Texel	Oct 9, 2017
Tim Kosse	May 23, 2013
Tinker	Aug 29, 2015
Titboards	Feb 20, 2013
Tornado	Dec 14, 2017
Traversing Subsets of a Set	Oct 14, 2016
Trevor Fenner	Jun 2, 2015
Trial and Error	Feb 11, 2018
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Vadim Demichev	Jul 26, 2013
Vajolet	Jan 25, 2018
Volker Annuss	Aug 3, 2017
Wing	Oct 26, 2017
Winglet	Apr 26, 2015
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Zevra	Mar 12, 2018
Ziggurat	Oct 9, 2017
Zurichess	Mar 12, 2018

Up one Level

Obstruction Difference

GerdIsenberg — Fri, 27 May 2016 12:50:52 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Obstruction Difference

		Obstruction Difference is another subtraction approach, proposed by Michael Hoffmann ^[1]. The idea is to get disjoint positive and negative ray masks of the occupancy, and to subtract the most significant one bit of the negative ray from the doubled least siginificat one bit (LS1B) of the positive ray. The difference is finally intersected with the linemask, excluding the sliding piece itself from the attack set.
Man Ray, Obstruction, 1947 ^[2]

Empty Sets

If there is no obstruction inside the positive ray, we simply subtract from zero, aka borrow from the hidden 2^64 bit, same if doubling results in an empty set. If there is no obstruction inside the negative ray, we need at least to subtract one. With neither blocker available, the difference is the universal set -1 (~0), and we end up with the linemask, excluding the sliding piece, which are all attacks on the otherwise empty board. Therefor, to subtract at least '1', oring '1' is required if the negative ray occupancy is empty. Since setting the least significant bit does not affect any MS1B extraction, it can be done unconditionally on the negative ray.

Isolation

While isolation of the LS1B is the intersection of a bitboard with its two's complement, the MS1B is not that simple to extract, and requires a fast 64-bit BitScanReverse, f.i. x86-64 bsr with throughput in the one cycle range, as with Intel's Core 2 or Nehalem architecture, or Leading Zero Count, f.i. x86-64 lzcnt on AMD K10 or Intel Nehalem CPUs.

C Code

The routine works for all lines, ranks, files, diagonals and anti-diagonals by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter, or in C even passing a pointer to a structure with three (or multiples for several lines in parallel) bitboards per square and line, upper- and lower rays and the union of both.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

/*
 * @author Michael Hoffmann, Gerd Isenberg
 * @param  U64 occ occupancy of the board
 * @param  SMasks* a mask structure by square and line
 * @return line attacks from that square
 */
U64 lineAttacks(U64 occ, const SMasks *pMask) {
   U64 lower, upper, mMS1B, ls1b, odiff;
   lower = pMask->lower & occ;
   upper = pMask->upper & occ;
   mMS1B = -C64(1) << bsr64(lower | 1); // ms1b of lower (at least bit zero)
   ls1b  = upper & -upper;
   odiff = 2 * ls1b + mMS1B; // x86 lea option due to add -ms1b
   return pMask->lineEx & odiff; // (pMask->lower | pMask->upper) & odiff;
}

To use it that way:

struct SMasks
{
   U64 lower;
   U64 upper;
   U64 lineEx; // lower | upper
} masks[64][4]; // 6 (4) KByte, needs initialization
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 0) | lineAttacks(occ, masks[sq] + 1);
}
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 2) | lineAttacks(occ, masks[sq] + 3);
}

Since with two's complement i << x == - (-i << x), 2*high-low is done by add for the option to use x86 lea-instruction. The routine looks competitive for CPUs with fast bsr or lzcnt but has problems on processors with slow bitScan or 32-bit processors. Register usage is moderate and should suffice all x88-64 scratch registers for two lines, even for Visual C++.

Java

Java programmers may rely on Long.numberOfLeadingZeros, where the 64-bit JVM may use appropriate machine instructions.

/*
 * @author Michael Hoffmann, Gerd Isenberg
 * @param  long occ occupancy of the board
 * @param  int sq  0..63
 * @param  int line  0..3 for rank, file, dia, antidia
 * @return line attacks from that square
 */
long lineAttacks(long occ, int sq, int line) {
   long lower = longMasks[sq][line][0] & occ;
   long upper = longMasks[sq][line][1] & occ;
   long mMs1b = 0x8000000000000000 >> Long.numberOfLeadingZeros (lower | 1);
   long ls1b  = upper & -upper;
   long odiff = 2*ls1b + mMs1b;
   return longMasks[sq][line][2] & odiff;
}

One may also use unsigned shift right, to subtract the MS1B.

   long ms1b  = 0x8000000000000000 >>> Long.numberOfLeadingZeros (lower | 1);
   long ls1b  = upper & -upper;
   long odiff = 2*ls1b - ms1b;

How it works

Following bitboard diagrams demonstrate how it works with Little-Endian Rank-File Mapping, file attacks rook on d4 (27):

occupancy              fileMaskEx(d4)           occupancy d-file
 . . . 1 . 1 . .       . . . 1 . . . .          . . . 1 . . . .
 1 . 1 . . 1 1 .       . . . 1 . . . .          . . . . . . . .
 . 1 . 1 . . . 1       . . . 1 . . . .          . . . 1 . . . .
 . . . . . 1 . .       . . . 1 . . . .          . . . . . . . .
 . 1 . 1 . . . .   &   . . . . . . . .    =     . . . R . . . .
 . . . . . . 1 .       . . . 1 . . . .          . . . . . . . .
 1 1 . 1 . 1 . 1       . . . 1 . . . .          . . . 1 . . . .
 . . . 1 1 . 1 .       . . . 1 . . . .          . . . 1 . . . .
______________________________________
 
occupancy upper        occupancy lower
 . . . 1 . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . 1 . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . 1 . . . .
 . . . . . . . .       . . . 1 . . . .
                   |
LS1B upper         v   lower | 1
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . 1 . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . 1 . . . .
 . . . . . . . .       1 . . 1 . . . .
______________________________________
 
2* LS1B upper      -   MS1B (lower | 1)   =    2*LS1Bhigh-MS1Blow
 . . . . . . . .       . . . . . . . .         . . . . . . . .
 . . . . . . . .       . . . . . . . .         . . . . . . . .
 . . . . 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 1 1 1
 . . . . . . . .       . . . . . . . .         . . . . . . . .
 
 
2*LS1Bhigh-MS1Blow     fileMaskEx         =    fileAttacks
 . . . . . . . .       . . . 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 1 1       . . . 1 . . . .         . . . 1 . . . .
 . . . 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . .
 . . . . . . . .       . . . 1 . . . .         . . . . . . . .

References

^ DIRECT BITBOARD MOVEGENERATION by Michael Hoffmann, CCC, July 23, 2009
^ IMAGINE - The Israel Museum's searchable collections database

What links here?

Page	Date Edited
Classical Approach	Jan 28, 2018
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Michael Hoffmann	Aug 9, 2015
Nemo	Sep 24, 2016
Obstruction Difference	May 27, 2016
Occupancy	Sep 19, 2016
SBAMG	Dec 4, 2016
Sliding Piece Attacks	May 27, 2016
Subtracting a Rook from a Blocking Piece	Dec 2, 2016

Up one Level

On an empty Board

GerdIsenberg — Tue, 18 Mar 2014 21:05:25 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * On an empty Board

Single sliding piece attacks on the otherwise empty board or their disjoint subsets on lines or rays are that simple than none sliding pieces. We simply use pre-calculated tables for each piece-type, line or ray, indexed by square-index. To initialize those tables, one may use a fill approach with single populated from-sets, if availably anyway since used elsewhere. While the proposed line-routines here are quite small and cheap, incremental update during an initialization loop has some merits.

The various ray-,line- and piece sets are foundation of further attack calculation considering blocking pieces, for instance to mask the occupancy of relevant rays. Of course the piece attacks are union-sets of the disjoint line attacks, while the line attacks are unions of the disjoint ray attacks.

Ray Attacks

  northwest    north   northeast
  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa
  southwest    south   southeast

Rays by Line

Ray-Attacks may be conducted from Line-Attacks by intersection with "positive" and "negative" squares:

 positiveRay[sq] = lineAttacks[sq] & (0 - 2*singleBit[sq]);
 negativeRay[sq] = lineAttacks[sq] & (singleBit[sq] - 1);

or with shifts instead of lookups

 positiveRay[sq] = lineAttacks[sq] & (C64(-2) << sq);
 negativeRay[sq] = lineAttacks[sq] & ((C64(1) << sq) - 1);

Positive Rays

Remember Square Mapping Considerations.

By Lookup

East (+1)           Nort (+8)            NoEa (+9)           NoWe (+7)
. . . . . . . .     . . . 1 . . . .      . . . . . . . 1     . . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . . 1 .     1 . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . 1 . .     . 1 . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . 1 . . .     . . 1 . . . . .
. . . R 1 1 1 1     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .

Initialization

North attacks are simple to initialize inside a loop, starting from a1, shifting left:

U64 nort = C64(0x0101010101010100);
for (int sq=0; sq < 64; sq++, nort <<= 1)
   rayAttacks[sq][Nort] = nort;

Similar, but tad trickier for ranks and diagonals, due to the wraps. For instance the north-east direction:

U64 noea = C64(0x8040201008040200);
for (int f=0; f < 8; f++, noea = eastOne(noea) {
   U64 ne = noea;
   for (int r8 = 0; r8 < 8*8; r8 += 8, ne <<= 8)
      rayAttacks[r8+f][NoEa] = ne;
}

By Calculation

Orthogonal positive rays are quite cheap to calculate on the fly. For diagonal rays split the lines as mentioned.

U64 eastMaskEx(int sq) {
   const U64 one = 1;
   return 2*( (one << (sq|7)) - (one << sq) );
}
 
U64 nortMaskEx(int sq) {
   return C64(0x0101010101010100) << sq;
}

Negative Rays

Remember Square Mapping Considerations.

By Lookup

West (-1)           Sout (-8)            SoWe (-9)           SoEa (-7)
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
1 1 1 R . . . .     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . 1 . . . .      . . 1 . . . . .     . . . . 1 . . .
. . . . . . . .     . . . 1 . . . .      . 1 . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . 1 . . . .      1 . . . . . . .     . . . . . . 1 .

Initialization

South attacks are simple to initialize inside a loop, starting from h8, shifting right:

U64 sout = C64(0x0080808080808080);
for (int sq=63; sq >= 0; sq--, sout >>= 1)
   rayAttacks[sq][Sout] = sout;

Similar, but tad trickier for ranks and diagonals, due to the wraps.

By Calculation

Orthogonal negative rays are quite cheap to calculate on the fly. For diagonal rays split the lines as mentioned.

U64 westMaskEx(int sq) {
   const U64 one = 1;
   return (one << sq) - (one << (sq&56));
}
 
U64 soutMaskEx(int sq) {
   return C64(0x0080808080808080) >> (sq ^ 63);
}

Line Attacks

 RankAttacks[sq]         = EastAttacks[sq] | WestAttacks[sq];
 FileAttacks[sq]         = NortAttacks[sq] | SoutAttacks[sq];
 DiagonalAttacks[sq]     = NoEaAttacks[sq] | SoWeAttacks[sq];
 AntiDiagonalAttacks[sq] = NoWeAttacks[sq] | SoEaAttacks[sq];

By Lookup

Rank                File                 Diagonal            Anti-Diagonal
. . . . . . . .     . . . 1 . . . .      . . . . . . . 1     . . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . . 1 .     1 . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . 1 . .     . 1 . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . 1 . . .     . . 1 . . . . .
1 1 1 R 1 1 1 1     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . 1 . . . .      . . 1 . . . . .     . . . . 1 . . .
. . . . . . . .     . . . 1 . . . .      . 1 . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . 1 . . . .      1 . . . . . . .     . . . . . . 1 .

By Calculation

To calculate them on the fly, including...

U64 rankMask(int sq) {return  C64(0xff) << (sq & 56);}
 
U64 fileMask(int sq) {return C64(0x0101010101010101) << (sq & 7);}
 
U64 diagonalMask(int sq) {
   const U64 maindia = C64(0x8040201008040201);
   int diag =8*(sq & 7) - (sq & 56);
   int nort = -diag & ( diag >> 31);
   int sout =  diag & (-diag >> 31);
   return (maindia >> sout) << nort;
}
 
U64 antiDiagMask(int sq) {
   const U64 maindia = C64(0x0102040810204080);
   int diag =56- 8*(sq&7) - (sq&56);
   int nort = -diag & ( diag >> 31);
   int sout =  diag & (-diag >> 31);
   return (maindia >> sout) << nort;
}

... or excluding the square bit:

U64 rankMaskEx    (int sq) {return (C64(1) << sq) ^ rankMask(sq);}
U64 fileMaskEx    (int sq) {return (C64(1) << sq) ^ fileMask(sq);}
U64 diagonalMaskEx(int sq) {return (C64(1) << sq) ^ diagonalMask(sq);}
U64 antiDiagMaskEx(int sq) {return (C64(1) << sq) ^ antiDiagMask(sq);}

Piece Attacks

RookAttacks[sq]   = RankAttacks[sq]     | FileAttacks[sq];
BishopAttacks[sq] = DiagonalAttacks[sq] | AntiDiagonalAttacks[sq];
QueenAttacks[sq]  = RookAttacks[sq] | BishopAttacks[sq];

By Lookup

                                   Queen
                               . . . 1 . . . 1
                               1 . . 1 . . 1 .
                               . 1 . 1 . 1 . .
               Rook            . . 1 1 1 . . .         Bishop
           . . . 1 . . . .     1 1 1 Q 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 R 1 1 1 1                         . . . B . . . .
           . . . 1 . . . .                         . . 1 . 1 . . .
           . . . 1 . . . .                         . 1 . . . 1 . .
           . . . 1 . . . .                         1 . . . . . 1 .

By Calculation

U64 rookMask    (int sq) {return rankMask(sq)     | fileMask(sq);}
U64 bishopMask  (int sq) {return diagonalMask(sq) | antiDiagMask(sq);}
 
 
U64 rookMaskEx  (int sq) {return rankMask(sq)     ^ fileMask(sq);}
U64 bishopMaskEx(int sq) {return diagonalMask(sq) ^ antiDiagMask(sq);}
 
U64 queenMask   (int sq) {return rookMask(sq)     | bishopMask(sq);}
U64 queenMaskEx (int sq) {return rookMask(sq)     ^ bishopMask(sq);}

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
AVX2	Aug 8, 2017
Backtracking	Dec 16, 2017
Bitfoot	Sep 8, 2015
Blockers and Beyond	Mar 21, 2014
Classical Approach	Jan 28, 2018
Direction	Oct 6, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Gerd Isenberg	Apr 4, 2016
Hyperbola Quintessence	Mar 25, 2017
Joker IT	Sep 16, 2017
Kindergarten Bitboards	Aug 1, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Magic Bitboards	Apr 13, 2018
Obstruction Difference	May 27, 2016
On an empty Board	Mar 18, 2014
Pieces versus Directions	Oct 6, 2016
Praetorian	Feb 21, 2015
Rays	Oct 20, 2016
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
SBAMG	Dec 4, 2016
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Squares	Feb 15, 2015
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Thor's Hammer	Nov 23, 2013
Tinker	Aug 29, 2015

Up one Level

Returning Bishop

GerdIsenberg — Sat, 16 Mar 2013 14:15:41 GMT

Home * Evaluation * of Pieces * Returning Bishop

The term returning bishop refers to a bishop that went back to its original square after allowing own king to castle in the same direction. The typical example would be something like that: 1.e4 c5 2.Nf3 Nc6 3.Bb5 d6 4.0-0 Bd7 5. c3 Nf6 6.Re1 a6 7.Bf1.

Simplistic piece-square evaluation would treat such a bishop as undeveloped. Yet it is a good defender and, more importantly, "developing" it would waste another tempo. For that reasons it might be beneficial to assign a bonus erasing the development penalty for such a bishop.

The idea has been proposed (or just reinvented?) by Pawel Koziol.

What links here?

Page	Date Edited
Chunking	Jun 12, 2017
Development	Jan 17, 2018
Evaluation of Pieces	Jan 8, 2018
Evaluation Patterns	Jun 24, 2013
Middlegame	Sep 6, 2016
Pattern Recognition	Sep 8, 2017
Returning Bishop	Mar 16, 2013

Up one Level

Rotated Indices

GerdIsenberg — Mon, 09 Oct 2017 08:04:39 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Rotated Indices

		Rotated indices, a deconcentrated version of rotated bitboards, proposed by Alessandro Damiani ^[1] as used in his engine Fortress. Instead of using rotated bitboards with packed 15 diagonals and 15 anti-diagonals each, Alessandro applies an array of 16 + 30 rotated indices for all 16 orthogonal and 30 diagonal lines on the board. Those indices are incrementally updated during make/unmake, which takes a tad more effort - but once updated, the rotated indices pay off, the more often they are used inside a node of the search. No further computation is required to look up attacks, pure indexed memory accesses. The possible disadvantage - rotated indices, similar or slightly worse than rotated bitboards, are not as versatile as techniques relying on one occupancy bitboard only - if it is about a temporary change of the occupancy on the fly for x-rays and pinned pieces etc..
Barbara Mittman, Yellow Cherries ^[2]

Forum Posts

Re: Rotated bitboards by Alessandro Damiani, rgcc, October 31, 1997
Re: Resources about rotated bitboards by Alessandro Damiani, CCC, January 16, 2004

References

^ Re: Rotated bitboards by Alessandro Damiani, rgcc, October 31, 1997
^ Still Lifes by Barbara Mittman

What links here?

Page	Date Edited
Alessandro Damiani	Oct 9, 2017
Fortress (Engine)	Oct 19, 2017
Gk	Oct 9, 2017
Rotated Bitboards	Mar 7, 2017
Rotated Indices	Oct 9, 2017
Sliding Piece Attacks	May 27, 2016

Up one Level

SBAMG

GerdIsenberg — Sun, 04 Dec 2016 09:16:26 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * SBAMG

SBAMG, (Subtraction based Attack Mask Generation)
a subtraction based approach proposed by Syed Fahad ^[1] which combines techniques used in Subtracting a Rook from a Blocking Piece aka o^(o-2r) and Obstruction Difference. The idea is to subtract three times the closest blocker in negative ray direction (most significant one bit of lower ray occupancy) from the line occupancy, to exclusive or that difference with the line occupancy again: o^(o-3cbn). Three times is necessary, since we need not only to subtract the next highest neigbouring square of the closest blocker for the borrow propagation, but the blocker square itself. The line occupancy excludes the sliding piece itself, and equivalently the final result is again restricted by the line-mask excluding the square of the attacker. Outer squares of the line occupancy, which don't affect resulting line attacks, are always set to avoid conditional code.

Sample

A two nibble sample calculating the rank aka byte attacks of a rook illustrates the technique:

                   binary     hex  dez
bit-index          7654 3210  
blockers and rook  .b.. r.bb
occ (without rook) 0100 0011  0x43  67
cbn                0000 0010  0x02   2 
occ-3cbn           0011 1101  0x3d  61
occ^(occ-3cbn)     0111 1110  0x7e 126
attacks (/rook)    0111 0110  0x76 118

C Code

The routine works for all lines, ranks, files, diagonals and anti-diagonals by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter. Signature and BitScanReverse (bsr64) similar to Obstruction Difference.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

/*
 * @author Syed Fahad, Gerd Isenberg
 * @param  U64 occ occupancy of the board
 * @param  SMasks* a mask structure by square and line
 * @return line attacks from that square
 */
U64 lineAttacks(U64 occ, const SMasks *pMask) {
   occ &= pMask->lineEx;
   occ |= pMask->outer;
   int bsq = bsr64(occ & pMask->lower);
   U64 cbnx3 = C64(3) << bsq; // or lookup
   occ = occ ^ (occ - cbnx3);
   return occ & pMask->lineEx;
}

To use it that way:

struct SMasks
{
   U64 lower;  // 1 for sq 0, otherwise (1 << sq) - 1
   U64 lineEx; // excluding (1 << sq)
   U64 outer;  // outer & 1 must be 1 to avoid calling bsr(0)
} masks[64][4]; // needs initialization
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 0) | lineAttacks(occ, masks[sq] + 1);
}
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 2) | lineAttacks(occ, masks[sq] + 3);
}

Forum Posts

Slider attack mask generation without table lookup by Syed Fahad, CCC, May 24, 2015
SBAMG - Competing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016 » Hyperbola Quintessence
Subtraction based Attack Mask Generation by Syed Fahad, CCC, November 16, 2016

References

^ SBAMG - Completing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016

What links here?

Page	Date Edited
Hyperbola Quintessence	Mar 25, 2017
Obstruction Difference	May 27, 2016
SBAMG	Dec 4, 2016
Sliding Piece Attacks	May 27, 2016
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Syed Fahad	Jan 1, 2017

Up one Level

Sherwin Bitboards

GerdIsenberg — Wed, 20 Mar 2013 12:47:36 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Sherwin Bitboards

The Sherwin bitboards were created by Michael Sherwin with some help from other people in CCC ^[1]. The idea is to generate the attacks of a sliding piece by collecting all occupied squares on its rays for each row. Then use a first lookup table to get an index into a second table that contains the attack bitboards. Most of the hard work is done in the initialization of the tables. Care must be taken with the right order and enumeration of the table indizes. The code below is taken from the chess engine Elephant and it uses the same big-endian file-mapping as the exploding bitboards.

Bishops

These are the relevant squares for a bishop on d4. We don't have to look at pieces at the border of the board to decide whether their squares can be attacked or defended.

 . . . . . . . -
 - . . . . . 1 .  giving 1 bit  or 2 different values from row 7
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 6
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 3
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .

We need an helper array and an initializing function for the rays. This mask covers the inner 6x6 board only.

Bitboard bishopBits[64];
void initBishopBits()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        bishopBits[sq] = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
            bishopBits[sq] |= C64(1) << i;
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
            bishopBits[sq] |= C64(1) << i;
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
            bishopBits[sq] |= C64(1) << i;
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
            bishopBits[sq] |= C64(1) << i;
        bishopBits[sq] &= C64(0x007e7e7e7e7e7e00);
    }
}

With the help of a first table we condense the scattered bits to a compact index number. For bits named a to i the value for Bd4 will be:

 . . . . . . . -
 - . . . . . i .  giving 1 bit  or 2 different values from row 7
 . g . . . h . .  giving 2 bits or 4 different values from row 6
 . . e . f . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . c . d . . .  giving 2 bits or 4 different values from row 3
 . a . . . b . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .
 
-> 0x0000000ihgfedcba as index. With 2^9 = 512 index values.

There are 4 squares with 9 bits like Bd4. Other squares need another amount of bits.

const byte squareBitsB[64] =
{
  6, 5, 5, 5, 5, 5, 5, 6,
  5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 5, 5, 5, 5, 5, 5, 6,
};

Here is how much values of the first table we need. That is also the size of the second table.

 4 squares with 9 bits for 512 indices are 2048 indices.
12 squares with 7 bits for 128 indices are 1536 indices.
44 squares with 5 bits for  32 indices are 1408 indices.
 4 squares with 6 bits for  64 indices are  256 indices.
                                     Total 5248 indices.

This is the layout of the first big table with index-bits for each square and all rows. The indices are in this order:

0000999999999 4 times 9 bit
0001999999999
0010999999999
0011999999999
0100007777777 12 times 7 bit
01....7777777
0110117777777
0111000666666 4 times 6 bit
0111001666666
0111010666666
0111011666666
0111100055555 44 times 5 bit
........55555
1010001155555

And here is the initializing function.

short int bishopRows[64][6][64];
void initBishopRows()
{
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsB[sq] != bits )
                continue;
            Bitboard bb = bishopBits[sq];
            bb >>= 9;
            int shift = 0;
            for ( int row = 0; row < 6; ++row )
            {
                int p = (bb >> (row * 8)) & 0x3f;
                for ( int pattern = 0; pattern < 64; ++pattern )
                {
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 6; ++i )
                    {
                        if ( p & (1 << i) )
                        {
                            index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
                            s++;
                            if ( pattern == 63 )
                                shift++;
                        }
                    }
                    bishopRows[sq][row][pattern] = baseIndex + index;
                }
            }
            baseIndex += (1 << bits);
        }
    }
}

A second table with 5248 entries can hold all bishop attack bitboards. This table must also be initialized.

Bitboard bishopAttackTable[5248];
void initBishopAttacks()
{
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsB[sq] != bits )
                continue;
            Bitboard bb = bishopBits[sq];
            for ( int index = 0; index < (1 << bits); ++ index )
            {
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                {
                    if ( bb.test_bit( rsq ) )
                    {
                        if ( i & 1 )
                            occ.set_bit( rsq );
                        i >>= 1;
                    }
                }
                Bitboard att = 0;
                int j;
                for ( j = sq + 9; j < 64 && (j & 7) != 0; j += 9 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq + 7; j < 64 && (j & 7) != 7; j += 7 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 9; j >= 0 && (j & 7) != 7; j -= 9 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 7; j >= 0 && (j & 7) != 0; j -= 7 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                bishopAttackTable[baseIndex + index] = att;
            }
            baseIndex += (1 << bits);
        }
    }
}

Ok, here comes the function to get the bishop attack bitboard for a square and occupied bitboard.

Bitboard bishopAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the X-rays
    occ  &= bishopBits[sq];
    occ >>= 9;
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    short int *bRows = &bishopRows[sq][0][0];
    int index = (bRows +   0)[(occ >>  0) & 0x3f]  // row 2
              | (bRows +  64)[(occ >>  8) & 0x3f]  // row 3
              | (bRows + 128)[(occ >> 16) & 0x3f]  // row 4
              | (bRows + 192)[(occ >> 24) & 0x3f]  // row 5
              | (bRows + 256)[(occ >> 32) & 0x3f]  // row 6
              | (bRows + 320)[(occ >> 40) & 0x3f]; // row 7
    return bishopAttackTable[index];
}

Perhaps you should look at this function first to understand the algorithm.

After the creation of the lookup tables which is only done once the often used bishopAttacks() function is rather easy and performant. And it is branchless.

There is a possible modification of this function that uses unions rather than >> and &. Some people believe that is faster. But it depends on big and little endianess.

#if BIG_ENDIAN() && !LITTLE_ENDIAN()
// Big end first means row 8 is first byte with my square encoding.
struct BBBytes
{
    unsigned char row8;
    unsigned char row7;
    unsigned char row6;
    unsigned char row5;
    unsigned char row4;
    unsigned char row3;
    unsigned char row2;
    unsigned char row1;
};
#elif LITTLE_ENDIAN() && !BIG_ENDIAN()
// Little end first means row 1 is first byte with my square encoding.
struct BBBytes
{
    unsigned char row1;
    unsigned char row2;
    unsigned char row3;
    unsigned char row4;
    unsigned char row5;
    unsigned char row6;
    unsigned char row7;
    unsigned char row8;
};
#else
    #error big little endian
#endif
 
union BBUnion
{
    Bits64   bb;    // typedef uint64 Bits64;
    BBBytes  bbb;
};
 
Bitboard bishopAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the X-rays
    occ  &= bishopBits[sq];
    occ >>= 1;
    BBUnion occu;
    occu.bb = occ;
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    short int *bRows = &bishopRows[sq][0][0];
    int index = (bRows +   0)[occu.bbb.row2]  // row 2
              | (bRows +  64)[occu.bbb.row3]  // row 3
              | (bRows + 128)[occu.bbb.row4]  // row 4
              | (bRows + 192)[occu.bbb.row5]  // row 5
              | (bRows + 256)[occu.bbb.row6]  // row 6
              | (bRows + 320)[occu.bbb.row7]; // row 7
    return bishopAttackTable[index];
}

Rooks

Rooks are mostly treated like the bishops. It starts with their rays.

Bitboard rookBits[64];
void initRookBits()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        rookBits[sq] = 0;
        int i;
        for ( i = sq - 1; i >= 0 && i % 8 != 7; --i )
            rookBits[sq] |= C64(1) << i;
        for ( i = sq - 8; i >= 0; i -= 8 )
            rookBits[sq] |= C64(1) << i;
        for ( i = sq + 1; i < 64 && i % 8 != 0; ++i )
            rookBits[sq] |= C64(1) << i;
        for ( i = sq + 8; i < 64; i += 8 )
            rookBits[sq] |= C64(1) << i;
        if ( (sq & 7) != 7 )
            rookBits[sq] &= C64(0x7f7f7f7f7f7f7f7f);
        if ( (sq & 7) != 0 )
            rookBits[sq] &= C64(0xfefefefefefefefe);
        if ( (sq / 8) != 7 )
            rookBits[sq] &= C64(0x00ffffffffffffff);
        if ( (sq / 8) != 0 )
            rookBits[sq] &= C64(0xffffffffffffff00);
    }
}

There are 36 squares with 10 bits like Rd4. Other squares need another amount of bits.

const byte squareBitsR[64] =
{
  12, 11, 11, 11, 11, 11, 11, 12,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  12, 11, 11, 11, 11, 11, 11, 12,
};

This is the layout of the first big table with index-bits for each square and all rows. The indices are in this order:

00000cccccccccccc 4 times 12 bit
00001cccccccccccc
00010cccccccccccc
00011cccccccccccc
001000bbbbbbbbbbb 24 times 11 bit
0.....bbbbbbbbbbb
100111bbbbbbbbbbb
1010000aaaaaaaaaa 36 times 10 bit
.......aaaaaaaaaa
1110011aaaaaaaaaa

For rooks we need a bigger second table. It has 102400 entries. This makes even the first table bigger because it can not use 2 byte short integer values. And the last dimension of the first table has to cover all 8 bits of a row. This is because rooks on file a or h have rays along the outside files.

Here is the initializing function.

int rookRows[64][8][256];
void initRookRows()
{
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsR[sq] != bits )
                continue;
            Bitboard bb = rookBits[sq];
            int shift = 0;
            for ( int row = 0; row < 8; ++row )
            {
                int p = (bb >> (row * 8)) & 0xff;
                for ( int pattern = 0; pattern < 256; ++pattern )
                {
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 8; ++i )
                    {
                        if ( p & (1 << i) )
                        {
                            index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
                            s++;
                            if ( pattern == 255 )
                                shift++;
                        }
                    }
                    rookRows[sq][row][pattern] = baseIndex + index;
                    //logf << "rookRows " << sq << " " << row << " " << pattern << " : ";
                    //logf << rookRows[sq][row][pattern] << endl;
                }
            }
            baseIndex += (1 << bits);
        }
    }
}

A second table with 102400 entries can hold all rook attack bitboards. This table must also be initialized.

Bitboard rookAttackTable[102400];
void initRookAttacks()
{
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsR[sq] != bits )
                continue;
            Bitboard bb = rookBits[sq];
            for ( int index = 0; index < (1 << bits); ++ index )
            {
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                {
                    if ( bb.test_bit( rsq ) )
                    {
                        if ( i & 1 )
                            occ.set_bit( rsq );
                        i >>= 1;
                    }
                }
                Bitboard att = 0;
                int j;
                for ( j = sq + 1; j < 64 && (j & 7) != 0; ++j )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq + 8; j < 64; j += 8 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 1; j >= 0 && (j & 7) != 7; --j )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 8; j >= 0; j -= 8 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                rookAttackTable[baseIndex + index] = att;
            }
            baseIndex += (1 << bits);
        }
    }
}

Ok, here comes the function to get the bishop attack bitboard for a square and occupied bitboard.

Bitboard rookAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the +-rays
    occ &= rookBits[sq];
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    int *rRows = &rookRows[sq][0][0];
    int index = (rRows +    0)[(occ >>  0) & 0xff]  // row 1
              | (rRows +  256)[(occ >>  8) & 0xff]  // row 2
              | (rRows +  512)[(occ >> 16) & 0xff]  // row 3
              | (rRows +  768)[(occ >> 24) & 0xff]  // row 4
              | (rRows + 1024)[(occ >> 32) & 0xff]  // row 5
              | (rRows + 1280)[(occ >> 40) & 0xff]  // row 6
              | (rRows + 1536)[(occ >> 48) & 0xff]  // row 7
              | (rRows + 1792)[(occ >> 56) & 0xff]; // row 8
    return rookAttackTable[index];
}

Bitboard rookAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the +-rays
    occ &= rookBits[sq];
    BBUnion occu;
    occu.bb = occ;
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    int *rRows = &rookRows[sq][0][0];
    int index = (rRows +    0)[occu.bbb.row1]  // row 1
              | (rRows +  256)[occu.bbb.row2]  // row 2
              | (rRows +  512)[occu.bbb.row3]  // row 3
              | (rRows +  768)[occu.bbb.row4]  // row 4
              | (rRows + 1024)[occu.bbb.row5]  // row 5
              | (rRows + 1280)[occu.bbb.row6]  // row 6
              | (rRows + 1536)[occu.bbb.row7]  // row 7
              | (rRows + 1792)[occu.bbb.row8]; // row 8
    return rookAttackTable[index];
}

Results

The results of the functions bishopAttacks() and rookAttacks() can be used in the same way as described in exploding bitboards.

References

^ New bitboard move generator by Michael Sherwin, Winboard Forum, September 14, 2006

What links here?

Page	Date Edited
Elephant	Sep 19, 2016
Harald Lüßen	Mar 20, 2013
Michael Sherwin	Dec 18, 2017
RomiChess	Jan 2, 2018
Sherwin Bitboards	Mar 20, 2013
Sliding Piece Attacks	May 27, 2016

Up one Level

Wikispaces : chessprogramming - items matching description

Bad bishop

Table of Contents

See also

Publications

Forum Posts

External Links

What links here?

Bishop

What links here?

Bishop Pair

Table of Contents

See also

Publications

Forum Posts

External Links

References

What links here?

Bishop versus knight

Table of Contents

Endgame Considerations

Winning Percentages

See also

Publications

References

What links here?

Bishops of Opposite Colors

Table of Contents

Scaling down

See also

Forum Posts

External Links

What links here?

Butterfly Boards

Table of Contents

Layout

Valid Entries

The Eponym

The Butterfly

Single Shape

Connected Shapes

C-Code

Analogy in Astronomy

See also

Publications

External links

Wikipedia

Musicvideo

References

What links here?

Color Weakness

Table of Contents

Examples

External Links

References

What links here?

Congruent Modulo Bitboards

Table of Contents

Modulo vs. Multiplication

Modulo

Congruence relation

Casting out 255

Reciprocal Multiplication

Multiplication

Fenner's and Levene's conclusion

Publications

Forum Posts

External Links

References

What links here?

Evaluation of Pieces

Table of Contents

Pawn

Knight

Bishop

Rook

Queen

King

See also

Forum Posts