Base work for exclusion search
authorJoona Kiiski <joona.kiiski@gmail.com>
Sat, 21 Nov 2009 12:44:50 +0000 (14:44 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Mon, 23 Nov 2009 20:00:05 +0000 (21:00 +0100)
No functional change

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

index 8954834ad546bb8c4902b9c3a45be485dafa707f..7de4ae826c246c0705019f2ccab936ff1afd33d6 100644 (file)
@@ -51,6 +51,7 @@ Key Position::zobEp[64];
 Key Position::zobCastle[16];
 Key Position::zobMaterial[2][8][16];
 Key Position::zobSideToMove;
 Key Position::zobCastle[16];
 Key Position::zobMaterial[2][8][16];
 Key Position::zobSideToMove;
+Key Position::zobExclusion;
 
 Score Position::PieceSquareTable[16][64];
 
 
 Score Position::PieceSquareTable[16][64];
 
@@ -1736,6 +1737,8 @@ void Position::init_zobrist() {
 
   for (int i = 0; i < 16; i++)
       zobMaterial[0][KING][i] = zobMaterial[1][KING][i] = Key(0ULL);
 
   for (int i = 0; i < 16; i++)
       zobMaterial[0][KING][i] = zobMaterial[1][KING][i] = Key(0ULL);
+
+  zobExclusion = genrand_int64();
 }
 
 
 }
 
 
index 5539b7a6faa660da7897c7caf43d0b5d662102bf..1d6a99bab0f9bfa13314c7a77c7ca6bae4192144 100644 (file)
@@ -281,6 +281,9 @@ public:
   static void init_zobrist();
   static void init_piece_square_tables();
 
   static void init_zobrist();
   static void init_piece_square_tables();
 
+  // Public zobs
+  static Key zobExclusion;
+
 private:
 
   // Initialization helper functions (used while setting up a position)
 private:
 
   // Initialization helper functions (used while setting up a position)
index 94eb5af981315ea8587a77d35b909d5130bdcc13..98bf24a828e7174e48d4687785b7579b81e3406f 100644 (file)
@@ -277,7 +277,7 @@ namespace {
   Value id_loop(const Position& pos, Move searchMoves[]);
   Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
   Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
   Value id_loop(const Position& pos, Move searchMoves[]);
   Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
   Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
-  Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID);
+  Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move forbiddenMove = MOVE_NONE);
   Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
   void sp_search(SplitPoint* sp, int threadID);
   void sp_search_pv(SplitPoint* sp, int threadID);
   Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
   void sp_search(SplitPoint* sp, int threadID);
   void sp_search_pv(SplitPoint* sp, int threadID);
@@ -1251,7 +1251,7 @@ namespace {
   // search() is the search function for zero-width nodes.
 
   Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
   // search() is the search function for zero-width nodes.
 
   Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
-               int ply, bool allowNullmove, int threadID) {
+               int ply, bool allowNullmove, int threadID, Move forbiddenMove) {
 
     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
     assert(ply >= 0 && ply < PLY_MAX);
 
     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
     assert(ply >= 0 && ply < PLY_MAX);
@@ -1293,8 +1293,14 @@ namespace {
     if (value_mate_in(ply + 1) < beta)
         return beta - 1;
 
     if (value_mate_in(ply + 1) < beta)
         return beta - 1;
 
+    // Position key calculation
+    Key posKey = pos.get_key();
+
+    if (forbiddenMove != MOVE_NONE)
+      posKey ^= Position::zobExclusion;
+
     // Transposition table lookup
     // Transposition table lookup
-    tte = TT.retrieve(pos.get_key());
+    tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
     if (tte && ok_to_use_TT(tte, depth, beta, ply))
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
     if (tte && ok_to_use_TT(tte, depth, beta, ply))
@@ -1399,6 +1405,9 @@ namespace {
     {
       assert(move_is_ok(move));
 
     {
       assert(move_is_ok(move));
 
+      if (move == forbiddenMove)
+          continue;
+
       singleReply = (isCheck && mp.number_of_evasions() == 1);
       moveIsCheck = pos.move_is_check(move, ci);
       captureOrPromotion = pos.move_is_capture_or_promotion(move);
       singleReply = (isCheck && mp.number_of_evasions() == 1);
       moveIsCheck = pos.move_is_check(move, ci);
       captureOrPromotion = pos.move_is_capture_or_promotion(move);
@@ -1540,7 +1549,7 @@ namespace {
     // All legal moves have been searched.  A special case: If there were
     // no legal moves, it must be mate or stalemate.
     if (moveCount == 0)
     // All legal moves have been searched.  A special case: If there were
     // no legal moves, it must be mate or stalemate.
     if (moveCount == 0)
-        return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
+        return (forbiddenMove == MOVE_NONE ? (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW) : beta - 1);
 
     // If the search is not aborted, update the transposition table,
     // history counters, and killer moves.
 
     // If the search is not aborted, update the transposition table,
     // history counters, and killer moves.
@@ -1548,7 +1557,7 @@ namespace {
         return bestValue;
 
     if (bestValue < beta)
         return bestValue;
 
     if (bestValue < beta)
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
+        TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
     else
     {
         BetaCounter.add(pos.side_to_move(), depth, threadID);
     else
     {
         BetaCounter.add(pos.side_to_move(), depth, threadID);
@@ -1558,7 +1567,7 @@ namespace {
             update_history(pos, move, depth, movesSearched, moveCount);
             update_killers(move, ss[ply]);
         }
             update_history(pos, move, depth, movesSearched, moveCount);
             update_killers(move, ss[ply]);
         }
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
+        TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
     }
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
     }
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);