2 Glaurung, a UCI chess playing engine.
3 Copyright (C) 2004-2008 Tord Romstad
5 Glaurung is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
10 Glaurung is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
34 //// Local definitions
42 PH_TT_MOVE
, // Transposition table move
43 PH_MATE_KILLER
, // Mate killer from the current ply
44 PH_GOOD_CAPTURES
, // Queen promotions and captures with SEE values >= 0
45 PH_BAD_CAPTURES
, // Queen promotions and captures with SEE valuse <= 0
46 PH_KILLER_1
, // Killer move 1 from the current ply (not used yet).
47 PH_KILLER_2
, // Killer move 2 from the current ply (not used yet).
48 PH_NONCAPTURES
, // Non-captures and underpromotions
49 PH_EVASIONS
, // Check evasions
50 PH_QCAPTURES
, // Captures in quiescence search
51 PH_QCHECKS
, // Checks in quiescence search
58 MovegenPhase PhaseTable
[32];
59 int MainSearchPhaseIndex
;
60 int EvasionsPhaseIndex
;
61 int QsearchWithChecksPhaseIndex
;
62 int QsearchWithoutChecksPhaseIndex
;
72 /// Constructor for the MovePicker class. Apart from the position for which
73 /// it is asked to pick legal moves, MovePicker also wants some information
74 /// to help it to return the presumably good moves first, to decide which
75 /// moves to return (in the quiescence search, for instance, we only want to
76 /// search captures, promotions and some checks) and about how important good
77 /// move ordering is at the current node.
79 MovePicker::MovePicker(Position
&p
, bool pvnode
, Move ttm
, Move mk
,
80 Move k1
, Move k2
, Depth dpth
) {
84 mateKiller
= (mk
== ttm
)? MOVE_NONE
: mk
;
91 dc
= p
.discovered_check_candidates(p
.side_to_move());
94 phaseIndex
= EvasionsPhaseIndex
;
95 else if(depth
> Depth(0))
96 phaseIndex
= MainSearchPhaseIndex
;
97 else if(depth
== Depth(0))
98 phaseIndex
= QsearchWithChecksPhaseIndex
;
100 phaseIndex
= QsearchWithoutChecksPhaseIndex
;
102 pinned
= p
.pinned_pieces(p
.side_to_move());
108 /// MovePicker::get_next_move() is the most important method of the MovePicker
109 /// class. It returns a new legal move every time it is called, until there
110 /// are no more moves left of the types we are interested in.
112 Move
MovePicker::get_next_move() {
116 // If we already have a list of generated moves, pick the best move from
117 // the list, and return it:
118 move
= this->pick_move_from_list();
119 if(move
!= MOVE_NONE
) {
120 assert(move_is_ok(move
));
126 switch(PhaseTable
[phaseIndex
]) {
129 if(ttMove
!= MOVE_NONE
) {
130 assert(move_is_ok(ttMove
));
131 Move m
= generate_move_if_legal(*pos
, ttMove
, pinned
);
140 if(mateKiller
!= MOVE_NONE
) {
141 assert(move_is_ok(mateKiller
));
142 Move m
= generate_move_if_legal(*pos
, mateKiller
, pinned
);
144 assert(m
== mateKiller
);
150 case PH_GOOD_CAPTURES
:
151 // pinned = pos->pinned_pieces(pos->side_to_move());
152 numOfMoves
= generate_captures(*pos
, moves
);
153 this->score_captures();
157 case PH_BAD_CAPTURES
:
158 badCapturesPicked
= 0;
162 numOfMoves
= generate_noncaptures(*pos
, moves
);
163 this->score_noncaptures();
168 assert(pos
->is_check());
169 // pinned = pos->pinned_pieces(pos->side_to_move());
170 numOfMoves
= generate_evasions(*pos
, moves
);
171 this->score_evasions();
176 // pinned = pos->pinned_pieces(pos->side_to_move());
177 numOfMoves
= generate_captures(*pos
, moves
);
178 this->score_qcaptures();
183 numOfMoves
= generate_checks(*pos
, moves
, dc
);
202 /// A variant of get_next_move() which takes a lock as a parameter, used to
203 /// prevent multiple threads from picking the same move at a split point.
205 Move
MovePicker::get_next_move(Lock
&lock
) {
213 m
= this->get_next_move();
222 /// MovePicker::number_of_moves() simply returns the numOfMoves member
223 /// variable. It is intended to be used in positions where the side to move
224 /// is in check, for detecting checkmates or situations where there is only
225 /// a single reply to check.
227 int MovePicker::number_of_moves() const {
232 /// MovePicker::score_captures(), MovePicker::score_noncaptures(),
233 /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
234 /// numerical move ordering score to each move in a move list. The moves
235 /// with highest scores will be picked first by
236 /// MovePicker::pick_move_from_list().
238 void MovePicker::score_captures() {
239 // Winning and equal captures in the main search are ordered by MVV/LVA.
240 // Suprisingly, this appears to perform slightly better than SEE based
241 // move ordering. The reason is probably that in a position with a winning
242 // capture, capturing a more valuable (but sufficiently defended) piece
243 // first usually doesn't hurt. The opponent will have to recapture, and
244 // the hanging piece will still be hanging (except in the unusual cases
245 // where it is possible to recapture with the hanging piece). Exchanging
246 // big pieces before capturing a hanging piece probably helps to reduce
248 for(int i
= 0; i
< numOfMoves
; i
++) {
249 int seeValue
= pos
->see(moves
[i
].move
);
251 if(move_promotion(moves
[i
].move
))
252 moves
[i
].score
= QueenValueMidgame
;
255 int(pos
->midgame_value_of_piece_on(move_to(moves
[i
].move
))) -
256 int(pos
->type_of_piece_on(move_from(moves
[i
].move
)));
259 moves
[i
].score
= seeValue
;
264 void MovePicker::score_noncaptures() {
265 for(int i
= 0; i
< numOfMoves
; i
++) {
266 Move m
= moves
[i
].move
;
268 moves
[i
].score
= HistoryMax
+ 2;
269 else if(m
== killer2
)
270 moves
[i
].score
= HistoryMax
+ 1;
272 moves
[i
].score
= H
.move_ordering_score(pos
->piece_on(move_from(m
)), m
);
276 void MovePicker::score_evasions() {
277 for(int i
= 0; i
< numOfMoves
; i
++) {
278 Move m
= moves
[i
].move
;
280 moves
[i
].score
= 2*HistoryMax
;
281 else if(!pos
->square_is_empty(move_to(m
))) {
282 int seeScore
= pos
->see(m
);
283 moves
[i
].score
= (seeScore
>= 0)? seeScore
+ HistoryMax
: seeScore
;
286 moves
[i
].score
= H
.move_ordering_score(pos
->piece_on(move_from(m
)), m
);
290 void MovePicker::score_qcaptures() {
291 // Use MVV/LVA ordering.
292 for(int i
= 0; i
< numOfMoves
; i
++) {
293 Move m
= moves
[i
].move
;
294 if(move_promotion(m
))
295 moves
[i
].score
= QueenValueMidgame
;
298 int(pos
->midgame_value_of_piece_on(move_to(m
))) -
299 int(pos
->midgame_value_of_piece_on(move_to(m
))) / 64;
304 /// MovePicker::pick_move_from_list() picks the move with the biggest score
305 /// from a list of generated moves (moves[] or badCaptures[], depending on
306 /// the current move generation phase). It takes care not to return the
307 /// transposition table move if that has already been serched previously.
308 /// While picking captures in the PH_GOOD_CAPTURES phase (i.e. while picking
309 /// non-losing captures in the main search), it moves all captures with
310 /// negative SEE values to the badCaptures[] array.
312 Move
MovePicker::pick_move_from_list() {
313 int bestScore
= -10000000;
317 switch(PhaseTable
[phaseIndex
]) {
319 case PH_GOOD_CAPTURES
:
320 assert(!pos
->is_check());
321 assert(movesPicked
>= 0);
322 while(movesPicked
< numOfMoves
) {
323 bestScore
= -10000000;
325 for(int i
= movesPicked
; i
< numOfMoves
; i
++) {
326 if(moves
[i
].score
< 0) {
327 // Losing capture, move it to the badCaptures[] array
328 assert(numOfBadCaptures
< 63);
329 badCaptures
[numOfBadCaptures
++] = moves
[i
];
330 moves
[i
--] = moves
[--numOfMoves
];
332 else if(moves
[i
].score
> bestScore
) {
334 bestScore
= moves
[i
].score
;
337 if(bestIndex
!= -1) { // Found a good capture
338 move
= moves
[bestIndex
].move
;
339 moves
[bestIndex
] = moves
[movesPicked
++];
340 if(move
!= ttMove
&& move
!= mateKiller
&&
341 pos
->move_is_legal(move
, pinned
))
348 assert(!pos
->is_check());
349 assert(movesPicked
>= 0);
350 while(movesPicked
< numOfMoves
) {
351 bestScore
= -10000000;
353 // If this is a PV node or we have only picked a few moves, scan
354 // the entire move list for the best move. If many moves have already
355 // been searched and it is not a PV node, we are probably failing low
356 // anyway, so we just pick the first move from the list.
357 if(pvNode
|| movesPicked
< 12) {
359 for(int i
= movesPicked
; i
< numOfMoves
; i
++)
360 if(moves
[i
].score
> bestScore
) {
362 bestScore
= moves
[i
].score
;
366 bestIndex
= movesPicked
;
368 if(bestIndex
!= -1) {
369 move
= moves
[bestIndex
].move
;
370 moves
[bestIndex
] = moves
[movesPicked
++];
371 if(move
!= ttMove
&& move
!= mateKiller
&&
372 pos
->move_is_legal(move
, pinned
))
379 assert(pos
->is_check());
380 assert(movesPicked
>= 0);
381 while(movesPicked
< numOfMoves
) {
382 bestScore
= -10000000;
384 for(int i
= movesPicked
; i
< numOfMoves
; i
++)
385 if(moves
[i
].score
> bestScore
) {
387 bestScore
= moves
[i
].score
;
390 if(bestIndex
!= -1) {
391 move
= moves
[bestIndex
].move
;
392 moves
[bestIndex
] = moves
[movesPicked
++];
398 case PH_BAD_CAPTURES
:
399 assert(!pos
->is_check());
400 assert(badCapturesPicked
>= 0);
401 // It's probably a good idea to use SEE move ordering here, instead
402 // of just picking the first move. FIXME
403 while(badCapturesPicked
< numOfBadCaptures
) {
404 move
= badCaptures
[badCapturesPicked
++].move
;
405 if(move
!= ttMove
&& move
!= mateKiller
&&
406 pos
->move_is_legal(move
, pinned
))
412 assert(!pos
->is_check());
413 assert(movesPicked
>= 0);
414 while(movesPicked
< numOfMoves
) {
415 bestScore
= -10000000;
416 if(movesPicked
< 4) {
418 for(int i
= movesPicked
; i
< numOfMoves
; i
++)
419 if(moves
[i
].score
> bestScore
) {
421 bestScore
= moves
[i
].score
;
425 bestIndex
= movesPicked
;
427 if(bestIndex
!= -1) {
428 move
= moves
[bestIndex
].move
;
429 moves
[bestIndex
] = moves
[movesPicked
++];
430 // Remember to change the line below if we decide to hash the qsearch!
431 // Maybe also postpone the legality check until after futility pruning?
432 if(/* move != ttMove && */ pos
->move_is_legal(move
, pinned
))
439 assert(!pos
->is_check());
440 assert(movesPicked
>= 0);
441 // Perhaps we should do something better than just picking the first
443 while(movesPicked
< numOfMoves
) {
444 move
= moves
[movesPicked
++].move
;
445 // Remember to change the line below if we decide to hash the qsearch!
446 if(/* move != ttMove && */ pos
->move_is_legal(move
, pinned
))
459 /// MovePicker::init_phase_table() initializes the PhaseTable[],
460 /// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex
461 /// and QsearchWithoutChecksPhaseIndex variables. It is only called once
462 /// during program startup, and never again while the program is running.
464 void MovePicker::init_phase_table() {
468 MainSearchPhaseIndex
= i
- 1;
469 PhaseTable
[i
++] = PH_TT_MOVE
;
470 PhaseTable
[i
++] = PH_MATE_KILLER
;
471 PhaseTable
[i
++] = PH_GOOD_CAPTURES
;
472 // PH_KILLER_1 and PH_KILLER_2 are not yet used.
473 // PhaseTable[i++] = PH_KILLER_1;
474 // PhaseTable[i++] = PH_KILLER_2;
475 PhaseTable
[i
++] = PH_NONCAPTURES
;
476 PhaseTable
[i
++] = PH_BAD_CAPTURES
;
477 PhaseTable
[i
++] = PH_STOP
;
480 EvasionsPhaseIndex
= i
- 1;
481 PhaseTable
[i
++] = PH_EVASIONS
;
482 PhaseTable
[i
++] = PH_STOP
;
484 // Quiescence search with checks
485 QsearchWithChecksPhaseIndex
= i
- 1;
486 PhaseTable
[i
++] = PH_QCAPTURES
;
487 PhaseTable
[i
++] = PH_QCHECKS
;
488 PhaseTable
[i
++] = PH_STOP
;
490 // Quiescence search without checks
491 QsearchWithoutChecksPhaseIndex
= i
- 1;
492 PhaseTable
[i
++] = PH_QCAPTURES
;
493 PhaseTable
[i
++] = PH_STOP
;