src/search.cpp

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