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 best_score;
  34         int searching_pv;
  35         struct moves_t moves;
  36
  37         assert(alpha >= -MATE_VALUE && alpha < +MATE_VALUE);
  38         assert(beta > alpha && beta <= +MATE_VALUE);
  39         assert(depth >= 0 && depth <= MAX_PLY);
  40         assert(board_is_legal(&brd));
  41
  42         moves_count = 0;
  43         best_score = -MATE_VALUE;
  44         searching_pv = TRUE;
  45
  46         if (reps() >= 3)
  47                 return 0;
  48
  49         pv_length[0] = 0;
  50         hash_moves[0] = pv[0][0];
  51
  52         gen_moves(&moves);
  53
  54         for (i = 0; i < moves.count; i++) {
  55                 /* get move with largest score */
  56                 sort_moves(&moves, i, 0);
  57
  58                 if (!make_move(moves.move[i], FALSE))
  59                         continue;
  60
  61                 counters.searched_nodes++;
  62                 moves_count++;
  63
  64                 is_check = IS_CHECKED(brd.wtm);
  65
  66                 if (searching_pv) {
  67                         score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  68                         if (abort_search)
  69                                 return 65535;
  70                 } else {
  71                         /* examine if we can reduce or extend move */
  72                         extend = moves_count > NOLMR_MOVES? \
  73                                 get_extensions(moves.move[i], check, is_check, depth, 0) : \
  74                                 check;
  75
  76                         score = -zwsearch(-alpha, depth + extend - 1, 1, is_check);
  77                         if (abort_search)
  78                                 return 65535;
  79
  80                         if (score > alpha && extend < 0) {
  81                                 score = -zwsearch(-alpha, depth - 1, 1, is_check);
  82                                 if (abort_search)
  83                                         return 65535;
  84                         }
  85
  86                         if (score > alpha && score < beta) {
  87                                 score = -search_pv(-beta, -alpha, depth + check - 1, 1, is_check);
  88                                 if (abort_search)
  89                                         return 65535;
  90                         }
  91                 }
  92
  93                 takeback();
  94
  95                 if (score > best_score) {
  96                         searching_pv = FALSE;
  97                         best_score = score;
  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, best_score);
 108
 109                                         return best_score;
 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
 121         if (!moves_count && !check)
 122                 return 0;
 123
 124         return best_score;
 125 }