Restore original movepick modulo space inflation
authorMarco Costalba <mcostalba@gmail.com>
Sat, 25 Oct 2008 14:28:24 +0000 (15:28 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sun, 26 Oct 2008 09:11:13 +0000 (10:11 +0100)
We have a regression somewhere here so restart from zero
and proceed one change at a time.

With this modification we have the same strenght of
"Introduce Stockfish" patch that is our strongest to date.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/movepick.cpp
src/movepick.h

index e1f8e4e77f944bd5831245b81dd16c467c9935f0..6525c7506b8b180cc9f36574c6cc22452c2d96a4 100644 (file)
@@ -7,12 +7,12 @@
   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.
-  
+
   Stockfish is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
-  
+
   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
@@ -61,8 +61,9 @@ namespace {
 /// search captures, promotions and some checks) and about how important good
 /// move ordering is at the current node.
 
-MovePicker::MovePicker(const Position& p, bool pvnode, Move ttm, Move mk,
-                       Move k1, Move k2, Depth d) : pos(p) {  
+MovePicker::MovePicker(Position& p, bool pvnode, Move ttm, Move mk,
+                       Move k1, Move k2, Depth d) {
+  pos = &p;
   pvNode = pvnode;
   ttMove = ttm;
   mateKiller = (mk == ttm)? MOVE_NONE : mk;
@@ -111,13 +112,16 @@ Move MovePicker::get_next_move() {
     // Next phase
     phaseIndex++;
     switch (PhaseTable[phaseIndex]) {
-
     case PH_TT_MOVE:
         if (ttMove != MOVE_NONE)
         {
             assert(move_is_ok(ttMove));
-            if (generate_move_if_legal(pos, ttMove, pinned) != MOVE_NONE)
-                return ttMove;
+            Move m = generate_move_if_legal(*pos, ttMove, pinned);
+            if (m != MOVE_NONE)
+            {
+                assert(m == ttMove);
+                return m;
+            }
         }
         break;
 
@@ -125,13 +129,17 @@ Move MovePicker::get_next_move() {
         if (mateKiller != MOVE_NONE)
         {
             assert(move_is_ok(mateKiller));
-            if (generate_move_if_legal(pos, mateKiller, pinned) != MOVE_NONE)
-                return mateKiller;
-        }
-        break;
-
-    case PH_GOOD_CAPTURES:      
-        numOfMoves = generate_captures(pos, moves);
+            Move m = generate_move_if_legal(*pos, mateKiller, pinned);
+            if (m != MOVE_NONE)
+            {
+                assert(m == mateKiller);
+                return m;
+            }
+       }
+       break;
+
+    case PH_GOOD_CAPTURES:
+        numOfMoves = generate_captures(*pos, moves);
         score_captures();
         movesPicked = 0;
         break;
@@ -141,26 +149,26 @@ Move MovePicker::get_next_move() {
         break;
 
     case PH_NONCAPTURES:
-        numOfMoves = generate_noncaptures(pos, moves);
+        numOfMoves = generate_noncaptures(*pos, moves);
         score_noncaptures();
         movesPicked = 0;
         break;
 
     case PH_EVASIONS:
-        assert(pos.is_check());      
-        numOfMoves = generate_evasions(pos, moves);
+        assert(pos->is_check());      
+        numOfMoves = generate_evasions(*pos, moves);
         score_evasions();
         movesPicked = 0;
         break;
 
     case PH_QCAPTURES:      
-        numOfMoves = generate_captures(pos, moves);
+        numOfMoves = generate_captures(*pos, moves);
         score_qcaptures();
         movesPicked = 0;
         break;
 
     case PH_QCHECKS:
-        numOfMoves = generate_checks(pos, moves, dc);
+        numOfMoves = generate_checks(*pos, moves, dc);
         movesPicked = 0;
         break;
 
@@ -173,7 +181,6 @@ Move MovePicker::get_next_move() {
     }
   }
   assert(false);
-
   return MOVE_NONE;
 }
 
@@ -183,27 +190,30 @@ Move MovePicker::get_next_move() {
 
 Move MovePicker::get_next_move(Lock &lock) {
 
-  lock_grab(&lock);
-  if (finished)
-  {
-      lock_release(&lock);
-      return MOVE_NONE;
-  }
-  Move m = get_next_move();
-  if (m == MOVE_NONE)
-      finished = true;
+   Move m;
 
-  lock_release(&lock);   
-  return m;
+   lock_grab(&lock);
+   if (finished)
+   {
+       lock_release(&lock);
+       return MOVE_NONE;
+   }
+   m = get_next_move();
+   if (m == MOVE_NONE)
+       finished = true;
+
+   lock_release(&lock);   
+   return m;
 }
 
+
 /// MovePicker::score_captures(), MovePicker::score_noncaptures(),
 /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
 /// numerical move ordering score to each move in a move list.  The moves
 /// with highest scores will be picked first by pick_move_from_list().
 
 void MovePicker::score_captures() {
-  // Winning and equal captures in the main search are ordered by MVV.
+  // Winning and equal captures in the main search are ordered by MVV/LVA.
   // Suprisingly, this appears to perform slightly better than SEE based
   // move ordering.  The reason is probably that in a position with a winning
   // capture, capturing a more valuable (but sufficiently defended) piece
@@ -214,11 +224,16 @@ void MovePicker::score_captures() {
   // the subtree size.
   for (int i = 0; i < numOfMoves; i++)
   {
-      Move m = moves[i].move;
-      moves[i].score = pos.see(m);
-      if (moves[i].score >= 0)
-          moves[i].score = move_promotion(m) ? QueenValueMidgame
-                         : pos.midgame_value_of_piece_on(move_to(m));
+      int seeValue = pos->see(moves[i].move);
+      if (seeValue >= 0)
+      {
+          if (move_promotion(moves[i].move))
+              moves[i].score = QueenValueMidgame;
+          else
+              moves[i].score = int(pos->midgame_value_of_piece_on(move_to(moves[i].move)))
+                              -int(pos->type_of_piece_on(move_from(moves[i].move)));
+      } else
+          moves[i].score = seeValue;
   }
 }
 
@@ -232,13 +247,7 @@ void MovePicker::score_noncaptures() {
       else if (m == killer2)
           moves[i].score = HistoryMax + 1;
       else
-          moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), m);
-
-      // Ensure moves in history are always sorted as first
-      if (moves[i].score > 0)
-          moves[i].score += 1000;
-
-      moves[i].score += pos.mg_pst_delta(moves[i].move);
+         moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m);
   }
 }
 
@@ -249,47 +258,31 @@ void MovePicker::score_evasions() {
       Move m = moves[i].move;
       if (m == ttMove)
           moves[i].score = 2*HistoryMax;
-      else if (!pos.square_is_empty(move_to(m)))
+      else if(!pos->square_is_empty(move_to(m)))
       {
-          moves[i].score = pos.see(m);
-          if (moves[i].score >= 0)
-              moves[i].score += HistoryMax;          
-      }
-      else
-          moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), m);
+          int seeScore = pos->see(m);
+          moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore;
+      } else
+          moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m);
   }
   // FIXME try psqt also here
 }
 
 void MovePicker::score_qcaptures() {
 
-  // Use MVV ordering
+  // Use MVV/LVA ordering
   for (int i = 0; i < numOfMoves; i++)
   {
       Move m = moves[i].move;
-      moves[i].score = move_promotion(m) ? QueenValueMidgame
-                      : pos.midgame_value_of_piece_on(move_to(m));
+      if (move_promotion(m))
+          moves[i].score = QueenValueMidgame;
+      else
+          moves[i].score = int(pos->midgame_value_of_piece_on(move_to(m)))
+                          -int(pos->midgame_value_of_piece_on(move_to(m))) / 64;
   }
 }
 
 
-/// find_best_index() loops across the moves and returns index of
-/// the highest scored one.
-
-int MovePicker::find_best_index() {
-
-  int bestScore = -10000000, bestIndex = -1;
-
-  for (int i = movesPicked; i < numOfMoves; i++)
-      if (moves[i].score > bestScore)
-      {
-          bestIndex = i;
-          bestScore = moves[i].score;
-      }
-  return bestIndex;
-}
-
-
 /// MovePicker::pick_move_from_list() picks the move with the biggest score
 /// from a list of generated moves (moves[] or badCaptures[], depending on
 /// the current move generation phase).  It takes care not to return the
@@ -300,17 +293,18 @@ int MovePicker::find_best_index() {
 
 Move MovePicker::pick_move_from_list() {
 
+  int bestScore = -10000000;
   int bestIndex;
   Move move;
 
   switch (PhaseTable[phaseIndex]) {
-
   case PH_GOOD_CAPTURES:
-      assert(!pos.is_check());
+      assert(!pos->is_check());
       assert(movesPicked >= 0);
+
       while (movesPicked < numOfMoves)
       {
-          int bestScore = -10000000;
+          bestScore = -10000000;
           bestIndex = -1;
           for (int i = movesPicked; i < numOfMoves; i++)
           {
@@ -320,66 +314,87 @@ Move MovePicker::pick_move_from_list() {
                   assert(numOfBadCaptures < 63);
                   badCaptures[numOfBadCaptures++] = moves[i];
                   moves[i--] = moves[--numOfMoves];
-               }
-               else if (moves[i].score > bestScore)
-               {
-                   bestIndex = i;
-                   bestScore = moves[i].score;
-               }
+              }
+              else if (moves[i].score > bestScore)
+              {
+                  bestIndex = i;
+                  bestScore = moves[i].score;
+              }
           }
           if (bestIndex != -1) // Found a good capture
           {
-              move = moves[bestIndex].move;\r
+              move = moves[bestIndex].move;
               moves[bestIndex] = moves[movesPicked++];
               if (   move != ttMove
                   && move != mateKiller
-                  && pos.move_is_legal(move, pinned))
+                  && pos->move_is_legal(move, pinned))
                   return move;
           }
       }
       break;
 
   case PH_NONCAPTURES:
-      assert(!pos.is_check());
+      assert(!pos->is_check());
       assert(movesPicked >= 0);
+
       while (movesPicked < numOfMoves)
       {
+          bestScore = -10000000;
+
           // If this is a PV node or we have only picked a few moves, scan
           // the entire move list for the best move.  If many moves have already
           // been searched and it is not a PV node, we are probably failing low
           // anyway, so we just pick the first move from the list.
-          bestIndex = (movesPicked < 12 || pvNode ? find_best_index() : movesPicked);
+          if (pvNode || movesPicked < 12)
+          {
+              bestIndex = -1;
+              for (int i = movesPicked; i < numOfMoves; i++)
+                  if (moves[i].score > bestScore)
+                  {
+                      bestIndex = i;
+                      bestScore = moves[i].score;
+                  }
+          } else
+              bestIndex = movesPicked;
 
           if (bestIndex != -1)
           {
-              move = moves[bestIndex].move;\r
+              move = moves[bestIndex].move;
               moves[bestIndex] = moves[movesPicked++];
               if (   move != ttMove
                   && move != mateKiller
-                  && pos.move_is_legal(move, pinned))
+                  && pos->move_is_legal(move, pinned))
                   return move;
-         }
-    }
-    break;
+          }
+      }
+      break;
 
   case PH_EVASIONS:
-      assert(pos.is_check());
+      assert(pos->is_check());
       assert(movesPicked >= 0);
+
       while (movesPicked < numOfMoves)
       {
-          bestIndex = find_best_index();
+          bestScore = -10000000;
+          bestIndex = -1;
+          for (int i = movesPicked; i < numOfMoves; i++)
+              if(moves[i].score > bestScore)
+              {
+                  bestIndex = i;
+                  bestScore = moves[i].score;
+              }
 
           if (bestIndex != -1)
           {
-              move = moves[bestIndex].move;\r
+              move = moves[bestIndex].move;
               moves[bestIndex] = moves[movesPicked++];
               return move;
           }
-      }
-      break;
+    }
+    break;
 
   case PH_BAD_CAPTURES:
-      assert(!pos.is_check());
+      assert(!pos->is_check());
       assert(badCapturesPicked >= 0);
       // It's probably a good idea to use SEE move ordering here, instead
       // of just picking the first move.  FIXME
@@ -388,38 +403,51 @@ Move MovePicker::pick_move_from_list() {
           move = badCaptures[badCapturesPicked++].move;
           if (   move != ttMove
               && move != mateKiller
-              && pos.move_is_legal(move, pinned))
+              && pos->move_is_legal(move, pinned))
               return move;
       }
       break;
 
   case PH_QCAPTURES:
-      assert(!pos.is_check());
+      assert(!pos->is_check());
       assert(movesPicked >= 0);
       while (movesPicked < numOfMoves)
       {
-          // FIXME makes sens to score qcaps?
-          bestIndex = (movesPicked < 4 ? find_best_index() : movesPicked);
+          bestScore = -10000000;
+          if (movesPicked < 4)
+          {
+              bestIndex = -1;
+              for (int i = movesPicked; i < numOfMoves; i++)
+                  if(moves[i].score > bestScore)
+                  {
+                      bestIndex = i;
+                      bestScore = moves[i].score;
+                  }
+          } else
+              bestIndex = movesPicked;
 
           if (bestIndex != -1)
           {
-              move = moves[bestIndex].move;\r
+              move = moves[bestIndex].move;
               moves[bestIndex] = moves[movesPicked++];
-              if (move != ttMove && pos.move_is_legal(move, pinned))
+              // Remember to change the line below if we decide to hash the qsearch!
+              // Maybe also postpone the legality check until after futility pruning?
+              if (/* move != ttMove && */ pos->move_is_legal(move, pinned))
                   return move;
           }
       }
       break;
 
   case PH_QCHECKS:
-      assert(!pos.is_check());
+      assert(!pos->is_check());
       assert(movesPicked >= 0);
       // Perhaps we should do something better than just picking the first
       // move here?  FIXME
       while (movesPicked < numOfMoves)
       {
-          move = moves[movesPicked++].move;          
-          if (move != ttMove && pos.move_is_legal(move, pinned))
+          move = moves[movesPicked++].move;
+          // Remember to change the line below if we decide to hash the qsearch!
+          if (/* move != ttMove && */ pos->move_is_legal(move, pinned))
               return move;
       }
       break;
@@ -430,19 +458,14 @@ Move MovePicker::pick_move_from_list() {
   return MOVE_NONE;
 }
 
-
-/// MovePicker::current_move_type() returns the type of the just
-/// picked next move. It can be used in search to further differentiate
-/// according to the current move type: capture, non capture, escape, etc.
 MovePicker::MovegenPhase MovePicker::current_move_type() const {
 
   return PhaseTable[phaseIndex];
 }
 
-
 /// MovePicker::init_phase_table() initializes the PhaseTable[],
 /// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex
-/// and QsearchWithoutChecksPhaseIndex variables.  It is only called once
+/// and QsearchWithoutChecksPhaseIndex variables. It is only called once
 /// during program startup, and never again while the program is running.
 
 void MovePicker::init_phase_table() {
index a835346db341b62c297c6f999247e561e9e570c6..cbb69a014dd83373193b6ef0eb68eff5f912a688 100644 (file)
@@ -2,12 +2,12 @@
   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
   Copyright (C) 2008 Marco Costalba
-
   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.
-  
+   
   Stockfish is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
@@ -60,7 +60,8 @@ public:
     PH_STOP
   };
 
-  MovePicker(const Position& p, bool pvnode, Move ttm, Move mk, Move k1, Move k2, Depth d);
+  MovePicker(Position &p, bool pvnode, Move ttm, Move mk, Move k1, Move k2,
+             Depth dpth);
   Move get_next_move();
   Move get_next_move(Lock &lock);
   int number_of_moves() const;
@@ -76,9 +77,8 @@ private:
   void score_evasions();
   void score_qcaptures();
   Move pick_move_from_list();
-  int find_best_index();
   
-  const Position& pos;
+  Position *pos;
   Move ttMove, mateKiller, killer1, killer2;
   Bitboard pinned, dc;
   MoveStack moves[256], badCaptures[64];
@@ -101,6 +101,7 @@ private:
 /// a single reply to check.
 
 inline int MovePicker::number_of_moves() const {
+
   return numOfMoves;
 }