/*

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

constexpr 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* byTypeBB, Square to, Bitboard stmAttackers,

Bitboard& occupied, Bitboard& attackers) {

Bitboard b = stmAttackers & byTypeBB[Pt];

if (!b)

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

occupied ^= lsb(b); // Remove the attacker from occupied

// Add any X-ray attack behind the just removed piece. For instance with

// rooks in a8 and a7 attacking a1, after removing a7 we add rook in a8.

// Note that new added attackers can be of any color.

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

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

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

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

// X-ray may add already processed pieces because byTypeBB[] is constant: in

// the rook example, now attackers contains _again_ rook in a7, so remove it.

attackers &= occupied;

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;

}

// Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"

// situations. Description of the algorithm in the following paper:

// https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf

// First and second hash functions for indexing the cuckoo tables

inline int H1(Key h) { return h & 0x1fff; }

inline int H2(Key h) { return (h >> 16) & 0x1fff; }

// Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves

Key cuckoo[8192];

Move cuckooMove[8192];

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

// Prepare the cuckoo tables

std::memset(cuckoo, 0, sizeof(cuckoo));

std::memset(cuckooMove, 0, sizeof(cuckooMove));

int count = 0;

for (Piece pc : Pieces)

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

for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)

if (PseudoAttacks[type_of(pc)][s1] & s2)

{

Move move = make_move(s1, s2);

Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;

int i = H1(key);

while (true)

{

std::swap(cuckoo[i], key);

std::swap(cuckooMove[i], move);

if (move == 0) // Arrived at empty slot ?

break;

i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot

}

count++;

}

assert(count == 3668);

}

/// 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->pinners[BLACK]);

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

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

}

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

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 blockers = 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 (b && !more_than_one(b))

{

blockers |= b;

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

pinners |= sniperSq;

}

}

return blockers;

}

/// 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 !(blockers_for_king(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 ( (st->blockersForKing[~sideToMove] & 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);

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

// update non-pawn material.

if (type_of(captured) == PAWN)

{

if (type_of(m) == ENPASSANT)

{

capsq -= pawn_push(us);

assert(pc == make_piece(us, 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[captured][capsq];

}

else

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

// Update board and piece lists

remove_piece(captured, capsq);

// Update material hash key and prefetch access to materialTable

k ^= Zobrist::psq[captured][capsq];

st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];

prefetch(thisThread->materialTable[st->materialKey]);

// Reset rule 50 counter

st->rule50 = 0;

}

// Update hash key

k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];

// Reset en passant square

if (st->epSquare != SQ_NONE)

{

k ^= Zobrist::enpassant[file_of(st->epSquare)];

st->epSquare = SQ_NONE;

}

// Update castling rights if needed

if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))

{

int cr = castlingRightsMask[from] | castlingRightsMask[to];

k ^= Zobrist::castling[st->castlingRights & cr];

st->castlingRights &= ~cr;

}

// Move the piece. The tricky Chess960 castling is handled earlier

if (type_of(m) != CASTLING)

move_piece(pc, from, to);

// If the moving piece is a pawn do some special extra work

if (type_of(pc) == PAWN)

{

// Set en-passant square if the moved pawn can be captured

if ( (int(to) ^ int(from)) == 16

&& (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))

{

st->epSquare = to - pawn_push(us);

k ^= Zobrist::enpassant[file_of(st->epSquare)];

}

else if (type_of(m) == PROMOTION)

{

Piece promotion = make_piece(us, promotion_type(m));

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

assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);

remove_piece(pc, to);

put_piece(promotion, to);

// Update hash keys

k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];

st->pawnKey ^= Zobrist::psq[pc][to];

st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]

^ Zobrist::psq[pc][pieceCount[pc]];

// Update material

st->nonPawnMaterial[us] += PieceValue[MG][promotion];

}

// Update pawn hash key and prefetch access to pawnsTable

st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];

prefetch2(thisThread->pawnsTable[st->pawnKey]);

// Reset rule 50 draw counter

st->rule50 = 0;

}

// Set capture piece

st->capturedPiece = captured;

// Update the key with the final value

st->key = k;

// Calculate checkers bitboard (if move gives check)

st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;

sideToMove = ~sideToMove;

// Update king attacks used for fast check detection

set_check_info(st);

assert(pos_is_ok());

}

/// Position::undo_move() unmakes a move. When it returns, the position should

/// be restored to exactly the same state as before the move was made.

void Position::undo_move(Move m) {

assert(is_ok(m));

sideToMove = ~sideToMove;

Color us = sideToMove;

Square from = from_sq(m);

Square to = to_sq(m);

Piece pc = piece_on(to);

assert(empty(from) || type_of(m) == CASTLING);

assert(type_of(st->capturedPiece) != KING);

if (type_of(m) == PROMOTION)

{

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

assert(type_of(pc) == promotion_type(m));

assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);

remove_piece(pc, to);

pc = make_piece(us, PAWN);

put_piece(pc, to);

}

if (type_of(m) == CASTLING)

{

Square rfrom, rto;

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

}

else

{

move_piece(pc, to, from); // Put the piece back at the source square

if (st->capturedPiece)

{

Square capsq = to;

if (type_of(m) == ENPASSANT)

{

capsq -= pawn_push(us);

assert(type_of(pc) == PAWN);

assert(to == st->previous->epSquare);

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

assert(piece_on(capsq) == NO_PIECE);

assert(st->capturedPiece == make_piece(~us, PAWN));

}

put_piece(st->capturedPiece, capsq); // Restore the captured piece

}

}

// Finally point our state pointer back to the previous state

st = st->previous;

--gamePly;

assert(pos_is_ok());

}

/// Position::do_castling() is a helper used to do/undo a castling move. This

/// is a bit tricky in Chess960 where from/to squares can overlap.

template<bool Do>

void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {

bool kingSide = to > from;

rfrom = to; // Castling is encoded as "king captures friendly rook"

rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);

to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);

// Remove both pieces first since squares could overlap in Chess960

remove_piece(make_piece(us, KING), Do ? from : to);

remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);

board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us

put_piece(make_piece(us, KING), Do ? to : from);

put_piece(make_piece(us, ROOK), Do ? rto : rfrom);

}

/// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips

/// the side to move without executing any move on the board.

void Position::do_null_move(StateInfo& newSt) {

assert(!checkers());

assert(&newSt != st);

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

newSt.previous = st;

st = &newSt;

if (st->epSquare != SQ_NONE)

{

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

st->epSquare = SQ_NONE;

}

st->key ^= Zobrist::side;

prefetch(TT.first_entry(st->key));

++st->rule50;

st->pliesFromNull = 0;

sideToMove = ~sideToMove;

set_check_info(st);

assert(pos_is_ok());

}

void Position::undo_null_move() {

assert(!checkers());

st = st->previous;

sideToMove = ~sideToMove;

}

/// Position::key_after() computes the new hash key after the given move. Needed

/// for speculative prefetch. It doesn't recognize special moves like castling,

/// en-passant and promotions.

Key Position::key_after(Move m) const {