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 static int futility_margins[] = {0, 125, 175, 325, 375, 425};
  27
  28 /* zero window search */
  29 int
  30 zwsearch(int beta, int depth, int ply, int check, int do_null)
  31 {
  32         int i;
  33         int extend;
  34         int moves_count;
  35         int score;
  36         int futility_max;
  37         int futility_prune;
  38         int is_check;
  39         struct moves_t moves;
  40
  41         assert(beta > -MATE_VALUE && beta <= +MATE_VALUE);
  42         assert(depth >= 0 && depth <= MAX_PLY);
  43         assert(board_is_legal(&brd));
  44
  45         if (check_time(ply))
  46                 return 65535;
  47
  48         if (reps() || evaluate_draw())
  49                 return 0;
  50
  51         /* if we are too deep */
  52         if (ply >= MAX_PLY - 1)
  53                 return evaluate(beta - 1, beta);
  54
  55         /* search for captures */
  56         if (depth <= 0 && !check)
  57                 return quiesce(beta - 1, beta, 0, ply, 0);
  58
  59         do_null = TRUE;
  60         futility_prune = FALSE;
  61         futility_max = 0;
  62         hash_moves[ply] = 0;
  63
  64         /* check transposition table */
  65         if (e.main_hash_enabled) {
  66                 i = hashtable_get(brd.wtm, depth, ply, &hash_moves[ply], &score);
  67                 if (i) {
  68 #ifdef STATISTIC_COUNTERS
  69                         counters.transposition++;
  70 #endif
  71                         switch (i) {
  72                                 case EXACT:
  73                                         return score;
  74                                 case LOWER:
  75                                         if (score >= beta)
  76                                                 return beta;
  77                                         do_null = FALSE;
  78                                         break;
  79                                 case UPPER:
  80                                         if (score < beta)
  81                                                 return beta - 1;
  82                                         break;
  83                                 default:
  84                                         assert(0);
  85                         }
  86                 }
  87         }
  88
  89         /* NULL move pruning */
  90         if (e.null_pruning && do_null && !check && (depth >= 2) && \
  91                         (MATERIAL_SCORE >= beta - 875) && \
  92                         !SCORE_IS_MATE(beta) && material_pieces[brd.wtm]) {
  93
  94                 int null_reduction = depth >= 5? 3 : 2;
  95
  96                 brd.cap_piece = 0;
  97                 brd.move = 0;                   /* NULL move */
  98
  99                 /* for takeback */
 100                 memcpy(&game_history.board[game_history.count++], &brd, \
 101                                 sizeof(struct board_t));
 102
 103                 if (brd.ep != -1)
 104                         brd.hash_key ^= hash_ep[_FILE(brd.ep)];
 105                 brd.hash_key ^= hash_side;
 106
 107                 brd.fifty_rule = 0;
 108                 brd.ep = -1;
 109                 brd.wtm ^= 1;
 110
 111                 /* search reduced depth */
 112                 if (depth - null_reduction - 1 > 0) {
 113                         score = -zwsearch(1 - beta, depth - null_reduction - 1, \
 114                                         ply + 1, 0, 0);
 115                         if (abort_search)
 116                                 return 65535;
 117                 } else {
 118                         score = -quiesce(-beta, 1 - beta, 0, ply + 1, 1);
 119                         if (abort_search)
 120                                 return 65535;
 121                 }
 122
 123                 takeback();
 124
 125                 if (score >= beta) {
 126 #ifdef STATISTIC_COUNTERS
 127                         counters.null_move_prunings++;
 128 #endif
 129                         return beta;
 130                 }
 131         }
 132
 133         /* extended futility pruning */
 134         if (e.futility_pruning && depth <= 5 && !check && !SCORE_IS_MATE(beta)) {
 135                 assert(depth > 0);
 136
 137                 if (MATERIAL_SCORE + futility_margins[depth] < beta)
 138                         futility_prune = TRUE;
 139         }
 140         moves_count = 0;
 141         gen_moves(&moves);
 142
 143         for (i = 0; i < moves.count; i++) {
 144                 /* get move with largest score */
 145                 sort_moves(&moves, i, ply);
 146                 if (!make_move(moves.move[i], FALSE))
 147                         continue;
 148
 149                 is_check = IS_CHECKED(brd.wtm);
 150
 151                 if (futility_prune && !is_check && moves_count && !MOVE_IS_TACTICAL(moves.move[i])) {
 152                         takeback();
 153 #ifdef STATISTIC_COUNTERS
 154                         counters.futility_prunings++;
 155 #endif
 156                         continue;
 157                 }
 158
 159                 moves_count++;
 160
 161                 /* examine if we can reduce or extend move */
 162                 extend = moves_count > NOLMR_MOVES? \
 163                         get_extensions(moves.move[i], check, is_check, depth, ply) : \
 164                         check;
 165                 if (extend < 0) {
 166                         extend = MIN(-MIN(depth - 2, (moves_count > 2)? 2 : 1), 0);
 167                 }
 168
 169                 score = -zwsearch(1 - beta, depth + extend - 1, ply + 1, is_check, 1);
 170                 if (abort_search)
 171                         return 65535;
 172
 173                 if (score >= beta && extend < 0) {
 174                         /* research with original depth */
 175                         score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check, 1);
 176                         if (abort_search)
 177                                 return 65535;
 178                 }
 179
 180                 takeback();
 181
 182                         if (score >= beta) {
 183 #ifdef STATISTIC_COUNTERS
 184                                 counters.failed_high_total++;
 185                                 if (moves_count == 1)
 186                                         counters.failed_high_first++;
 187 #endif
 188                                 /* update history only for non tactical move */
 189                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 190                                         history_store(moves.move[i], depth, ply, beta);
 191                                 if (e.main_hash_enabled)
 192                                         /* save in hashtable */
 193                                         hashtable_put(brd.wtm, depth, ply, LOWER, moves.move[i],
 194                                                         beta);
 195
 196                                 return beta;
 197                         }
 198         }
 199         if (!moves_count)
 200                 beta = check? -MATE_VALUE + ply + 1 : 1;
 201
 202         if (e.main_hash_enabled)
 203                 /* save in hashtable */
 204                 hashtable_put(brd.wtm, depth, ply, UPPER, 0, beta - 1);
 205
 206         return beta - 1;
 207 }