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