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;

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

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;

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;

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

}

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

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;

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

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

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;

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;

}

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

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

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

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

assert(!checkers());

st = st->previous;

sideToMove = ~sideToMove;