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
  61                 is_check = IS_CHECKED(brd.wtm);
  62
  63                 if (searching_pv) {
  64                         score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  65                         if (abort_search)
  66                                 return 65535;
  67                 } else {
  68                         /* examine if we can reduce or extend move */
  69                         extend = moves_count > NOLMR_MOVES? \
  70                                          get_extensions(moves.move[i], check, is_check, depth, 0) : \
  71                                          check;
  72
  73                         score = -zwsearch(-alpha, depth + extend - 1, 1, is_check);
  74                         if (abort_search)
  75                                 return 65535;
  76
  77                         if (score > alpha && extend < 0) {
  78                                 score = -zwsearch(-alpha, depth - 1, 1, is_check);
  79                                 if (abort_search)
  80                                         return 65535;
  81                         }
  82
  83                         if (score > alpha && score < beta) {
  84                                 score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  85                                 if (abort_search)
  86                                         return 65535;
  87                         }
  88                 }
  89
  90                 takeback();
  91
  92                 searching_pv = FALSE;
  93
  94                 if (score > alpha) {
  95                         if (score >= beta) {
  96 #ifdef STATISTIC_COUNTERS
  97                                 counters.failed_high_total++;
  98                                 if (moves_count == 1)
  99                                         counters.failed_high_first++;
 100 #endif
 101                                 if (!MOVE_IS_TACTICAL(moves.move[i]))
 102                                         history_store(moves.move[i], depth, 0, beta);
 103
 104                                 return beta;
 105                         }
 106                         alpha = score;
 107                         pv[0][0] = moves.move[i];
 108
 109                         for (j = 1; j < pv_length[1]; j++)
 110                                 pv[0][j] = pv[1][j];
 111                         pv_length[0] = pv_length[1];
 112                 }
 113         }
 114
 115         if (!moves_count && !check)
 116                 return 0;
 117
 118         return alpha;
 119 }