SEE algorithm on chessprogramming wiki

[hgm]

I don't think this issue can be fully clear without exactly seeing what is involved in the itertive version. So let me have a stab at this:

This is the regular alpha-beta search as applied to SEE, where there is no loop over moves, as at any stage we only try stand pat or the capture to the given target with the lowest attacker:

Code: Select all

int SEE(int apha, int beta, int eval)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  // FOR ALL MOVES
  MakeNextCapture();
  score = -SEE(-beta, -alpha, -(eval + PieceValue[victim]));
  UnMake();
  if(score > alpha) alpha = score;
  // NEXT MOVE
  return alpha;
}

Note that with fail-hard, the returned score will be at least alpha, so the update of alpha can be made unconditionally, and the code becomes:

Code: Select all

int SEE(int apha, int beta, int eval)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  MakeNextCapture();
  alpha = -SEE(-beta, -alpha, -(eval + PieceValue[victim]));
  UnMake();
  return alpha;
}

Now note that this is a 'tail recursion' except for the UnMake(). So after we reach the deepest level, the whole thing unwinds by doing a series of UnMakes. Now the representation we use during a SEE is usually not a board, but some sorted lists of captures to the given square, made at the beginning. And we do not want to use these lists again; after we are done wth the SEE, we will just discard them. So there really is no reason to UnMake() anything at all, and UnMake() is a no-op. Even the MakeNextCapture() is usually not more than remembering which piece is on the target square after the move (and perhaps activating X-ray pieces that were behind the used piece by adding them to the list). So we get:

Code: Select all

int SEE(int apha, int beta, int eval, int victim)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  victim = NextPieceOfAttackersList(); // attacker is now on target square
  alpha = -SEE(-beta, -alpha, -eval, victim);
  return alpha;
}

This negamax formulation still involves flipping the sign of alpha a number of times while unwinding; to make it into an iterative version it is thus more efficient to 'unroll' that iteration in pairs, so that white and black use different code. As preparation for this, first the recursive version:

Code: Select all

int MySEE(int apha, int beta, int eval, int victim)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  victim = NextPieceOfMyAttackersList(); // attacker is now on target square
  return HisSEE(beta, alpha, eval, victim);
}

int HisSEE(int apha, int beta, int eval, int victim)
{
  if&#40;eval <= beta&#41; return beta; // stand pat produces &#40;fail-hard&#41; cutoff
  if&#40;eval < alpha&#41; alpha = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
  return MySEE&#40;beta, alpha, eval, victim&#41;;
&#125;

So we made a HisSEE version for the opponent where alpha, beta and eval by convention all use opposite signs from those in MySEE. This means also that all comparisons have been flpped to the opposite comparison there (i.e. >= becomes <=, etc.). Finally we swap the dummy parameter names alpha and beta in HisSee, to harmonize the naming with that in MySEE (which was calling HisSEE with actual value alpha for the formal parameter beta, and vice versa):

Code: Select all

int HisSEE(int beta, int alpha, int eval, int victim)
{
  if&#40;eval <= alpha&#41; return alpha; // stand pat produces &#40;fail-hard&#41; cutoff
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
  return MySEE&#40;alpha, beta, eval, victim&#41;;
&#125;

So now we have a true tail recursion, which can be trivially converted to an iteraton, where every internal return simply breaks out of the loop, and the return at the end starts the next iteration:

Code: Select all

eval = 0;
while(1)
{
  // MySEE part
  if(eval >= beta) {result = beta; break; }// stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  victim = NextPieceOfMyAttackersList(); // attacker is now on target square
  // HisSee part
  if&#40;eval <= alpha&#41; &#123; result = alpha; break; &#125; // stand pat produces &#40;fail-hard&#41; cutoff
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
&#125;

A slight optimization puts the stand-pat tests to before 'making' the next move, corresponding to the well-known futility-pruning in the recursive implementation:

Code: Select all

eval = 0;
while(1)
{
  // MySEE part
  if(eval >= beta) {result = beta; break; }// stand pat produces (fail-hard) cutoff
  victim = NextPieceOfHisAttackersList(); // attacker is now on target square
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  // HisSee part
  if&#40;eval <= alpha&#41; &#123; result = alpha; break; &#125; // stand pat produces &#40;fail-hard&#41; cutoff
  victim = NextPieceOfMyAttackersList&#40;); // attacker is now on target square
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
&#125;

This made the taking of the next piece from 'his' list of attackers wrap around to the previous iteration, which can be corrected by putting the original content of the square as first element in this list. An aternative would be to skip the first three statements on the first iteration: the comparison for cut-off is not likely to be useful there (or coud be done outide of the loop) as we want to start with beta = INFINITE in the SEE root. And we do not want to allow stand-pat before the side to move actually captures anything; the first move must be forced (and not necessarily by the LVA). This transforms the loop to:

Code: Select all

eval = 0;
victim = board[targetSquare];
while(1)
{
  eval += PieceValue[victim];
  if&#40;eval <= alpha&#41; &#123; result = alpha; break; &#125; // stand pat produces &#40;fail-hard&#41; cutoff
  victim = NextPieceOfMyAttackersList&#40;); // attacker is now on target square
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  if&#40;eval >= beta&#41; &#123;result = beta; break; &#125;// stand pat produces &#40;fail-hard&#41; cutoff
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
  if&#40;eval > alpha&#41; alpha = eval; // this is the crucial alpha update
&#125;

So the bottom line is that proper implementation of alpha-beta only adds a single conditional move to each original (i.e. non-unrolled) iteration of the SEE loop, to update alpha or beta. I don't think that would be a very large computational burdon.

[bob]

I don't think this issue can be fully clear without exactly seeing what is involved in the itertive version. So let me have a stab at this:

This is the regular alpha-beta search as applied to SEE, where there is no loop over moves, as at any stage we only try stand pat or the capture to the given target with the lowest attacker:

Code: Select all

int SEE(int apha, int beta, int eval)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  // FOR ALL MOVES
  MakeNextCapture();
  score = -SEE(-beta, -alpha, -(eval + PieceValue[victim]));
  UnMake();
  if(score > alpha) alpha = score;
  // NEXT MOVE
  return alpha;
}

Note that with fail-hard, the returned score will be at least alpha, so the update of alpha can be made unconditionally, and the code becomes:

Code: Select all

int SEE(int apha, int beta, int eval)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  MakeNextCapture();
  alpha = -SEE(-beta, -alpha, -(eval + PieceValue[victim]));
  UnMake();
  return alpha;
}

Now note that this is a 'tail recursion' except for the UnMake(). So after we reach the deepest level, the whole thing unwinds by doing a series of UnMakes. Now the representation we use during a SEE is usually not a board, but some sorted lists of captures to the given square, made at the beginning. And we do not want to use these lists again; after we are done wth the SEE, we will just discard them. So there really is no reason to UnMake() anything at all, and UnMake() is a no-op. Even the MakeNextCapture() is usually not more than remembering which piece is on the target square after the move (and perhaps activating X-ray pieces that were behind the used piece by adding them to the list). So we get:

Code: Select all

int SEE(int apha, int beta, int eval, int victim)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  victim = NextPieceOfAttackersList(); // attacker is now on target square
  alpha = -SEE(-beta, -alpha, -eval, victim);
  return alpha;
}

This negamax formulation still involves flipping the sign of alpha a number of times while unwinding; to make it into an iterative version it is thus more efficient to 'unroll' that iteration in pairs, so that white and black use different code. As preparation for this, first the recursive version:

Code: Select all

int MySEE(int apha, int beta, int eval, int victim)
{
  if(eval >= beta) return beta; // stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  victim = NextPieceOfMyAttackersList(); // attacker is now on target square
  return HisSEE(beta, alpha, eval, victim);
}

int HisSEE(int apha, int beta, int eval, int victim)
{
  if&#40;eval <= beta&#41; return beta; // stand pat produces &#40;fail-hard&#41; cutoff
  if&#40;eval < alpha&#41; alpha = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
  return MySEE&#40;beta, alpha, eval, victim&#41;;
&#125;

So we made a HisSEE version for the opponent where alpha, beta and eval by convention all use opposite signs from those in MySEE. This means also that all comparisons have been flpped to the opposite comparison there (i.e. >= becomes <=, etc.). Finally we swap the dummy parameter names alpha and beta in HisSee, to harmonize the naming with that in MySEE (which was calling HisSEE with actual value alpha for the formal parameter beta, and vice versa):

Code: Select all

int HisSEE(int beta, int alpha, int eval, int victim)
{
  if&#40;eval <= alpha&#41; return alpha; // stand pat produces &#40;fail-hard&#41; cutoff
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
  return MySEE&#40;alpha, beta, eval, victim&#41;;
&#125;

So now we have a true tail recursion, which can be trivially converted to an iteraton, where every internal return simply breaks out of the loop, and the return at the end starts the next iteration:

Code: Select all

eval = 0;
while(1)
{
  // MySEE part
  if(eval >= beta) {result = beta; break; }// stand pat produces (fail-hard) cutoff
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  victim = NextPieceOfMyAttackersList(); // attacker is now on target square
  // HisSee part
  if&#40;eval <= alpha&#41; &#123; result = alpha; break; &#125; // stand pat produces &#40;fail-hard&#41; cutoff
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
&#125;

A slight optimization puts the stand-pat tests to before 'making' the next move, corresponding to the well-known futility-pruning in the recursive implementation:

Code: Select all

eval = 0;
while(1)
{
  // MySEE part
  if(eval >= beta) {result = beta; break; }// stand pat produces (fail-hard) cutoff
  victim = NextPieceOfHisAttackersList(); // attacker is now on target square
  if(eval > alpha) alpha = eval; // this is the crucial alpha update
  eval += PieceValue[victim];
  // HisSee part
  if&#40;eval <= alpha&#41; &#123; result = alpha; break; &#125; // stand pat produces &#40;fail-hard&#41; cutoff
  victim = NextPieceOfMyAttackersList&#40;); // attacker is now on target square
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
&#125;

This made the taking of the next piece from 'his' list of attackers wrap around to the previous iteration, which can be corrected by putting the original content of the square as first element in this list. An aternative would be to skip the first three statements on the first iteration: the comparison for cut-off is not likely to be useful there (or coud be done outide of the loop) as we want to start with beta = INFINITE in the SEE root. And we do not want to allow stand-pat before the side to move actually captures anything; the first move must be forced (and not necessarily by the LVA). This transforms the loop to:

Code: Select all

eval = 0;
victim = board[targetSquare];
while(1)
{
  eval += PieceValue[victim];
  if&#40;eval <= alpha&#41; &#123; result = alpha; break; &#125; // stand pat produces &#40;fail-hard&#41; cutoff
  victim = NextPieceOfMyAttackersList&#40;); // attacker is now on target square
  if&#40;eval < beta&#41; beta = eval; // this is the crucial alpha update
  eval -= PieceValue&#91;victim&#93;;
  if&#40;eval >= beta&#41; &#123;result = beta; break; &#125;// stand pat produces &#40;fail-hard&#41; cutoff
  victim = NextPieceOfHisAttackersList&#40;); // attacker is now on target square
  if&#40;eval > alpha&#41; alpha = eval; // this is the crucial alpha update
&#125;

So the bottom line is that proper implementation of alpha-beta only adds a single conditional move to each original (i.e. non-unrolled) iteration of the SEE loop, to update alpha or beta. I don't think that would be a very large computational burdon.

The issue is the procedure call. Which is not optimized away by the compiler, and which is an expensive operation. If the compiler would turn it into an interative version, that would be nice, but I have not seen any that would even attempt this. That's why I've always just coded it as a loop.

[bob]

This has very low cost.

Yes, I agree.

One interesting problem is to see if there is some benefit in adding the burden to detect captures by pinned pieces.

I have experimented a bit some months ago with this, but I have no found any measurable gain in real games, so I dropped also this one

I tried this a year or two ago when it first came up. I first ran a bunch of fixed-depth games, and modified SEE to just blindly look for pinned pieces and factor in the cost of moving that piece in addition to how it contributes to the capture. I didn't try to do this efficiently because I was not sure the idea was worth anything. Using fixed depth, I found no difference in old and new. But for my implementation, new was certainly expensive. Net result would have been horrible if I had tried using time. But with no measurable benefit, I simply dropped the idea. SEE can be wrong for other reasons just as frequently, including using overloaded pieces, or moving a piece that is not "directly pinned" but which is blocking a key attack on a square that is important. I think there's enough errors that eliminating just pinned pieces is not going to help enough to make it worthwhile, even if it can be done very fast.

To the moderators: Don Dailey has hijacked Bob's account

Miguel

Not quite.

The point here was that someone suggested that evaluating pins might help make the search more accurate since SEE is often used to prune captures in the q-search. I was pretty sure it would not make any significant difference since the entire q-search is already extremely error-prone. To answer the question that was asked, I simply did a working implementation, without regard to speed at all, since I wanted to answer the question with minimal effort. Hence the test. If I had tested the way it _should_ have been tested, I would have spent significant time trying to make it efficient, even though I was almost certain the idea would not be beneficial.

In the normal course of events in Crafty development, I don't try things that I am nearly certain won't help, I only implement things that seem logical/reasonable and then I spend the necessary time to come up with an efficient implementation as well. In this case, this seemed like the easiest way to show that the idea was not helpful, with minimal effort. And the accuracy of this test is _still_ in question since changing SEE changes the shape of the tree as well, which really needs timed testing, not depth. But it was "good enough" to answer a question I was pretty sure I already knew the answer to. This was the second fixed-depth test I have run in the past 5 years (that I can recall). The first was to simply verify that my cluster opponents had no random component in their evaluation that would change the results unexpectedly.

[hgm]

The issue is the procedure call. Which is not optimized away by the compiler, and which is an expensive operation. If the compiler would turn it into an interative version, that would be nice, but I have not seen any that would even attempt this. That's why I've always just coded it as a loop.

Not sure what you are talking about. Seems to me the issue is a conditional move, not a procedure call...

[bob]

The issue is the procedure call. Which is not optimized away by the compiler, and which is an expensive operation. If the compiler would turn it into an interative version, that would be nice, but I have not seen any that would even attempt this. That's why I've always just coded it as a loop.

Not sure what you are talking about. Seems to me the issue is a conditional move, not a procedure call...

Here's the part of my previous post I was commenting on:

That's why I have never used a recursive implementation even though the code becomes a bit simpler. And a bit slower.

A recursive implementation depends on procedure calls and returns, which is less efficient because of the call instruction in X86. An iterative approach (which I have always used) avoids this overhead completely. I have tried this recursive approach, just for fun, but there is a small speed penalty. But since this gets executed so frequently, it has a measurable impact on overall speed.

[hgm]

A recursive implementation depends on procedure calls and returns, which is less efficient because of the call instruction in X86. An iterative approach (which I have always used) avoids this overhead completely. I have tried this recursive approach, just for fun, but there is a small speed penalty. But since this gets executed so frequently, it has a measurable impact on overall speed.

OK, but that procedure calling involves overhead is well known. The issue here if it would pay to implement apha-beta fully. Be it recursively or iteratively. My post that you quoted showed the iterative version of the fully implemented alpha-beta.

[bob]

A recursive implementation depends on procedure calls and returns, which is less efficient because of the call instruction in X86. An iterative approach (which I have always used) avoids this overhead completely. I have tried this recursive approach, just for fun, but there is a small speed penalty. But since this gets executed so frequently, it has a measurable impact on overall speed.

OK, but that procedure calling involves overhead is well known. The issue here if it would pay to implement apha-beta fully. Be it recursively or iteratively. My post that you quoted showed the iterative version of the fully implemented alpha-beta.

I would never argue with that point. My alpha/beta search in Cray Blitz was fully iterative since when it was started, FORTRAN didn't support recursion at all. (they used a fixed static area to store registers which included the return address so recursion would introduce an instant infinite loop). I like the look of the recursive SEE, but not the speed.