SEE algorithm

[Robert Pope]

Is there a good write-up on this anywhere? I can figure out the pieces and the order easily enough, but I am trying to figure out how to best back up the score for SEE, since either person can opt out before all the captures are exhausted.

I saw this comment in GNUChess:

* When performing the "captures", we stop if one side is ahead
* and doesn't need to capture, a form of pseudo-minimaxing.

That doesn't seem like the right rule for stopping to me, but I'm not quite sure what the rule ought to be.

[Pradu]

The algorithm can be more advanced. Instead of "pseudo-minimaxing", you can do alphabeta in SEE. The tree will basically be nullmove on the left branch and capture on the right branch. See: http://www.vpittlik.org/wbforum/viewtopic.php?t=6104

[Mangar]

Hi,

in SEE you calculate the Material the side to move can gain by capture/recapture/re-recapture ... on a single square.
There are two special rules for SEE:

1. Captures can allways been done with the "lowest" piece. If there are multiple pieces with the same value you can take anyone of them.

2. You can allways do nothing and terminate the captures. It´s not a nullmove as then the opponent will be at move again.

You can stop whenever you are sure that doing nothing is better than capturing.
Imagin you can capture a pawn with a rook and a queen. The pawn is protected by another pawn.
Now you will capture the pawn with the rook:
Gain +1
The pawn recapture (if a rook = 5 pawn in SEE):
Gain -4
Max Gain in next capture: 1 (another pawn).
As -4 + 1 < 0 you can stop.
No need to try to capture the second pawn with the queen.

Thus use alpha, beta and a forewardpruning to test if capturing the next piece will reenter the window.

If you whant you can take care of pinned pieces. I think its worth doing it.

Greetings Volker

[Tord Romstad]

Is there a good write-up on this anywhere? I can figure out the pieces and the order easily enough, but I am trying to figure out how to best back up the score for SEE, since either person can opt out before all the captures are exhausted.

Hi Robert,

Here is my SEE from Glaurung 2. It is very simple and straightforward, and does not use any tricks like alpha/beta pruning. It also does not consider pins. I have tried both of these in the past, but decided that they do not give enough benefits to compensate for the increased complexity of code.

The code is bitboard based, but it should be easy to adapt the algorithm to other board representations. I have done my best to make the code readable, and have added plenty of comments. Because one of the main goals of my program is to serve as an instructional example (even when I have to sacrifice some speed or strength for simplicity), questions and criticisms about the code are very welcome.

Tord

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, b;

  assert(square_is_ok(from));
  assert(square_is_ok(to));

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

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

  // Find all attackers to the destination square, 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;

  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 at least one attacker left.
    for(pt = PAWN; !(attackers&this->pieces_of_color_and_type(c, pt)); pt++)
      assert&#40;pt < KING&#41;;

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

    // Add the new entry to the swap list&#58;
    assert&#40;n < 32&#41;;
    swapList&#91;n&#93; = -swapList&#91;n - 1&#93; + lastCapturingPieceValue;
    n++;

    // Remember the value of the capturing piece, and change the side to move
    // before beginning the next iteration&#58;
    lastCapturingPieceValue = seeValues&#91;pt&#93;;
    c = opposite_color&#40;c&#41;;

    // Stop after a king capture&#58;
    if&#40;pt == KING && &#40;attackers & this->pieces_of_color&#40;c&#41;)) &#123;
      assert&#40;n < 32&#41;;
      swapList&#91;n++&#93; = 100;
      break;
    &#125;
  &#125; while&#40;attackers & this->pieces_of_color&#40;c&#41;);

  // 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&#58;
  while&#40;--n&#41; swapList&#91;n-1&#93; = Min&#40;-swapList&#91;n&#93;, swapList&#91;n-1&#93;);

  return swapList&#91;0&#93;;
&#125;

[Pradu]

You can allways do nothing and terminate the captures. It´s not a nullmove as then the opponent will be at move again.

Sorry I meant "do nothing" not "nullmove" in my post. Thanks for pointing out my mistake.

[Pradu]

...does not use any tricks like alpha/beta pruning...decided that they do not give enough benefits to compensate for the increased complexity of code.

Alphabeta pruning is relatively simple to add. Only an additional 9 lines of code so it's worth a try. I think it should be as simple to implement and read when compared to keeping a history of SEE scores and minimaxing backwards at the end and it should perform as fast.

[Pradu]

I just did a quick test. On the initial position the ratio (SEEcutoffs inside the movemaking loops)/SEEcalls is about 0.06%-0.08% and increases with search depth. On a random middle game position (2k3r1/1ppq1r2/p2bp2Q/3p1ppp/3PN3/P3PP2/1PP3PP/R4RK1 b) the ratio varies between 0.1%-0.3%.

[Tord Romstad]

...does not use any tricks like alpha/beta pruning...decided that they do not give enough benefits to compensate for the increased complexity of code.

Alphabeta pruning is relatively simple to add.

I know. I have tried it and discarded it before, as I wrote

Only an additional 9 lines of code so it's worth a try.

From my point of view, 9 extra lines of code is far too much for something that makes no difference whatsoever except possibly an infinitesimal speed improvement. I am much more inclined to remove micro-optimizations like this than to add new ones. My program is already too big and complex, and it is quite likely that I will sacrifice some speed for simplicity in the next version.

Tord

[hgm]

In a SEE alpha-beta pruning is only a single line of code, not? In the non-recursive implementation of alpha-beta I use for SEE, it shows up as futility pruning: don't even try the next capture in line if it doesn't get you above alpha.

A SEE is just a normal minimax search, where in each node you can do only one move, or stand pat. The 'branches' where you stand pat terminate immediately, so you get in practice an unbranched tree.

Most of the complexity of my SEE comes from keeping track of the x-rays, and checking if the capturing piece is pinned on the King (which I only do in the first capture, to make sure the move a good SEE comes up with is a legal one). Not from the alpha-beta implementation.