Subversion Repositories Games.Chess Giants

Rev

Rev 169 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  3.   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  4.   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
  5.   Copyright (C) 2015-2019 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
  6.  
  7.   Stockfish is free software: you can redistribute it and/or modify
  8.   it under the terms of the GNU General Public License as published by
  9.   the Free Software Foundation, either version 3 of the License, or
  10.   (at your option) any later version.
  11.  
  12.   Stockfish is distributed in the hope that it will be useful,
  13.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.   GNU General Public License for more details.
  16.  
  17.   You should have received a copy of the GNU General Public License
  18.   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19. */
  20.  
  21. #include <algorithm>
  22. #include <cassert>
  23. #include <cstddef> // For offsetof()
  24. #include <cstring> // For std::memset, std::memcmp
  25. #include <iomanip>
  26. #include <sstream>
  27.  
  28. #include "bitboard.h"
  29. #include "misc.h"
  30. #include "movegen.h"
  31. #include "position.h"
  32. #include "thread.h"
  33. #include "tt.h"
  34. #include "uci.h"
  35. #include "syzygy/tbprobe.h"
  36.  
  37. using std::string;
  38.  
  39. namespace Zobrist {
  40.  
  41.   Key psq[PIECE_NB][SQUARE_NB];
  42.   Key enpassant[FILE_NB];
  43.   Key castling[CASTLING_RIGHT_NB];
  44.   Key side, noPawns;
  45. }
  46.  
  47. namespace {
  48.  
  49. const string PieceToChar(" PNBRQK  pnbrqk");
  50.  
  51. constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
  52.                              B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
  53.  
  54. // min_attacker() is a helper function used by see_ge() to locate the least
  55. // valuable attacker for the side to move, remove the attacker we just found
  56. // from the bitboards and scan for new X-ray attacks behind it.
  57.  
  58. template<int Pt>
  59. PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers,
  60.                        Bitboard& occupied, Bitboard& attackers) {
  61.  
  62.   Bitboard b = stmAttackers & byTypeBB[Pt];
  63.   if (!b)
  64.       return min_attacker<Pt + 1>(byTypeBB, to, stmAttackers, occupied, attackers);
  65.  
  66.   occupied ^= lsb(b); // Remove the attacker from occupied
  67.  
  68.   // Add any X-ray attack behind the just removed piece. For instance with
  69.   // rooks in a8 and a7 attacking a1, after removing a7 we add rook in a8.
  70.   // Note that new added attackers can be of any color.
  71.   if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
  72.       attackers |= attacks_bb<BISHOP>(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]);
  73.  
  74.   if (Pt == ROOK || Pt == QUEEN)
  75.       attackers |= attacks_bb<ROOK>(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]);
  76.  
  77.   // X-ray may add already processed pieces because byTypeBB[] is constant: in
  78.   // the rook example, now attackers contains _again_ rook in a7, so remove it.
  79.   attackers &= occupied;
  80.   return (PieceType)Pt;
  81. }
  82.  
  83. template<>
  84. PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
  85.   return KING; // No need to update bitboards: it is the last cycle
  86. }
  87.  
  88. } // namespace
  89.  
  90.  
  91. /// operator<<(Position) returns an ASCII representation of the position
  92.  
  93. std::ostream& operator<<(std::ostream& os, const Position& pos) {
  94.  
  95.   os << "\n +---+---+---+---+---+---+---+---+\n";
  96.  
  97.   for (Rank r = RANK_8; r >= RANK_1; --r)
  98.   {
  99.       for (File f = FILE_A; f <= FILE_H; ++f)
  100.           os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
  101.  
  102.       os << " |\n +---+---+---+---+---+---+---+---+\n";
  103.   }
  104.  
  105.   os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
  106.      << std::setfill('0') << std::setw(16) << pos.key()
  107.      << std::setfill(' ') << std::dec << "\nCheckers: ";
  108.  
  109.   for (Bitboard b = pos.checkers(); b; )
  110.       os << UCI::square(pop_lsb(&b)) << " ";
  111.  
  112.   if (    int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
  113.       && !pos.can_castle(ANY_CASTLING))
  114.   {
  115.       StateInfo st;
  116.       Position p;
  117.       p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
  118.       Tablebases::ProbeState s1, s2;
  119.       Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
  120.       int dtz = Tablebases::probe_dtz(p, &s2);
  121.       os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
  122.          << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
  123.   }
  124.  
  125.   return os;
  126. }
  127.  
  128.  
  129. // Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
  130. // situations. Description of the algorithm in the following paper:
  131. // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
  132.  
  133. // First and second hash functions for indexing the cuckoo tables
  134. inline int H1(Key h) { return h & 0x1fff; }
  135. inline int H2(Key h) { return (h >> 16) & 0x1fff; }
  136.  
  137. // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
  138. Key cuckoo[8192];
  139. Move cuckooMove[8192];
  140.  
  141.  
  142. /// Position::init() initializes at startup the various arrays used to compute
  143. /// hash keys.
  144.  
  145. void Position::init() {
  146.  
  147.   PRNG rng(1070372);
  148.  
  149.   for (Piece pc : Pieces)
  150.       for (Square s = SQ_A1; s <= SQ_H8; ++s)
  151.           Zobrist::psq[pc][s] = rng.rand<Key>();
  152.  
  153.   for (File f = FILE_A; f <= FILE_H; ++f)
  154.       Zobrist::enpassant[f] = rng.rand<Key>();
  155.  
  156.   for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
  157.   {
  158.       Zobrist::castling[cr] = 0;
  159.       Bitboard b = cr;
  160.       while (b)
  161.       {
  162.           Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
  163.           Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
  164.       }
  165.   }
  166.  
  167.   Zobrist::side = rng.rand<Key>();
  168.   Zobrist::noPawns = rng.rand<Key>();
  169.  
  170.   // Prepare the cuckoo tables
  171.   std::memset(cuckoo, 0, sizeof(cuckoo));
  172.   std::memset(cuckooMove, 0, sizeof(cuckooMove));
  173.   int count = 0;
  174.   for (Piece pc : Pieces)
  175.       for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
  176.           for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
  177.               if (PseudoAttacks[type_of(pc)][s1] & s2)
  178.               {
  179.                   Move move = make_move(s1, s2);
  180.                   Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
  181.                   int i = H1(key);
  182.                   while (true)
  183.                   {
  184.                       std::swap(cuckoo[i], key);
  185.                       std::swap(cuckooMove[i], move);
  186.                       if (move == 0)   // Arrived at empty slot ?
  187.                           break;
  188.                       i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
  189.                   }
  190.                   count++;
  191.              }
  192.   assert(count == 3668);
  193. }
  194.  
  195.  
  196. /// Position::set() initializes the position object with the given FEN string.
  197. /// This function is not very robust - make sure that input FENs are correct,
  198. /// this is assumed to be the responsibility of the GUI.
  199.  
  200. Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
  201. /*
  202.    A FEN string defines a particular position using only the ASCII character set.
  203.  
  204.    A FEN string contains six fields separated by a space. The fields are:
  205.  
  206.    1) Piece placement (from white's perspective). Each rank is described, starting
  207.       with rank 8 and ending with rank 1. Within each rank, the contents of each
  208.       square are described from file A through file H. Following the Standard
  209.       Algebraic Notation (SAN), each piece is identified by a single letter taken
  210.       from the standard English names. White pieces are designated using upper-case
  211.       letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
  212.       noted using digits 1 through 8 (the number of blank squares), and "/"
  213.       separates ranks.
  214.  
  215.    2) Active color. "w" means white moves next, "b" means black.
  216.  
  217.    3) Castling availability. If neither side can castle, this is "-". Otherwise,
  218.       this has one or more letters: "K" (White can castle kingside), "Q" (White
  219.       can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
  220.       can castle queenside).
  221.  
  222.    4) En passant target square (in algebraic notation). If there's no en passant
  223.       target square, this is "-". If a pawn has just made a 2-square move, this
  224.       is the position "behind" the pawn. This is recorded only if there is a pawn
  225.       in position to make an en passant capture, and if there really is a pawn
  226.       that might have advanced two squares.
  227.  
  228.    5) Halfmove clock. This is the number of halfmoves since the last pawn advance
  229.       or capture. This is used to determine if a draw can be claimed under the
  230.       fifty-move rule.
  231.  
  232.    6) Fullmove number. The number of the full move. It starts at 1, and is
  233.       incremented after Black's move.
  234. */
  235.  
  236.   unsigned char col, row, token;
  237.   size_t idx;
  238.   Square sq = SQ_A8;
  239.   std::istringstream ss(fenStr);
  240.  
  241.   std::memset(this, 0, sizeof(Position));
  242.   std::memset(si, 0, sizeof(StateInfo));
  243.   std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
  244.   st = si;
  245.  
  246.   ss >> std::noskipws;
  247.  
  248.   // 1. Piece placement
  249.   while ((ss >> token) && !isspace(token))
  250.   {
  251.       if (isdigit(token))
  252.           sq += (token - '0') * EAST; // Advance the given number of files
  253.  
  254.       else if (token == '/')
  255.           sq += 2 * SOUTH;
  256.  
  257.       else if ((idx = PieceToChar.find(token)) != string::npos)
  258.       {
  259.           put_piece(Piece(idx), sq);
  260.           ++sq;
  261.       }
  262.   }
  263.  
  264.   // 2. Active color
  265.   ss >> token;
  266.   sideToMove = (token == 'w' ? WHITE : BLACK);
  267.   ss >> token;
  268.  
  269.   // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
  270.   // Shredder-FEN that uses the letters of the columns on which the rooks began
  271.   // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
  272.   // if an inner rook is associated with the castling right, the castling tag is
  273.   // replaced by the file letter of the involved rook, as for the Shredder-FEN.
  274.   while ((ss >> token) && !isspace(token))
  275.   {
  276.       Square rsq;
  277.       Color c = islower(token) ? BLACK : WHITE;
  278.       Piece rook = make_piece(c, ROOK);
  279.  
  280.       token = char(toupper(token));
  281.  
  282.       if (token == 'K')
  283.           for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
  284.  
  285.       else if (token == 'Q')
  286.           for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
  287.  
  288.       else if (token >= 'A' && token <= 'H')
  289.           rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
  290.  
  291.       else
  292.           continue;
  293.  
  294.       set_castling_right(c, rsq);
  295.   }
  296.  
  297.   // 4. En passant square. Ignore if no pawn capture is possible
  298.   if (   ((ss >> col) && (col >= 'a' && col <= 'h'))
  299.       && ((ss >> row) && (row == '3' || row == '6')))
  300.   {
  301.       st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
  302.  
  303.       if (   !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
  304.           || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
  305.           st->epSquare = SQ_NONE;
  306.   }
  307.   else
  308.       st->epSquare = SQ_NONE;
  309.  
  310.   // 5-6. Halfmove clock and fullmove number
  311.   ss >> std::skipws >> st->rule50 >> gamePly;
  312.  
  313.   // Convert from fullmove starting from 1 to gamePly starting from 0,
  314.   // handle also common incorrect FEN with fullmove = 0.
  315.   gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
  316.  
  317.   chess960 = isChess960;
  318.   thisThread = th;
  319.   set_state(st);
  320.  
  321.   assert(pos_is_ok());
  322.  
  323.   return *this;
  324. }
  325.  
  326.  
  327. /// Position::set_castling_right() is a helper function used to set castling
  328. /// rights given the corresponding color and the rook starting square.
  329.  
  330. void Position::set_castling_right(Color c, Square rfrom) {
  331.  
  332.   Square kfrom = square<KING>(c);
  333.   CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
  334.   CastlingRight cr = (c | cs);
  335.  
  336.   st->castlingRights |= cr;
  337.   castlingRightsMask[kfrom] |= cr;
  338.   castlingRightsMask[rfrom] |= cr;
  339.   castlingRookSquare[cr] = rfrom;
  340.  
  341.   Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
  342.   Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
  343.  
  344.   for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
  345.       if (s != kfrom && s != rfrom)
  346.           castlingPath[cr] |= s;
  347.  
  348.   for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
  349.       if (s != kfrom && s != rfrom)
  350.           castlingPath[cr] |= s;
  351. }
  352.  
  353.  
  354. /// Position::set_check_info() sets king attacks to detect if a move gives check
  355.  
  356. void Position::set_check_info(StateInfo* si) const {
  357.  
  358.   si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
  359.   si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
  360.  
  361.   Square ksq = square<KING>(~sideToMove);
  362.  
  363.   si->checkSquares[PAWN]   = attacks_from<PAWN>(ksq, ~sideToMove);
  364.   si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
  365.   si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
  366.   si->checkSquares[ROOK]   = attacks_from<ROOK>(ksq);
  367.   si->checkSquares[QUEEN]  = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
  368.   si->checkSquares[KING]   = 0;
  369. }
  370.  
  371.  
  372. /// Position::set_state() computes the hash keys of the position, and other
  373. /// data that once computed is updated incrementally as moves are made.
  374. /// The function is only used when a new position is set up, and to verify
  375. /// the correctness of the StateInfo data when running in debug mode.
  376.  
  377. void Position::set_state(StateInfo* si) const {
  378.  
  379.   si->key = si->materialKey = 0;
  380.   si->pawnKey = Zobrist::noPawns;
  381.   si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
  382.   si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
  383.  
  384.   set_check_info(si);
  385.  
  386.   for (Bitboard b = pieces(); b; )
  387.   {
  388.       Square s = pop_lsb(&b);
  389.       Piece pc = piece_on(s);
  390.       si->key ^= Zobrist::psq[pc][s];
  391.   }
  392.  
  393.   if (si->epSquare != SQ_NONE)
  394.       si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
  395.  
  396.   if (sideToMove == BLACK)
  397.       si->key ^= Zobrist::side;
  398.  
  399.   si->key ^= Zobrist::castling[si->castlingRights];
  400.  
  401.   for (Bitboard b = pieces(PAWN); b; )
  402.   {
  403.       Square s = pop_lsb(&b);
  404.       si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
  405.   }
  406.  
  407.   for (Piece pc : Pieces)
  408.   {
  409.       if (type_of(pc) != PAWN && type_of(pc) != KING)
  410.           si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
  411.  
  412.       for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
  413.           si->materialKey ^= Zobrist::psq[pc][cnt];
  414.   }
  415. }
  416.  
  417.  
  418. /// Position::set() is an overload to initialize the position object with
  419. /// the given endgame code string like "KBPKN". It is mainly a helper to
  420. /// get the material key out of an endgame code.
  421.  
  422. Position& Position::set(const string& code, Color c, StateInfo* si) {
  423.  
  424.   assert(code.length() > 0 && code.length() < 8);
  425.   assert(code[0] == 'K');
  426.  
  427.   string sides[] = { code.substr(code.find('K', 1)),      // Weak
  428.                      code.substr(0, code.find('K', 1)) }; // Strong
  429.  
  430.   std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
  431.  
  432.   string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
  433.                        + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
  434.  
  435.   return set(fenStr, false, si, nullptr);
  436. }
  437.  
  438.  
  439. /// Position::fen() returns a FEN representation of the position. In case of
  440. /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
  441.  
  442. const string Position::fen() const {
  443.  
  444.   int emptyCnt;
  445.   std::ostringstream ss;
  446.  
  447.   for (Rank r = RANK_8; r >= RANK_1; --r)
  448.   {
  449.       for (File f = FILE_A; f <= FILE_H; ++f)
  450.       {
  451.           for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
  452.               ++emptyCnt;
  453.  
  454.           if (emptyCnt)
  455.               ss << emptyCnt;
  456.  
  457.           if (f <= FILE_H)
  458.               ss << PieceToChar[piece_on(make_square(f, r))];
  459.       }
  460.  
  461.       if (r > RANK_1)
  462.           ss << '/';
  463.   }
  464.  
  465.   ss << (sideToMove == WHITE ? " w " : " b ");
  466.  
  467.   if (can_castle(WHITE_OO))
  468.       ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE |  KING_SIDE))) : 'K');
  469.  
  470.   if (can_castle(WHITE_OOO))
  471.       ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
  472.  
  473.   if (can_castle(BLACK_OO))
  474.       ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK |  KING_SIDE))) : 'k');
  475.  
  476.   if (can_castle(BLACK_OOO))
  477.       ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
  478.  
  479.   if (!can_castle(WHITE) && !can_castle(BLACK))
  480.       ss << '-';
  481.  
  482.   ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
  483.      << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
  484.  
  485.   return ss.str();
  486. }
  487.  
  488.  
  489. /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
  490. /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
  491. /// slider if removing that piece from the board would result in a position where
  492. /// square 's' is attacked. For example, a king-attack blocking piece can be either
  493. /// a pinned or a discovered check piece, according if its color is the opposite
  494. /// or the same of the color of the slider.
  495.  
  496. Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
  497.  
  498.   Bitboard blockers = 0;
  499.   pinners = 0;
  500.  
  501.   // Snipers are sliders that attack 's' when a piece is removed
  502.   Bitboard snipers = (  (PseudoAttacks[  ROOK][s] & pieces(QUEEN, ROOK))
  503.                       | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
  504.  
  505.   while (snipers)
  506.   {
  507.     Square sniperSq = pop_lsb(&snipers);
  508.     Bitboard b = between_bb(s, sniperSq) & pieces();
  509.  
  510.     if (b && !more_than_one(b))
  511.     {
  512.         blockers |= b;
  513.         if (b & pieces(color_of(piece_on(s))))
  514.             pinners |= sniperSq;
  515.     }
  516.   }
  517.   return blockers;
  518. }
  519.  
  520.  
  521. /// Position::attackers_to() computes a bitboard of all pieces which attack a
  522. /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
  523.  
  524. Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
  525.  
  526.   return  (attacks_from<PAWN>(s, BLACK)    & pieces(WHITE, PAWN))
  527.         | (attacks_from<PAWN>(s, WHITE)    & pieces(BLACK, PAWN))
  528.         | (attacks_from<KNIGHT>(s)         & pieces(KNIGHT))
  529.         | (attacks_bb<  ROOK>(s, occupied) & pieces(  ROOK, QUEEN))
  530.         | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
  531.         | (attacks_from<KING>(s)           & pieces(KING));
  532. }
  533.  
  534.  
  535. /// Position::legal() tests whether a pseudo-legal move is legal
  536.  
  537. bool Position::legal(Move m) const {
  538.  
  539.   assert(is_ok(m));
  540.  
  541.   Color us = sideToMove;
  542.   Square from = from_sq(m);
  543.  
  544.   assert(color_of(moved_piece(m)) == us);
  545.   assert(piece_on(square<KING>(us)) == make_piece(us, KING));
  546.  
  547.   // En passant captures are a tricky special case. Because they are rather
  548.   // uncommon, we do it simply by testing whether the king is attacked after
  549.   // the move is made.
  550.   if (type_of(m) == ENPASSANT)
  551.   {
  552.       Square ksq = square<KING>(us);
  553.       Square to = to_sq(m);
  554.       Square capsq = to - pawn_push(us);
  555.       Bitboard occupied = (pieces() ^ from ^ capsq) | to;
  556.  
  557.       assert(to == ep_square());
  558.       assert(moved_piece(m) == make_piece(us, PAWN));
  559.       assert(piece_on(capsq) == make_piece(~us, PAWN));
  560.       assert(piece_on(to) == NO_PIECE);
  561.  
  562.       return   !(attacks_bb<  ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
  563.             && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
  564.   }
  565.  
  566.   // If the moving piece is a king, check whether the destination
  567.   // square is attacked by the opponent. Castling moves are checked
  568.   // for legality during move generation.
  569.   if (type_of(piece_on(from)) == KING)
  570.       return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
  571.  
  572.   // A non-king move is legal if and only if it is not pinned or it
  573.   // is moving along the ray towards or away from the king.
  574.   return   !(blockers_for_king(us) & from)
  575.         ||  aligned(from, to_sq(m), square<KING>(us));
  576. }
  577.  
  578.  
  579. /// Position::pseudo_legal() takes a random move and tests whether the move is
  580. /// pseudo legal. It is used to validate moves from TT that can be corrupted
  581. /// due to SMP concurrent access or hash position key aliasing.
  582.  
  583. bool Position::pseudo_legal(const Move m) const {
  584.  
  585.   Color us = sideToMove;
  586.   Square from = from_sq(m);
  587.   Square to = to_sq(m);
  588.   Piece pc = moved_piece(m);
  589.  
  590.   // Use a slower but simpler function for uncommon cases
  591.   if (type_of(m) != NORMAL)
  592.       return MoveList<LEGAL>(*this).contains(m);
  593.  
  594.   // Is not a promotion, so promotion piece must be empty
  595.   if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
  596.       return false;
  597.  
  598.   // If the 'from' square is not occupied by a piece belonging to the side to
  599.   // move, the move is obviously not legal.
  600.   if (pc == NO_PIECE || color_of(pc) != us)
  601.       return false;
  602.  
  603.   // The destination square cannot be occupied by a friendly piece
  604.   if (pieces(us) & to)
  605.       return false;
  606.  
  607.   // Handle the special case of a pawn move
  608.   if (type_of(pc) == PAWN)
  609.   {
  610.       // We have already handled promotion moves, so destination
  611.       // cannot be on the 8th/1st rank.
  612.       if (rank_of(to) == relative_rank(us, RANK_8))
  613.           return false;
  614.  
  615.       if (   !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
  616.           && !((from + pawn_push(us) == to) && empty(to))       // Not a single push
  617.           && !(   (from + 2 * pawn_push(us) == to)              // Not a double push
  618.                && (rank_of(from) == relative_rank(us, RANK_2))
  619.                && empty(to)
  620.                && empty(to - pawn_push(us))))
  621.           return false;
  622.   }
  623.   else if (!(attacks_from(type_of(pc), from) & to))
  624.       return false;
  625.  
  626.   // Evasions generator already takes care to avoid some kind of illegal moves
  627.   // and legal() relies on this. We therefore have to take care that the same
  628.   // kind of moves are filtered out here.
  629.   if (checkers())
  630.   {
  631.       if (type_of(pc) != KING)
  632.       {
  633.           // Double check? In this case a king move is required
  634.           if (more_than_one(checkers()))
  635.               return false;
  636.  
  637.           // Our move must be a blocking evasion or a capture of the checking piece
  638.           if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
  639.               return false;
  640.       }
  641.       // In case of king moves under check we have to remove king so as to catch
  642.       // invalid moves like b1a1 when opposite queen is on c1.
  643.       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
  644.           return false;
  645.   }
  646.  
  647.   return true;
  648. }
  649.  
  650.  
  651. /// Position::gives_check() tests whether a pseudo-legal move gives a check
  652.  
  653. bool Position::gives_check(Move m) const {
  654.  
  655.   assert(is_ok(m));
  656.   assert(color_of(moved_piece(m)) == sideToMove);
  657.  
  658.   Square from = from_sq(m);
  659.   Square to = to_sq(m);
  660.  
  661.   // Is there a direct check?
  662.   if (st->checkSquares[type_of(piece_on(from))] & to)
  663.       return true;
  664.  
  665.   // Is there a discovered check?
  666.   if (   (st->blockersForKing[~sideToMove] & from)
  667.       && !aligned(from, to, square<KING>(~sideToMove)))
  668.       return true;
  669.  
  670.   switch (type_of(m))
  671.   {
  672.   case NORMAL:
  673.       return false;
  674.  
  675.   case PROMOTION:
  676.       return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
  677.  
  678.   // En passant capture with check? We have already handled the case
  679.   // of direct checks and ordinary discovered check, so the only case we
  680.   // need to handle is the unusual case of a discovered check through
  681.   // the captured pawn.
  682.   case ENPASSANT:
  683.   {
  684.       Square capsq = make_square(file_of(to), rank_of(from));
  685.       Bitboard b = (pieces() ^ from ^ capsq) | to;
  686.  
  687.       return  (attacks_bb<  ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
  688.             | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
  689.   }
  690.   case CASTLING:
  691.   {
  692.       Square kfrom = from;
  693.       Square rfrom = to; // Castling is encoded as 'King captures the rook'
  694.       Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
  695.       Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
  696.  
  697.       return   (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
  698.             && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
  699.   }
  700.   default:
  701.       assert(false);
  702.       return false;
  703.   }
  704. }
  705.  
  706.  
  707. /// Position::do_move() makes a move, and saves all information necessary
  708. /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
  709. /// moves should be filtered out before this function is called.
  710.  
  711. void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
  712.  
  713.   assert(is_ok(m));
  714.   assert(&newSt != st);
  715.  
  716.   thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
  717.   Key k = st->key ^ Zobrist::side;
  718.  
  719.   // Copy some fields of the old state to our new StateInfo object except the
  720.   // ones which are going to be recalculated from scratch anyway and then switch
  721.   // our state pointer to point to the new (ready to be updated) state.
  722.   std::memcpy(&newSt, st, offsetof(StateInfo, key));
  723.   newSt.previous = st;
  724.   st = &newSt;
  725.  
  726.   // Increment ply counters. In particular, rule50 will be reset to zero later on
  727.   // in case of a capture or a pawn move.
  728.   ++gamePly;
  729.   ++st->rule50;
  730.   ++st->pliesFromNull;
  731.  
  732.   Color us = sideToMove;
  733.   Color them = ~us;
  734.   Square from = from_sq(m);
  735.   Square to = to_sq(m);
  736.   Piece pc = piece_on(from);
  737.   Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
  738.  
  739.   assert(color_of(pc) == us);
  740.   assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
  741.   assert(type_of(captured) != KING);
  742.  
  743.   if (type_of(m) == CASTLING)
  744.   {
  745.       assert(pc == make_piece(us, KING));
  746.       assert(captured == make_piece(us, ROOK));
  747.  
  748.       Square rfrom, rto;
  749.       do_castling<true>(us, from, to, rfrom, rto);
  750.  
  751.       k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
  752.       captured = NO_PIECE;
  753.   }
  754.  
  755.   if (captured)
  756.   {
  757.       Square capsq = to;
  758.  
  759.       // If the captured piece is a pawn, update pawn hash key, otherwise
  760.       // update non-pawn material.
  761.       if (type_of(captured) == PAWN)
  762.       {
  763.           if (type_of(m) == ENPASSANT)
  764.           {
  765.               capsq -= pawn_push(us);
  766.  
  767.               assert(pc == make_piece(us, PAWN));
  768.               assert(to == st->epSquare);
  769.               assert(relative_rank(us, to) == RANK_6);
  770.               assert(piece_on(to) == NO_PIECE);
  771.               assert(piece_on(capsq) == make_piece(them, PAWN));
  772.  
  773.               board[capsq] = NO_PIECE; // Not done by remove_piece()
  774.           }
  775.  
  776.           st->pawnKey ^= Zobrist::psq[captured][capsq];
  777.       }
  778.       else
  779.           st->nonPawnMaterial[them] -= PieceValue[MG][captured];
  780.  
  781.       // Update board and piece lists
  782.       remove_piece(captured, capsq);
  783.  
  784.       // Update material hash key and prefetch access to materialTable
  785.       k ^= Zobrist::psq[captured][capsq];
  786.       st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
  787.       prefetch(thisThread->materialTable[st->materialKey]);
  788.  
  789.       // Reset rule 50 counter
  790.       st->rule50 = 0;
  791.   }
  792.  
  793.   // Update hash key
  794.   k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
  795.  
  796.   // Reset en passant square
  797.   if (st->epSquare != SQ_NONE)
  798.   {
  799.       k ^= Zobrist::enpassant[file_of(st->epSquare)];
  800.       st->epSquare = SQ_NONE;
  801.   }
  802.  
  803.   // Update castling rights if needed
  804.   if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
  805.   {
  806.       int cr = castlingRightsMask[from] | castlingRightsMask[to];
  807.       k ^= Zobrist::castling[st->castlingRights & cr];
  808.       st->castlingRights &= ~cr;
  809.   }
  810.  
  811.   // Move the piece. The tricky Chess960 castling is handled earlier
  812.   if (type_of(m) != CASTLING)
  813.       move_piece(pc, from, to);
  814.  
  815.   // If the moving piece is a pawn do some special extra work
  816.   if (type_of(pc) == PAWN)
  817.   {
  818.       // Set en-passant square if the moved pawn can be captured
  819.       if (   (int(to) ^ int(from)) == 16
  820.           && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
  821.       {
  822.           st->epSquare = to - pawn_push(us);
  823.           k ^= Zobrist::enpassant[file_of(st->epSquare)];
  824.       }
  825.  
  826.       else if (type_of(m) == PROMOTION)
  827.       {
  828.           Piece promotion = make_piece(us, promotion_type(m));
  829.  
  830.           assert(relative_rank(us, to) == RANK_8);
  831.           assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
  832.  
  833.           remove_piece(pc, to);
  834.           put_piece(promotion, to);
  835.  
  836.           // Update hash keys
  837.           k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
  838.           st->pawnKey ^= Zobrist::psq[pc][to];
  839.           st->materialKey ^=  Zobrist::psq[promotion][pieceCount[promotion]-1]
  840.                             ^ Zobrist::psq[pc][pieceCount[pc]];
  841.  
  842.           // Update material
  843.           st->nonPawnMaterial[us] += PieceValue[MG][promotion];
  844.       }
  845.  
  846.       // Update pawn hash key and prefetch access to pawnsTable
  847.       st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
  848.       prefetch2(thisThread->pawnsTable[st->pawnKey]);
  849.  
  850.       // Reset rule 50 draw counter
  851.       st->rule50 = 0;
  852.   }
  853.  
  854.   // Set capture piece
  855.   st->capturedPiece = captured;
  856.  
  857.   // Update the key with the final value
  858.   st->key = k;
  859.  
  860.   // Calculate checkers bitboard (if move gives check)
  861.   st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
  862.  
  863.   sideToMove = ~sideToMove;
  864.  
  865.   // Update king attacks used for fast check detection
  866.   set_check_info(st);
  867.  
  868.   assert(pos_is_ok());
  869. }
  870.  
  871.  
  872. /// Position::undo_move() unmakes a move. When it returns, the position should
  873. /// be restored to exactly the same state as before the move was made.
  874.  
  875. void Position::undo_move(Move m) {
  876.  
  877.   assert(is_ok(m));
  878.  
  879.   sideToMove = ~sideToMove;
  880.  
  881.   Color us = sideToMove;
  882.   Square from = from_sq(m);
  883.   Square to = to_sq(m);
  884.   Piece pc = piece_on(to);
  885.  
  886.   assert(empty(from) || type_of(m) == CASTLING);
  887.   assert(type_of(st->capturedPiece) != KING);
  888.  
  889.   if (type_of(m) == PROMOTION)
  890.   {
  891.       assert(relative_rank(us, to) == RANK_8);
  892.       assert(type_of(pc) == promotion_type(m));
  893.       assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
  894.  
  895.       remove_piece(pc, to);
  896.       pc = make_piece(us, PAWN);
  897.       put_piece(pc, to);
  898.   }
  899.  
  900.   if (type_of(m) == CASTLING)
  901.   {
  902.       Square rfrom, rto;
  903.       do_castling<false>(us, from, to, rfrom, rto);
  904.   }
  905.   else
  906.   {
  907.       move_piece(pc, to, from); // Put the piece back at the source square
  908.  
  909.       if (st->capturedPiece)
  910.       {
  911.           Square capsq = to;
  912.  
  913.           if (type_of(m) == ENPASSANT)
  914.           {
  915.               capsq -= pawn_push(us);
  916.  
  917.               assert(type_of(pc) == PAWN);
  918.               assert(to == st->previous->epSquare);
  919.               assert(relative_rank(us, to) == RANK_6);
  920.               assert(piece_on(capsq) == NO_PIECE);
  921.               assert(st->capturedPiece == make_piece(~us, PAWN));
  922.           }
  923.  
  924.           put_piece(st->capturedPiece, capsq); // Restore the captured piece
  925.       }
  926.   }
  927.  
  928.   // Finally point our state pointer back to the previous state
  929.   st = st->previous;
  930.   --gamePly;
  931.  
  932.   assert(pos_is_ok());
  933. }
  934.  
  935.  
  936. /// Position::do_castling() is a helper used to do/undo a castling move. This
  937. /// is a bit tricky in Chess960 where from/to squares can overlap.
  938. template<bool Do>
  939. void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
  940.  
  941.   bool kingSide = to > from;
  942.   rfrom = to; // Castling is encoded as "king captures friendly rook"
  943.   rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
  944.   to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
  945.  
  946.   // Remove both pieces first since squares could overlap in Chess960
  947.   remove_piece(make_piece(us, KING), Do ? from : to);
  948.   remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
  949.   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
  950.   put_piece(make_piece(us, KING), Do ? to : from);
  951.   put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
  952. }
  953.  
  954.  
  955. /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
  956. /// the side to move without executing any move on the board.
  957.  
  958. void Position::do_null_move(StateInfo& newSt) {
  959.  
  960.   assert(!checkers());
  961.   assert(&newSt != st);
  962.  
  963.   std::memcpy(&newSt, st, sizeof(StateInfo));
  964.   newSt.previous = st;
  965.   st = &newSt;
  966.  
  967.   if (st->epSquare != SQ_NONE)
  968.   {
  969.       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
  970.       st->epSquare = SQ_NONE;
  971.   }
  972.  
  973.   st->key ^= Zobrist::side;
  974.   prefetch(TT.first_entry(st->key));
  975.  
  976.   ++st->rule50;
  977.   st->pliesFromNull = 0;
  978.  
  979.   sideToMove = ~sideToMove;
  980.  
  981.   set_check_info(st);
  982.  
  983.   assert(pos_is_ok());
  984. }
  985.  
  986. void Position::undo_null_move() {
  987.  
  988.   assert(!checkers());
  989.  
  990.   st = st->previous;
  991.   sideToMove = ~sideToMove;
  992. }
  993.  
  994.  
  995. /// Position::key_after() computes the new hash key after the given move. Needed
  996. /// for speculative prefetch. It doesn't recognize special moves like castling,
  997. /// en-passant and promotions.
  998.  
  999. Key Position::key_after(Move m) const {
  1000.  
  1001.   Square from = from_sq(m);
  1002.   Square to = to_sq(m);
  1003.   Piece pc = piece_on(from);
  1004.   Piece captured = piece_on(to);
  1005.   Key k = st->key ^ Zobrist::side;
  1006.  
  1007.   if (captured)
  1008.       k ^= Zobrist::psq[captured][to];
  1009.  
  1010.   return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
  1011. }
  1012.  
  1013.  
  1014. /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
  1015. /// SEE value of move is greater or equal to the given threshold. We'll use an
  1016. /// algorithm similar to alpha-beta pruning with a null window.
  1017.  
  1018. bool Position::see_ge(Move m, Value threshold) const {
  1019.  
  1020.   assert(is_ok(m));
  1021.  
  1022.   // Only deal with normal moves, assume others pass a simple see
  1023.   if (type_of(m) != NORMAL)
  1024.       return VALUE_ZERO >= threshold;
  1025.  
  1026.   Bitboard stmAttackers;
  1027.   Square from = from_sq(m), to = to_sq(m);
  1028.   PieceType nextVictim = type_of(piece_on(from));
  1029.   Color us = color_of(piece_on(from));
  1030.   Color stm = ~us; // First consider opponent's move
  1031.   Value balance;   // Values of the pieces taken by us minus opponent's ones
  1032.  
  1033.   // The opponent may be able to recapture so this is the best result
  1034.   // we can hope for.
  1035.   balance = PieceValue[MG][piece_on(to)] - threshold;
  1036.  
  1037.   if (balance < VALUE_ZERO)
  1038.       return false;
  1039.  
  1040.   // Now assume the worst possible result: that the opponent can
  1041.   // capture our piece for free.
  1042.   balance -= PieceValue[MG][nextVictim];
  1043.  
  1044.   // If it is enough (like in PxQ) then return immediately. Note that
  1045.   // in case nextVictim == KING we always return here, this is ok
  1046.   // if the given move is legal.
  1047.   if (balance >= VALUE_ZERO)
  1048.       return true;
  1049.  
  1050.   // Find all attackers to the destination square, with the moving piece
  1051.   // removed, but possibly an X-ray attacker added behind it.
  1052.   Bitboard occupied = pieces() ^ from ^ to;
  1053.   Bitboard attackers = attackers_to(to, occupied) & occupied;
  1054.  
  1055.   while (true)
  1056.   {
  1057.       stmAttackers = attackers & pieces(stm);
  1058.  
  1059.       // Don't allow pinned pieces to attack (except the king) as long as
  1060.       // all pinners are on their original square.
  1061.       if (!(st->pinners[~stm] & ~occupied))
  1062.           stmAttackers &= ~st->blockersForKing[stm];
  1063.  
  1064.       // If stm has no more attackers then give up: stm loses
  1065.       if (!stmAttackers)
  1066.           break;
  1067.  
  1068.       // Locate and remove the next least valuable attacker, and add to
  1069.       // the bitboard 'attackers' the possibly X-ray attackers behind it.
  1070.       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
  1071.  
  1072.       stm = ~stm; // Switch side to move
  1073.  
  1074.       // Negamax the balance with alpha = balance, beta = balance+1 and
  1075.       // add nextVictim's value.
  1076.       //
  1077.       //      (balance, balance+1) -> (-balance-1, -balance)
  1078.       //
  1079.       assert(balance < VALUE_ZERO);
  1080.  
  1081.       balance = -balance - 1 - PieceValue[MG][nextVictim];
  1082.  
  1083.       // If balance is still non-negative after giving away nextVictim then we
  1084.       // win. The only thing to be careful about it is that we should revert
  1085.       // stm if we captured with the king when the opponent still has attackers.
  1086.       if (balance >= VALUE_ZERO)
  1087.       {
  1088.           if (nextVictim == KING && (attackers & pieces(stm)))
  1089.               stm = ~stm;
  1090.           break;
  1091.       }
  1092.       assert(nextVictim != KING);
  1093.   }
  1094.   return us != stm; // We break the above loop when stm loses
  1095. }
  1096.  
  1097.  
  1098. /// Position::is_draw() tests whether the position is drawn by 50-move rule
  1099. /// or by repetition. It does not detect stalemates.
  1100.  
  1101. bool Position::is_draw(int ply) const {
  1102.  
  1103.   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
  1104.       return true;
  1105.  
  1106.   int end = std::min(st->rule50, st->pliesFromNull);
  1107.  
  1108.   if (end < 4)
  1109.     return false;
  1110.  
  1111.   StateInfo* stp = st->previous->previous;
  1112.   int cnt = 0;
  1113.  
  1114.   for (int i = 4; i <= end; i += 2)
  1115.   {
  1116.       stp = stp->previous->previous;
  1117.  
  1118.       // Return a draw score if a position repeats once earlier but strictly
  1119.       // after the root, or repeats twice before or at the root.
  1120.       if (   stp->key == st->key
  1121.           && ++cnt + (ply > i) == 2)
  1122.           return true;
  1123.   }
  1124.  
  1125.   return false;
  1126. }
  1127.  
  1128.  
  1129. // Position::has_repeated() tests whether there has been at least one repetition
  1130. // of positions since the last capture or pawn move.
  1131.  
  1132. bool Position::has_repeated() const {
  1133.  
  1134.     StateInfo* stc = st;
  1135.     while (true)
  1136.     {
  1137.         int i = 4, end = std::min(stc->rule50, stc->pliesFromNull);
  1138.  
  1139.         if (end < i)
  1140.             return false;
  1141.  
  1142.         StateInfo* stp = stc->previous->previous;
  1143.  
  1144.         do {
  1145.             stp = stp->previous->previous;
  1146.  
  1147.             if (stp->key == stc->key)
  1148.                 return true;
  1149.  
  1150.             i += 2;
  1151.         } while (i <= end);
  1152.  
  1153.         stc = stc->previous;
  1154.     }
  1155. }
  1156.  
  1157.  
  1158. /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
  1159. /// or an earlier position has a move that directly reaches the current position.
  1160.  
  1161. bool Position::has_game_cycle(int ply) const {
  1162.  
  1163.   int j;
  1164.  
  1165.   int end = std::min(st->rule50, st->pliesFromNull);
  1166.  
  1167.   if (end < 3)
  1168.     return false;
  1169.  
  1170.   Key originalKey = st->key;
  1171.   StateInfo* stp = st->previous;
  1172.  
  1173.   for (int i = 3; i <= end; i += 2)
  1174.   {
  1175.       stp = stp->previous->previous;
  1176.  
  1177.       Key moveKey = originalKey ^ stp->key;
  1178.       if (   (j = H1(moveKey), cuckoo[j] == moveKey)
  1179.           || (j = H2(moveKey), cuckoo[j] == moveKey))
  1180.       {
  1181.           Move move = cuckooMove[j];
  1182.           Square s1 = from_sq(move);
  1183.           Square s2 = to_sq(move);
  1184.  
  1185.           if (!(between_bb(s1, s2) & pieces()))
  1186.           {
  1187.               // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in the same
  1188.               // location. We select the legal one by reversing the move variable if necessary.
  1189.               if (empty(s1))
  1190.                   move = make_move(s2, s1);
  1191.  
  1192.               if (ply > i)
  1193.                   return true;
  1194.  
  1195.               // For repetitions before or at the root, require one more
  1196.               StateInfo* next_stp = stp;
  1197.               for (int k = i + 2; k <= end; k += 2)
  1198.               {
  1199.                   next_stp = next_stp->previous->previous;
  1200.                   if (next_stp->key == stp->key)
  1201.                      return true;
  1202.               }
  1203.           }
  1204.       }
  1205.   }
  1206.   return false;
  1207. }
  1208.  
  1209.  
  1210. /// Position::flip() flips position with the white and black sides reversed. This
  1211. /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
  1212.  
  1213. void Position::flip() {
  1214.  
  1215.   string f, token;
  1216.   std::stringstream ss(fen());
  1217.  
  1218.   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
  1219.   {
  1220.       std::getline(ss, token, r > RANK_1 ? '/' : ' ');
  1221.       f.insert(0, token + (f.empty() ? " " : "/"));
  1222.   }
  1223.  
  1224.   ss >> token; // Active color
  1225.   f += (token == "w" ? "B " : "W "); // Will be lowercased later
  1226.  
  1227.   ss >> token; // Castling availability
  1228.   f += token + " ";
  1229.  
  1230.   std::transform(f.begin(), f.end(), f.begin(),
  1231.                  [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
  1232.  
  1233.   ss >> token; // En passant square
  1234.   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
  1235.  
  1236.   std::getline(ss, token); // Half and full moves
  1237.   f += token;
  1238.  
  1239.   set(f, is_chess960(), st, this_thread());
  1240.  
  1241.   assert(pos_is_ok());
  1242. }
  1243.  
  1244.  
  1245. /// Position::pos_is_ok() performs some consistency checks for the
  1246. /// position object and raises an asserts if something wrong is detected.
  1247. /// This is meant to be helpful when debugging.
  1248.  
  1249. bool Position::pos_is_ok() const {
  1250.  
  1251.   constexpr bool Fast = true; // Quick (default) or full check?
  1252.  
  1253.   if (   (sideToMove != WHITE && sideToMove != BLACK)
  1254.       || piece_on(square<KING>(WHITE)) != W_KING
  1255.       || piece_on(square<KING>(BLACK)) != B_KING
  1256.       || (   ep_square() != SQ_NONE
  1257.           && relative_rank(sideToMove, ep_square()) != RANK_6))
  1258.       assert(0 && "pos_is_ok: Default");
  1259.  
  1260.   if (Fast)
  1261.       return true;
  1262.  
  1263.   if (   pieceCount[W_KING] != 1
  1264.       || pieceCount[B_KING] != 1
  1265.       || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
  1266.       assert(0 && "pos_is_ok: Kings");
  1267.  
  1268.   if (   (pieces(PAWN) & (Rank1BB | Rank8BB))
  1269.       || pieceCount[W_PAWN] > 8
  1270.       || pieceCount[B_PAWN] > 8)
  1271.       assert(0 && "pos_is_ok: Pawns");
  1272.  
  1273.   if (   (pieces(WHITE) & pieces(BLACK))
  1274.       || (pieces(WHITE) | pieces(BLACK)) != pieces()
  1275.       || popcount(pieces(WHITE)) > 16
  1276.       || popcount(pieces(BLACK)) > 16)
  1277.       assert(0 && "pos_is_ok: Bitboards");
  1278.  
  1279.   for (PieceType p1 = PAWN; p1 <= KING; ++p1)
  1280.       for (PieceType p2 = PAWN; p2 <= KING; ++p2)
  1281.           if (p1 != p2 && (pieces(p1) & pieces(p2)))
  1282.               assert(0 && "pos_is_ok: Bitboards");
  1283.  
  1284.   StateInfo si = *st;
  1285.   set_state(&si);
  1286.   if (std::memcmp(&si, st, sizeof(StateInfo)))
  1287.       assert(0 && "pos_is_ok: State");
  1288.  
  1289.   for (Piece pc : Pieces)
  1290.   {
  1291.       if (   pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
  1292.           || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
  1293.           assert(0 && "pos_is_ok: Pieces");
  1294.  
  1295.       for (int i = 0; i < pieceCount[pc]; ++i)
  1296.           if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
  1297.               assert(0 && "pos_is_ok: Index");
  1298.   }
  1299.  
  1300.   for (Color c = WHITE; c <= BLACK; ++c)
  1301.       for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
  1302.       {
  1303.           if (!can_castle(c | s))
  1304.               continue;
  1305.  
  1306.           if (   piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
  1307.               || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
  1308.               || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
  1309.               assert(0 && "pos_is_ok: Castling");
  1310.       }
  1311.  
  1312.   return true;
  1313. }
  1314.