Subversion Repositories Games.Chess Giants

/*

  Stockfish, a UCI chess playing engine derived from Glaurung 2.1

  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)

  Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad

  Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad

  Stockfish is free software: you can redistribute it and/or modify

  it under the terms of the GNU General Public License as published by

  the Free Software Foundation, either version 3 of the License, or

  (at your option) any later version.

  Stockfish is distributed in the hope that it will be useful,

  but WITHOUT ANY WARRANTY; without even the implied warranty of

  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License

  along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include <algorithm>

#include <cassert>

#include <cstring>   // For std::memset, std::memcmp

#include <iomanip>

#include <sstream>

#include "bitcount.h"

#include "misc.h"

#include "movegen.h"

#include "position.h"

#include "thread.h"

#include "tt.h"

#include "uci.h"

using std::string;

Value PieceValue[PHASE_NB][PIECE_NB] = {

{ VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },

{ VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };

namespace Zobrist {

  Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];

  Key enpassant[FILE_NB];

  Key castling[CASTLING_RIGHT_NB];

  Key side;

  Key exclusion;

}

Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }

namespace {

const string PieceToChar(" PNBRQK  pnbrqk");

// min_attacker() is a helper function used by see() to locate the least

// valuable attacker for the side to move, remove the attacker we just found

// from the bitboards and scan for new X-ray attacks behind it.

template<int Pt>

PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,

                       Bitboard& occupied, Bitboard& attackers) {

  Bitboard b = stmAttackers & bb[Pt];

  if (!b)

      return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);

  occupied ^= b & ~(b - 1);

  if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)

      attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);

  if (Pt == ROOK || Pt == QUEEN)

      attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);

  attackers &= occupied; // After X-ray that may add already processed pieces

  return (PieceType)Pt;

}

template<>

PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {

  return KING; // No need to update bitboards: it is the last cycle

}

} // namespace

/// CheckInfo constructor

CheckInfo::CheckInfo(const Position& pos) {

  Color them = ~pos.side_to_move();

  ksq = pos.square<KING>(them);

  pinned = pos.pinned_pieces(pos.side_to_move());

  dcCandidates = pos.discovered_check_candidates();

  checkSquares[PAWN]   = pos.attacks_from<PAWN>(ksq, them);

  checkSquares[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);

  checkSquares[BISHOP] = pos.attacks_from<BISHOP>(ksq);

  checkSquares[ROOK]   = pos.attacks_from<ROOK>(ksq);

  checkSquares[QUEEN]  = checkSquares[BISHOP] | checkSquares[ROOK];

  checkSquares[KING]   = 0;

}

/// operator<<(Position) returns an ASCII representation of the position

std::ostream& operator<<(std::ostream& os, const Position& pos) {

  os << "\n +---+---+---+---+---+---+---+---+\n";

  for (Rank r = RANK_8; r >= RANK_1; --r)

  {

      for (File f = FILE_A; f <= FILE_H; ++f)

          os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];

      os << " |\n +---+---+---+---+---+---+---+---+\n";

  }

  os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase

     << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";

  for (Bitboard b = pos.checkers(); b; )

      os << UCI::square(pop_lsb(&b)) << " ";

  return os;

}

/// Position::init() initializes at startup the various arrays used to compute

/// hash keys.

void Position::init() {

  PRNG rng(1070372);

  for (Color c = WHITE; c <= BLACK; ++c)

      for (PieceType pt = PAWN; pt <= KING; ++pt)

          for (Square s = SQ_A1; s <= SQ_H8; ++s)

              Zobrist::psq[c][pt][s] = rng.rand<Key>();

  for (File f = FILE_A; f <= FILE_H; ++f)

      Zobrist::enpassant[f] = rng.rand<Key>();

  for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)

  {

      Zobrist::castling[cr] = 0;

      Bitboard b = cr;

      while (b)

      {

          Key k = Zobrist::castling[1ULL << pop_lsb(&b)];

          Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();

      }

  }

  Zobrist::side = rng.rand<Key>();

  Zobrist::exclusion  = rng.rand<Key>();

}

/// Position::operator=() creates a copy of 'pos' but detaching the state pointer

/// from the source to be self-consistent and not depending on any external data.

Position& Position::operator=(const Position& pos) {

  std::memcpy(this, &pos, sizeof(Position));

  std::memcpy(&startState, st, sizeof(StateInfo));

  st = &startState;

  nodes = 0;

  assert(pos_is_ok());

  return *this;

}

/// Position::clear() erases the position object to a pristine state, with an

/// empty board, white to move, and no castling rights.

void Position::clear() {

  std::memset(this, 0, sizeof(Position));

  startState.epSquare = SQ_NONE;

  st = &startState;

  for (int i = 0; i < PIECE_TYPE_NB; ++i)

      for (int j = 0; j < 16; ++j)

          pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;

}

/// Position::set() initializes the position object with the given FEN string.

/// This function is not very robust - make sure that input FENs are correct,

/// this is assumed to be the responsibility of the GUI.

void Position::set(const string& fenStr, bool isChess960, Thread* th) {

/*

   A FEN string defines a particular position using only the ASCII character set.

   A FEN string contains six fields separated by a space. The fields are:

   1) Piece placement (from white's perspective). Each rank is described, starting

      with rank 8 and ending with rank 1. Within each rank, the contents of each

      square are described from file A through file H. Following the Standard

      Algebraic Notation (SAN), each piece is identified by a single letter taken

      from the standard English names. White pieces are designated using upper-case

      letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are

      noted using digits 1 through 8 (the number of blank squares), and "/"

      separates ranks.

   2) Active color. "w" means white moves next, "b" means black.

   3) Castling availability. If neither side can castle, this is "-". Otherwise,

      this has one or more letters: "K" (White can castle kingside), "Q" (White

      can castle queenside), "k" (Black can castle kingside), and/or "q" (Black

      can castle queenside).

   4) En passant target square (in algebraic notation). If there's no en passant

      target square, this is "-". If a pawn has just made a 2-square move, this

      is the position "behind" the pawn. This is recorded regardless of whether

      there is a pawn in position to make an en passant capture.

   5) Halfmove clock. This is the number of halfmoves since the last pawn advance

      or capture. This is used to determine if a draw can be claimed under the

      fifty-move rule.

   6) Fullmove number. The number of the full move. It starts at 1, and is

      incremented after Black's move.

*/

  unsigned char col, row, token;

  size_t idx;

  Square sq = SQ_A8;

  std::istringstream ss(fenStr);

  clear();

  ss >> std::noskipws;

  // 1. Piece placement

  while ((ss >> token) && !isspace(token))

  {

      if (isdigit(token))

          sq += Square(token - '0'); // Advance the given number of files

      else if (token == '/')

          sq -= Square(16);

      else if ((idx = PieceToChar.find(token)) != string::npos)

      {

          put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);

          ++sq;

      }

  }

  // 2. Active color

  ss >> token;

  sideToMove = (token == 'w' ? WHITE : BLACK);

  ss >> token;

  // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,

  // Shredder-FEN that uses the letters of the columns on which the rooks began

  // the game instead of KQkq and also X-FEN standard that, in case of Chess960,

  // if an inner rook is associated with the castling right, the castling tag is

  // replaced by the file letter of the involved rook, as for the Shredder-FEN.

  while ((ss >> token) && !isspace(token))

  {

      Square rsq;

      Color c = islower(token) ? BLACK : WHITE;

      Piece rook = make_piece(c, ROOK);

      token = char(toupper(token));

      if (token == 'K')

          for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}

      else if (token == 'Q')

          for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}

      else if (token >= 'A' && token <= 'H')

          rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));

      else

          continue;

      set_castling_right(c, rsq);

  }

  // 4. En passant square. Ignore if no pawn capture is possible

  if (   ((ss >> col) && (col >= 'a' && col <= 'h'))

      && ((ss >> row) && (row == '3' || row == '6')))

  {

      st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));

      if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))

          st->epSquare = SQ_NONE;

  }

  // 5-6. Halfmove clock and fullmove number

  ss >> std::skipws >> st->rule50 >> gamePly;

  // Convert from fullmove starting from 1 to ply starting from 0,

  // handle also common incorrect FEN with fullmove = 0.

  gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);

  chess960 = isChess960;

  thisThread = th;

  set_state(st);

  assert(pos_is_ok());

}

/// Position::set_castling_right() is a helper function used to set castling

/// rights given the corresponding color and the rook starting square.

void Position::set_castling_right(Color c, Square rfrom) {

  Square kfrom = square<KING>(c);

  CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;

  CastlingRight cr = (c | cs);

  st->castlingRights |= cr;

  castlingRightsMask[kfrom] |= cr;

  castlingRightsMask[rfrom] |= cr;

  castlingRookSquare[cr] = rfrom;

  Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);

  Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);

  for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)

      if (s != kfrom && s != rfrom)

          castlingPath[cr] |= s;

  for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)

      if (s != kfrom && s != rfrom)

          castlingPath[cr] |= s;

}

/// Position::set_state() computes the hash keys of the position, and other

/// data that once computed is updated incrementally as moves are made.

/// The function is only used when a new position is set up, and to verify

/// the correctness of the StateInfo data when running in debug mode.

void Position::set_state(StateInfo* si) const {

  si->key = si->pawnKey = si->materialKey = 0;

  si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;

  si->psq = SCORE_ZERO;

  si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);

  for (Bitboard b = pieces(); b; )

  {

      Square s = pop_lsb(&b);

      Piece pc = piece_on(s);

      si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];

      si->psq += PSQT::psq[color_of(pc)][type_of(pc)][s];

  }

  if (si->epSquare != SQ_NONE)

      si->key ^= Zobrist::enpassant[file_of(si->epSquare)];

  if (sideToMove == BLACK)

      si->key ^= Zobrist::side;

  si->key ^= Zobrist::castling[si->castlingRights];

  for (Bitboard b = pieces(PAWN); b; )

  {

      Square s = pop_lsb(&b);

      si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];

  }

  for (Color c = WHITE; c <= BLACK; ++c)

      for (PieceType pt = PAWN; pt <= KING; ++pt)

          for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)

              si->materialKey ^= Zobrist::psq[c][pt][cnt];

  for (Color c = WHITE; c <= BLACK; ++c)

      for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)

          si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];

}

/// Position::fen() returns a FEN representation of the position. In case of

/// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.

const string Position::fen() const {

  int emptyCnt;

  std::ostringstream ss;

  for (Rank r = RANK_8; r >= RANK_1; --r)

  {

      for (File f = FILE_A; f <= FILE_H; ++f)

      {

          for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)

              ++emptyCnt;

          if (emptyCnt)

              ss << emptyCnt;

          if (f <= FILE_H)

              ss << PieceToChar[piece_on(make_square(f, r))];

      }

      if (r > RANK_1)

          ss << '/';

  }

  ss << (sideToMove == WHITE ? " w " : " b ");

  if (can_castle(WHITE_OO))

      ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE |  KING_SIDE))) : 'K');

  if (can_castle(WHITE_OOO))

      ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');

  if (can_castle(BLACK_OO))

      ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK |  KING_SIDE))) : 'k');

  if (can_castle(BLACK_OOO))

      ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');

  if (!can_castle(WHITE) && !can_castle(BLACK))

      ss << '-';

  ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")

     << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;

  return ss.str();

}

/// Position::game_phase() calculates the game phase interpolating total non-pawn

/// material between endgame and midgame limits.

Phase Position::game_phase() const {

  Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];

  npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));

  return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));

}

/// Position::check_blockers() returns a bitboard of all the pieces with color

/// 'c' that are blocking check on the king with color 'kingColor'. A piece

/// blocks a check if removing that piece from the board would result in a

/// position where the king is in check. A check blocking piece can be either a

/// pinned or a discovered check piece, according if its color 'c' is the same

/// or the opposite of 'kingColor'.

Bitboard Position::check_blockers(Color c, Color kingColor) const {

  Bitboard b, pinners, result = 0;

  Square ksq = square<KING>(kingColor);

  // Pinners are sliders that give check when a pinned piece is removed

  pinners = (  (pieces(  ROOK, QUEEN) & PseudoAttacks[ROOK  ][ksq])

             | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);

  while (pinners)

  {

      b = between_bb(ksq, pop_lsb(&pinners)) & pieces();

      if (!more_than_one(b))

          result |= b & pieces(c);

  }

  return result;

}

/// Position::attackers_to() computes a bitboard of all pieces which attack a

/// given square. Slider attacks use the occupied bitboard to indicate occupancy.

Bitboard Position::attackers_to(Square s, Bitboard occupied) const {

  return  (attacks_from<PAWN>(s, BLACK)    & pieces(WHITE, PAWN))

        | (attacks_from<PAWN>(s, WHITE)    & pieces(BLACK, PAWN))

        | (attacks_from<KNIGHT>(s)         & pieces(KNIGHT))

        | (attacks_bb<ROOK  >(s, occupied) & pieces(ROOK,   QUEEN))

        | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))

        | (attacks_from<KING>(s)           & pieces(KING));

}

/// Position::legal() tests whether a pseudo-legal move is legal

bool Position::legal(Move m, Bitboard pinned) const {

  assert(is_ok(m));

  assert(pinned == pinned_pieces(sideToMove));

  Color us = sideToMove;

  Square from = from_sq(m);

  assert(color_of(moved_piece(m)) == us);

  assert(piece_on(square<KING>(us)) == make_piece(us, KING));

  // En passant captures are a tricky special case. Because they are rather

  // uncommon, we do it simply by testing whether the king is attacked after

  // the move is made.

  if (type_of(m) == ENPASSANT)

  {

      Square ksq = square<KING>(us);

      Square to = to_sq(m);

      Square capsq = to - pawn_push(us);

      Bitboard occupied = (pieces() ^ from ^ capsq) | to;

      assert(to == ep_square());

      assert(moved_piece(m) == make_piece(us, PAWN));

      assert(piece_on(capsq) == make_piece(~us, PAWN));

      assert(piece_on(to) == NO_PIECE);

      return   !(attacks_bb<  ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))

            && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));

  }

  // If the moving piece is a king, check whether the destination

  // square is attacked by the opponent. Castling moves are checked

  // for legality during move generation.

  if (type_of(piece_on(from)) == KING)

      return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));

  // A non-king move is legal if and only if it is not pinned or it

  // is moving along the ray towards or away from the king.

  return   !pinned

        || !(pinned & from)

        ||  aligned(from, to_sq(m), square<KING>(us));

}

/// Position::pseudo_legal() takes a random move and tests whether the move is

/// pseudo legal. It is used to validate moves from TT that can be corrupted

/// due to SMP concurrent access or hash position key aliasing.

bool Position::pseudo_legal(const Move m) const {

  Color us = sideToMove;

  Square from = from_sq(m);

  Square to = to_sq(m);

  Piece pc = moved_piece(m);

  // Use a slower but simpler function for uncommon cases

  if (type_of(m) != NORMAL)

      return MoveList<LEGAL>(*this).contains(m);

  // Is not a promotion, so promotion piece must be empty

  if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)

      return false;

  // If the 'from' square is not occupied by a piece belonging to the side to

  // move, the move is obviously not legal.

  if (pc == NO_PIECE || color_of(pc) != us)

      return false;

  // The destination square cannot be occupied by a friendly piece

  if (pieces(us) & to)

      return false;

  // Handle the special case of a pawn move

  if (type_of(pc) == PAWN)

  {

      // We have already handled promotion moves, so destination

      // cannot be on the 8th/1st rank.

      if (rank_of(to) == relative_rank(us, RANK_8))

          return false;

      if (   !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture

          && !((from + pawn_push(us) == to) && empty(to))       // Not a single push

          && !(   (from + 2 * pawn_push(us) == to)              // Not a double push

               && (rank_of(from) == relative_rank(us, RANK_2))

               && empty(to)

               && empty(to - pawn_push(us))))

          return false;

  }

  else if (!(attacks_from(pc, from) & to))

      return false;

  // Evasions generator already takes care to avoid some kind of illegal moves

  // and legal() relies on this. We therefore have to take care that the same

  // kind of moves are filtered out here.

  if (checkers())

  {

      if (type_of(pc) != KING)

      {

          // Double check? In this case a king move is required

          if (more_than_one(checkers()))

              return false;

          // Our move must be a blocking evasion or a capture of the checking piece

          if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))

              return false;

      }

      // In case of king moves under check we have to remove king so as to catch

      // invalid moves like b1a1 when opposite queen is on c1.

      else if (attackers_to(to, pieces() ^ from) & pieces(~us))

          return false;

  }

  return true;

}

/// Position::gives_check() tests whether a pseudo-legal move gives a check

bool Position::gives_check(Move m, const CheckInfo& ci) const {

  assert(is_ok(m));

  assert(ci.dcCandidates == discovered_check_candidates());

  assert(color_of(moved_piece(m)) == sideToMove);

  Square from = from_sq(m);

  Square to = to_sq(m);

  // Is there a direct check?

  if (ci.checkSquares[type_of(piece_on(from))] & to)

      return true;

  // Is there a discovered check?

  if (    ci.dcCandidates

      && (ci.dcCandidates & from)

      && !aligned(from, to, ci.ksq))

      return true;

  switch (type_of(m))

  {

  case NORMAL:

      return false;

  case PROMOTION:

      return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;

  // En passant capture with check? We have already handled the case

  // of direct checks and ordinary discovered check, so the only case we

  // need to handle is the unusual case of a discovered check through

  // the captured pawn.

  case ENPASSANT:

  {

      Square capsq = make_square(file_of(to), rank_of(from));

      Bitboard b = (pieces() ^ from ^ capsq) | to;

      return  (attacks_bb<  ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))

            | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));

  }

  case CASTLING:

  {

      Square kfrom = from;

      Square rfrom = to; // Castling is encoded as 'King captures the rook'

      Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);

      Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);

      return   (PseudoAttacks[ROOK][rto] & ci.ksq)

            && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);

  }

  default:

      assert(false);

      return false;

  }

}

/// Position::do_move() makes a move, and saves all information necessary

/// to a StateInfo object. The move is assumed to be legal. Pseudo-legal

/// moves should be filtered out before this function is called.

void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {

  assert(is_ok(m));

  assert(&newSt != st);

  ++nodes;

  Key k = st->key ^ Zobrist::side;

  // Copy some fields of the old state to our new StateInfo object except the

  // ones which are going to be recalculated from scratch anyway and then switch

  // our state pointer to point to the new (ready to be updated) state.

  std::memcpy(&newSt, st, offsetof(StateInfo, key));

  newSt.previous = st;

  st = &newSt;

  // Increment ply counters. In particular, rule50 will be reset to zero later on

  // in case of a capture or a pawn move.

  ++gamePly;

  ++st->rule50;

  ++st->pliesFromNull;

  Color us = sideToMove;

  Color them = ~us;

  Square from = from_sq(m);

  Square to = to_sq(m);

  PieceType pt = type_of(piece_on(from));

  PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));

  assert(color_of(piece_on(from)) == us);

  assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));

  assert(captured != KING);

  if (type_of(m) == CASTLING)

  {

      assert(pt == KING);

      Square rfrom, rto;

      do_castling<true>(us, from, to, rfrom, rto);

      captured = NO_PIECE_TYPE;

      st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];

      k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];

  }

  if (captured)

  {

      Square capsq = to;

      // If the captured piece is a pawn, update pawn hash key, otherwise

      // update non-pawn material.

      if (captured == PAWN)

      {

          if (type_of(m) == ENPASSANT)

          {

              capsq -= pawn_push(us);

              assert(pt == PAWN);

              assert(to == st->epSquare);

              assert(relative_rank(us, to) == RANK_6);

              assert(piece_on(to) == NO_PIECE);

              assert(piece_on(capsq) == make_piece(them, PAWN));

              board[capsq] = NO_PIECE; // Not done by remove_piece()

          }

          st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];

      }

      else

          st->nonPawnMaterial[them] -= PieceValue[MG][captured];

      // Update board and piece lists

      remove_piece(them, captured, capsq);