One is to have some early shortcuts (e.g. in see_sign) and if they don't lead to cutoffs, build the complete swap list first and evaluate it at the end. This approach was for example taken by Fruit and Stockfish.
At first glance this approach seems to be inferior, because once the swap list is started, it is always built completely even if its later evaluation shows that only the first terms would be needed.
Several people have written SEE with alpha beta independently. Me in Onno, Fritz in Loop and HGM here: http://www.talkchess.com/forum/viewtopi ... 82&t=30905
(Note that HGM seems not to prevent moving into check. This cannot be handled with infinite king value if the king is captured by the other king which in turn can be recaptured. Test with this position: 8/8/3p4/4r3/2RKP3/5k2/8/8 b - - ).
I thought that alpha beta SEE would be better. Marco disagreed because of the extra branches.
I gave an alpha beta SEE a try in Stockfish. My result was that the speed is practically the same. nps on "stockfish bench" has no significant differences. Cachegrind estimates time for SEE in at 6.8% in the original and 6.7% with alpha beta (both with my probcut patch, at depth 11). Your mileage may vary, but I would be surprised if either version is significantly faster than the other if a different computer is used.
Anyway, here is the SEE function. Supposed to replace both see and see_sign. Call with update=false if the search window has zero width.
Code: Select all
template<bool update> int Position::see (Square from, Square to, int alpha, int beta) const
{
assert(square_is_ok(from));
assert(square_is_ok(to));
// handle castle moves
if (color_of_piece_on(from)==color_of_piece_on(to))
return 0; // TODO: for FRC, consider to compute SEE of rook move instead
// remove his piece from target square
// -------------------------------------------------------------
// get his piece to remove
PieceType capturedType = type_of_piece_on(to);
// King cannot be recaptured; illegal moves are pruned at higher level
if (type_of_piece_on(from) == KING)
return seeValues[capturedType];
Bitboard occupied = occupied_squares();
// Handle en passant moves
if (st->epSquare == to && type_of_piece_on(from) == PAWN)
{
Square capQq = (side_to_move() == WHITE ? to - DELTA_N : to - DELTA_S);
assert(capturedType == PIECE_TYPE_NONE);
assert(type_of_piece_on(capQq) == PAWN);
// Remove the captured pawn
clear_bit(&occupied, capQq);
capturedType = PAWN;
}
int eval = seeValues[capturedType];
// Assume that my piece cannot be (re)captured.
// If the move is still not good enough, return.
if (eval <= alpha)
return alpha;
// update
if (update && eval < beta)
beta = eval;
// my initial move
// -------------------------------------------------------------
// get my moving piece
capturedType = type_of_piece_on (from);
// early check: assume that my piece can be (re)captured.
// If the move is still good, return.
eval -= seeValues[capturedType];
if (eval >= beta)
return beta;
// update
if (update && eval > alpha)
alpha = eval;
// execute the move
clear_bit(&occupied, from);
// some setup
// -----------------------------------------------------------
// Find all attackers to the destination square
Bitboard attackers = (rook_attacks_bb(to, occupied) & pieces(ROOK, QUEEN))
| (bishop_attacks_bb(to, occupied)& pieces(BISHOP, QUEEN))
| (attacks_from<KNIGHT>(to) & pieces(KNIGHT))
| (attacks_from<KING>(to) & pieces(KING))
| (attacks_from<PAWN>(to, WHITE) & pieces(PAWN, BLACK))
| (attacks_from<PAWN>(to, BLACK) & pieces(PAWN, WHITE));
// setup colors
Color me = color_of_piece_on(from);
Color him = opposite_color (me);
while (true)
{
// his (re)capture
// ------------------------------------------------------------
// get his attackers
Bitboard stmAttackers = attackers & pieces_of_color(him);
// no more captures possible: return
if (!stmAttackers)
return beta;
// last move or capture was illegal
if (capturedType==KING)
return alpha;
// find his cheapest attacker
for (capturedType = PAWN; !(stmAttackers & pieces(capturedType)); capturedType++);
// early check: assume that his piece can be recaptured
// if that would not be sufficient, return
eval += seeValues[capturedType];
if (eval <= alpha)
return alpha;
// update
if (update && eval < beta)
beta = eval;
// execute his (re) capture
Bitboard b = stmAttackers & pieces(capturedType);
occupied ^= b & (~b + 1);
attackers |= (rook_attacks_bb(to, occupied) & pieces(ROOK, QUEEN))
| (bishop_attacks_bb(to, occupied) & pieces(BISHOP, QUEEN));
attackers &= occupied;
// my recapture
// -----------------------------------------------------------
// get my attackers
stmAttackers = attackers & pieces_of_color(me);
// no more captures possible: return
if (!stmAttackers)
return alpha;
// last (re)capture was illegal
if (capturedType==KING)
return beta;
// find my cheapest attacker
for (capturedType = PAWN; !(stmAttackers & pieces(capturedType)); capturedType++);
// early check: assume that my piece can be recaptured.
// If the move is still good, return
eval -= seeValues[capturedType];
if (eval >= beta)
return beta;
// update
if (update && eval > alpha)
alpha = eval;
// execute my capture
b = stmAttackers & pieces(capturedType);
occupied ^= b & (~b + 1);
attackers |= (rook_attacks_bb(to, occupied) & pieces(ROOK, QUEEN))
| (bishop_attacks_bb(to, occupied) & pieces(BISHOP, QUEEN));
attackers &= occupied;
}
}
