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