src/search.cpp

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