Passed pawn detection in array based board representations

[hgm]

If I would have to design an original incremental method, I would come up with the following:

For each Pawn in the piece list keep a byte with flags that indicate which enemy Pawns prevent it from being a passer (where each bit posiiton corresponds to an index in the Pawn section of the piece list). In the initial position each Pawn would have 2 (rook Pawns) or 3 'opposers'. Note that the relation is always reciprocal.

If a Pawn that still has opposers moves forward, any opposers now next to it (or for a double-push also diagonally behind it) as seen on the board get their flag cleared, and the moving Pawn's flag gets cleard in their flags byte.

If a Pawn is captured, its bit is cleared from the flags of its opposers. Note that the flags for each of the 8 Pawns could be packed into an int64, so that you might clear the bit corresponding to the captured Pawn by masking the int64, and there is no need to do it selectively.

If a Pawn captures, you loop through all its opposers. Any opposer on the file it captures away from would get its bit cleared in the flags of the moving Pawn, and those opposers would get the bit corresponding to the mover cleared in their flags. An opposer that was on the square in front of you is likewise removed. Opposers on the file you capture to stay opposers (unless they were captured, but this is handled as part of their capture). That only leaves the creation of a new opposer in the new neighboring file in the direction in which you captured. For this you hav to scan that file on the board. This sounds worse than it is, as any capture would bring you already on 3rd rank, so that opposers could only be on 4th-7th rank (4 squares). How many of the moves are captures with Pawns anyway?

[hgm]

Of course in the above proposal it is stupid to maintain the opposer info per Pawn, if the relation is reciprocal. So one should just use a single 8x8 matrix of bits, ('stops') remeniscent to a bitboard, but having a completely different meaning: each row corresponds to a white Pawn, each column to a black Pawn. A bit is set if the corresponding white and black Pawn are preventing each other from being a passer.

In the piece list you store a mask with each piece (stopCode[]) that indicates which eight bits (row or column) in 'stops' correspond to the piece; for non-Pawns this would be 0. With

Code: Select all

if((stops & stopCode[pawnNr]) == 0) ... 

you can test if the indicated pawn is a passer.

During MakeMove you clear the bits belonging to the captured piece:

Code: Select all

stops &= ~stopCode[victim];

When a Pawn is pushed you clear the stops due to the Pawns it passes. If it changes file by capturing we have to clear the stops in the file it moves away from, and add new ones in the new file it neigbors:

Code: Select all

void Pass(int pawnNr, int sqr)
{
  int p = board[sqr];
  stops &= ~(stopCode[pawnNr] & stopCode[p]);
}

void AddStop(int pawnNr, int sq)
{
  int p = board[sqr];
  stops |= (stopCode[pawnNr] & stopCode[p]);
}

// in MakeMove
if(IS_PAWN(pieceNr)) {
  if((to - from) & 7) { // capture
    uint64 opposers = stops & stopCode[pieceNr];
    int file = 2*from - to & 7; // file we move away from
    int forward = Forward(stm); // 16 or -16 on 0x88 board
    int sq;
    Pass(pieceNr, from + forward);
    while(opposers) {
      uint64 next = opposers & -opposers;
      opposers -= next;
      opposerNr = bit2oppo[BitNr(next)];
      sq = location[opposerNr];
      if((sq & 7) == file) Pass(pieceNr, sq);
    }
    for(sq = 2*to - from; IN_PAWN_ZONE(sq); sq += forward)
      AddStop(pieceNr, sq);
  } else { // non-capture
    Pass(pieceNr, to+1); // K-side neighbor
    Pass(pieceNr, to-1); // Q-side neighbor
    if((from - to & 1) == 0) { // double-push
      int ep = to ^ 0x10; // shift one rank
      Pass(pieceNr, ep+1); // K-side neighbor
      Pass(pieceNr, ep-1); // Q-side neighbor
    }
  }
}

Still, I believe this kind of incremental update could never be competitive with just updating a Pawn key and use it to access hashed results of a slow 'from-scratch' calculation.