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 #include <math.h>
  25
  26 /* forward declarations of functions */
  27 static int zwsearch_nonull(int beta, int depth, int ply);
  28
  29 /* zero window search */
  30 int
  31 zwsearch(int beta, int depth, int ply, int check)
  32 {
  33         int i;
  34         int extend;
  35         int do_null;
  36         int moves_count;
  37         int score;
  38         int futility_max;
  39         int futility_prune;
  40         int is_check;
  41         struct moves_t moves;
  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
 125                 int null_reduction = 3;
 126
 127                 brd.cap_piece = 0;
 128                 brd.move = 0;                   /* NULL move */
 129
 130                 /* for takeback */
 131                 memcpy(&game_history.board[game_history.count++], &brd, \
 132                                 sizeof(struct board_t));
 133
 134                 if (brd.ep != -1)
 135                         brd.hash_key ^= hash_ep[_FILE(brd.ep)];
 136                 brd.hash_key ^= hash_side;
 137
 138                 brd.fifty_rule = 0;
 139                 brd.ep = -1;
 140                 brd.wtm ^= 1;
 141
 142                 /* search reduced depth */
 143                 if (depth - null_reduction - 1 > 0) {
 144                         score = -zwsearch_nonull(1 - beta, depth - null_reduction - 1, \
 145                                         ply + 1);
 146                         if (abort_search)
 147                                 return 65535;
 148                 } else {
 149                         score = -quiesce(-beta, 1 - beta, 0, ply + 1, 1);
 150                         if (abort_search)
 151                                 return 65535;
 152                 }
 153
 154                 takeback();
 155
 156                 if (score >= beta) {
 157 #ifdef STATISTIC_COUNTERS
 158                         counters.null_move_prunings++;
 159 #endif
 160                         return beta;
 161                 }
 162         }
 163
 164         moves_count = 0;
 165         gen_moves(&moves);
 166
 167         for (i = 0; i < moves.count; i++) {
 168                 /* get move with largest score */
 169                 sort_moves(&moves, i, ply);
 170                 if (!make_move(moves.move[i], FALSE))
 171                         continue;
 172
 173                 is_check = IS_CHECKED(brd.wtm);
 174
 175                 if (futility_prune && !is_check && moves_count && !MOVE_IS_TACTICAL(moves.move[i])) {
 176                         takeback();
 177 #ifdef STATISTIC_COUNTERS
 178                         counters.futility_prunings++;
 179 #endif
 180                         continue;
 181                 }
 182
 183                 moves_count++;
 184
 185                 /* examine if we can reduce or extend move */
 186                 extend = moves_count > NOLMR_MOVES? \
 187                         get_extensions(moves.move[i], check, is_check, depth, ply) : \
 188                         check;
 189
 190                 score = -zwsearch(1 - beta, depth + extend - 1, ply + 1, is_check);
 191                 if (abort_search)
 192                         return 65535;
 193
 194                 if (score >= beta && extend < 0) {
 195                         /* research with original depth */
 196                         score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check);
 197                         if (abort_search)
 198                                 return 65535;
 199                 }
 200
 201                 takeback();
 202
 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, beta);
 212                                 if (e.main_hash_enabled)
 213                                         /* save in hashtable */
 214                                         hashtable_put(brd.wtm, depth, ply, LOWER, moves.move[i],
 215                                                         beta);
 216
 217                                 return beta;
 218                         }
 219         }
 220         if (!moves_count)
 221                 beta = check? -MATE_VALUE + ply : 0 + 1;
 222
 223         if (e.main_hash_enabled)
 224                 /* save in hashtable */
 225                 hashtable_put(brd.wtm, depth, ply, UPPER, 0, beta - 1);
 226
 227         return beta - 1;
 228 }
 229
 230 /* zero window search with some restrictions */
 231 static int
 232 zwsearch_nonull(int beta, int depth, int ply)
 233 {
 234         int i;
 235         int is_check;
 236         int moves_count = 0;
 237         int score;
 238         struct moves_t moves;
 239
 240         assert(beta > -MATE_VALUE && beta <= +MATE_VALUE);
 241         assert(depth >= 1 && depth <= MAX_PLY);
 242         assert(!IS_CHECKED(brd.wtm));
 243         assert(board_is_legal(&brd));
 244
 245         if (check_time(ply))
 246                 return 65535;
 247
 248         hash_moves[ply] = 0;
 249
 250         gen_moves(&moves);
 251
 252         for (i = 0; i < moves.count; i++) {
 253                 /* get move with largest score */
 254                 sort_moves(&moves, i, ply);
 255                 if (!make_move(moves.move[i], FALSE))
 256                         continue;
 257
 258                 moves_count++;
 259
 260                 is_check = IS_CHECKED(brd.wtm);
 261                 score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check);
 262                 if (abort_search)
 263                         return 65535;
 264
 265                 takeback();
 266
 267                 if (score >= beta) {
 268 #ifdef STATISTIC_COUNTERS
 269                         counters.failed_high_total++;
 270                         if (moves_count == 1)
 271                                 counters.failed_high_first++;
 272 #endif
 273                         return beta;
 274                 }
 275         }
 276
 277         if (!moves_count)
 278                 /* FIXME: what should I return? */
 279                 return MATE_VALUE;
 280
 281         return beta - 1;
 282 }