Sync with master
authorMarco Costalba <mcostalba@gmail.com>
Sat, 31 Jan 2015 12:04:15 +0000 (13:04 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sat, 31 Jan 2015 12:05:51 +0000 (13:05 +0100)
bench: 7374604

1  2 
src/search.cpp
src/tt.cpp
src/tt.h

diff --combined src/search.cpp
index da8f457d6f01bdfeab1283237b2bf641115c3b31,eea529845ab8474822a6e38c142e98c4f7d7216f..c188469146eb074ae85ea6c72cef191fdaa014a2
@@@ -66,29 -66,22 +66,29 @@@ namespace 
    // Different node types, used as template parameter
    enum NodeType { Root, PV, NonPV };
  
 -  // Dynamic razoring margin based on depth
 +  // Razoring and futility margin based on depth
    inline Value razor_margin(Depth d) { return Value(512 + 32 * d); }
 +  inline Value futility_margin(Depth d) { return Value(200 * d); }
  
 -  // Futility lookup tables (initialized at startup) and their access functions
 -  int FutilityMoveCounts[2][16]; // [improving][depth]
 +  // Futility and reductions lookup tables, initialized at startup
 +  int FutilityMoveCounts[2][16];  // [improving][depth]
 +  Depth Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber]
  
 -  inline Value futility_margin(Depth d) {
 -    return Value(200 * d);
 +  template <bool PvNode> inline Depth reduction(bool i, Depth d, int mn) {
 +    return Reductions[PvNode][i][std::min(d, 63 * ONE_PLY)][std::min(mn, 63)];
    }
  
 -  // Reduction lookup tables (initialized at startup) and their access function
 -  int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber]
 +  // Skill struct is used to implement strength limiting
 +  struct Skill {
 +    Skill(int l) : level(l) {}
 +    bool enabled() const { return level < 20; }
 +    bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; }
 +    Move best_move(size_t multiPV) { return best ? best : pick_best(multiPV); }
 +    Move pick_best(size_t multiPV);
  
 -  template <bool PvNode> inline Depth reduction(bool i, Depth d, int mn) {
 -    return (Depth) Reductions[PvNode][i][std::min(int(d), 63)][std::min(mn, 63)];
 -  }
 +    int level;
 +    Move best = MOVE_NONE;
 +  };
  
    size_t PVIdx;
    TimeManager TimeMgr;
    Value value_from_tt(Value v, int ply);
    void update_pv(Move* pv, Move move, Move* childPv);
    void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt);
 -  string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta);
 -
 -  struct Skill {
 -    Skill(int l, size_t rootSize) : level(l),
 -                                    candidates(l < 20 ? std::min(4, (int)rootSize) : 0),
 -                                    best(MOVE_NONE) {}
 -   ~Skill() {
 -      if (candidates) // Swap best PV line with the sub-optimal one
 -          std::swap(RootMoves[0], *std::find(RootMoves.begin(),
 -                    RootMoves.end(), best ? best : pick_move()));
 -    }
 -
 -    size_t candidates_size() const { return candidates; }
 -    bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; }
 -    Move pick_move();
 -
 -    int level;
 -    size_t candidates;
 -    Move best;
 -  };
  
  } // namespace
  
  
  void Search::init() {
  
 -  // Init reductions array
 -  for (int d = 1; d < 64; ++d)
 -      for (int mc = 1; mc < 64; ++mc)
 -      {
 -          double    pvRed = 0.00 + log(double(d)) * log(double(mc)) / 3.00;
 -          double nonPVRed = 0.33 + log(double(d)) * log(double(mc)) / 2.25;
 +  const double K[][2] = {{ 0.83, 2.25 }, { 0.50, 3.00 }};
  
 -          Reductions[1][1][d][mc] = int8_t(   pvRed >= 1.0 ?    pvRed + 0.5: 0);
 -          Reductions[0][1][d][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed + 0.5: 0);
 +  for (int pv = 0; pv <= 1; ++pv)
 +      for (int imp = 0; imp <= 1; ++imp)
 +          for (int d = 1; d < 64; ++d)
 +              for (int mc = 1; mc < 64; ++mc)
 +              {
 +                  double r = K[pv][0] + log(d) * log(mc) / K[pv][1];
  
 -          Reductions[1][0][d][mc] = Reductions[1][1][d][mc];
 -          Reductions[0][0][d][mc] = Reductions[0][1][d][mc];
 +                  if (r >= 1.5)
 +                      Reductions[pv][imp][d][mc] = int(r) * ONE_PLY;
  
 -          // Increase reduction when eval is not improving
 -          if (Reductions[0][0][d][mc] >= 2)
 -              Reductions[0][0][d][mc] += 1;
 -      }
 +                  // Increase reduction when eval is not improving
 +                  if (!pv && !imp && Reductions[pv][imp][d][mc] >= 2 * ONE_PLY)
 +                      Reductions[pv][imp][d][mc] += ONE_PLY;
 +              }
  
 -  // Init futility move count array
    for (int d = 0; d < 16; ++d)
    {
        FutilityMoveCounts[0][d] = int(2.4 + 0.773 * pow(d + 0.00, 1.8));
@@@ -152,19 -167,19 +152,19 @@@ uint64_t Search::perft(Position& pos, D
    CheckInfo ci(pos);
    const bool leaf = (depth == 2 * ONE_PLY);
  
 -  for (MoveList<LEGAL> it(pos); *it; ++it)
 +  for (const ExtMove& ms : MoveList<LEGAL>(pos))
    {
        if (Root && depth <= ONE_PLY)
            cnt = 1, nodes++;
        else
        {
 -          pos.do_move(*it, st, ci, pos.gives_check(*it, ci));
 +          pos.do_move(ms.move, st, ci, pos.gives_check(ms.move, ci));
            cnt = leaf ? MoveList<LEGAL>(pos).size() : perft<false>(pos, depth - ONE_PLY);
            nodes += cnt;
 -          pos.undo_move(*it);
 +          pos.undo_move(ms.move);
        }
        if (Root)
 -          sync_cout << UCI::move(*it, pos.is_chess960()) << ": " << cnt << sync_endl;
 +          sync_cout << UCI::move(ms.move, pos.is_chess960()) << ": " << cnt << sync_endl;
    }
    return nodes;
  }
@@@ -237,8 -252,8 +237,8 @@@ void Search::think() 
            }
        }
  
 -      for (size_t i = 0; i < Threads.size(); ++i)
 -          Threads[i]->maxPly = 0;
 +      for (Thread* th : Threads)
 +          th->maxPly = 0;
  
        Threads.timer->run = true;
        Threads.timer->notify_one(); // Wake up the recurring timer
@@@ -294,14 -309,11 +294,14 @@@ namespace 
      Followupmoves.clear();
  
      size_t multiPV = Options["MultiPV"];
 -    Skill skill(Options["Skill Level"], RootMoves.size());
 +    Skill skill(Options["Skill Level"]);
  
 -    // Do we have to play with skill handicap? In this case enable MultiPV search
 -    // that we will use behind the scenes to retrieve a set of possible moves.
 -    multiPV = std::max(multiPV, skill.candidates_size());
 +    // When playing with strength handicap enable MultiPV search that we will
 +    // use behind the scenes to retrieve a set of possible moves.
 +    if (skill.enabled())
 +        multiPV = std::max(multiPV, (size_t)4);
 +
 +    multiPV = std::min(multiPV, RootMoves.size());
  
      // Iterative deepening loop until requested to stop or target depth reached
      while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth))
  
          // Save the last iteration's scores before first PV line is searched and
          // all the move scores except the (new) PV are set to -VALUE_INFINITE.
 -        for (size_t i = 0; i < RootMoves.size(); ++i)
 -            RootMoves[i].previousScore = RootMoves[i].score;
 +        for (RootMove& rm : RootMoves)
 +            rm.previousScore = rm.score;
  
          // MultiPV loop. We perform a full root search for each PV line
 -        for (PVIdx = 0; PVIdx < std::min(multiPV, RootMoves.size()) && !Signals.stop; ++PVIdx)
 +        for (PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx)
          {
              // Reset aspiration window starting size
              if (depth >= 5 * ONE_PLY)
                  if (   multiPV == 1
                      && (bestValue <= alpha || bestValue >= beta)
                      && Time::now() - SearchTime > 3000)
 -                    sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
 +                    sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl;
  
                  // In case of failing low/high increase aspiration window and
                  // re-search, otherwise exit the loop.
                  sync_cout << "info nodes " << RootPos.nodes_searched()
                            << " time " << Time::now() - SearchTime << sync_endl;
  
 -            else if (   PVIdx + 1 == std::min(multiPV, RootMoves.size())
 -                     || Time::now() - SearchTime > 3000)
 -                sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
 +            else if (PVIdx + 1 == multiPV || Time::now() - SearchTime > 3000)
 +                sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl;
          }
  
 -        // If skill levels are enabled and time is up, pick a sub-optimal best move
 -        if (skill.candidates_size() && skill.time_to_pick(depth))
 -            skill.pick_move();
 +        // If skill level is enabled and time is up, pick a sub-optimal best move
 +        if (skill.enabled() && skill.time_to_pick(depth))
 +            skill.pick_best(multiPV);
  
          // Have we found a "mate in x"?
          if (   Limits.mate
              }
          }
      }
 +
 +    // If skill level is enabled, swap best PV line with the sub-optimal one
 +    if (skill.enabled())
 +        std::swap(RootMoves[0], *std::find(RootMoves.begin(),
 +                  RootMoves.end(), skill.best_move(multiPV)));
    }
  
  
          splitPoint = ss->splitPoint;
          bestMove   = splitPoint->bestMove;
          bestValue  = splitPoint->bestValue;
 -        tte = NULL;
 +        tte = nullptr;
          ttHit = false;
          ttMove = excludedMove = MOVE_NONE;
          ttValue = VALUE_NONE;
  
          // If ttMove is quiet, update killers, history, counter move and followup move on TT hit
          if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck)
 -            update_stats(pos, ss, ttMove, depth, NULL, 0);
 +            update_stats(pos, ss, ttMove, depth, nullptr, 0);
  
          return ttValue;
      }
@@@ -781,7 -789,7 +781,7 @@@ moves_loop: // When in check and at SpN
        }
  
        if (PvNode)
 -          (ss+1)->pv = NULL;
 +          (ss+1)->pv = nullptr;
  
        extension = DEPTH_ZERO;
        captureOrPromotion = pos.capture_or_promotion(move);
      // played quiet moves.
      Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY));
      History.update(pos.moved_piece(move), to_sq(move), bonus);
 +
      for (int i = 0; i < quietsCnt; ++i)
      {
          Move m = quiets[i];
    }
  
  
 -  // When playing with a strength handicap, choose best move among the first 'candidates'
 -  // RootMoves using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.
 +  // When playing with strength handicap, choose best move among a set of RootMoves
 +  // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.
  
 -  Move Skill::pick_move() {
 +  Move Skill::pick_best(size_t multiPV) {
  
      // PRNG sequence should be non-deterministic, so we seed it with the time at init
      static PRNG rng(Time::now());
  
      // RootMoves are already sorted by score in descending order
 -    int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg);
 +    int variance = std::min(RootMoves[0].score - RootMoves[multiPV - 1].score, PawnValueMg);
      int weakness = 120 - 2 * level;
      int maxScore = -VALUE_INFINITE;
 -    best = MOVE_NONE;
  
      // Choose best move. For each move score we add two terms both dependent on
 -    // weakness. One deterministic and bigger for weaker moves, and one random,
 +    // weakness. One deterministic and bigger for weaker levels, and one random,
      // then we choose the move with the resulting highest score.
 -    for (size_t i = 0; i < candidates; ++i)
 +    for (size_t i = 0; i < multiPV; ++i)
      {
          int score = RootMoves[i].score;
  
      return best;
    }
  
 +} // namespace
  
 -  // uci_pv() formats PV information according to the UCI protocol. UCI
 -  // requires that all (if any) unsearched PV lines are sent using a previous
 -  // search score.
  
 -  string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta) {
 +/// UCI::pv() formats PV information according to the UCI protocol. UCI requires
 +/// that all (if any) unsearched PV lines are sent using a previous search score.
  
 -    std::stringstream ss;
 -    Time::point elapsed = Time::now() - SearchTime + 1;
 -    size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size());
 -    int selDepth = 0;
 +string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
  
 -    for (size_t i = 0; i < Threads.size(); ++i)
 -        if (Threads[i]->maxPly > selDepth)
 -            selDepth = Threads[i]->maxPly;
 +  std::stringstream ss;
 +  Time::point elapsed = Time::now() - SearchTime + 1;
 +  size_t multiPV = std::min((size_t)Options["MultiPV"], RootMoves.size());
 +  int selDepth = 0;
  
 -    for (size_t i = 0; i < uciPVSize; ++i)
 -    {
 -        bool updated = (i <= PVIdx);
 +  for (Thread* th : Threads)
 +      if (th->maxPly > selDepth)
 +          selDepth = th->maxPly;
  
 -        if (depth == ONE_PLY && !updated)
 -            continue;
 +  for (size_t i = 0; i < multiPV; ++i)
 +  {
 +      bool updated = (i <= PVIdx);
  
 -        Depth d = updated ? depth : depth - ONE_PLY;
 -        Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore;
 +      if (depth == ONE_PLY && !updated)
 +          continue;
  
 -        bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
 -        v = tb ? TB::Score : v;
 +      Depth d = updated ? depth : depth - ONE_PLY;
 +      Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore;
  
 -        if (ss.rdbuf()->in_avail()) // Not at first line
 -            ss << "\n";
 +      bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
 +      v = tb ? TB::Score : v;
  
 -        ss << "info depth " << d / ONE_PLY
 -           << " seldepth "  << selDepth
 -           << " multipv "   << i + 1
 -           << " score "     << UCI::value(v);
 +      if (ss.rdbuf()->in_avail()) // Not at first line
 +          ss << "\n";
  
 -        if (!tb && i == PVIdx)
 -              ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
 +      ss << "info"
 +         << " depth "    << d / ONE_PLY
 +         << " seldepth " << selDepth
 +         << " multipv "  << i + 1
 +         << " score "    << UCI::value(v);
  
 -        ss << " nodes "     << pos.nodes_searched()
 -           << " nps "       << pos.nodes_searched() * 1000 / elapsed;
 +      if (!tb && i == PVIdx)
 +          ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
  
 -        if (elapsed > 1000) // Earlier makes little sense
 -           ss << " hashfull "  << TT.hashfull();
 +      ss << " nodes "    << pos.nodes_searched()
-          << " nps "      << pos.nodes_searched() * 1000 / elapsed
-          << " tbhits "   << TB::Hits
++         << " nps "      << pos.nodes_searched() * 1000 / elapsed;
 -        ss << " tbhits "    << TB::Hits
 -           << " time "      << elapsed
 -           << " pv";
++      if (elapsed > 1000) // Earlier makes little sense
++          ss << " hashfull "  << TT.hashfull();
 -        for (size_t j = 0; j < RootMoves[i].pv.size(); ++j)
 -            ss << " " << UCI::move(RootMoves[i].pv[j], pos.is_chess960());
 -    }
++      ss << " tbhits "   << TB::Hits
 +         << " time "     << elapsed
 +         << " pv";
  
 -    return ss.str();
 +      for (Move m : RootMoves[i].pv)
 +          ss << " " << UCI::move(m, pos.is_chess960());
    }
  
 -} // namespace
 +  return ss.str();
 +}
  
  
  /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and
  void RootMove::insert_pv_in_tt(Position& pos) {
  
    StateInfo state[MAX_PLY], *st = state;
 -  size_t idx = 0;
 +  bool ttHit;
  
 -  for ( ; idx < pv.size(); ++idx)
 +  for (Move m : pv)
    {
 -      bool ttHit;
 -      TTEntry* tte = TT.probe(pos.key(), ttHit);
 +      assert(MoveList<LEGAL>(pos).contains(m));
  
 -      if (!ttHit || tte->move() != pv[idx]) // Don't overwrite correct entries
 -          tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.generation());
 +      TTEntry* tte = TT.probe(pos.key(), ttHit);
  
 -      assert(MoveList<LEGAL>(pos).contains(pv[idx]));
 +      if (!ttHit || tte->move() != m) // Don't overwrite correct entries
 +          tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, m, VALUE_NONE, TT.generation());
  
 -      pos.do_move(pv[idx], *st++);
 +      pos.do_move(m, *st++);
    }
  
 -  while (idx) pos.undo_move(pv[--idx]);
 +  for (size_t i = pv.size(); i > 0; )
 +      pos.undo_move(pv[--i]);
  }
  
  
  /// root. We try hard to have a ponder move to return to the GUI, otherwise in case of
  /// 'ponder on' we have nothing to think on.
  
 -Move RootMove::extract_ponder_from_tt(Position& pos)
 +bool RootMove::extract_ponder_from_tt(Position& pos)
  {
      StateInfo st;
 -    bool found;
 +    bool ttHit;
  
      assert(pv.size() == 1);
  
      pos.do_move(pv[0], st);
 -    TTEntry* tte = TT.probe(pos.key(), found);
 -    Move m = found ? tte->move() : MOVE_NONE;
 -    if (!MoveList<LEGAL>(pos).contains(m))
 -        m = MOVE_NONE;
 -
 +    TTEntry* tte = TT.probe(pos.key(), ttHit);
      pos.undo_move(pv[0]);
 -    pv.push_back(m);
 -    return m;
 +
 +    if (ttHit)
 +    {
 +        Move m = tte->move(); // Local copy to be SMP safe
 +        if (MoveList<LEGAL>(pos).contains(m))
 +           return pv.push_back(m), true;
 +    }
 +
 +    return false;
  }
  
  
@@@ -1513,7 -1522,7 +1517,7 @@@ void Thread::idle_loop() 
  
    // Pointer 'this_sp' is not null only if we are called from split(), and not
    // at the thread creation. This means we are the split point's master.
 -  SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL;
 +  SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : nullptr;
  
    assert(!this_sp || (this_sp->masterThread == this && searching));
  
  
            sp->mutex.lock();
  
 -          assert(activePosition == NULL);
 +          assert(activePosition == nullptr);
  
            activePosition = &pos;
  
            assert(searching);
  
            searching = false;
 -          activePosition = NULL;
 +          activePosition = nullptr;
            sp->slavesMask.reset(idx);
            sp->allSlavesSearching = false;
            sp->nodes += pos.nodes_searched();
                for (size_t i = 0; i < Threads.size(); ++i)
                {
                    const int size = Threads[i]->splitPointsSize; // Local copy
 -                  sp = size ? &Threads[i]->splitPoints[size - 1] : NULL;
 +                  sp = size ? &Threads[i]->splitPoints[size - 1] : nullptr;
  
                    if (   sp
                        && sp->allSlavesSearching
        }
  
        // Grab the lock to avoid races with Thread::notify_one()
 -      mutex.lock();
 +      std::unique_lock<std::mutex> lk(mutex);
  
        // If we are master and all slaves have finished then exit idle_loop
        if (this_sp && this_sp->slavesMask.none())
        {
            assert(!searching);
 -          mutex.unlock();
            break;
        }
  
        // If we are not searching, wait for a condition to be signaled instead of
        // wasting CPU time polling for work.
        if (!searching && !exit)
 -          sleepCondition.wait(mutex);
 -
 -      mutex.unlock();
 +          sleepCondition.wait(lk);
    }
  }
  
@@@ -1665,10 -1677,10 +1669,10 @@@ void check_time() 
  
        // Loop across all split points and sum accumulated SplitPoint nodes plus
        // all the currently active positions nodes.
 -      for (size_t i = 0; i < Threads.size(); ++i)
 -          for (int j = 0; j < Threads[i]->splitPointsSize; ++j)
 +      for (Thread* th : Threads)
 +          for (int i = 0; i < th->splitPointsSize; ++i)
            {
 -              SplitPoint& sp = Threads[i]->splitPoints[j];
 +              SplitPoint& sp = th->splitPoints[i];
  
                sp.mutex.lock();
  
diff --combined src/tt.cpp
index bb49a824519a52b97828b1a6055d2e12cc8f198b,19de55ae3cbf55d15eb6624909114f843076739c..d0e2d729c8c766e883092277bfc5fd97b2bb58e2
@@@ -32,6 -32,8 +32,6 @@@ TranspositionTable TT; // Our global tr
  
  void TranspositionTable::resize(size_t mbSize) {
  
 -  assert(sizeof(Cluster) == CacheLineSize / 2);
 -
    size_t newClusterCount = size_t(1) << msb((mbSize * 1024 * 1024) / sizeof(Cluster));
  
    if (newClusterCount == clusterCount)
@@@ -94,3 -96,20 +94,20 @@@ TTEntry* TranspositionTable::probe(cons
  
    return found = false, replace;
  }
+ /// Returns an approximation of the hashtable occupation during a search. The
+ /// hash is x permill full, as per UCI protocol.
+ int TranspositionTable::hashfull() const
+ {
+   int cnt = 0;
+   for (int i = 0; i < 1000 / ClusterSize; i++)
+   {
+       const TTEntry* tte = &table[i].entry[0];
+       for (int j = 0; j < ClusterSize; j++)
+           if ((tte[j].genBound8 & 0xFC) == generation8)
+               cnt++;
+   }
+   return cnt;
+ }
diff --combined src/tt.h
index 14f820d0cb6677637615f7d21b312514ed2d26fe,7343c525fc6847da40c83c3168fdfa857446f73a..32b4036e39dea085974410867b7212facfc6c625
+++ b/src/tt.h
@@@ -81,13 -81,12 +81,14 @@@ class TranspositionTable 
      char padding[2]; // Align to the cache line size
    };
  
 +  static_assert(sizeof(Cluster) == CacheLineSize / 2, "Cluster size incorrect");
 +
  public:
   ~TranspositionTable() { free(mem); }
    void new_search() { generation8 += 4; } // Lower 2 bits are used by Bound
    uint8_t generation() const { return generation8; }
    TTEntry* probe(const Key key, bool& found) const;
+   int hashfull() const;
    void resize(size_t mbSize);
    void clear();