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-2018 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 <cstddef> // For offsetof()

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

#include <iomanip>

#include <sstream>

#include "bitboard.h"

#include "misc.h"

#include "movegen.h"

#include "position.h"

#include "thread.h"

#include "tt.h"

#include "uci.h"

#include "syzygy/tbprobe.h"

using std::string;

namespace PSQT {

  extern Score psq[PIECE_NB][SQUARE_NB];

}

namespace Zobrist {

  Key psq[PIECE_NB][SQUARE_NB];

  Key enpassant[FILE_NB];

  Key castling[CASTLING_RIGHT_NB];

  Key side, noPawns;

}

namespace {

const string PieceToChar(" PNBRQK  pnbrqk");

const Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,

                         B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };

// min_attacker() is a helper function used by see_ge() 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

/// 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::setfill(' ') << std::dec << "\nCheckers: ";

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

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

  if (    int(Tablebases::MaxCardinality) >= popcount(pos.pieces())

      && !pos.can_castle(ANY_CASTLING))

  {

      StateInfo st;

      Position p;

      p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());

      Tablebases::ProbeState s1, s2;

      Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);

      int dtz = Tablebases::probe_dtz(p, &s2);

      os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"

         << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";

  }

  return os;

}

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

/// hash keys.

void Position::init() {

  PRNG rng(1070372);

  for (Piece pc : Pieces)

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

          Zobrist::psq[pc][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::noPawns = rng.rand<Key>();

}

/// 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.

Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, 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 only if there is a pawn

      in position to make an en passant capture, and if there really is a pawn

      that might have advanced two squares.

   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);

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

  std::memset(si, 0, sizeof(StateInfo));

  std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);

  st = si;

  ss >> std::noskipws;

  // 1. Piece placement

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

  {

      if (isdigit(token))

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

      else if (token == '/')

          sq += 2 * SOUTH;

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

      {

          put_piece(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))

          || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))

          st->epSquare = SQ_NONE;

  }

  else

      st->epSquare = SQ_NONE;

  // 5-6. Halfmove clock and fullmove number

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

  // Convert from fullmove starting from 1 to gamePly 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());

  return *this;

}

/// 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_check_info() sets king attacks to detect if a move gives check

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

  si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);

  si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);

  Square ksq = square<KING>(~sideToMove);

  si->checkSquares[PAWN]   = attacks_from<PAWN>(ksq, ~sideToMove);

  si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);

  si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);

  si->checkSquares[ROOK]   = attacks_from<ROOK>(ksq);

  si->checkSquares[QUEEN]  = si->checkSquares[BISHOP] | si->checkSquares[ROOK];

  si->checkSquares[KING]   = 0;

}

/// 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->materialKey = 0;

  si->pawnKey = Zobrist::noPawns;

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

  si->psq = SCORE_ZERO;

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

  set_check_info(si);

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

  {

      Square s = pop_lsb(&b);

      Piece pc = piece_on(s);

      si->key ^= Zobrist::psq[pc][s];

      si->psq += PSQT::psq[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[piece_on(s)][s];

  }

  for (Piece pc : Pieces)

  {

      if (type_of(pc) != PAWN && type_of(pc) != KING)

          si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];

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

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

  }

}

/// Position::set() is an overload to initialize the position object with

/// the given endgame code string like "KBPKN". It is mainly a helper to

/// get the material key out of an endgame code.

Position& Position::set(const string& code, Color c, StateInfo* si) {

  assert(code.length() > 0 && code.length() < 8);

  assert(code[0] == 'K');

  string sides[] = { code.substr(code.find('K', 1)),      // Weak

                     code.substr(0, code.find('K', 1)) }; // Strong

  std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);

  string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"

                       + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";

  return set(fenStr, false, si, nullptr);

}

/// 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::slider_blockers() returns a bitboard of all the pieces (both colors)

/// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a

/// slider if removing that piece from the board would result in a position where

/// square 's' is attacked. For example, a king-attack blocking piece can be either

/// a pinned or a discovered check piece, according if its color is the opposite

/// or the same of the color of the slider.

Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {

  Bitboard result = 0;

  pinners = 0;

  // Snipers are sliders that attack 's' when a piece is removed

  Bitboard snipers = (  (PseudoAttacks[  ROOK][s] & pieces(QUEEN, ROOK))

                      | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;

  while (snipers)

  {

    Square sniperSq = pop_lsb(&snipers);

    Bitboard b = between_bb(s, sniperSq) & pieces();

    if (!more_than_one(b))

    {

        result |= b;

        if (b & pieces(color_of(piece_on(s))))

            pinners |= sniperSq;

    }

  }

  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) const {

  assert(is_ok(m));

  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_pieces(us) & 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(type_of(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 {

  assert(is_ok(m));

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

  Square from = from_sq(m);

  Square to = to_sq(m);

  // Is there a direct check?

  if (st->checkSquares[type_of(piece_on(from))] & to)

      return true;

  // Is there a discovered check?

  if (   (discovered_check_candidates() & from)

      && !aligned(from, to, square<KING>(~sideToMove)))

      return true;

  switch (type_of(m))

  {

  case NORMAL:

      return false;

  case PROMOTION:

      return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);

  // 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>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))

            | (attacks_bb<BISHOP>(square<KING>(~sideToMove), 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] & square<KING>(~sideToMove))

            && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));

  }

  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);

  thisThread->nodes.fetch_add(1, std::memory_order_relaxed);

  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);

  Piece pc = piece_on(from);

  Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);

  assert(color_of(pc) == us);

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

  assert(type_of(captured) != KING);

  if (type_of(m) == CASTLING)

  {

      assert(pc == make_piece(us, KING));

      assert(captured == make_piece(us, ROOK));

      Square rfrom, rto;

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

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

      k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];

      captured = NO_PIECE;

  }

  if (captured)

  {

      Square capsq = to;

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