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(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 = NextPieceOfHisAttackersList(); // attacker is now on target square
return MySEE(beta, alpha, eval, victim);
}
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(eval <= alpha) return alpha; // stand pat produces (fail-hard) cutoff
if(eval < beta) beta = eval; // this is the crucial alpha update
eval -= PieceValue[victim];
victim = NextPieceOfHisAttackersList(); // attacker is now on target square
return MySEE(alpha, beta, eval, victim);
}
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(eval <= alpha) { result = alpha; break; } // stand pat produces (fail-hard) cutoff
if(eval < beta) beta = eval; // this is the crucial alpha update
eval -= PieceValue[victim];
victim = NextPieceOfHisAttackersList(); // attacker is now on target square
}
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(eval <= alpha) { result = alpha; break; } // stand pat produces (fail-hard) cutoff
victim = NextPieceOfMyAttackersList(); // attacker is now on target square
if(eval < beta) beta = eval; // this is the crucial alpha update
eval -= PieceValue[victim];
}
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(eval <= alpha) { result = alpha; break; } // stand pat produces (fail-hard) cutoff
victim = NextPieceOfMyAttackersList(); // attacker is now on target square
if(eval < beta) beta = eval; // this is the crucial alpha update
eval -= PieceValue[victim];
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
}
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.