All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
alphaBeta3.cc
Go to the documentation of this file.
1 /* alphaBeta3.cc
2  */
12 #include "osl/eval/see.h"
13 #include "osl/rating/featureSet.h"
14 #include "osl/rating/ratingEnv.h"
23 #include "osl/move_action/store.h"
28 #include "osl/record/csa.h"
29 #include "osl/stl/hash_map.h"
30 #include "osl/stat/average.h"
31 #include "osl/stat/histogram.h"
32 #include "osl/repetitionCounter.h"
33 #include <boost/scoped_array.hpp>
34 #include <boost/foreach.hpp>
35 #include <algorithm>
36 #include <iostream>
37 #include <cstdio>
38 #include <iomanip>
39 const int extended_futility_margin = 256*16, futility_margin = 128*16, table_record_limit = 400;
40 const int lmr_fullwidth = 4, lmr_reduce_limit = 200;
41 const bool best_move_extension_enabled = false;
42 const bool futility_pruning_enabled = true;
45 const bool lmr_enabled = true, lmr_verify_enabled = true;
46 const bool immediate_checkmate_enabled = true;
47 const bool decorate_csa_in_pv = false, show_height_in_pv = false;
48 /* ------------------------------------------------------------------------- */
49 namespace osl
50 {
51  namespace search
52  {
53  inline Ptype promoteIf(Ptype ptype)
54  {
55  return canPromote(ptype) ? promote(ptype) : ptype;
56  }
58  {
60  int value, limit;
63  CompactRecord() : limit(-1000000)
64  {
65  }
66  template <Player P>
67  bool highFail(int height, int threshold) const
68  {
70  && (type == Exact || type == LowerBound);
71  }
72  template <Player P>
73  bool lowFail(int height, int threshold) const
74  {
76  && (type == Exact || type == UpperBound);
77  }
78  };
79  struct CompactHashTable // todo: open hash
80  {
81  typedef hash_map<HashKey, CompactRecord> table_t;
83  mutable int probe_success, probe_fail;
85  {
86  }
88  {
89  }
90  const CompactRecord probe(const HashKey& key) const
91  {
92  table_t::const_iterator p = table.find(key);
93  if (p != table.end()) {
94  ++probe_success;
95  return p->second;
96  }
97  ++probe_fail;
98  return CompactRecord();
99  }
100  void store(const HashKey& key, const CompactRecord& value)
101  {
102  table[key] = value;
103  }
104  void clear()
105  {
106  table.clear();
108  }
109  };
110  }
111 }
112 /* ------------------------------------------------------------------------- */
113 // TODO: make shared? object
114 namespace
115 {
116  boost::scoped_array<osl::search::AlphaBeta3::SearchInfo> tree;
118  osl::stat::Average mpn, mpn_cut, last_alpha_update;
119  osl::stat::Histogram alpha_update_type(1,8);
120  osl::search::BigramKillerMove bigram_killers;
121  osl::search::KillerMoveTable killer_moves;
122  int eval_count;
123  int max_node_depth, total_node_count, depth_node_count[osl::search::AlphaBeta3::MaxDepth];
124  void init_node_count()
125  {
126  max_node_depth = total_node_count = 0;
127  std::fill(depth_node_count, depth_node_count+sizeof(depth_node_count)/sizeof(int), 0);
128  }
129  inline void add_node_count(int depth)
130  {
131  max_node_depth = std::max(max_node_depth, depth);
132  ++depth_node_count[depth];
133  ++total_node_count;
134  }
135  osl::Player root_player;
136  osl::RepetitionCounter repetition_counter;
137 }
138 
139 /* ------------------------------------------------------------------------- */
140 
142 AlphaBeta3(const NumEffectState& s, checkmate_t& /*checker*/,
144  : state(s), depth(0), recorder(r), table_common(t)
145 {
146  if (! tree) {
148  tree.reset(new SearchInfo[MaxDepth]);
149  }
150 }
151 
154 {
155 }
156 
158 evalValue() const
159 {
160  ++eval_count;
161  if ((eval_count % (1<<18) == 0) || stop_by_alarm)
162  if (this->timeAssigned().standard.toSeconds() - this->elapsed() < 0.3 || stop_by_alarm)
163  throw misc::NoMoreTime();
164  return tree[depth].eval.value();
165 }
166 
168 computeBestMoveIteratively(int limit, int /*step*/, int initial_limit,
169  size_t /*node_limit*/,
170  const TimeAssigned& assign,
171  MoveWithComment */*additional_info*/)
172 {
173  this->setStartTime(MilliSeconds::now());
174  this->setTimeAssign(assign);
175 
176  mpn.clear();
177  mpn_cut.clear();
178  last_alpha_update.clear();
179  bigram_killers.clear();
180  table.clear();
181  eval_count = 0;
182  init_node_count();
183 
184  initial_limit = std::min(initial_limit, limit);
185 
186  // todo: iteration
187  Move best_move;
188  double consumed = 0;
189 
190  try {
191  for (int i=0; i<=limit; i+=100) {
192  double new_consumed = this->elapsed(), diff = new_consumed - consumed;
193  consumed = new_consumed;
194  if (table_common->verboseLevel() > 1)
195  std::cerr << i << " sec " << diff << " " << new_consumed
196  << " mpn " << mpn.getAverage() << " " << mpn_cut.getAverage()
197  << " " << last_alpha_update.getAverage() << "\n";
198  best_move = searchRoot(i);
199 
200  if (hasSchedule()) {
201  const double current_time_left = this->timeAssigned().standard.toSeconds()-this->elapsed();
202  const double coef = nextIterationCoefficient();
203  if (current_time_left < new_consumed * coef) {
204  if (table_common->verboseLevel() > 1)
205  std::cerr << "expected timeover\n";
206  break;
207  }
208  }
209  }
210  }
211  catch (misc::NoMoreTime&) {
212  if (table_common->verboseLevel() > 1)
213  std::cerr << "timeover\n";
214  }
215  catch (NoMoreMemory&) {
216  if (table_common->verboseLevel() > 1)
217  std::cerr << "memory full\n";
218  }
219  double new_consumed = this->elapsed(), diff = new_consumed - consumed;
220  consumed = new_consumed;
221  if (table_common->verboseLevel() > 1) {
222  std::cerr << "finish" << " sec " << diff << " " << new_consumed
223  << " mpn " << mpn.getAverage() << " " << mpn_cut.getAverage()
224  << " " << last_alpha_update.getAverage() << "\n";
225  std::cerr << "table " << table.table.size() << " " << table.probe_success << " " << table.probe_fail
226  << "\n";
227  recorder.finishSearch(best_move, consumed, table_common->verboseLevel() > 1);
228  // alpha_update_type.show(std::cerr);
229  for (int i=0; i<=max_node_depth/4; ++i) {
230  for (int j=0; j<4; ++j) {
231  const int id = i + (max_node_depth/4)*j;
232  fprintf(stderr, " depth %2d %5.2f%%",
233  id, 100.0*depth_node_count[id] / (double)total_node_count);
234  }
235  fprintf(stderr, "\n");
236  }
237  }
238  return best_move;
239 }
240 
242 isReasonableMove(Move /*move*/, int /*pawn_sacrifice*/)
243 {
244  return true;
245 }
246 
248 setRootIgnoreMoves(const MoveVector * /*rim*/, bool)
249 {
250 }
252 setHistory(const MoveStack& /*h*/)
253 {
254 }
255 
257 showNodeDepth(std::ostream&)
258 {
259 }
262 {
263 }
264 /* ------------------------------------------------------------------------- */
265 
268 {
269  depth = 0;
270  SearchInfo& root = tree[0];
271  root.moved = Move::PASS(alt(state.turn()));
272  root.hash_key = HashKey(state);
273  root.height = limit;
274  root.path = PathEncoding(state.turn(), 0);
275  root.eval = eval_t(state);
276  root.moves.clear();
277  recorder.resetNodeCount();
278  root_player = state.turn();
279  repetition_counter.clear();
280  repetition_counter.push(root.hash_key, state);
281 #if 1
282  RatedMoveVector moves;
283  {
285  RatingEnv env;
286  env.make(state);
287  features.generateRating(state, env, 2000, moves);
288  BOOST_FOREACH(const RatedMove& move, moves)
289  root.moves.push_back(move.move());
290  }
291 #else
292  LegalMoves::generate(state, root.moves);
293 #endif
294 
295  Move best_move;
296  const Player turn = state.turn();
297  int best_value = minusInfty(turn);
298  root.alpha = best_value + eval::delta(turn);
299  root.beta = -minusInfty(turn) - eval::delta(turn);
300  root.node_type = PvNode;
301 
302  CompactRecord record = table.probe(root.hash_key);
303  if (record.best_move.isNormal()) {
304  MoveVector::iterator p
305  =std::find(root.moves.begin(), root.moves.end(), record.best_move);
306  if (p != root.moves.end())
307  std::swap(*root.moves.begin(), *p);
308  }
309 
310  BOOST_FOREACH(Move move, root.moves) {
311  if (best_move.isNormal())
312  root.node_type = AllNode;
314  if (best_move.isNormal())
315  continue;
316  const int value = (turn == BLACK)
317  ? makeMoveAndSearch<BLACK>(move, 100)
318  : makeMoveAndSearch<WHITE>(move, 100);
319  if (eval::betterThan(turn, value, best_value)) {
320  root.pv.setPV(move, root, tree[depth+1].pv);
321  if (limit && table_common->verboseLevel()) {
322  std::cerr << " " << record::csa::show(move) << " " << std::setw(6) << value << " " << std::setw(3) << root.pv.size() << " ";
323  for (size_t i=1; i<root.pv.size(); ++i) {
324  std::cerr << record::csa::show(root.pv[i].move);
325  if (decorate_csa_in_pv) {
326  if (i && root.pv[i-1].move.to() == root.pv[i].move.to()) std::cerr << '!';
327  else if (root.pv[i].move.capturePtype()) std::cerr << 'x' << record::csa::show(root.pv[i].move.capturePtype());
328  if (root.pv[i].move.isPromotion()) std::cerr << '*';
329  if (root.pv[i].in_check) std::cerr << '#';
330  if (show_height_in_pv) std::cerr << "(" << root.pv[i].height/10 << ")";
331  }
332  }
333  std::cerr << std::endl;
334  }
335  best_value = value;
336  best_move = move;
337  root.alpha = best_value + eval::delta(turn);
338  SimpleHashRecord *record = table_common->allocate(root.hash_key, limit);
339  if (record)
340  record->setLowerBound(turn, limit, MoveLogProb(best_move,100), best_value);
341  }
342  }
343  record.best_move = best_move;
344  record.value = best_value;
345  record.type = CompactRecord::Exact;
346  record.limit = root.height;
347  table.store(root.hash_key, record);
348  return best_move;
349 }
350 
351 template <osl::Player P>
353 {
355  explicit CallSearch(AlphaBeta3 *s) : search(s) {}
356  void operator()(Square) const { search->template presearch<P>(); }
357 };
358 
359 template <osl::Player P>
361 {
363  explicit CallQuiesce(AlphaBeta3 *s) : search(s) {}
364  void operator()(Square) const { search->template quiesce<PlayerTraits<P>::opponent>(); }
365 };
366 
367 template <osl::Player P>
369 makeMoveAndSearch(Move move, int consume)
370 {
371  ++depth;
372  SearchInfo &node = tree[depth], &parent = tree[depth-1];
373  node.moved = move;
374  node.hash_key = tree[depth-1].hash_key.newHashWithMove(move);
375  node.path = parent.path;
376  node.height = parent.height - consume;
377  node.alpha = parent.beta;
378  node.beta = parent.alpha;
379  node.node_type = (NodeType)-(parent.node_type);
380  node.eval = parent.eval;
381  node.pv.clear();
382  node.extended = 0;
383 
384  // 千日手確認
385  if (0)
386  {
387  const Sennichite next_sennichite
388  = repetition_counter.isAlmostSennichite(node.hash_key);
389  if (node.moved.isNormal() && next_sennichite.isDraw())
390  return this->drawValue();
391  if (next_sennichite.hasWinner())
392  return this->winByFoul(next_sennichite.winner());
393  }
394  // repetition_counter.push(node.hash_key, state);
395 
396  CallSearch<P> f(this);
397  node.path.pushMove(move);
398  state.makeUnmakeMove(Player2Type<P>(), move, f);
399  node.path.popMove(move);
400 
401  // repetition_counter.pop();
402  --depth;
403 
404  return tree[depth+1].search_value;
405 }
406 
407 inline
409 reductionOk() const
410 {
411  const SearchInfo& node = tree[depth];
412  const Move m = node.moved;
413  if (m.isCaptureOrPromotion())
414  return false;
415  if (node.in_check || (depth > 0 && tree[depth-1].in_check))
416  return false;
417  return true;
418 }
419 
420 template <osl::Player P>
423 {
424  SearchInfo& node = tree[depth];
425  assert(state.turn() == alt(P));
426  const Player turn = alt(P);
427  if (state.hasEffectAt(turn, state.kingSquare(alt(turn)))) {
428  node.search_value = winByFoul(turn);
429  return;
430  }
431  node.in_check = state.hasEffectAt(alt(turn), state.kingSquare(turn));
432  node.eval.update(state, node.moved);
433 
434  // heuristic extension
435 #if 0
436  if (depth > 1 && tree[depth-1].in_check && tree[depth-1].moves.size() == 1) { // one reply
437  const int ext = 50;
438  node.extended += ext;
439  node.height += ext;
440  }
441 #endif
442  if (node.in_check) {
443  const int ext = (node.alpha != node.beta
444  || (depth > 2 && tree[depth-1].moved.ptype() == KING))
445  ? 100 : 100;
446  node.extended += ext;
447  node.height += ext;
448  }
449  else if (depth > 1 && node.moved.to() == tree[depth-1].moved.to() && ! node.moved.isPass()) {
450  const int ext = (node.alpha != node.beta
451  || tree[depth-1].moved.isCapture())
452  ? 50 : 25;
453  node.extended += ext;
454  node.height += ext;
455  }
456 
457  // null move pruning
458  if (node.moved.isPass()) { // need verify?
459  const int ext = (node.height >= 500) ? -200 : -100;
460  node.height += ext;
461  node.extended = ext;
462  }
463 
464  // null window search
465  const int org_alpha = node.alpha, org_height = node.height;
466  const NodeType org_node_type = node.node_type;
467  const bool pv_in_pvs = node.node_type == CutNode && node.alpha != node.beta;
468  int lmr_reduce = 0;
469  if (pv_in_pvs)
470  node.alpha = node.beta;
471 
472  if (node.alpha == node.beta) {
473  if (lmr_enabled && ! node.extended && reductionOk()
474  && (!pv_in_pvs || node.height >= lmr_reduce_limit+100)
475  && depth > 0) {
476  if (pv_in_pvs)
477  lmr_reduce = tree[depth-1].moves_tried / lmr_fullwidth * 50;
478  else
479  lmr_reduce = tree[depth-1].moves_tried / lmr_fullwidth * 75;
480  lmr_reduce = std::min(400, lmr_reduce);
481  node.height -= lmr_reduce;
482  if (pv_in_pvs && node.height < lmr_reduce_limit)
483  node.height = lmr_reduce_limit;
484  }
485  search<PlayerTraits<P>::opponent>();
486  if (EvalTraits<P>::betterThan(node.beta, node.search_value)) // note: beta cut for opponent
487  return;
488  node.height = org_height;
489  node.alpha = org_alpha;
490  node.node_type = org_node_type;
491  // verification search not in pv
492  if (! pv_in_pvs) {
493  if (lmr_verify_enabled && lmr_reduce) {
494  node.height -= lmr_reduce/2;
495  if (lmr_reduce >= 100 || node.height >= 400)
496  search<PlayerTraits<P>::opponent>();
497  }
498  return;
499  }
500  node.node_type = PvNode;
501  }
502  // now node is pv
503  assert(node.node_type == PvNode);
504  if (node.height >= table_record_limit)
505  {
506  CompactRecord record = table.probe(node.hash_key);
507  // iid if hash-move is not available
508  if (! record.best_move.isNormal()) {
509  const int height = node.height;
510  for (int i=200; i+100<height; i+=200) {
511  node.height = i;
512  search<PlayerTraits<P>::opponent>();
513  node.alpha = org_alpha;
514  node.node_type = PvNode;
515  }
516  node.height = height;
517  }
518  }
519  // main search
520  const bool best_move_extension_candidate
521  = best_move_extension_enabled && root_player == P
522  && node.height >= 150 && node.extended < 50;
523  const bool skip_main_search
524  = best_move_extension_candidate && pv_in_pvs;
525  if (! skip_main_search)
526  search<PlayerTraits<P>::opponent>();
527  // best move ext --- ?
528  if (best_move_extension_candidate
529  && EvalTraits<P>::betterThan(node.search_value, node.beta)) // alpha value update for P
530  {
531  node.node_type = PvNode;
532  node.alpha = org_alpha;
533  const int ext = 50;
534  node.height += ext; node.extended += ext;
535  search<PlayerTraits<P>::opponent>();
536  }
537 }
538 
539 template <osl::Player P>
542 {
543  using namespace move_classifier;
544  add_node_count(depth);
545 
546  SearchInfo& node = tree[depth];
547  assert(state.turn() == P);
548  recorder.addNodeCount();
549 
550  if (node.height < 0) {
551  quiesceRoot<P>();
552  return;
553  }
554 
555  CompactRecord record = node.height >= table_record_limit
556  ? table.probe(node.hash_key)
557  : CompactRecord();
558  if (node.alpha == node.beta) {
559  if (record.highFail<P>(node.height, node.beta)) {
560  node.search_value = record.value;
561  return;
562  }
563  if (record.lowFail<P>(node.height, node.alpha)) {
564  node.search_value = record.value;
565  return;
566  }
567  }
568  const bool frontier_node = futility_pruning_enabled && node.height < 100;
569  const bool extended_frontier_node = (! frontier_node) && extended_futility_pruning_enabled && node.height < 200;
570  const bool in_pv = node.alpha != node.beta;
571  node.move_type = Initial;
572  node.moves_tried = 0;
573  const int initial_value = minusInfty(P)+depth*EvalTraits<P>::delta*2;
574  int best_value = initial_value, last_alpha_update=0;
575  if (EvalTraits<P>::betterThan(best_value, node.alpha)) {
576  node.alpha = best_value + EvalTraits<P>::delta;
577  if (EvalTraits<P>::betterThan(best_value, node.beta)) {
578  node.search_value = best_value;
579  return;
580  }
581  }
582  const int initial_alpha = node.alpha;
583  if (record.best_move.isNormal()) {
584  const Move move = record.best_move;
585  int value = makeMoveAndSearch<P>(move, 100);
586  if (EvalTraits<P>::betterThan(value, best_value)) {
587  best_value = value;
588  if (EvalTraits<P>::betterThan(value, node.alpha)) {
589  if (in_pv)
590  node.pv.setPV(move, node, tree[depth+1].pv);
591  node.alpha = value + EvalTraits<P>::delta;
592  last_alpha_update = node.moves_tried+1;
593  alpha_update_type.add(node.move_type);
594  if (EvalTraits<P>::betterThan(value, node.beta)) {
595  mpn_cut.add(node.moves_tried+1);
596  goto done;
597  }
598  }
599  }
600  node.moves_tried++;
601  }
602  if (immediate_checkmate_enabled && ! node.in_check && (frontier_node || extended_futility_pruning_enabled)
603  && ImmediateCheckmate::hasCheckmateMove<P>(state)) {
604  node.search_value = winByCheckmate(P);
605  return;
606  }
607  for (Move move=nextMove<P>(); !move.isInvalid(); move=nextMove<P>(), node.moves_tried++) {
608  if (node.moves_tried == 1)
609  node.node_type = AllNode;
610  if (move == record.best_move)
611  continue;
612  if (! node.in_check && node.node_type != PvNode) {
613  if (frontier_node && node.move_type > Pass) {
614  const int futility = evalValue()
615  + (move.capturePtype() ? eval_t::captureValue(move.capturePtypeO()) : 0)
617  if (EvalTraits<P>::betterThan(best_value, futility)
618  && (!tree[depth-1].in_check || !PlayerMoveAdaptor<DirectCheck>::isMember(state,move)))
619  continue;
620  }
621  else if (extended_frontier_node && node.move_type > Killer) {
622  const int futility_base = evalValue()+ extended_futility_margin*EvalTraits<P>::delta;
623  if ((move.capturePtype()
624  && EvalTraits<P>::betterThan(best_value, futility_base+node.eval.captureValue(move.capturePtypeO())))
625  || EvalTraits<P>::betterThan(best_value, futility_base+See::see(state, move)))
626  if (!tree[depth-1].in_check || !PlayerMoveAdaptor<DirectCheck>::isMember(state,move))
627  continue;
628  }
629  }
630  int value = makeMoveAndSearch<P>(move, 100);
631  if (EvalTraits<P>::betterThan(value, best_value)) {
632  best_value = value;
633  record.best_move = move;
634  if (EvalTraits<P>::betterThan(value, node.alpha)) {
635  if (in_pv)
636  node.pv.setPV(move, node, tree[depth+1].pv);
637  node.alpha = value + EvalTraits<P>::delta;
638  last_alpha_update = node.moves_tried+1;
639  alpha_update_type.add(node.move_type);
640  if (EvalTraits<P>::betterThan(value, node.beta)) {
641  mpn_cut.add(node.moves_tried+1);
642  goto done;
643  }
644  }
645  }
646  }
647  mpn.add(node.moves_tried);
648  if (last_alpha_update)
649  ::last_alpha_update.add(last_alpha_update);
650 done:
651  if (last_alpha_update && node.move_type > Killer) {
652  bigram_killers.setMove(node.moved, record.best_move);
653  killer_moves.setMove(depth, record.best_move);
654  // history_table.setMove(depth, record.best_move);
655  }
656  if (node.height >= table_record_limit) {
657  record.value = best_value;
658  record.limit = node.height;
659  if (EvalTraits<P>::betterThan(initial_alpha, best_value))
660  record.type = CompactRecord::UpperBound;
661  else if (EvalTraits<P>::betterThan(node.beta, best_value))
662  record.type = CompactRecord::Exact;
663  else
664  record.type = CompactRecord::LowerBound;
665  table.store(node.hash_key, record);
666  }
667  node.search_value = best_value;
668 }
669 
670 template <osl::Player P>
672 {
673  SearchInfo& node = tree[depth];
674  switch (node.move_type) {
675  case Initial:
676  node.move_index = 0;
677  node.moves.clear();
678  if (node.in_check) {
680  generate(state,state.kingPiece<P>(),node.moves);
681  node.move_type = KingEscape; // fall through
682  } // fall through
683  case KingEscape:
684  if (! node.moves.empty()) {
685  if (node.move_index < node.moves.size())
686  return node.moves[node.move_index++];
687  return Move();
688  }
689  node.move_type = Pass; // fall through
690  node.move_index = 0;
691  case Pass:
692  if (node.move_index++ == 0 && node.node_type != PvNode && !node.in_check)
693  return Move::PASS(P);
694  node.move_type = TakeBack; // fall through
695  node.move_index = 0;
696  if (node.moved.isNormal()) {
698  // move_order::MoveSorter::sort(node.moves, move_order::CheapPtype());
699  }
700  case TakeBack:
701  if (node.move_index == 0 && node.moves.size())
702  return node.moves[node.move_index++];
703  node.move_type = Capture; // fall through
704  node.move_index = 0;
705  generateCapture<P>(state, node);
706  case Capture:
707  if (node.move_index < node.moves.size())
708  return node.moves[node.move_index++];
709  node.move_type = Killer; // fall through
710  node.move_index = 0;
711  node.moves.clear();
712  bigram_killers.getMove(state, node.moved, node.moves);
713  killer_moves.getMove(state, depth, node.moves);
714  case Killer:
715  if (node.move_index < node.moves.size())
716  return node.moves[node.move_index++];
717  node.move_type = CaptureAll; // fall through
718  node.move_index = 0;
719  generateCaptureAll<P>(state, node);
720  case CaptureAll:
721  if (node.move_index < node.moves.size())
722  return node.moves[node.move_index++];
723  node.move_type = All; // fall through
724  node.move_index = 0;
725  generateAllMoves<P>(state, tree[depth-1], node);
726  case All:
727  if (node.move_index < node.moves.size())
728  return node.moves[node.move_index++];
729  }
730  return Move();
731 }
732 
733 template <osl::Player P>
735 generateAllMoves(const NumEffectState& state, const SearchInfo& parent, SearchInfo& node)
736 {
737  node.moves.clear();
739  && ! parent.in_check
740  && ! node.in_check && node.node_type != PvNode) {
741  if ((futility_pruning_enabled && node.height < 100)
742  || (extended_futility_pruning_enabled && node.height < 200
744  // generation considering futility pruning
745  GenerateAllMoves::generateOnBoard<P>(state, node.moves);
746  }
747  }
748 #if 1
749 # if 1
750  if (node.alpha != node.beta || node.height >= 800) {
751  RatedMoveVector moves;
753  RatingEnv env;
754  env.make(state);
755  features.generateRating(state, env, 2000, moves);
756  BOOST_FOREACH(const RatedMove& move, moves)
757  if (move.move().isDrop() || ! seePlusLight<P>(state, move.move()))
758  node.moves.push_back(move.move());
759  return;
760  }
761 # endif
762  GenerateAllMoves::generate<P>(state, node.moves);
763 
764  if (node.alpha != node.beta || node.height > 300)
765  std::sort(node.moves.begin(), node.moves.end(), move_order::CaptureEstimation(state));
766 #endif
767 }
768 
769 template <osl::Player P>
771 generateCapture(const NumEffectState& state, SearchInfo& node)
772 {
773  node.moves.clear();
774  MoveVector all;
775  for (size_t i=0; i+1<PieceStand::order.size(); ++i) { // except for pawn
776  const Ptype ptype = PieceStand::order[i];
777  all.clear();
779  for (int j=Ptype_Table.getIndexMin(ptype); j<Ptype_Table.getIndexLimit(ptype); ++j) {
780  const Piece p = state.pieceOf(j);
782  continue;
784  }
785  BOOST_FOREACH(Move move, all) {
786  if (See::see(state, move) > 0) {
787  node.moves.push_back(move);
788  }
789  }
790  if (! node.moves.empty())
791  return;
792  }
793  // promote
794  all.clear();
796  BOOST_FOREACH(Move move, all) {
797  if (See::see(state, move) > 0) {
798  node.moves.push_back(move);
799  }
800  }
801  if (! node.moves.empty())
802  return;
803  // pawn
804  all.clear();
805  {
807  for (int j=Ptype_Table.getIndexMin(PAWN); j<Ptype_Table.getIndexLimit(PAWN); ++j) {
808  const Piece p = state.pieceOf(j);
810  continue;
812  }
813  }
814  BOOST_FOREACH(Move move, all) {
815  if (See::see(state, move) > 0) {
816  node.moves.push_back(move);
817  }
818  }
819 }
820 template <osl::Player P>
821 inline
823 seePlusLight(const NumEffectState& state, Move m)
824 {
825  assert(P == m.player());
826  assert(P == state.turn());
827  assert(! m.isDrop());
828  if (state.countEffect(P, m.to()) > state.countEffect(P, m.to()))
829  return true;
831 }
832 
833 template <osl::Player P>
835 generateCaptureAll(const NumEffectState& state, SearchInfo& node)
836 {
837  node.moves.clear();
838  MoveVector all;
839  {
841  for (size_t i=0; i+1<PieceStand::order.size(); ++i) {
842  const Ptype ptype = PieceStand::order[i];
843  for (int j=Ptype_Table.getIndexMin(ptype); j<Ptype_Table.getIndexLimit(ptype); ++j) {
844  const Piece p = state.pieceOf(j);
846  continue;
848  }
849  }
851  for (int j=PtypeTraits<PAWN>::indexMin; j<PtypeTraits<PAWN>::indexLimit; ++j) {
852  const Piece p = state.pieceOf(j);
854  continue;
856  }
857  }
858  BOOST_FOREACH(Move move, all)
859  if (seePlusLight<P>(state, move))
860  node.moves.push_back(move);
861  std::sort(node.moves.begin(), node.moves.end(), move_order::CaptureEstimation(state));
862 }
863 
864 template <osl::Player P>
867 {
868  SearchInfo& node = tree[depth];
869  assert(! state.hasEffectAt(P, state.kingSquare(alt(P))));
870  assert(node.in_check == state.hasEffectAt(alt(P), state.kingSquare(P)));
871 
872  node.search_value = evalValue();
873  const int static_value = node.search_value;
874  int best_value = static_value;
875  if (node.in_check) {
876  node.moves.clear();
878  generate(state,state.kingPiece<P>(),node.moves);
879  best_value = threatmatePenalty(P)+depth*EvalTraits<P>::delta*2;
880 
881  BOOST_FOREACH(Move move, node.moves) {
882  int value = makeMoveAndQuiesce<P>(move);
883  if (EvalTraits<P>::betterThan(value, best_value)) {
884  best_value = value;
885  if (EvalTraits<P>::betterThan(value, node.alpha)) {
886  if (node.node_type == PvNode)
887  node.pv.setPV(move, node, tree[depth+1].pv);
888  node.alpha = value + EvalTraits<P>::delta;
889  if (EvalTraits<P>::betterThan(value, node.beta))
890  goto done;
891  }
892  }
893  }
894  goto done;
895  } // end of in check
896  if (EvalTraits<P>::betterThan(best_value, node.beta))
897  goto done;
898  if (immediate_checkmate_enabled && ImmediateCheckmate::hasCheckmateMove<P>(state)) {
899  node.search_value = winByCheckmate(P);
900  return;
901  }
902  BOOST_FOREACH(Ptype ptype, PieceStand::order) {
903  const int expected = static_value + node.eval.captureValue(newPtypeO(alt(P), promoteIf(ptype)));
904  if (EvalTraits<P>::betterThan(node.alpha, expected))
905  break;
906  for (int j=Ptype_Table.getIndexMin(ptype); j<Ptype_Table.getIndexLimit(ptype); ++j) {
907  const Piece p = state.pieceOf(j);
909  continue;
910  node.moves.clear();
912  BOOST_FOREACH(Move move, node.moves) {
913  if (See::see(state, move) < 0)
914  continue;
915  int value = makeMoveAndQuiesce<P>(move);
916  if (EvalTraits<P>::betterThan(value, best_value)) {
917  best_value = value;
918  if (EvalTraits<P>::betterThan(value, node.alpha)) {
919  if (node.node_type == PvNode)
920  node.pv.setPV(move, node, tree[depth+1].pv);
921  node.alpha = value + EvalTraits<P>::delta;
922  if (EvalTraits<P>::betterThan(value, node.beta))
923  goto done;
924  }
925  }
926  }
927  }
928  }
929 done:
930  node.search_value = best_value;
931 }
932 
933 template <osl::Player P>
936 {
937  ++depth;
938  tree[depth] = tree[depth-1];
939  tree[depth].moved = move;
940  tree[depth].hash_key = tree[depth-1].hash_key.newHashWithMove(move);
941  tree[depth].height -= 1;
942  std::swap(tree[depth].alpha, tree[depth].beta);
943  tree[depth].pv.clear();
944 
945  CallQuiesce<P> f(this);
946  tree[depth].path.pushMove(move);
947  state.makeUnmakeMove(move, f);
948  tree[depth].path.popMove(move);
949 
950  --depth;
951 
952  return tree[depth+1].search_value;
953 }
954 
955 template <osl::Player P>
958 {
959  add_node_count(depth);
960 
961  assert(state.turn() == P);
962  recorder.addQuiescenceCount();
963  SearchInfo& node = tree[depth];
964  if (state.hasEffectAt(P, state.kingSquare(alt(P)))) {
965  node.search_value = winByFoul(P);
966  return;
967  }
968  node.eval.update(state, node.moved);
969  node.in_check = state.hasEffectAt(alt(P), state.kingSquare(P));
970 
971  const int static_value = evalValue();
972  int best_value = static_value;
973 
974  if (node.in_check) {
975  node.moves.clear();
977  generate(state,state.kingPiece<P>(),node.moves);
978 
979  best_value = threatmatePenalty(P)+depth*EvalTraits<P>::delta*2;
980 
981  BOOST_FOREACH(Move move, node.moves) {
982  int value = makeMoveAndQuiesce<P>(move);
983  if (EvalTraits<P>::betterThan(value, best_value)) {
984  best_value = value;
985  if (EvalTraits<P>::betterThan(value, node.alpha)) {
986  node.alpha = value + EvalTraits<P>::delta;
987  if (EvalTraits<P>::betterThan(value, node.beta))
988  goto done;
989  }
990  }
991  }
992  goto done;
993  } // end of in check
994 
995  // leaf
996  if (EvalTraits<P>::betterThan(best_value, node.beta))
997  goto done;
998  if (immediate_checkmate_enabled && node.alpha != node.beta && ImmediateCheckmate::hasCheckmateMove<P>(state)) {
999  node.search_value = winByCheckmate(P);
1000  return;
1001  }
1002  for (size_t i=0; i<PieceStand::order.size(); ++i) {
1003  const Ptype ptype = PieceStand::order[i];
1004  const int expected = static_value + node.eval.captureValue(newPtypeO(alt(P), promoteIf(ptype)));
1005  if (EvalTraits<P>::betterThan(node.alpha, expected))
1006  break;
1007  for (int j=Ptype_Table.getIndexMin(ptype); j<Ptype_Table.getIndexLimit(ptype); ++j) {
1008  const Piece p = state.pieceOf(j);
1010  continue;
1011  node.moves.clear();
1013 
1014  for (size_t k=0; k<std::min((size_t)1, node.moves.size()); ++k) {
1015  const Move move = node.moves[k];
1016  const int see = See::see(state, move);
1017  int value = static_value + see*eval_t::seeScale()*EvalTraits<P>::delta;
1018  if (EvalTraits<P>::betterThan(value, best_value)) {
1019  if (node.node_type == PvNode)
1020  node.pv.setPV(move, node, tree[depth+1].pv);
1021  best_value = value;
1022  if (i < 6 || EvalTraits<P>::betterThan(value, node.beta))
1023  goto done;
1024  }
1025  }
1026  }
1027  }
1028 done:
1029  node.search_value = best_value;
1030 }
1031 
1032 /* ------------------------------------------------------------------------- */
1034 SearchInfo::SearchInfo() : eval((NumEffectState(SimpleState(HIRATE)))), pv()
1035 {
1036 }
1037 
1039 PVVector::setPV(Move m, const SearchInfo& node, const PVVector& child)
1040 {
1041  clear();
1042  const PVInfo info = { m, node.height, node.in_check, };
1043  push_back(info);
1044  push_back(child.begin(), child.end());
1045 }
1046 
1047 /* ------------------------------------------------------------------------- */
1048 // ;;; Local Variables:
1049 // ;;; mode:c++
1050 // ;;; c-basic-offset:2
1051 // ;;; End: