a18c46923b60742160816fddb3d9c8ff2734dc35
[stockfish] / src / movepick.cpp
1 /*
2   Glaurung, a UCI chess playing engine.
3   Copyright (C) 2004-2008 Tord Romstad
4
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.
9   
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.
14   
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/>.
17 */
18
19
20 ////
21 //// Includes
22 ////
23
24 #include <cassert>
25
26 #include "history.h"
27 #include "movegen.h"
28 #include "movepick.h"
29 #include "search.h"
30 #include "value.h"
31
32
33 ////
34 //// Local definitions
35 ////
36
37 namespace {
38
39   /// Variables
40
41   int MainSearchPhaseIndex;
42   int EvasionsPhaseIndex;
43   int QsearchWithChecksPhaseIndex;
44   int QsearchWithoutChecksPhaseIndex;
45
46 }
47
48 // Static array definition
49 MovePicker::MovegenPhase MovePicker::PhaseTable[32];
50
51
52 ////
53 //// Functions
54 ////
55
56
57 /// Constructor for the MovePicker class.  Apart from the position for which
58 /// it is asked to pick legal moves, MovePicker also wants some information
59 /// to help it to return the presumably good moves first, to decide which
60 /// moves to return (in the quiescence search, for instance, we only want to
61 /// search captures, promotions and some checks) and about how important good
62 /// move ordering is at the current node.
63
64 MovePicker::MovePicker(Position &p, bool pvnode, Move ttm, Move mk,
65                        Move k1, Move k2, Depth dpth) {
66   pos = &p;
67   pvNode = pvnode;
68   ttMove = ttm;
69   mateKiller = (mk == ttm)? MOVE_NONE : mk;
70   killer1 = k1;
71   killer2 = k2;
72   depth = dpth;
73   movesPicked = 0;
74   numOfMoves = 0;
75   numOfBadCaptures = 0;
76   dc = p.discovered_check_candidates(p.side_to_move());
77
78   if(p.is_check())
79     phaseIndex = EvasionsPhaseIndex;
80   else if(depth > Depth(0))
81     phaseIndex = MainSearchPhaseIndex;
82   else if(depth == Depth(0))
83     phaseIndex = QsearchWithChecksPhaseIndex;
84   else
85     phaseIndex = QsearchWithoutChecksPhaseIndex;
86
87   pinned = p.pinned_pieces(p.side_to_move());
88
89   finished = false;
90 }
91
92
93 /// MovePicker::get_next_move() is the most important method of the MovePicker
94 /// class.  It returns a new legal move every time it is called, until there
95 /// are no more moves left of the types we are interested in.
96
97 Move MovePicker::get_next_move() {
98   Move move;
99
100   while(true) {
101     // If we already have a list of generated moves, pick the best move from
102     // the list, and return it:
103     move = this->pick_move_from_list();
104     if(move != MOVE_NONE) {
105       assert(move_is_ok(move));
106       return move;
107     }
108
109     // Next phase:
110     phaseIndex++;
111     switch(PhaseTable[phaseIndex]) {
112
113     case PH_TT_MOVE:
114       if(ttMove != MOVE_NONE) {
115         assert(move_is_ok(ttMove));
116         Move m = generate_move_if_legal(*pos, ttMove, pinned);
117         if(m != MOVE_NONE) {
118           assert(m == ttMove);
119           return m;
120         }
121       }
122       break;
123
124     case PH_MATE_KILLER:
125       if(mateKiller != MOVE_NONE) {
126         assert(move_is_ok(mateKiller));
127         Move m = generate_move_if_legal(*pos, mateKiller, pinned);
128         if(m != MOVE_NONE) {
129           assert(m == mateKiller);
130           return m;
131         }
132       }
133       break;
134
135     case PH_GOOD_CAPTURES:
136       // pinned = pos->pinned_pieces(pos->side_to_move());
137       numOfMoves = generate_captures(*pos, moves);
138       this->score_captures();
139       movesPicked = 0;
140       break;
141
142     case PH_BAD_CAPTURES:
143       badCapturesPicked = 0;
144       break;
145
146     case PH_NONCAPTURES:
147       numOfMoves = generate_noncaptures(*pos, moves);
148       this->score_noncaptures();
149       movesPicked = 0;
150       break;
151
152     case PH_EVASIONS:
153       assert(pos->is_check());
154       // pinned = pos->pinned_pieces(pos->side_to_move());
155       numOfMoves = generate_evasions(*pos, moves);
156       this->score_evasions();
157       movesPicked = 0;
158       break;
159
160     case PH_QCAPTURES:
161       // pinned = pos->pinned_pieces(pos->side_to_move());
162       numOfMoves = generate_captures(*pos, moves);
163       this->score_qcaptures();
164       movesPicked = 0;
165       break;
166
167     case PH_QCHECKS:
168       numOfMoves = generate_checks(*pos, moves, dc);
169       movesPicked = 0;
170       break;
171
172     case PH_STOP:
173       return MOVE_NONE;
174
175     default:
176       assert(false);
177       return MOVE_NONE;
178     }
179   }
180
181   assert(false);
182
183   return MOVE_NONE;
184 }
185
186
187 /// A variant of get_next_move() which takes a lock as a parameter, used to
188 /// prevent multiple threads from picking the same move at a split point.
189
190 Move MovePicker::get_next_move(Lock &lock) {
191    Move m;
192
193    lock_grab(&lock);
194    if(finished) {
195      lock_release(&lock);
196      return MOVE_NONE;
197    }
198    m = this->get_next_move();
199    if(m == MOVE_NONE)
200      finished = true;
201    lock_release(&lock);
202    
203    return m;
204 }
205
206  
207 /// MovePicker::number_of_moves() simply returns the numOfMoves member
208 /// variable.  It is intended to be used in positions where the side to move
209 /// is in check, for detecting checkmates or situations where there is only
210 /// a single reply to check.
211
212 int MovePicker::number_of_moves() const {
213   return numOfMoves;
214 }
215
216
217 /// MovePicker::score_captures(), MovePicker::score_noncaptures(),
218 /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
219 /// numerical move ordering score to each move in a move list.  The moves
220 /// with highest scores will be picked first by
221 /// MovePicker::pick_move_from_list().
222
223 void MovePicker::score_captures() {
224   // Winning and equal captures in the main search are ordered by MVV/LVA.
225   // Suprisingly, this appears to perform slightly better than SEE based
226   // move ordering.  The reason is probably that in a position with a winning
227   // capture, capturing a more valuable (but sufficiently defended) piece
228   // first usually doesn't hurt.  The opponent will have to recapture, and
229   // the hanging piece will still be hanging (except in the unusual cases
230   // where it is possible to recapture with the hanging piece).  Exchanging
231   // big pieces before capturing a hanging piece probably helps to reduce
232   // the subtree size.
233   for(int i = 0; i < numOfMoves; i++) {
234     int seeValue = pos->see(moves[i].move);
235     if(seeValue >= 0) {
236       if(move_promotion(moves[i].move))
237         moves[i].score = QueenValueMidgame;
238       else 
239         moves[i].score =
240           int(pos->midgame_value_of_piece_on(move_to(moves[i].move))) -
241           int(pos->type_of_piece_on(move_from(moves[i].move)));
242     }
243     else
244       moves[i].score = seeValue;
245         
246   }
247 }
248
249 void MovePicker::score_noncaptures() {
250   for(int i = 0; i < numOfMoves; i++) {
251     Move m = moves[i].move;
252     if(m == killer1)
253       moves[i].score = HistoryMax + 2;
254     else if(m == killer2)
255       moves[i].score = HistoryMax + 1;
256     else
257       moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m);
258   }
259 }
260
261 void MovePicker::score_evasions() {
262   for(int i = 0; i < numOfMoves; i++) {
263     Move m = moves[i].move;
264     if(m == ttMove)
265       moves[i].score = 2*HistoryMax;
266     else if(!pos->square_is_empty(move_to(m))) {
267       int seeScore = pos->see(m);
268       moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore;
269     }
270     else
271       moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m);
272   }
273 }
274
275 void MovePicker::score_qcaptures() {
276   // Use MVV/LVA ordering.
277   for(int i = 0; i < numOfMoves; i++) {
278     Move m = moves[i].move;
279     if(move_promotion(m))
280       moves[i].score = QueenValueMidgame;
281     else
282       moves[i].score =
283         int(pos->midgame_value_of_piece_on(move_to(m))) -
284         int(pos->midgame_value_of_piece_on(move_to(m))) / 64;
285   }
286 }
287
288
289 /// MovePicker::pick_move_from_list() picks the move with the biggest score
290 /// from a list of generated moves (moves[] or badCaptures[], depending on
291 /// the current move generation phase).  It takes care not to return the
292 /// transposition table move if that has already been serched previously.
293 /// While picking captures in the PH_GOOD_CAPTURES phase (i.e. while picking
294 /// non-losing captures in the main search), it moves all captures with
295 /// negative SEE values to the badCaptures[] array.
296
297 Move MovePicker::pick_move_from_list() {
298   int bestScore = -10000000;
299   int bestIndex;
300   Move move;
301
302   switch(PhaseTable[phaseIndex]) {
303
304   case PH_GOOD_CAPTURES:
305     assert(!pos->is_check());
306     assert(movesPicked >= 0);
307     while(movesPicked < numOfMoves) {
308       bestScore = -10000000;
309       bestIndex = -1;
310       for(int i = movesPicked; i < numOfMoves; i++) {
311         if(moves[i].score < 0) {
312           // Losing capture, move it to the badCaptures[] array
313           assert(numOfBadCaptures < 63);
314           badCaptures[numOfBadCaptures++] = moves[i];
315           moves[i--] = moves[--numOfMoves];
316         }
317         else if(moves[i].score > bestScore) {
318           bestIndex = i;
319           bestScore = moves[i].score;
320         }
321       }
322       if(bestIndex != -1) { // Found a good capture
323         move = moves[bestIndex].move;\r
324         moves[bestIndex] = moves[movesPicked++];
325         if(move != ttMove && move != mateKiller &&
326            pos->move_is_legal(move, pinned))
327           return move;
328       }
329     }
330     break;
331
332   case PH_NONCAPTURES:
333     assert(!pos->is_check());
334     assert(movesPicked >= 0);
335     while(movesPicked < numOfMoves) {
336       bestScore = -10000000;
337
338       // If this is a PV node or we have only picked a few moves, scan
339       // the entire move list for the best move.  If many moves have already
340       // been searched and it is not a PV node, we are probably failing low
341       // anyway, so we just pick the first move from the list.
342       if(pvNode || movesPicked < 12) {
343         bestIndex = -1;
344         for(int i = movesPicked; i < numOfMoves; i++)
345           if(moves[i].score > bestScore) {
346             bestIndex = i;
347             bestScore = moves[i].score;
348           }
349       }
350       else
351         bestIndex = movesPicked;
352
353       if(bestIndex != -1) {
354         move = moves[bestIndex].move;\r
355         moves[bestIndex] = moves[movesPicked++];
356         if(move != ttMove && move != mateKiller &&
357            pos->move_is_legal(move, pinned))
358           return move;
359       }
360     }
361     break;
362
363   case PH_EVASIONS:
364     assert(pos->is_check());
365     assert(movesPicked >= 0);
366     while(movesPicked < numOfMoves) {
367       bestScore = -10000000;
368       bestIndex = -1;
369       for(int i = movesPicked; i < numOfMoves; i++)
370         if(moves[i].score > bestScore) {
371           bestIndex = i;
372           bestScore = moves[i].score;
373         }
374
375       if(bestIndex != -1) {
376         move = moves[bestIndex].move;\r
377         moves[bestIndex] = moves[movesPicked++];
378         return move;
379       }
380     }
381     break;
382
383   case PH_BAD_CAPTURES:
384     assert(!pos->is_check());
385     assert(badCapturesPicked >= 0);
386     // It's probably a good idea to use SEE move ordering here, instead
387     // of just picking the first move.  FIXME
388     while(badCapturesPicked < numOfBadCaptures) {
389       move = badCaptures[badCapturesPicked++].move;
390       if(move != ttMove && move != mateKiller && 
391          pos->move_is_legal(move, pinned))
392         return move;
393     }
394     break;
395
396   case PH_QCAPTURES:
397     assert(!pos->is_check());
398     assert(movesPicked >= 0);
399     while(movesPicked < numOfMoves) {
400       bestScore = -10000000;
401       if(movesPicked < 4) {
402         bestIndex = -1;
403         for(int i = movesPicked; i < numOfMoves; i++)
404           if(moves[i].score > bestScore) {
405             bestIndex = i;
406             bestScore = moves[i].score;
407           }
408       }
409       else
410         bestIndex = movesPicked;
411
412       if(bestIndex != -1) {
413         move = moves[bestIndex].move;\r
414         moves[bestIndex] = moves[movesPicked++];
415         // Remember to change the line below if we decide to hash the qsearch!
416         // Maybe also postpone the legality check until after futility pruning?
417         if(/* move != ttMove && */ pos->move_is_legal(move, pinned))
418           return move;
419       }
420     }
421     break;
422
423   case PH_QCHECKS:
424     assert(!pos->is_check());
425     assert(movesPicked >= 0);
426     // Perhaps we should do something better than just picking the first
427     // move here?  FIXME
428     while(movesPicked < numOfMoves) {
429       move = moves[movesPicked++].move;
430       // Remember to change the line below if we decide to hash the qsearch!
431       if(/* move != ttMove && */ pos->move_is_legal(move, pinned))
432         return move;
433     }
434     break;
435
436   default:
437     break;
438   }
439
440   return MOVE_NONE;
441 }
442
443
444 /// MovePicker::init_phase_table() initializes the PhaseTable[],
445 /// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex
446 /// and QsearchWithoutChecksPhaseIndex variables.  It is only called once
447 /// during program startup, and never again while the program is running.
448
449 void MovePicker::init_phase_table() {
450   int i = 0;
451
452   // Main search
453   MainSearchPhaseIndex = i - 1;
454   PhaseTable[i++] = PH_TT_MOVE;
455   PhaseTable[i++] = PH_MATE_KILLER;
456   PhaseTable[i++] = PH_GOOD_CAPTURES;
457   // PH_KILLER_1 and PH_KILLER_2 are not yet used.
458   // PhaseTable[i++] = PH_KILLER_1;
459   // PhaseTable[i++] = PH_KILLER_2;
460   PhaseTable[i++] = PH_NONCAPTURES;
461   PhaseTable[i++] = PH_BAD_CAPTURES;
462   PhaseTable[i++] = PH_STOP;
463
464   // Check evasions
465   EvasionsPhaseIndex = i - 1;
466   PhaseTable[i++] = PH_EVASIONS;
467   PhaseTable[i++] = PH_STOP;
468
469   // Quiescence search with checks
470   QsearchWithChecksPhaseIndex = i - 1;
471   PhaseTable[i++] = PH_QCAPTURES;
472   PhaseTable[i++] = PH_QCHECKS;
473   PhaseTable[i++] = PH_STOP;
474
475   // Quiescence search without checks
476   QsearchWithoutChecksPhaseIndex = i - 1;
477   PhaseTable[i++] = PH_QCAPTURES;
478   PhaseTable[i++] = PH_STOP;
479 }