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