SEE with magic bitboards

[Pradu]

I've rewritten a bitscan-free x-raying SEE optimized for magic bitboards. The basic idea is that one can assume that a piece behind another piece is always of a greater or equal value. This way order of captures in battery doesn't matter. The exception is for the queen for which new attackers must be generated. Any comments or suggestions on this approach?

Code: Select all

//the board structure
typedef struct _board //104 bytes
{
   U64   AllPieces;                 //All the pieces on the board
   U64   PiecesSide[2];             //All the pieces belonging to each side
   U64   Pieces[NUMPIECETYPES];     //Specific pieces on the board eg Pieces[R]
   U64   hashkey;                   //the hash key for the transposition table
   unsigned char PieceTypes[64];    //All the piece types according to squares
   unsigned char KingPos[2];        //King position for a side
   unsigned char EP;                //The enpassant square
   unsigned char castling;          //Castling privilages - format defined below
   unsigned char fifty;             //Fifty move count
   unsigned char SF;                //Search Flags (see Search Related section)
   bool side;                       //the side to play
   bool xside;                      //the side opposite to play
}board;

#define LSB(X) ((X)&-(X))

//full static exchange evaluvation
int SEE(const board* pos, const move m)
{
   //The variables are set to the inital state where the move in question has been played
   int SEEscore=pieceValue[extractCapture(m)]; //The score to be returned
   int SEEmax, SEEmin; //Maximum and minimum SEE scores (alphbeta approach)
   int target=extractTo(m); //The square that we are doing a SEE on
   int currentPieceValue=pieceValue[extractPiece(m)]; //Value of the piece currently on the target square
   U64 used=toBit(extractFrom(m)); //Used attackers
   //Battery attacks will be calculated instead of regular attacks
   //Piece order isn't a problem (except when dealing with Queens)
   U64 occupancy=(pos->AllPieces^used) &
       ~(pos->Pieces[B]|pos->Pieces[R]|( (pos->Pieces[P]) & (Pcaps(target,WHITE)|Pcaps(target,BLACK))));

   U64 attackers; //attackers of each piece type from both sides
   U64 attackersSide; //attackers for each piece type for a particular side
   U64 attackersPiece; //attackers for a particular color and a particular type

   //handle enpassant and promotion
   if(currentPieceValue==Pval)
   {
      if(extractEP(m))
      {
         used|=toBit(extractEP(m));
         occupancy^=toBit(extractEP(m));
         SEEscore=Pval;
      }
      else if(extractPromotion(m)!=E)
      {
         SEEscore+=pieceValue[extractPromotion(m)]-Pval;
         currentPieceValue=Qval
      }
   }

   //these are the bounds, we will be doing an alphabeta-like search in SEE
   SEEmax=SEEscore; //upperbound
   SEEmin=-INF; //lowerbound

   //Generate attackers
   attackers=attacksToOcc(*pos,target,occupancy)^used;

   //Loop Through Opponent Captures
   while(attackersSide=attackers&pos->PiecesSide[pos->xside])
   {
      SEEscore-=currentPieceValue;
      if(SEEscore>=SEEmax) return SEEmax;
      if(SEEscore>SEEmin) SEEmin=SEEscore;

      if(attackersPiece=attackersSide&pos->Pieces[P]) //Pawn
      {
         used|=LSB(attackersPiece);
         attackers^=LSB(attackersPiece);
         currentPieceValue=Pval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[N]) //Knight
      {
         attackers^=LSB(attackersPiece);
         currentPieceValue=Nval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[B]) //Bishop
      {
         attackers^=LSB(attackersPiece);
         used|=LSB(attackersPiece);
         currentPieceValue=Bval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[R]) //Rook
      {
         attackers^=LSB(attackersPiece);
         used|=LSB(attackersPiece);
         currentPieceValue=Rval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[Q]) //Queen
      {
         used|=LSB(attackersPiece);
         occupancy^=LSB(attackersPiece);
         attackers=attacksBQRToOcc(*pos,target,occupancy)^used;
         currentPieceValue=Qval;
      }
      else //King
      {
         attackers^=toBit(pos->KingPos[pos->xside]);
         currentPieceValue=Kval;
      }
      //Loop Through My Captures
      if(!(attackersSide=attackers&pos->PiecesSide[pos->side])) break;
      
      SEEscore+=currentPieceValue;
      if(SEEscore<=SEEmin) return SEEmin;
      if(SEEscore<SEEmax) SEEmax=SEEscore;

      if(attackersPiece=attackersSide&pos->Pieces[P]) //Pawn
      {
         used|=LSB(attackersPiece);
         attackers^=LSB(attackersPiece);
         currentPieceValue=Pval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[N]) //Knight
      {
         attackers^=LSB(attackersPiece);
         currentPieceValue=Nval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[B]) //Bishop
      {
         attackers^=LSB(attackersPiece);
         used|=LSB(attackersPiece);
         currentPieceValue=Bval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[R]) //Rook
      {
         attackers^=LSB(attackersPiece);
         used|=LSB(attackersPiece);
         currentPieceValue=Rval;
      }
      else if(attackersPiece=attackersSide&pos->Pieces[Q]) //Queen
      {
         used|=LSB(attackersPiece);
         occupancy^=LSB(attackersPiece);
         attackers|=attacksBQRToOcc(*pos,target,occupancy)&~used;
         currentPieceValue=Qval;
      }
      else //King
      {
         attackers^=toBit(pos->KingPos[pos->side]);
         currentPieceValue=Kval;
      }
   }
   if(SEEscore<SEEmin) return SEEmin;
   if(SEEscore>SEEmax) return SEEmax;
   return SEEscore;
}

[Tord Romstad]

You can easily avoid bitscans and still handle all X-ray attacks correctly. This is how my bitboard SEE currently looks. It seems fast enough, and is nowhere near the top in my profiler output, but as always, hints about obvious optimisations are welcome:

Code: Select all

int Position::see(Square from, Square to) const {
  // Approximate material values, with pawn = 1:
  static const int seeValues[18] = {
    0, 1, 3, 3, 5, 10, 100, 0, 0, 1, 3, 3, 5, 10, 100, 0, 0, 0
  };
  Color us, them;
  Piece piece, capture;
  Bitboard attackers, occ;

  // Initialize colors:
  us = this->color_of_piece_at(from);
  them = opposite_color(us);

  // Initialize pieces:
  piece = this->piece_at(from);
  capture = this->piece_at(to);

  // Find all attackers to the destination square, but with the moving piece
  // removed, but possibly an X-ray attacker added behind it:
  occ = this->occupied_squares();
  clear_bit(&occ, from);
  attackers =
    (rook_attacks_bb(to, occ) & this->rooks_and_queens()) |
    (bishop_attacks_bb(to, occ) & this->bishops_and_queens()) |
    (this->knight_attacks(to) & this->knights()) |
    (this->king_attacks(to) & this->kings()) |
    (this->white_pawn_attacks(to) & this->pawns_of_color(BLACK)) |
    (this->black_pawn_attacks(to) & this->pawns_of_color(WHITE));
  attackers &= occ;

  // If the opponent has no attackers, we are finished:
  if((attackers & this->pieces_of_color(them)) == EmptyBoardBB)
    return seeValues[capture];

  // The destination square is defended, which makes things rather more
  // difficult to compute.  We proceed by building up a "swap list" containing
  // the material gain or loss at each stop in a sequence of captures to the
  // destination square, where the sides alternately capture, and always
  // capture with the least valuable piece.  After each capture, we look for
  // new X-ray attacks from behind the capturing piece.
  int lastCapturingPieceValue = seeValues[piece];
  int swapList[32], n = 1;
  Color c = them;
  PieceType pt;
  Bitboard b;

  swapList[0] = seeValues[capture];

  do {
    // Locate the least valuable attacker for the side to move.  The loop
    // below looks like it is potentially infinite, but it isn't.  We know
    // that the side to move still has some attackers left.
    for(pt = PAWN; !(attackers&this->pieces_of_color_and_type(c, pt)); pt++)
      assert(pt <= KING);

    // Remove the attacker we just found from the 'attackers' bitboard,
    // and scan for new X-ray attacks behind the attacker:
    b = attackers & this->pieces_of_color_and_type(c, pt);
    occ ^= (b & -b);
    attackers |=
      (rook_attacks_bb(to, occ) & this->rooks_and_queens()) |
      (bishop_attacks_bb(to, occ) & this->bishops_and_queens());
    attackers &= occ;

    // Add the new entry to the swap list:
    swapList[n] = -swapList[n - 1] + lastCapturingPieceValue;
    n++;

    // Remember the value of the capturing piece, and change the side to move
    // before beginning the next iteration:
    lastCapturingPieceValue = seeValues[pt];
    c = opposite_color(c);
   
    // Stop after a king capture:
    if(pt == KING && (attackers & this->pieces_of_color(c))) {
      swapList[n++] = 100;
      break;
    }
  } while(attackers & this->pieces_of_color(c));

  // Having built the swap list, we negamax through it to find the best
  // achievable score from the point of view of the side to move:
  while(--n) swapList[n-1] = Min(-swapList[n], swapList[n-1]);

  return swapList[0];
}

Tord

[Pradu]

This doesn't sound correct at first glance. A captured promoted piece should only have a value of a pawn, not the promoted piece's value as it was a pawn to begin with.

It gains the value of a Q-P when played and looses it when captured. Code updated thanks for the bug.

And SEE after the EP capture? On which square?

On the square just captured

Also, your code shows the problems of bitboard implementations - you need to check each piece's bitboard to find what the attacker is.

All attackers are gotten in one go then each is picked off, in a chosen order.

There's an alternative to this : Find the least valueable attacker/defender pair in each loop and remove them from the "attackers list" until the set conditions are met - this is more like a QSearch the attacked square. I use this method, not with your magic btw :P

Well that's exactly what's done in my method. I don't need to check each piece's bitboard to find what the attacker is I just try to see if an attacker of the lowest value exist.

You had some explaining to do boy!

I always mess up
Andrew.

[Pradu]

You can easily avoid bitscans and still handle all X-ray attacks correctly. This is how my bitboard SEE currently looks. It seems fast enough, and is nowhere near the top in my profiler output, but as always, hints about obvious optimisations are welcome:

Strangely SEE is rather expensive in my program. Perhaps I'm using it incorrectly (SEEing all generated moves).

Code: Select all

    b = attackers & this->pieces_of_color_and_type(c, pt);
    occ ^= (b & -b);
    attackers |=
      (rook_attacks_bb(to, occ) & this->rooks_and_queens()) |
      (bishop_attacks_bb(to, occ) & this->bishops_and_queens());
    attackers &= occ;

Instead of a bitscan you do something twice as expensive here (2 move generations) for all captures. The thing is you could avoid bitscans and move generations by generating attacks in battery (except for the case of the queen).

Code: Select all

// Add the new entry to the swap list:
    swapList[n] = -swapList[n - 1] + lastCapturingPieceValue;
    n++;

You seem to keep track of a list of scores here and minimax back in the end. I guess instead of this you can keep track of upper and lower bounds and immediately return when cutoffs happen and no need to minimax in the end.

[Tord Romstad]

You can easily avoid bitscans and still handle all X-ray attacks correctly. This is how my bitboard SEE currently looks. It seems fast enough, and is nowhere near the top in my profiler output, but as always, hints about obvious optimisations are welcome:

Strangely SEE is rather expensive in my program. Perhaps I'm using it incorrectly (SEEing all generated moves).

Yes, SEEing all generated moves indeed sounds expensive. What do you use it for? Unless you use some unusual tricks, I am not sure it is a good idea to do SEE computations for all moves. For instance, in my experience, SEE values are not useful for move ordering of non-captures. I have tried to search all non-captures with negative SEE values (except killers) after the non-captures with SEE=0, but this doesn't seem to improve move ordering at all. This is very counter-intuitive to me, and I have no good explanation for it.

The main area where SEE is useful is to prune losing captures in the qsearch. Even there, you can reduce the use of SEE by observing that when the capturing piece has the same or lower value than the captured piece, the capture can never have negative SEE value. You can get away by SEEing only those captures where the capturing piece is more valuable than the captured piece.

This idea can also be taken a bit further, by writing a simplified SEE which doesn't produce an exact value, but only decides whether a capture is losing or not. This can often be done without finding all attackers. I haven't tried this, and have no idea whether it would be worth the effort (it probably depends on the program).

Code: Select all

    b = attackers & this->pieces_of_color_and_type(c, pt);
    occ ^= (b & -b);
    attackers |=
      (rook_attacks_bb(to, occ) & this->rooks_and_queens()) |
      (bishop_attacks_bb(to, occ) & this->bishops_and_queens());
    attackers &= occ;

Instead of a bitscan you do something twice as expensive here (2 move generations) for all captures. The thing is you could avoid bitscans and move generations by generating attacks in battery (except for the case of the queen).

Sorry, I didn't read your first post and your code carefully enough. I now see that your point wasn't just to avoid bitscans, but to avoid having to do a detailed analysis of X-ray attacks. Unfortunately, it seems to me that your approach won't work. The problem isn't just batteries with queens, but also when there are pieces of both colors along the same ray. For instance, consider the following two positions:

[diag]6k1/7p/8/7R/4B3/8/7r/4K3[/diag]

[diag]6k1/7p/8/7r/4B3/8/7R/4K3[/diag]

In the first position, Bxh7 is a winning capture, in the second position, it's a losing capture. I don't see how your SEE can figure out this without finding X-ray attackers in the correct order.

On the other hand, I agree that it isn't really necessary to scan for sliding attacks in all directions, like I do. It would be possible to make the code slightly faster at the expense of increased complexity, by adding a 'switch' statement on the type of the capturing piece (if it is a knight or king, no X-ray attack is possible, if it is a bishop, only diagonal X-rays are possible, etc.). At the moment, this doesn't seem to be worth the effort.

Code: Select all

// Add the new entry to the swap list:
    swapList[n] = -swapList[n - 1] + lastCapturingPieceValue;
    n++;

You seem to keep track of a list of scores here and minimax back in the end. I guess instead of this you can keep track of upper and lower bounds and immediately return when cutoffs happen and no need to minimax in the end.

You are right, but according to my profiler this isn't a bottleneck. Updating the swap list and executing the tiny loop at the end of the function takes almost no time. This isn't really surprising, considering that the number of attackers is usually very small.

Anyway, thanks for the suggestions!

Tord

[H.G.Muller]

It seems to me you are re-inventing alpha-beta pruning as applied to minimaxing in SEE!

The current SEE in Joker is just a non-recursive implementation of alpha-beta (with futility pruning) on a search that, besides standing pat, only considers recapture with the lowest (non-pinned?) piece. Instead of doing the moves I just mark the pieces used already, so that they become transparent for X-rays. There is no need to actually move the pieces to the to-square, since they will be immediately captured there. Ther is no UnMake, since you try stand-pat first, and after trying the single move, you won't try anything else.

I do it from a piece list, rather than a bitboard, but that hardly makes any difference, since bitboards are much like a piece list that stores multiple pieces of the same type per entry. The piece list is scanned in increasing order, so the deeper nodes of the search don't start at the beginning, but just continue from the last piece used before. Only if low pieces that are aligned with the target square are blocked by another piece, this piece is marked, and when a marked piece is used in the capture sequence, the piece list is 'rewound' to the piece blocked by it, for a retry. This guarantees proper handling of frustrated batteries (Queen before Bishop/Rook).

Nevertheless, there still are problems that I have not solved, related to those in the diagrams above: if it can capture with two Rooks, and one of them is backed by an enemy Rook, the other not, it picks one of them at random. That can make a big difference for the result, it should use the foe-backed Rook last to delay involvement of the enemy Rook as long as it can.

Also in table-driven SEEs foe-backing cause tremendous complications. It seemed I found a way to do it, but I never got to implement all the details.

By the way, Joker does SEE non-captures just before searching them, to postpone those with negative SEE to the end. It never occurred to me that this could be counterproductive. Based on your observation, I might reconsider it. I guess in alpha nodes any effort spend on move ordering is a waste. But what you do in internal nodes usually hardly has any impact (because there are too few), and in frontier nodes non-captures are futile if eval <= alpha. So the fact that you want to search them means that eval > alpha, (and most likely beta=alpha+1...), so it does not seem hopeless to find a cut-move amongst the non-captures. Non-captures with bad SEE will almost certainly not do it, though, and SEE is far cheaper than really searching them. The snag might be that you only get into this situation if the null move failed to cut you. So there is a threat, and the move to deal with the threat might be hard to find. If you find it randomly, after 15 tries, or so, you would have done 15 SEEs. Not many moves might have bad SEE, so without SEE you might have found it after 20 moves. So you have to compare the search time of 5 moves to that of 15 SEEs.

On the other hand, if the null move scores only marginally below beta, there is no real threat (just the move-lead advantage), and trying the non-captures in order of expected positional merit (e.g. based on piece-square) will make you find a cut-move quite quickly. In that case postponing those with bad SEE seems a worthwile investment.

So I guess I will switch to searching the null move with window {beta-50, beta} (centiPawn), rather than {beta-1,beta}, to make sure I can determine the type of threat (material, positional or move-lead), and determine how to handle it (concentrating on finding moves to counter the specific threat, or just go for my own plan).

[Pradu]

Yes, SEEing all generated moves indeed sounds expensive. What do you use it for?

I use it to order all moves and if a move is a losing it gets sent to the back of the list. My engine isn't mature enough to try things like LMR or other pruning techniques yet so I'm not sure if it can be helpful to detect and prune these moves.

Unless you use some unusual tricks, I am not sure it is a good idea to do SEE computations for all moves. For instance, in my experience, SEE values are not useful for move ordering of non-captures.

I think your right because the best move is usually ordered up front and you get cutoffs.

I have tried to search all non-captures with negative SEE values (except killers) after the non-captures with SEE=0, but this doesn't seem to improve move ordering at all. This is very counter-intuitive to me, and I have no good explanation for it.

The main area where SEE is useful is to prune losing captures in the qsearch. Even there, you can reduce the use of SEE by observing that when the capturing piece has the same or lower value than the captured piece, the capture can never have negative SEE value. You can get away by SEEing only those captures where the capturing piece is more valuable than the captured piece.

This idea can also be taken a bit further, by writing a simplified SEE which doesn't produce an exact value, but only decides whether a capture is losing or not. This can often be done without finding all attackers. I haven't tried this, and have no idea whether it would be worth the effort (it probably depends on the program).

Perhaps a parallel SEE could be used for the isLosing. I'm not quite sure if it would be faster when there are few captures available.

Sorry, I didn't read your first post and your code carefully enough. I now see that your point wasn't just to avoid bitscans, but to avoid having to do a detailed analysis of X-ray attacks. Unfortunately, it seems to me that your approach won't work. The problem isn't just batteries with queens, but also when there are pieces of both colors along the same ray. For instance, consider the following two positions:

You are correct.

On the other hand, I agree that it isn't really necessary to scan for sliding attacks in all directions, like I do. It would be possible to make the code slightly faster at the expense of increased complexity, by adding a 'switch' statement on the type of the capturing piece (if it is a knight or king, no X-ray attack is possible, if it is a bishop, only diagonal X-rays are possible, etc.). At the moment, this doesn't seem to be worth the effort.

I agree, simplicity is best. But perhaps instead of a switch one could unroll the "getting lowest value piece" loop.

You are right, but according to my profiler this isn't a bottleneck. Updating the swap list and executing the tiny loop at the end of the function takes almost no time. This isn't really surprising, considering that the number of attackers is usually very small.

Anyway, thanks for the suggestions!

Tord

[Pradu]

So I guess I will switch to searching the null move with window {beta-50, beta} (centiPawn), rather than {beta-1,beta}, to make sure I can determine the type of threat (material, positional or move-lead), and determine how to handle it (concentrating on finding moves to counter the specific threat, or just go for my own plan).

Intresting idea to use bigger windows to find the type of threat, but how do you determine how to handle the threat after you find it?

[H.G.Muller]

If the null move failed low by about the score of the average non-tactical move (say ~15 centiPawn), I would try to beat it with my own best positional move, i.e. sort the non-captures on piece-square merit, and try them if they have non-negative SEE.

If a more evere threat was a non-capture, it is unlikely that our own best move is going to beat it, and the emphasis should ly on trying to prevent that move. I would sort all non-captures that attack the to-field of the dreaded move in front (least-valuale piece first). I probably would screen them by SEE. If it is too expensive to screen all my moves for attacking a given square (although this should be much cheaper than a SEE), I would just try the non-captures unsorted, without SEEing, because it is a blind search.

If the threat is a capture, I would also try that, but I would search all moves that evacuate the to-square first. (These, at least, are quite trivial to find.) Here I would certainly subject them to SEE before trying, because the first evacuation that works is likely to provide the cut move. (Also sort by piece-square, btw.)

(If a non-capture threat is a Pawn move, all moves to the to-square in order to block it should be treated the same as moves that attack the to-square.)