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 we are too deep */
51 if (ply
>= MAX_PLY
- 1)
52 return evaluate(beta
- 1, beta
);
54 /* search for captures */
55 if (depth
<= 0 && !check
)
56 return quiesce(beta
- 1, beta
, 0, ply
, 0);
59 futility_prune
= FALSE
;
63 /* check transposition table */
64 if (e
.main_hash_enabled
) {
65 i
= hashtable_get(brd
.wtm
, depth
, ply
, &hash_moves
[ply
], &score
);
67 #ifdef STATISTIC_COUNTERS
68 counters
.transposition
++;
88 /* limited razoring at pre pre frontier */
89 if (e
.razoring
&& depth
== 3 && !check
&& (MATERIAL_SCORE
+ 875) < beta
) {
90 #ifdef STATISTIC_COUNTERS
96 /* futility pruning according to Ernst A. Heinz */
97 if (e
.futility_pruning
&& depth
< 3 && !check
) {
102 score
= evaluate(beta
- 1, beta
) + 475;
104 futility_max
= score
;
105 futility_prune
= TRUE
;
109 score
= evaluate(beta
- 1, beta
) + 175;
111 futility_max
= score
;
112 futility_prune
= TRUE
;
117 /* NULL move pruning */
118 if (e
.null_pruning
&& do_null
&& !check
&& (depth
>= 2) && \
119 (MATERIAL_SCORE
>= beta
- 875) && \
120 !SCORE_IS_MATE(beta
) && (popcount(r_pieces
[brd
.wtm
]) > 3)) {
121 int null_reduction
= 3; /* R = 3 */
124 brd
.move
= 0; /* NULL move */
127 memcpy(&game_history
.board
[game_history
.count
++], &brd
, \
128 sizeof(struct board_t
));
131 brd
.hash_key
^= hash_ep
[_FILE(brd
.ep
)];
132 brd
.hash_key
^= hash_side
;
138 /* search reduced depth */
139 if (depth
- null_reduction
- 1 > 0) {
140 score
= -zwsearch_nonull(1 - beta
, depth
- null_reduction
- 1, \
145 score
= -quiesce(-beta
, 1 - beta
, 0, ply
+ 1, 1);
153 #ifdef STATISTIC_COUNTERS
154 counters
.null_move_prunings
++;
163 for (i
= 0; i
< moves
.count
; i
++) {
164 /* get move with largest score */
165 sort_moves(&moves
, i
, ply
);
166 if (!make_move(moves
.move
[i
], FALSE
))
169 is_check
= IS_CHECKED(brd
.wtm
);
171 if (futility_prune
&& !is_check
&& moves_count
&& !MOVE_IS_TACTICAL(moves
.move
[i
])) {
172 best_score
= MAX(best_score
, futility_max
);
174 #ifdef STATISTIC_COUNTERS
175 counters
.futility_prunings
++;
180 counters
.searched_nodes
++;
183 /* examine if we can reduce or extend move */
184 extend
= moves_count
> NOLMR_MOVES
? \
185 get_extensions(moves
.move
[i
], check
, is_check
, depth
, ply
) : \
188 score
= -zwsearch(1 - beta
, depth
+ extend
- 1, ply
+ 1, is_check
);
192 if (score
>= beta
&& extend
< 0) {
193 /* research with original depth */
194 score
= -zwsearch(1 - beta
, depth
- 1, ply
+ 1, is_check
);
201 if (score
> best_score
) {
204 #ifdef STATISTIC_COUNTERS
205 counters
.failed_high_total
++;
206 if (moves_count
== 1)
207 counters
.failed_high_first
++;
209 /* update history only for non tactical move */
210 if (!MOVE_IS_TACTICAL(moves
.move
[i
]))
211 history_store(moves
.move
[i
], depth
, ply
, best_score
);
212 if (e
.main_hash_enabled
)
213 /* save in hashtable */
214 hashtable_put(brd
.wtm
, depth
, ply
, LOWER
, moves
.move
[i
], best_score
);
221 best_score
= check
? -MATE_VALUE
+ ply
: 0;
223 if (e
.main_hash_enabled
)
224 /* save in hashtable */
225 hashtable_put(brd
.wtm
, depth
, ply
, UPPER
, 0, best_score
);
227 assert(best_score
> -MATE_VALUE
);
231 /* zero window search with some restrictions */
233 zwsearch_nonull(int beta
, int depth
, int ply
)
239 struct moves_t moves
;
240 int best_score
= -MATE_VALUE
;
242 assert(beta
> -MATE_VALUE
&& beta
<= +MATE_VALUE
);
243 assert(depth
>= 1 && depth
<= MAX_PLY
);
244 assert(!IS_CHECKED(brd
.wtm
));
245 assert(board_is_legal(&brd
));
254 for (i
= 0; i
< moves
.count
; i
++) {
255 /* get move with largest score */
256 sort_moves(&moves
, i
, ply
);
257 if (!make_move(moves
.move
[i
], FALSE
))
260 counters
.searched_nodes
++;
263 is_check
= IS_CHECKED(brd
.wtm
);
264 score
= -zwsearch(1 - beta
, depth
- 1, ply
+ 1, is_check
);
270 if (score
> best_score
) {
273 #ifdef STATISTIC_COUNTERS
274 counters
.failed_high_total
++;
275 if (moves_count
== 1)
276 counters
.failed_high_first
++;
285 /* FIXME: what should I return? */
288 assert(best_score
> -MATE_VALUE
);