search_root.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 <assert.h>
  17 #include <stdio.h>
  18 #include "common.h"
  19 #include "attacks.h"
  20 #include "board.h"
  21 #include "engine.h"
  22 #include "move.h"
  23 #include "search.h"
  24
  25 int
  26 search_root(int alpha, int beta, int depth, int check)
  27 {
  28         int i, j;
  29         int extend;
  30         int score;
  31         int is_check;
  32         int moves_count;
  33         int searching_pv;
  34         struct moves_t moves;
  35
  36         assert(alpha >= -MATE_VALUE && alpha < +MATE_VALUE);
  37         assert(beta > alpha && beta <= +MATE_VALUE);
  38         assert(depth >= 0 && depth <= MAX_PLY);
  39         assert(board_is_legal(&brd));
  40
  41         moves_count = 0;
  42         searching_pv = TRUE;
  43
  44         if (reps() >= 3)
  45                 return 0;
  46
  47         pv_length[0] = 0;
  48         hash_moves[0] = pv[0][0];
  49
  50         gen_moves(&moves);
  51
  52         for (i = 0; i < moves.count; i++) {
  53                 /* get move with largest score */
  54                 sort_moves(&moves, i, 0);
  55
  56                 if (!make_move(moves.move[i], FALSE))
  57                         continue;
  58
  59                 moves_count++;
  60                 fail_high_root = FALSE;
  61
  62                 is_check = IS_CHECKED(brd.wtm);
  63
  64                 if (searching_pv) {
  65                         score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  66                         if (abort_search)
  67                                 return 65535;
  68                 } else {
  69                         /* examine if we can reduce or extend move */
  70                         extend = moves_count > NOLMR_MOVES? \
  71                                          get_extensions(moves.move[i], check, is_check, depth, 0) : \
  72                                          check;
  73                         if (extend < 0) {
  74                                 extend = MIN(-MIN(depth - 2, (moves_count > 2)? 2 : 1), 0);
  75                         }
  76
  77                         score = -zwsearch(-alpha, depth + extend - 1, 1, is_check, 1);
  78                         if (abort_search)
  79                                 return 65535;
  80
  81                         if (score > alpha && extend < 0) {
  82                                 score = -zwsearch(-alpha, depth - 1, 1, is_check, 1);
  83                                 if (abort_search)
  84                                         return 65535;
  85                         }
  86
  87                         if (score > alpha && score < beta) {
  88                                 fail_high_root = TRUE;
  89                                 score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  90                                 if (abort_search)
  91                                         return 65535;
  92                         }
  93                 }
  94
  95                 takeback();
  96
  97                 searching_pv = FALSE;
  98
  99                 if (score > alpha) {
 100                         if (score >= beta) {
 101 #ifdef STATISTIC_COUNTERS
 102                                 counters.failed_high_total++;
 103                                 if (moves_count == 1)
 104                                         counters.failed_high_first++;
 105 #endif
 106                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 107                                         history_store(moves.move[i], depth, 0, beta);
 108
 109                                 return beta;
 110                         }
 111                         alpha = score;
 112                         pv[0][0] = moves.move[i];
 113
 114                         for (j = 1; j < pv_length[1]; j++)
 115                                 pv[0][j] = pv[1][j];
 116                         pv_length[0] = pv_length[1];
 117                 }
 118         }
 119
 120         if (!moves_count && !check)
 121                 return 0;
 122
 123         return alpha;
 124 }