Wikispaces : chessprogramming - items matching description

All Shortest Paths

GerdIsenberg — Tue, 21 Jan 2014 21:59:47 GMT

Home * Board Representation * Bitboards * King Pattern * All shortest Paths

The All shortest Paths algorithm was introduced by Steffan Westcott ^[1]:

The Algorithm

The following routine determines if a path of set bits in 'path' 8-way connect (ie. king move) any set bit in sq1 with any set bit in sq2 (this is the same as Squares Are Connected). Also, it will return an array of bitboards showing all possible shortest paths - This is probably best explained by showing an example:

Setting sq1 to contain e4, sq2 to have both a1 and h8, and mask to be ~0 yields this all shortest paths array of bitboards:

. . . . . . . .   . . . . . . . .     . . . . . . . .   . . . . . . . .   . . . . . . . 1
. . . . . . . .   . . . . . . . .     . . . . . . . .   . . . . . . 1 1   . . . . . . . .
. . . . . . . .   . . . . . . . .     . . . . . 1 1 .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . 1 1 . .     . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . 1 . . .   . . . 1 . . . .     . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . 1 . . . .     . . 1 . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .     . . 1 . . . . .   . 1 . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .     . . . . . . . .   . 1 . . . . . .   1 . . . . . . .

The king needs 4 moves to reach either a1 or h8, so both possibilities are shown in the last bitboard. Also, the king has a choice of squares along the way, meaning there are many shortest paths.

/////////////////////////////////////////////////////////////////////////
//
// Returns length of shortest path of set bits present in 'path' that
// 8-way connect any set bit in sq1 to any set bit of sq2. 0 is returned
// if no such path exists. Also fills a sequence of bitboards asp[length]
// that describes all such shortest paths.
 
int allShortestPaths(U64 sq1, U64 sq2, U64 path, U64* asp)
{
    // Do an 8-way flood fill with sq1, masking off bits not in path and
    // storing the fill frontier at every step. Stop when fill reaches
    // any set bit in sq2 or quit if fill cannot progress any further.
    // Then do 8-way flood fill from reached bits in sq2, ANDing the
    // frontiers with those from the first fill in reverse order.
 
    if (!(sq1 &= path) || !(sq2 &= path)) return 0;
                        // Drop bits not in path
                        // Early exit if sq1 or sq2 not on any path
    int i = 1;
    asp[0] = sq1;
 
    while(1)  // Fill from all set bits in sq1, to any set bit in sq2
    {
        if (sq1 & sq2) break;                     // Found good path
        U64 temp = sq1;
        sq1 |= eastOne(sq1) | westOne(sq1);       // Set all 8 neighbours
        sq1 |= soutOne(sq1) | nortOne(sq1);
        sq1 &= path;                              // Drop bits not in path
        if (sq1 == temp) return 0;                // Fill has stopped
        asp[i++] = sq1 & ~temp;                   // Store fill frontier
    }
 
    int length = i;                               // Remember path length
    asp[--i] = (sq2 &= sq1);                      // Drop unreached bits
 
    while(i)  // Fill from reached bits in sq2
    {
        U64 temp = sq2;
        sq2 |= eastOne(sq2) | westOne(sq2);       // Set all 8 neighbours
        sq2 |= soutOne(sq2) | nortOne(sq2);
        sq2 &= path;                              // Drop bits not in path
        asp[--i] &= sq2 & ~temp;                  // Intersect frontiers
    }
    return length;
}

As a reminder - one step only.

So far we've just mentioned 8-way flood filling for king/queen moves, and diagonal or rank/file 4-way filling for bishop or rook moves. A simple variant exists for knight moves too, which is handy for calculating knight mobility, and helping solve "Knight's Tour" type puzzles. Its even useful for pawns too, for quick determination of outposts outside all enemy pawn "attack cones", for example.

A fill iteration need not just go one square in each direction. With appropriate bitboard manipulation, it may extend the full ray of a sliding piece, for example. Examining the filled bitboard for 1 or 2 iterations will enable design of piece mobility terms with some simulated ply.

Optimization

Edmund Moshammer proposed following optimization with an inlined king fill routine ^[2]:

// Set all up to eight neighbours
// inline
U64 fillKing(U64 b) {
    b |= eastOne(b) | westOne(b);   
    b |= soutOne(b) | nortOne(b);
    return b;
}
 
int allShortestPaths(U64 sq1, U64 sq2, U64 path, U64* asp) {
    int i, length;
    asp[0] = sq1;
    for (i=0; !(asp[i] & sq2); i++)
        if (!(asp[i+1] = fillKing(asp[i]) & path &~asp[i])) return 0;
    length = i;
    asp[i] = sq2;
    for (; i; i--) 
       asp[i-1] &= fillKing(asp[i]) & path;
    return length;
}

External Links

Pathfinding from Wikipedia
Remember Shakti ^[3], Finding the way, part 1, YouTube Video
Zakir Hussain, U. Srinivas, John McLaughlin, V. Selvaganesh

References

^ All shortest paths & other flood-fill based algorithms by Steffan Westcott, CCC, September 13, 2002
^ Discussion about this page
^ Shakti from Wikipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
All Shortest Paths	Jan 21, 2014
Edmund Moshammer	Sep 23, 2017
Fill Algorithms	Nov 6, 2013
Helmut Horacek	Oct 31, 2016
King Pattern	Nov 15, 2013
Mobility	Jan 17, 2018
PawnKing	Sep 5, 2014
Steffan Westcott	Jan 21, 2014
Trajectory	Jan 3, 2015

Up one Level

Attack and Defend Maps

GerdIsenberg — Sat, 05 Nov 2016 09:18:44 GMT

Home * Programming * Data * Attack and Defend Maps

		Attack and Defend Maps, also called Attack Tables, refer to data-structures, most often arrays, containing attack or defend information for every pawn or piece and/or the transposed information for each square, which pieces control, that is either attack or defend it. These Maps are useful for evaluation purposes such as safe mobility, SEE and of course move generation. While the piece centric attack information, a set of attacked squares per piece, is often encoded as bitboard, there are more alternatives for storing the square centric information, about attacking pieces.
Samuel Bak - Sheltering Myths, 1998 ^[1]

Maintaining Attacks

Incremental Update

The piece centric and/or square centric information is often initialized at the root and updated incrementally during the search while making and unmaking moves. The idea is that a move has often only a local influence on the attack tables, and that it is usually cheaper to change only those squares which changed from- or to-attacks, rather than all squares from scratch. This is especially true during the opening or early middlegame phase, but does become more expensive in the late middlegame or endings with sliding pieces, especially queens.

On the Fly

Programmers like Joël Rivat ^[2], Robert Hyatt ^[3], Ed Schröder and Gerd Isenberg avoid or have abandoned incrementally updated attack tables and rely on the paradigm to process information if needed. A lot of nodes don't need the attack information at all, or only a small part of it. With all the hash tables, incremental update tends to do some unnecessary work, considering the update costs in "worst case" positions, f.i. queen endings, where one move change the attack information of many squares.

On the other hand, if attack tables are available, one should utilize the information as much as possible for a smarter search and evaluation to gain exponentially. Anyway, one has to be careful with too complicated data structures and update code.

Implementations

Classical Approach

The square centric classical approach with bitboards was used in Chess 4.5 and descibed by Larry Atkin and David Slate ^[4] . The incrementally updated attack tables, from which most move generation is done, are called ATKFR and ATKTO. ATKFR is a set of 64 bitboards which give, for each square, all the squares attacked by the piece, if any, that resides on the square. ATKTO (Square Attacked By) is the transpose of ATKFR, giving for each square, the locations of all pieces that attack that square. For instance the square E4 (T) is attacked by a black rook at E8, a black knight at F6, and defended by a white rook at E1 and a white pawn at D3 ^[5] :

attacks_to[E4]
 . . . . 1 . . .
 . . . . . . . .
 . . . . . 1 . .
 . . . . . . . .
 . . . . T . . .
 . . . 1 . . . .
 . . . . . . . .
 . . . . 1 . . .

Alternatives

There are several alternatives for keeping the square centric information what pieces attack each particular square.

Piece-Sets

A Square Attacked By bitboard aka ATKFR as possible union-set of multiple pawns and pieces of either side require intersections with piece bitboards, or bitscanned square lookups, to determine which pieces and how many attack or defend.

Based on a fixed piece-type and bit-position relation with usual material dispositions (for each side, no more than one queen, two rooks, one bishop per square color, two knights), 32-bit Piece-Sets already inherit the information which pieces (and how many of both sides) attack a particular square, one can even imagine a 16-bit lookup inside a 64KByte table to get an denser attack indicator/count byte for each color a lá Ed Schröder. MS-DOS IsiChess maintained an array of 64 32-bit piece-sets for every square, and an array of up to 32 attack-to bitboards for every piece. However working with piece-sets requires an additional indirection via a Piece-list to get the square of that piece.

Ed's lookup

As described by Ed Schröder in Evaluation in REBEL ^[6] , Rebel uses two board tables for both sides, one byte entry each, the three lower bits contain an attack counter, while the five upper bits indicate the presence of least one pawn or piece attacking/defending:

+------+------+------+------+------+------+------+------+
| BIT0 | BIT1 | BIT2 | BIT3 | BIT4 | BIT5 | BIT6 | BIT7 |
+------+------+------+------+------+------+------+------+
|      Number of     | PAWN |KNIGHT| ROOK | QUEEN| KING |
|      ATTACKERS     |      |BISHOP|      |      |      |
+------+------+------+------+------+------+------+------+

The information might be inaccurate in some cases since it loses some information if multiple pieces of one kind are involved. However, since SEE might be erroneous anyway due to pins, x-rays or overloaded pieces, Ed's scheme seems sufficient for practical purposes - and it is fast. Each byte (for both sides) can act as index inside pre-calculated three-dimensional table to perform an SEE by looking up a target piece or square, attack- and defend-byte:

char see_table [14][256][256];   // 14*64 K = 896 KByte
 
see = see_table[Piece][attackByte][defendByte];

While the counter might be updated incrementally, the piece indicators as possible union of multiple pieces (i.e. two knights and one bishop) is not that simple to update, thus Ed generates those tables in evaluation on the fly by scanning the pieces of the board.

Direction wise

An other alternative to incremental updated attack tables is motivated by direction wise fill algorithms like Kogge-Stone for sliding pieces, and that one may hide memory latencies from probes of the transposition table. Especially pawn attacks are cheap to determine on the fly, and likely reduce the set of capture targets of least valuable pieces defended by pawns, which are otherwise object of Quiescence Search or SEE.

Forums Posts

1995 ...

Chess programming using bitboards by Joël Rivat, rgcc, August 18, 1995
Attack Tables by Roberto Waldteufel, CCC, October 20, 1998

2000 ...

Counting attacked squares: how? by Leen Ammeraal, CCC, January 24, 2002
attacks_from[] and attacks_to[] info by Nagendra Singh Tomar, CCC, October 21, 2002
Attack tables by Andreas Herrmann, CCC, November 20, 2002
The Zappa Attack Table Code by Anthony Cozzie, CCC, May 05, 2004
bitboards and incrementally updated attack tables by Eric Oldre, CCC, June 30, 2004
Attack table by Anonymous, Winboard Forum, October 06, 2004

2005 ...

Attack table musings by GeoffW, Winboard Forum, February 11, 2005
Incremental updating for positional evaluation by Steven Edwards, CCC, March 27, 2008
Piece attacks count by Marco Costalba, CCC, May 18, 2009 » Population Count

2010 ...

Incrementally-updated attack map by Harm Geert Muller, April 21, 2014 » Incremental Updates

References

^ The Game of War from Samuel Bak - represented by Pucker Gallery since 1969
^ Chess programming using bitboards by Joël Rivat, rgcc, August 18, 1995
^ Speed of Move Generator by Valavan Manohararajah, rgcc, August 15, 1995, post 5 by Robert Hyatt where he mentions on the fly generation with rotated bitboards
^ David Slate and Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine (ed. Peter W. Frey), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted (1988) in Computer Chess Compendium
^ Rotated bitmaps, a new twist on an old idea by Robert Hyatt
^ Evaluation in REBEL (hanging pieces) from How Rebel Plays Chess by Ed Schröder, also available as pdf

What links here?

Page	Date Edited
Andreas Herrmann	Nov 7, 2014
Arasan	Apr 8, 2018
Attack and Defend Maps	Nov 5, 2016
Bebe	Dec 23, 2017
Bitboards	Nov 14, 2017
BlackBishop	Nov 7, 2014
Board Representation	Dec 11, 2017
Bruja	Feb 3, 2015
CAPS	Dec 23, 2017
Check	Feb 1, 2018
Chess (Program)	Dec 22, 2017
Chess 0.5	Nov 20, 2016
Chest	Mar 3, 2015
Combinatorial Logic	Apr 6, 2017
Constellation	Oct 2, 2016
DanChess	Jun 17, 2012
Data	Nov 26, 2017
Deflection	May 21, 2011
Diablo	May 17, 2016
Dorpsgek	Apr 2, 2018
Double Attack	Oct 22, 2014
Encoding Moves	Mar 27, 2016
Eugen	Jan 7, 2016
Eugenio Castillo Jiménez	Jul 23, 2017
Eye Movements	Jul 22, 2015
Floyd	Sep 11, 2016
Golch	Dec 7, 2017
Gromit	Apr 5, 2017
Hagrid	Apr 12, 2016
Horizon	Mar 17, 2013
Incremental Updates	Sep 6, 2017
Interception	May 21, 2011
Interference	May 20, 2011
Joker NL	Sep 15, 2017
José Carlos Martínez Galán	Feb 19, 2017
King Safety	Feb 14, 2018
KnightCap	Nov 6, 2016
Legal Move	Feb 16, 2017
M-20	Oct 9, 2013
Mate at a Glance	Sep 24, 2014
Mediocre	Feb 27, 2015
MessChess	Mar 6, 2014
Mikhail Botvinnik	Jul 15, 2017
Mobility	Jan 17, 2018
Movei	Jan 7, 2016
MVV-LVA	Oct 26, 2017
Neural Networks	Mar 12, 2018
Node Types	Oct 22, 2017
Nullmover	Jul 21, 2013
Ostrich	Dec 28, 2017
Overloading	May 5, 2017
Pandix	Feb 4, 2017
Patzer	Apr 5, 2017
Perceiver	Nov 21, 2017
Peter Fendrich	May 19, 2017
Piece-Sets	Jun 9, 2017
Pioneer	Dec 23, 2017
Population Count	Sep 3, 2017
RDChess	May 3, 2013
Rookie	Jan 7, 2016
SEE - The Swap Algorithm	Jun 5, 2017
SnailChess	Nov 26, 2014
Snitch	Apr 7, 2016
SOMA	Mar 25, 2015
Spartacus	Oct 17, 2016
Spector	Nov 11, 2016
Square Attacked By	Jan 20, 2018
Square Control	Sep 15, 2016
Static Exchange Evaluation	Dec 14, 2017
Sunsetter	Jun 1, 2017
Tao	Jan 8, 2016
Vladimir Butenko	Aug 12, 2013
Woodpusher	Dec 12, 2016
Zach Wegner	Jan 7, 2016
Zappa	Oct 24, 2017

Up one Level

Attack Spans

GerdIsenberg — Thu, 04 Mar 2010 17:40:18 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Attack Spans

Set-wise pattern, based on attackspans are for instance isolated pawns, passers and candidates.

The admittedly arbitrary definition of front attackspans includes the attacked squares itself, thus it is like a fill of attacked squares in the appropriate direction. The rear attackspan is the complement set on the same file, so that the union of both spans covers the whole file. As always, we keep disjoint east-west sets for separate applications, despite illustrated as union with one single pawn:

white attack        white attack     attack filefill with least one
frontspan           rearspan         square attacked by white
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .
. . . w . . . .     . . 1 w 1 . . .     . . 1 w 1 . . .
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
 
black attack        black attack     attack filefill with least one
frontspan           rearspan         square attacked by black
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. . . . . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. . . b . . . .     . . 1 b 1 . . .     . . 1 b 1 . . .
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .
. . 1 . 1 . . .     . . . . . . . .     . . 1 . 1 . . .

The routines based on one step only, vertical fills and pawn spans :

U64 wEastAttackFrontSpans (U64 wpawns) {return eastOne(wFrontSpans(wpawns));}
U64 wWestAttackFrontSpans (U64 wpawns) {return westOne(wFrontSpans(wpawns));}
U64 bEastAttackFrontSpans (U64 bpawns) {return eastOne(bFrontSpans(bpawns));}
U64 bWestAttackFrontSpans (U64 bpawns) {return westOne(bFrontSpans(bpawns));}
 
U64 wEastAttackRearSpans (U64 wpawns)  {return eastOne(wRearFill(wpawns));}
U64 wWestAttackRearSpans (U64 wpawns)  {return westOne(wRearFill(wpawns));}
U64 bEastAttackRearSpans (U64 bpawns)  {return eastOne(bRearFill(bpawns));}
U64 bWestAttackRearSpans (U64 bpawns)  {return westOne(bRearFill(bpawns));}

The filefills are independent on color

U64 eastAttackFileFill (U64 pawns) {return eastOne(fileFill(pawns));}
U64 westAttackFileFill (U64 pawns) {return westOne(fileFill(pawns));}

If a pawn is not member of own west or east attack filefills, the pawn is half-isolated.
If a pawn is not member of the union of own east and west attack filefills, the pawn is isolated.
If a pawn is not member of the union of all opponent front pawn- and attack-spans, it is a passed pawn.

What links here?

Page	Date Edited
Attack Spans	Mar 4, 2010
Backward Pawns (Bitboards)	May 5, 2017
Candidates (Bitboards)	Nov 11, 2017
Fill Algorithms	Nov 6, 2013
Holes	Oct 16, 2017
Isolated Pawns (Bitboards)	Nov 18, 2012
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Pattern and Properties	Nov 11, 2017
Pawn Spans	Jul 22, 2010
PawnKing	Sep 5, 2014
Pin	Mar 7, 2017

Up one Level

Backward Pawns (Bitboards)

GerdIsenberg — Fri, 05 May 2017 10:28:18 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Backward Pawns

Stops with negative SEE

Kmoch's definition of a backward pawn or straggler: A half-free pawn on the second or third rank whose stop square lacks pawn protection but is controlled by a sentry. The definition of a backward pawn seems a bit ambiguous. May an isolated pawn also be a backward one? Or an pawn on a closed file? What about a backward ram or faked candidates or even levers?

Backward

We may use a more general definition of backwardness, to consider certain subsets independently. All pawns, which stop is not member of own front-attackspans but controlled by a sentry are backward:

U64 wBackward(U64 wpawns, U64 bpawns) {
   U64 stops = wpawns << 8;
   U64 wAttackSpans = wEastAttackFrontSpans(wpawns)
                    | wWestAttackFrontSpans(wpawns);
   U64 bAttacks     = bPawnEastAttacks(bpawns)
                    | bPawnWestAttacks(bpawns);
   return (stops & bAttacks & ~wAttackSpans) >> 8;
}

Straggler

Stragglers are the intersection of backward with open pawns and the second or third rank:

U64 wStraggler(U64 wpawns, U64 bpawns) {
   return wBackward (wpawns, bpawns)
        & wOpenPawns(wpawns, bpawns)
        & 0xffff00; // rank 2,3
}

In the strict sense, we still need to exclude levers. On the other hand, levers are subject of quiescence search anyway.

Telestop Weakness

As pointed out by Sam Hamilton ^[1] considering stop squares might be insufficient for pawns which may actually push, but have a permanent weakened telestop, f.i.:

8/5p2/6p1/p1p3P1/P1P5/7P/1P6/8 w - -

On the other hand, such a backward prospective pawn has a vital tempo, which is often decisive in certain pawn endings, so one should be careful to don't make the penalty too worse. Anyway, one may either apply the above wBackward algorithm with so far movable pawns shifted one rank up, or alternatively determine a backward square area, which is the black attack span of all black attacks which are outside the white front attack spans:

white pawns         black pawns
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . . . . 1 .
. . . . . . 1 .     1 . 1 . . . . .
1 . 1 . . . . .     . . . . . . . .
. . . . . . . 1     . . . . . . . .
. 1 . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
 
~white front     &  black attacks    -> stop squares
attackspans                             dominated by black 
. . . . 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     . . . . . . . .     . . . . . . . .
stop squares
dominated by black
filled down
-> white         &  white pawns      -> backward pawns
backward area
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 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     . . . . . . . .     . . . . . . . .

Dynamic Backwardness

A further Pass

Another issue is that some pawns or their stop squares are statically member of their own attack spans, but those spans could not be realized, since their pawns are either backward or rammed (or both). Those pawns (f.i. white pawn c4, and mutually black pawn a4 in the diagram) may determined in a second pass, only considering attack spans of movable pawns.

8/8/1p6/8/p1P1p3/3pP3/1P1P4/8 w - -

Stops with negative SEE

A more sophisticated definition of backwardness was given by Vincent Diepeveen ^[2], even a member of a pawn duo may be backward, if its stop square has a negative SEE score, also considering pieces. Here b7 is considered backward, no matter whether the other friendly pawn is on c7 or c6, since it's stop square b6 has a negative SEE in both cases.

8/1pp5/8/2P5/8/8/8/1R6 w - -

Publications

Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. Previous ed.: New York: McKay, 1959. ISBN 0-486-26486-6

Forum Posts

WHAT is the definition of a backward pawn? by Bas Hamstra, CCC, December 23, 2002
Backward Pawns by Mark Lefler, CCC, March 24, 2008
Doubled and Backward Pawn Engine "Definitions" by Brian Richardson, CCC, September 07, 2009
What is a backward pawn? by Lyudmil Tsvetkov, CCC, May 12, 2014

External Links

Backward pawn from Wikipedia

References

^ Re: Doubled and Backward Pawn Engine "Definitions" by Sam Hamilton, CCC, September 13, 2009
^ Re: WHAT is the definition of a backward pawn? by Vincent Diepeveen, CCC, December 24, 2002

What links here?

Page	Date Edited
Backward Pawn	May 5, 2017
Backward Pawns (Bitboards)	May 5, 2017
Bas Hamstra	Feb 4, 2018
Dartmouth CP	Jan 19, 2018
Design Principles	Jan 17, 2018
Hans Kmoch	Nov 11, 2017
Lyudmil Tsvetkov	Mar 28, 2018
Murka	Nov 11, 2016
Open Pawns (Bitboards)	Aug 24, 2017
Pawn Attacks (Bitboards)	Mar 4, 2010
Pawn chain	Jan 17, 2018
Pawn Pattern and Properties	Nov 11, 2017
PawnKing	Sep 5, 2014
Weak Pawns	Dec 19, 2013

Up one Level

Best Magics so far

GerdIsenberg — Fri, 13 Apr 2018 13:10:54 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Magic Bitboards * Best Magics so far

This page is intended to publish and share results on magic factors and shifts (64 - Bits used) for most dense magic bitboards tables. Little endian file and rank mapping is used (a1 = 0), for other mappings simply transform the square.

If you prefer your own magics, see Looking for Magics.

Legende

sq - the square of a rook or bishop considering little endian file and rank mapping
#sq - index of that square in the 0..63 range
premask - the mask to get all relevant occupied bits, considering the inner six bits.
bits - the population count of premask
used - hopefully less than bits, determines the shift (64 - used)
magic - the magic factor
postmask - attacks on the otherwise empty board
found by (optional) - the person who found that number.

Rook Magics

sq	#sq	premask	bits	used	magic	postmask	found by
a1	0	0x000101010101017E . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . . 1 1 1 1 1 1 .	12			0x01010101010101FE 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . . 1 1 1 1 1 1 1
b1	1	0x000202020202027C	11			0x02020202020202FD
c1	2	0x000404040404047A	11			0x04040404040404FB
d1	3	0x0008080808080876	11			0x08080808080808F7
e1	4	0x001010101010106E	11			0x10101010101010EF
f1	5	0x002020202020205E	11
g1	6	0x004040404040403E	11
h1	7	0x008080808080807E	12			0x808080808080807F
a2	8	0x0001010101017E00	11			0x010101010101FE01
b2	9	0x0002020202027C00	10			0x020202020202FD02
c2	10		10
d2	11		10
e2	12		10
f2	13		10
g2	14		10
h2	15		11
a3	16		11
b3	17		10
c3	18		10
d3	19		10
e3	20		10
f3	21		10
g3	22		10
h3	23		11
a4	24		11
b4	25		10
c4	26		10
d4	27		10
e4	28		10
f4	29		10
g4	30		10
h4	31		11
a5	32		11
b5	33		10
c5	34		10
d5	35		10
e5	36		10
f5	37		10
g5	38		10
h5	39		11
a6	40		11
b6	41		10
c6	42		10
d6	43		10
e6	44		10
f6	45		10
g6	46		10
h6	47		11
a7	48	0x007E010101010100	11	10	0x48FFFE99FECFAA00	0x01FE010101010101	Grant Osborne
b7	49	0x007C020202020200	10	9	0x48FFFE99FECFAA00	0x02FD020202020202	Grant Osborne
c7	50		10	9	0x497FFFADFF9C2E00		Grant Osborne
d7	51		10	9	0x613FFFDDFFCE9200		Grant Osborne
e7	52		10	9	0xffffffe9ffe7ce00		Volker Annuss
f7	53		10	9	0xfffffff5fff3e600		Volker Annuss
g7	54		10	9	0x3ff95e5e6a4c0		Niklas Fiekas
h7	55	0x007E808080808000	11	10	0x510FFFF5F63C96A0	0x807F808080808080	Grant Osborne
a8	56	0x7E01010101010100	12	11	0xEBFFFFB9FF9FC526	0xFE01010101010101	Grant Osborne
b8	57	0x7C02020202020200	11	10	0x61FFFEDDFEEDAEAE	0xFD02020202020202	Grant Osborne
c8	58	0x7A04040404040400	11	10	0x53BFFFEDFFDEB1A2	0xFB04040404040404	Grant Osborne
d8	59	0x7608080808080800	11	10	0x127FFFB9FFDFB5F6	0xF708080808080808	Grant Osborne
e8	60	0x6E10101010101000	11	10	0x411FFFDDFFDBF4D6	0xEF10101010101010	Grant Osborne
f8	61		11
g8	62	0x3E40404040404000	11	10	0x0003ffef27eebe74	0xBF40404040404040	Peter Österlund
h8	63	0x7E80808080808000	12	11	0x7645FFFECBFEA79E	0x7F80808080808080	Grant Osborne

Bishop Magics

sq	#sq	premask	bits	used	magic	postmask	found by
a1	0	0x0040201008040200 . . . . . . . . . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . . . . . . . . .	6	5	0xffedf9fd7cfcffff	0x8040201008040200 . . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . . . . . . . . .	Gerd Isenberg
b1	1		5	4	0xfc0962854a77f576		Gerd Isenberg
c1	2		5	5	0xE433BF9FF9BD3C0DL
d1	3		5	5	0x8F0BBE9CF98C0405L
e1	4		5	5	0x7E11DFD9DDFBDBF0L
f1	5		5
g1	6		5	4	0xfc0a66c64a7ef576		Gerd Isenberg
h1	7		6	5	0x7ffdfdfcbd79ffff		Gerd Isenberg
a2	8		5	4	0xfc0846a64a34fff6		Gerd Isenberg
b2	9		5	4	0xfc087a874a3cf7f6		Gerd Isenberg
c2	10		5	5	0x0040020042188680L
d2	11		5	5	0x0080000108D80200L
e2	12		5	5	0xF2048D48B0240820L
f2	13		5	5	0x810040B921030010L
g2	14		5	4	0xfc0864ae59b4ff76		Gerd Isenberg
h2	15		5	4	0x3c0860af4b35ff76		Gerd Isenberg
a3	16		5	4	0x73C01AF56CF4CFFB		Richard Pijl
b3	17		5	4	0x41A01CFAD64AAFFC		Richard Pijl
c3	18		7
d3	19		7
e3	20		7
f3	21		7
g3	22		5	4	0x7c0c028f5b34ff76		Gerd Isenberg
h3	23		5	4	0xfc0a028e5ab4df76		Gerd Isenberg
a4	24		5
b4	25		5
c4	26		7
d4	27		9
e4	28		9
f4	29		7
g4	30		5
h4	31		5
a5	32		5
b5	33		5
c5	34		7
d5	35		9
e5	36		9
f5	37		7
g5	38		5
h5	39		5
a6	40		5	4	0xDCEFD9B54BFCC09F		Richard Pijl
b6	41		5	4	0xF95FFA765AFD602B		Richard Pijl
c6	42		7
d6	43		7
e6	44		7
f6	45		7
g6	46		5	4	0x43ff9a5cf4ca0c01		Gerd Isenberg
h6	47		5	4	0x4BFFCD8E7C587601		Richard Pijl
a7	48		5	4	0xfc0ff2865334f576		Gerd Isenberg
b7	49		5	4	0xfc0bf6ce5924f576		Gerd Isenberg
c7	50		5
d7	51		5
e7	52		5
f7	53		5
g7	54		5	4	0xc3ffb7dc36ca8c89		Gerd Isenberg
h7	55		5	4	0xc3ff8a54f4ca2c89		Gerd Isenberg
a8	56		6	5	0xfffffcfcfd79edff		Gerd Isenberg
b8	57		5	4	0xfc0863fccb147576		Gerd Isenberg
c8	58		5
d8	59		5
e8	60		5
f8	61		5
g8	62		5	4	0xfc087e8e4bb2f736		Gerd Isenberg
h8	63		6	5	0x43ff9e4ef4ca2c89		Gerd Isenberg

Forum Posts

Looking for dense magics by Lucas Braesch, CCC, July 11, 2017
Disproving the existence of some magics by Niklas Fiekas, CCC, September 16, 2017
No bishop magics with fixed shift 8 by Niklas Fiekas, CCC, April 09, 2018

External Links

Tehran Wind Orchestra - Mission Impossible, Vahdat Hall, Tehran, Iran, YouTube Video

What links here?

Page	Date Edited
Best Magics so far	Apr 13, 2018
Grant Osborne	Dec 2, 2011
Home	Jul 2, 2018
Looking for Magics	Apr 13, 2018
Magic Bitboards	Apr 13, 2018

Up one level

BikJump

GerdIsenberg — Mon, 11 Aug 2014 15:27:51 GMT

Java Version

Platforms

History and Future Plans

External Links

What Links Here?

Home * Engines * BikJump

BikJump,
an UCI chess engine written in C++ by Aart Bik that features:

UCI compliant chess engine (runs in e.g. Chessbase Fritz, Chess for Android, or Arena GUI).
Iterative deepening with alpha-beta pruning and quiescent search.
Transposition table, null move pruning, and tactical extensions.
Ability to query Nalimov Endgame Tablebases (3,4,5,6-piece) during search.

All source code of BikJump (except the probing and decompression code for the endgame tablebases, which are used with kind permission of Eugene Nalimov and Andrew Kadatch) has been built from the ground up by Aart as a simple after-hours project to gain some experience with chess engine programming and experiment with new ideas.

Java Version

A derived Java version is used as built-in engine in Chess for Android and Chess for Glass. This application also supports the Universal Chess Interface (UCI) and the Chess Engine Communication Protocol to allow users to play against more powerful third party engines or even play tournaments between engines.

Platforms

BikJump is available for the following platforms:

History and Future Plans

BikJump was first released In January, 2007. The first generation (v1.x) was based on a mailbox representation, and over time increased in strength from about 1750 to 2000 RUEL. The second and current generation (v2.x), based on a bitboard representation, was released in November, 2008. Aart now has started work on "Deep" BikJump, featuring multi-threading to perform the search in parallel (commonly referred to as SMP support). Upcoming versions will be designated with the suffix P (e.g. v2.1P) to denote this new parallel support.

External Links

What Links Here?

Page	Date Edited
Aart Bik	Mar 1, 2018
BikJump	Aug 11, 2014
Chess for Android	Mar 1, 2018
Chess for Glass	Dec 26, 2016
Eigenmann Endgame Test	Jun 1, 2017
Engines	Mar 10, 2018
Mathematician	Apr 9, 2018
PuppetMaster	Sep 17, 2015

Up one Level

Bitboard Board-Definition

GerdIsenberg — Mon, 23 Jun 2014 19:33:45 GMT

Home * Board Representation * Bitboards * Bitboard Board-Definition

To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position ^[1]:

To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C/C++ source snippets, the scalar 64-bit long in Java. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time.

Classical Board

Those bitboards may part of a central position object which is incrementally updated while making or unmaking moves.

Structure

class CBoard
{
   U64 whitePawns;
   U64 whiteKnights;
   U64 whiteBishops;
   U64 whiteRooks;
   U64 whiteQueens;
   U64 whiteKing;
 
   U64 blackPawns;
   U64 blackKnights;
   U64 blackBishops;
   U64 blackRooks;
   U64 blackQueens;
   U64 blackKing;
   ...
};

Array

For better generalization and to avoid branches, one may encapsulate arrays of bitboards. For instance, inside the Beowulf sources (sample from moves.c) one finds a lot of branches on side to move to either fetch white or black piece bitboards, as already criticized by Vincent Diepeveen in 2001 ^[2] ...

  switch (side) {
   case WHITE: tsq = B->whiteRooks; break;
   case BLACK: tsq = B->blackRooks; break;
  }

.. where an indexed access with appropriate defined {0,1} color range for the side to move would avoid those branches, per piece-kind, ...

  tsq = B->rooks[side];

... or over all piece-kinds, ...

  tsq = B->pieceBB[nWhiteRook + side];

... for instance, on x86 or x86-64, utilizing its addressing modes with base- and scalable index register, plus displacement:

   ; rsi pointer to structure, rcx side (0 == White, 1 == Black)
   mov  rax, qword ptr [rsi + rookOffset + 8*rcx]

Likely one also keeps some often used redundant union sets like white and black pieces, occupancy or their complement, the empty squares.

class CBoard
{
   U64 pieceBB[14];
   U64 emptyBB;
   U64 occupiedBB;
   ...
public:
   enum enumPiece
   {
      nWhite,     // any white piece
      nBlack,     // any black piece
      nWhitePawn, // white Pawn
      nBlackPawn, // white Pawn
      ...
   };
 
   U64 getPieceSet(PieceType pt) const {return pieceBB[pt];}
   U64 getWhitePawns() const {return pieceBB[nWhitePawn];}
   ...
   U64 getPawns(ColorType ct) const {return pieceBB[nWhitePawn + ct];}
   ...
};

On initialization and update of the bitboards, see general setwise operations.

Denser Board

A common alternative to reduce the size of the board structure is to keep two color bitboards and six color independent piece bitboards, which are the union of black and white respective pieces, i.e. all queens. This space saving requires a cheap intersection of a color and a piece bitboard to get the required pieces of that color only.

class CBoard
{
   U64 pieceBB[8];
public:
   enum enumPiece
   {
      nWhite,     // any white piece
      nBlack,     // any black piece
      nPawn,
      nKnight,
      nBishop,
      nRook,
      nQueen,
      nKing
   };
 
   U64 getPieceSet(PieceType pt) const {return pieceBB[pieceCode(pt)] & pieceBB[colorCode(pt)];}
   U64 getWhitePawns() const {return pieceBB[nPawn] & pieceBB[nWhite];}
   ...
   U64 getPawns(ColorType ct) const {return pieceBB[nPawn] & pieceBB[ct];}
   ...
};

Forum Posts

Bit Board Bonkers?? by Dave, rec.games.chess.computer, July 28, 1997
Bitboard board representation by Eric Oldre, CCC, January 13, 2005
BitBoard representations of the board by Uri Blass, CCC, October 14, 2007
Decision concerning board representation by Piotr Lopusiewicz, CCC, May 05, 2013

External Links

Glenn Gould - Paul Hindemith, Piano Sonata No. 3 - Fugue, YouTube Video

References

^ Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond by Glen Pepicelli, 2005, O'Reilly's OnJava.com
^ On Beowulf - long post by Vincent Diepeveen, CCC, April 04, 2001

What links here?

Page	Date Edited
AlphaZero	Feb 10, 2018
Array	Dec 1, 2016
Bitboard Board-Definition	Jun 23, 2014
Bitboards	Nov 14, 2017
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
Chess 0.5	Nov 20, 2016
Color Flipping	May 17, 2017
Counter	Nov 13, 2017
Demolito	Mar 1, 2018
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
General Setwise Operations	Feb 25, 2018
Incremental Updates	Sep 6, 2017
Initial Position	Apr 14, 2018
King Pattern	Nov 15, 2013
Knight Pattern	Feb 23, 2015
Lachex	Jan 7, 2016
Make Move	Mar 2, 2016
Material Tables	May 5, 2017
Occupancy	Sep 19, 2016
Pieces	Feb 19, 2018
Quad-Bitboards	Jan 30, 2017
Rodent	Jan 11, 2018
Rotated Bitboards	Mar 7, 2017
RuyDos	Feb 17, 2018
SEE - The Swap Algorithm	Jun 5, 2017
Simona Tancig	Nov 7, 2012
Sliding Piece Attacks	May 27, 2016
Spector	Nov 11, 2016
Square Attacked By	Jan 20, 2018
Sungorus	Apr 11, 2014
Teki	Mar 29, 2018
Tunguska	Sep 16, 2017
WyldChess	Mar 10, 2018
X-ray Attacks (Bitboards)	Mar 31, 2015

Up one Level

Bitboards

GerdIsenberg — Tue, 14 Nov 2017 20:13:35 GMT

Home * Board Representation * Bitboards

		Bitboards, also called bitsets or bitmaps, are among other things used to represent the board inside a chess program in a piece centric manner. Bitboards, are in essence, finite sets of up to 64 elements - all the squares of a chessboard, one bit per square. Other board games with greater board sizes may be use set-wise representations as well ^[1], but classical chess has the advantage that one 64-bit word or register covers the whole board. Even more bitboard friendly is Checkers with 32-bit bitboards and less piece-types than chess ^[2] ^[3] .
Samuel Bak - Boards Meeting ^[4]

The Board of Sets

To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.

Bitboard Basics

Of course bitboards are not only about the existence of pieces - it is a general purpose, set-wise data-structure fitting in one 64-bit register. For example, a bitboard can represent things like attack- and defend sets, move-target sets and so on.

General Bitboard Techniques

The fundamental bitboard basics.

Pattern and Attacks

This is basically about chess, how to calculate attack-sets and various pattern for evaluation and move generation purposes.

Move Generation Issues

Bitboard aspects on move generation and static exchange evaluation (SEE).

Miscellaneous

Defining Bitboards

To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C or C++ source snippets, the scalar 64-bit long in Java. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time. The macro C64 will append a suffix to 64-bit constants as required by some compilers:

typedef unsigned __int64 U64;    // for the old microsoft compilers
typedef unsigned long long  U64; // supported by MSC 13.00+ and C99
#define C64(constantU64) constantU64##ULL

Bitboard-History

The general approach of bitsets was proposed by Mikhail R. Shura-Bura in 1952 ^[5] ^[6]. The bitboard method for holding a board game appears to have been invented also in 1952 by Christopher Strachey using White, Black and King bitboards in his checkers program for the Ferranti Mark 1 ^[7], and in the mid 1950's by Arthur Samuel in his checkers program as well. In computer chess, bitboards were first described by Georgy Adelson-Velsky et al. in 1967 ^[8] , reprinted 1970 ^[9] . Bitboards were used in Kaissa and in Chess. The invention and publication of Rotated Bitboards by Robert Hyatt ^[10] and Peter Gillgasch with Ernst A. Heinz in the 90s was another milestone in the history of bitboards. Steffan Westcott's innovations, too expensive on 32-bit x86 processors, should be revisited with x86-64 and SIMD instructions in mind. With the advent of fast 64-bit multiplication along with faster memory, Magic Bitboards as proposed by Lasse Hansen ^[11] and refined by Pradu Kannan ^[12] have surpassed Rotated.

Analysis

The use of bitboards has spawned numerous discussions about their costs and benefits. The major points to consider are:

Bitboards can have a high information density.
Single populated or even empty Bitboards have a low information density.
Bitboards are weak in answering questions like what piece if any resides on square x. One reason to keep a redundant mailbox board representation with some additional update costs during make/unmake.
Bitboards can operate on all squares in parallel using bitwise instructions. This is one of the main arguments used by proponents of bitboards, because it allows for a flexibility in evaluation.
Bitboards are rather handicapped on 32 bit processors, as each bitwise computation must be split into two or more instructions ^[13] . As most modern processors are now 64 bit, this point is somewhat diminished ^[14] .
Bitboards often rely on bit-twiddling and various optimization tricks and special instructions for certain hardware architectures, such as bitscan and population count. Optimal code requires machine dependent header-files in C/C++. Portable code is likely not optimal for all processors.
Some operations on bitboards are less general, f.i. shifts. This requires additional code overhead.

Publications

1970 ...

Georgy Adelson-Velsky, Vladimir Arlazarov, Alexander Bitman, Alexander Zhivotovsky and Anatoly Uskov (1970). Programming a Computer to Play Chess. Russian Mathematical Surveys, Vol. 25, pp. 221-262.
David Slate and Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium » Chess

1980 ...

Zdenek Zdráhal, Ivan Bratko, Alen Shapiro (1981). Recognition of Complex Patterns Using Cellular Arrays. The Computer Journal, Vol. 24, No. 3, pp. 263-270
Stuart Cracraft (1984). Bitmap move generation in Chess. ICCA Journal, Vol. 7, No. 3
Burton Wendroff (1985). Attack Detection and Move Generation on the X-MP/48. ICCA Journal, Vol. 8, No. 2
Arch D. Robison, Brian J. Hafner, Steven Skiena (1989). Eight Pieces Cannot Cover a Chess Board. The Computer Journal, Vol. 32, No. 6, pdf

1990 ...

Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3 » DarkThought
Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4 » Rotated Bitboards ^[15]

2000 ...

David Rasmussen (2004). Parallel Chess Searching and Bitboards. Master's thesis, ps » Parallel Search
Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces
Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
Pablo San Segundo, Ramón Galán, Fernando Matía, Diego Rodríguez-Losada, Agustín Jiménez (2006). Efficient Search Using Bitboard Models. ICTAI 2006, pdf
Fridel Fainshtein (2006). An Orthodox k-Move Problem-Composer for Chess Directmates. M.Sc. thesis, Bar-Ilan University, pdf, Appendix D - 64-bit Representation, pp. 105
Fridel Fainshtein, Yaakov HaCohen-Kerner (2006). A Chess Composer of Two-Move Mate Problems. ICGA Journal, Vol. 29, No. 1, pdf, Appendix E: 64-bit representation, pp. 22
Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf » Move Generation, Shogi
James Glenn, David Binkley (2008) An Investigation of Hierarchical Bit Vectors. New Topics in Theoretical Computer Science, pdf
Shi-Jim Yen, Jung-Kuei Yang (2009). The Bitboard Design and Bitwise Computing in Connect Six. 14th Game Programming Workshop
Fritz Reul (2009). New Architectures in Computer Chess, Ph.D. Thesis, pdf

2010 ...

Stefano Carlini (2010). Arimaa, a New Challenge for Artificial Intelligence. M.Sc. thesis, University of Modena and Reggio Emilia, pdf » Chapter 4, Bitboards in Arimaa
Shi-Jim Yen, Jung-Kuei Yang, Kuo-Yuan Kao, Tai-Ning Yang (2012). Bitboard Knowledge Base System and Elegant Search Architectures for Connect6. Knowledge-Based Systems, Vol. 34 » Connect6
Cameron Browne, Stephen Tavener (2013). Life in the Fast Lane. AI Factory » Conway's Game of Life within a Bitboard
Cameron Browne (2014). Bitboard Methods for Games. ICGA Journal, Vol. 37, No. 2

Forum Posts

1994

bitboard move generation by Robert Hyatt, rgc, October 25, 1994
bitboard move generator by Joël Rivat, rgc, November 13, 1994
bitboard position evaluations by Robert Hyatt, rgc, November 17, 1994 » Evaluation

1995 ...

Chess programming using bitboards by Joël Rivat, rgcc, August 18, 1995
Bit Board Bonkers?? by Dave, rec.games.chess.computer, July 28, 1997
Efficient Bitboard Implementation on 32-bit Architecture by Roberto Waldteufel, CCC, October 25, 1998
Bitboard question by Werner Inmann, CCC, December 02, 1998
Bitboards by Frank Phillips, CCC, December 05, 1998
bitboards in java? by vitor, CCC, April 06, 1999 » Java
BitBoards by Frank Phillips, CCC, May 29, 1999
Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999 » Rotated Bitboards ^[16]

2000 ...

To bitboard or not to bitboard? by Tord Romstad, CCC, August 30, 2003
How important are Bitboards? by Martin Schreiber, CCC, February 29, 2004
Two questions for bitboard experts by Tord Romstad, Winboard Forum, November 06, 2004 » In Between, Piece-Lists

2005 ...

Bitboard question by Tord Romstad, Winboard Forum, March 14, 2006
Speedup with bitboards on 64-bit CPUs by Tord Romstad, CCC, April 27, 2007
Speedup by bitboards by Onno Garms, Winboard Forum, July 13, 2007
BitBoard representations of the board by Uri Blass, CCC, October 14, 2007
Bitboards / move generation on larger boards by Gregory Strong, CCC, January 09, 2009
Bitboard techniques in Xiangqi by Harm Geert Muller, CCC, February 12, 2009 » Chinese Chess
Bitboards using 2 DOUBLE's ? by Carey, CCC, June 02, 2009 » Double

2010 ...

Bitboard implementation, how much time? by Ed Schröder, CCC, January 22, 2012
64 bits for 64 squares ? by Thomas Petzke, mACE Chess, April 28, 2013 » Population Count
Bitboard Tricks for Large Chess Variants by Ed Trice, CCC, November 01, 2014

2015 ...

Bitboard database code samples by Steven Edwards, CCC, May 25, 2015 » Symbolic
M42 - A C++ library for Bitboard attack mask generation by Syed Fahad, CCC, April 30, 2016 ^[17]
Checkers Bitboard representation by Pranav Deshpande, CCC, July 02, 2017 » Checkers
Bitboards and Java by Fred Hamilton, CCC, November 14, 2017 » Java

Viewer & Calculator

External Links

References

^ Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf
^ Checker Bitboards Tutorial by Jonathan Kreuzer
^ Checkers Bitboard representation by Pranav Deshpande, CCC, July 02, 2017
^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ Lazar A. Lyusternik, Aleksandr A. Abramov, Victor I. Shestakov, Mikhail R. Shura-Bura (1952). Programming for High-Speed Electronic Computers. (Программирование для электронных счетных машин)
^ Andrey Ershov, Mikhail R. Shura-Bura (1980). The Early Development of Programming in the USSR. in Nicholas C. Metropolis (ed.) A History of Computing in the Twentieth Century. Academic Press, preprint pp. 43
^ On Bitboards for White, Black and Kings to represent the checkers board, see David Link Video at 1:04:02
^ Early Reference on Bit-Boards by Tony Warnock from rec.games.chess, October 29, 1994
^ Georgy Adelson-Velsky, Vladimir Arlazarov, Alexander Bitman, Alexander Zhivotovsky and Anatoly Uskov (1970). Programming a Computer to Play Chess. Russian Mathematical Surveys, Vol. 25, pp. 221-262.
^ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
^ 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
^ Efficient Bitboard Implementation on 32-bit Architecture by Roberto Waldteufel, CCC, October 25, 1998
^ Speedup by bitboards by Onno Garms, Winboard Forum, July 13, 2007
^ Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
^ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
^ M42 by Syed Fahad

Up one level

BitScan

GerdIsenberg — Sun, 10 Sep 2017 15:44:37 GMT

Home * Board Representation * Bitboards * BitScan

		BitScan, a function that determines the bit-index of the least significant 1 bit (LS1B) or the most significant 1 bit (MS1B) in an integer such as bitboards. If exactly one bit is set in an unsigned integer, representing a numerical value of a power of two, this is equivalent to a base-2 logarithm. Many implementations have been devised since the advent of bitboards, as described on this page, and some implementation samples of concrete open source engines listed for didactic purpose.
M. C. Escher, Eye, 1946 ^[1]

Hardware vs. Software

For recent x86-64 architectures like Core 2 duo and K10, one should use the Processor Instructions for Bitscans via intrinsics or inline assembly, see x86-64 timing. P4 and K8 have rather slow bitscan-instructions. K8 uses so called vector path instructions ^[2] with 9 or 11 cycles latency, even blocking other processor resources. For these processors, specially K8 with already fast multiplication, the De Bruijn Multiplication (64-bit mode) or Matt Taylor's Folded 32-bit Multiplication (32-bit mode) might be the right choice. Other routines mentioned might be advantageous on certain architectures, specially with slow integer multiplications.

Non Empty Sets

Bitscan is most often used in serializing bitboards, and is therefor - due to a leading while-condition - not called with empty sets. Until stated otherwise, most mentioned bitscan-routines in C/C++ have the same prototype and assume none empty sets as actual parameter.

Bitscan forward

A bitscan forward is used to find the index of the least significant 1 bit (LS1B).

Trailing Zero Count

Bitscan forward is identical with a Trailing Zero Count for none empty sets, possibly available as machine instruction on some architectures, for instance the x86-64 bit-manipulation expansion set BMI1.

De Bruijn Multiplication

The De Bruijn bitscan was devised in 1997, according to Donald Knuth ^[3] by Martin Läuter, and independently by Charles Leiserson, Harald Prokop and Keith H. Randall a few month later ^[4] ^[5] , to determine the LS1B index by minimal perfect hashing. De Bruijn sequences were named after the Dutch mathematician Nicolaas de Bruijn. Interestingly sequences with the binary alphabet were already investigated by the French mathematician Camille Flye Sainte-Marie in 1894, but later "forgotten" and re-investigated and generalized by De Bruijn and Tanja van Ardenne-Ehrenfest half a century later ^[6] .

A 64-bit De Bruijn sequence contains 64-overlapped unique 6-bit sequences, thus a circle of 64 bits, where five leading zeros overlap five hidden "trailing" zeros. There are 226 = 67108864 odd sequences with 6 leading binary zeros and 226 even sequences with 5 leading binary zeros, which may be calculated from the odd ones by shifting left one.

With isolated LS1B

A multiplication with a power of two value (the isolated LS1B) acts like a left shift by it's exponent. Thus, if we multiply a 64-bit De Bruijn sequence with the isolated LS1B, we get a unique six bit subsequence inside the most significant bits. To obtain the bit-index we need to extract these upper six bits by shifting right the product, to lookup an array.

const int index64[64] = {
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6
};
 
/**
 * bitScanForward
 * @author Martin Läuter (1997)
 *         Charles E. Leiserson
 *         Harald Prokop
 *         Keith H. Randall
 * "Using de Bruijn Sequences to Index a 1 in a Computer Word"
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

See also how to Generate your "private" De Bruijn Bitscan Routine.

With separated LS1B

Instead of the classical LS1B isolation, Kim Walisch proposed the faster xor with the ones' decrement. The separation bb ^ (bb-1) contains all bits set including and below the LS1B. The 222 (4,194,304) upper De Bruijn sequences of the 226 available leave unique 6-bit indices. Using LS1B separation takes advantage of the x86 lea instruction, which saves the move instruction and unlike negate, has no data dependency on the flag register. Kim reported a 10 to 15 percent faster execution (compilers: g++-4.7 -O2, clang++-3.1 -O2, x86_64) than the traditional 64-bit De Bruijn bitscan on Intel Nehalem and Sandy Bridge CPUs.

const int index64[64] = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
 
/**
 * bitScanForward
 * @author Kim Walisch (2012)
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   return index64[((bb ^ (bb-1)) * debruijn64) >> 58];
}

Matt Taylor's Folding trick

A 32-bit friendly implementation to find the the bit-index of LS1B by Matt Taylor ^[7]. The xor with the ones' decrement, bb ^ (bb-1) contains all bits set including and below the LS1B. The 32-bit xor-difference of both halves yields either the complement of the upper half, or the lower half otherwise. Some samples:

ls1b	bb ^ (bb-1)	folded
63	`0xffffffffffffffff`	`0x00000000`
62	`0x7fffffffffffffff`	`0x80000000`
59	`0x0fffffffffffffff`	`0xf0000000`
32	`0x00000001ffffffff`	`0xfffffffe`
31	`0x00000000ffffffff`	`0xffffffff`
30	`0x000000007fffffff`	`0x7fffffff`
0	`0x0000000000000001`	`0x00000001`

Even if this folded "LS1B" contains multiple consecutive one-bits, the multiplication is De Bruijn like. There are only two magic 32-bit constants with the combined property of 32- and 64-bit De Bruijn sequences to apply this minimal perfect hashing:

const int lsb_64_table[64] =
{
   63, 30,  3, 32, 59, 14, 11, 33,
   60, 24, 50,  9, 55, 19, 21, 34,
   61, 29,  2, 53, 51, 23, 41, 18,
   56, 28,  1, 43, 46, 27,  0, 35,
   62, 31, 58,  4,  5, 49, 54,  6,
   15, 52, 12, 40,  7, 42, 45, 16,
   25, 57, 48, 13, 10, 39,  8, 44,
   20, 47, 38, 22, 17, 37, 36, 26
};
 
/**
 * bitScanForward
 * @author Matt Taylor (2003)
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   unsigned int folded;
   assert (bb != 0);
   bb ^= bb - 1;
   folded = (int) bb ^ (bb >> 32);
   return lsb_64_table[folded * 0x78291ACF >> 26];
}

A slightly modified version may take one x86-register less in 32-bit mode, but calculates bb-1 twice:

int bitScanForwardM(BitBoard bb) {
   unsigned int folded;
   assert (bb != 0);
   folded  = (int)((bb ^ (bb-1)) >> 32);
   folded ^= (int)( bb ^ (bb-1)); // lea
   return lsb_64_table[folded * 0x78291ACF >> 26];
}

with this VC6 generated x86 assembly to compare:

bitScanForward PROC NEAR                   bitScanForwardM PROC NEAR
   mov  ecx, DWORD PTR _bb$[esp-4]            mov  eax, DWORD PTR _bb$[esp-4]
   mov  eax, DWORD PTR _bb$[esp]              mov  ecx, eax
   mov  edx, ecx                              add  ecx, -1
   push esi                                   mov  ecx, DWORD PTR _bb$[esp]
   add  edx, -1                               mov  edx, ecx
   mov  esi, eax                              adc  edx, -1
   adc  esi, -1                               xor  edx, ecx
   xor  ecx, edx                              lea  ecx, DWORD PTR [eax-1]
   xor  eax, esi                              xor  edx, ecx
   pop  esi
   xor  eax, ecx                              xor  edx, eax
   imul eax, 78291acfH                        imul edx, 78291acfH
   shr  eax, 26                               shr  edx, 26
   mov  eax, DWORD PTR _lsb_64_table[eax*4]   mov  eax, DWORD PTR _lsb_64_table[edx*4]
   ret  0                                     ret  0
bitScanForward ENDP                        bitScanForward ENDP

Walter Faxon's magic Bitscan

Walter Faxon's 32-bit friendly magic bitscan ^[8] uses a fast none minimal perfect hashing function:

const char LSB_64_table[154] =
{
#define __ 0
   22,__,__,__,30,__,__,38,18,__, 16,15,17,__,46, 9,19, 8, 7,10,
   0, 63, 1,56,55,57, 2,11,__,58, __,__,20,__, 3,__,__,59,__,__,
   __,__,__,12,__,__,__,__,__,__, 4,__,__,60,__,__,__,__,__,__,
   __,__,__,__,21,__,__,__,29,__, __,37,__,__,__,13,__,__,45,__,
   __,__, 5,__,__,61,__,__,__,53, __,__,__,__,__,__,__,__,__,__,
   28,__,__,36,__,__,__,__,__,__, 44,__,__,__,__,__,27,__,__,35,
   __,52,__,__,26,__,43,34,25,23, 24,33,31,32,42,39,40,51,41,14,
   __,49,47,48,__,50, 6,__,__,62, __,__,__,54
#undef __
};
 
/**
 * bitScanForward
 * @author Walter Faxon, slightly modified
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb)
{
   unsigned int t32;
   assert(bb);
   bb  ^= bb - 1;
   t32  = (int)bb ^ (int)(bb >> 32);
   t32 ^= 0x01C5FC81;
   t32 +=  t32 >> 16;
   t32 -= (t32 >> 8) + 51;
   return LSB_64_table [t32 & 255]; // 0..63
}

A slightly modified version may take one x86-register less in 32-bit mode, but calculates bb-1 twice:

int bitScanForward(U64 bb)
{
   int t32 = 0x01C5FC81;
   assert(bb);
   t32 ^= (int)((bb ^ (bb-1)) >> 32);
   t32 ^= (int)( bb ^ (bb-1)); // lea
   t32 += t32 >> 16;
   t32 -=(t32 >>  8) + 51;
   return LSB_64_table [t32 & 255];
}

The initial LS1B separation by bb ^ (bb-1) and folding is equivalent to Matt's,

ls1b	bb ^ (bb-1)	folded
63	`0xffffffffffffffff`	`0x00000000`
62	`0x7fffffffffffffff`	`0x80000000`
59	`0x0fffffffffffffff`	`0xf0000000`
32	`0x00000001ffffffff`	`0xfffffffe`
31	`0x00000000ffffffff`	`0xffffffff`
30	`0x000000007fffffff`	`0x7fffffff`
0	`0x0000000000000001`	`0x00000001`

while Walter originally resets the LS1B, yielding in a cyclic index wrap:

LS1B	(bb & (bb-1)) ^ (bb-1)	folded
0	`0x0000000000000000`	`0x00000000`
63	`0x7fffffffffffffff`	`0x80000000`
60	`0x0fffffffffffffff`	`0xf0000000`
33	`0x00000001ffffffff`	`0xfffffffe`
32	`0x00000000ffffffff`	`0xffffffff`
31	`0x000000007fffffff`	`0x7fffffff`
1	`0x0000000000000001`	`0x00000001`

Bitscan by Modulo

Another idea is to apply a modulo (remainder of a division) operation of the isolated LS1B by the prime number 67 ^[9] ^[10] . The remainder 0..66 can be used to perfectly hash the bit-index table. Three gaps are 0, 17, and 34, so the mod 67 can make a branchless trailing zero count:

Bit-Index	Bitboard	mod 67
-	0x0000000000000000	0
0	0x0000000000000001	1
1	0x0000000000000002	2
2	0x0000000000000004	4
3	0x0000000000000008	8
4	0x0000000000000010	16
5	0x0000000000000020	32
6	0x0000000000000040	64
7	0x0000000000000080	61
8	0x0000000000000100	55
9	0x0000000000000200	43
10	0x0000000000000400	19
11	0x0000000000000800	38
12	0x0000000000001000	9
13	0x0000000000002000	18
14	0x0000000000004000	36
15	0x0000000000008000	5
16	0x0000000000010000	10
17	0x0000000000020000	20
18	0x0000000000040000	40
19	0x0000000000080000	13
20	0x0000000000100000	26
21	0x0000000000200000	52
22	0x0000000000400000	37
23	0x0000000000800000	7
24	0x0000000001000000	14
25	0x0000000002000000	28
26	0x0000000004000000	56
27	0x0000000008000000	45
28	0x0000000010000000	23
29	0x0000000020000000	46
30	0x0000000040000000	25
31	0x0000000080000000	50
32	0x0000000100000000	33
33	0x0000000200000000	66
34	0x0000000400000000	65
35	0x0000000800000000	63
36	0x0000001000000000	59
37	0x0000002000000000	51
38	0x0000004000000000	35
39	0x0000008000000000	3
40	0x0000010000000000	6
41	0x0000020000000000	12
42	0x0000040000000000	24
43	0x0000080000000000	48
44	0x0000100000000000	29
45	0x0000200000000000	58
46	0x0000400000000000	49
47	0x0000800000000000	31
48	0x0001000000000000	62
49	0x0002000000000000	57
50	0x0004000000000000	47
51	0x0008000000000000	27
52	0x0010000000000000	54
53	0x0020000000000000	41
54	0x0040000000000000	15
55	0x0080000000000000	30
56	0x0100000000000000	60
57	0x0200000000000000	53
58	0x0400000000000000	39
59	0x0800000000000000	11
60	0x1000000000000000	22
61	0x2000000000000000	44
62	0x4000000000000000	21
63	0x8000000000000000	42

/**
 * trailingZeroCount
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit, 64 if bb is zero
 */
int trailingZeroCount(U64 bb) {
   static const int lookup67[67+1] = {
      64,  0,  1, 39,  2, 15, 40, 23,
       3, 12, 16, 59, 41, 19, 24, 54,
       4, -1, 13, 10, 17, 62, 60, 28,
      42, 30, 20, 51, 25, 44, 55, 47,
       5, 32, -1, 38, 14, 22, 11, 58,
      18, 53, 63,  9, 61, 27, 29, 50,
      43, 46, 31, 37, 21, 57, 52,  8,
      26, 49, 45, 36, 56,  7, 48, 35,
       6, 34, 33, -1 };
   return lookup67[(bb & -bb) % 67];
}

Since div/mod is an expensive instruction, a modulo by a constant is likely replaced by reciprocal fixed point multiplication to get the quotient and a second multiplication and difference to get the remainder. Compared with De Bruijn multiplication it is still too slow.

Divide and Conquer

This is a broad group of bitscans that test in succession, like the trailing zero count based on Reinhard Scharnagl's proposal ^[11] :

/**
 * trailingZeroCount
 *  like bitScanForward for none empty sets
 * @author Reinhard Scharnagl
 * @param bb bitboard to scan
 * @return index (0..64)
 */
unsigned char lsbRS[256] = {
    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
 
int trailingZeroCount(U64 b) {
  unsigned buf;
  int acc = 0;
 
  if ((buf = (unsigned)b) == 0) {
    buf = (unsigned)(b >> 32);
    acc = 32;
  }
  if ((unsigned short)buf == 0) {
    buf >>= 16;
    acc += 16;
  }
  if ((unsigned char)buf == 0) {
    buf >>= 8;
    acc += 8;
  }
  return acc + lsbRS[buf & 0xff];
}

What about direct calculation? On x86 this is a chain of test, set and lea instructions:

/**
 * bitScanForward
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   unsigned int lsb;
   assert (bb != 0);
   bb &= -bb; // LS1B-Isolation
   lsb = (unsigned)bb
       | (unsigned)(bb>>32);
   return (((((((((((unsigned)(bb>>32) !=0)  * 2)
                 + ((lsb & 0xffff0000) !=0)) * 2)
                 + ((lsb & 0xff00ff00) !=0)) * 2)
                 + ((lsb & 0xf0f0f0f0) !=0)) * 2)
                 + ((lsb & 0xcccccccc) !=0)) * 2)
                 + ((lsb & 0xaaaaaaaa) !=0);
}

Double conversion of LS1B

Assuming 64-bit doubles and little-endian structure (not portable). We convert the isolated LS1B to a double and interprete the exponent:

/**
 * bitScanForward
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit
 *         -1023 if passing zero
 */
int bitScanForward(U64 bb)
{
   union {
      double d;
      struct {
         unsigned int mantissal : 32;
         unsigned int mantissah : 20;
         unsigned int exponent : 11;
         unsigned int sign : 1;
      };
   } ud;
   ud.d = (double)(bb & -bb); // isolated LS1B to double
   return ud.exponent - 1023;
}

Index of LS1B by Popcount

If we have a fast population-count instruction, we can count the trailing zeros of LS1B after subtracting one:

// precondition bb != 0
int bitScanForward(U64 bb) {
   assert (bb != 0);
   return popCount( (bb & -bb) - 1 );
}

Bitscan reverse

A bitscan reverse is used to find the index of the most significant 1 bit (MS1B). For non empty sets it is equivalent to floor of the base-2 logarithm. MS1B isolalation or separation is more expensive than LS1B isolalation or separation, due to the LS1B related Two's complement tricks are not applicable. However, beside Divide and Conquer and Double conversion, Bitscan reverse with MS1B separation is mentioned.

Divide and Conquer

As introduced by Eugene Nalimov in 2000, for an IA-64 version of Crafty ^[12] ^[13]

/**
 * bitScanReverse
 * @author Eugene Nalimov
 * @param bb bitboard to scan
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 bb)
{
   int result = 0;
   if (bb > 0xFFFFFFFF) {
      bb >>= 32;
      result = 32;
   }
   if (bb > 0xFFFF) {
      bb >>= 16;
      result += 16;
   }
   if (bb > 0xFF) {
      bb >>= 8;
      result += 8;
   }
   return result + ms1bTable[bb];
}

Tribute to Frank Zappa

A branchless and little bit obfuscated version of the devide and conquer bitScanReverse with in-register-lookup ^[14] - as tribute to Frank Zappa with identifiers from Freak Out! (1966), Hot Rats (1969), Waka/Jawaka (1972), Sofa (1975), One Size Fits All (1975), Sheik Yerbouti (1979), and Jazz from Hell (1986):

typedef unsigned __int64 OneSizeFits;
typedef unsigned int HotRats;
const HotRats s      =   0;
const HotRats heik   = 457;
const HotRats y      =   1;
const HotRats e      =   2;
const HotRats r      =   3;
const HotRats b      =   4;
const HotRats o      =   5;
const HotRats u      =   8;
const HotRats t      =  16;
const HotRats i      =  32;
const HotRats     ka = (1<< 4)-1;
const HotRats   waka = (1<< 8)-1;
const HotRats jawaka = (1<<16)-1;
const HotRats jazzFromHell = 0-(16*3*heik);
 
HotRats freakOut(OneSizeFits all) {
   HotRats so,fa;
   fa   = (HotRats)(all >> i);
   so   = (fa!=s)       << o;
   fa  ^= (HotRats) all & (fa!=s)-y;
   so  ^= (jawaka < fa) << b;
   fa >>= (jawaka < fa) << b;
   so  ^= (  waka - fa) >> t    & u;
   fa >>= (  waka - fa) >> t    & u;
   so  ^= (    ka - fa) >> u    & b;
   fa >>= (    ka - fa) >> u    & b;
   so  ^=  jazzFromHell >> e*fa & r;
   return so;
}

De Bruijn Multiplication

While the tribute to Frank Zappa is quite 32-bit friendly ^[15], Kim Walisch suggested to use the parallel prefix fill for a MS1B separation with the same De Bruijn multiplication and lookup as in his bitScanForward routine with separated LS1B, with less instructions in 64-bit mode. A log base 2 method was already devised by Eric Cole on January 8, 2006, and shaved off rounded up to one less than the next power of 2 by Mark Dickinson ^[16] on December 10, 2009, as published in Sean Eron Anderson's Bit Twiddling Hacks for 32-bit integers ^[17].

const int index64[64] = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
 
/**
 * bitScanReverse
 * @authors Kim Walisch, Mark Dickinson
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   bb |= bb >> 1; 
   bb |= bb >> 2;
   bb |= bb >> 4;
   bb |= bb >> 8;
   bb |= bb >> 16;
   bb |= bb >> 32;
   return index64[(bb * debruijn64) >> 58];
}

Double conversion

Assuming 64-bit doubles and little-endian structure (not portable!). Conversion to a double, interpreting the exponent. To avoid possible rounding errors, some lower bits may be cleared.

/**
 * bitScanReverse
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @return index (0..63) of most significant one bit
 *         -1023 if passing zero
 */
int bitScanReverse(U64 bb)
{
   union {
      double d;
      struct {
         unsigned int mantissal : 32;
         unsigned int mantissah : 20;
         unsigned int exponent : 11;
         unsigned int sign : 1;
      };
   } ud;
   ud.d = (double)(bb & ~(bb >> 32));  // avoid rounding error
   return ud.exponent - 1023;
}

Leading Zero Count

Some processors have a fast leading zero count instruction. The Motorola 68020 has a bit field find first one instruction (BFFFO), which actually performs an up to 32-bit Leading Zero Count ^[18] . x86-64 AMD K10 has lzcnt as part of the SSE4a extension ^[19] ^[20] , BMI1 has lzcnt as well, while AVX-512CD even features leading zero count on vectors of eight bitbaords.

One can replace bitScanReverse of non empty sets by leadingZeroCount xor 63. Like trailing zero count, it returns 64 for empty sets, and might therefor save the leading condition in some applications.

Bitscan versus Zero Count

While the presented bitscan routines are suited to work only on none empty sets and return a value-range from 0 to 63 as bit-index, leading or trailing zero-count instructions or routines leave 64 for empty sets. Zero-counting has a immanent property of dealing correctly with empty sets - while it likely takes a conditional branch to implement this semantic in bit-scanning.

int trailingZeroCount(U64 bb) {
    if ( bb )
       return bitScanForward(bb);
    return 64;
}
 
int leadingZeroCount(U64 bb) {
    if ( bb )
       return bitScanReverse(bb) ^ 63;
    return 64;
}

Bitscan with Reset

While traversing sets, one may combine bitscanning with reset found bit. That implies passing the bitboard per reference or pointer, and tends to confuse compilers to keep all inside registers inside a typical serialization loop ^[21] .

int bitScanForwardWithReset(U64 &bb) { // also called dropForward
    int idx = bitScanForward(bb);
    bb &= bb - 1; // reset bit outside
    return idx;
}

Generalized Bitscan

This generalized bitscan uses a boolean parameter to scan reverse or forward. It relies on bitScanReverse, but conditionally masks the LS1B in case of scanning forward. It might be used in the classical approach to get positive or negative ray directions with one generalized routine.

 /**
 * generalized bitScan
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @param reverse, true bitScanReverse, false bitScanForward
 * @return index (0..63) of least/most significant one bit
 */
 int bitScan(U64 bb, bool reverse) {
    U64 rMask;
    assert (bb != 0);
    rMask = -(U64)reverse;
    bb &= -bb | rMask;
    return bitScanReverse(bb);
 }

Processor Instructions for Bitscans

x86

x86-64 processors have bitscan instructions and can be accessed with compilers today through either inline assembly or compiler intrinsics. For the Microsoft/Intel C compiler, the intrinsics can be accessed by including and using the instructions _BitScanForward64 ^[22] , _BitScanReverse64 ^[23] or _lzcnt64 ^[24] .

unsigned char_BitScanForward64(unsigned long * Index,  unsigned __int64 Mask);
unsigned char _BitScanReverse64(unsigned long * Index,  unsigned __int64 Mask);
unsigned __int64 __lzcnt64(unsigned __int64 value); // AMD K10 only see CPUID

Linux provides library functions ^[25] , find first bit set (ffsll) in a word leaves an index of 1..64, and zero of no bit is set ^[26] . GCC 4.4.5 further has the Built-in Function _builtin_ffsll for finding the least significant one bit, _builtin_ctzll for trailing, and _builtin_clzll for leading zero count ^[27] :

/* Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero */
int __builtin_ffsll (unsigned long long);
 
/* Returns the number of trailing 0-bits in x, starting at the least significant bit position.
   If x is 0, the result is undefined */
int __builtin_ctzll (unsigned long long);
 
/* Returns the number of leading 0-bits in x, starting at the most significant bit position.
   If x is 0, the result is undefined */
int __builtin_clzll (unsigned long long);

Emulating Intrinsics

For the GNU C compiler, the intrinsics can be emulated with inline assembly ^[28] .

//These processor instructions work only for 64-bit processors
#ifdef _MSC_VER
    #include <intrin.h>
    #ifdef _WIN64
        #pragma intrinsic(_BitScanForward64)
        #pragma intrinsic(_BitScanReverse64)
        #define USING_INTRINSICS
    #endif
#elif defined(__GNUC__) && defined(__LP64__)
    static INLINE unsigned char _BitScanForward64(unsigned long* Index, U64 Mask)
    {
        U64 Ret;
        __asm__
        (
            "bsfq %[Mask], %[Ret]"
            :[Ret] "=r" (Ret)
            :[Mask] "mr" (Mask)
        );
        *Index = (unsigned long)Ret;
        return Mask?1:0;
    }
    static INLINE unsigned char _BitScanReverse64(unsigned long* Index, U64 Mask)
    {
        U64 Ret;
        __asm__
        (
            "bsrq %[Mask], %[Ret]"
            :[Ret] "=r" (Ret)
            :[Mask] "mr" (Mask)
        );
        *Index = (unsigned long)Ret;
        return Mask?1:0;
    }
    #define USING_INTRINSICS
#endif

Intrinsics versus asm

Alternatively, rather than to emulate the intrinsics one might use the standard prototype, by using intrinsics or inline assembly for GCC ^[29] :

#ifdef USE_X86INTRINSICS
#include <intrin.h>
#pragma intrinsic(_BitScanForward64)
#pragma intrinsic(_BitScanReverse64)
 
/**
 * bitScanForward
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 x) {
   unsigned long index;
   assert (x != 0);
   _BitScanForward64(&index, x);
   return (int) index;
}
 
/**
 * bitScanReverse
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 x) {
   unsigned long index;
   assert (x != 0);
   _BitScanReverse64(&index, x);
   return (int) index;
}
#else
 
/**
 * bitScanForward
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 x) {
   assert (x != 0);
   asm ("bsfq %0, %0" : "=r" (x) : "0" (x));
   return (int) x;
}
 
/**
 * bitScanReverse
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 x) {
   assert (x != 0);
   asm ("bsrl %0, %0" : "=r" (x) : "0" (x));
   return (int) x;
}
#endif

Bsf/Bsr x86-64 Timings

The instruction latency and reciprocal throughput ^[30] heavily differs between various x86-64 architectures:

Architecture Stepping	Instruction(s)	Latency / Cycles	Reciprocal Throughput
AMD
K8 ^[31]	BSF reg16/32/64, mreg16/32/64	Vector Path 8/8/9	8/8/9
K8 ^[31]	BSR reg16/32/64, mreg16/32/64	Vector Path 11	11
K10 ^[32]	BSF reg, reg	Vector Path 4	4
	BSR reg, reg	Vector Path 4	4
	LZCNT reg, reg	Direct Path single 2	1
Intel ^[33]
ATOM	BSF/BSR	16	15
NetBurst 0F_3H	BSF/BSR	16	4
NetBurst 0F_2H	BSF/BSR	8	2
Core 06_0EH	BSF/BSR	2	1
65 nm Intel Core 06_0FH	BSF/BSR	2	1
Enhanced Intel Core 06_17H	BSF/BSR	1	1
Enhanced Intel Core 06_1DH	BSF/BSR	1	1
Nehalem 06_1AH	BSF/BSR	3	1
Sandy Bridge Ivy Bridge Haswell ^[34]	BSF/BSR	3	1
	LZCNT	3	1
	TZCNT	3	1

Bsf/Bsr behavior with zero source

Intel and AMD specify different behavior. In praxis there seems no difference so far. However, as long as Intel docs explicitly state content undefined, it is recommend to don't rely on a pre-initialized content of that target register, if the source is zero.

Intel : If the content of the source operand is 0, the content of the destination operand is undefined. ^[35]
AMD: If the second operand contains 0, the instruction sets ZF to 1 and does not change the contents of the destination register. ^[36]

ARM

ARM has CLZ (Count Leading Zeros) instruction for 32-bit integers. ARM instruction is available in ARMv5 and above, 32-bit Thumb instruction is available in ARMv6T2 and ARMv7 ^[37] , the C-intrinsic is called _builtin_clz ^[38] ^[39] ^[40] .

Engine Samples

Publications

Alan Turing (1949). Alan Turing's Manual for the Ferranti Mk. I. transcribed in 2000 by Robert Thau, pdf from The Computer History Museum, 9.4 The position of the most significant digit » Ferranti Mark 1
Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf
Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p. 10
Andreas Stiller (2013). Spezialkommando - Bits setzen, abfragen, scannen und mehr. c't Magazin für Computertechnik 7/2013, p. 186 (German)

Forum Posts

1996 ...

Bitboards: speeding up FirstOne by Laurent Desnogues, rgcc, April 10, 1996 » Othello
bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 6, 1996
bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 7, 1996
bitboard 2^i mod 67 is unique by Joël Rivat, rgcc, September 2, 1996
Question to Bob: Crafty , Alpha and FindBit() by Guido Schimmels, CCC, June 05, 1998
To Nalimov and other programmers about BSF/BSR in VC by Dezhi Zhao, CCC, January 16, 1999

2000 ...

Re: TASM 5.0 versus BSF by Frans Morsch, comp.lang.asm.x86, March 28, 2000
Will the Itanium have a BSF or BSR instruction? by Larry Griffiths, CCC, August 15, 2000
Re: Will the Itanium have a BSF or BSR instruction? by Eugene Nalimov, CCC, August 16, 2000
Binary question by Severi Salminen, CCC, October 19, 2000
Bitboards and Piece Lists by Dann Corbit, CCC, June 14, 2001
FirstBit() in assembler by David Rasmussen, CCC, January 13, 2002
Reply from Intel about BSF/BSR by Severi Salminen, CCC, January 31, 2002
"Using de Bruijn Sequences to Index a 1 in a Computer Word" by Oliver Roese, CCC, February 08, 2002
Another hacky method for bitboard bit extraction by Walter Faxon, CCC, November 17, 2002
Modulo verus BitScan and MMX-PopCount by Gerd Isenberg, CCC, November 29, 2002
Fast 3DNow! BitScan by Gerd Isenberg, CCC, December 01, 2002
Bitscan Conclusions by Matt Taylor, CCC, January 05, 2003
Bitscan by Matt Taylor, CCC, February 11, 2003
FirstOne for Linux by Sune Fischer, CCC, March 29, 2003
Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
Re: De Bruijn Sequence Generator by Dieter Bürssner, CCC, December 30, 2003 » De Bruijn Sequence Generator
Determining location of LSB/MSB by Renze Steenhuisen, CCC, February 09, 2004
Nalimov: bsf/bsr intrinsics implementation still not optimal by Dezhi Zhao, CCC, September 22, 2004
Re: Nalimov: bsf/bsr intrinsics implementation still not optimal by Eugene Nalimov, CCC, September 23, 2004

2005 ...

A data point for PowerPC bitboard program authors by Steven Edwards, CCC, May 09, 2005 » PowerPC
Best BitBoard LSB funktion? by Reinhard Scharnagl, Winboard Programming Forum, July 20, 2005
Fastest bitboard compress routine when you can't use ASM by mambofish, CCC, May 31, 2007
Bit twiddling question, part 2: arbitrary bitscan order by Zach Wegner, CCC, August 11, 2009
32 bit versions for bitscan64 by Michael Hoffmann, CCC, August 21, 2009
64-bit intrinsic performance by Nathan Thom, CCC, October 27, 2009
Bit Scan (equivalent to ASM instructions bsr and bsf) by Pascal Georges, CCC, December 24, 2009

2010 ...

bitScanReverse32 by Luca Hemmerich, CCC, January 25, 2010
Introduction and (hopefully) contribution - bitboard methods by Alcides Schulz, CCC, June 03, 2011 » Population Count
Leading Zero Count Question by Matthew R. Brades, CCC, September 16, 2012
Optimizing bitboards for ARM by Martin Sedlak, CCC, November 17, 2012
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014
Stockfish 32-bit and hardware instructions on MSVC++ by Syed Fahad, CCC, December 30, 2014 » Stockfish, BitScan, Population Count

2015 ...

Fun with De Bruijn by Henk van den Belt, CCC, August 27, 2015
Re: Linux Version of Maverick 1.5 by Michael Dvorkin, CCC, November 12, 2015 » OS X, Maverick
syzygy users (and Ronald) by Robert Hyatt, CCC, September 29, 2016 » Population Count

External Links

Find first set from Wikipedia
The Aggregate Magic Algorithms by Hank Dietz
Bit Twiddling Hacks by Sean Eron Anderson
An Efficient Bit-Reversal Sorting Algorithm for the Fast Fourier Transform by Jennifer Elaan, January 16, 2005
Efficient bit scan mechanism - United States Patent 6172623 from FreePatentsOnline.com
Frank Zappa & the Mothers - King Kong BBC Studio Recording 1968, YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Chip Architect: Detailed Architecture of AMD's Opteron - 1.3 A third class of Instructions by Hans de Vries
^ Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p 10
^ Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf
^ "Using de Bruijn Sequences to Index a 1 in a Computer Word" discussion in CCC, February 08, 2002
^ N. G. de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, available as pdf reprint
^ Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
^ Another hacky method for bitboard bit extraction by Walter Faxon, CCC, November 17, 2002
^ bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 6, 1996
^ Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
^ Best BitBoard LSB funktion? by Reinhard Scharnagl, Winboard Programming Forum, July 20, 2005
^ Re: Will the Itanium have a BSF or BSR instruction? by Eugene Nalimov, CCC, August 16, 2000
^ ms1bTable array in Eugene Nalimovs bitScanReverse by Stef Luijten, CCC, April 17, 2011
^ just another reverse bitscan by Gerd Isenberg, CCC, December 22, 2005
^ final version - homage to FZ by Gerd Isenberg, CCC, December 23, 2005
^ EuroPython 2012: Florence, July 2–8 | Mark Dickinson
^ Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup from Bit Twiddling Hacks by Sean Eron Anderson
^ 68020 Bit Field Instructions
^ SSE4a from Wikipedia
^ __lzcnt16, __lzcnt, __lzcnt64 Visual C++ Language Reference
^ Bitscan by Matt Taylor, CCC, February 11, 2003
^ _BitScanForward, _BitScanForward64 Visual C++ Language Reference
^ _BitScanReverse, _BitScanReverse64 Visual C++ Language Reference
^ __lzcnt16, __lzcnt, __lzcnt64 Visual C++ Language Reference
^ Section 3: library functions - Linux man pages
^ ffsll(3): find first bit set in word - Linux man page
^ Other Builtins - Using the GNU Compiler Collection (GCC)
^ Re: Nalimov: bsf/bsr intrinsics implementation still not optimal by Eugene Nalimov, CCC, September 23, 2004
^ Matters Computational - ideas, algorithms, source code (pdf) Ideas and Source Code by Jörg Arndt
^ Instruction tables, Lists of instruction latencies, throughputs and microoperation breakdowns for Intel and AMD CPU's (pdf) by Agner Fog
^ Software Optimization Guide for AMD64 Processors
^ Software Optimization Guide for AMD Family 10h and 12h Processors
^ Intel 64 and IA32 Architectures Optimization Reference Manual
^ Haswell Instructions Latency
^ Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2A: Instruction Set Reference, A-M (pdf) BSF—Bit Scan Forward 3-87
^ AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions (pdf) Bit Scan Forward pg. 111
^ ARM Information Center > General data processing instructions > CLZ
^ ARM Information Center > Instruction intrinsics > __builtin_clz
^ Other Builtins - Using the GNU Compiler Collection (GCC)
^ Bit Scan (equivalent to ASM instructions bsr and bsf) by Pascal Georges, CCC, December 24, 2009

What links here?

Page	Date Edited
68020	Jun 7, 2016
Alcides Schulz	Mar 29, 2018
Algorithms	May 5, 2017
Amundsen	Sep 3, 2013
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
AVX-512	Aug 8, 2017
Backtracking	Dec 16, 2017
Beowulf	May 5, 2017
Bison	Sep 29, 2016
Bit	Oct 29, 2012
Bit-Twiddling	Nov 6, 2017
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Bitfoot	Sep 8, 2015
BitScan	Sep 10, 2017
Blockage Detection	Oct 19, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Bobcat	Jun 27, 2017
Brainless	Jun 24, 2017
Cassandre	Jul 5, 2013
Charles Leiserson	Oct 12, 2016
CHEOPS	Apr 18, 2015
Chess 0.5	Nov 20, 2016
Chezzz	Jan 20, 2013
Classical Approach	Jan 28, 2018
Congruent Modulo Bitboards	Jun 26, 2013
CookieCat	Nov 15, 2016
Crafty	Jan 28, 2018
Cray-1	Dec 25, 2017
Cupcake	May 19, 2016
Daniel White	Feb 9, 2016
David Rasmussen	Dec 16, 2017
De Bruijn sequence	Feb 20, 2018
De Bruijn Sequence Generator	Dec 1, 2016
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Dieter Bürssner	Dec 1, 2016
Djinn	Feb 8, 2016
Double	May 30, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Encoding Moves	Mar 27, 2016
Eugene Nalimov	Dec 23, 2016
Ferranti Mark 1	Jun 2, 2015
Fizbo	Dec 22, 2017
Float	Nov 11, 2016
Gaviota	Jan 21, 2018
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Guido Schimmels	Apr 23, 2013
Hakkapeliitta	Apr 26, 2016
Harald Prokop	Nov 29, 2017
Hash Table	Jan 1, 2018
HeavyChess	Feb 14, 2014
Ifrit	Feb 7, 2016
Intel	Aug 29, 2015
Itanium	Aug 29, 2015
Jan Renze Steenhuisen	Sep 10, 2017
Java-Bitscan	Mar 15, 2014
Joël Rivat	Jul 21, 2017
Joker IT	Sep 16, 2017
Keith H. Randall	Jun 16, 2015
Kim Walisch	Aug 10, 2017
King of Kings	Sep 4, 2013
King Pattern	Nov 15, 2013
Knight Pattern	Feb 23, 2015
Koundinya Veluri	Feb 2, 2013
Kurt	Apr 20, 2014
Leila	May 8, 2017
Little Wing	Oct 26, 2017
Luca Hemmerich	Jun 19, 2017
Mac OS	Mar 25, 2016
Martin Sedlak	Dec 25, 2017
Mathematician	Apr 9, 2018
Matt Taylor	Feb 17, 2013
Matthew R. Brades	Jun 9, 2017
Michael Dvorkin	Jan 8, 2016
Mikhail R. Shura-Bura	Oct 30, 2013
Murka	Nov 11, 2016
Nathan Thom	Mar 15, 2013
Nicolaas de Bruijn	Feb 3, 2015
NoraGrace	Nov 23, 2014
Obstruction Difference	May 27, 2016
Othello	Jan 4, 2018
Pablo San Segundo	Feb 25, 2015
Paladin	Jan 29, 2017
Pascal Georges	Jun 1, 2014
PIC Microcontroller	Oct 27, 2017
Pieces versus Directions	Oct 6, 2016
Population Count	Sep 3, 2017
PowerPC	Oct 6, 2017
Prophet	Sep 30, 2017
Ramón Galán	Feb 25, 2015
RedQueen	Nov 13, 2017
Reinhard Scharnagl	Apr 9, 2016
Reverse Bitboards	Aug 29, 2015
Robert Hyatt	Dec 25, 2017
Robocide	May 11, 2016
SBAMG	Dec 4, 2016
Scorpio	Mar 28, 2018
Searcher	Sep 26, 2016
Senpai	Nov 10, 2017
Severi Salminen	May 7, 2015
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Space-Time Tradeoff	Jun 17, 2015
Spector	Nov 11, 2016
SSE4	Jun 5, 2016
Stef Luijten	Apr 26, 2015
Stefan Plenkner	Dec 31, 2015
Stockfish	Apr 7, 2018
Sune Fischer	Apr 7, 2014
Sungorus	Apr 11, 2014
Syed Fahad	Jan 1, 2017
Thor's Hammer	Nov 23, 2013
Traversing Subsets of a Set	Oct 14, 2016
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Vadim Demichev	Jul 26, 2013
Vice	Mar 8, 2016
Walter Faxon	Mar 6, 2015
Warrior	Feb 23, 2015
Wasp	Nov 24, 2017
X-ray Attacks (Bitboards)	Mar 31, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
x86-64 Instructions to Include	Feb 12, 2011
Zurichess	Mar 12, 2018

Up one Level

Candidates (Bitboards)

GerdIsenberg — Sat, 11 Nov 2017 09:57:18 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Candidates

		Candidates, pawns that can force themselves to become passed pawns simply with a series of pawn moves. Candidates are half-open pawns with no mechanical but dynamical obstructions. Specifially, the pawn must be on a half-open file, and the number of defender pawns that can help the pawn advance are greater than or equal to the number of pawns which attack the pawn or squares in front of it.
Samuel Bak - The Designated ^[1]

Candidate and Faker

While the intersection of the frontspan with opposing pawns is empty, the intersection of front attackspans with opposing pawns is not (otherwise it would already a passer). The opposing pawns as member of the front attackspan(s), stand sentinel over one or more squares in the frontfill of the open pawn, and are about to capture the open pawn, if it may advance into - or already is - a lever. Those opposing pawns are called sentries.

If the open pawn has one or more helper-pawns on adjacent files, which are able to recapture the sentry, the candidate is a real one and is guaranteed to force a passer. Otherwise, without enough support from helpers, the candidate is only a faker.

The following diagrams shows advanced candidates and fakers, assuming black to move:

candidates b6, f4   fakers -
sentries   c7, g2   more sentries
helper     c5, g4   than helpers
. . . . | . . .     . . . . | . . .
. . b . . . . .     b . b . . . . .
. w . . . . . .     . w . . . . . .
. . w . . . . .     . . w . . . . .
. . . . . b b .     . . . . . b b .
. . . . . . . .     . . . . . . . .
. . . . . . w .     . . . . w . w .
. . . | . . . .     . . . | . . . .

The white candidate on b6 is already in lever-distance with the sentry c7. The sentry c7 is likely forced to capture - otherwise b6 captures or pushes to become a passer. The white helper immediately recaptures and takes the role of the former candidate and becomes a passer. The black candidate on f4 can also force a passer. The helper on g4 compensates the sentry on g2. Usually, the candidate has to push forward, not the helper.

In the second diagram both candidates are pseudo-candidates or fakers, since there are more sentries than helpers - a7xb6 is required - otherwise, after c7xb6, c5-c6 would allow the helper to advance to a passer.

Advanced Candidates

Advanced candidates, already inside or about to enter the opponent side of the board are the most important to consider in evaluation. Even more if the interspan of sentries and helper is already one - and it is only about the control of the stop-square - or if the candidate is already part of a lever, the number of attacks and defenses.

In such cases, due to the forced nature of exchanging candidate, sentry and helper, only two or up to five plies are necessary to establish a passer. In fact those candidates may even be more worth than pawns already a passer - specially if the opponent king is outside the candidates square - or if the outside candidate may deflect the opponent king.

One may argue that a candidate already in lever distance with the sentry should be covered by quiescence search - since it is a capture/recapture sequence. Therefor more important to evaluate are the candidate-helper-duo/trio against one or two sentries, which is likely a kind of static exchange evaluation of the candidate's stop-square.

. . . . . . . .
. . s . . s . s   sentries
. . . . . . . .
. c h . . h c h   candidates with helpers
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

To cover sets of advanced white candidates with attacked but sufficient defended stops already on the on the 5th rank, one may use some code like this. Feel free to introduce branches, e.g. if there are no white pawns on the fifth rank. Anyway, wSafePawnSquares might be used elsewhere, e.g. to decide whether helper pawns may advance to defend candidate's stop.

U64 wCandidatesOn5th(U64 wpawns, U64 bpawns) {
   const U64 rank5     = C64(0x000000ff00000000);
   U64 bPawnAnyAttacks = bPawnAnyAttacks(bpawns);
   U64 wSafeSquares    = wSafePawnSquares(wpawns, bpawns);
   U64 wSafeAttacked   = bPawnAnyAttacks  &  wSafeSquares;
   U64 blackFrontSpan  = (bpawns >> 8)    | (bpawns >> 16); // only for 5th rank
   return wpawns & rank5 &~blackFrontSpan & (wSafeAttacked >> 8);
}

Less Advanced

If it is about the long-term evaluation of telestop -squares - or the need of advancement of helper(s) to defend the stop-square, things become more complicated and one probably better relies on search and some general bonus to advance half-free pawns and advanced duos. Feel free to cover attackspan-related stuff for less advanced candidates respectively helpers and helper's helpers.

d4 is candidate     d4 is faker         d4 faker due to     d4 is candidate
                                        helper's sentry     due to helper's helper f2
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . s . s . . .     . . s . s . . .     . . s . s . . .     . . s . s . . .
. . . . . . . .     . . . . . . . .     . . . . . hs. .     . . . . . hs. .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . c . . . .     . . . f . . . .     . . . f . . . .     . . . c . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . h . h . . .     . . h . . . . .     . . h . h . . .     . . h . h hh. .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .

The Sneaker

Also known as a hidden passed pawn. A kind of candidate in disguise is an unfree pawn or faker that may become a passer through a sacrificial combination. In the diagram white may sacrifice the faker with b5-b6 - allowing black to establish a passer on b6 - but the sneaker on c6 becomes a much more advanced passer with a frontspan of only two against five:

. . . . . . . .
. . b . . . . .
. . w . . . . .
. w . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

A sneaker is likely advanced (opponent side of the board), rammed and defended, but no lever. No other opposing pawn controls it's stop or telestop squares.

External Links

Pawn Power in Chess by Hans Kmoch - Glossary of Terms - Chess Forums - Chess.com ^[2]
Candidates Tournament from Wikipedia
Jango Edwards - Harry Christmas, September 10, 2009, Zeche Carl ^[3], Essen, YouTube Video

References

^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. Previous ed.: New York: McKay, 1959. ISBN 0-486-26486-6
^ Zeche Carl is part of The Industrial Heritage Trail

What links here?

Page	Date Edited
Attack Spans	Mar 4, 2010
Backward Pawns (Bitboards)	May 5, 2017
Candidate Passed Pawn	Nov 11, 2017
Candidates (Bitboards)	Nov 11, 2017
Faker	Nov 11, 2017
Hans Kmoch	Nov 11, 2017
Hidden Passed Pawn	Nov 11, 2017
Murka	Nov 11, 2016
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Attacks (Bitboards)	Mar 4, 2010
Pawn Pattern and Properties	Nov 11, 2017
Pawn Spans	Jul 22, 2010
PawnKing	Sep 5, 2014

Up one Level

Checks and Pinned Pieces (Bitboards)

GerdIsenberg — Wed, 14 Aug 2013 19:33:50 GMT

Opposite Ray-Directions

See also

Forum Posts

What links here?

Home * Board Representation * Bitboards * Checks and Pinned Pieces

This is about whether the king is in check. If so, one likely uses a specialized check evasion move generator. One may also trigger search extensions - based on the king is in check - or based on the check evasion move generator only reports one valid move. Related to determining discovered check is to look for absolute pins.

Checks

Whether the king is in check may be determined on the fly by looking up attacks to the king square - or based on the last move made by the other, probably checking side. Another option is to determine check giving moves already at generation time, and to flag moves accordantly.

On the Fly

Whether a king is in check can be determined by the attacked-routine mentioned in Square Attacked By. We pass the square of the king and opposite color for the potential attackers.

If one needs the set of attackers, either empty, single or double populated - one likely better relies on a specialized attacksTo-routine for each side, e.g. as member of the standard bitboard board-definition:

U64 CBoard::attacksToKing(enumSquare squareOfKing, enumColor colorOfKing) {
   U64 opPawns, opKnights, opRQ, opBQ;
   opPawns     = pieceBB[nBlackPawn   - colorOfKing];
   opKnights   = pieceBB[nBlackKnight - colorOfKing];
   opRQ = opBQ = pieceBB[nBlackQueen  - colorOfKing];
   opRQ       |= pieceBB[nBlackRook   - colorOfKing];
   opBQ       |= pieceBB[nBlackBishop - colorOfKing];
   return (arrPawnAttacks[colorOfKing][squareOfKing] & opPawns)
        | (arrKnightAttacks[squareOfKing]            & opKnights)
        | (bishopAttacks (occupiedBB, squareOfKing)  & opBQ)
        | (rookAttacks   (occupiedBB, squareOfKing)  & opRQ)
        ;
}

By Move

Another idea is to determine the check inside the search-routine by the last move done by the opponent. It might be a direct or discovered check - or in case of double check, both. With bitboards the possible savings to determine checks by last move seems negligible - and one probably better relies on the branch-less on the fly solution, since we may reuse the rook-wise and bishop-wise attacks for other purposes - like determining absolute pinned pieces, kingsafety-evaluation, and/or whether the opponent side threatens checks or discovered checks.

Direct Check

For the direct check we may use the routine mentioned in Square Attacked By:

if ( isAttacked(squareOfKing, move.to, move.piece(), occupiedBB) ) -> direct check

Discovered Check

One solution is to determine the direction between the from-square and the king square (e.g. by 0x88 difference). If both squares share a common line, one calls an appropriate sliding ray- or line-attack getter with king square and occupancy, to look whether this set intersects the possible opponing sliders of that ray. One also has to prove, whether a possible true result was not caused by a direct check of a sliding capture.

Absolute Pins

To detect absolute pins is necessary for legal move generation and may be considered in evaluation. While there are different approaches, the most common for programs based on single sliding piece attacks rather than direction wise set-wise attack getter, relies on the xrayRookAttacks or xrayBishopAttacks routines - called with square of own king and own pieces as blockers. An in-between lookup determines the set of pinned pieces while traversing the pinning pieces.

pinned = 0;
pinner = xrayRookAttacks(occupiedBB, ownPieces, squareOfKing) & opRQ;
while ( pinner ) {
   int sq  = bitScanForward(pinner);
   pinned |= obstructed(sq, squareOfKing) & ownPieces;
   pinner &= pinner - 1;
}
pinner = xrayBishopAttacks(occupiedBB, ownPieces, squareOfKing) & opBQ;
while ( pinner ) {
   int sq  = bitScanForward(pinner);
   pinned |= obstructed(sq, squareOfKing) & ownPieces;
   pinner &= pinner - 1;
}

Opposite Ray-Directions

Another idea to determine absolute pins as well as distant check block-targets, or possible discovered check origins, is to apply disjoint direction-wise attacks, as demonstrated in the DirGolem proposal, where this technique is used for all eight ray-dirctions. The intersection of direction attacks of potential pinning sliding pieces with the opposite ray-direction attacks of the king treated as sliding super piece, gains enough information if further intersected by empty squares, own, or opponent pieces. For instance as illustrated with a black rook and white king on the same rank, with no, one and two pieces inbetween:

No obstruction, king in check. In-between intersection consists of empty squares as target set to block the distant check:

     . r . . . . K .     
r->  . . 1 1 1 1 1 .      
<-K  . 1 1 1 1 1 . .
&    . . 1 1 1 1 . .

One piece in-between. Intersection leaves a pinned piece if of king color, otherwise a possible discovered checker:

     . r . . x . K .  
r->  . . 1 1 1 . . .             
<-K  . . . . 1 1 . .
&    . . . . 1 . . .

Two (or more) pieces in-between. Intersection is null:

      . r . x x . K .  
r->   . . 1 1 . . . .
<-K   . . . . 1 1 . .
&     . . . . . . . .

Forum Posts

Fast check detection in bitboard engine by Jean-Francois Romang, CCC, December 10, 2003
Bitboards and inCheck by Andreas Guettinger, Winboard Forum, January 03, 2007
Bitboard of Pinned Pieces by Grant Osborne, CCC, July 24, 2008
Check detection and move generation using bitboards by Lasse Hansen, CCC, December 06, 2011

What links here?

Page	Date Edited
Andreas Guettinger	Aug 14, 2013
Bitboards	Nov 14, 2017
Check	Feb 1, 2018
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
DirGolem	Jun 5, 2016
Discovered Check	Feb 1, 2018
Double Check	Apr 4, 2013
Intersection Squares	Oct 4, 2014
Mate at a Glance	Sep 24, 2014
Pin	Mar 7, 2017
Square Attacked By	Jan 20, 2018
Tactics	Jan 12, 2018

Up one Level

Classical Approach

GerdIsenberg — Sun, 28 Jan 2018 18:03:50 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Classical Approach

The classical approach to generate sliding piece attacks was probably first used by Chess and Kaissa.

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

Ray Attacks

The classical approach works ray-wise and uses pre-calculated ray-attacks for each of the eight ray-directions and each of the 64 squares. It has to distinguish between positive and negative directions, because it has to bitscan the ray-attack intersection with the occupancy in different orders. That usually don't cares for getting line- or piece attacks, since one likely unrolls all directions needed for a particular line or piece - otherwise one may rely on a generalized bitscan.

We rely on the compass rose to enumerate ray-directions:

  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa

Positive Rays

Attacks of Positive Ray-Directions:

East (+1)           North (+8)           NorthEast (+9)      NorthWest (+7)
. . . . . . . .     . . . 1 . . . .      . . . . . . . 1     . . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . . 1 .     1 . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . 1 . .     . 1 . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . 1 . . .     . . 1 . . . . .
. . . R 1 1 1 1     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .

Conditional

The first step gets the ray-attack on the otherwise empty board. Potential blockers are then determined by intersection with the occupancy, the set of all pieces. The first blocker, if any, is the least significant one-bit of the intersection. A bitscan forward determines the square of the first blocker, to reset it's ray-bits from the attack set. For instance a bishop on g2:

occupied         &  NorthWest(g2)       {a8, c6}
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 . 1 1     . . . . . . . .     . . . . . . . .
 
                    xor NorthWest(c6 = bitscanForward{a8,c6}
                    1 . . . . . . .
                    . 1 . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
 
                    =  final northWest Attacks
                    . . . . . . . .
                    . . . . . . . .
                    . . 1 . . . . .
                    . . . 1 . . . .
                    . . . . 1 . . .
                    . . . . . 1 . .
                    . . . . . . . .
                    . . . . . . . .

U64 rayAttacks[8][64];
 
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   if ( blocker ) {
      square = bitScanForward(blocker);
      attacks ^= rayAttacks[dir8][square];
   }
   return attacks;
}

Branchless

Branches are evil with todays super pipelined processors. Even if branch-prediction heuristics become smarter, branch-less solutions allow better scheduling and parallel speedup of independent instruction chains, like processing several directions.

Considering todays fast x86-64 bsf-instruction of Core 2 or K10, a branch-less solution may be worth a try. Due to the fact the occupancy of the outer squares doesn't affect the attack set, setting the most significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.

U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
   U64 attacks    = rayAttacks[dir8][square];
   U64 blocker    =  attacks & occupied;
   _BitScanForward64 (&square, blocker | C64(0x8000000000000000));
   return attacks ^ rayAttacks[dir8][square];
}

Negative Rays

Attacks of Negative Ray-Directions:

West (-1)           South (-8)           SouthWest (-9)      SouthEast (-7)
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
1 1 1 R . . . .     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . 1 . . . .      . . 1 . . . . .     . . . . 1 . . .
. . . . . . . .     . . . 1 . . . .      . 1 . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . 1 . . . .      1 . . . . . . .     . . . . . . 1 .

Conditional

Works the same way, but needs reverse bitscan to find the first blocking piece, if any.

U64 getNegativeRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   if ( blocker ) {
      square = bitScanReverse(blocker);
      attacks ^= rayAttacks[dir8][square];
   }
   return attacks;
}

Branchless

The branch-less solution with a fast x86-64 bsr-instruction allows better scheduling and parallel speedup of independent instruction chains, like processing several directions. Setting the least significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.

U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
   U64 attacks    = rayAttacks[dir8][square];
   U64 blocker    =  attacks & occupied;
   _BitScanReverse64 (&square, blocker | 1);
   return attacks ^ rayAttacks[dir8][square];
}

Generalized

The idea of the generalized bitscan may be used to share the same code for all directions. The implementation of isNegative(dir8), a macro or inline-function, depends on the definition or enumeration of the directions and is likely a compare or test instruction.

Conditional

The conditional by a good predictable branch on blocker is favorable - specially for slow bitscans with some chance to skip it, e.g. in endings.

U64 getRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   if ( blocker ) {
      square = bitScan(blocker, isNegative(dir8));
      attacks ^= rayAttacks[dir8][square];
   }
   return attacks;
}

Branchless

The branch-less routine provides a dirMask as universal set for negative rays and the empty set for positive rays, to implement the generalized bitscan. The dirBit-or ensures to scan at least outer square with empty ray sets.

U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
   U64 attacks    = rayAttacks[dir8][square];
   U64 blocker    =  attacks & occupied;
   blocker       &= -blocker | dirMask[dir8];
   blocker       |=            dirBit [dir8]
   _BitScanReverse64 (&square, blocker | dirBit[dir8]);
   return attacks ^ rayAttacks[dir8][square];
}

Zero Count

If available, Leading- or Trailing Zero Count instructions may be used instead of bitscan for another branch-less solution of the classical attack getter. Since they leave 64 for empty sets, it needs to make the ray attack arrays one greater to allow index by 64 which contains an empty set - or one needs to map 64 to 63 for positive directions.

U64 rayAttacks[8][65];
 
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   int firstBlockingSquare = trailingZeroCount(blocker);
   attacks ^= rayAttacks[dir8][firstBlockingSquare];
   return attacks;
}

LeadingZeroCount instead of bitscanReverse may be done similarly, considering the reversed order.

Line Attacks

As mentioned, line attacks are the union of positive and opposite negative ray-directions - since they are disjoint one may also use 'xor' or 'add':

U64 diagonalAttacks(U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, noEa, sq)
       | getNegativeRayAttacks(occ, soWe, sq); // ^ +
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, noWe, sq)
       | getNegativeRayAttacks(occ, soEa, sq); // ^ +
}
 
U64 fileAttacks (U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, nort, sq)
       | getNegativeRayAttacks(occ, sout, sq); // ^ +
}
 
U64 rankAttacks (U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, east, sq)
       | getNegativeRayAttacks(occ, west, sq); // ^ +
}

Piece Attacks

Union of Line Attacks

Of course piece attacks are the union of the line attacks:

U64 rookAttacks (U64 occ, enumSquare sq) {
  return fileAttacks(occ, sq)
       | rankAttacks(occ, sq); // ^ +
}
 
U64 bishopAttacks (U64 occ, enumSquare sq) {
  return diagonalAttacks(occ, sq)
       | antiDiagAttacks(occ, sq); // ^ +
}
 
U64 queenAttacks (U64 occ, enumSquare sq) {
  return rookAttacks  (occ, sq)
       | bishopAttacks(occ, sq); // ^ +
}

In one Run

As mentioned by Robert Hyatt ^[1], instead of fetching four ray-attacks on the otherwise empty board, one may already use the rook- or bishop attacks to reset outer squares from that union set.

A further improvement was suggested by Michael Sherwin ^[2], to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.

struct {
  U64 bitsN;  // bits North, including MSB (bit 63)
  U64 bitsE;  // bits East, including MSB
  U64 bitsS;  // bits South, including LSB (bit 0 == 1)
  U64 bitsW;  // bits West, including LSB 
} CACHE_ALIGN rayWstop[64]; 
 
U64 attacksEmpty[64];
U64 rayN[64];
U64 rayE[64];
U64 rayS[64];
U64 rayW[64];
 
U64 rookAttacks(U64 occ, unsigned int sq) {
   unsigned long ulN, ulE, ulS, ulW;
   occ |= C64(0x8000000000000001);
   _BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);
   _BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);
   _BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);
   _BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);
   return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];
}

Publications

Stuart Cracraft (1984). Bitmap move generation in Chess. ICCA Journal, Vol. 7, No. 3, pp. 146–153
Fridel Fainshtein (2006). An Orthodox k-Move Problem-Composer for Chess Directmates. M.Sc. thesis, Bar-Ilan University, pdf, Appendix D - 64-bit Representation, pp. 105
Fridel Fainshtein, Yaakov HaCohen-Kerner (2006). A Chess Composer of Two-Move Mate Problems. ICGA Journal, Vol. 29, No. 1, pdf, Appendix E: 64-bit representation

Forum Posts

Re: Thinker output by Robert Hyatt, CCC, March 25, 2009
Re: Yet another bitboard attack generator by Robert Hyatt, CCC, October 28, 2009
Modified old 64 bit attack getter by Michael Sherwin, CCC, December 06, 2009

References

^ Re: Yet another bitboard attack generator by Robert Hyatt, CCC, October 28, 2009
^ Modified old 64 bit attack getter by Michael Sherwin, CCC, December 06, 2009

What links here?

Page	Date Edited
Andscacs	Jan 16, 2018
Bitfoot	Sep 8, 2015
BitScan	Sep 10, 2017
Blockers and Beyond	Mar 21, 2014
Classical Approach	Jan 28, 2018
DirGolem	Jun 5, 2016
Fridel Fainshtein	Oct 8, 2014
Hiding the Implementation	Feb 3, 2011
Pieces versus Directions	Oct 6, 2016
SEE - The Swap Algorithm	Jun 5, 2017
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Teki	Mar 29, 2018
Tunguska	Sep 16, 2017
Yaakov HaCohen-Kerner	Aug 23, 2014

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

Defended Pawns (Bitboards)

GerdIsenberg — Fri, 27 Feb 2015 14:46:51 GMT

Defended

Defenders

Defended Defenders

Not Defended Defenders

Not Defending Defended

Forum Posts

What links here?

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Defended Pawns

Working in the bitboard centric world to determine pawn related pattern set-wise.

Each pawn, member of the own pawn attack set is obviously defended by a pawn, thus likely not a winning capture target for opponent pieces (except pawns). If a defended pawn is open, opponent rooks on half-open files bang one's head against a brick wall.

Defended

Again, it is advantageous to keep disjoint east-west attack sets for a unique 1:1 source-target relationship. On demand we can use the union or intersection on the fly. Note that attack direction is related to the target square. East attack is from south/north-west to north/south-east

white pawns         defended            defended
                    from west ->        from east <-
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . 1 . . .     . . . . . . . .
. . . 1 . . 1 .     . . . 1 . . . .     . . . . . . 1 .
. . 1 . . . . 1     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

U64 wPawnDefendedFromWest(U64 wpawns) {
   return wpawns & wPawnEastAttacks(wpawns);
}
 
U64 wPawnDefendedFromEast(U64 wpawns) {
   return wpawns & wPawnWestAttacks(wpawns);
}

Defenders

To get the set of defenders on the fly, we use the intersection of white pawns with it's "black" attacks:

white pawns         defenders           defenders
                    from west           from east
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . 1 . . 1 .     . . . 1 . . . .     . . . . . . . .
. . 1 . . . . 1     . . 1 . . . . .     . . . . . . . 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

U64 wPawnDefendersFromWest(U64 wpawns) {
   return wpawns & bPawnWestAttacks(wpawns);
}
 
U64 wPawnDefendersFromEast(U64 wpawns) {
   return wpawns & bPawnEastAttacks(wpawns);
}

Otherwise, if the set of defenders was already determined (or vice versa), we can already take advantage of the unique target/source relation ship:

wPawnDefendersFromWest = wPawnDefendedFromWest >> 9;
wPawnDefendersFromEast = wPawnDefendedFromEast >> 7;

Defended Defenders

Defended defenders already are the inner pawns of a at least triple-chain, the d5 pawn for instance:

white pawns         defended            defended
                    from west           from east
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . 1 . . .     . . . . . . . .
. . . 1 . . 1 .     . . . 1 . . . .     . . . . . . 1 .
. . 1 . . . . 1     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
white pawns         defenders           defenders
                    from west           from east
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . 1 . . 1 .     . . . 1 . . . .     . . . . . . . .
. . 1 . . . . 1     . . 1 . . . . .     . . . . . . . 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                    defenders and       defenders and
white pawns         defended            defended
                    from west           from east
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . 1 . . 1 .     . . . 1 . . . .     . . . . . . . .
. . 1 . . . . 1     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

Not Defended Defenders

Not defended defenders are the base of a chain - target of opponent attacks:

                    not defended        not defended
white pawns         defenders           defenders
                    from west           from east
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . 1 . . 1 .     . . . . . . . .     . . . . . . . .
. . 1 . . . . 1     . . 1 . . . . .     . . . . . . . 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

Not Defending Defended

Defended pawns not defending other pawns are likely the peak of a chain.

                    not defending       not defending
white pawns         defended            defended
                    from west           from east
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . 1 . . .     . . . . . . . .
. . . 1 . . 1 .     . . . . . . . .     . . . . . . 1 .
. . 1 . . . . 1     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

Forum Posts

pattern coding in bitboards by Pawel Koziol, CCC, February 26, 2015 » Pawn chain

What links here?

Page	Date Edited
More Links
Connected Passed Pawns	Mar 27, 2015
Dartmouth CP	Jan 19, 2018
Defended Pawns (Bitboards)	Feb 27, 2015
Demolito	Mar 1, 2018
Gk	Oct 9, 2017
Pawel Koziol	Dec 17, 2017
Pawn chain	Jan 17, 2018
Pawn Levers (Bitboards)	Nov 11, 2017
Pawn Pattern and Properties	Nov 11, 2017
Protected Passed Pawn	Jun 7, 2012

Up one Level

Design Principles

GerdIsenberg — Wed, 17 Jan 2018 18:50:12 GMT

Home * Board Representation * Bitboards * Design Principles

By Steffan Westcott ^[1]:

I should add that these techniques (Kogge-Stone) are designed to take advantage of the parallel nature of bitboards, in that they consider the entire board. Here, routines like RookMovesUp() will calculate the upward rook moves of all friendly rooks.

In general, I first identify a (bit) pattern of interest, then devise methods for recognising all instances of that pattern on the board. Pattern instances are counted as late as possible, if at all. The complexity of the patterns varies greatly. Simple ones are like OpenFiles(), UnmovedRooks(), PawnAttacks(), PawnRams(), PawnDuos(), KingIsUpRight(). Medium complexity are ones like ConnectedRooks(), RooksCanCastle(), OnKingDiagonal(), NearKingDiagonal(), OutPost(). Complex examples are Fortress(), PawnMass(), PawnStorm(), BackwardPawns(), MaterialSignature(), WeakSquareControl(), StrongSquareControl(), SpaceBehindPawnFront(), StrongKnightOutposts(), StrongFianchettoedBishops(), WeakWhiteSquares(), KingShelter(), GamePhase().

Often the more complex patterns are combinations of the simpler ones. In fact, the chess position itself can be viewed as composed of 'primitive' or 'atomic' patterns (bitboards). Most of the simpler patterns are returned as bitboards, where set bits indicate a (bit) pattern match. This is fine where simple square-centric patterns are sought, and a yes/no for each square is sufficient.

Complex patterns like KingShelter() and GamePhase() are really functions which classify (group together) general patterns spread across the whole board, eg. KingShelter() classifies the pawn structure near the king (matches against a large pattern set), MaterialSignature() returns things like BNbn to classify the material balance.

Just considering the simple patterns, if your engine deals with pattern instances in a serial fashion (strictly one at a time), the algorithm requirements are sufficiently different that an alternative may be better eg. rotated bitboard table lookups, or perhaps even a different board representation altogether. To my mind, the major reason to use bitboards in the first place is to find many pattern instances quickly. In summary, I would advise that my algorithms are no magic bullet - They are better judged in the wider context of your engine design and target architecture.

Rererences

^ Bitboard algorithm design principles by Steffan Westcott, CCC, October 23, 2002

What links here?

Page	Date Edited
Bitboards	Nov 14, 2017
Chunking	Jun 12, 2017
Design Principles	Jan 17, 2018
Kogge-Stone Algorithm	Sep 17, 2016
Pattern Recognition	Sep 8, 2017
Steffan Westcott	Jan 21, 2014

Up one Level

DirGolem

GerdIsenberg — Sun, 05 Jun 2016 18:31:50 GMT

Home * Board Representation * Move Generation * DirGolem

		DirGolem, Direction-wise Generation of Legal Moves, is best done with vectors of bitboards applying AltiVec, SSE2, AVX2 or similar SIMD architectures with appropriate register sets. Legal moves are stored as target-bitboards for all 16 move directions as a kind of unsorted move list inside the state of a node. That are four orthogonal directions with rook-, queen- and king-moves including castling and vertical pawn-pushes, four diagonal directions with bishop-, queen- and king-moves and pawn-captures including en passant, and eight knight directions. Each target square of each direction set has an unique one-to-one relation to it's source square.
The Golem ^[1]

Generating White Moves

Prospect

To get the idea, the following description with scalar C++ code intended as pseudo code, is a rough translation of HansDamf's intrinsic SSE2 code by Gerd Isenberg. It assumes White to move within a color flipper approach. More information for a set-wise SEE, determining check giving moves including discovered checks, etc. may be collected and considered. There are zillions of implementation nuances to utilize up to 16 128-bit XMM-, 16 256-bit YMM (AVX2), or even AVX-512 32 512-bit ZMM-SIMD registers ^[2]. The generation is completely branch-less, does not use huge lookup tables, and is intended to hide the latency of a prefetched TT probe. However, picking any moves or move proposals like hash- or killer moves from that list is more expensive and is typically done by a finite state machine to ensure proper move ordering considering MVV-LVA, hanging pieces, etc., as mentioned in pieces versus directions.

Basics

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

Move Target Sets

To determine white absolutely pinned pieces and squares attacked by black pieces, pawns, and king, taboo for the white king, black attacks are generated in a first phase. Those attacks are also utilized to detect whether the own king is in check. Aggregated collected information is then used in a second phase of legal move target generation.

Black Attacks

Sliders & Super King

First, all black sliding attacks are generated by Dumb7- or Kogge-Stone fill, unrolled for all eight ray directions, to aggregate them into a white king taboo bitboard, and to determine and keep line-wise in-between bitboards by intersection with opposite ray-direction attacks of the white king as sliding super piece, best generated by the classical approach, or alternatively along with the sliding pieces itself as additional SIMD data element processing two opponent fill direction in one run.

The occupancy for the black sliding attacks has the white king excluded, so that in case of check by a sliding piece the king is x-rayed to later avoid king moves to otherwise non attacked squares. The in-between sets intersected with own pieces leave pinned pieces, but are also handy to determine an interposing block target set in case of distant sliding checks. In total, seven bitboards are processed as used in the second part of the routine, four line-wise in-between sets, orthogonal and diagonal white king super piece attacks to later determine a possible sliding checking piece, and the aggregated black attacks.

  U64 horInbetween, verInbetween, diaInbetween, antInbetween;   
  U64 wKSuperAttacksOrth, wKSuperAttacksDia , bAnyAttacks;

Intended members associated with a position object have a m_-prefix, scratch or register variables an underscore:

  /* black rooks and queens west */
  _bAttacks = westAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks         = _bAttacks;
  _wKSuperAttacks     = slidingRayEastAttacks(m_wKsq, m_occ);
  wKSuperAttacksOrth  = _wKSuperAttacks;
  horInbetween        = _bAttacks & _wKSuperAttacks;
  /* black rooks and queens east */
  _bAttacks = eastAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRayWestAttacks(m_wKsq, m_occ);
  wKSuperAttacksOrth |= _wKSuperAttacks;
  horInbetween       |= _bAttacks & _wKSuperAttacks;
  /* black rooks and queens north */
  _bAttacks = nortAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRaySoutAttacks(m_wKsq, m_occ);
  wKSuperAttacksOrth |= _wKSuperAttacks;
  verInbetween        = _bAttacks & _wKSuperAttacks;
  /* black rooks and queens south */
  _bAttacks = soutAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRayNortAttacks(m_wKsq, m_occ);
  wKSuperAttacksOrth |= _wKSuperAttacks;
  verInbetween       |= _bAttacks & _wKSuperAttacks;
 
  /* black bishops and queens north east */
  _bAttacks = noEaAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRaySoWeAttacks(m_wKsq, m_occ);
  wKSuperAttacksDia   = _wKSuperAttacks;
  diaInbetween        = _bAttacks & _wKSuperAttacks;
  /* black bishops and queens south west */
  _bAttacks = soWeAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRayNoEaAttacks(m_wKsq, m_occ);
  wKSuperAttacksDia  |= _wKSuperAttacks;
  diaInbetween       |= _bAttacks & _wKSuperAttacks;
  /* black bishops and queens north west */
  _bAttacks = noWeAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRaySoEaAttacks(m_wKsq, m_occ);
  wKSuperAttacksDia  |= _wKSuperAttacks;
  antInbetween        = _bAttacks & _wKSuperAttacks;
  /* black bishops and queens south east */
  _bAttacks = soEaAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
  bAnyAttacks        |= _bAttacks;
  _wKSuperAttacks     = slidingRayNoWeAttacks(m_wKsq, m_occ);
  wKSuperAttacksDia  |= _wKSuperAttacks;
  antInbetween       |= _bAttacks & _wKSuperAttacks;

None Sliding Pieces

Black pawn- and knight- attacks are best determined by disjoint direction-wise steps and the multiple knight attacks routine. Black king attacks may be determined by lookup or calculation:

  /* black knight attacks */
  bAnyAttacks  |= _knightAttacks  (m_bKnights);
  /* black pawn attacks */
  bAnyAttacks |= _bPawnEastAttacks(m_bPawns);
  bAnyAttacks |= _bPawnWestAttacks(m_bPawns);
  /* black king attacks */
  bAnyAttacks |= _kingAttacks(m_bKbb);

Generating White Moves

Now, with all black attacks and black sliding vs white king in-between sets processed, one generates all legal white moves into 16 move-target bitboards.

In Check?

To make in check or double check handling branch-less, a target mask for all non king moves is calculated, which is needed anyway to remove own white pieces from the attack sets. In case of check it only contains the check giving piece as capture target - distant sliding checks include the in-between set intersected with empty squares as target set for blocking the check. The rare case of double check is considered by a mask (_nullIfDblCheck) computed from the set of check giving pieces - which leaves empty if population greater one and the universe (~empty) otherwise. Note that the ones' decrement of any single populated bitboard is always positive and leaves the empty set if shifted right 63 arithmetically:

  U64 allInbetween = horInbetween | verInbetween | diaInbetween | antInbetween;
  _blocks      =  allInbetween & ~m_occ; /* in case of distant check */
  _checkFrom   = (wKSuperAttacksOrth    & (m_bRooks  | m_bQueens) )
               | (wKSuperAttacksDia     & (m_bBishop | m_bQueens) )
               | (knightAttacks(m_wKbb) &  m_bKnights )
               | (wPawnAttacks (m_wKbb) &  m_bPawns )
               ;
  I64 _nullIfcheck    = ( (I64)( bAnyAttacks & m_wKbb ) - 1) >> 63; /* signed shifts */
  I64 _nullIfDblCheck = ( (I64)( checkFrom & (checkFrom-1) ) - 1) >> 63; 
 
  _checkTo     = _checkFrom | _blocks  | _nullIfcheck;
  targetMask   = ~m_wPieces & _checkTo & _nullIfDblCheck;

Sliding Pieces

Moves by white sliding pieces are computed with eight Dumb7 or Kogge-Stone fills. Pinned sliders are considered partial pinned to move along the pinned direction:

  /* horizontal rook and queen moves */
  _sliders = (m_wRooks | m_wQueens) & ~(allInbetween ^ horInbetween);
  m_moveTargets[eWest] = westAttacks (_sliders, m_occ) & targetMask;
  m_moveTargets[eEast] = eastAttacks (_sliders, m_occ) & targetMask;
  /* vertical rook and queen moves*/
  _sliders = (m_wRooks | m_wQueens) & ~(allInbetween ^ verInbetween);
  m_moveTargets[eNort] = nortAttacks (_sliders, m_occ) & targetMask;
  m_moveTargets[eSout] = soutAttacks (_sliders, m_occ) & targetMask;
  /* diagonal bishop and queen moves */
  _sliders = (m_wBishops | m_wQueens) & ~(allInbetween ^ diaInbetween);
  m_moveTargets[eNoEa] = noEaAttacks (_sliders, m_occ) & targetMask;
  m_moveTargets[eSoWe] = soWeAttacks (_sliders, m_occ) & targetMask;
  /* antidiagonal bishop and queen moves */
  _sliders = (m_wBishops | m_wQueens) & ~(allInbetween ^ antInbetween);
  m_moveTargets[eNoWe] = noWeAttacks (_sliders, m_occ) & targetMask;
  m_moveTargets[eSoEa] = soEaAttacks (_sliders, m_occ) & targetMask;

None Sliding Pieces

Knight moves with their disjoint unique directions are generated by eight appropriate direction shifts with all white knights not pinned, using the same targetMask considering in check. Pawn captures and Pawn pushes also consider partial pins. A given en passant target square implies a strictly legal move, as already secured while making the triggering double pawn push.

Finally king move targets are generated by eight one step direction shifts, masking off target squares occupied by own pieces, or attacked by black, including x-rays through the white king in case of check by a sliding piece. Castling is left to the ambitious reader. In orthodox chess, west or east castling can simply distinguished from ordinal king moves due to the double king step, but requires some more tinkering in Chess960.

  /* knight moves */
  _knights = m_wKnights & ~allInbetween;
  m_moveTargets[eNoNoEa] = noNoEa(_knights) & targetMask; 
  m_moveTargets[eNoEaEa] = noEaEa(_knights) & targetMask; 
  m_moveTargets[eSoEaEa] = soEaEa(_knights) & targetMask; 
  m_moveTargets[eSoSoEa] = soSoEa(_knights) & targetMask; 
  m_moveTargets[eNoNoWe] = noNoWe(_knights) & targetMask; 
  m_moveTargets[eNoWeWe] = noWeWe(_knights) & targetMask; 
  m_moveTargets[eSoWeWe] = soWeWe(_knights) & targetMask; 
  m_moveTargets[eSoSoWe] = soSoWe(_knights) & targetMask; 
  /* pawn captures and en passant */
  _targets = ( m_bPieces & targetMask) | (C64(1) << m_epTarget);
  _pawns   = m_wPans & ~(allInbetween ^ diaInbetween);
  m_moveTargets[eNoEa] |=  noEaOne (_pawns) & _targets ;
  _pawns   = m_wPans & ~(allInbetween ^ antInbetween);
  m_moveTargets[eNoWe] |= noWeOne(_pawns) & _targets;
  /* pawn pushes ... */
  _pawns   = m_wPans  & ~(allInbetween ^ verInbetween);
  _pawnPushs = nortOne (_pawns) & ~m_occ;
  m_moveTargets[eNort] |= _pawnPushs & targetMask;
  /* and double pushs */
  _rank4 = C64(0x00000000FF000000);
  m_moveTargets[eNort] |= nortOne (_pawnPushs) & ~m_occ & targetMask & _rank4;
  /* king moves */
  targetMask = ~(m_wPieces | bAnyAttacks);
  m_moveTargets[eWest] |= westOne (m_wKbb) & targetMask;
  m_moveTargets[eEast] |= eastOne (m_wKbb) & targetMask;
  m_moveTargets[eNort] |= nortOne (m_wKbb) & targetMask;
  m_moveTargets[eSout] |= soutOne (m_wKbb) & targetMask;
  m_moveTargets[eNoEa] |= noEaOne (m_wKbb) & targetMask;
  m_moveTargets[eSoWe] |= soWeOne (m_wKbb) & targetMask;
  m_moveTargets[eNoWe] |= noWeOne (m_wKbb) & targetMask;
  m_moveTargets[eSoEa] |= soEaOne (m_wKbb) & targetMask;

Finally

Additionally, all 16 move target bitboards might be aggregated into a union set, so that checkmate and stalemate is indicated by the zero flag for early returns, wasting a TT prefetch. Further, some disjoint and aggregated attack and pinned piece information might be utilized in evaluation, maybe best associated with thread local memory shared by all nodes searched, and allocated at the bottom of the stack referred by a (this) pointer, with the limited validity from generation until evaluation or the first (null) move is deepened.

Forum Posts

Is there such a thing as branchless move generation? by John Hamlen, CCC, June 07, 2012

External Links

References

^ The Golem: How He Came Into the World, from Wikipedia
^ AVX-512 instructions | Intel® Developer Zone, by James Reinders, July 23, 2013

What links here?

Page	Date Edited
AltiVec	Jun 7, 2016
Avoiding Branches	Dec 16, 2016
AVX2	Aug 8, 2017
Bitboards	Nov 14, 2017
Check	Feb 1, 2018
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
DirGolem	Jun 5, 2016
Golem	May 18, 2017
HansDamf	Jun 27, 2012
Legal Move	Feb 16, 2017
Move Generation	Jan 29, 2018
Pieces versus Directions	Oct 6, 2016
SSE2	Feb 27, 2018

Up one Level

Dispersion and Distortion

GerdIsenberg — Sat, 11 Nov 2017 09:15:45 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Dispersion and Distortion

		Dispersion and Distortion, Kmoch's terms ^[1] ^[2] for pawn structure weaknesses due to vertical or horizontal splitting caused by captures or advancement. The proposed functions may be used via an additional scaling or indirection, f.i. to index a table with concrete penalties.
Samuel Bak - Luna ^[3]

Dispersion

Dispersion is Kmoch's term for vertical splitting of pawns (most commonly, isolation) caused by captures. Having three or four islands while the opponent has one or two - assuming about the same number of pawns for both sides - may be considered in evaluation. But this is also implicitly done by evaluating double- or triple and isolated or the balance of weak pawns in general. Some arbitrary dispersion measure, intended as evaluation term.

int dispersion(U64 pawns)
{
   BYTE fileset  = (BYTE) soutFill(pawns);
   int  ni = popCount(islandsEastFiles(fileset));
   int  np = popCount(wpawns);
   return abs(3*ni*ni - np);
}
 
BYTE islandsEastFiles(BYTE f) {return f & ((f ^ (f >> 1));}

The higher the worse.

  \  number if islands
   \     1   2   3   4
np  \    3  12  27  48
_____\________________
 1   |   2   -   -   -
 2   |   1  10   -   -
 3   |   0   9  24   -
 4   |   1   8  23  44
 5   |   2   7  22  43
 6   |   3   6  21  42
 7   |   4   5  20  41
 8   |   5   4  19  40

Distortion

Distortion is Kmoch's term for horizontal splitting of pawns caused by advances. One may use something like this based on rearfill, xor and population count to get an idea of distortion. It considers the rank-difference of two file-adjacent pawns (if any) as distortion penalty - the higher the worse. Half-isolated or even isolated pawns contribute a distortion penalty according to the size of their rearfill from 2 to 7 for each empty neighboring file, which discourages advancement of such pawns, interacting with terms considerring (half-) isolated pawns. Alternatively, for a "reverse" distortion penalty to encourage advancement of half-isolanis, one may use frontfill instead with a slightly different semantic is case of doubled pawns.

int wDistortion(U64 wpawns) {
   U64 fill  = wRearFill(wpawns); // wFrontFill
   U64 delta = (fill ^ (fill<<1)) & C64(0xfefefefefefefefe));
   return popCount(delta);
}

High distortion sample:

wpawns              rearFill            rearFill << 1      xor & ~A-File
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . 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 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     . . . . . . . .
 
                                                            26 bits sets

External Links

References

^ Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. Previous ed.: New York: McKay, 1959. ISBN 0-486-26486-6
^ Pawn Power in Chess by Hans Kmoch - Glossary of Terms - Chess Forums - Chess.com
^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota

What links here?

Page	Date Edited
Dispersion and Distortion	Nov 11, 2017
Hans Kmoch	Nov 11, 2017
Pawn Islands (Bitboards)	May 4, 2017
Pawn Pattern and Properties	Nov 11, 2017
Space-Time Tradeoff	Jun 17, 2015
Weak Pawns	Dec 19, 2013

Up one Level

Double and Triple (Bitboards)

GerdIsenberg — Thu, 12 May 2016 19:25:45 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Double and Triple

By Square

Working in the square centric world of the board implies using a square index of one particular pawn, likely from bitboard traversal.

For doubled (twins) or multiple pawns on a file, we simply intersect the file-mask by own-pawns and perform a population count. This symmetrical property appears to be equal for white and black pawns, except for the before- and behind semantic.

wPawnsOnFile = arrFiles[sqOfWhitePawn] & pawnBB[white];
if ( wPawnsOnFile & (wPawnsOnFile-1) ) -> white pawn is a least double pawn
if ( wPawnsOnFile & arrNortRay[sqOfWhitePawns] ) -> white pawn has own pawn ahead
if ( wPawnsOnFile & arrSoutRay[sqOfWhitePawns] ) -> white pawn has own pawn behind

arrFiles[d*]
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .

The arrFiles might be condensed to eight bitboards only, instead of 64 - if we index by

file(sq) == sq & 7

instead of square.

Multiple Pawns

Working in the bitboard centric world to determine pawn related pattern set-wise.

All pawns that are member of the rearspan of all own pawns, have at least one pawn in front on the same file. All pawns that are member of the frontspan of all own pawns, have at least one pawn behind on the same file.

// pawns with at least one pawn in front on the same file
U64 wPawnsBehindOwn(U64 wpawns) {return wpawns & wRearSpans(wpawns);}
 
// pawns with at least one pawn behind on the same file
U64 wPawnsInfrontOwn (U64 wpawns) {return wpawns & wFrontSpans(wpawns);}

Obviously, since each pawn in front of a pawn implies this pawn behind, the number of pawns in front is equal the number of pawns behind.

popCount(wPawnsBehindOwn) == popCount(wPawnsInfrontOwn)

The intersection of both sets implies at least a triple, thus a pawn in front and behind.

U64 wPawnsInfrontAndBehindOwn (U64 wpawns) {
   return wPawnsInfrontOwn(wpawns) &  wPawnsBehindOwn(wpawns);
}

If the intersection is empty on a file, it is a double pawn or a twin.

fileWithAtLeastTriple = fileFill(infrontAndBehindOwn);
rearTwin  = behindOwn  & ~fileWithAtLeastTriple;
frontTwin = infrontOwn & ~fileWithAtLeastTriple;

Forum Posts

Doubled and Backward Pawn Engine "Definitions" by Brian Richardson, CCC, September 07, 2009
Doubled pawns by Stefano Gemma, CCC, May 11, 2016

What links here?

Page	Date Edited
Aegon 1993	Mar 26, 2017
Dispersion and Distortion	Nov 11, 2017
Double and Triple (Bitboards)	May 12, 2016
Doubled Pawn	Mar 27, 2017
Hans Kmoch	Nov 11, 2017
Pawn Pattern and Properties	Nov 11, 2017

Up one Level

Dumb7Fill

GerdIsenberg — Fri, 27 May 2016 08:32:45 GMT

Comparison with Kogge-Stone

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

Dumb7Fill - the obvious, straight forward flood-fill approach works set-wise - seven times one fill-cycle by one step only in one of eight directions. We rely on the compass rose to identify ray-directions.

  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa

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

Occluded Fill

An occluded fill includes the flood generating sliding pieces, but excludes the blocker. It is base of attack fills. One additional direction shift excludes the sliders but includes the blocker.

Seven Fill Cycles

The sliding pieces generate the flood. They were shifted one step in the desired direction and intersected with the set of empty squares, the propagator. The flood aggregates the intersection and the cycle repeats six further times to cover the maximum distance on the chessboard. A blocker, not member of propagator, stops the flood in that particular ray-direction for one sliding piece. Therefor occluded fill contains the initial generator but excludes any blocker.

U64 soutOccl(U64 gen, U64 pro) {
   for (int cycle = 0; cycle < 7; cycle++)
      gen |= pro & (gen >> 8);
   return gen;
}

Fill Loop

Alternatively one may save move-instructions by introducing an explicit flood accumulator, and to probably terminate the loop early if the flood stops:

U64 soutOccl(U64 gen, U64 pro) {
   U64 flood = 0;
   while (gen) {
      flood |= gen;
      gen = (gen >> 8) & pro;
   }
   return flood;
}

Unrolled Loop

To avoid conditional branches and to schedule several directions in parallel, the "real" dumb7fill unrolls the loop:

U64 soutOccl(U64 gen, U64 pro) {
   U64 flood = gen;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |=       (gen >> 8) & pro;
   return flood;
}

Some south fill cycles in slow motion:

flood = gen =
brooks|bqueen       empty
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.fill
 gen = gen >> 8   &  empty           =>  flood
. . . . . . . .      . . . . . . . .     1 . . . . . . .
1 . . . . . . .      1 . . . . . . .     1 . . 1 . . . .
. . . 1 . . . .      . . . 1 . . . .     . . . 1 . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . 1 . .      . . . . . 1 . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
2.fill
 gen = gen >> 8   &  empty               flood  |= ...
. . . . . . . .      . . . . . . . .     1 . . . . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
1 . . . . . . .      1 . . . . . . .     1 . . 1 . . . .
. . . 1 . . . .      . . . 1 . . . .     . . . 1 . . . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . 1 . .      . . . . . 0 . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
3.fill
 gen = gen >> 8   &  empty               flood |= ...
. . . . . . . .      . . . . . . . .     1 . . . . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
1 . . . . . . .      1 . . . . . . .     1 . . 1 . . . .
. . . 1 . . . .      . . . 0 . . . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
 
...
 
6.fill
 gen = gen >> 8  &   empty               flood  |= ...
. . . . . . . .      . . . . . . . .     1 . . . . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . . . 1 . .
. . . . . . . .      . . . . . . . .     1 . . . . 1 . .
1 . . . . . . .      0 . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .

The flood already stopped, the final 7th fill cycles don't change anything.

Attack Fill

To get attacks, one additional direction shift of the occluded fill is necessary to exclude the rooks/queen and include the blocker:

U64 soutAttacks (U64 rooks, U64 empty) {return soutOne(soutOccl(rooks, empty));}

Comparison with Kogge-Stone

To combine the dumb7fill as attack getter, we also can take advantage of outer square occupancy doesn't affect the attack set. We need one fill cycle less, before the final shift. That takes 19 operations. In anticipation to parallel prefix, a Kogge-Stone approach takes 14 instructions, 5 less. Kogge-Stone needs more move-instructions and a temporary register to compute generator as well as propagator, while dumb7fill uses a const propagator:

dumb7fill                                  | Kogge-Stone Algorithm
                                           |
U64 soutAttacks(U64 rooks, U64 empty) {    | U64 soutAttacks(U64 rooks, U64 empty) {
   U64 flood = rooks;                      |    rooks |= empty & (rooks >>  8);
   flood |= rooks = (rooks >> 8) & empty;  |    empty  = empty & (empty >>  8);
   flood |= rooks = (rooks >> 8) & empty;  |    rooks |= empty & (rooks >> 16);
   flood |= rooks = (rooks >> 8) & empty;  |    empty  = empty & (empty >> 16);
   flood |= rooks = (rooks >> 8) & empty;  |    rooks |= empty & (rooks >> 32);
   flood |= rooks = (rooks >> 8) & empty;  |    return            rooks >>  8;
   flood |=         (rooks >> 8) & empty;  | }
   return            flood >> 8;           |
}                                          |
                                           |
in x86/64 assembly                         | in x86/64 assembly
; dumb7fill                                |  ; koggeStone
; rooks rdx                                |  ; rooks rdx
; empty rcx                                |  ; empty rcx
                                           |
  mov   rax, rdx                           |    mov   rax, rdx
                                           |    shr   rax, 8
  shr   rdx, 8                             |    and   rax, rcx
  and   rdx, rcx                           |    or    rdx, rax
  or    rax, rdx                           |
                                           |    mov   rax, rcx
  shr   rdx, 8                             |    shr   rax, 8
  and   rdx, rcx                           |    and   rcx, rax
  or    rax, rdx                           |
                                           |    mov   rax, rdx
  shr   rdx, 8                             |    shr   rax, 16
  and   rdx, rcx                           |    and   rax, rcx
  or    rax, rdx                           |    or    rdx, rax
                                           |
  shr   rdx, 8                             |    mov   rax, rcx
  and   rdx, rcx                           |    shr   rax, 16
  or    rax, rdx                           |    and   rcx, rax
                                           |
  shr   rdx, 8                             |    mov   rax, rdx
  and   rdx, rcx                           |    shr   rax, 32
  or    rax, rdx                           |    and   rax, rcx
                                           |    or    rax, rdx
  shr   rdx, 8                             |
  and   rdx, rcx                           |    shr   rax, 8
  or    rax, rdx                           |
                                           |
  shr   rax, 8                             |
                                           |
   1 move                                  |     5 moves
  19 operations                            |    14 operations
  20 instructions                          |    19 instructions

Thus, dumb7fill is not that bad, specially if processing several directions in parallel, like south and north, all east and all west attacks.

All Directions

U64 soutAttacks(U64 rooks, U64 empty) {
   U64 flood = rooks;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |=         (rooks >> 8) & empty;
   return            flood >> 8;
}
 
U64 nortAttacks(U64 rooks, U64 empty) {
   U64 flood = rooks;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |=         (rooks << 8) & empty;
   return            flood << 8;
}

Horizontal fills need to consider wraps from H-file to A-file and vice versa. Fortunately this can be combined by intersection of ~A-file or ~H-file with the propagator:

U64 eastAttacks(U64 rooks, U64 empty) {
   const U64 notA = C64(0xfefefefefefefefe);
   U64 flood = rooks;
   empty &= notA;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |=         (rooks << 1) & empty;
   return           (flood << 1) & notA ;
}
 
U64 noEaAttacks(U64 bishops, U64 empty) {
   const U64 notA = C64(0xfefefefefefefefe);
   U64 flood = bishops;
   empty &= notA;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |=           (bishops << 9) & empty;
   return               (flood << 9) & notA ;
}
 
U64 soEaAttacks(U64 bishops, U64 empty) {
   const U64 notA = C64(0xfefefefefefefefe);
   U64 flood = bishops;
   empty &= notA;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |=           (bishops >> 7) & empty;
   return               (flood >> 7) & notA ;
}
 
U64 westAttacks(U64 rooks, U64 empty) {
   const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
   U64 flood = rooks;
   empty &= notH;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |=         (rooks >> 1) & empty;
   return           (flood >> 1) & notH ;
}
 
U64 soWeAttacks(U64 bishops, U64 empty) {
   const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
   U64 flood = bishops;
   empty &= notH;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |=           (bishops >> 9) & empty;
   return               (flood >> 9) & notH ;
}
 
U64 noWeAttacks(U64 bishops, U64 empty) {
   const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
   U64 flood = bishops;
   empty &= notH;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |=           (bishops << 7) & empty;
   return               (flood << 7) & notH ;
}

Generalized Rays

Since rotate works like a generalized shift with positive or negative shift amount - since it internally applies a modulo 64 and makes -i = 64-i. We need to clear either the lower or upper bits by intersection with a mask, which might be combined with the wrap-ands for one step. It might be applied to get attacks for both sides with a direction parameter and small lookups for shift amount and wrap-ands - instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.

Loop Version

This is the loop-version:

U64 occludedFill (U64 gen, U64 pro, int dir8) {
   U64 flood = 0;
   if (gen) {
      int r = shift[dir8]; // {+-1,7,8,9}
      pro  &= avoidWrap[dir8];
      do {
         flood |= gen;
         gen = rotateLeft(gen, r) & pro;
      } while (gen);
   }
   return flood;
}
 
U64 shiftOne (U64 b, int dir8) {
   int r = shift[dir8]; // {+-1,7,8,9}
   return rotateLeft(b, r) & avoidWrap[dir8];
}
 
U64 slidingAttacks (U64 sliders, U64 empty, int dir8) {
   U64 fill = occludedFill(slider, empty, dir8)
   return shiftOne(fill, dir8);
}
 
// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
 
U64 avoidWrap[8] =
{
   0xfefefefefefefe00,
   0xfefefefefefefefe,
   0x00fefefefefefefe,
   0x00ffffffffffffff,
   0x007f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f00,
   0xffffffffffffff00,
};

The avoidWrap masks by some arbitrary dir8 enumeration and shift amount:

6 == noWe -> +7     7 == nort -> +8     0 == noEa -> +9
0x7F7F7F7F7F7F7F00  0xFFFFFFFFFFFFFF00  0xFEFEFEFEFEFEFE00
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 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 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
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
5 == west -> -1                         1 == east -> +1
0x7F7F7F7F7F7F7F7F                      0xFEFEFEFEFEFEFEFE
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 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
 
4 == soWe -> -9     3 == sout -> -8     2 == soEa -> -7
0x007F7F7F7F7F7F7F  0x00FFFFFFFFFFFFFF  0x00FEFEFEFEFEFEFE
. . . . . . . .     . . . . . . . .     . . . . . . . .
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 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 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

Unrolled Attacks

The generalized unrolled sliding attack getter:

U64 slidingAttacks (U64 sliders, U64 empty, int dir8) {
   U64 flood = sliders;
   int r = shift[dir8]; // {+-1,7,8,9}
   empty &= avoidWrap[dir8];
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |=         = rotateLeft(sliders , r) & empty;
   return   rotateLeft(flood, r)  &   avoidWrap[dir8];
}

External Links

Weather Report - Seventh Arrow / Umbrellas, 1971, YouTube Video
Joe Zawinul, Wayne Shorter, Miroslav Vitouš, Alphonse Mouzon, Dom Um Romão

What links here?

Page	Date Edited
More Links
AVX2	Aug 8, 2017
DirGolem	Jun 5, 2016
Dumb7Fill	May 27, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Fill Algorithms	Nov 6, 2013
Gaviota	Jan 21, 2018
General Setwise Operations	Feb 25, 2018
Gunnar Andersson	Jun 23, 2011
Influence Quantity of Pieces	Jul 21, 2017
John L. Jerz	Jul 15, 2013
Kogge-Stone Algorithm	Sep 17, 2016
Lachex	Jan 7, 2016
Little Wing	Oct 26, 2017
Mobility	Jan 17, 2018
Othello	Jan 4, 2018
Pieces versus Directions	Oct 6, 2016
Sequential Logic	May 10, 2017
Shifted Bitboards	Jan 9, 2011
SIMD and SWAR Techniques	Jun 27, 2017
Sliding Piece Attacks	May 27, 2016

Up one Level

Duo Trio Quart (Bitboards)

GerdIsenberg — Fri, 18 Aug 2017 17:28:27 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Duo Trio Quart

Pawn-Duo, (Phalanx) ^[1]
two adjacent pawns of the same color on the same rank that mutually cover the other's stop square. A Trio are three horizontal friendly pawns, a Quart four horizontal friendly pawns.

Working in the bitboard centric world to determine pawn related pattern set-wise.

The code snippets rely on shifting bitboards, specially by one step only.

Neighbors

To get pawns with east or west neighbors is simple:

U64 pawnsWithEastNeighbors(U64 pawns) {
   return pawns & westOne (pawns);
}
 
U64 pawnsWithWestNeighbors(U64 pawns) {
   return pawnsWithEastNeighbors(pawns) << 1; // * 2
}

U64 pawnsWithWestNeighbors(U64 pawns) {
   return pawns & eastOne (pawns);
}
 
U64 pawnsWithEastNeighbors(U64 pawns) {
   return pawnsWithWestNeighbors(pawns) >> 1;
}

pawns               pawns with east     pawns with west     pawns with east
                    neighbors           neighbors           and west neighbors
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
1 1 1 . . . . .     1 1 . . . . . .     . 1 1 . . . . .     . 1 . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . 1 1 .     . . . . . 1 . .     . . . . . . 1 .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .

Neighbor Algebra

Pawns with east or west neighbors are at least member of a duo. Pawns with east and west neighbors at least member of a trio. If two neighbors have both east and west neighbors, it is at least a quart.

An exclusive pawn duo is therefor a pawn with one neighbor, while this neighbor has no other neighbor as well.

U64 duo (U64 pawns) {
   U64 withWestNeighbors = pawnsWithWestNeighbors(pawns);
   U64 withEastNeighbors = withWestNeighbors >> 1;
 
   U64 withOneExclusiveNeighbor  = withWestNeighbors ^ withEastNeighbors;
   U64 withExclusiveWestNeighbor = withWestNeighbors & withOneExclusiveNeighbor;
   U64 withExclusiveEastNeighbor = withEastNeighbors & withOneExclusiveNeighbor;
 
   U64 duoWestOne = withEclusiveEastNeighbor & (withEclusiveWestNeighbor >> 1);
   U64 duoEastOne = duoWestOne << 1;
   return duoWestOne | duoEastOne;
}

pawns               pawns with excl.    pawns with excl.    duo
                    east neighbor       west neighbor
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
1 1 1 . . . . .     1 . . . . . . .     . . 1 . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . 1 1 .     . . . . . 1 . .     . . . . . . 1 .     . . . . . 1 1 .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .

Forum Posts

The phalanx concept by Lyudmil Tsvetkov, CCC, May 21, 2014

External Links

Pawn Structure (General) | Page 5 of 5 | Phalanx Formation
Duet from Wikipedia
Phalanx from Wikipedia
Trio from Wikipedia
Kinga Głyk Trio - Walking Baby, VisionInMusica, Terni, March 10, 2017, YouTube Video
Kinga Głyk, Irek Głyk, Rafal Stepien
Quart (disambiguation) from Wikipedia
Panta Rhei plays Bartók's Quarts, 1977, YouTube Video

References

^ Pawn Structure (General) | Page 5 of 5 | Phalanx Formation

What links here?

Page	Date Edited
Backward Pawns (Bitboards)	May 5, 2017
ChessBrainVB	Jun 24, 2017
Connected Passed Pawns	Mar 27, 2015
Dartmouth CP	Jan 19, 2018
Demolito	Mar 1, 2018
Design Principles	Jan 17, 2018
Duo Trio Quart (Bitboards)	Aug 18, 2017
En prise	Oct 11, 2016
GopherCheck	Feb 3, 2017
Hanging pawns	Aug 5, 2015
Hanging Piece	Jan 14, 2017
Hans Kmoch	Nov 11, 2017
Isolated Pawns (Bitboards)	Nov 18, 2012
Kaissa	Apr 9, 2018
Lyudmil Tsvetkov	Mar 28, 2018
Pawn Pattern and Properties	Nov 11, 2017
Pawn Structure	Oct 2, 2017
Pawns Breakthrough	May 4, 2014
Protected Passed Pawn	Jun 7, 2012
Stockfish	Apr 7, 2018

Up one Level

Wikispaces : chessprogramming - items matching description

All Shortest Paths

Table of Contents

The Algorithm

Optimization

External Links

References

What links here?

Attack and Defend Maps

Table of Contents

Maintaining Attacks

Incremental Update

On the Fly

Implementations

Classical Approach

Alternatives

Piece-Sets

Ed's lookup

Direction wise

See also

Forums Posts

1995 ...

2000 ...

2005 ...

2010 ...

References

What links here?

Attack Spans

What links here?

Backward Pawns (Bitboards)

Table of Contents

Backward

Straggler

Telestop Weakness

Dynamic Backwardness

A further Pass

Stops with negative SEE

See also

Publications

Forum Posts

External Links

References

What links here?

Best Magics so far

Table of Contents

Legende

Rook Magics

Bishop Magics

Forum Posts

External Links

What links here?

BikJump

Table of Contents

Java Version

Platforms

History and Future Plans

External Links

What Links Here?

Bitboard Board-Definition

Table of Contents

Classical Board

Structure

Array

Denser Board

See also

Forum Posts

External Links

References

What links here?

Bitboards

Table of Contents

The Board of Sets

Bitboard Basics

General Bitboard Techniques

Pattern and Attacks

Move Generation Issues

Miscellaneous

Defining Bitboards

Bitboard-History

Analysis