}
-/// Position::see() is a static exchange evaluator: It tries to estimate the
-/// material gain or loss resulting from a move.
+/// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
+/// SEE value of move is greater or equal to the given value. We'll use an
+/// algorithm similar to alpha-beta pruning with a null window.
-Value Position::see_sign(Move m) const {
+bool Position::see_ge(Move m, Value v) const {
assert(is_ok(m));
- // Early return if SEE cannot be negative because captured piece value
- // is not less then capturing one. Note that king moves always return
- // here because king midgame value is set to 0.
- if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
- return VALUE_KNOWN_WIN;
-
- return see(m);
-}
-
-Value Position::see(Move m) const {
-
- Square from, to;
- Bitboard occupied, attackers, stmAttackers;
- Value swapList[32];
- int slIndex = 1;
- PieceType nextVictim;
- Color stm;
-
- assert(is_ok(m));
-
- from = from_sq(m);
- to = to_sq(m);
- swapList[0] = PieceValue[MG][piece_on(to)];
- stm = color_of(piece_on(from));
- occupied = pieces() ^ from;
-
- // Castling moves are implemented as king capturing the rook so cannot
- // be handled correctly. Simply return VALUE_ZERO that is always correct
- // unless in the rare case the rook ends up under attack.
+ // Castling moves are implemented as king capturing the rook so cannot be
+ // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
+ // correct unless in the rare case the rook ends up under attack.
if (type_of(m) == CASTLING)
- return VALUE_ZERO;
+ return VALUE_ZERO >= v;
+
+ Square from = from_sq(m), to = to_sq(m);
+ PieceType nextVictim = type_of(piece_on(from));
+ Color stm = ~color_of(piece_on(from)); // First consider opponent's move
+ Value balance; // Values of the pieces taken by us minus opponent's ones
+ Bitboard occupied, stmAttackers;
if (type_of(m) == ENPASSANT)
{
- occupied ^= to - pawn_push(stm); // Remove the captured pawn
- swapList[0] = PieceValue[MG][PAWN];
+ occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
+ balance = PieceValue[MG][PAWN];
+ }
+ else
+ {
+ balance = PieceValue[MG][piece_on(to)];
+ occupied = 0;
}
- // Find all attackers to the destination square, with the moving piece
- // removed, but possibly an X-ray attacker added behind it.
- attackers = attackers_to(to, occupied) & occupied;
+ if (balance < v)
+ return false;
- // If the opponent has no attackers we are finished
- stm = ~stm;
- stmAttackers = attackers & pieces(stm);
- occupied ^= to; // For the case when captured piece is a pinner
+ if (nextVictim == KING)
+ return true;
+
+ balance -= PieceValue[MG][nextVictim];
+
+ if (balance >= v)
+ return true;
- // Don't allow pinned pieces to attack pieces except the king as long all
- // pinners are on their original square.
- if (!(st->pinnersForKing[stm] & ~occupied))
- stmAttackers &= ~st->blockersForKing[stm];
+ bool relativeStm = true; // True if the opponent is to move
+ occupied ^= pieces() ^ from ^ to;
- if (!stmAttackers)
- return swapList[0];
+ // Find all attackers to the destination square, with the moving piece removed,
+ // but possibly an X-ray attacker added behind it.
+ Bitboard attackers = attackers_to(to, occupied) & occupied;
- // 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.
- nextVictim = type_of(piece_on(from));
+ while (true)
+ {
+ stmAttackers = attackers & pieces(stm);
- do {
- assert(slIndex < 32);
+ // Don't allow pinned pieces to attack pieces except the king as long all
+ // pinners are on their original square.
+ if (!(st->pinnersForKing[stm] & ~occupied))
+ stmAttackers &= ~st->blockersForKing[stm];
- // Add the new entry to the swap list
- swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][nextVictim];
+ if (!stmAttackers)
+ return relativeStm;
// Locate and remove the next least valuable attacker
nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
- stm = ~stm;
- stmAttackers = attackers & pieces(stm);
- // Don't allow pinned pieces to attack pieces except the king
- if ( nextVictim != KING
- && !(st->pinnersForKing[stm] & ~occupied))
- stmAttackers &= ~st->blockersForKing[stm];
+ if (nextVictim == KING)
+ return relativeStm == bool(attackers & pieces(~stm));
- ++slIndex;
+ balance += relativeStm ? PieceValue[MG][nextVictim]
+ : -PieceValue[MG][nextVictim];
- } while (stmAttackers && (nextVictim != KING || (--slIndex, false))); // Stop before a king capture
+ relativeStm = !relativeStm;
- // 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 (--slIndex)
- swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
+ if (relativeStm == (balance >= v))
+ return relativeStm;
- return swapList[0];
+ stm = ~stm;
+ }
}