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
  74                         score = -zwsearch(-alpha, depth + extend - 1, 1, is_check);
  75                         if (abort_search)
  76                                 return 65535;
  77
  78                         if (score > alpha && extend < 0) {
  79                                 score = -zwsearch(-alpha, depth - 1, 1, is_check);
  80                                 if (abort_search)
  81                                         return 65535;
  82                         }
  83
  84                         if (score > alpha && score < beta) {
  85                                 fail_high_root = TRUE;
  86                                 score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  87                                 if (abort_search)
  88                                         return 65535;
  89                         }
  90                 }
  91
  92                 takeback();
  93
  94                 searching_pv = FALSE;
  95
  96                 if (score > alpha) {
  97                         if (score >= beta) {
  98 #ifdef STATISTIC_COUNTERS
  99                                 counters.failed_high_total++;
 100                                 if (moves_count == 1)
 101                                         counters.failed_high_first++;
 102 #endif
 103                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 104                                         history_store(moves.move[i], depth, 0, beta);
 105
 106                                 return beta;
 107                         }
 108                         alpha = score;
 109                         pv[0][0] = moves.move[i];
 110
 111                         for (j = 1; j < pv_length[1]; j++)
 112                                 pv[0][j] = pv[1][j];
 113                         pv_length[0] = pv_length[1];
 114                 }
 115         }
 116
 117         if (!moves_count && !check)
 118                 return 0;
 119
 120         return alpha;
 121 }