Wikispaces : chessprogramming - items matching description

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

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

bitboard mobility Copyright (c) 2003, Gunnar Andersson » Othello, Mobility
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

Fill by Subtraction

GerdIsenberg — Fri, 05 Mar 2010 18:22:13 GMT

Source Code

Comparison with Kogge-Stone

See also

What links here?

Home * Board Representation * Bitboards * Sliding Piece Attacks * Fill by Subtraction

Performing the o^(o-2r) - trick in a SWAR-wise fashion with bytes (ranks), saves some instructions compared to Kogge-Stone.

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

Unfortunately it only works in positive horizontal direction, so the possible savings are marginal, despite even less generalization of handling one out of eight cases with a different code pattern.

Source Code

U64 eastAttacks(U64 rooks, U64 empty) {
   const U64 H     =  0x8080808080808080;
   U64 occInclRook =  rooks | ~empty | H;
   U64 occExclRook = (rooks   &=      ~H)  ^ occInclRook;
   U64 rookAttacks = (occExclRook - rooks) ^ occInclRook;
   return rookAttacks;
}

Even more with vectors of two bitboards and SSE2-instructions.

Comparison with Kogge-Stone

For comparison the Kogge-Stone attack-getter. It gives an idea how to implement a Kogge-Stone Adder with bitwise operations only.

U64 eastAttacks(U64 rooks, U64 empty) {
   empty &= notAFile;
   rooks |= empty & (rooks << 1);
   empty &=         (empty << 1);
   rooks |= empty & (rooks << 2);
   empty &=         (empty << 2);
   rooks |= empty & (rooks << 4);
   return notAFile& (rooks << 1);
}

What links here?

Page	Date Edited
DirGolem	Jun 5, 2016
Fill Algorithms	Nov 6, 2013
Fill by Subtraction	Mar 5, 2010
Kogge-Stone Algorithm	Sep 17, 2016
MMX	Jun 5, 2016
Parallel Prefix Algorithms	Jun 22, 2016
Pieces versus Directions	Oct 6, 2016
Sliding Piece Attacks	May 27, 2016
SSE2	Feb 27, 2018
Subtracting a Rook from a Blocking Piece	Dec 2, 2016

Up one Level

Isolated Pawns (Bitboards)

GerdIsenberg — Sun, 18 Nov 2012 09:53:37 GMT

Isolani by Square

Isolanis and Half-isolanis set-wise

Hanging pawns

What links here?

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

An Isolated Pawn or Isolani has no friendly pawns on adjacent files .

Isolani by Square

To determine whether a pawn is isolated, we simply lookup an array with neighboring file-masks. If the intersection of neighbored files with own pawns is empty, the pawn is isolated. This symmetrical property appears to be equal for white and black pawns.

if ( (arrNeighborFiles[sqOfWhitePawn] & pawnBB[white]) == 0 ) -> pawn is isolated

arrNeighborFiles[d*]
. . 1 . 1 . . .
. . 1 . 1 . . .
. . 1 . 1 . . .
. . 1 . 1 . . .
. . 1 . 1 . . .
. . 1 . 1 . . .
. . 1 . 1 . . .
. . 1 . 1 . . .

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

file(sq) == sq & 7

instead of square.

Isolanis and Half-isolanis set-wise

Isolated pawns are the relative complement of pawns with the union of their own attack fills over the whole file. To keep disjoint pawns with no neighbor on either east or west adjacent files has the advantage of greater versatility. Isolanis are the intersection of them, half-isolanis the exclusive or:

U64 noNeighborOnEastFile (U64 pawns) {
    return pawns & ~westAttackFileFill(pawns);
}
 
U64 noNeighborOnWestFile (U64 pawns) {
    return pawns & ~eastAttackFileFill(pawns);
}
 
U64 isolanis(U64 pawns) {
   return  noNeighborOnEastFile(pawns)
         & noNeighborOnWestFile(pawns);
}
 
U64 halfIsolanis(U64 pawns) {
   return  noNeighborOnEastFile(pawns)
         ^ noNeighborOnWestFile(pawns);
}

Hanging pawns

Hanging pawns are a duo of open and half-isolated pawns.

U64 wHangingPawns(U64 wpawns, U64 bpawns) {
   return wOpenPawns(wpawns, bpawns)
        & halfIsolanis(wpawns) & duo(wpawns);
}

What links here?

Page	Date Edited
Attack Spans	Mar 4, 2010
Backward Pawns (Bitboards)	May 5, 2017
Dispersion and Distortion	Nov 11, 2017
En prise	Oct 11, 2016
Hanging pawns	Aug 5, 2015
Hanging Piece	Jan 14, 2017
Hans Kmoch	Nov 11, 2017
Isolated Pawn	Nov 18, 2012
Isolated Pawns (Bitboards)	Nov 18, 2012
Murka	Nov 11, 2016
Pawn Islands (Bitboards)	May 4, 2017
Pawn Pattern and Properties	Nov 11, 2017
Pawn Spans	Jul 22, 2010
Robocide	May 11, 2016
Weak Pawns	Dec 19, 2013

Up one Level

King Pattern

GerdIsenberg — Fri, 15 Nov 2013 17:23:35 GMT

Home * Board Representation * Bitboards * King Pattern

		King pattern are about king attacks, some king safety issues and pawn endgame related stuff. There is exactly one king per side - the whole game. Not a big issue, but even if white and black kings are member of the standard bitboard definition one may avoid bitscanning whole the time. Even without explicit piece-lists , one may consider to keep the redundant king-squares incrementally updated during make/unmake.
Moore neighborhood ^[1]

Vulnerable on distant Checks

Branchless

SSE4

King and Pawns

Set-wise Rule of the Square

Flood Fill Algorithms

King Attacks

The King attacks all squares in Moore neighborhood, that is squares with a Chebyshev distance of one.

by Lookup

Likely we have a the square-index handy, to access a table of precalculated king-attacks.

U64 arrKingAttacks[64];
 
U64 kingAttacks(enumSquare sq) {return arrKingAttacks[sq];}

For instance a king on g2:

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

by Calculation

To calculate all eight directions, one can actually do some simple parallel prefix stuff. Rather than to do a union of all eight direction-steps, one first applies the horizontal attacks considering file-wraps. Those up to two bits are then shifted up and down, together with the king-bitboard itself, to get all the other direction bits:

U64 kingAttacks(U64 kingSet) {
   U64 attacks = eastOne(kingSet) | westOne(kingSet);
   kingSet    |= attacks;
   attacks    |= nortOne(kingSet) | soutOne(kingSet);
   return attacks;
}

The routine is handy to initialize the kingAttacks arrays:

U64 sqBB = 1;
for (int sq = 0; sq < 64; sq++, sqBB <<= 1)
   arrKingAttacks[sq] = kingAttacks(sqBB);

It must not necessarily called with single-populated bitboards, and is base of king path fill algorithms.

King Safety

King Safety is an important evaluation topic. Some bitboard pattern are about to recognize king safety related features. To evaluate those features is a complete other story.

Pawn-Shield Pattern

During the middlegame, the king is encouraged to hide behind own pawn shields. Beside Considering open and half-open files on king's and adjacent files, one idea is to mask potential pawn shield pattern per wing of the king file - and to hash it to an appropriate index range to access tables with precalculated stuff. This mask might be used for kings on f1-h1 or f1-h2:

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

Vulnerable on distant Checks

Assuming we are aware of all taboo squares of the king. That is the union of own pieces with all opposite attacks, then we can simply calculate a move target set by relative complement of the king attacks.

moveTargets = arrKingAttacks[sq] & ~taboo;

If moveTargets is empty - the king has no move. The king might be vulnerable on distant checks from any sliding piece direction, due to lack of any escape. Otherwise, the king might be vulnerable on distant checks, if escape squares are on one line only - either rank, file, diagonal or anti-diagonal:

if ( moveTargets == 0 )
{
   dirSet = 15; // vulnerable on all lines
}
else
{
   dirSet = 0;
   pattern = moveTargets | sqBBofKing;
   if ( pattern & rankBits[sq] == pattern )
      dirSet =  1; // vulnerable on rank, e.g. base rank
   else if ( pattern & fileBits[sq] == pattern )
      dirSet =  2; // vulnerable on file
   else if ( pattern & diagBits[sq] == pattern )
      dirSet =  4; // vulnerable on diagonal
   else if ( pattern & antiBits[sq] == pattern )
      dirSet =  8; // vulnerable on antidiagonal
}

Branchless

Branchless in C - since boolean compare result is treated 0 or 1 arithmetically:

pattern = moveTargets | sqBBofKing;
dirSet  = ( pattern & rankBits[sq] == pattern ) * 1;
dirSet += ( pattern & fileBits[sq] == pattern ) * 2;
dirSet += ( pattern & diagBits[sq] == pattern ) * 4;
dirSet += ( pattern & antiBits[sq] == pattern ) * 8;

to possibly test later

if ( dirSet ) evaluate and look for possible distant mates

SSE4

Using the SSE4.1 PCMPEQQ Quadword compare for equality instruction via _mm_cmpeq_epi64 intrinsic, following otherwise SSE2 approach might be applied:

struct SKingBits {
    U64 rankBits;
    U64 fileBits;
    U64 diagBits;
    U64 antiBits;
} XMM_ALIGN kingBits[64];
 
int dirSet(U64 pattern, int sq)
{
   static const U64 XMM_ALIGN weights[4] = {
     C64(0x0000000000000001),
     C64(0x0000000000000002),
     C64(0x0000000000000004),
     C64(0x0000000000000008)
   };
   __m128i x0, x1, x2;
   const __m128i* pKB = (__m128i*)(kingBits + sq);
   const __m128i* pW  = (__m128i*) weights;
   x2 = _mm_cvtsi64x_si128 (pattern);
   x2 = _mm_unpacklo_epi64 (x2, x2);
   x0 = _mm_and_si128   (x2, pKB[0]);
   x1 = _mm_and_si128   (x2, pKB[1]);
   x0 = _mm_cmpeq_epi64 (x0, x2);
   x1 = _mm_cmpeq_epi64 (x1, x2);
   x0 = _mm_and_si128   (x0, pW[0]);
   x1 = _mm_and_si128   (x1, pW[1]);
   x0 = _mm_or_si128    (x0, x1);
   x1 = _mm_unpackhi_epi64 (x0, x0);
   x0 = _mm_or_si128    (x0, x1);
   return _mm_cvtsi128_si32(x0);
}

King and Pawns

Some pawn endgame issues. A set-wise rule of the square from king's point of view. Or does a king have a connected path along safe and empty squares to a certain square?

Set-wise Rule of the Square

Assuming a black-king on g5 - white to move. What is the set of squares, where a king can never catch a white passer? Or the inverse, where can passers might be caught, considering the rule of the square? In this inverse case, where passers may be close enough, there are other aspects to consider like two distant passers, or passer supported by own king - here it is only about races between passers and opponent king. It is about a set-wise view, where the distance to promotion is greater or equal than the distance of the king. We need to consider double pushes from the initial rank though.

black king on g5    white passers         double pawn push, need
wtm                 possibly caught       to copy 3rd to 2nd rank
. . . . . . . .      . . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .      . . . . . . . .
. . . . . . K .      . . . 1 1 1 K 1      . . . 1 1 1 K 1
. . . . . . . .      . . 1 1 1 1 1 1      . . 1 1 1 1 1 1
. . . . . . . .      . 1 1 1 1 1 1 1      . 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1      . 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1      1 1 1 1 1 1 1 1

Of course we may even mask off the base ranks since pawns can not exist there - but since we intersect with passers anyway, it don't cares.

We need to consider tempo, if black to move, the area of caught grows accordantly:

black king on g5    white passers
btm                 possibly caught
. . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .
. . . . . K K K      . . . 1 1 1 1 1
. . . . . K K K      . . 1 1 1 1 K 1
. . . . . K K K      . 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1

We can now pre-initialize an array of caught pawn area for each king square, for both black and white king as well as side to move:

U64 arrCaughtableArea[2][2][64];  // [color of king][side to move][square]
 
unCaughtable = whitePassers & ~arrCaughtableArea[black][white][squareOfBlackKing];

How can the array be initialized, how can we calculate it? That is already some special fill approach. For the mentioned black king, wtm case, we use the rank-distance of the black king to the 8th rank.

distance = rank(kingSquare) ^ 7; // 7 - rank
 
. . . . 3 . . .
. . . . 2 . . .
. . . . 1 . . .
. . . . K . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

One solution is first expand the king-set distance (3) times, in east and west direction along the rank:

caughtable = kingBB;
for (i = 0; i < distance; i++)
   caughtable |= westOne(caughtable) | eastOne(caughtable);
 
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . 1 1 1     . . . . 1 1 1 1      . . . 1 1 1 1 1
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .

Now it is about filling south-west and south-east rank(kingSquare) times, which finally results in the desired set of catchable passers. Special handling is required for the doubles pushes ^[2]:

for (i = 0; i < rank(kingSquare)-2; i++)
   caughtable |= soutOne(westOne(caughtable) | caughtable | eastOne(caughtable) );
caughtable |= soutOne(caughtable) | 0xff;
 
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . 1 1 1 1 1     . . . 1 1 1 1 1      . . . 1 1 1 1 1
. . 1 1 1 1 1 1     . . 1 1 1 1 1 1      . . 1 1 1 1 1 1
. . . . . . . .     . 1 1 1 1 1 1 1   |  . 1 1 1 1 1 1 1
. . . . . . . .     . . . . . . . .   |  . 1 1 1 1 1 1 1
. . . . . . . .     . . . . . . . .   v  1 1 1 1 1 1 1 1

To initialize black to move and white king arrays should not that difficult either - and is left to the ambitious reader.

Flood Fill Algorithms

Answering questions like can a king on a1 reach h8 along this path?

. . . . . . 1 T
. . 1 1 1 1 . .
. 1 . . . . . .
. . 1 1 1 1 . .
. . . . . . 1 .
. . . . . . . 1
. . . . . . 1 .
F 1 1 1 1 1 . .

The squaresAreConnected flood-fill ^[3] algorithm was introduced by Steffan Westcott ^[4].

A flood fill algorithm, like the one below, starting at the "from" square and stopping if the fill hits the to" square or the fill can't make any more progress. The fill progresses in all directions at once, so should return an answer within a few iterations. Each iteration is pretty fast too, as it just a bunch of shifting and logic operations. And no lookup tables either.

/////////////////////////////////////////////////////////////////////////
//
// Returns true if a path of set bits in 'path' exists that 8-way connect
// any set bit in sq1 to any set bit of sq2
 
bool squaresAreConnected(U64 sq1, U64 sq2, U64 path)
{
   // With bitboard sq1, do an 8-way flood fill, masking off bits not in
   // path at every step. Stop when fill reaches any set bit in sq2, or
   // fill cannot progress any further
 
   if (!(sq1 &= path) || !(sq2 &= path)) return false;
                      // Drop bits not in path
                      // Early exit if sq1 or sq2 not on any path
 
   while(!(sq1 & sq2))
   {
      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 false;         // Fill has stopped
   }
   return true;                              // Found a good path
}

External Links

Checkmate pattern from Wikipedia
King's Pattern Flatware - Spoons/Teaspoon
Amon Düül II - Archangel Thunderbird (1971), YouTube Video ^[5]

References

^ Moore neighborhood from Wikipedia
^ Thanks to Thomas Herges for pointing out a bug if kings are on the eighth rank
^ Flood Fill from Wikipedia
^ Re: algorithm question answer by Steffan Westcott in CCC September 09, 2002
^ Male and Female - 1919 American silent adventure/drama film - Wikipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
All Shortest Paths	Jan 21, 2014
Bitboards	Nov 14, 2017
Blockage Detection	Oct 19, 2017
Blockers and Beyond	Mar 21, 2014
Chunking	Jun 12, 2017
Daniel Shawul	Jan 28, 2018
Demolito	Mar 1, 2018
DirGolem	Jun 5, 2016
Evaluation Patterns	Jun 24, 2013
Fill Algorithms	Nov 6, 2013
Helmut Horacek	Oct 31, 2016
Hex	Dec 29, 2017
Iteration	May 5, 2017
King	Feb 26, 2013
King Pattern	Nov 15, 2013
King Safety	Feb 14, 2018
KPK	May 12, 2016
Mate at a Glance	Sep 24, 2014
Morph	Dec 7, 2017
Nirvanachess	Sep 30, 2017
Passed Pawn	Oct 11, 2017
Passed Pawns (Bitboards)	Aug 23, 2010
Pattern Recognition	Sep 8, 2017
Pawn Endgame	Oct 11, 2017
Pawn Race	Dec 16, 2017
PawnKing	Sep 5, 2014
Pieces versus Directions	Oct 6, 2016
Rule of the Square	Sep 6, 2014
Searcher	Sep 26, 2016
Sliding Pieces	Aug 3, 2017
Square Attacked By	Jan 20, 2018
Squares	Feb 15, 2015
SSE4	Jun 5, 2016
Steffan Westcott	Jan 21, 2014
Unstoppable Passer	Jun 21, 2016

Up one Level

Knight Pattern

GerdIsenberg — Mon, 23 Feb 2015 19:45:51 GMT

Home * Board Representation * Bitboards * Knight Pattern

		Knight Pattern with Bitboards covers knight attacks of single or multiple knights, either by indexed pre-calculated tables or direct bitboard calculation, and the set wise determination of Knight fork target squares.
M. C. Escher, Horseman ^[1]

Knight Attacks

by Lookup

by Calculation

Multiple Knight Attacks

Knight Fill

Knight Forks

See also

Selected Publications

Knight Attacks

The Knight attacks the target squares independently from other pieces around. The compass rose of all eight attacking directions associated with the to - from square differences from an 8x8 board:

        noNoWe    noNoEa
            +15  +17
             |     |
noWeWe  +6 __|     |__+10  noEaEa
              \   /
               >0<
           __ /   \ __
soWeWe -10   |     |   -6  soEaEa
             |     |
            -17  -15
        soSoWe    soSoEa

by Lookup

The knight is specified by square index, likely from a bitscan of a piece-wise bitboard serialization of a knight bitboard from a standard board-definition, to index a table of pre-calculated knight-attacks:

U64 arrKnightAttacks[64];
 
U64 knightAttacks(enumSquare sq) {return arrKnightAttacks[sq];}

For instance a knight on d4

arrKnightAttacks[d4]
 . . . . . . . .
 . . . . . . . .
 . . 1 . 1 . . .
 . 1 . . . 1 . .
 . . . . . . . .
 . 1 . . . 1 . .
 . . 1 . 1 . . .
 . . . . . . . .

by Calculation

Similar to one step only of the four orthogonal and four diagonal directions,each of the eight knight directions is calculated by left or right shift with appropriate pre- or post shift mask, to avoid A- H-file wraps or vice versa. See also AVX2 Knight Attacks.

U64 noNoEa(U64 b) {return (b << 17) & notAFile ;}
U64 noEaEa(U64 b) {return (b << 10) & notABFile;}
U64 soEaEa(U64 b) {return (b >>  6) & notABFile;}
U64 soSoEa(U64 b) {return (b >> 15) & notAFile ;}
U64 noNoWe(U64 b) {return (b << 15) & notHFile ;}
U64 noWeWe(U64 b) {return (b <<  6) & notGHFile;}
U64 soWeWe(U64 b) {return (b >> 10) & notGHFile;}
U64 soSoWe(U64 b) {return (b >> 17) & notHFile ;}
 
U64 noNoEa(U64 b) {return (b & notHFile ) << 17;}
U64 noEaEa(U64 b) {return (b & notGHFile) << 10;}
U64 soEaEa(U64 b) {return (b & notGHFile) >>  6;}
U64 soSoEa(U64 b) {return (b & notHFile ) >> 15;}
U64 noNoWe(U64 b) {return (b & notAFile ) << 15;}
U64 noWeWe(U64 b) {return (b & notABFile) <<  6;}
U64 soWeWe(U64 b) {return (b & notABFile) >> 10;}
U64 soSoWe(U64 b) {return (b & notAFile ) >> 17;}

In almost the same manner as the three pawn directions, there is a unique source-target relationship. The difference is - we have up to eight pawns, but likely not more than two knights per side. Keeping eight disjoint knight directions is consistent to direction-wise fill approaches of other pieces with unique target-source relationship - but disjoint direction-wise knight targets are sparse populated and usually contain only up to two bits.

Multiple Knight Attacks

To initialize the KnightAttacks array one may use a routine with some kind of parallel prefix calculations, rather than the union of all eight directions:

U64 knightAttacks(U64 knights) {
   U64 west, east, attacks;
   east     = eastOne (knights);
   west     = westOne (knights);
   attacks  = (east|west) << 16;
   attacks |= (east|west) >> 16;
   east     = eastOne (east);
   west     = westOne (west);
   attacks |= (east|west) <<  8;
   attacks |= (east|west) >>  8;
   return attacks;
}

or to possibly gain some more parallelism:

U64 knightAttacks(U64 knights) {
   U64 l1 = (knights >> 1) & C64(0x7f7f7f7f7f7f7f7f);
   U64 l2 = (knights >> 2) & C64(0x3f3f3f3f3f3f3f3f);
   U64 r1 = (knights << 1) & C64(0xfefefefefefefefe);
   U64 r2 = (knights << 2) & C64(0xfcfcfcfcfcfcfcfc);
   U64 h1 = l1 | r1;
   U64 h2 = l2 | r2;
   return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}

If we pass multiple knights set-wise, attacks of some squares may be caused by different knights. Feeding back (safe) target sets, the routine may used to get sets of squares, knights may reach in two or more moves. For instance in late pawn-knight endings whether a knight may catch a passer.

Knight Fill

A fill cycle for a fill algorithm is the union of the attack set with the knights itself:

U64 knightFill(U64 knights) {return knightAttacks(knights) | knights;}

for instance applied six times on the otherwise empty board:

                  1. Fill            2. Fill            3. Fill
. . . . . . . .   . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .   . . . . . . . .   . 1 . 1 . . . .
. . . . . . . .   . . . . . . . .   . . . . . . . .   1 . 1 . 1 . . .
. . . . . . . .   . . . . . . . .   1 . 1 . . . . .   1 1 1 1 . 1 . .
. . . . . . . .   . . . . . . . .   . 1 . 1 . . . .   1 1 1 1 1 . 1 .
. . . . . . . .   . 1 . . . . . .   1 1 . . 1 . . .   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. Fill            5. Fill            6. Fill
                  . 1 . 1 . 1 . .   1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1
                  1 1 1 1 1 . 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 . 1   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1

Knight Forks

A common knight pattern is the knight fork. Targets are heavy pieces - king, queen and rooks, hanging pieces, or even undefended pawns. A royal knight fork or "family" check, winning the queen is most important. Otherwise one may loop over all possible pieces, to get the knight-attacks by lookup and to intersect all combinations of attack-squares. A loop- and branch-less solution to get potential fork-attack squares is to union all intersections of all direction attacks, as explained in greater one sets:

U64 forkTargetSquare(U64 targets) {
   U64 west, east, attak, forks;
   east   = eastOne (targets);
   west   = westOne (targets);
   attak  =  east << 16;
   forks  = (west << 16) & attak;
   attak |=  west << 16;
   forks |= (east >> 16) & attak;
   attak |=  east >> 16;
   forks |= (west >> 16) & attak;
   attak |=  west >> 16;
   east   = eastOne (east);
   west   = westOne (west);
   forks |= (east <<  8) & attak;
   attak |=  east <<  8;
   forks |= (west <<  8) & attak;
   attak |=  west <<  8;
   forks |= (east >>  8) & attak;
   attak |=  east >>  8;
   forks |= (west >>  8) & attak;
   return forks;
}

The intersection of those targets with squares not occupied by own pieces or attacked by opponent pawns and knights, but attacked by own knight(s) leaves a move target set with some forced properties.

Selected Publications

Martin Gardner (1967). Problems that are Built on the Knight's Tour in Chess. Scientific American, Vol. 130
Noam D. Elkies, Richard P. Stanley (2003). The Mathematical Knight. The Mathematical Intelligencer, Vol. 25, No. 1, pdf
Ben Hill (2004). Knight’s Tours. pdf
Philip Hingston, Graham Kendall (2005). Ant Colonies Discover Knight's Tours. AI 2004, Lecture Notes in Computer Science 3339
Philip Hingston, Graham Kendall (2005). Enumerating knight's tours using an ant colony algorithm. CEC 2005

Forum Posts

Symbolic: From bitboards to ideas by Steven Edwards, CCC, March 13, 2004 » Symbolic
knight's multiple atacks by Daniel Anulliero, CCC, January 27, 2015

External Links

Knight's tour from Wikipedia
Knight's Tour Notes compiled by George Jelliss
Knight's Tour - from Wolfram MathWorld
Longest uncrossed knight's path from Wikipedia
László Lindner's knight wheel by Frederic Friedel from ChessBase Puzzle
Knight's Tour from Research Reflections by Graham Kendall, January 18, 2014
Knight's Tour - Numberphile, YouTube Video

References

^ View facsimile print from M.C. Escher - 16 Facsimile Prints

What links here?

Page	Date Edited
AVX2	Aug 8, 2017
Bitboards	Nov 14, 2017
Blockers and Beyond	Mar 21, 2014
Chunking	Jun 12, 2017
Combination	Oct 25, 2016
Decoying	Jan 12, 2015
DirGolem	Jun 5, 2016
Double Attack	Oct 22, 2014
Fill Algorithms	Nov 6, 2013
General Setwise Operations	Feb 25, 2018
Graham Kendall	May 26, 2015
Hanging Piece	Jan 14, 2017
Jonathan Warkentin	Jun 29, 2014
Killer (NL)	Dec 15, 2017
Knight Pattern	Feb 23, 2015
Knight-Distance	Oct 20, 2013
Knowledge	Jul 22, 2017
Loose Piece	Jan 10, 2015
Mathematician	Apr 9, 2018
Pattern Recognition	Sep 8, 2017
Pieces versus Directions	Oct 6, 2016
Square Attacked By	Jan 20, 2018
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
Zillions of Games	May 29, 2017

Up one Level

Kogge-Stone Algorithm

GerdIsenberg — Sat, 17 Sep 2016 21:52:19 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Kogge-Stone Algorithm

		The Kogge-Stone Algorithm for set-wise sliding piece attack generation was first introduced by Steffan Westcott in CCC ^[1] . It is a parallel prefix approach of a occluded dumb7 flood-fill, propagating sliding piece attacks like carries of a Kogge-Stone hardware adder ^[2] in software. One needs to pass sliding pieces as generator set "g" and the set of empty squares as propagator set "p". For appropriate attacks we need to shift the occluded fill one step further, considering wraps.
4-bit Kogge-Stone adder ^[3]

Parallel Prefix

Direction-wise Fill

Fill on an empty Board

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

Parallel Prefix

The routine fillUpOccluded() smears the set bits of bitboard g upwards, but only along set bits of p; a reset bit in p is enough to halt a smear. Other routines have a similar effect.

U64 fillUpOccluded(U64 g, U64 p) {
   g |= p & (g <<  8);
   p &=     (p <<  8);
   g |= p & (g << 16);
   p &=     (p << 16);
   g |= p & (g << 32);
   return g;
}

The method chosen in FillUpOccluded() is based on a Kogge-Stone parallel prefix network, because it can be implemented very easily in software. The diagram below (trust me, it really _is_ supposed to look like that) is an illustration of how it works. The corresponding lines of program code are shown on the right. The inputs are fed into the network at the top, pass along the connecting lines, are combined by the # operator at various points, and the outputs appear at the bottom.

x1 x2 x3 x4 x5 x6 x7 x8         Input : g, p
|  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|\ |\ |\ |\ |\ |\ |\ |
| \| \| \| \| \| \| \|
|  #  #  #  #  #  #  #          g |= p & (g <<  8);
|  |  |  |  |  |  |  |          p &=     (p <<  8);
|\ |\ |\ |\ |\ |\ |  |
| \: \: \: \: \: \:  |
|  \  \  \  \  \  \  |
|  :\ :\ :\ :\ :\ :\ |
|  | \| \| \| \| \| \|
|  |  #  #  #  #  #  #          g |= p & (g << 16);
|  |  |  |  |  |  |  |          p &=     (p << 16);
|\ |\ |\ |\ |  |  |  |
| \: \: \: \:  |  |  |
|  \  \  \  \  |  |  |
|  :\ :\ :\ :\ |  |  |
|  | \: \: \: \:  |  |
|  |  \  \  \  \  |  |
|  |  :\ :\ :\ :\ |  |
|  |  | \: \: \: \:  |
|  |  |  \  \  \  \  |
|  |  |  ;\ ;\ :\ :\ |
|  |  |  | \| \| \| \|
|  |  |  |  #  #  #  #          g |= p & (g << 32);
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V
q1 q2 q3 q4 q5 q6 q7 q8         Output : g

Direction-wise Fill

We further 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

Assuming little-endian file mapping. Big-endian file mapping has to swap A and H and east and west. As a reminder - shifting bitboards - the base of further stuff.

Fill on an empty Board

We already used the south- and north- parallel prefix fill-routines while calculating pawn spans. We need one additional direction step for ray-attacks on the otherwise empty board to exclude sliders. Convenient to initialize ray-attacks arrays of single sliders. We may conduct those routines from the general occluded fills by passing the universal propagator set. The vertical fills already look familiar.

U64 soutFill(U64 gen) {
   gen |= (gen >>  8);
   gen |= (gen >> 16);
   gen |= (gen >> 32);
   return gen;
}
 
U64 nortFill(U64 gen) {
   gen |= (gen <<  8);
   gen |= (gen << 16);
   gen |= (gen << 32);
   return gen;
}

Using explicit propagators as compile time constants to manage the A-, H-file-wraps.

U64 eastFill(U64 gen) {
   const U64 pr0 = notAFile;
   const U64 pr1 = pr0 & (pr0 << 1);
   const U64 pr2 = pr1 & (pr1 << 2);
   gen |= pr0 & (gen  << 1);
   gen |= pr1 & (gen  << 2);
   gen |= pr2 & (gen  << 4);
   return gen;
}
 
U64 noEaFill(U64 gen) {
   const U64 pr0 = notAFile;
   const U64 pr1 = pr0 & (pr0 <<  9);
   const U64 pr2 = pr1 & (pr1 << 18);
   gen |= pr0 & (gen <<  9);
   gen |= pr1 & (gen << 18);
   gen |= pr2 & (gen << 36);
   return gen;
}
 
U64 soEaFill(U64 gen) {
   const U64 pr0 = notAFile;
   const U64 pr1 = pr0 & (pr0 >>  7);
   const U64 pr2 = pr1 & (pr1 >> 14);
   gen |= pr0 & (gen >>  7);
   gen |= pr1 & (gen >> 14);
   gen |= pr2 & (gen >> 28);
   return gen;
}
 
U64 westFill(U64 gen) {
   const U64 pr0 = notHFile;
   const U64 pr1 = pr0 & (pr0 >> 1);
   const U64 pr2 = pr1 & (pr1 >> 2);
   gen |= pr0 & (gen >> 1);
   gen |= pr1 & (gen >> 2);
   gen |= pr2 & (gen >> 4);
   return gen;
}
 
U64 soWeFill(U64 gen) {
   const U64 pr0 = notHFile;
   const U64 pr1 = pr0 & (pr0 >>  9);
   const U64 pr2 = pr1 & (pr1 >> 18);
   gen |= pr0 & (gen >>  9);
   gen |= pr1 & (gen >> 18);
   gen |= pr2 & (gen >> 36);
   return gen;
}
 
U64 noWeFill(U64 gen) {
   const U64 pr0 = notHFile;
   const U64 pr1 = pr0 & (pr0 <<  7);
   const U64 pr2 = pr1 & (pr1 << 14);
   gen |= pr0 & (gen <<  7);
   gen |= pr1 & (gen << 14);
   gen |= pr2 & (gen << 28);
   return gen;
}

Occluded Fill

Occluded fills include sliders, but exclude blockers ^[4].

U64 soutOccl(U64 gen, U64 pro) {
   gen |= pro & (gen >>  8);
   pro &=       (pro >>  8);
   gen |= pro & (gen >> 16);
   pro &=       (pro >> 16);
   gen |= pro & (gen >> 32);
   return gen;
}
 
U64 nortOccl(U64 gen, U64 pro) {
   gen |= pro & (gen <<  8);
   pro &=       (pro <<  8);
   gen |= pro & (gen << 16);
   pro &=       (pro << 16);
   gen |= pro & (gen << 32);
   return gen;
}
 
U64 eastOccl(U64 gen, U64 pro) {
   pro &= notAFile;
   gen |= pro & (gen << 1);
   pro &=       (pro << 1);
   gen |= pro & (gen << 2);
   pro &=       (pro << 2);
   gen |= pro & (gen << 4);
   return gen;
}
 
U64 noEaOccl(U64 gen, U64 pro) {
   pro &= notAFile;
   gen |= pro & (gen <<  9);
   pro &=       (pro <<  9);
   gen |= pro & (gen << 18);
   pro &=       (pro << 18);
   gen |= pro & (gen << 36);
   return gen;
}
 
U64 soEaOccl(U64 gen, U64 pro) {
   pro &= notAFile;
   gen |= pro & (gen >>  7);
   pro &=       (pro >>  7);
   gen |= pro & (gen >> 14);
   pro &=       (pro >> 14);
   gen |= pro & (gen >> 28);
   return gen;
}
 
U64 westOccl(U64 gen, U64 pro) {
   pro &= notHFile;
   gen |= pro & (gen >> 1);
   pro &=       (pro >> 1);
   gen |= pro & (gen >> 2);
   pro &=       (pro >> 2);
   gen |= pro & (gen >> 4);
   return gen;
}
 
U64 soWeOccl(U64 gen, U64 pro) {
   pro &= notHFile;
   gen |= pro & (gen >>  9);
   pro &=       (pro >>  9);
   gen |= pro & (gen >> 18);
   pro &=       (pro >> 18);
   gen |= pro & (gen >> 36);
   return gen;
}
 
U64 noWeOccl(U64 gen, U64 pro) {
   pro &= notHFile;
   gen |= pro & (gen <<  7);
   pro &=       (pro <<  7);
   gen |= pro & (gen << 14);
   pro &=       (pro << 14);
   gen |= pro & (gen << 28);
   return gen;
}

Ray-wise Attacks

Ray-wise attacks need the occluded fills shift one further, considering wraps.

U64 soutAttacks (U64 rooks,   U64 empty) {return soutOne(soutOccl(rooks,   empty));}
U64 nortAttacks (U64 rooks,   U64 empty) {return nortOne(nortOccl(rooks,   empty));}
U64 eastAttacks (U64 rooks,   U64 empty) {return eastOne(eastOccl(rooks,   empty));}
U64 noEaAttacks (U64 bishops, U64 empty) {return noEaOne(noEaOccl(bishops, empty));}
U64 soEaAttacks (U64 bishops, U64 empty) {return soEaOne(soEaOccl(bishops, empty));}
U64 westAttacks (U64 rooks,   U64 empty) {return westOne(westOccl(rooks,   empty));}
U64 soWeAttacks (U64 bishops, U64 empty) {return soWeOne(soWeOccl(bishops, empty));}
U64 noWeAttacks (U64 bishops, U64 empty) {return noWeOne(noWeOccl(bishops, empty));}

Generalized Rays

Since rotate 64 works like a generalized shift with positive or negative shift amount, it might be applied to get pawn-attacks for both sides - or a Kogge-Stone fill 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.

U64 occludedFill (U64 gen, U64 pro, int dir8)
{
   int r = shift[dir8]; // {+-1,7,8,9}
   pro &= avoidWrap[dir8];
   gen |= pro & rotateLeft(gen, r);
   pro &=       rotateLeft(pro, r);
   gen |= pro & rotateLeft(gen, 2*r);
   pro &=       rotateLeft(pro, 2*r);
   gen |= pro & rotateLeft(gen, 4*r);
   return gen;
}
 
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,
};

Publications

Peter M. Kogge, Harold S. Stone (1973). A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Transactions on Computers, 1973, C-22, 783-791, pdf

Forum Posts

Re: flood fill attack bitboards by Steffan Westcott, CCC, September 15, 2002
Kogge Stone Algorithm mistake on chessprogramming Wiki by Christopher Conkie, CCC, June 29, 2008
Re: Hyperbola Quiesscene: hardly any improvement by Karlo Bala Jr., CCC, January 14, 2009 » Hyperbola Quintessence
Kogge Stone, Vector Based by Srdja Matovic, CCC, January 22, 2013 » GPU ^[5] ^[6]
Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013 » Perft, GPU

External Links

Kogge-Stone adder from Wikipedia
Kogge-Stone algorithm from Terra Help and Information - Theories by Peter Fendrich
Gong - Shapeshifter ^[7], 1992, YouTube Video

References

^ Re: flood fill attack bitboards by Steffan Westcott, CCC, September 15, 2002
^ Hardware algorithms for arithmetic modules from the ARITH research group, Aoki lab., Tohoku University
^ Kogge-Stone adder from Wikipedia
^ Kogge Stone Algorithm mistake on chessprogramming Wiki by Christopher Conkie, CCC, June 29, 2008
^ Parallel Thread Execution from Wikipedia
^ NVIDIA Compute PTX: Parallel Thread Execution, ISA Version 1.4, March 31, 2009, pdf
^ Shapeshifting from Wikipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
Ankan Banerjee	Aug 26, 2017
Anubis	Sep 29, 2015
Attack and Defend Maps	Nov 5, 2016
Bit-Twiddling	Nov 6, 2017
Christopher Conkie	May 17, 2016
Design Principles	Jan 17, 2018
DirGolem	Jun 5, 2016
Dumb7Fill	May 27, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Fill Algorithms	Nov 6, 2013
Fill by Subtraction	Mar 5, 2010
GPU	Dec 16, 2017
Gunnar Andersson	Jun 23, 2011
John L. Jerz	Jul 15, 2013
Karlo Bala Jr.	Feb 19, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Mathematician	Apr 9, 2018
Mobility	Jan 17, 2018
On an empty Board	Mar 18, 2014
Othello	Jan 4, 2018
Paladin	Jan 29, 2017
Parallel Prefix Algorithms	Jun 22, 2016
Pawn Fills	Jul 18, 2014
Perft	Sep 26, 2017
Pieces versus Directions	Oct 6, 2016
Quad-Bitboards	Jan 30, 2017
Rodent	Jan 11, 2018
Russell Reagan	Aug 31, 2013
Shifted Bitboards	Jan 9, 2011
SIMD and SWAR Techniques	Jun 27, 2017
Sliding Piece Attacks	May 27, 2016
Srdja Matovic	Apr 14, 2018
SSE2	Feb 27, 2018
Steffan Westcott	Jan 21, 2014
Tarrasch Rule	Jun 2, 2014
X-ray Attacks (Bitboards)	Mar 31, 2015

Up one Level

Open Pawns (Bitboards)

davidcnorris — Thu, 24 Aug 2017 14:11:28 GMT

Open Single Pawn

Open Pawns set-wise

What links here?

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

Open pawns have no mechanical obstruction - an opponent pawn in front. They are at least half-free or even free passers. Thus, open pawns are a superset of passed pawns and half-free pawns like candidates but also weak pawns like the half-free straggler (backward pawn ) or half-free isolanis. Open pawns are vulnerable from opponent rook-attacks on half-open files.

Open Single Pawn

Working in the square centric world of the board, thus using a square index of one particular pawn, likely from bitboard traversal, to lookup pre-calculated pattern.

For a single pawn we need to access a lookup-table to get all squares on the same file in front of the pawn. If the intersection of the fronspan with the set of opponent pawns is empty, it is a open pawn.

U64 arrFrontSpans[2][64];
 
if ( (arrFrontSpans[white][sqOfWhitePawn] & pawnBB[black]) == 0 ) -> pawn open

arrFrontSpan[white][d4]
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . p . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Open Pawns set-wise

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

Open Pawns have no mechanical obstruction in front - an opponent pawn as member of the own frontfill or frontspan. A relative complement with the opponents frontspans is sufficient to determine open pawns:

U64 wOpenPawns(U64 wpawns, U64 bpawns) {
   return wpawns & ~bFrontSpan(bpawns);
}
 
U64 bOpenPawns(U64 bpawns, U64 wpawns) {
   return bpawns & ~wFrontSpan(wpawns);
}

What links here?

Page	Date Edited
Backward Pawns (Bitboards)	May 5, 2017
Blockade of Stop	Oct 11, 2016
Defended Pawns (Bitboards)	Feb 27, 2015
En prise	Oct 11, 2016
Hanging pawns	Aug 5, 2015
Hanging Piece	Jan 14, 2017
Isolated Pawns (Bitboards)	Nov 18, 2012
Murka	Nov 11, 2016
Open Pawns (Bitboards)	Aug 24, 2017
Pawn chain	Jan 17, 2018
Pawn Pattern and Properties	Nov 11, 2017
Pawns and Files (Bitboards)	Jan 16, 2013

Up one Level

Passed Pawns (Bitboards)

GerdIsenberg — Mon, 23 Aug 2010 20:40:00 GMT

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

		A passed pawn, also called passer, has no opponent pawns in front on the same or adjacent files. In Bitboards, passers may be determined square- or set-wise.
Carina Jørgensen, Pawn's Dream ^[1]

Single Passer

Working in the square centric world of the board, thus using a square index of one particular pawn, likely from bitboard traversal, to lookup pre-calculated pattern.

For a single pawn we need to access a lookup-table to get all squares on the same file and adjacent file in front of the pawn. This is what we call front-span and attack spans. If the intersection of those span-union with the set of opponent pawns is empty, it is a passed pawn.

U64 arrFrontSpans[2][64];
 
if ( (arrFrontSpans[white][sqOfWhitePawn] & pawnBB[black]) == 0 ) -> pawn is a passer

arrFrontSpans[white][d4]
. . 1 1 1 . . .
. . 1 1 1 . . .
. . 1 1 1 . . .
. . 1 1 1 . . .
. . . p . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Pawns ready to promote don't need above condition, the appearance on the 7th (or 2nd) rank is already sufficient to be a passer:

if ( sqOfWhitePawn >= a7 ) -> white pawn may promote
if ( sqOfBlackPawn <= h2 ) -> black pawn may promote

Passers set-wise

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

Passers are the pawns outside the union of all opponent frontspans and attack-frontspans.

U64 wPassedPawns(U64 wpawns, U64 bpawns) {
   U64 allFrontSpans = bFrontSpans(bpawns);
   allFrontSpans |= eastOne(allFrontSpans)
                 |  westOne(allFrontSpans);
   return wpawns & ~allFrontSpans;
}
 
U64 bPassedPawns(U64 bpawns, U64 wpawns) {
   U64 allFrontSpans = wFrontSpans(wpawns);
   allFrontSpans |= eastOne(allFrontSpans)
                 |  westOne(allFrontSpans);
   return bpawns & ~allFrontSpans;
}

External Links

Passed pawn from Wikipedia

References

^ Pawn's Dream 2009 by Carina Jørgensen

What links here?

Page	Date Edited
Attack Spans	Mar 4, 2010
Candidates (Bitboards)	Nov 11, 2017
Murka	Nov 11, 2016
Passed Pawn	Oct 11, 2017
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Pattern and Properties	Nov 11, 2017
Pawn Spans	Jul 22, 2010
PawnKing	Sep 5, 2014

Up one Level

Pawn Attacks (Bitboards)

GerdIsenberg — Thu, 04 Mar 2010 17:41:49 GMT

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

Of a Single Pawn

Attacks

To get attacks, we use a lookup of pre-calculated pawn-atacks, similar to knight- and king-attacks, except the need to consider color of the pawn.

whitePawnAttacks = arrPawnAttacks[white][sqOfWhitePawn];
if ( whitePawnAttacks & pieceBB[black] ) -> pseudo legal captures possible

arrPawnAttacks[white][d4]
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . 1 . 1 . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Captures

Only intersection with the opponent pieces is required.
We may include a possible en-passant target square.

Pawns set-wise

Working in the bitboard centric world to determine attacks and properties set-wise.

Attacks

Generate all squares that are attacked by pawns of a color. It makes sense to keep disjoint sets for both attacking directions. For move-gen disjoint east-west attacks has the advantage of unique source-target relation ship (+-7,9). After obtaining the direction-wise target-set a reverse shift is sufficient to get the source-set without further intersections and wrap issues.

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

U64 wPawnEastAttacks(U64 wpawns) {return noEaOne(wpawns);}
U64 wPawnWestAttacks(U64 wpawns) {return noWeOne(wpawns);}
 
U64 bPawnEastAttacks(U64 bpawns) {return soEaOne(bpawns);}
U64 bPawnWestAttacks(U64 bpawns) {return soWeOne(bpawns);}

A bit-wise boolean instruction to combine those disjoint sets:

U64 wPawnAnyAttacks(U64 wpawns) {
   return wPawnEastAttacks(wpawns) | wPawnWestAttacks(wpawns);
}
 
U64 wPawnDblAttacks(U64 wpawns) {
   return wPawnEastAttacks(wpawns) & wPawnWestAttacks(wpawns);
}
 
U64 wPawnSingleAttacks(U64 wpawns) {
   return wPawnEastAttacks(wpawns) ^ wPawnWestAttacks(wpawns);
}

and similar for black.

 white pawns       white pawns << 9  &       notAFile     ==   wPawnEastAttacks
. . . . . . . .     . . . . . . . .      . 1 1 1 1 1 1 1      . . . . . . . . 
. . . . . . . .     . . . . . . . .      . 1 1 1 1 1 1 1      . . . . . . . . 
. . . . . . . .     . . . . . . . .      . 1 1 1 1 1 1 1      . . . . . . . . 
. . . . . . . .     . . . . . . . .      . 1 1 1 1 1 1 1      . . . . . . . . 
. . . . . . . .     h . . c . . . .      . 1 1 1 1 1 1 1      . . . c . . . . 
. . c . . . . .     . a b . d . f g      . 1 1 1 1 1 1 1      . a b . d . f g 
a b . d . f g h     . . . . . . . .      . 1 1 1 1 1 1 1      . . . . . . . . 
. . . . . . . .     / . . . . . . .      . 1 1 1 1 1 1 1      / . . . . . . . 
 
 white pawns       white pawns << 7  &       notHFile     ==  wPawnWestAttacks
. . . . . . . .     . . . . . . . .      1 1 1 1 1 1 1 .      . . . . . . . . 
. . . . . . . .     . . . . . . . .      1 1 1 1 1 1 1 .      . . . . . . . . 
. . . . . . . .     . . . . . . . .      1 1 1 1 1 1 1 .      . . . . . . . . 
. . . . . . . .     . . . . . . . .      1 1 1 1 1 1 1 .      . . . . . . . . 
. . . . . . . .     . c . . . . . .      1 1 1 1 1 1 1 .      . c . . . . . . 
. . c . . . . .     b . d . f g h .      1 1 1 1 1 1 1 .      b . d . f g h . 
a b . d . f g h     . . . . . . . a      1 1 1 1 1 1 1 .      . . . . . . . . 
. . . . . . . .     . . . . . . . \      1 1 1 1 1 1 1 .      . . . . . . . \ 
 
 white pawns                                                  wPawnAnyAttacks
. . . . . . . .                                               . . . . . . . .  
. . . . . . . .                                               . . . . . . . .  
. . . . . . . .                                               . . . . . . . .  
. . . . . . . .                                               . . . . . . . .  
. . . . . . . .                                               . c . c . . . .  
. . c . . . . .                                               b a 1 . 1 g 1 g  
a b . d . f g h                                               . . . . . . . .  
. . . . . . . .                                               . . . . . . . .

Attack Maps

One idea to combine pawn-attacks is about safe squares or push-targets for white respectively black pawns. A kind if of set-wise static exchange evaluation - only considering pawn-attacks from both sides. A square is assumed safe, if the number of own pawn defends if greater or equal than opponent pawn attacks. That is true if the own side defends a square twice, or the opposite side has no attacks at all, or own side attacks once and opponent not twice.

U64 wSafePawnSquares(U64 wpawns, U64 bpawns) {
   U64 wPawnEastAttacks =  wPawnEastAttacks (wpawns);
   U64 wPawnWestAttacks =  wPawnWestAttacks (wpawns);
   U64 bPawnEastAttacks =  bPawnEastAttacks (bpawns);
   U64 bPawnWestAttacks =  bPawnWestAttacks (bpawns);
   U64 wPawnDblAttacks  =  wPawnEastAttacks &  wPawnWestAttacks;
   U64 wPawnOddAttacks  =  wPawnEastAttacks ^  wPawnWestAttacks;
   U64 bPawnDblAttacks  =  bPawnEastAttacks &  bPawnWestAttacks;
   U64 bPawnAnyAttacks  =  bPawnEastAttacks |  bPawnWestAttacks;
   return wPawnDblAttacks |~bPawnAnyAttacks | (wPawnOddAttacks &~bPawnDblAttacks);
}

Those attack maps are among other things useful to decide about candidates and backward pawns .

Captures

As usual, capture targets are the intersection of attack-sets with opponent pieces. Except en-passant captures of course. A reverse shift of disjoint direction-wise sets obtains the pawns which may capture.

To find the pawn set, which can actually capture, on the fly, we can start with the target squares as well:

U64 wPawnsAble2CaptureEast(U64 wpawns, U64 bpieces) {
   return wpawns & bPawnWestAttacks(bpieces);
}
 
U64 wPawnsAble2CaptureWest(U64 wpawns, U64 bpieces) {
   return wpawns & bPawnEastAttacks(bpieces);
}
 
U64 wPawnsAble2CaptureAny(U64 wpawns, U64 bpieces) {
   return wpawns & bPawnAnyAttacks(bpieces);
}

What links here?

Page	Date Edited
More Links
Attack and Defend Maps	Nov 5, 2016
Attack Spans	Mar 4, 2010
Blockage Detection	Oct 19, 2017
Candidates (Bitboards)	Nov 11, 2017
Defended Pawns (Bitboards)	Feb 27, 2015
Design Principles	Jan 17, 2018
DirGolem	Jun 5, 2016
Double Attack	Oct 22, 2014
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Fill Algorithms	Nov 6, 2013
General Setwise Operations	Feb 25, 2018
Kaissa	Apr 9, 2018
MVV-LVA	Oct 26, 2017
Pawn Attacks (Bitboards)	Mar 4, 2010
Pawn Levers (Bitboards)	Nov 11, 2017
Pawn Pattern and Properties	Nov 11, 2017
Pieces versus Directions	Oct 6, 2016
SEE	Jan 14, 2013
Square Control	Sep 15, 2016
Square Mapping Considerations	Feb 28, 2018

Up one Level

Pawn Fills

GerdIsenberg — Fri, 18 Jul 2014 12:54:18 GMT

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

Vertical pawn fills are base of spans. They are used to determine closed, half-open and open files.

Front- and Rearfill

Frontfills and rearfills are the base of front- and rearspans, which require one additional north/south shift. Of course whites front direction is north, while blacks front direction is south - vice versa for the rear side.

white frontfill     black rearfill
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 . 1 1 . . . 1
1 1 1 . . 1 1 1     . . . 1 . . . .
1 1 1 . . 1 1 1  ^  . . . . . . . .
. 1 1 . . . 1 1  |   . . . . . . . .
. 1 1 . . . 1 1  |   . . . . . . . .
. . . . . . . .  |   . . . . . . . .
               north
white pawns         black pawns
. . . . . . . .     . . . . . . . .
. . . . . . . .     . 1 . . . 1 1 .
. . . . . . . .     1 . 1 . . . . 1
. . . . . . . .     . . . 1 . . . .
1 . . . . 1 . .     . . . . . . . .
. . 1 . . . . .     . . . . . . . .
. 1 1 . . . 1 1     . . . . . . . .
. . . . . . . .     . . . . . . . .
               south
white rearfill      black frontfill
. . . . . . . .  |  . . . . . . . .
. . . . . . . .  |  . 1 . . . 1 1 .
. . . . . . . .  |  1 1 1 . . 1 1 1
. . . . . . . .  v  1 1 1 1 . 1 1 1
1 . . . . 1 . .     1 1 1 1 . 1 1 1
1 . 1 . . 1 . .     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1

Parallel prefix Kogge-Stone-routines are used to fill either north or south:

U64 nortFill(U64 gen) {
   gen |= (gen <<  8);
   gen |= (gen << 16);
   gen |= (gen << 32);
   return gen;
}
 
U64 soutFill(U64 gen) {
   gen |= (gen >>  8);
   gen |= (gen >> 16);
   gen |= (gen >> 32);
   return gen;
}

Note that the pawns are still subset of their fill sets. The intersection of both north and south fills leaves the initial pawn set again. All pawns which are member of the opponent front fills have a mechanical obstruction and are unfree.

U64 wFrontFill(U64 wpawns) {return nortFill(wpawns);}
U64 wRearFill (U64 wpawns) {return soutFill(wpawns);}
 
U64 bFrontFill(U64 bpawns) {return soutFill(bpawns);}
U64 bRearFill (U64 bpawns) {return nortFill(bpawns);}

Filefill

The union of both front- and rearfills, leaves the complete file with at least one either white or black pawn on it. Since filefills have all ranks equal, they may treated as bytes, if it is about pure file sets.

U64 fileFill(U64 gen) {
   return nortFill(gen) | soutFill(gen);
}

white pawns         black pawns
. . . . . . . .     . . . . . . . .
. . . . . . . .     . 1 . . . 1 1 .
. . . . . . . .     1 . 1 . . . . 1
. . . . . . . .     . . . 1 . . . .
1 . . . . 1 . .     . . . . . . . .
. . 1 . . . . .     . . . . . . . .
. 1 1 . . . 1 1     . . . . . . . .
. . . . . . . .     . . . . . . . .
white filefill      black filefill
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1
1 1 1 . . 1 1 1     1 1 1 1 . 1 1 1

Based on pawns, files are either closed, open or halfopen.

External Links

Billy Cobham - George Duke Band - Juicy, YouTube Video
feat. John Scofield and Alphonso Johnson, Montreux Jazz Festival, July 6, 1976

What links here?

Page	Date Edited
Attack Spans	Mar 4, 2010
Candidates (Bitboards)	Nov 11, 2017
Dispersion and Distortion	Nov 11, 2017
Fill Algorithms	Nov 6, 2013
Kogge-Stone Algorithm	Sep 17, 2016
Open Pawns (Bitboards)	Aug 24, 2017
Parallel Prefix Algorithms	Jun 22, 2016
Passed Pawn	Oct 11, 2017
Pawn Fills	Jul 18, 2014
Pawn Pattern and Properties	Nov 11, 2017
Pawn Spans	Jul 22, 2010
PawnKing	Sep 5, 2014
Pawns and Files (Bitboards)	Jan 16, 2013
Rule of the Square	Sep 6, 2014
Unfree Pawns (Bitboards)	Nov 11, 2017

Up one Level

Pawn Levers (Bitboards)

GerdIsenberg — Sat, 11 Nov 2017 09:47:44 GMT

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

		Pawn Lever, opposing pawns in contact that can capture each other. In chess the term lever is also used as option to attack an opposing pawn by a push or double push. In Pawn Power in Chess ^[1], Hans Kmoch classified levers in the following way ^[2]:
Samuel Bak - To The Right ^[3]

Lever Classification

East and West Levers

Inner, Outer and Center Levers

Lever Classification

Center lever - A lever wholly within the two center files.
Chain lever - Adjacent levers in a diagonal formation, where the respective headpawns attack the base of the opposing chain, e.g., f5, g4 vs. g6, h5. Produces passed pawns.
Fork lever - A lever attacking two units at once (can include a piece).
Inner Lever - A lever where the capture would move toward the center.
Loose lever - A lever where each side has the option of capturing or bypassing.
Mute chain lever - A chain lever in which the bases of the opposing pawn chains are not attacked, e.g., a5, b4, c3 vs. a7, b6, c5. Doesn't produce passers.
Outer lever - A lever where the capture would move away from the center.
Tight lever - A lever including a ram, that offers only one side the option of both capture and bypass, e.g., c4, d4 vs. d5, e6.

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

East and West Levers

We define lever direction by the two horizontal attack directions of the pawn, not where it comes from if capturing. Whites east lever implies blacks west lever and vice versa:

whites east lever   whites west lever
is blacks west      is blacks east
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
. . . b . . . .     . . . b . . . .
. . w . . . . .     . . . . w . . .
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .

Keeping disjoint west- or east levers...

Code is based on Pawn Attacks (Bitboards) and Pawn Pushes (Bitboards).

U64 wEastLever(U64 wpawns, U64 bpawns) {
   return wpawns & bPawnWestAttacks(bpawns);
}
 
U64 wWestLever(U64 wpawns, U64 bpawns) {
   return wpawns & bPawnEastAttacks(bpawns);
}
 
U64 wAnyLever(U64 wpawns, U64 bpawns) {
   return wEastLever(wpawns, bpawns)
        | wWestLever(wpawns, bpawns);
}

... makes it easier to decide about inner or outer levers.

If it is about black levers, we can calculate them accordantly. On the other hand, if we already calculated white levers, we may simply shift them back since wraps are already considered:

bEastLever = wWestLever << 7;
bWestLever = wEastLever << 9

Inner, Outer and Center Levers

Whites inner levers imply black outer levers and vice versa. Inner levers are usually more advantageous than outer levers.

whites inner lever  whites outer lever
is blacks outer     is blacks inner
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
. . b . . . b .     . b . . . . . b
. w . . . . . w     . . w . . . w .
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .

U64 wInnerLever(U64 wpawns, U64 bpawns) {
   const U64 abcFiles = C64(0x0707070707070707);
   const U64 fghFiles = C64(0xE0E0E0E0E0E0E0E0);
   return ( wEastLever(wpawns, bpawns) & abcFiles )
        | ( wWestLever(wpawns, bpawns) & fghFiles );
}
 
U64 wOuterLever(U64 wpawns, U64 bpawns) {
   const U64 bcdFiles = C64(0x0E0E0E0E0E0E0E0E);
   const U64 efgFiles = C64(0x7070707070707070);
   return ( wEastLever(wpawns, bpawns) & efgFiles )
        | ( wWestLever(wpawns, bpawns) & bcdFiles );
}
 
U64 wCenterLever(U64 wpawns, U64 bpawns) {
   const U64 dFile = C64(0x0808080808080808);
   const U64 eFile = C64(0x1010101010101010);
   return ( wEastLever(wpawns, bpawns) & dFile )
        | ( wWestLever(wpawns, bpawns) & eFile );
}

with similar code for black levers.

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
Backward Pawns (Bitboards)	May 5, 2017
Battery	Jan 29, 2017
Blockage Detection	Oct 19, 2017
Candidates (Bitboards)	Nov 11, 2017
Dartmouth CP	Jan 19, 2018
Development	Jan 17, 2018
Hans Kmoch	Nov 11, 2017
Lyudmil Tsvetkov	Mar 28, 2018
Opponent Model Search	Aug 14, 2017
Passed Pawn	Oct 11, 2017
Pawn Center	Feb 12, 2015
Pawn Levers (Bitboards)	Nov 11, 2017
Pawn Pattern and Properties	Nov 11, 2017
Pawn Rams (Bitboards)	Nov 11, 2017
Pawn Structure	Oct 2, 2017
PawnKing	Sep 5, 2014
Pawns Breakthrough	May 4, 2014
Tempo	Jan 17, 2018

Up one Level

Pawn Rams (Bitboards)

GerdIsenberg — Sat, 11 Nov 2017 09:28:17 GMT

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

		Pawn Rams, all pawns that are blocked by the opponent's pawns. A ram is a mutual mechanical obstruction. If the rammed pawn is no lever pawn, it becomes member of the immobile pawns. Specially if other properties match, e.g. there is no or no mutual lever-possibility against the opponent counterpart, rams are a symptom of congealment. The term Ram or Widder in German (Ovis, Aries) was coined by Hans Kmoch ^[1] ^[2]. Rammed none lever pawns in the center or extended center are most important to decide about bad bishops.
Samuel Bak - Locked ^[3]

Blocked Positions

Code

Mutual Mechanical Obstruction

Blocked Positions

Three or four isolated rams are a perfect barrier - no path for either king to enter to opposite area.

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

Code

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.

U64 wRam(U64 wpawns, U64 bpawns) {return soutOne(bpawns) & wpawns;}
U64 bRam(U64 wpawns, U64 bpawns) {return nortOne(wpawns) & bpawns;}

Obviously the number of white rammed pawns is equal to the number of black rammed pawns.

Mutual Mechanical Obstruction

Mutual Mechanical Obstruction ^[4]

Forum Posts

Pawn ram code in gnuchess by Chua Kong Sian, gnu.chess, June 18, 1994

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
^ Kämpfende Steinböcke ... fighting ibex from Flickr - Fotosharing!, kleinwegen.net

What links here?

Page	Date Edited
Backward Pawns (Bitboards)	May 5, 2017
Bad bishop	Jun 22, 2015
Blockade of Stop	Oct 11, 2016
Blockage Detection	Oct 19, 2017
Candidates (Bitboards)	Nov 11, 2017
Denis Onneweer	Oct 3, 2012
Design Principles	Jan 17, 2018
Hans Kmoch	Nov 11, 2017
Hidden Passed Pawn	Nov 11, 2017
Middlegame	Sep 6, 2016
Najib Nakad	Oct 22, 2014
Opponent Model Search	Aug 14, 2017
Pawn Center	Feb 12, 2015
Pawn chain	Jan 17, 2018
Pawn Endgame	Oct 11, 2017
Pawn Levers (Bitboards)	Nov 11, 2017
Pawn Pattern and Properties	Nov 11, 2017
Pawn Rams (Bitboards)	Nov 11, 2017
Pawn Structure	Oct 2, 2017
Pawns Breakthrough	May 4, 2014
Ramjet	Sep 27, 2017
Stalemate	Feb 21, 2018
Vajolet	Jan 25, 2018

Up one Level

Pieces versus Directions

GerdIsenberg — Thu, 06 Oct 2016 20:21:40 GMT

Home * Board Representation * Bitboards * Pieces versus Directions

Despite the generation of moves to one target square by pieces from different directions as mentioned Square Attacked By, there are two approaches to generate moves in an origin centric manner to determine a set of distinct target squares. The classical approach, also applied in Mailbox array representation, is to generate attacks and moves piece by piece. Alternately there are set-wise approaches, to determine distinct direction attacks for sets of multiple pieces and pawns. Sliding pieces rely on dumb7fill, kogge-stone algorithm or fill by subtraction.

Piece by Piece

In general there are lookup techniques to determine attack- or move-target sets for each individual pawn or piece, indexed by bitscanned square and for the sliders by occupancy. Each piece-wise attack covers all their inherited ray- or knight directions. This classical approach traverses all pieces and generates attack sets and move sets by following techniques:

As usual, captures are determined by intersection of attacks with opponent pieces or en passant target, while all other attacks or push targets of empty squares are quiet moves.

for all pieces {
  generateMovetargets(piece);
  for all capture targets
      generate captures (move or capture list)
  for all empty square targets
      generate quite moves (move list)
}

Directions

The direction-wise approach relies on following set-wise techniques to determine move-targets. As usual, captures are determined by intersection of attacks with opponent pieces or en passant target, while all other attacks or push targets of empty squares are quiet moves.

For move generation purpose one may store target-sets of different piece types per direction. Thus, 16 bitboards as a kind of unsorted move list. Each target square in each ray-direction set has an unique one-to-one relation to it's source square.

for all 16 ray- and knight directions {
  generateMovetargets(dirtargets[dir], dir);
}

Likely this loop is unrolled - at least for the ray-attacks - where pawns, kings, bishops, rooks or queens may involved. See the proposal of DirGolem for a branch-less direction-wise generation of legal moves.

An incremental finite state machine - move-getter may scan and reset the target squares per direction. For distant source squares of sliding pieces, one may intersect the ray-wise masks per direction and target-square with the occupancy - to use either bitscan reverse or forward for the positive or negative directions - similar to the classical approach, except one don't needs the if (blocker) - condition, which is always true. However, one may delay determining the source square and moving piece until make move time, and to encode moves uniquely with target square (six bits) and direction (4 bits).

Alternatively, one may process a ray in one run, to bitscan the most farthest destination square from one distinct direction, i.e. bitscan reverse of positive ray attacks, and to loop over all intermediate targets by adding offsets until the source square is arrived. The below loop considers that move-target bits may already reset due to staged move generation, i.e. hash move or killer moves may already tried. Therefor the extra condition with testAndResetBit ^[1].

while ( northMoveTargets )
{
    targetSquare = bitScanReverse( northMoveTargets );
    sourceSquare = bitScanReverse( rayAttacks[sout][targetSquare] & occupied);
    storeMoveOrCapture( sourceSquare, targetSquare); 
    resetBit (northMoveTargets, targetSquare);
    targetSquare -= 8; 
    while ( targetSquare > sourceSquare) {
       if ( testAndResetBit (northMoveTargets, targetSquare) )
          storeMove( sourceSquare, targetSquare); 
       targetSquare -= 8; 
    }
}

Hybrid

One may combine both approaches with usual move lists. For instance direction-wise attacks for all pawns, piece-wise attacks for none-pawns. The target set-of pawn-captures should be considered early, since this are winning or at least equal captures.

External Links

Miles Davis - Call It Anything, Isle of Wight Festival, August 29, 1970, YouTube Video
Miles Davis, Gary Bartz, Chick Corea, Keith Jarrett, Dave Holland, Jack DeJohnette, Airto Moreira ^[2] ^[3]
Directions (Joe Zawinul) 0:00 (7:30), Bitches Brew 7:30 (10:09), It's About That Time 17:39 (6:17),
Sanctuary (Wayne Shorter) 23:56 (1:10), Spanish Key 25:06 (8:15), The Theme 33:21 (2:10)

References

What links here?

Page	Date Edited
Attack and Defend Maps	Nov 5, 2016
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Classical Approach	Jan 28, 2018
Direction	Oct 6, 2016
DirGolem	Jun 5, 2016
Dumb7Fill	May 27, 2016
Encoding Moves	Mar 27, 2016
Fill by Subtraction	Mar 5, 2010
Kogge-Stone Algorithm	Sep 17, 2016
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Origin Square	Oct 10, 2016
Pieces versus Directions	Oct 6, 2016
Target Square	Oct 26, 2017

Up one Level

Sliding Piece Attacks

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

Home * Board Representation * Bitboards * Sliding Piece Attacks

		This is basically about how to calculate attack-sets of sliding pieces for evaluation and move-generation purposes. While the attack-sets of pawn, king and knight are only dependent on their origin square, sliding pieces like rook, bishop or queen have to consider occupancy, as pieces may block the attack-ray in one particular direction.
Carina Jørgensen, Queen's Star ^[1]

Move targets

Single Sliding Piece Attacks

Multiple Sliding Pieces

Move targets

Move target sets from attack-sets require intersection

with opponent pieces for captures
with all empty squares for quiet moves

Single Sliding Piece Attacks

The single sliding piece, a rook, bishop or queen is determined by square index, likely from a bitscan of a piece-wise bitboard serialization of a sliding piece bitboard from a standard board-definition.

On an empty Board

Sliding piece attack sets or their disjoint subsets on lines or rays on an otherwise empty board are that simple than none sliding pieces. They are often base of further attack calculations.

Attacks on the otherwise empty Board

Tinker's Approach

Brian Richardson proposed a move generation approach as used in Tinker based on rook or bishop attacks on the otherwise empty board ^[2]. While serializing all potential targets, he tests for legality inside the loop body, that is whether the inbetween squares of origin and target are empty. This is not in the "real" bitboard spirit to determine attack sets in advance rather than to test individual elements of a superset belonging to a set, but at least it allows traversing disjoint target sets i.e. for captures in quiescence search.

By Calculation

Some bit-twiddling ray-wise and line-wise approaches, unfortunately not always for all directions.

By Occupancy Lookup

Covering line-attacks in one run, magic bitboards even covers rook- and bishop-attacks in one run.

Miscellaneous

Multiple Sliding Pieces

For bitsets with multiple sliding pieces one can apply a fill algorithm in each of the eight ray-directions to determine attacks. Since we keep disjoint directions, there is still a unique 1:1 relation from each bit of the target set to it's source square. This approach is great to determine target sets we may reach in two or more moves. One may use the union of rooks and queen(s), respectively bishops or queen(s) though.

If applied for move generation we better traverse directions rather than sliding pieces. Naturally this approach becomes less efficient, the less sliders are processed in parallel. Of course, one should avoid processing empty sets.

Forum Posts

1999

Re: How do you represent chess boards in your chess programms by Sven Reichard, CCC, September 29, 1999

2000 ...

Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed by Brian Richardson, CCC, April 24, 2000
An idea to generate rook moves without rotated BBs by Severi Salminen, CCC, October 22, 2000
sliding attacks in three #define by Rasjid Chan, CCC, April 09, 2004

2005 ...

BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Brian Richardson, CCC, August 24, 2007
Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Harald Lüßen, CCC, August 24, 2007
Yet another bitboard attack generator by Miguel A. Ballicora, CCC, October 28, 2009
Other attack generator just for good measure ... C++ only... by Filip Tvrzsky, CCC, October 29, 2009
Caching AttackSets by Michael Hoffmann, CCC, November 09, 2009

2010 ...

Bitboards by Jeroen de Bruin, Winboard Forum, July 07, 2010
Low memory usage attack bitboard generation by crystalclear, Winboard Forum, October 06, 2011
Re: Bitboard implementation, how much time? by Michael Hoffmann, CCC, January 26, 2012
152k rook and bishop attacks using PEXT and PDEP by Lasse Hansen, CCC, October 06, 2013 » BMI2

2015 ...

On Rook tables in magic move generation by Syed Fahad, CCC, February 22, 2015
Yet another way of generating sliding attack masks by Syed Fahad, CCC, March 09, 2015
Slider attack mask generation without table lookup by Syed Fahad, CCC, May 24, 2015
Comparison of bitboard attack-getter variants by Sven Schüle, CCC, January 04, 2016
SBAMG - Completing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016

External Links

Slide attack from Wikipedia
Focus - Glider, Ship of Memories 1976, YouTube Video

References

^ Queen's Star 2009 by Carina Jørgensen
^ Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed by Brian Richardson, CCC, April 24, 2000

Up one Level

Wikispaces : chessprogramming - items matching description

Defended Pawns (Bitboards)

Table of Contents

Defended

Defenders

Defended Defenders

Not Defended Defenders

Not Defending Defended

Forum Posts

What links here?

Design Principles

Rererences

What links here?

Double and Triple (Bitboards)

Table of Contents

By Square

Multiple Pawns

Forum Posts

What links here?

Dumb7Fill

Table of Contents

Occluded Fill

Seven Fill Cycles

Fill Loop

Unrolled Loop

Attack Fill

Comparison with Kogge-Stone

All Directions

Generalized Rays

Loop Version

Unrolled Attacks

See also

External Links

What links here?

Duo Trio Quart (Bitboards)

Table of Contents

Neighbors

Neighbor Algebra

See also

Forum Posts

External Links

References

What links here?

Fill by Subtraction

Table of Contents

Source Code

Comparison with Kogge-Stone

See also

What links here?

Isolated Pawns (Bitboards)

Table of Contents

Isolani by Square

Isolanis and Half-isolanis set-wise

Hanging pawns

What links here?

King Pattern

Table of Contents

King Attacks

by Lookup

by Calculation

King Safety

Pawn-Shield Pattern

Vulnerable on distant Checks

Branchless

SSE4

King and Pawns

Set-wise Rule of the Square

Flood Fill Algorithms

See also

External Links

References

What links here?

Knight Pattern

Table of Contents

Knight Attacks

by Lookup

by Calculation

Multiple Knight Attacks

Knight Fill

Knight Forks