WebSVN – Games.Chess Giants – Diff – /engine-stockfish/position.cpp

   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
-  Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, 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.
 #include "tt.h"
 #include "uci.h"
 #include "syzygy/tbprobe.h"
 using std::string;
-namespace PSQT {
-  extern Score psq[PIECE_NB][SQUARE_NB];
-}
 namespace Zobrist {
   Key psq[PIECE_NB][SQUARE_NB];
   Key enpassant[FILE_NB];
 namespace {
 const string PieceToChar(" PNBRQK  pnbrqk");
-const Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
+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 };
+                             B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
 // min_attacker() is a helper function used by see_ge() to locate the least
 // valuable attacker for the side to move, remove the attacker we just found
 // from the bitboards and scan for new X-ray attacks behind it.
 template<int Pt>
-PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
+PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers,
                        Bitboard& occupied, Bitboard& attackers) {
-  Bitboard b = stmAttackers & bb[Pt];
+  Bitboard b = stmAttackers & byTypeBB[Pt];
   if (!b)
-      return min_attacker<Pt + 1>(bb, to, stmAttackers, occupied, attackers);
+      return min_attacker<Pt + 1>(byTypeBB, to, stmAttackers, occupied, attackers);
-  occupied ^= b & ~(b - 1);
+  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) & (bb[BISHOP] | bb[QUEEN]);
+      attackers |= attacks_bb<BISHOP>(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]);
   if (Pt == ROOK || Pt == QUEEN)
-      attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
+      attackers |= attacks_bb<ROOK>(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]);
+  // X-ray may add already processed pieces because byTypeBB[] is constant: in
-  attackers &= occupied; // After X-ray that may add already processed pieces
+  // 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&) {
          << "\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.
+      }
+  }
   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,
 /// Position::set_check_info() sets king attacks to detect if a move gives check
 void Position::set_check_info(StateInfo* si) const {
-  si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
+  si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
-  si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[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);
 void Position::set_state(StateInfo* si) const {
   si->key = si->materialKey = 0;
   si->pawnKey = Zobrist::noPawns;
   si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
-  si->psq = SCORE_ZERO;
   si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
   set_check_info(si);
   for (Bitboard b = pieces(); b; )
+  {
       Square s = pop_lsb(&b);
       Piece pc = piece_on(s);
       si->key ^= Zobrist::psq[pc][s];
-      si->psq += PSQT::psq[pc][s];
+  }
   if (si->epSquare != SQ_NONE)
       si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
 /// a pinned or a discovered check piece, according if its color is the opposite
 /// or the same of the color of the slider.
 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
-  Bitboard result = 0;
+  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 (!more_than_one(b))
+    if (b && !more_than_one(b))
+    {
-        result |= b;
+        blockers |= b;
         if (b & pieces(color_of(piece_on(s))))
             pinners |= sniperSq;
+    }
+  }
-  return result;
+  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.
   if (type_of(piece_on(from)) == KING)
       return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
   // A non-king move is legal if and only if it is not pinned or it
   // is moving along the ray towards or away from the king.
-  return   !(pinned_pieces(us) & from)
+  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
   // Is there a direct check?
   if (st->checkSquares[type_of(piece_on(from))] & to)
       return true;
   // Is there a discovered check?
-  if (   (discovered_check_candidates() & from)
+  if (   (st->blockersForKing[~sideToMove] & from)
       && !aligned(from, to, square<KING>(~sideToMove)))
       return true;
   switch (type_of(m))
+  {
       assert(captured == make_piece(us, ROOK));
       Square rfrom, rto;
       do_castling<true>(us, from, to, rfrom, rto);
-      st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
       k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
       captured = NO_PIECE;
+  }
   if (captured)
       // 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]);
-      // Update incremental scores
-      st->psq -= PSQT::psq[captured][capsq];
       // Reset rule 50 counter
       st->rule50 = 0;
+  }
           // 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 incremental score
-          st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
           // Update material
           st->nonPawnMaterial[us] += PieceValue[MG][promotion];
+      }
       prefetch2(thisThread->pawnsTable[st->pawnKey]);
       // Reset rule 50 draw counter
       st->rule50 = 0;
+  }
-  // Update incremental scores
-  st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
   // Set capture piece
   st->capturedPiece = captured;
   // Update the key with the final value
   // Only deal with normal moves, assume others pass a simple see
   if (type_of(m) != NORMAL)
       return VALUE_ZERO >= threshold;
+  Bitboard stmAttackers;
   Square from = from_sq(m), to = to_sq(m);
   PieceType nextVictim = type_of(piece_on(from));
+  Color us = color_of(piece_on(from));
-  Color stm = ~color_of(piece_on(from)); // First consider opponent's move
+  Color stm = ~us; // First consider opponent's move
-  Value balance; // Values of the pieces taken by us minus opponent's ones
+  Value balance;   // Values of the pieces taken by us minus opponent's ones
-  Bitboard occupied, stmAttackers;
   // The opponent may be able to recapture so this is the best result
   // we can hope for.
   balance = PieceValue[MG][piece_on(to)] - threshold;
   // Now assume the worst possible result: that the opponent can
   // capture our piece for free.
   balance -= PieceValue[MG][nextVictim];
+  // If it is enough (like in PxQ) then return immediately. Note that
-  if (balance >= VALUE_ZERO) // Always true if nextVictim == KING
+  // in case nextVictim == KING we always return here, this is ok
+  // if the given move is legal.
+  if (balance >= VALUE_ZERO)
       return true;
-  bool opponentToMove = true;
-  occupied = pieces() ^ from ^ to;
-  // Find all attackers to the destination square, with the moving piece removed,
+  // Find all attackers to the destination square, with the moving piece
-  // but possibly an X-ray attacker added behind it.
+  // removed, but possibly an X-ray attacker added behind it.
+  Bitboard occupied = pieces() ^ from ^ to;
   Bitboard attackers = attackers_to(to, occupied) & occupied;
   while (true)
+  {
-      // The balance is negative only because we assumed we could win
-      // the last piece for free. We are truly winning only if we can
-      // win the last piece _cheaply enough_. Test if we can actually
-      // do this otherwise "give up".
-      assert(balance < VALUE_ZERO);
       stmAttackers = attackers & pieces(stm);
-      // Don't allow pinned pieces to attack pieces except the king as long all
+      // Don't allow pinned pieces to attack (except the king) as long as
-      // pinners are on their original square.
+      // all pinners are on their original square.
-      if (!(st->pinnersForKing[stm] & ~occupied))
+      if (!(st->pinners[~stm] & ~occupied))
           stmAttackers &= ~st->blockersForKing[stm];
-      // If we have no more attackers we must give up
+      // If stm has no more attackers then give up: stm loses
       if (!stmAttackers)
           break;
-      // Locate and remove the next least valuable attacker
+      // Locate and remove the next least valuable attacker, and add to
+      // the bitboard 'attackers' the possibly X-ray attackers behind it.
       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
-      if (nextVictim == KING)
-      {
-          // Our only attacker is the king. If the opponent still has
-          // attackers we must give up. Otherwise we make the move and
-          // (having no more attackers) the opponent must give up.
-          if (!(attackers & pieces(~stm)))
+      stm = ~stm; // Switch side to move
-              opponentToMove = !opponentToMove;
-          break;
-      }
-      // Assume the opponent can win the next piece for free and switch sides
+      // Negamax the balance with alpha = balance, beta = balance+1 and
+      // add nextVictim's value.
+      //
-      balance += PieceValue[MG][nextVictim];
+      //      (balance, balance+1) -> (-balance-1, -balance)
+      //
-      opponentToMove = !opponentToMove;
+      assert(balance < VALUE_ZERO);
-      // If balance is negative after receiving a free piece then give up
+      balance = -balance - 1 - PieceValue[MG][nextVictim];
-      if (balance < VALUE_ZERO)
-          break;
-      // Complete the process of switching sides. The first line swaps
+      // If balance is still non-negative after giving away nextVictim then we
-      // all negative numbers with non-negative numbers. The compiler
+      // win. The only thing to be careful about it is that we should revert
-      // probably knows that it is just the bitwise negation ~balance.
+      // stm if we captured with the king when the opponent still has attackers.
-      balance = -balance-1;
+      if (balance >= VALUE_ZERO)
+      {
+          if (nextVictim == KING && (attackers & pieces(stm)))
-      stm = ~stm;
+              stm = ~stm;
+          break;
+      }
+      assert(nextVictim != KING);
+  }
-  // If the opponent gave up we win, otherwise we lose.
+  return us != stm; // We break the above loop when stm loses
-  return opponentToMove;
+}
 /// Position::is_draw() tests whether the position is drawn by 50-move rule
 /// or by repetition. It does not detect stalemates.
       if (   stp->key == st->key
           && ++cnt + (ply > i) == 2)
           return true;
+  }
+  return false;
+}
+// Position::has_repeated() tests whether there has been at least one repetition
+// of positions since the last capture or pawn move.
+bool Position::has_repeated() const {
+    StateInfo* stc = st;
+    while (true)
+    {
+        int i = 4, end = std::min(stc->rule50, stc->pliesFromNull);
+        if (end < i)
+            return false;
+        StateInfo* stp = stc->previous->previous;
+        do {
+            stp = stp->previous->previous;
+            if (stp->key == stc->key)
+                return true;
+            i += 2;
+        } while (i <= end);
+        stc = stc->previous;
+    }
+}
+/// Position::has_game_cycle() tests if the position has a move which draws by repetition,
+/// or an earlier position has a move that directly reaches the current position.
+bool Position::has_game_cycle(int ply) const {
+  int j;
+  int end = std::min(st->rule50, st->pliesFromNull);
+  if (end < 3)
+    return false;
+  Key originalKey = st->key;
+  StateInfo* stp = st->previous;
+  for (int i = 3; i <= end; i += 2)
+  {
+      stp = stp->previous->previous;
+      Key moveKey = originalKey ^ stp->key;
+      if (   (j = H1(moveKey), cuckoo[j] == moveKey)
+          || (j = H2(moveKey), cuckoo[j] == moveKey))
+      {
+          Move move = cuckooMove[j];
+          Square s1 = from_sq(move);
+          Square s2 = to_sq(move);
+          if (!(between_bb(s1, s2) & pieces()))
+          {
+              // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in the same
+              // location. We select the legal one by reversing the move variable if necessary.
+              if (empty(s1))
+                  move = make_move(s2, s1);
+              if (ply > i)
+                  return true;
+              // For repetitions before or at the root, require one more
+              StateInfo* next_stp = stp;
+              for (int k = i + 2; k <= end; k += 2)
+              {
+                  next_stp = next_stp->previous->previous;
+                  if (next_stp->key == stp->key)
+                     return true;
+              }
+          }
+      }
+  }
   return false;
+}
 /// Position::flip() flips position with the white and black sides reversed. This
 /// position object and raises an asserts if something wrong is detected.
 /// This is meant to be helpful when debugging.
 bool Position::pos_is_ok() const {
-  const bool Fast = true; // Quick (default) or full check?
+  constexpr bool Fast = true; // Quick (default) or full check?
   if (   (sideToMove != WHITE && sideToMove != BLACK)
       || piece_on(square<KING>(WHITE)) != W_KING
       || piece_on(square<KING>(BLACK)) != B_KING
       || (   ep_square() != SQ_NONE

Subversion Repositories Games.Chess Giants

Games.Chess Giants/engine-stockfish/position.cpp – Rev 169 → 185