zwsearch.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 /* forward declarations of functions */
  26 static int zwsearch_nonull(int beta, int depth, int ply);
  27
  28 /* zero window search */
  29 int
  30 zwsearch(int beta, int depth, int ply, int check)
  31 {
  32         int i;
  33         int extend;
  34         int do_null;
  35         int moves_count;
  36         int score;
  37         int futility_max;
  38         int futility_prune;
  39         int is_check;
  40         struct moves_t moves;
  41         int best_score = -MATE_VALUE;
  42
  43         assert(beta > -MATE_VALUE && beta <= +MATE_VALUE);
  44         assert(depth >= 0 && depth <= MAX_PLY);
  45         assert(board_is_legal(&brd));
  46
  47         if (check_time(ply))
  48                 return 65535;
  49
  50         /* if we are too deep */
  51         if (ply >= MAX_PLY - 1)
  52                 return evaluate(beta - 1, beta);
  53
  54         /* search for captures */
  55         if (depth <= 0 && !check)
  56                 return quiesce(beta - 1, beta, 0, ply, 0);
  57
  58         do_null = TRUE;
  59         futility_prune = FALSE;
  60         futility_max = 0;
  61         hash_moves[ply] = 0;
  62
  63         /* check transposition table */
  64         if (e.main_hash_enabled) {
  65                 i = hashtable_get(brd.wtm, depth, ply, &hash_moves[ply], &score);
  66                 if (i) {
  67 #ifdef STATISTIC_COUNTERS
  68                         counters.transposition++;
  69 #endif
  70                         switch (i) {
  71                                 case EXACT:
  72                                         return score;
  73                                 case LOWER:
  74                                         if (score >= beta)
  75                                                 return score;
  76                                         do_null = FALSE;
  77                                         break;
  78                                 case UPPER:
  79                                         if (score < beta)
  80                                                 return score;
  81                                         break;
  82                                 default:
  83                                         assert(0);
  84                         }
  85                 }
  86         }
  87
  88         /* limited razoring at pre pre frontier */
  89         if (e.razoring && depth == 3 && !check && (MATERIAL_SCORE + 875) < beta) {
  90 #ifdef STATISTIC_COUNTERS
  91                 counters.razorings++;
  92 #endif
  93                 depth--;
  94         }
  95
  96         /* futility pruning according to Ernst A. Heinz */
  97         if (e.futility_pruning && depth < 3 && !check) {
  98                 assert(depth > 0);
  99
 100                 /* pre frontier */
 101                 if (depth == 2) {
 102                         score = evaluate(beta - 1, beta) + 475;
 103                         if (score < beta) {
 104                                 futility_max = score;
 105                                 futility_prune = TRUE;
 106                         }
 107                 } else {
 108                         /* frontier */
 109                         score = evaluate(beta - 1, beta) + 175;
 110                         if (score < beta) {
 111                                 futility_max = score;
 112                                 futility_prune = TRUE;
 113                         }
 114                 }
 115         }
 116
 117         /* NULL move pruning */
 118         if (e.null_pruning && do_null && !check && (depth >= 2) && \
 119                         (MATERIAL_SCORE >= beta - 875) && \
 120                         !SCORE_IS_MATE(beta) && (popcount(r_pieces[brd.wtm]) > 3)) {
 121                 int null_reduction = 3;         /* R = 3 */
 122
 123                 brd.cap_piece = 0;
 124                 brd.move = 0;                   /* NULL move */
 125
 126                 /* for takeback */
 127                 memcpy(&game_history.board[game_history.count++], &brd, \
 128                                 sizeof(struct board_t));
 129
 130                 if (brd.ep != -1)
 131                         brd.hash_key ^= hash_ep[_FILE(brd.ep)];
 132                 brd.hash_key ^= hash_side;
 133
 134                 brd.fifty_rule = 0;
 135                 brd.ep = -1;
 136                 brd.wtm ^= 1;
 137
 138                 /* search reduced depth */
 139                 if (depth - null_reduction - 1 > 0) {
 140                         score = -zwsearch_nonull(1 - beta, depth - null_reduction - 1, \
 141                                         ply + 1);
 142                         if (abort_search)
 143                                 return 65535;
 144                 } else {
 145                         score = -quiesce(-beta, 1 - beta, 0, ply + 1, 1);
 146                         if (abort_search)
 147                                 return 65535;
 148                 }
 149
 150                 takeback();
 151
 152                 if (score >= beta) {
 153 #ifdef STATISTIC_COUNTERS
 154                         counters.null_move_prunings++;
 155 #endif
 156                         return score;
 157                 }
 158         }
 159
 160         moves_count = 0;
 161         gen_moves(&moves);
 162
 163         for (i = 0; i < moves.count; i++) {
 164                 /* get move with largest score */
 165                 sort_moves(&moves, i, ply);
 166                 if (!make_move(moves.move[i], FALSE))
 167                         continue;
 168
 169                 is_check = IS_CHECKED(brd.wtm);
 170
 171                 if (futility_prune && !is_check && moves_count && !MOVE_IS_TACTICAL(moves.move[i])) {
 172                         best_score = MAX(best_score, futility_max);
 173                         takeback();
 174 #ifdef STATISTIC_COUNTERS
 175                         counters.futility_prunings++;
 176 #endif
 177                         continue;
 178                 }
 179
 180                 counters.searched_nodes++;
 181                 moves_count++;
 182
 183                 /* examine if we can reduce or extend move */
 184                 extend = moves_count > NOLMR_MOVES? \
 185                         get_extensions(moves.move[i], check, is_check, depth, ply) : \
 186                         check;
 187
 188                 score = -zwsearch(1 - beta, depth + extend - 1, ply + 1, is_check);
 189                 if (abort_search)
 190                         return 65535;
 191
 192                 if (score >= beta && extend < 0) {
 193                         /* research with original depth */
 194                         score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check);
 195                         if (abort_search)
 196                                 return 65535;
 197                 }
 198
 199                 takeback();
 200
 201                 if (score > best_score) {
 202                         best_score = score;
 203                         if (score >= beta) {
 204 #ifdef STATISTIC_COUNTERS
 205                                 counters.failed_high_total++;
 206                                 if (moves_count == 1)
 207                                         counters.failed_high_first++;
 208 #endif
 209                                 /* update history only for non tactical move */
 210                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 211                                         history_store(moves.move[i], depth, ply, best_score);
 212                                 if (e.main_hash_enabled)
 213                                         /* save in hashtable */
 214                                         hashtable_put(brd.wtm, depth, ply, LOWER, moves.move[i], best_score);
 215
 216                                 return best_score;
 217                         }
 218                 }
 219         }
 220         if (!moves_count)
 221                 best_score = check? -MATE_VALUE + ply : 0;
 222
 223         if (e.main_hash_enabled)
 224                 /* save in hashtable */
 225                 hashtable_put(brd.wtm, depth, ply, UPPER, 0, best_score);
 226
 227         assert(best_score > -MATE_VALUE);
 228         return best_score;
 229 }
 230
 231 /* zero window search with some restrictions */
 232 static int
 233 zwsearch_nonull(int beta, int depth, int ply)
 234 {
 235         int i;
 236         int is_check;
 237         int moves_count = 0;
 238         int score;
 239         struct moves_t moves;
 240         int best_score = -MATE_VALUE;
 241
 242         assert(beta > -MATE_VALUE && beta <= +MATE_VALUE);
 243         assert(depth >= 1 && depth <= MAX_PLY);
 244         assert(!IS_CHECKED(brd.wtm));
 245         assert(board_is_legal(&brd));
 246
 247         if (check_time(ply))
 248                 return 65535;
 249
 250         hash_moves[ply] = 0;
 251
 252         gen_moves(&moves);
 253
 254         for (i = 0; i < moves.count; i++) {
 255                 /* get move with largest score */
 256                 sort_moves(&moves, i, ply);
 257                 if (!make_move(moves.move[i], FALSE))
 258                         continue;
 259
 260                 counters.searched_nodes++;
 261                 moves_count++;
 262
 263                 is_check = IS_CHECKED(brd.wtm);
 264                 score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check);
 265                 if (abort_search)
 266                         return 65535;
 267
 268                 takeback();
 269
 270                 if (score > best_score) {
 271                         best_score = score;
 272                         if (score >= beta) {
 273 #ifdef STATISTIC_COUNTERS
 274                                 counters.failed_high_total++;
 275                                 if (moves_count == 1)
 276                                         counters.failed_high_first++;
 277 #endif
 278
 279                                 return best_score;
 280                         }
 281                 }
 282         }
 283
 284         if (!moves_count)
 285                 /* FIXME: what should I return? */
 286                 return MATE_VALUE;
 287
 288         assert(best_score > -MATE_VALUE);
 289         return best_score;
 290 }