All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
moveGenerator.cc
Go to the documentation of this file.
1 /* moveGenerator.cc
2  */
15 #include "osl/move_action/store.h"
20 #include "osl/rating/featureSet.h"
21 #include "osl/rating/ratingEnv.h"
22 #include "osl/eval/pieceEval.h"
23 #include "osl/eval/progressEval.h"
25 #include "osl/stat/average.h"
26 #include <boost/foreach.hpp>
27 #include <iostream>
28 #include <iomanip>
29 
30 // #define STAT_WIDTH_VS_LIMIT
31 
32 #ifndef NDEBUG
33 # define SAFE_MOVE_ONLY
34 #endif
35 const int max_see = 20000;
36 
39 {
40  return *static_feature_set;
41 }
42 
44 {
45  if (static_feature_set == 0)
46  static_feature_set = &rating::StandardFeatureSet::instance();
47 }
48 
49 namespace osl
50 {
51  namespace search
52  {
53  const CArray2d<MoveGenerator::generator_t, 2, MoveGenerator::FINISH> MoveGenerator::Generators = {{
54  {
55  0,
56  &MoveGenerator::generateKingEscape<BLACK>,
57  &MoveGenerator::generateTakeBack<BLACK>,
58  &MoveGenerator::generateBreakThreatmate<BLACK>,
59  &MoveGenerator::generateCapture<BLACK>,
60  0,
61  &MoveGenerator::generateTesuji<BLACK>,
62  &MoveGenerator::generateAll<BLACK>,
63  },
64  {
65  0,
66  &MoveGenerator::generateKingEscape<WHITE>,
67  &MoveGenerator::generateTakeBack<WHITE>,
68  &MoveGenerator::generateBreakThreatmate<WHITE>,
69  &MoveGenerator::generateCapture<WHITE>,
70  0,
71  &MoveGenerator::generateTesuji<WHITE>,
72  &MoveGenerator::generateAll<WHITE>,
73  }
74  }};
75  const CArray<const char *, MoveGenerator::FINISH> MoveGenerator::GeneratorNames = {{
76  "INITIAL", "KING_ESCAPE", "TAKEBACK", "BREAK_THREATMATE", "TACTICAL", "SENTINEL", "TESUJI", "ALL",
77  }};
78 #ifdef STAT_WIDTH_VS_LIMIT
79  struct WidthVSLimit
80  {
81  CArray<stat::Average,10> averages;
82 
83  ~WidthVSLimit()
84  {
85  report();
86  }
87  stat::Average& average(int limit)
88  {
89  limit /= 100 - 3;
90  return averages[std::min(std::max(limit,0),(int)averages.size()-1)];
91  }
92  void report()
93  {
94  std::cerr << "WidthVSLimit@MoveGenerator\n";
95  for (int limit=300; limit<300+(int)averages.size()*100; limit+=100) {
96  std::cerr << std::setw(5) << limit << " " << average(limit).getAverage() << std::endl;
97  }
98  }
99  } Width_VS_Limit;
100 #endif
101  template
102  void MoveGenerator::init<osl::eval::ProgressEval>(
103  int limit, const SimpleHashRecord *record, const osl::eval::ProgressEval&,
104  const NumEffectState&, bool in_pv, Move hash_move, bool quiesce);
105  template
106  void MoveGenerator::init<osl::eval::ml::OpenMidEndingEval>(
107  int limit, const SimpleHashRecord *record,
109  const NumEffectState&, bool in_pv, Move hash_move, bool quiesce);
110  }
111 }
112 
113 /* ------------------------------------------------------------------------- */
114 
117 {
118  marker.fill(0);
119 }
120 
121 void osl::search::
123 {
124  ++cur;
125  if (cur == 0) {
126  marker.fill(0);
127  cur = 1;
128  }
129 }
130 
131 bool osl::search::
132 MoveMarker::registerIfNew(const NumEffectState& state, Move m)
133 {
134  value_t& val = marker(toIndex(m), pieceIndex(state, m));
135  if (val == cur)
136  return false;
137  val = cur;
138  return true;
139 }
140 
141 bool osl::search::
142 MoveMarker::registered(const NumEffectState& state, Move m) const
143 {
144  return marker(toIndex(m), pieceIndex(state, m)) == cur;
145 }
146 
147 /* ------------------------------------------------------------------------- */
148 
150 MoveGenerator::MoveGenerator() : record(0), progress(16)
151 {
152 }
153 
154 int osl::search::
156 {
157  if (! isPiece(ptype))
158  return 0;
159  int result
161  assert(result >= 0);
162  return result;
163 }
164 
165 template <class EvalT>
166 void osl::search::
168  const EvalT& eval,
169  const NumEffectState& state, bool in_pv, Move hash_move,
170  bool quiesce)
171 {
172  assert(r);
173  assert(l > 0);
174  limit = l;
175  record = r;
176  cur_state = INITIAL;
177  moves.clear();
178  cur_index = tried = 0;
179  progress = eval.progress32();
180  eval_suggestion = eval.suggestMove(state);
181 
182  marker.clear();
183  env.make(state, state.pin(state.turn()), state.pin(alt(state.turn())),
184  eval.progress16());
185  if (hash_move.isNormal())
186  marker.registerMove(state, hash_move);
187 #ifndef MINIMAL
188  in_quiesce = quiesce;
189 #endif
190  this->in_pv = in_pv;
191 }
192 
193 void osl::search::
195 {
196  std::cerr << "generator " << cur_state << " index " << cur_index
197  << " limit " << limit << " tried " << tried << "\n";
198  std::cerr << moves.size() << "\n"
199 #ifndef MINIMAL
200  << moves
201 #endif
202  ;
203 }
204 
205 template <osl::Player P>
208 {
209  assert(record);
210  while (true) {
211  assert(cur_index >= moves.size());
212  if (cur_state == KING_ESCAPE && record->inCheck()) {
213  cur_state = FINISH;
214  break;
215  }
216  if (++cur_state >= TACTICAL_FINISH)
217  break;
218  // generate
219  assert(Generators[playerToIndex(P)][cur_state]);
220  (this->*Generators[playerToIndex(P)][cur_state])(state);
221  if (cur_index < moves.size()) {
222  ++tried;
223  return moves[cur_index++];
224  }
225  }
226  return MoveLogProb();
227 }
228 
229 template <osl::Player P>
232 {
233  assert(record);
234  while (true) {
235  assert(cur_index >= moves.size());
236  if (++cur_state >= FINISH)
237  break;
238  // generate
239  assert(Generators[playerToIndex(P)][cur_state]);
240  (this->*Generators(playerToIndex(P), cur_state))(state);
241  if (cur_index < moves.size()) {
242  ++tried;
243  return moves[cur_index++];
244  }
245  }
246  return MoveLogProb();
247 }
248 
249 template <osl::Player P>
250 void osl::search::
252 {
253  env.history = sstate.history();
254  if (! record->inCheck())
255  return;
256 
257  const NumEffectState& state = sstate.state();
258  const Piece king = state.kingPiece<P>();
259  assert(state.hasEffectAt(alt(P), king.square()));
260 
261  MoveVector src;
263  size_t last = src.size();
264  for (size_t i=0; i<last; ++i)
265  if (src[i].hasIgnoredUnpromote<P>())
266  src.push_back(src[i].unpromote());
267 
268  if (src.size() == 1) {
269  moves.push_back(MoveLogProb(src[0], 20));
270  return;
271  }
272  BOOST_FOREACH(Move move, src) {
273  const int prob = std::min(limit, feature_set().logProbKingEscape(state, env, move));
274  assert(prob > 0);
275  moves.push_back(MoveLogProb(move, prob));
276  }
277  moves.sortByProbability();
278 }
279 
280 
281 
282 template <osl::Player P>
283 void osl::search::
285 {
286  const NumEffectState& state = sstate.state();
287  const Move threatmate_move = record->threatmate().threatmateMove(state.turn());
288  if (! threatmate_move.isNormal())
289  return;
290  BreakThreatmate::generate(limit, state, threatmate_move, moves);
291  BOOST_FOREACH(const MoveLogProb& move, moves)
292  marker.registerMove(state, move.move());
293 }
294 
295 template <osl::Player P>
296 void osl::search::
298 {
299  using namespace move_action;
300  const Move last_move = sstate.lastMove();
301  if (! last_move.isNormal())
302  return;
303  const Square last_to = last_move.to();
304 
305  const NumEffectState& state = sstate.state();
306 #ifndef MINIMAL
307  if (in_quiesce)
308  return quiesceCapture<P>(state, last_to);
309 #endif
310  MoveVector src;
311  move_generator::GenerateCapture::generate(state, last_to, src);
312 
313  assert(moves.empty());
314  BOOST_FOREACH(Move move, src) {
315  assert(! ShouldPromoteCut::canIgnoreMove<P>(move));
316  const int prob = feature_set().logProbTakeBack(state, env, move);
317 #ifdef OSL_SMP
318  if (! move.isDrop() && move.ptype() != KING
319  && env.my_pin.test(state.pieceOnBoard(move.from()).number())) {
320  if (move_classifier::KingOpenMove<P>::isMember(state, move.ptype(), move.from(), move.to()))
321  continue;
322  }
323 #endif
324  if (prob <= std::min(200, limit) && marker.registerIfNew(state, move))
325  moves.push_back(MoveLogProb(move, prob));
326  }
327  moves.sortByProbability();
328 }
329 
330 namespace osl
331 {
332  template <Player P, Ptype PTYPE>
333  static void makeCapture(const NumEffectState& state,
334  MoveVector& out)
335  {
337  mask_t pieces = state.piecesOnBoard(alt(P)).template selectBit<PTYPE>()
338  & state.effectedMask(P).getMask(PtypeFuns<PTYPE>::indexNum);
339  while (pieces.any())
340  {
341  const Piece p = state.pieceOf(pieces.takeOneBit()+PtypeFuns<PTYPE>::indexNum*32);
344  }
345  }
346 }
347 
348 template <osl::Player P>
349 void osl::search::
350 MoveGenerator::addCapture(const NumEffectState& state, const RatingEnv& env, const MoveVector& src)
351 {
352 #ifndef MINIMAL
353  if (in_quiesce) {
354  BOOST_FOREACH(Move move, src) {
355  assert(!ShouldPromoteCut::canIgnoreMove<P>(move));
356  const int see = PieceEval::computeDiffAfterMoveForRP(state, move);
357  if (see < 0)
358  continue;
359  moves.push_back(MoveLogProb(move, max_see - see));
360  }
361  return;
362  }
363 #endif
364  BOOST_FOREACH(Move move, src) {
365  assert(! ShouldPromoteCut::canIgnoreMove<P>(move));
366 #ifdef SAFE_MOVE_ONLY
367  if (! move.isDrop() && move.ptype() != KING
368  && env.my_pin.test(state.pieceOnBoard(move.from()).number())) {
369  if (move_classifier::KingOpenMove<P>::isMember(state, move.ptype(), move.from(), move.to()))
370  continue;
371  }
372 #endif
373  const int prob = feature_set().logProbSeePlus(state, env, move);
374  // const int prob = feature_set().logProbTakeBack(state, env, move);
375  if (prob <= 200 && marker.registerIfNew(state, move)) {
376  moves.push_back(MoveLogProb(move, prob));
377  }
378  }
379  return;
380 }
381 
382 template <osl::Player P>
383 void osl::search::
385 {
386  using namespace move_action;
387 
388  const NumEffectState& state = sstate.state();
389  MoveVector src;
390 #if 1
391  // lance, bishop, rook
392  makeCapture<P,LANCE>(state, src);
393  makeCapture<P,BISHOP>(state, src);
394  makeCapture<P,ROOK>(state, src);
395  // knight, silver, gold
396  makeCapture<P,KNIGHT>(state, src);
397  makeCapture<P,SILVER>(state, src);
398  makeCapture<P,GOLD>(state, src);
399 #else
400  makeCaptureOtherThanPawn<P>(state, src);
401 #endif
402  addCapture<P>(state, env, src);
403 }
404 
405 template <osl::Player P>
406 void osl::search::
408 {
409  const NumEffectState& state = sstate.state();
410  if (! state.inCheck() && eval_suggestion.isNormal()
411  && marker.registerIfNew(state, eval_suggestion)) {
412  assert(sstate.state().isValidMove(eval_suggestion));
413  moves.push_back(MoveLogProb(eval_suggestion, 250));
414  }
415 #ifndef MINIMAL
416  if (in_quiesce) {
417  MoveVector src;
419  makeCapture<P,PAWN>(state, src);
420  addCapture<P>(state, env, src);
421  }
422 #endif
423 }
424 
425 #ifndef MINIMAL
426 template <osl::Player P>
427 void osl::search::
428 MoveGenerator::quiesceCapture(const NumEffectState& state, Square to)
429 {
430  MoveVector moves;
432 
433  BOOST_FOREACH(Move move, moves) {
434  assert(!ShouldPromoteCut::canIgnoreAndNotDrop<P>(move));
435  int see = PieceEval::computeDiffAfterMoveForRP(state, move);
436  if (see < 0)
437  continue;
438  this->moves.push_back(MoveLogProb(move, max_see - see));
439  }
440  this->moves.sortByProbabilityReverse();
441 }
442 #endif
443 
444 template <osl::Player P>
445 void osl::search::
447 {
448 #ifndef MINIMAL
449  if (in_quiesce)
450  return;
451 #endif
452  const NumEffectState& state = sstate.state();
453  MoveLogProbVector all;
454  feature_set().generateLogProb(state, env, limit, all, in_pv);
455 #ifdef STAT_WIDTH_VS_LIMIT
456  const size_t moves_size_before = moves.size();
457 #endif
458  BOOST_FOREACH(const MoveLogProb& move, all) {
459  assert(!ShouldPromoteCut::canIgnoreAndNotDrop<P>(move.move()));
460  const Move m = move.move();
461  int limit = move.logProb();
462  if (this->limit >= 400) {
463  using namespace move_classifier;
464  if (m.isCaptureOrPromotion()
465  || (in_pv && MoveAdaptor<Check<P> >::isMember(state, move.move())))
466  limit = std::min(limit, 400);
467  }
468  if (limit <= this->limit
469  && marker.registerIfNew(state, move.move())) {
470 #ifndef NDEBUG
471  if (! m.isDrop()) {
472  assert(! (env.my_pin.test(state.pieceOnBoard(m.from()).number())
473  && move_classifier::KingOpenMove<P>::isMember(state, m.ptype(), m.from(), m.to())));
474  assert(! (m.ptype() == KING && state.hasEffectAt(alt(P), m.to())));
475  }
476 #endif
477  moves.push_back(MoveLogProb(move.move(), limit));
478  }
479  }
480 #ifdef STAT_WIDTH_VS_LIMIT
481  Width_VS_Limit.average(limit).add(moves.size() - moves_size_before);
482 #endif
483 }
484 
485 #ifndef MINIMAL
486 void osl::search::
489 {
490  assert(moves.size() == 0);
491 
492  for (int i=0; i<FINISH; ++i) {
493  if (! Generators[playerToIndex(P)][i])
494  continue;
495  (this->*Generators[playerToIndex(P)][i])(state);
496  out.push_front(analyzer::CategoryMoves(moves, GeneratorNames[i]));
497  bool generated = moves.size();
498  moves.clear();
499  if (i == KING_ESCAPE && generated)
500  break;
501  }
502  out.reverse();
503 }
504 #endif
505 
506 template <osl::Player P>
507 void
508 #if (defined __GNUC__) && (! defined GPSONE) && (! defined GPSUSIONE)
509 __attribute__ ((used))
510 #endif
512 MoveGenerator::generateAll(const SearchState2& state, MoveLogProbVector& out)
513 {
514  using namespace move_classifier;
515  for (MoveLogProb m = nextTacticalMove<P>(state);
516  m.validMove(); m = nextTacticalMove<P>(state)) {
517  assert(state.state().isValidMove(m.move()));
518  if (ConditionAdaptor<SafeMove>::isMember(state.state(), m.move()))
519  out.push_back(m);
520  }
521  for (MoveLogProb m = nextMove<P>(state); m.validMove();
522  m = nextMove<P>(state)) {
523  assert(state.state().isValidMove(m.move()));
524  if (ConditionAdaptor<SafeMove>::isMember(state.state(), m.move()))
525  out.push_back(m);
526  }
527 }
528 
529 void osl::search::
530 MoveGenerator::generateAll(Player P, const SearchState2& state, MoveLogProbVector& out)
531 {
532  if (P==BLACK)
533  generateAll<BLACK>(state, out);
534  else
535  generateAll<WHITE>(state, out);
536 }
537 
538 namespace osl
539 {
540  namespace search
541  {
542  template const MoveLogProb MoveGenerator::nextMoveWithGeneration<BLACK>(const SearchState2&);
543  template const MoveLogProb MoveGenerator::nextMoveWithGeneration<WHITE>(const SearchState2&);
544 
545  template const MoveLogProb MoveGenerator::nextTacticalMoveWithGeneration<BLACK>(const SearchState2&);
546  template const MoveLogProb MoveGenerator::nextTacticalMoveWithGeneration<WHITE>(const SearchState2&);
547  }
548 }
549 
550 /* ------------------------------------------------------------------------- */
551 // ;;; Local Variables:
552 // ;;; mode:c++
553 // ;;; c-basic-offset:2
554 // ;;; End: