src/search.cpp

   1 /* Copyright (C) 2007-2011 Vincent Ollivier
   2  *
   3  * Purple Haze is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * Purple Haze is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  15  */
  16
  17 #include <assert.h>
  18 #include <iostream>
  19 #include <stdio.h>
  20 #include <time.h>
  21 #include <iomanip>
  22
  23 #include "game.h"
  24 #include "search.h"
  25 #include "eval.h"
  26
  27 unsigned long long int Game::perft(unsigned int depth)
  28 {
  29     if (depth == 0) return 1;
  30     unsigned int nodes = 0;
  31     Color c = current_position().get_turn_color();
  32     bool use_lazy = false; // Lazy moves generation is not usefull in perft()
  33     Moves moves(board, pieces, current_position(), search_moves, use_lazy);
  34     Move move;
  35     while (!(move = moves.next()).is_null()) {
  36 #ifdef LEGAL
  37         if (depth == 1) {
  38             if (is_legal(move)) ++nodes; // TODO: Finish is_legal()
  39         } else {
  40 #endif
  41             make_move(move);
  42             if (!is_check(c)) nodes += perft(depth - 1);
  43             undo_move(move);
  44 #ifdef LEGAL
  45         }
  46 #endif
  47     }
  48     return nodes;
  49 }
  50
  51 int Game::quiescence(int alpha, int beta, int depth, const int ply)
  52 {
  53     if (time.poll(nodes_count)) return 0;
  54
  55     const int stand_pat = eval(alpha, beta);
  56     if (ply >= MAX_PLY) return stand_pat;
  57
  58     if (stand_pat >= beta) return stand_pat; // Beta cut-off
  59
  60     // Delta pruning
  61     const int delta = PIECE_VALUE[QUEEN]; // TODO: Switch off in late endgame
  62     if (stand_pat < alpha - delta) return alpha;
  63
  64     if (alpha < stand_pat) alpha = stand_pat; // New alpha
  65
  66     Color player = current_position().get_turn_color();
  67
  68     Moves moves(board, pieces, current_position(), search_moves);
  69     Move move;
  70     while (!(move = moves.next()).is_null()) {
  71         if (moves.get_state() > GOOD_CAPTURES) break; // Skip bad captures
  72         make_move(move);
  73
  74         if (is_check(player)) { // Illegal move
  75             undo_move(move);
  76             continue;
  77         }
  78
  79         const int score = -quiescence(-beta, -alpha, depth - 1, ply + 1);
  80         undo_move(move);
  81         if (time.poll(nodes_count)) return 0;
  82         if (score >= beta) {
  83             return score;
  84         }
  85         if (score > alpha) {
  86             alpha = score;
  87         }
  88     }
  89     if (time.poll(nodes_count)) return 0;
  90     return alpha;
  91 }
  92
  93 template<NodeType node_type>
  94 int Game::search(int alpha, int beta, int depth, const int ply)
  95 {
  96     if (time.poll(nodes_count)) return 0;
  97     if (depth <= 0) return quiescence(alpha, beta, 0, ply + 1); // Quiescence
  98     if (tree.has_repetition_draw()) return 0; // Repetition draw rules
  99
 100     int score = -INF;
 101     const int old_alpha = alpha;
 102     Position pos = current_position();
 103     int best_score = -INF;
 104     Move best_move;
 105     const bool is_pv = (node_type == PV);
 106
 107     // Lookup in Transposition Table
 108     bool is_empty;
 109     Transposition trans = tt.lookup(pos.hash(), &is_empty);
 110     if (!is_empty) {
 111         // FIXME Avoid a potential bug with tt.lookup()
 112         const bool discard = pos.hash() == 0 &&
 113                              trans.get_bound() == UNDEF_BOUND;
 114
 115         if (/*!is_pv &&*/ depth <= trans.get_depth() && !discard) {
 116             const int tr_score = trans.get_value();
 117             switch (trans.get_bound()) {
 118                 case EXACT: return tr_score; // Already searched node
 119                 case UPPER: if (tr_score < beta) beta = tr_score; break;
 120                 case LOWER: if (tr_score > alpha) alpha = tr_score; break;
 121                 default: assert(false);
 122             }
 123             if (alpha >= beta) return tr_score; // TT cause a cut-off
 124         }
 125         Move bm = trans.get_best_move();
 126         if (!bm.is_null()) best_move = bm; // Save the best move
 127     }
 128
 129     const Color player = pos.get_turn_color();
 130     const bool is_in_check = is_check(player);
 131     const bool is_null_move = !pos.get_null_move_right(); // No more than one
 132
 133     // Check Extension
 134     if (is_in_check) ++depth;
 135
 136 #ifdef NMP
 137     // Null Move Pruning
 138     const bool null_move_allowed = !is_in_check && !is_null_move && !is_pv;
 139
 140     const int nb_pieces = pieces.get_nb_pieces(player);
 141     if (null_move_allowed && depth > NMP_DEPTH && nb_pieces > 3) {
 142         Move null_move;
 143         make_move(null_move);
 144         current_position().set_null_move_right(false); // No consecutive NM
 145         const int r_depth = depth - R_ADAPT(depth, nb_pieces) - 1;
 146         score = -search<node_type>(-beta, -beta + 1, r_depth, ply + 1);
 147         undo_move(null_move);
 148         if (score >= beta) {
 149             return score;
 150         }
 151     } else if (is_null_move) {
 152         // Next move we will again have the right to do another null-move
 153         pos.set_null_move_right(true);
 154     }
 155 #endif
 156
 157     // Internal Iterative Deepening
 158     if (depth > IID_DEPTH && best_move.is_null() && !is_null_move && is_pv) {
 159         Moves moves(board, pieces, current_position(), search_moves);
 160         int internal_best_score = -INF;
 161         Move move;
 162         while (!(move = moves.next()).is_null()) {
 163             make_move(move);
 164             if (is_check(player)) {
 165                 undo_move(move);
 166                 continue;
 167             }
 168             score = -search<PV>(-beta, -alpha, depth / 2, ply + 1);
 169             undo_move(move);
 170             if (score > internal_best_score) {
 171                 internal_best_score = score;
 172                 best_move = move;
 173             }
 174         }
 175         // TODO Call search directly and find the best move in TT?
 176         /*
 177         tt.save(pos.hash(), 0, UNDEF_BOUND, 0, Move());
 178         Transposition trans_test = tt.lookup(pos.hash());
 179         pos.set_null_move_right(false);
 180         score = search<PV>(alpha, beta, depth / 2, ply);
 181         if (score <= alpha) {
 182             // Avoid storing lower bound in TT
 183             score = search<PV>(-INF, beta, depth / 2, ply);
 184         }
 185         pos.set_null_move_right(true);
 186         Move trans_move = tt.lookup(pos.hash()).get_best_move();
 187         if (trans_move != best_move) {
 188             cout << "score=" << score << " alpha=" << alpha << " ";
 189             cout << trans_test.to_string() << " ";
 190             cout << internal_best_score << " " << best_move << " ";
 191             cout << tt.lookup(pos.hash()).to_string() << endl;
 192         }
 193         //assert(trans_move == best_move); // trans_move is sometime null
 194         */
 195     }
 196
 197     bool legal_move_found = false;
 198     bool is_principal_variation = true;
 199
 200     Moves moves(board, pieces, current_position(), search_moves);
 201     moves.add(best_move, BEST);
 202
 203     // Killer moves need pseudo legality checking before we can use them,
 204     // but they can cause a cut-off and dispense to generate quiet moves
 205     // so it's worth it.
 206     for (int i = 0; i < MAX_KILLERS; ++i) {
 207         Move killer = get_killer_move(depth, i);
 208         if (is_legal(killer)) moves.add(killer, KILLERS);
 209     }
 210
 211     Move move;
 212     while (!(move = moves.next()).is_null()) {
 213         if (move.is_capture()) {
 214             if (board.get_piece(move.get_dest()).get_type() == KING) {
 215                 return INF - ply; // Checkmate
 216             }
 217         }
 218         make_move(move);
 219         if (is_check(player)) { // Skip illegal move
 220             undo_move(move);
 221             continue;
 222         }
 223         legal_move_found = true;
 224
 225         // PVS code from http://www.talkchess.com/forum/viewtopic.php?t=26974
 226         if (is_principal_variation) {
 227             best_score = -search<PV>(-beta, -alpha, depth - 1, ply + 1);
 228
 229             undo_move(move);
 230             if (best_score > alpha) {
 231                 if (best_score >= beta) { // Beta cut-off
 232                     // Update killer moves
 233                     if (!move.is_capture()) set_killer_move(depth, move);
 234
 235                     best_move = move;
 236                     goto transposition;
 237                 }
 238                 alpha = best_score;
 239             }
 240             is_principal_variation = false;
 241         } else {
 242             const bool is_giving_check = is_check(!player);
 243
 244             // Futility Pruning
 245             if (depth <= FUTILITY_DEPTH &&
 246                 //!best_move.is_null() &&
 247                 !is_in_check && !is_giving_check &&
 248                 !is_killer_move(depth, move) &&
 249                 !move.is_capture() && !move.is_promotion()) {
 250                     // Using an array of margins is an idea from Crafty
 251                     score = material_eval() + FUTILITY_MARGINS[depth];
 252                     if (score < alpha) {
 253                         if (score > best_score) best_score = score;
 254                         undo_move(move);
 255                         continue;
 256                     }
 257             }
 258
 259             // Late Move Reduction
 260             if (depth > LMR_DEPTH && // TODO find the best minimal depth
 261                 //!best_move.is_null() &&
 262                 !is_in_check && !is_giving_check &&
 263                 !is_killer_move(depth, move) &&
 264                 !move.is_capture() && !move.is_promotion()) {
 265
 266                 // Do the search at a reduced depth
 267                 score = -search<ALL>(-alpha - 1, -alpha, depth - 2, ply + 1);
 268             } else {
 269                 score = -search<ALL>(-alpha - 1, -alpha, depth - 1, ply + 1);
 270             }
 271
 272             // Re-search
 273             if (alpha < score && score < beta) {
 274                 score = -search<ALL>(-beta, -alpha, depth - 1, ply + 1);
 275                 if (alpha < score) {
 276                     alpha = score;
 277                 }
 278             }
 279
 280             undo_move(move);
 281             if (time.poll(nodes_count)) return 0;
 282             if (score > best_score) { // Found a new best move
 283                 best_score = score;
 284                 best_move = move;
 285                 if (score >= beta) {// Sufficient to cause a cut-off?
 286                     // Update killer moves
 287                     if (!move.is_capture()) set_killer_move(depth, move);
 288
 289                     goto transposition;
 290                 }
 291             }
 292         }
 293     }
 294     if (time.poll(nodes_count)) return 0;
 295     if (!legal_move_found) { // End of game?
 296         if (is_in_check) return -INF + ply; // Checkmate
 297         return 0; // Stalemate
 298     }
 299
 300 transposition:
 301     // Store the search to Transposition Table
 302     //assert(!best_move.is_null());
 303     if (depth >= trans.get_depth() /*&& !is_null_move*/) {
 304         const int value = best_score;
 305         const Bound bound = (best_score >= beta ? LOWER :
 306                                 (best_score <= old_alpha ? UPPER : EXACT));
 307         if (bound == UPPER) best_move = Move(); // Don't store best move
 308         tt.save(pos.hash(), value, bound, depth, best_move);
 309     }
 310
 311     return best_score;
 312 }
 313
 314 Move Game::root(int max_depth)
 315 {
 316     time.start_thinking(current_position().get_ply());
 317     Color player = current_position().get_turn_color();
 318     print_thinking_header();
 319     nodes_count = 0;
 320     int best_score = 0;
 321     Move best_move;
 322     assert(max_depth <= MAX_PLY);
 323     int it; // Iteration of Depth
 324     int best_scores[MAX_PLY];
 325     for (it = 1; it < max_depth; ++it) { // Iterative Deepening
 326         int score;
 327         int alpha = -INF;
 328         int beta = INF;
 329         if (time.is_out_of_time()) break; // Do not start this ply if no time
 330         if (time.get_allocated_time() - time.get_elapsed_time() < 100) {
 331             // Decrease polling interval if <1s left
 332             time.set_polling_interval(100000);
 333         }
 334         // Mate pruning
 335         if (it > 6) {
 336             bool is_mate = true;
 337             for (int i = 1; i < 4; ++i) {
 338                 int val = best_scores[it - i];
 339                 if (-INF + MAX_PLY < val && val < INF - MAX_PLY) {
 340                     is_mate = false;
 341                 }
 342             }
 343             if (is_mate) break; // The position was mate in the 3 previous ply
 344         }
 345
 346         Moves moves(board, pieces, current_position(), search_moves);
 347         moves.add(best_move, BEST);
 348         Move move;
 349         int nb_moves;
 350         for (nb_moves = 1; !(move = moves.next()).is_null(); ++nb_moves) {
 351             make_move(move);
 352             if (is_check(player)) { // Skip illegal move
 353                 undo_move(move);
 354                 --nb_moves;
 355                 continue;
 356             }
 357             // FIXME
 358             //NodeType node_type = (nb_moves ? PV : ALL);
 359             //score = -search<node_type>(-beta, -alpha, it - 1, 1);
 360             if (nb_moves == 1) {
 361                 score = -search<PV>(-beta, -alpha, it - 1, 1);
 362             } else {
 363                 score = -search<ALL>(-beta, -alpha, it - 1, 1);
 364             }
 365             undo_move(move);
 366             if (time.is_out_of_time()) break; // Discard this move
 367             if (score > alpha) {
 368                 alpha = score;
 369                 best_score = score;
 370                 best_move = move;
 371                 if (nodes_count > 200000) { // Save CPU time at the beginning
 372                     print_thinking(it, alpha, best_move);
 373                 }
 374             }
 375         }
 376         if (time.is_out_of_time()) {
 377             // TODO: restore best_move and best_score from previous ply?
 378             break; // Discard this ply
 379         }
 380         if (!best_move.is_null()) {
 381             tt.save(current_position().hash(), alpha, EXACT, it, best_move);
 382         }
 383         best_scores[it] = best_score;
 384
 385         // If there is only one legal move, no iterative deepening needed
 386         if (nb_moves == 1) break;
 387     }
 388     if (!best_move.is_null()) {
 389         print_thinking(it, best_score, best_move);
 390     }
 391     return best_move;
 392 }