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.
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.
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.
25 /* forward declarations of functions */
26 static int zwsearch_nonull(int beta
, int depth
, int ply
);
28 /* zero window search */
30 zwsearch(int beta
, int depth
, int ply
, int check
)
41 int best_score
= -MATE_VALUE
;
43 assert(beta
> -MATE_VALUE
&& beta
<= +MATE_VALUE
);
44 assert(depth
>= 0 && depth
<= MAX_PLY
);
45 assert(board_is_legal(&brd
));
50 if (reps() || evaluate_draw())
53 /* if we are too deep */
54 if (ply
>= MAX_PLY
- 1)
55 return evaluate(beta
- 1, beta
);
57 /* search for captures */
58 if (depth
<= 0 && !check
)
59 return quiesce(beta
- 1, beta
, 0, ply
, 0);
62 futility_prune
= FALSE
;
66 /* check transposition table */
67 if (e
.main_hash_enabled
) {
68 i
= hashtable_get(brd
.wtm
, depth
, ply
, &hash_moves
[ply
], &score
);
70 #ifdef STATISTIC_COUNTERS
71 counters
.transposition
++;
91 /* limited razoring at pre pre frontier */
92 if (e
.razoring
&& depth
== 3 && !check
&& (MATERIAL_SCORE
+ 875) < beta
) {
93 #ifdef STATISTIC_COUNTERS
99 /* futility pruning according to Ernst A. Heinz */
100 if (e
.futility_pruning
&& depth
< 3 && !check
) {
105 score
= evaluate(beta
- 1, beta
) + 475;
107 futility_max
= score
;
108 futility_prune
= TRUE
;
112 score
= evaluate(beta
- 1, beta
) + 175;
114 futility_max
= score
;
115 futility_prune
= TRUE
;
120 /* NULL move pruning */
121 if (e
.null_pruning
&& do_null
&& !check
&& (depth
>= 2) && \
122 (MATERIAL_SCORE
>= beta
- 875) && \
123 !SCORE_IS_MATE(beta
) && (popcount(r_pieces
[brd
.wtm
]) > 3)) {
124 int null_reduction
= 3; /* R = 3 */
127 brd
.move
= 0; /* NULL move */
130 memcpy(&game_history
.board
[game_history
.count
++], &brd
, \
131 sizeof(struct board_t
));
134 brd
.hash_key
^= hash_ep
[_FILE(brd
.ep
)];
135 brd
.hash_key
^= hash_side
;
141 /* search reduced depth */
142 if (depth
- null_reduction
- 1 > 0) {
143 score
= -zwsearch_nonull(1 - beta
, depth
- null_reduction
- 1, \
148 score
= -quiesce(-beta
, 1 - beta
, 0, ply
+ 1, 1);
156 #ifdef STATISTIC_COUNTERS
157 counters
.null_move_prunings
++;
166 for (i
= 0; i
< moves
.count
; i
++) {
167 /* get move with largest score */
168 sort_moves(&moves
, i
, ply
);
169 if (!make_move(moves
.move
[i
], FALSE
))
172 is_check
= IS_CHECKED(brd
.wtm
);
174 if (futility_prune
&& !is_check
&& moves_count
&& !MOVE_IS_TACTICAL(moves
.move
[i
])) {
175 best_score
= MAX(best_score
, futility_max
);
177 #ifdef STATISTIC_COUNTERS
178 counters
.futility_prunings
++;
183 counters
.searched_nodes
++;
186 /* examine if we can reduce or extend move */
187 extend
= moves_count
> NOLMR_MOVES
? \
188 get_extensions(moves
.move
[i
], check
, is_check
, depth
, ply
) : \
191 score
= -zwsearch(1 - beta
, depth
+ extend
- 1, ply
+ 1, is_check
);
195 if (score
>= beta
&& extend
< 0) {
196 /* research with original depth */
197 score
= -zwsearch(1 - beta
, depth
- 1, ply
+ 1, is_check
);
204 if (score
> best_score
) {
207 #ifdef STATISTIC_COUNTERS
208 counters
.failed_high_total
++;
209 if (moves_count
== 1)
210 counters
.failed_high_first
++;
212 /* update history only for non tactical move */
213 if (!MOVE_IS_TACTICAL(moves
.move
[i
]))
214 history_store(moves
.move
[i
], depth
, ply
, best_score
);
215 if (e
.main_hash_enabled
)
216 /* save in hashtable */
217 hashtable_put(brd
.wtm
, depth
, ply
, LOWER
, moves
.move
[i
], best_score
);
224 best_score
= check
? -MATE_VALUE
+ ply
: 0;
226 if (e
.main_hash_enabled
)
227 /* save in hashtable */
228 hashtable_put(brd
.wtm
, depth
, ply
, UPPER
, 0, best_score
);
230 assert(best_score
> -MATE_VALUE
);
234 /* zero window search with some restrictions */
236 zwsearch_nonull(int beta
, int depth
, int ply
)
242 struct moves_t moves
;
243 int best_score
= -MATE_VALUE
;
245 assert(beta
> -MATE_VALUE
&& beta
<= +MATE_VALUE
);
246 assert(depth
>= 1 && depth
<= MAX_PLY
);
247 assert(!IS_CHECKED(brd
.wtm
));
248 assert(board_is_legal(&brd
));
257 for (i
= 0; i
< moves
.count
; i
++) {
258 /* get move with largest score */
259 sort_moves(&moves
, i
, ply
);
260 if (!make_move(moves
.move
[i
], FALSE
))
263 counters
.searched_nodes
++;
266 is_check
= IS_CHECKED(brd
.wtm
);
267 score
= -zwsearch(1 - beta
, depth
- 1, ply
+ 1, is_check
);
273 if (score
> best_score
) {
276 #ifdef STATISTIC_COUNTERS
277 counters
.failed_high_total
++;
278 if (moves_count
== 1)
279 counters
.failed_high_first
++;
288 /* FIXME: what should I return? */
291 assert(best_score
> -MATE_VALUE
);