Passed pawn detection in array based board representations

[zd3nik]

While tinkering with a new array based engine I've realized that I am in need of a fast way to identify passed pawns.

I knew the naive approach would be kinda slow, but it's actually VERY slow.

Anyone out there willing to divulge their idea(s), implemented in practice or otherwise, for fast passed pawn identification in an array based board representation?

[mjlef]

In my old "mailbox" program NOW, I merely kept an incrementally updated value for each color and side which indicated the least advanced pawn rank for that side. Then to detect a passed pawn you just had to check the values of the appropriate files to see there was no opponent pawn in front of the pawn being score.

If I was to do it now, I would probably just add logic for each pawn move and pawn capture to maintain a list of the passed pawns. Slightly annoying to program, but then the info is always available.

Later versions of NOW had mailbox, but duplicated the pawn locations in 2 64 bit values. Detection passed pawns them is a simple mask operation, and once pawns are represented as bitmaps, isolated, doubled, backward, passed, open files.... all get a lot easier. It is a gentle way to learn about bitmaps without requiring the whole program get converted at once.

[mvk]

While tinkering with a new array based engine I've realized that I am in need of a fast way to identify passed pawns.

I knew the naive approach would be kinda slow, but it's actually VERY slow.

Anyone out there willing to divulge their idea(s), implemented in practice or otherwise, for fast passed pawn identification in an array based board representation?

I have a 10-element array approach in the study engine I'm working from time to time (which doesn't play chess yet, but that is not the purpose):

Declaration of helper arrays:

Code: Select all

        /*
         *  Maximum distance of pawn to rank1, for each file and both sides.
         *  And then the same from rank8 point of view.
         *  Used to detect open files, doubled pawns, passers, etc.
         */
        int maxPawnFromRank1[10][2];
        int maxPawnFromRank8[10][2];

In the board scan of evaluate:

Code: Select all

                case whitePawn:
                case blackPawn:
                        setMax(e.maxPawnFromRank1[1+fileIndex][side], rank ^ rank1);
                        setMax(e.maxPawnFromRank8[1+fileIndex][side], rank ^ rank8);

In the scoring part of evaluate:

Code: Select all

        for &#40;int fileIndex=0; fileIndex<8; fileIndex++) &#123;

                e.pawns&#91;white&#93; += evaluatePawn&#40;v,
                                              &e.maxPawnFromRank1&#91;1+fileIndex&#93;,
                                              &e.maxPawnFromRank8&#91;1+fileIndex&#93;,
                                              fileIndex,
                                              white,
                                              // ...

                e.pawns&#91;black&#93; += evaluatePawn&#40;v,
                                              &e.maxPawnFromRank8&#91;1+fileIndex&#93;, // flipped!
                                              &e.maxPawnFromRank1&#91;1+fileIndex&#93;,
                                              fileIndex,
                                              black,
                                              // ...

        &#125;

And in evaluatePawn:

Code: Select all

static int evaluatePawn(const int v[vectorLen],
                        const int maxPawnFromRank1[][2],
                        const int maxPawnFromRank8[][2],
                        int fileIndex,
                        int side,
                        // ...
{
        #define maxRank(i, j)  maxPawnFromRank1[i][j]

        int frontPawn = maxRank(0, side);

[... snip ...]

        /*
         *  Passer
         */

        if &#40;maxRank&#40;-1, xside&#41; <= frontPawn
         && maxRank&#40; 0, xside&#41; <= frontPawn
         && maxRank&#40;+1, xside&#41; <= frontPawn&#41;
                pawnScore += v&#91;passerA_0 + fileIndex&#93;
                           + v&#91;passerA_1 + fileIndex&#93; * &#40;frontPawn - 1&#41;
                           + v&#91;passerA_2 + fileIndex&#93; * &#40;frontPawn - 1&#41; * &#40;frontPawn - 2&#41; / 4;

[hgm]

I use basically the same method as Mark mentions: keep track of the most backward Pawn in every file (setting it to last rank if there are no Pawns in that file). Then detecting of a given Pawn is a passer is just a matter of comparing it with the rank of the most-backward opponent Pawns in its own file and the files next to it.

On several occasions I thought on how I could do this incrementally. This is rather cumbersome, though, because there are many situations in which the information changes. (Pawns move, capture, are captured. If they leave the file by capture or being captured you would have to scan the board to see what now becomes the rear-most Pawn in that file.)

The point is that, although doing it from scratch (starting from the Pawn section of a piece list) is somewhat expensive, the fact that you have a Pawn hash hides this cost so well that it becomes very difficult to compete with it through an incremental method that has to be performed on every MakeMove (and UnMake...). The only incremental stuff becomes the update of a 64-bit Pawn key, which is easily done through copy-modify.

In KingSlayer (formerly called Simple) I now do it as follows (in a function only called on a Pawn-hash miss, to replace the old entry):

Code: Select all

int
PawnEval(PawnInfo *info)
{
  int i, sq, pawnFiles, w=0, b=0, score = 0;
  char white[8], black[8], rearWhite[10], rearBlack[10];

  for&#40;i=0; i<10; i++) rearWhite&#91;i&#93; = 0x70, rearBlack&#91;i&#93; = 0; // initialize most backward Pawn for each file
  info->passer&#91;0&#93; = info->passer&#91;1&#93; = -1;                    // invalid square number means no passer
  ...

  // create pawn list
  for&#40;sq=1*16; sq<7*16; sq=sq+9&~8&#41; &#123; // scan Pawn area of 0x88 board rank by rank
    int piece = board&#91;sq&#93;;
    if&#40;piece == WHITE+PAWN&#41; white&#91;w++&#93; = sq; else // and create pawn lists
    if&#40;piece == BLACK+PAWN&#41; black&#91;b++&#93; = sq;      // for white and black separately
  &#125;

  // determine rear guards
  for&#40;i=w-1; i >= 0; i--) &#123;
    sq = white&#91;i&#93;;
    rearWhite&#91;&#40;sq & 7&#41; + 1&#93; = sq & 0x70; // because of scan order last is always most backward
  &#125;
  for&#40;i=0; i<b; i++) &#123;
    sq = black&#91;i&#93;;
    rearBlack&#91;&#40;sq & 7&#41; + 1&#93; = sq & 0x70;
  &#125;

  // determine pawn types
  pawnFiles = 0;
  for&#40;i=w-1; i>=0; i--) &#123;                                                   // loop through white Pawns, high to low rank
    int d, r = &#40;sq = white&#91;i&#93;) & 0x70, f = sq & 7;                          // get file and rank
    ...
    if&#40;!&#40;pawnFiles & 1<<f&#41; &&                                               // only first (= most forward Pawn&#41; in file
       r >= rearBlack&#91;f&#93; && r >= rearBlack&#91;f+1&#93; && r >= rearBlack&#91;f+2&#93;) &#123;   // Pawn is passer
      score += pst&#91;PASSER+WHITE&#93;&#91;sq&#93;;                                       // give position-dependent bonus for that
      if&#40;f == 0 || f == 7&#41; info->passerFlags |= 0x10;                       // remember passer is on edge file
      if&#40;f != 0 && board&#91;sq-17&#93; == WHITE+PAWN ||                            // test for Pawns diagonally behind it
         f != 7 && board&#91;sq-15&#93; == WHITE+PAWN   ) &#123;                         // we have protected passer!
        info->passerFlags |= 1;                                             // flag that fact
        score += PROTPASS + &#40;r == 0x60&#41;*PROTPASS7;                          // flag that fact, and give bonus
      &#125;
      if&#40;info->passer&#91;0&#93; < 0&#41; &#123;                                             // first passer &#40;and thus most forward&#41;
        info->passer&#91;0&#93;= sq;                                                // remember its location
        info->promoSqr&#91;0&#93; = sq | 0x70;                                      // promotion square
        d = dist&#91;sq - &#40;sq|0x70&#41;&#93;; info->promoDist&#91;0&#93; = d - &#40;d == 6&#41;;        // and promotion distance &#40;in moves&#41;
      &#125; else info->passerFlags |= 4;                                        // multiple passers, just flag
    &#125;
    ...
  &#125;
  ...
  for&#40;i=0; i<b; i++) &#123;
    int d, r = &#40;sq = black&#91;i&#93;) & 0x70, f = sq & 7;                          // get file and rank
    ...
    if&#40;!&#40;pawnFiles & 1<<f&#41; &&                                               // only first (= most forward Pawn&#41; in file
       r <= rearWhite&#91;f&#93; && r <= rearWhite&#91;f+1&#93; && r <= rearWhite&#91;f+2&#93;) &#123;   // Pawn is passer
      score -= pst&#91;PASSER+BLACK&#93;&#91;sq&#93;;                                       // give position-dependent bonus for that
      if&#40;f == 0 || f == 7&#41; info->passerFlags |= 0x20;                       // remember passer is on edge file
      if&#40;f != 0 && board&#91;sq+15&#93; == BLACK+PAWN ||                            // test for Pawns diagonally behind it
         f != 7 && board&#91;sq+17&#93; == BLACK+PAWN   ) &#123;                         // we have protected passer!
        info->passerFlags |= 2;                                             // flag that fact
        score -= PROTPASS + &#40;r == 0x10&#41;*PROTPASS7;                          // and give bonus
      &#125;
      if&#40;info->passer&#91;1&#93; < 0&#41; &#123;                                             // first passer &#40;and thus most forward&#41;
        info->passer&#91;1&#93;= sq;                                                // remember its location
        info->promoSqr&#91;1&#93; = f;                                              // promotion square
        d = dist&#91;sq - f&#93;; info->promoDist&#91;1&#93; = d - &#40;d == 6&#41;;                // and promotion distance &#40;in moves&#41;
      &#125; else info->passerFlags |= 8;                                        // multiple passers, just flag
    &#125;
    ...
  &#125;
  ...
  info->score = score; // white POV score
&#125;

I deleted stuff not associated with passers, like backward/doubled Pawns (which can easily be determined based on the same info), Pawn shields around the default King locations (after castling) etc.

Note KingSlayer does not even have a piece list, so the first step is creating the Pawn sections of such a piece list by scanning the board...

IMO with modern hardware more could be gained by improving the hashing algorithm (increasing hit rate or access time) than by trying to speed up the actual calculation. A RAM access would probably still be cheaper than the calculation of everything you want to calculate about Pawns, so you could take a huge table that would virtually never cause a miss and use a much smaller table with copies of recently-used values that easily fits in L2/L3 and satisfies >90% of the demand.

[Rebel]

While tinkering with a new array based engine I've realized that I am in need of a fast way to identify passed pawns.

I knew the naive approach would be kinda slow, but it's actually VERY slow.

Anyone out there willing to divulge their idea(s), implemented in practice or otherwise, for fast passed pawn identification in an array based board representation?

I incrementally maintain an 10 byte pawn table for white and black. From the start position it looks like this:

Code: Select all

+----+----+----+----+----+-----+----+---+----+----+   
|  0 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  0 |   [ black ]
+----+----+----+----+----+----+----+----+----+----+
|  9 |  2 |  2 |  2 |  2 |  2 |  2 |  2 |  2 |  9 |   [ white ]
+----+----+----+----+-----+----+---+----+----+----+
        a    b    c    d    e    f    g    h  

Then for detecting a passer a maximum of 3 "if's" suffices. In case of double pawns use the pawn that has advanced most.

[Volker Annuss]

You can use a pawn hash table to speed up the evaluation of pawns.

If you need to carry the position of passers to other parts of the evaluation (you may want to evalutate blocked or threatened squares in front of passers) you can put the position of all passers found into the pawn hash table and pass a pointer to the pawn hash table entry to other functions.

Each side has at most 8 passers even in pathological cases. That's 16 bytes per entry. My pawn hash table has 80 bytes per entry.

[zd3nik]

Excellent feedback everyone. Thanks!

I am actually using 2 file arrays as well, but with extra logic to identify potential passers (which I actually don't have working quite right yet). And I'm setting high bits in each file to mark the file as containing a passed|backward|supported pawn - for use in eval of other pieces (bonus for rooks behind passers, etc). That potential passer code, and perhaps the masking I need to occasionally do to deal with those high bit markers, is probably why it's so slow.

Mark, I agree that doing passer detection with bitboards is pretty trivial, and that's the way I usually do it. However, for "fun", I'm trying to see how fast I can make this engine without using bitboards. Pointless, I know. But so are the other couple dozen chess engines I've written: pointless. I just like writing them. Tinkering with new ideas. See if I can make it work. Then drop it and try a new engine...

Marcel, I like your idea of keeping both the most advanced and least advanced positions per file. Perhaps I can adapt this into something that works for potential passer detection without too much overhead. If I figure something out I'll post it here (or just make the engine open source when I'm done). I'm not sure how to properly incorporate your xor trick though - seems like that would only work for the first pawn per file.

[zd3nik]

Marcel,
... I'm not sure how to properly incorporate your xor trick though - seems like that would only work for the first pawn per file.

Nevermind. For some reason my brain interpreted:

Code: Select all

                case whitePawn: 
                case blackPawn: 
                        setMax(e.maxPawnFromRank1[1+fileIndex][side], rank ^ rank1); 
                        setMax(e.maxPawnFromRank8[1+fileIndex][side], rank ^ rank8); 

as the following (with the assumption that maxPawnFromRank1 is initialized with rank1 and maxPawnFromRank8 is initialized with rank8):

Code: Select all

                case whitePawn: 
                case blackPawn: 
                        e.maxPawnFromRank1[1+fileIndex][side] ^= rank; 
                        e.maxPawnFromRank8[1+fileIndex][side] ^= rank; 

[sje]

Use a transposition table for pawn structures where each entry contains, possibly along with other data, a bitboard with passed pawn locations. With a sufficiently large table capacity, the hit rate on a pawn structure transposition table will be 99+%, and so the total calculation time for detecting passed pawns won't be very significant because the calculation won't be performed very often.

[mvk]

Marcel,
... I'm not sure how to properly incorporate your xor trick though - seems like that would only work for the first pawn per file.

Nevermind. For some reason my brain interpreted:

Code: Select all

[...snip...]

Indeed. The '^ rank1' operation ensures that the counting starts from the point of view of rank 1, and the opposite for '^ rank8'. I try to write this program without propagating the underlying square indexing throughout the code. So far, that results in symmetric and slightly better self-documenting code, so I like that experiment. But if it confused you here, maybe it is not clear enough. Maybe the 'setMax' macro is obfuscating things a bit too much. Thanks for your feedback.

BTW, updating only 'max'es is instead of both 'min' and 'max' is a bit easier because you can initialize the arrays with zeroes. So I did it from both rank1 and rank8 point of view, and got rid of the pawn move direction as well while doing so.

Of course, everything can be sped up by hiding it behind a hash table, as many have pointed out. This program doesn't have that because it is a study for a different purpose. I might convert it into a playing program and release it as MSCP v2 however.