search.c

   1 /*
   2  *      This program is free software; you can redistribute it and/or modify
   3  *      it under the terms of the GNU General Public License as published by
   4  *      the Free Software Foundation; either version 2 of the License, or
   5  *      (at your option) any later version.
   6  *
   7  *      This program is distributed in the hope that it will be useful,
   8  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  *      GNU General Public License for more details.
  11  *
  12  *      You should have received a copy of the GNU General Public License
  13  *      along with this program; if not, write to the Free Software
  14  *      Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  15  */
  16 #include "common.h"
  17 #include "attacks.h"
  18 #include "board.h"
  19 #include "engine.h"
  20 #include "evaluate.h"
  21 #include "move.h"
  22 #include "search.h"
  23 #include "trans.h"
  24
  25 /* save move to killers if needed and update history */
  26 void
  27 history_store(int move, int depth, int ply, int score)
  28 {
  29         history[brd.wtm][PIECE(move)][move & 0xFFF] += depth * depth;
  30
  31         if (SCORE_IS_MATE(score)) {
  32                 /* save mate killer separately */
  33                 if (!killers[ply].mate_killer)
  34                         killers[ply].mate_killer = move;
  35         } else
  36                 if (killers[ply].killer1 != move) {
  37                         killers[ply].killer2 = killers[ply].killer1;
  38                         killers[ply].killer1 = move;
  39                 }
  40 }
  41
  42 /* search for PV */
  43 int
  44 search_pv(int alpha, int beta, int depth, int ply, int check)
  45 {
  46         int i, j;
  47         int old_alpha;
  48         int extend;
  49         int score;
  50         int is_check;
  51         int moves_count;
  52         int searching_pv;
  53         struct moves_t moves;
  54
  55         assert(alpha >= -MATE_VALUE && alpha < +MATE_VALUE);
  56         assert(beta > alpha && beta <= +MATE_VALUE);
  57         assert(depth >= 0 && depth <= MAX_PLY);
  58         assert(board_is_legal(&brd));
  59
  60         searching_pv = TRUE;
  61         moves_count = 0;
  62
  63         old_alpha = alpha;
  64         pv_length[ply] = ply;
  65
  66         if (check_time(ply))
  67                 return 65535;
  68
  69         if (reps() || evaluate_draw())
  70                 return 0;
  71
  72         /* if we are too deep */
  73         if (ply >= MAX_PLY - 1)
  74                 return evaluate(alpha, beta);
  75
  76         if (depth <= 0 && !check)
  77                 return quiesce(alpha, beta, 0, ply, 0);
  78
  79         gen_moves(&moves);
  80
  81         hash_moves[ply] = 0;
  82
  83         /* always try to follow previous PV */
  84         if (follow_pv) {
  85                 follow_pv = FALSE;
  86                 for (i = 0; i < moves.count; i++)
  87                         if (moves.move[i] == pv[0][ply]) {
  88                                 follow_pv = TRUE;
  89                                 hash_moves[ply] = pv[0][ply];
  90                                 break;
  91                         }
  92         }
  93
  94         if (!hash_moves[ply] && e.main_hash_enabled)
  95                 if (hashtable_get(brd.wtm, depth, ply, &hash_moves[ply], &score)) {
  96 #ifdef STATISTIC_COUNTERS
  97                         counters.transposition++;
  98 #endif
  99                 }
 100
 101         /* internal iterative deeping if we haven't hash move */
 102         if (!hash_moves[ply] && get_engine_value(&e.iid) && depth > 3) {
 103                 i = MIN(depth - 2, depth / 2);
 104
 105                 score = search_pv(alpha, beta, i, ply, check);
 106                 if (abort_search)
 107                         return 65535;
 108
 109                 if (score <= alpha) {
 110                         score = search_pv(-MATE_VALUE, beta, i, ply, check);
 111                         if (abort_search)
 112                                 return 65535;
 113                 }
 114                 hash_moves[ply] = pv[ply][ply];
 115         }
 116
 117         for (i = 0; i < moves.count; i++) {
 118                 /* get move with largest score */
 119                 sort_moves(&moves, i, ply);
 120                 if (!make_move(moves.move[i], FALSE))
 121                         continue;
 122
 123                 moves_count++;
 124
 125                 is_check = IS_CHECKED(brd.wtm);
 126
 127                 /* search first move with full window */
 128                 if (searching_pv) {
 129                         score = -search_pv(-beta, -alpha, depth + check - 1, ply + 1, is_check);
 130                         if (abort_search)
 131                                 return 65535;
 132                 } else {
 133                         /* examine if we can reduce or extend move */
 134                         extend = moves_count > NOLMR_MOVES? \
 135                                          get_extensions(moves.move[i], check, is_check, depth, ply) : \
 136                                          check;
 137                         if (extend < 0) {
 138                                 extend = MIN(-MIN(depth - 2, (moves_count > 2)? 2 : 1), 0);
 139                         }
 140
 141                         score = -zwsearch(-alpha, depth + extend - 1, ply + 1, is_check, 1);
 142                         if (abort_search)
 143                                 return 65535;
 144
 145                         if (score > alpha && extend < 0) {
 146                                 score = -zwsearch(-alpha, depth - 1, ply + 1, is_check, 1);
 147                                 if (abort_search)
 148                                         return 65535;
 149                         }
 150
 151                         if (score > alpha && score < beta) {
 152                                 int reset_fhr = FALSE;
 153                                 if (!fail_high_root && ply == 1) {
 154                                         fail_high_root = TRUE;
 155                                         reset_fhr = TRUE;
 156                                 }
 157                                 score = -search_pv(-beta, -alpha, depth + check - 1, ply + 1, is_check);
 158                                 if (reset_fhr)
 159                                         fail_high_root = FALSE;
 160                                 if (abort_search)
 161                                         return 65535;
 162                         }
 163                 }
 164
 165                 takeback();
 166
 167                 searching_pv = FALSE;
 168
 169                 if (score > alpha) {
 170                         if (score >= beta) {
 171 #ifdef STATISTIC_COUNTERS
 172                                 counters.failed_high_total++;
 173                                 if (moves_count == 1)
 174                                         counters.failed_high_first++;
 175 #endif
 176                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 177                                         history_store(moves.move[i], depth, ply, beta);
 178
 179                                 return beta;
 180                         }
 181                         alpha = score;
 182                         pv[ply][ply] = moves.move[i];
 183
 184                         for (j = ply + 1; j < pv_length[ply + 1]; j++)
 185                                 pv[ply][j] = pv[ply + 1][j];
 186                         pv_length[ply] = pv_length[ply + 1];
 187                 }
 188         }
 189
 190         if (!moves_count)
 191                 alpha = check? -MATE_VALUE + ply : 0;
 192
 193         return alpha;
 194 }