Reorder conditions according to their frequency

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index e9c0ad26a27b1ba13e063c3d8d64ec7350c6491f..7b7bc5cd8ec00b4b4b2f056046c8560eabf25408 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -91,7 +91,7 @@ namespace {
   CountermovesStats Countermoves;
 
   template <NodeType NT>
   CountermovesStats Countermoves;
 
   template <NodeType NT>

-  Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
+  Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);

 
   template <NodeType NT, bool InCheck>
   Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
 
   template <NodeType NT, bool InCheck>
   Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);


@@ -155,21 +155,17 @@ void Search::init() {
 
 size_t Search::perft(Position& pos, Depth depth) {
 
 
 size_t Search::perft(Position& pos, Depth depth) {
 

-  // At the last ply just return the number of legal moves (leaf nodes)
-  if (depth == ONE_PLY)
-      return MoveList<LEGAL>(pos).size();
-

   StateInfo st;
   size_t cnt = 0;
   CheckInfo ci(pos);
   StateInfo st;
   size_t cnt = 0;
   CheckInfo ci(pos);

+  const bool leaf = depth == 2 * ONE_PLY;

 
   for (MoveList<LEGAL> it(pos); *it; ++it)
   {
       pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci));
 
   for (MoveList<LEGAL> it(pos); *it; ++it)
   {
       pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci));

-      cnt += perft(pos, depth - ONE_PLY);
+      cnt += leaf ? MoveList<LEGAL>(pos).size() : perft(pos, depth - ONE_PLY);

       pos.undo_move(*it);
   }
       pos.undo_move(*it);
   }

-

   return cnt;
 }
 
   return cnt;
 }
 


@@ -349,7 +345,7 @@ namespace {
             // research with bigger window until not failing high/low anymore.
             while (true)
             {
             // research with bigger window until not failing high/low anymore.
             while (true)
             {

-                bestValue = search<Root>(pos, ss, alpha, beta, depth * ONE_PLY);
+                bestValue = search<Root>(pos, ss, alpha, beta, depth * ONE_PLY, false);

 
                 // Bring to front the best move. It is critical that sorting is
                 // done with a stable algorithm because all the values but the first
 
                 // Bring to front the best move. It is critical that sorting is
                 // done with a stable algorithm because all the values but the first


@@ -455,7 +451,7 @@ namespace {
                 Value rBeta = bestValue - 2 * PawnValueMg;
                 ss->excludedMove = RootMoves[0].pv[0];
                 ss->skipNullMove = true;
                 Value rBeta = bestValue - 2 * PawnValueMg;
                 ss->excludedMove = RootMoves[0].pv[0];
                 ss->skipNullMove = true;

-                Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY);
+                Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY, true);

                 ss->skipNullMove = false;
                 ss->excludedMove = MOVE_NONE;
 
                 ss->skipNullMove = false;
                 ss->excludedMove = MOVE_NONE;
 


@@ -485,7 +481,7 @@ namespace {
   // here: This is taken care of after we return from the split point.
 
   template <NodeType NT>
   // here: This is taken care of after we return from the split point.
 
   template <NodeType NT>

-  Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) {
+  Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) {

 
     const bool PvNode   = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot);
     const bool SpNode   = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot);
 
     const bool PvNode   = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot);
     const bool SpNode   = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot);


@@ -574,9 +570,9 @@ namespace {
         && tte
         && tte->depth() >= depth
         && ttValue != VALUE_NONE // Only in case of TT access race
         && tte
         && tte->depth() >= depth
         && ttValue != VALUE_NONE // Only in case of TT access race

-        && (           PvNode ?  tte->type() == BOUND_EXACT
-            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
-                              : (tte->type() & BOUND_UPPER)))
+        && (           PvNode ?  tte->bound() == BOUND_EXACT
+            : ttValue >= beta ? (tte->bound() &  BOUND_LOWER)
+                              : (tte->bound() &  BOUND_UPPER)))

     {
         TT.refresh(tte);
         ss->currentMove = ttMove; // Can be MOVE_NONE
     {
         TT.refresh(tte);
         ss->currentMove = ttMove; // Can be MOVE_NONE


@@ -605,8 +601,8 @@ namespace {
 
         // Can ttValue be used as a better position evaluation?
         if (ttValue != VALUE_NONE)
 
         // Can ttValue be used as a better position evaluation?
         if (ttValue != VALUE_NONE)

-            if (   ((tte->type() & BOUND_LOWER) && ttValue > eval)
-                || ((tte->type() & BOUND_UPPER) && ttValue < eval))
+            if (   ((tte->bound() & BOUND_LOWER) && ttValue > eval)
+                || ((tte->bound() & BOUND_UPPER) && ttValue < eval))

                 eval = ttValue;
     }
     else
                 eval = ttValue;
     }
     else


@@ -618,10 +614,10 @@ namespace {
 
     // Update gain for the parent non-capture move given the static position
     // evaluation before and after the move.
 
     // Update gain for the parent non-capture move given the static position
     // evaluation before and after the move.

-    if (   (move = (ss-1)->currentMove) != MOVE_NULL
-        && (ss-1)->staticEval != VALUE_NONE
+    if (   !pos.captured_piece_type()

         &&  ss->staticEval != VALUE_NONE
         &&  ss->staticEval != VALUE_NONE

-        && !pos.captured_piece_type()
+        && (ss-1)->staticEval != VALUE_NONE
+        && (move = (ss-1)->currentMove) != MOVE_NULL

         &&  type_of(move) == NORMAL)
     {
         Square to = to_sq(move);
         &&  type_of(move) == NORMAL)
     {
         Square to = to_sq(move);


@@ -679,7 +675,7 @@ namespace {
         pos.do_null_move(st);
         (ss+1)->skipNullMove = true;
         nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
         pos.do_null_move(st);
         (ss+1)->skipNullMove = true;
         nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)

-                                      : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R);
+                                      : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R, !cutNode);

         (ss+1)->skipNullMove = false;
         pos.undo_null_move();
 
         (ss+1)->skipNullMove = false;
         pos.undo_null_move();
 


@@ -694,7 +690,7 @@ namespace {
 
             // Do verification search at high depths
             ss->skipNullMove = true;
 
             // Do verification search at high depths
             ss->skipNullMove = true;

-            Value v = search<NonPV>(pos, ss, alpha, beta, depth-R);
+            Value v = search<NonPV>(pos, ss, alpha, beta, depth-R, false);

             ss->skipNullMove = false;
 
             if (v >= beta)
             ss->skipNullMove = false;
 
             if (v >= beta)


@@ -726,7 +722,6 @@ namespace {
         &&  depth >= 5 * ONE_PLY
         && !inCheck
         && !ss->skipNullMove
         &&  depth >= 5 * ONE_PLY
         && !inCheck
         && !ss->skipNullMove

-        &&  excludedMove == MOVE_NONE

         &&  abs(beta) < VALUE_MATE_IN_MAX_PLY)
     {
         Value rbeta = beta + 200;
         &&  abs(beta) < VALUE_MATE_IN_MAX_PLY)
     {
         Value rbeta = beta + 200;


@@ -744,7 +739,7 @@ namespace {
             {
                 ss->currentMove = move;
                 pos.do_move(move, st, ci, pos.move_gives_check(move, ci));
             {
                 ss->currentMove = move;
                 pos.do_move(move, st, ci, pos.move_gives_check(move, ci));

-                value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth);
+                value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);

                 pos.undo_move(move);
                 if (value >= rbeta)
                     return value;
                 pos.undo_move(move);
                 if (value >= rbeta)
                     return value;


@@ -759,7 +754,7 @@ namespace {
         Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4);
 
         ss->skipNullMove = true;
         Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4);
 
         ss->skipNullMove = true;

-        search<PvNode ? PV : NonPV>(pos, ss, alpha, beta, d);
+        search<PvNode ? PV : NonPV>(pos, ss, alpha, beta, d, true);

         ss->skipNullMove = false;
 
         tte = TT.probe(posKey);
         ss->skipNullMove = false;
 
         tte = TT.probe(posKey);


@@ -780,7 +775,7 @@ split_point_start: // At split points actual search starts from here
                            &&  depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY)
                            &&  ttMove != MOVE_NONE
                            && !excludedMove // Recursive singular search is not allowed
                            &&  depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY)
                            &&  ttMove != MOVE_NONE
                            && !excludedMove // Recursive singular search is not allowed

-                           && (tte->type() & BOUND_LOWER)
+                           && (tte->bound() & BOUND_LOWER)

                            &&  tte->depth() >= depth - 3 * ONE_PLY;
 
     // Step 11. Loop through moves
                            &&  tte->depth() >= depth - 3 * ONE_PLY;
 
     // Step 11. Loop through moves


@@ -855,7 +850,7 @@ split_point_start: // At split points actual search starts from here
           Value rBeta = ttValue - int(depth);
           ss->excludedMove = move;
           ss->skipNullMove = true;
           Value rBeta = ttValue - int(depth);
           ss->excludedMove = move;
           ss->skipNullMove = true;

-          value = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2);
+          value = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);

           ss->skipNullMove = false;
           ss->excludedMove = MOVE_NONE;
 
           ss->skipNullMove = false;
           ss->excludedMove = MOVE_NONE;
 


@@ -948,6 +943,10 @@ split_point_start: // At split points actual search starts from here
           &&  move != ss->killers[1])
       {
           ss->reduction = reduction<PvNode>(depth, moveCount);
           &&  move != ss->killers[1])
       {
           ss->reduction = reduction<PvNode>(depth, moveCount);

+
+          if (!PvNode && cutNode)
+              ss->reduction += ONE_PLY;
+

           if (move == countermoves[0] || move == countermoves[1])
               ss->reduction = std::max(DEPTH_ZERO, ss->reduction-ONE_PLY);
 
           if (move == countermoves[0] || move == countermoves[1])
               ss->reduction = std::max(DEPTH_ZERO, ss->reduction-ONE_PLY);
 


@@ -955,7 +954,7 @@ split_point_start: // At split points actual search starts from here
           if (SpNode)
               alpha = splitPoint->alpha;
 
           if (SpNode)
               alpha = splitPoint->alpha;
 

-          value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d);
+          value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);

 
           doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO);
           ss->reduction = DEPTH_ZERO;
 
           doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO);
           ss->reduction = DEPTH_ZERO;


@@ -972,7 +971,7 @@ split_point_start: // At split points actual search starts from here
           value = newDepth < ONE_PLY ?
                           givesCheck ? -qsearch<NonPV,  true>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
                                      : -qsearch<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
           value = newDepth < ONE_PLY ?
                           givesCheck ? -qsearch<NonPV,  true>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
                                      : -qsearch<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)

-                                     : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth);
+                                     : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);

       }
 
       // Only for PV nodes do a full PV search on the first move or after a fail
       }
 
       // Only for PV nodes do a full PV search on the first move or after a fail


@@ -982,7 +981,7 @@ split_point_start: // At split points actual search starts from here
           value = newDepth < ONE_PLY ?
                           givesCheck ? -qsearch<PV,  true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                      : -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
           value = newDepth < ONE_PLY ?
                           givesCheck ? -qsearch<PV,  true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                      : -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)

-                                     : - search<PV>(pos, ss+1, -beta, -alpha, newDepth);
+                                     : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, false);

       // Step 17. Undo move
       pos.undo_move(move);
 
       // Step 17. Undo move
       pos.undo_move(move);
 


@@ -1057,7 +1056,7 @@ split_point_start: // At split points actual search starts from here
           assert(bestValue < beta);
 
           thisThread->split<FakeSplit>(pos, ss, alpha, beta, &bestValue, &bestMove,
           assert(bestValue < beta);
 
           thisThread->split<FakeSplit>(pos, ss, alpha, beta, &bestValue, &bestMove,

-                                       depth, threatMove, moveCount, &mp, NT);
+                                       depth, threatMove, moveCount, &mp, NT, cutNode);

           if (bestValue >= beta)
               break;
       }
           if (bestValue >= beta)
               break;
       }


@@ -1173,9 +1172,9 @@ split_point_start: // At split points actual search starts from here
     if (   tte
         && tte->depth() >= ttDepth
         && ttValue != VALUE_NONE // Only in case of TT access race
     if (   tte
         && tte->depth() >= ttDepth
         && ttValue != VALUE_NONE // Only in case of TT access race

-        && (           PvNode ?  tte->type() == BOUND_EXACT
-            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
-                              : (tte->type() & BOUND_UPPER)))
+        && (           PvNode ?  tte->bound() == BOUND_EXACT
+            : ttValue >= beta ? (tte->bound() &  BOUND_LOWER)
+                              : (tte->bound() &  BOUND_UPPER)))

     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
         return ttValue;
     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
         return ttValue;


@@ -1585,7 +1584,7 @@ split_point_start: // At split points actual search starts from here
 void RootMove::extract_pv_from_tt(Position& pos) {
 
   StateInfo state[MAX_PLY_PLUS_2], *st = state;
 void RootMove::extract_pv_from_tt(Position& pos) {
 
   StateInfo state[MAX_PLY_PLUS_2], *st = state;

-  TTEntry* tte;
+  const TTEntry* tte;

   int ply = 0;
   Move m = pv[0];
 
   int ply = 0;
   Move m = pv[0];
 


@@ -1618,7 +1617,7 @@ void RootMove::extract_pv_from_tt(Position& pos) {
 void RootMove::insert_pv_in_tt(Position& pos) {
 
   StateInfo state[MAX_PLY_PLUS_2], *st = state;
 void RootMove::insert_pv_in_tt(Position& pos) {
 
   StateInfo state[MAX_PLY_PLUS_2], *st = state;

-  TTEntry* tte;
+  const TTEntry* tte;

   int ply = 0;
 
   do {
   int ply = 0;
 
   do {


@@ -1705,13 +1704,13 @@ void Thread::idle_loop() {
 
           switch (sp->nodeType) {
           case Root:
 
           switch (sp->nodeType) {
           case Root:

-              search<SplitPointRoot>(pos, ss, sp->alpha, sp->beta, sp->depth);
+              search<SplitPointRoot>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);

               break;
           case PV:
               break;
           case PV:

-              search<SplitPointPV>(pos, ss, sp->alpha, sp->beta, sp->depth);
+              search<SplitPointPV>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);

               break;
           case NonPV:
               break;
           case NonPV:

-              search<SplitPointNonPV>(pos, ss, sp->alpha, sp->beta, sp->depth);
+              search<SplitPointNonPV>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);

               break;
           default:
               assert(false);
               break;
           default:
               assert(false);