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         /* NULL move pruning */
 100         if (e.null_pruning && do_null && !check && (depth >= 2) && \
 101                         (MATERIAL_SCORE >= beta - 875) && \
 102                         !SCORE_IS_MATE(beta) && (popcount(side_boards[brd.wtm]) > 4)) {
 103
 104                 int null_reduction = 3;
 105
 106                 brd.cap_piece = 0;
 107                 brd.move = 0;                   /* NULL move */
 108
 109                 /* for takeback */
 110                 memcpy(&game_history.board[game_history.count++], &brd, \
 111                                 sizeof(struct board_t));
 112
 113                 if (brd.ep != -1)
 114                         brd.hash_key ^= hash_ep[_FILE(brd.ep)];
 115                 brd.hash_key ^= hash_side;
 116
 117                 brd.fifty_rule = 0;
 118                 brd.ep = -1;
 119                 brd.wtm ^= 1;
 120
 121                 /* search reduced depth */
 122                 if (depth - null_reduction - 1 > 0) {
 123                         score = -zwsearch_nonull(1 - beta, depth - null_reduction - 1, \
 124                                         ply + 1);
 125                         if (abort_search)
 126                                 return 65535;
 127                 } else {
 128                         score = -quiesce(-beta, 1 - beta, 0, ply + 1, 1);
 129                         if (abort_search)
 130                                 return 65535;
 131                 }
 132
 133                 takeback();
 134
 135                 if (score >= beta) {
 136 #ifdef STATISTIC_COUNTERS
 137                         counters.null_move_prunings++;
 138 #endif
 139                         return beta;
 140                 }
 141         }
 142
 143         /* futility pruning according to Ernst A. Heinz */
 144         if (e.futility_pruning && depth < 3 && !check) {
 145                 assert(depth > 0);
 146
 147                 /* pre frontier */
 148                 if (depth == 2) {
 149                         score = evaluate(beta - 1, beta) + 475;
 150                         if (score < beta) {
 151                                 futility_max = score;
 152                                 futility_prune = TRUE;
 153                         }
 154                 } else {
 155                         /* frontier */
 156                         score = evaluate(beta - 1, beta) + 175;
 157                         if (score < beta) {
 158                                 futility_max = score;
 159                                 futility_prune = TRUE;
 160                         }
 161                 }
 162         }
 163         moves_count = 0;
 164         gen_moves(&moves);
 165
 166         int futil_count = 3 + (1 << (6 * depth / 8));
 167
 168         for (i = 0; i < moves.count; i++) {
 169                 /* get move with largest score */
 170                 sort_moves(&moves, i, ply);
 171                 if (!make_move(moves.move[i], FALSE))
 172                         continue;
 173
 174                 is_check = IS_CHECKED(brd.wtm);
 175
 176                 if (futility_prune && !is_check && moves_count && !MOVE_IS_TACTICAL(moves.move[i])) {
 177                         takeback();
 178 #ifdef STATISTIC_COUNTERS
 179                         counters.futility_prunings++;
 180 #endif
 181                         continue;
 182                 }
 183
 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                 if (extend < 0 && moves_count >= futil_count) extend--;
 191
 192                 score = -zwsearch(1 - beta, depth + extend - 1, ply + 1, is_check);
 193                 if (abort_search)
 194                         return 65535;
 195
 196                 if (score >= beta && extend < 0) {
 197                         /* research with original depth */
 198                         score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check);
 199                         if (abort_search)
 200                                 return 65535;
 201                 }
 202
 203                 takeback();
 204
 205                         if (score >= beta) {
 206 #ifdef STATISTIC_COUNTERS
 207                                 counters.failed_high_total++;
 208                                 if (moves_count == 1)
 209                                         counters.failed_high_first++;
 210 #endif
 211                                 /* update history only for non tactical move */
 212                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 213                                         history_store(moves.move[i], depth, ply, beta);
 214                                 if (e.main_hash_enabled)
 215                                         /* save in hashtable */
 216                                         hashtable_put(brd.wtm, depth, ply, LOWER, moves.move[i],
 217                                                         beta);
 218
 219                                 return beta;
 220                         }
 221         }
 222         if (!moves_count)
 223                 beta = check? -MATE_VALUE + ply + 1 : 1;
 224
 225         if (e.main_hash_enabled)
 226                 /* save in hashtable */
 227                 hashtable_put(brd.wtm, depth, ply, UPPER, 0, beta - 1);
 228
 229         return beta - 1;
 230 }
 231
 232 /* zero window search with some restrictions */
 233 static int
 234 zwsearch_nonull(int beta, int depth, int ply)
 235 {
 236         int i;
 237         int is_check;
 238         int moves_count = 0;
 239         int score;
 240         struct moves_t moves;
 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                 moves_count++;
 261
 262                 is_check = IS_CHECKED(brd.wtm);
 263                 score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check);
 264                 if (abort_search)
 265                         return 65535;
 266
 267                 takeback();
 268
 269                 if (score >= beta) {
 270 #ifdef STATISTIC_COUNTERS
 271                         counters.failed_high_total++;
 272                         if (moves_count == 1)
 273                                 counters.failed_high_first++;
 274 #endif
 275                         return beta;
 276                 }
 277         }
 278
 279         if (!moves_count)
 280                 /* FIXME: what should I return? */
 281                 return MATE_VALUE;
 282
 283         return beta - 1;
 284 }