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         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 beta;
  76                                         do_null = FALSE;
  77                                         break;
  78                                 case UPPER:
  79                                         if (score < beta)
  80                                                 return beta - 1;
  81                                         break;
  82                                 default:
  83                                         assert(0);
  84                         }
  85                 }
  86         }
  87
  88         /* NULL move pruning */
  89         if (e.null_pruning && do_null && !check && (depth >= 2) && \
  90                         (MATERIAL_SCORE >= beta - 875) && \
  91                         !SCORE_IS_MATE(beta) && material_pieces[brd.wtm]) {
  92
  93                 int null_reduction = depth >= 5? 3 : 2;
  94
  95                 brd.cap_piece = 0;
  96                 brd.move = 0;                   /* NULL move */
  97
  98                 /* for takeback */
  99                 memcpy(&game_history.board[game_history.count++], &brd, \
 100                                 sizeof(struct board_t));
 101
 102                 if (brd.ep != -1)
 103                         brd.hash_key ^= hash_ep[_FILE(brd.ep)];
 104                 brd.hash_key ^= hash_side;
 105
 106                 brd.fifty_rule = 0;
 107                 brd.ep = -1;
 108                 brd.wtm ^= 1;
 109
 110                 /* search reduced depth */
 111                 if (depth - null_reduction - 1 > 0) {
 112                         score = -zwsearch(1 - beta, depth - null_reduction - 1, \
 113                                         ply + 1, 0, 0);
 114                         if (abort_search)
 115                                 return 65535;
 116                 } else {
 117                         score = -quiesce(-beta, 1 - beta, 0, ply + 1, 1);
 118                         if (abort_search)
 119                                 return 65535;
 120                 }
 121
 122                 takeback();
 123
 124                 if (score >= beta) {
 125 #ifdef STATISTIC_COUNTERS
 126                         counters.null_move_prunings++;
 127 #endif
 128                         return beta;
 129                 }
 130         }
 131
 132         /* extended futility pruning */
 133         if (e.futility_pruning && depth <= 5 && !check && !SCORE_IS_MATE(beta)) {
 134                 assert(depth > 0);
 135
 136                 if (MATERIAL_SCORE + futility_margins[depth] < beta)
 137                         futility_prune = TRUE;
 138         }
 139         moves_count = 0;
 140         gen_moves(&moves);
 141
 142         for (i = 0; i < moves.count; i++) {
 143                 /* get move with largest score */
 144                 sort_moves(&moves, i, ply);
 145                 if (!make_move(moves.move[i], FALSE))
 146                         continue;
 147
 148                 is_check = IS_CHECKED(brd.wtm);
 149
 150                 if (futility_prune && !is_check && moves_count && !MOVE_IS_TACTICAL(moves.move[i])) {
 151                         takeback();
 152 #ifdef STATISTIC_COUNTERS
 153                         counters.futility_prunings++;
 154 #endif
 155                         continue;
 156                 }
 157
 158                 moves_count++;
 159
 160                 /* examine if we can reduce or extend move */
 161                 extend = moves_count > NOLMR_MOVES? \
 162                         get_extensions(moves.move[i], check, is_check, depth, ply) : \
 163                         check;
 164                 if (extend < 0) {
 165                         extend = MIN(-MIN(depth - 2, (moves_count > 2)? 2 : 1), 0);
 166                 }
 167
 168                 score = -zwsearch(1 - beta, depth + extend - 1, ply + 1, is_check, 1);
 169                 if (abort_search)
 170                         return 65535;
 171
 172                 if (score >= beta && extend < 0) {
 173                         /* research with original depth */
 174                         score = -zwsearch(1 - beta, depth - 1, ply + 1, is_check, 1);
 175                         if (abort_search)
 176                                 return 65535;
 177                 }
 178
 179                 takeback();
 180
 181                         if (score >= beta) {
 182 #ifdef STATISTIC_COUNTERS
 183                                 counters.failed_high_total++;
 184                                 if (moves_count == 1)
 185                                         counters.failed_high_first++;
 186 #endif
 187                                 /* update history only for non tactical move */
 188                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 189                                         history_store(moves.move[i], depth, ply, beta);
 190                                 if (e.main_hash_enabled)
 191                                         /* save in hashtable */
 192                                         hashtable_put(brd.wtm, depth, ply, LOWER, moves.move[i],
 193                                                         beta);
 194
 195                                 return beta;
 196                         }
 197         }
 198         if (!moves_count)
 199                 beta = check? -MATE_VALUE + ply + 1 : 1;
 200
 201         if (e.main_hash_enabled)
 202                 /* save in hashtable */
 203                 hashtable_put(brd.wtm, depth, ply, UPPER, 0, beta - 1);
 204
 205         return beta - 1;
 206 }