All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
alphaBeta2.cc
Go to the documentation of this file.
1 /* alphaBeta2.cc
2  */
4 #ifdef OSL_SMP
6 #endif
17 #include "osl/search/usiReporter.h"
19 #include "osl/eval/see.h"
20 #include "osl/eval/pieceEval.h"
22 #include "osl/record/csa.h"
23 #include "osl/record/ki2.h"
24 #include "osl/record/kanjiCode.h"
31 #include "osl/misc/ctime.h"
32 #include "osl/misc/eucToLang.h"
33 #include "osl/stat/ratio.h"
35 #include <boost/foreach.hpp>
36 #include <stdexcept>
37 #include <iostream>
38 #include <iomanip>
39 
40 #define search_assert(x, m) assert((x) || SearchState2::abort(m))
41 
43 
44 #ifdef CHECKMATE_COUNT
45 static size_t root_checkmate = 0, checkmate_before = 0, checkmate_after = 0,
46  count_threatmate = 0, quiesce_checkmate=0;
47 #endif
48 
49 // #define EXPERIMENTAL_QUIESCE
50 
51 /* ------------------------------------------------------------------------- */
53 showLastPv(int limit) const
54 {
55  for (int i=last_pv.size()-1; i>=0 && last_pv[i].depth == limit; --i) {
56  std::cerr << last_pv[i].eval << ' ';
57  for (size_t j=0; j<std::min((size_t)2, last_pv[i].pv.size()); ++j)
58  std::cerr << record::csa::show(last_pv[i].pv[j]);
59  std::cerr << " ";
60  }
61  std::cerr << "\n";
62 }
63 
64 /* ------------------------------------------------------------------------- */
65 /* Constructors */
66 /* ------------------------------------------------------------------------- */
67 
68 #ifndef MINIMAL
69 template <class EvalT>
70 osl::CArray<int, osl::search::SearchState2Core::MaxDepth> osl::search::AlphaBeta2Tree<EvalT>::depth_node_count;
71 #endif
72 
73 template <class EvalT>
75 AlphaBeta2Tree(const NumEffectState& s, checkmate_t& c,
78  SearchState2(s, c), AlphaBeta2Common<EvalT>(s), node_count(0), shared_root(new AlphaBeta2SharedRoot)
79 {
80 #ifdef OSL_SMP
81  for (int i=0; i<4; ++i) {
82  try
83  {
84  shared.reset(new AlphaBeta2Parallel<EvalT>(this));
85  break;
86  }
87  catch (std::bad_alloc&)
88  {
89  std::cerr << "panic " << i << " allocation of AlphaBeta2Parallel failed\n";
90 #ifdef _WIN32
91  boost::this_thread::sleep(boost::posix_time::seconds(1));
92 #else
93  sleep(1);
94 #endif
95  NonBlockDelete::deleteAll();
96  }
97  }
98 #endif
99 }
100 
101 template <class EvalT>
105  SearchState2(src), SearchTimer(src), AlphaBeta2Common<EvalT>(src),
106  node_count(0), shared(src.shared), shared_root(src.shared_root)
107 {
108  BOOST_FOREACH(PVVector& p, pv)
109  p.clear();
110 }
111 
112 template <class EvalT>
115 {
116  BOOST_FOREACH(MoveGenerator *p, generators)
117  dealloc(p);
118 #ifdef OSL_SMP
119  if (shared && shared.use_count() == 1)
120  NonBlockDelete::reset(shared);
121 #endif
122 }
123 
124 template <class EvalT>
127 {
128  try
129  {
130  return new MoveGenerator;
131  }
132  catch (std::bad_alloc&)
133  {
134  std::cerr << "panic. allocation of MoveGenerator failed\n";
135  throw TableFull(); // stop search anyway
136  }
137  return 0;
138 }
139 
140 template <class EvalT>
142 {
143  delete p;
144 }
145 
146 template <class EvalT>
148 {
149  const size_t cur_depth = this->curDepth();
150  while (generators.size() <= cur_depth)
151  generators.push_back(0);
152  if (generators[cur_depth] == 0)
153  generators[cur_depth] = alloc();
154  return *generators[cur_depth];
155 }
156 
157 /* ------------------------------------------------------------------------- */
158 /* Methods for alpha beta search */
159 /* ------------------------------------------------------------------------- */
160 
161 template <class EvalT>
162 template <osl::Player P>
165  bool in_pv)
166 {
167  assert(w.alpha(P) % 2);
168  assert(w.beta(P) % 2);
169  assert(alt(P) == state().turn());
170  assert(P == moved.player());
171  assert(eval::notLessThan(P, w.beta(P), w.alpha(P)));
172 
173  // Pが指した後でPの王に利きがある => 直前の手が非合法手
174  if (state().inCheck(P)) {
175  return this->minusInfty(P);
176  }
177  this->eval.update(state(), moved.move());
178  const Player Turn = PlayerTraits<P>::opponent;
179  const size_t previous_node_count = nodeCount();
180 
181  pv[this->curDepth()].clear();
182 
183  int result;
184  // 局面表が利用不可能の場合にこの関数と子孫で利用するrecord
185  // TODO: class に max_depth だけ持たせるべき
186  boost::scoped_ptr<SimpleHashRecord> record_if_unavailable;
187  int alloc_limit = curLimit(), memory1000 = lastMemoryUseRatio1000();
188  const SimpleHashRecord *parent = hasLastRecord(1) ? lastRecord(1) : 0;
189  const uint64_t table_use = this->table->memoryUse();
190  if (table_use*8 > OslConfig::memoryUseLimit()
191  && memory1000 > 300 && (root_limit >= 1600 || memory1000 > 500)
192  && ! in_pv && ! state().inCheck() && (!parent||! parent->inCheck()))
193  {
194  if (table_use*6 > OslConfig::memoryUseLimit())
195  alloc_limit -= std::max(root_limit - 1400, 200);
196  else
197  alloc_limit -= std::max((root_limit - 1400)*3/4, 0);
198  if (memory1000 > 900)
199  alloc_limit -= 400;
200  else if (root_limit >= 1600 && memory1000 > 800)
201  alloc_limit -= 200;
202  else if (root_limit >= 1600 && memory1000 > 700)
203  alloc_limit -= 100;
204  alloc_limit = std::max(0, alloc_limit);
205  }
206  SimpleHashRecord *record
207  = this->table->allocate(currentHash(), alloc_limit);
208  const bool has_table_record = record;
209  if (! record) {
210  record_if_unavailable.reset(new SimpleHashRecord());
211  record = record_if_unavailable.get(); // memorize してはいけない
212  }
213  setCurrentRecord(record);
214  record->setInCheck(state().inCheck());
215 #if 0
216  // harmful now
217  if (pass_count.loopByBothPass()) {
218  return quiesce<Turn>(w);
219  }
220 #endif
221  ++node_count;
222  int consumption = moved.logProb();
223 
224  // hash の手がない場合のiid
225  if (in_pv
226  && (! record->bestMove().isNormal())) {
227  assert(node_type[this->curDepth()] == PvNode);
228  for (int limit = curLimit() - 200+1; limit > consumption+200;
229  limit -= 200) {
230  searchAllMoves<Turn>(moved.move(), limit,
231  record, w);
232  if (! record->bestMove().validMove()) {
233  Move quiesce_best = record->qrecord.bestMove();
234  if (quiesce_best.isNormal())
235  record->setBestMove(quiesce_best, 200);
236  }
237  }
238  }
239  if (! in_pv) {
240  // null window search
241  if (node_type[this->curDepth()] == PvNode)
242  node_type[this->curDepth()] = AllNode;
243  result = searchAllMoves<Turn>
244  (moved.move(), consumption, record,
245  Window(w.alpha(P), w.alpha(P)));
246  } else {
247  // normal search
248  assert(node_type[this->curDepth()] == PvNode);
249  result = searchAllMoves<Turn>(moved.move(), consumption,
250  record, w);
251  }
252  bool extended = false;
253  // extension if the alpha value is updated
254  if (eval::betterThan(P, result, w.alpha(P))) {
255  const SimpleHashRecord *parent = lastRecord(1);
256  int consumption_here = consumption+1;
257  const int re_search = 100;
258  if (! w.null() && (! in_pv || consumption > re_search))
259  consumption_here = std::min(consumption, re_search);
260  else if (consumption > re_search
262  || record->threatmate().mayHaveCheckmate(P)))
263  consumption_here = re_search;
264  else if (consumption > 150
265  && ((parent && parent->inCheck())
266  || state().hasEffectAt(P, state().kingSquare(alt(P)))))
267  consumption_here = 150;
268  if (consumption_here <= consumption) {
269  node_type[this->curDepth()] = PvNode;
270  extended = true;
271  ext_limit.add(consumption - consumption_here);
272  result = searchAllMoves<Turn>(moved.move(), consumption_here, record, w);
273  }
274  }
275  ext.add(extended);
276 
277  if (has_table_record)
278  record->addNodeCount(nodeCount() - previous_node_count);
279  return result;
280 }
281 
282 template <class EvalT>
283 template <osl::Player Turn>
285 searchAllMoves(Move m, int limit_consumption, SimpleHashRecord *record,
286  Window w)
287 {
288  if (! w.null())
289  assert(node_type[this->curDepth()] == PvNode);
291  this->recorder.tryMove(MoveLogProb(m, limit_consumption),
292  w.alpha(P), curLimit());
293  subLimit(limit_consumption);
294 
295  const int result = searchAllMoves<Turn>(record, w);
296 
297  addLimit(limit_consumption);
298  this->recorder.recordValue(MoveLogProb(m, limit_consumption),
299  result,eval::betterThan(P, result, w.alpha(P)),
300  curLimit());
301  return result;
302 }
303 
304 template <class EvalT>
305 template <osl::Player P>
307 testThreatmate(SimpleHashRecord *record, bool in_pv)
308 {
309  if ((! record->inCheck())
310  && (! (record && record->threatmate().isThreatmate(P)))
311  && (in_pv || (this->curDepth() > 0
312  && this->node_type[this->curDepth()-1] != CutNode))
313  && tryThreatmate())
314  {
315  int threatmate_limit = 0;
316  const SimpleHashRecord *parent = lastRecord(1);
317  size_t node_count = record->nodeCount();
318  if (parent)
319  node_count = std::max(node_count, parent->nodeCount()/32);
320  threatmate_limit = 4500-this->curDepth()*1000;
321  int threatmate_max = 0;
322  if ((node_count >= 1000 && this->recorder.checkmateRatio() < 0.5)
323  || (node_count >= 200
324  && (state().king8Info(P).libertyCount() == 0
325  || state().king8Info(P).dropCandidate()
326  || state().king8Info(P).template hasMoveCandidate<PlayerTraits<P>::opponent>(state()))))
327  threatmate_max = 100;
328  threatmate_limit = std::max(threatmate_limit, threatmate_max);
329  if (! in_pv)
330  threatmate_limit /= 2;
331  if (root_limit < 800)
332  threatmate_limit /= 2;
333 #ifdef EXPERIMENTAL_QUIESCE
334  if (curLimit() <= 400)
335  threatmate_limit = 1;
336  else if (curLimit() <= 500)
337  threatmate_limit /= 16;
338  else if (curLimit() <= 600)
339  threatmate_limit /= 4;
340 #endif
341 
342  if (curLimit() >= this->table->minimumRecordLimit())
343  {
344  threatmate_limit = record->qrecord.threatmateNodesLeft(threatmate_limit);
345  }
346  else
347  {
348  threatmate_limit /= 2; // for safety against multiple calls
349  }
350 
351  Move threatmate_move;
352  this->recorder.gotoCheckmateSearch(state(), threatmate_limit);
353 #ifdef CHECKMATE_COUNT
354  size_t count = checkmateSearcher().totalNodeCount();
355 #endif
356  bool threatmate
357  = isThreatmateState<P>(threatmate_limit, threatmate_move);
358 #ifdef CHECKMATE_COUNT
359  count_threatmate += checkmateSearcher().totalNodeCount() - count;
360 #endif
361  if (threatmate_limit > 100) {
362  updateCheckmateCount();
363  testStop();
364  }
365  this->recorder.backFromCheckmateSearch();
366  if (!threatmate && threatmate_limit == 0
367  && record->qrecord.threatmateNodesLeft(2)) {
368  threatmate = isThreatmateStateShort<P>(2, threatmate_move);
369  }
370  if (threatmate)
371  {
372  record->threatmate().setThreatmate(P, threatmate_move);
373  }
374  }
375 }
376 
377 template <class EvalT>
378 template <osl::Player P>
380 tryCheckmate(SimpleHashRecord *record, bool in_pv, Move& checkmate_move)
381 {
382  int checkmate_limit = 1;
383  if (! in_pv) {
384  const SimpleHashRecord *parent = lastRecord(1);
385  if (! (record->threatmate().mayHaveCheckmate(alt(P))
386  || (parent && parent->threatmate().maybeThreatmate(alt(P)))))
387  return false;
388  // simulation only
389  }
390  if (in_pv && root_limit >= 500+this->rootLimitBias()) {
391  int depth = this->curDepth();
392  if (root_limit >= 700+this->rootLimitBias() && depth <= 3) {
393  if (/*record_memorize &&*/ (depth <= 1))
394  checkmate_limit = checkmate::limitToCheckCount(3500);
395  else if (/* record_memorize &&*/ (depth == 2))
396  checkmate_limit = 1000;
397  else if (/* record_memorize &&*/ (depth == 3))
398  checkmate_limit = 200;
399  }
400  else if (((root_limit - curLimit()) <= 500) || (depth <= 5))
401  {
402  assert(static_cast<unsigned int>(curLimit()) < 4096);
403  checkmate_limit = checkmate::limitToCheckCount(std::max(0,curLimit()-200-this->rootLimitBias()));
404  }
405  const SimpleHashRecord *parent = lastRecord(1);
406  if (record->threatmate().mayHaveCheckmate(alt(P))
407  || (parent && parent->threatmate().maybeThreatmate(alt(P))))
408  checkmate_limit += std::max(100, checkmate_limit);
409  else
410  checkmate_limit = std::min((long)record->nodeCount()/2, (long)checkmate_limit);
411  if (root_limit < 800)
412  checkmate_limit /= 2;
413  }
414  if (curLimit() >= this->table->minimumRecordLimit())
415  {
416  // 詰将棋はある程度深さが増えたときだけ呼ぶ
417  checkmate_limit = record->qrecord.checkmateNodesLeft(checkmate_limit);
418  if (checkmate_limit <= 0)
419  return false;
420  }
421  else
422  {
423  checkmate_limit /= 2; // for safety against multiple calls
424  }
425 
426  // 相手を詰ますことを考える
427 #ifdef CHECKMATE_COUNT
428  size_t count = checkmateSearcher().totalNodeCount();
429 #endif
430  this->recorder.gotoCheckmateSearch(state(), checkmate_limit);
431  const bool win = isWinningState<P>
432  (checkmate_limit, checkmate_move);
433  if (checkmate_limit > 100)
434  updateCheckmateCount();
435  this->recorder.backFromCheckmateSearch();
436 #ifdef CHECKMATE_COUNT
437  checkmate_before += checkmateSearcher().totalNodeCount() - count;
438 #endif
439  if (this->root_limit >= 1600 && checkmate_limit >= 100)
440  this->checkmate_searcher->runGC(this->table->isVerbose(),
441  lastMemoryUseRatio1000());
442  return win;
443 }
444 
445 template <class EvalT>
446 template <osl::Player P>
448 tryCheckmateAgain(SimpleHashRecord *record, Move& checkmate_move,
449  int node_count, int best_value)
450 {
451  int checkmate_limit = 1;
452  if (record->threatmate().maybeThreatmate(P)) {
453  if (EvalTraits<P>::betterThan(this->eval.captureValue(newPtypeO(P,KING)), best_value))
454  checkmate_limit = node_count / 2; // この局面は必死 or 詰将棋以外のalt(P)の勝
455  else
456  checkmate_limit = node_count / 8;
457  checkmate_limit += 100;
458  if (this->recorder.checkmateRatio() < 0.5) {
459  int checkmate_importance_wrt_root = this->recorder.searchNodeCount()/2
460  + this->recorder.checkmateCount()/8;
461  for (int i=0; i<this->curDepth(); ++i) {
462  if (this->in_pv[i])
463  checkmate_importance_wrt_root = checkmate_importance_wrt_root*7/8;
464  else
465  checkmate_importance_wrt_root /= 7;
466  }
467  checkmate_limit = std::max(checkmate_limit, checkmate_importance_wrt_root);
468  }
469  } else if (record->threatmate().mayHaveCheckmate(alt(P))) {
470  checkmate_limit = countCheckAfterThreatmate(alt(P),2)*320 + 100;
471 #ifdef MORE_CHECKMATE_IF_CAPTURE_MAJOR
472  if (lastMove().isNormal() && isMajorNonPieceOK(lastMove().capturePtype())
473  && ! state().hasEffectAt(P, lastMove().to()))
474  checkmate_limit += 20000;
475 #endif
476  }
477  if (curDepth() == 1 && hasLastRecord(1)) {
478  const SimpleHashRecord *parent = lastRecord(1); // root
479  if (parent->inCheck() || parent->threatmate().maybeThreatmate(alt(P)))
480  checkmate_limit = std::max(checkmate_limit, (int)parent->nodeCount()/2+parent->checkmateNodes());
481  }
482 
483  // adjustment by time
484  int checkmate_afford = this->nodeAffordable();
485 #ifdef OSL_SMP
486  checkmate_afford *= 1.5 / shared->max_threads;
487 #endif
488  if (checkmate_limit > 100 && checkmate_limit > checkmate_afford) {
489 #ifndef NDEBUG
490  if (checkmate_afford > 0 && this->timeAssigned().standard.toSeconds() >= 10.0)
491  std::cerr << "adjust checkmate near timeover " << checkmate_limit << " => " << checkmate_afford << "\n";
492 #endif
493  checkmate_limit = checkmate_afford;
494  }
495 
496  if (true /*record_memorize*/)
497  checkmate_limit = record->qrecord.checkmateNodesLeft(checkmate_limit);
498 
499 #ifdef CHECKMATE_COUNT
500  size_t count = checkmateSearcher().totalNodeCount();
501 #endif
502  this->recorder.gotoCheckmateSearch(state(), checkmate_limit);
503  const bool win = isWinningState<P>
504  (checkmate_limit, checkmate_move);
505  if (checkmate_limit > 100)
506  updateCheckmateCount();
507  this->recorder.backFromCheckmateSearch();
508 #ifdef CHECKMATE_COUNT
509  checkmate_after += checkmateSearcher().totalNodeCount() - count;
510 #endif
511  if (this->root_limit >= 1600 && checkmate_limit >= 100)
512  this->checkmate_searcher->runGC(this->table->isVerbose(),
513  lastMemoryUseRatio1000());
514  return win;
515 }
516 
517 template <class EvalT>
518 bool osl::search::
520 {
521  return ! record->inCheck()
522  && ! record->threatmate().maybeThreatmate(P);
523 }
524 
525 template <class EvalT>
526 template <osl::Player P>
529 {
530  MoveGenerator& generator = makeGenerator();
531  SimpleHashRecord *record = lastRecord();
532  switch (this->move_type[this->curDepth()]) {
533  case common_t::HASH:
534  {
535  if (curLimit() < this->leafLimit()) {
536  this->move_type[this->curDepth()] = common_t::FINISH;
537  break;
538  }
539  this->move_type[this->curDepth()] = common_t::TACTICAL;
540  MoveLogProb best_move_in_table = record->bestMove();
541  assert(curLimit() > 0);
542  generator.init<eval_t>(curLimit(), record, this->eval, state(),
543  node_type[this->curDepth()] != CutNode,
544  best_move_in_table.move());
545  if (best_move_in_table.validMove() &&
546  this->validTableMove(state(), best_move_in_table, curLimit())) {
547  if (this->in_pv[this->curDepth()]
548  || best_move_in_table.move().capturePtype())
550  else
551  best_move_in_table.setLogProbAtMost(state().inCheck() ? 120 : 150);
552  return best_move_in_table;
553  }
554  }
555  // fall through
556  // TODO: 打歩詰めはここでチェックすると早そう
557  case common_t::TACTICAL:
558  {
559  MoveLogProb m = generator.nextTacticalMove<P>(*this);
560  if (m.validMove())
561  return m;
562  // fall through
563  this->move_type[this->curDepth()] = common_t::KILLER;
564  this->killers[this->curDepth()].clear();
565  if ((! record->inCheck())
566  && ! record->threatmate().maybeThreatmate(P)
567  && (curLimit() >= 300)) {
568  MoveVector killer_moves; // TODO: 効率化
569  getKillerMoves(killer_moves);
570  BOOST_FOREACH(Move move, killer_moves) {
571  assert(this->killers[this->curDepth()].size() < this->killers[this->curDepth()].capacity());
572  this->killers[this->curDepth()].push_back(move);
573  }
574  std::reverse(this->killers[this->curDepth()].begin(), this->killers[this->curDepth()].end());
575  }
576  }
577  case common_t::KILLER:
578  {
579  typename common_t::killer_t& killers = this->killers[this->curDepth()];
580  if (! killers.empty()) {
581  Move m = killers[killers.size()-1];
582  killers.pop_back();
583  return MoveLogProb(m, 300);
584  }
585  // fall through
586  this->move_type[this->curDepth()] = common_t::PASS;
587  }
588  case common_t::PASS:
589  assert(record->inCheck() == state().inCheck());
590  this->move_type[this->curDepth()] = common_t::ALL;
591  if (tryPass(record, P)) {
592  const int pass_consumption = (curLimit() >= 800) ? 300 : 200;
593  return MoveLogProb(Move::PASS(P), pass_consumption);
594  }
595  // TODO: pass の後の最善手
596  // fall through
597  case common_t::ALL:
598  {
599  MoveLogProb m = generator.nextMove<P>(*this);
600  if (m.validMove())
601  return m;
602  this->move_type[this->curDepth()] = common_t::FINISH;
603  }
604  default:
605  assert(this->move_type[this->curDepth()] == common_t::FINISH);
606  }
607  return MoveLogProb();
608 }
609 
610 template <class EvalT>
611 template <osl::Player P>
614 {
615 #ifndef NDEBUG
616  checkPointSearchAllMoves();
617 #endif
618  assert(P == state().turn());
619  search_assert(w.isConsistent(), lastMove());
620  assert(curLimit() >= 0);
621 
622  assert(hasLastRecord(1));
623  const SimpleHashRecord *parent = lastRecord(1);
624 #ifndef DONT_USE_CHECKMATE
625  const int node_count_at_beginning = nodeCount();
626 #endif
627 #if (! defined OSL_USE_RACE_DETECTOR) && (! defined MINIMAL)
628  depth_node_count[this->curDepth()]++;
629 #endif
630  this->move_type[this->curDepth()] = common_t::INITIAL;
631  const bool in_pv = this->in_pv[this->curDepth()] = ! w.null();
632 
633  // テーブルにある値を調べる
634  if (record) {
635  if (in_pv) {
637  int lower_bound = record->lowerBound();
638  if (this->isWinValue(P, lower_bound)
640  && record->upperBound() == lower_bound))
641  return lower_bound;
642  }
644  int upper_bound = record->upperBound();
645  if (this->isWinValue(alt(P), upper_bound))
646  return upper_bound;
647  }
648  }
649  else { // ! in_pv
650  int table_value = 0;
651  if (record->hasGreaterLowerBound<P>(curLimit(), w.alpha(P),
652  table_value)) {
653  assert(eval::isConsistentValue(table_value));
654  w.alpha(P) = table_value + EvalTraits<P>::delta;
655  if (EvalTraits<P>::betterThan(table_value, w.beta(P))) {
656  this->recorder.tableHitLowerBound(P, table_value, w.beta(P), curLimit());
657  return table_value;
658  }
659  }
660  if (record->hasLesserUpperBound<P>(curLimit(), w.beta(P), table_value)) {
661  assert(eval::isConsistentValue(table_value));
662  w.beta(P) = table_value - EvalTraits<P>::delta;
663  if (EvalTraits<P>::betterThan(w.alpha(P), table_value))
664  {
665  this->recorder.tableHitUpperBound(P, table_value, w.alpha(P), curLimit());
666  return table_value;
667  }
668  }
669  }
670 
671  Move checkmate_move=Move::INVALID();
672  if ((!record->inCheck())
673  && record->qrecord.checkmateNodesLeft(1)
674  && isWinningStateShort<P>(2, checkmate_move))
675  {
676  this->recordWinByCheckmate(P, record, checkmate_move);
677  return this->winByCheckmate(P);
678  }
679 #ifndef DONT_USE_CHECKMATE
680  assert(record);
681  // try simulation or simple checkmate search
682  int additional_limit = 0; // simulation only
683  if (parent && parent->threatmate().maybeThreatmate(alt(P)))
684  {
685  additional_limit = std::max(100, parent->qrecord.threatmateNodes()/8);
686  additional_limit = record->qrecord.checkmateNodesLeft(additional_limit);
687  }
688  this->recorder.gotoCheckmateSearch(state(), additional_limit);
689  const bool win = isWinningState<P>(additional_limit, checkmate_move);
690  updateCheckmateCount();
691  this->recorder.backFromCheckmateSearch();
692  if (win) {
693  assert(checkmate_move.isValid());
694  this->recordWinByCheckmate(P, record, checkmate_move);
695  return this->winByCheckmate(P);
696  }
697 #endif
698  }
699 
700  search_assert(w.isConsistent(), lastMove());
701  const int initial_alpha = w.alpha(P);
702 
703 #ifndef DONT_USE_CHECKMATE
704  // 詰めろを考える
705  testThreatmate<P>(record, in_pv);
706 #endif
707  // 探索前に ThreatmateState を設定
708  record->qrecord.updateThreatmate(P, (parent ? &(parent->threatmate()) : 0),
709  state().inCheck());
710 
711  MoveLogProb best_move; // invalidated
712  int best_value = this->minusInfty(P);
713  int tried_moves = 0;
714  int alpha_update = 0;
715  int last_alpha_update = 0;
716 #if (defined OSL_SMP)
717  int last_smp_idle = 0;
718 # if (! defined OSL_SMP_NO_SPLIT_INTERNAL)
719 # if (! defined NDEBUG)
720  bool already_split = false;
721 # endif
722 # endif
723 #endif
724 
725  // the first move
726  MoveLogProb m = nextMove<P>();
727  ++tried_moves;
728  if (! m.validMove() || m.logProb() > curLimit()) {
729  goto move_generation_failure;
730  }
731 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
732  int first_move_node;
733 #endif
734  {
735 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
736  const int previous_node_count = nodeCount();
737 #endif
738  assert(eval::betterThan(P, w.alpha(P), best_value));
739  const int result = alphaBetaSearch<P>(m, w, in_pv);
740  if (eval::betterThan(P, result, best_value)) {
741  best_value = result;
742  best_move = m;
743  if (eval::betterThan(P, best_value, w.alpha(P))) {
744  w.alpha(P) = result + EvalTraits<P>::delta;;
745  assert(best_move.validMove());
746  ++alpha_update;
747  last_alpha_update = 1;
748  if (eval::betterThan(P, result, w.beta(P))) {
749  mpn_cut.add(tried_moves);
750  if (this->move_type[this->curDepth()] >= common_t::ALL) {
751  setKillerMove(best_move.move());
752  if (best_move.isNormal()
753  && ! best_move.move().isCapture())
754  {
755  const int d = (curLimit()+200)/100;
756  this->historyTable().add(best_move.move(), d*d);
757  }
758  }
759  assert(best_move.validMove());
760  assert(! this->isWinValue(alt(P), best_value));
761  goto register_table;
762  } else {
763  if (in_pv)
764  makePV(m.move());
765  }
766  }
767  }
768 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
769  first_move_node = nodeCount() - previous_node_count;
770 #endif
771  }
772  testStop();
773 
774 #ifndef DONT_USE_CHECKMATE
775  if (in_pv)
776  {
777  Move checkmate_move;
778  if (tryCheckmate<P>(record, in_pv, checkmate_move)) {
779  assert(checkmate_move.isValid());
780  best_value= this->winByCheckmate(P);
781  this->recordWinByCheckmate(P, record, checkmate_move);
782  return best_value;
783  }
784  }
785 #endif
786  search_assert(w.isConsistent(), lastMove());
787  if (curLimit() < this->leafLimit())
788  goto move_generation_failure;
789  while (true) {
790 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
791  const bool prefer_split = shared && curLimit() >= shared->split_min_limit
792  && (curLimit() >= 600+this->rootLimitBias()
793  // || (curLimit() >= 400 && this->curDepth() < 2)
794  || (first_move_node >= 30000));
795  try {
796  if (prefer_split) {
797  int cur_smp_idle;
798  {
799 # ifdef OSL_USE_RACE_DETECTOR
800  boost::mutex::scoped_lock lk(shared->lock_smp);
801 #endif
802  cur_smp_idle = shared->smp_idle;
803  }
804  if (cur_smp_idle > last_smp_idle) {
805  last_smp_idle = cur_smp_idle;
806  assert(! already_split);
807 # if (! defined NDEBUG)
808  already_split = true;
809 # endif
810  if (examineMovesOther<P>(w, best_move, best_value, tried_moves,
811  alpha_update, last_alpha_update)) {
812  assert(best_move.validMove());
813  assert(best_move.player() == P);
814  if (this->move_type[this->curDepth()] >= common_t::ALL) {
815  setKillerMove(best_move.move());
816  if (best_move.isNormal()
817  && ! best_move.move().isCapture())
818  {
819  const int d = (curLimit()+200)/100;
820  this->historyTable().add(best_move.move(), d*d);
821  }
822  }
823  mpn_cut.add(tried_moves);
824  goto register_table;
825  }
826  goto all_moves_done;
827  }
828  }
829  }
830  catch(AlphaBeta2ParallelCommon::SplitFailed&) {
831 # if (! defined NDEBUG)
832  already_split = false;
833 # endif
834  // fall through
835  }
836 #endif
837  MoveLogProb m = nextMove<P>();
838  if (! m.validMove())
839  break;
840  ++tried_moves;
841 
842  assert(eval::betterThan(P, w.alpha(P), best_value));
843  const int result = alphaBetaSearch<P>(m, w, in_pv && ! best_move.validMove());
844  if (eval::betterThan(P, result, best_value)) {
845  best_value = result;
846  best_move = m;
847  if (eval::betterThan(P, best_value, w.alpha(P))) {
848  w.alpha(P) = result + EvalTraits<P>::delta;;
849  assert(best_move.validMove());
850  ++alpha_update;
851  last_alpha_update = tried_moves;
852  if (eval::betterThan(P, result, w.beta(P))) {
853  assert(best_move.validMove());
854  if (this->move_type[this->curDepth()] >= common_t::ALL) {
855  setKillerMove(best_move.move());
856  if (best_move.isNormal()
857  && ! best_move.move().isCapture())
858  {
859  const int d = (curLimit()+200)/100;
860  this->historyTable().add(best_move.move(), d*d);
861  }
862  }
863  mpn_cut.add(tried_moves);
864  goto register_table;
865  } else {
866  if (in_pv)
867  makePV(m.move());
868  }
869  }
870  }
871  }
872 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
873 all_moves_done:
874 #endif
875  if (tried_moves == 1 && tryPass(record, P)) {
876  // goto quiescence search if tried move is only null move
877  goto move_generation_failure;
878  }
879  mpn.add(tried_moves);
880  if (alpha_update) {
881  this->alpha_update.add(alpha_update);
882  this->last_alpha_update.add(last_alpha_update);
883  }
884  // 宣言勝
885  if (((this->curDepth() % 2) == 0 || OslConfig::usiMode())
886  && EnterKing::canDeclareWin<P>(state())) {
887  best_value = this->brinkmatePenalty(alt(P), std::max(1,16-this->curDepth())*256)
888  + this->eval.value();
889  record->setAbsoluteValue(Move::DeclareWin(), best_value,
891  return best_value;
892  }
893  if (record) {
894  // もう一度,相手を詰ますことを考える
895 #ifndef DONT_USE_CHECKMATE
896  Move checkmate_move=Move::INVALID();
897  if (tryCheckmateAgain<P>(record, checkmate_move,
898  nodeCount() - node_count_at_beginning,
899  best_value)) {
900  assert(checkmate_move.isValid());
901  best_value= this->winByCheckmate(P);
902  this->recordWinByCheckmate(P, record, checkmate_move);
903  return best_value;
904  }
905 #endif
906  }
907 register_table:
908  assert(best_value == this->minusInfty(P) || best_move.validMove());
909  assert(eval::isConsistentValue(best_value));
910  if (this->isWinValue(alt(P), best_value))
911  {
912  // TODO: 直前の着手が(やけくそ)王手の連続だった場合
913  // 必死ではなくて詰扱いの方が良い可能性はある
914  best_value = this->brinkmatePenalty(P, std::max(1,16-this->curDepth())*256) + this->eval.value();
915 
916  // (この深さでは)上限==下限
917  record->setAbsoluteValue(best_move, best_value, curLimit());
918  return best_value;
919  }
920  else if (EvalTraits<P>::betterThan(w.alpha(P), initial_alpha)) {
921  if (best_move.validMove()) {
922  assert(best_value % 2 == 0);
923  record->setLowerBound(P, curLimit(), best_move, best_value);
924  }
925  }
926  if (EvalTraits<P>::betterThan(w.beta(P), best_value)) {
927  if (best_move.validMove())
928  record->setUpperBound(P, curLimit(), best_move, best_value);
929  }
930  return best_value;
931 move_generation_failure:
932  pv[this->curDepth()].clear();
933  // 手を生成できなかった
934  // limit が 200 未満だった場合と,以上だったが move generator が limit 以下の手を生成できなかった場合ここに来る
935  best_value = quiesce<P>(w);
936  if (record)
937  {
938  if (EvalTraits<P>::betterThan(best_value, initial_alpha)) {
939  if (EvalTraits<P>::betterThan(w.beta(P), best_value)) {
940  record->setAbsoluteValue(MoveLogProb(), best_value, curLimit());
941  } else {
942  record->setLowerBound(P, curLimit(), MoveLogProb(), best_value);
943  }
944  }
945  else
946  {
947  assert(EvalTraits<P>::betterThan(w.beta(P), best_value));
948  record->setUpperBound(P, curLimit(), MoveLogProb(), best_value);
949  }
950  }
951  assert(eval::isConsistentValue(best_value));
952  return best_value;
953 }
954 
955 template <class EvalT>
956 template <osl::Player P>
959 {
960 #ifdef EXPERIMENTAL_QUIESCE
961  return quiesceExp<P>(w);
962 #else
963  return quiesceStable<P>(w);
964 #endif
965 }
966 
967 template <class EvalT>
968 template <osl::Player P>
971 {
972  testStop();
973  initPV();
974 
975  typedef QuiescenceSearch2<eval_t> qsearcher_t;
976  qsearcher_t qs(*this, *this->table);
977  Move last_move = lastMove();
978  if (last_move.isInvalid())
979  last_move = Move::PASS(alt(P));
980  assert(w.alpha(P) % 2);
981  assert(w.beta(P) % 2);
982 #ifdef CHECKMATE_COUNT
983  size_t count = checkmateSearcher().totalNodeCount();
984 #endif
985  const int result = qs.template search<P>(w.alpha(P), w.beta(P), this->eval, last_move, 4);
986  node_count += qs.nodeCount();
987  this->recorder.addQuiescenceCount(qs.nodeCount());
988 #ifdef CHECKMATE_COUNT
989  quiesce_checkmate += checkmateSearcher().totalNodeCount() - count;
990 #endif
991 
992  assert(result % 2 == 0);
993  return result;
994 }
995 
996 template <class EvalT>
997 template <osl::Player P>
1000 {
1001  testStop();
1002 
1003  SimpleHashRecord *record = lastRecord();
1004  assert(record);
1005  Move best_move;
1006  const int qdepth = 4;
1007  const int previous_node_count = nodeCount();
1008 
1009  int result =
1010  quiesceRoot<P>(w, qdepth, best_move, record->threatmate());
1011 
1012  const size_t qnode = nodeCount() - previous_node_count;
1013  this->recorder.addQuiescenceCount(qnode);
1014  record->qrecord.setLowerBound(qdepth, result, best_move);
1015  return result;
1016 }
1017 
1018 template <class EvalT>
1019 template <osl::Player P>
1020 struct osl::search::AlphaBeta2Tree<EvalT>::NextQMove
1021 {
1024  const int depth;
1025  int *result;
1027  NextQMove(AlphaBeta2Tree *s, Window w, int d, int *r,
1029  : searcher(s), window(w), depth(d), result(r), threatmate(t) {
1030  }
1031  void operator()(Square /*last_to*/) {
1032  searcher->eval.update(searcher->state(), searcher->lastMove());
1033  *result =
1034  searcher->quiesce<P>(window, depth, threatmate);
1035  }
1036 };
1037 
1038 template <class EvalT>
1039 template <osl::Player P>
1041 quiesceWithMove(Move move, Window& w, int depth_left, Move& best_move, int& best_value,
1042  const DualThreatmateState& threatmate)
1043 {
1044  // TODO: futility margin
1045  const bool in_pv = ! w.null();
1046  int result;
1047  typedef NextQMove<PlayerTraits<P>::opponent> next_t;
1048  next_t helper(this, w, depth_left, &result, threatmate);
1049 
1050  const HashKey new_hash = currentHash().newHashWithMove(move);
1051  const eval_t old_eval = this->eval;
1052  doUndoMoveOrPass<P,next_t>(new_hash, move, helper);
1053  this->eval = old_eval;
1054 
1055  if (eval::betterThan(P, result, best_value)) {
1056  best_value = result;
1057  best_move = move;
1058  if (eval::betterThan(P, best_value, w.alpha(P))) {
1059  w.alpha(P) = result + EvalTraits<P>::delta;
1060  if (in_pv)
1061  makePV(best_move);
1062  if (eval::betterThan(P, result, w.beta(P))) {
1063  return true;
1064  }
1065  }
1066  }
1067  return false;
1068 }
1069 
1070 template <class EvalT>
1071 template <osl::Player P>
1073 quiesceRoot(Window w, int depth_left, Move& best_move, DualThreatmateState threatmate)
1074 {
1075  assert(! state().inCheck(alt(P)));
1076 
1077  initPV();
1078  // depth_node_count_quiesce[this->curDepth()]++;
1079  // ++node_count;
1080 
1081  SimpleHashRecord& record = *lastRecord();
1082  assert(record.inCheck() == state().inCheck());
1083  assert(depth_left > 0);
1084 
1085  int best_value = this->minusInfty(P);
1086  // stand pat
1087  if (! record.inCheck()) {
1088  if (! threatmate.maybeThreatmate(P)) {
1089  best_value = this->eval.value();
1090  } else {
1091  const int value = this->eval.value() + this->threatmatePenalty(P);
1092  best_value = EvalTraits<P>::max(best_value, value);
1093  }
1094  best_move = Move::PASS(P);
1095  if (EvalTraits<P>::betterThan(best_value, w.alpha(P))) {
1096  if (EvalTraits<P>::betterThan(best_value, w.beta(P)))
1097  return best_value;
1098  w.alpha(P) = best_value + EvalTraits<P>::delta;
1099  }
1100  }
1101 
1102  Move prev_best = record.qrecord.bestMove();
1103  MoveGenerator& generator = makeGenerator();
1104  generator.init(200, &record, this->eval, state(),
1105  w.alpha(P) == w.beta(P),
1106  prev_best, true);
1107  int tried_moves = 0;
1108  // previous 最善手を試す
1109  if (prev_best.isNormal()) {
1110  ++tried_moves;
1111  if (quiesceWithMove<P>(prev_best, w, depth_left-1, best_move, best_value,
1112  threatmate))
1113  goto finish;
1114  }
1115 
1116 
1117  // captures or king escape
1118  for (MoveLogProb m = generator.nextTacticalMove<P>(*this);
1119  m.validMove(); m = generator.nextTacticalMove<P>(*this)) {
1120  ++tried_moves;
1121  if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1122  threatmate))
1123  goto finish;
1124  }
1125  for (MoveLogProb m = generator.nextMove<P>(*this);
1126  m.validMove(); m = generator.nextMove<P>(*this)) {
1127  ++tried_moves;
1128  if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1129  threatmate))
1130  goto finish;
1131  }
1132 
1133  // pawn drop foul?
1134  if (record.inCheck()) {
1135  if (tried_moves == 0) {
1136  if (lastMove().isNormal() && lastMove().ptype() == PAWN && lastMove().isDrop())
1137  return this->winByFoul(P);
1138  return this->winByCheckmate(alt(P));
1139  }
1140  goto finish;
1141  }
1142 finish:
1143  return best_value;
1144 }
1145 
1146 template <class EvalT>
1147 template <osl::Player P>
1149 quiesce(Window w, int depth_left, DualThreatmateState parent_threatmate)
1150 {
1151  if (state().inCheck(alt(P))) {
1152  return this->minusInfty(alt(P));
1153  }
1154 
1155  initPV();
1156 #ifndef MINIMAL
1157  depth_node_count_quiesce[this->curDepth()]++;
1158 #endif
1159  ++node_count;
1160 
1161  SimpleHashRecord record;
1162  record.setInCheck(state().inCheck());
1163 
1164  DualThreatmateState threatmate;
1165  threatmate.updateInLock(P, &parent_threatmate, record.inCheck());
1166 
1167  int best_value = this->minusInfty(P);
1168  // TODO: 玉の回りのtakeback延長
1169  if (depth_left <= 0) {
1170  if (record.inCheck()) {
1171  if (lastMove().isCapture())
1172  depth_left +=2;
1173  else
1174  depth_left = 0;
1175  }
1176  else if (threatmate.maybeThreatmate(P)) {
1177  if (threatmate.mayHaveCheckmate(alt(P))) {
1178  Move checkmate_move;
1179  bool win = isWinningState<P>(10, checkmate_move);
1180  if (win)
1181  return this->winByCheckmate(P);
1182  }
1183  return this->eval.value() + this->threatmatePenalty(P);
1184  }
1185  else {
1186  if (threatmate.mayHaveCheckmate(alt(P)))
1187  return this->eval.value() + this->threatmatePenalty(alt(P));
1188  if (ImmediateCheckmate::hasCheckmateMove<P>(state()))
1189  return this->winByCheckmate(P);
1191  return this->eval.value() + this->threatmatePenalty(P);
1192  return this->eval.value();
1193  }
1194  }
1195 
1196  if (! record.inCheck()) {
1197  if (ImmediateCheckmate::hasCheckmateMove<P>(state())) {
1198  return this->winByCheckmate(P);
1199  }
1200  }
1201  if (threatmate.mayHaveCheckmate(alt(P))) {
1202  Move checkmate_move;
1203  bool win = isWinningState<P>(10, checkmate_move);
1204  if (win)
1205  return this->winByCheckmate(P);
1206  }
1207  MoveGenerator& generator = makeGenerator();
1208  generator.init(200, &record, this->eval, state(),
1209  w.alpha(P) == w.beta(P),
1210  Move(), true);
1211  int tried_moves = 0;
1212  Move best_move;
1213  // stand pat
1214  if (! record.inCheck()) {
1215  if (! threatmate.maybeThreatmate(P)) {
1216  best_value = this->eval.value();
1217  } else {
1218  const int value = this->eval.value() + this->threatmatePenalty(P);
1219  best_value = EvalTraits<P>::max(best_value, value);
1220  }
1221  best_move = Move::PASS(P);
1222  if (EvalTraits<P>::betterThan(best_value, w.alpha(P))) {
1223  if (EvalTraits<P>::betterThan(best_value, w.beta(P)))
1224  return best_value;
1225  w.alpha(P) = best_value + EvalTraits<P>::delta;
1226  }
1227  }
1228 
1229  // captures or king escape
1230  for (MoveLogProb m = generator.nextTacticalMove<P>(*this);
1231  m.validMove(); m = generator.nextTacticalMove<P>(*this)) {
1232  ++tried_moves;
1233  if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1234  threatmate))
1235  goto finish;
1236  }
1237  for (MoveLogProb m = generator.nextMove<P>(*this);
1238  m.validMove(); m = generator.nextMove<P>(*this)) {
1239  ++tried_moves;
1240  if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1241  threatmate))
1242  goto finish;
1243  }
1244 
1245  // pawn drop foul?
1246  if (record.inCheck()) {
1247  if (tried_moves == 0) {
1248  if (lastMove().ptype() == PAWN && lastMove().isDrop())
1249  return this->winByFoul(P);
1250  return this->winByCheckmate(alt(P));
1251  }
1252  goto finish;
1253  }
1254 finish:
1255  return best_value;
1256 }
1257 
1258 template <class EvalT>
1260 {
1261 #ifdef OSL_SMP
1262  if (shared) {
1263  const size_t new_count = shared->checkmateCount();
1264  this->recorder.setCheckmateCount(new_count);
1265  return;
1266  }
1267 #endif
1268  this->recorder.setCheckmateCount
1269  (checkmateSearcher().totalNodeCount());
1270 }
1271 
1272 template <class EvalT>
1273 int
1275 rootAlpha(Player P, int last_value, Progress16 progress)
1276 {
1277  int pawns = 3;
1278  if (eval::betterThan(P, last_value, eval_t::captureValue(newPtypeO(alt(P),KING))))
1279  {
1280  pawns = 10;
1281  }
1282  else if (progress.value() <= 1)
1283  {
1284  pawns = 3;
1285  }
1286  else if (progress.value() <= 7)
1287  {
1288  pawns = 4;
1289  }
1290  else if (progress.value() <= 9)
1291  {
1292  pawns = 5;
1293  }
1294  else if (progress.value() <= 10)
1295  {
1296  pawns = 6;
1297  }
1298  else
1299  {
1300  pawns = 7;
1301  }
1302  const int width = eval_t::captureValue(newPtypeO(alt(P),PAWN))*pawns/2;
1303  return last_value - width - eval::delta(P);
1304 }
1305 
1306 template <class EvalT>
1307 int
1309 stableThreshold(Player P, int last_value)
1310 {
1311  int pawns = 3;
1312  if (eval::betterThan(P, last_value, eval_t::captureValue(newPtypeO(alt(P),KING))))
1313  pawns = 10;
1314  else if (eval::betterThan(P, eval_t::captureValue(newPtypeO(alt(P),PAWN))*2, last_value)
1315  && eval::betterThan(P, last_value, eval_t::captureValue(newPtypeO(P,PAWN))*2))
1316  pawns = 2;
1317  const int width = eval_t::captureValue(newPtypeO(alt(P),PAWN))*pawns/2;
1318  return last_value - width - eval::delta(P);
1319 }
1320 
1321 namespace osl
1322 {
1323  namespace
1324  {
1325  void find_threatmate(const SimpleHashTable& table, HashKey key,
1327  CArray<bool, search::SearchState2::MaxDepth>& threatmate)
1328  {
1329  for (size_t i=0; i<pv.size(); ++i) {
1330  key = key.newMakeMove(pv[i]);
1331  const SimpleHashRecord *record = table.find(key);
1332  threatmate[i] = record
1333  && record->threatmate().isThreatmate(key.turn());
1334  }
1335  }
1336  }
1337 }
1338 
1339 template <class EvalT>
1341 updateRootPV(Player P, std::ostream& os, int result, Move m)
1342 {
1343  boost::mutex::scoped_lock lk(OslConfig::lock_io);
1344  this->makePV(m);
1345  const int last_root_value = shared_root->root_values_for_iteration.size() ? shared_root->root_values_for_iteration.back() : 0;
1346  const int threshold = stableThreshold(P, last_root_value);
1347  bool new_stable = eval::betterThan(P, result, threshold);
1348  shared_root->last_root_value_update = result;
1349 
1350  if (new_stable && m != shared_root->last_root_move
1351  && (See::see(state(), m) < -eval::Ptype_Eval_Table.value(KNIGHT)*2
1352  || eval::betterThan(P, result, eval_t::captureValue(newPtypeO(alt(P),KING))))) {
1353  new_stable = false;
1354  }
1355  if (new_stable && shared_root->root_values_for_iteration.size() > 1) {
1356  const int last_root_value2 = shared_root->root_values_for_iteration[shared_root->root_values_for_iteration.size()-2];
1357  const int threshold2 = stableThreshold(P, last_root_value2);
1358  if (eval::betterThan(P, threshold2, result)
1359  && eval::betterThan(P, last_root_value2, last_root_value))
1360  new_stable = false;
1361  }
1362  this->shared_root->last_pv.push_back(RootPV(root_limit, pv[0], result));
1363  this->setStable(new_stable);
1364 #ifndef GPSONE
1365  if (this->hasMonitor() && !this->prediction_for_speculative_search) {
1366  const double scale = OslConfig::usiOutputPawnValue()*2.0
1367  / eval_t::captureValue(newPtypeO(alt(P),PAWN));
1368  CArray<bool, MaxDepth> threatmate = {{ 0 }};
1369  find_threatmate(*this->table, currentHash(), pv[0], threatmate);
1370  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
1371  this->monitors())
1372  monitor->showPV(root_limit/200, this->recorder.allNodeCount(),
1373  this->elapsed(), static_cast<int>(result*scale),
1374  m, &*pv[0].begin(), &*pv[0].end(),
1375  &threatmate[0], &threatmate[0]+pv[0].size());
1376  }
1377 #endif
1378  if (this->table->isVerbose()) {
1379  showPV(os, result, m, new_stable ? ' ' : '*');
1380  }
1381 }
1382 
1383 template <class EvalT>
1386 {
1387  boost::mutex::scoped_lock lk(OslConfig::lock_io);
1388  this->makePV(m);
1389  this->shared_root->last_pv.push_back(RootPV(root_limit, pv[0], result));
1390  std::swap(*this->shared_root->last_pv.rbegin(), *(this->shared_root->last_pv.rbegin()+1));
1391 
1392  if (this->hasMonitor() && !this->prediction_for_speculative_search) {
1393  const double scale = OslConfig::usiOutputPawnValue()*2.0
1394  / eval_t::captureValue(newPtypeO(alt(P),PAWN));
1395  CArray<bool, MaxDepth> threatmate = {{ 0 }};
1396  find_threatmate(*this->table, currentHash(), pv[0], threatmate);
1397  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
1398  this->monitors())
1399  monitor->showPV(root_limit/200, this->recorder.allNodeCount(),
1400  this->elapsed(), static_cast<int>(result*scale),
1401  m, &*pv[0].begin(), &*pv[0].end(),
1402  &threatmate[0], &threatmate[0]+pv[0].size());
1403  }
1404 
1405  if (this->table->isVerbose()) {
1406  showPV(std::cerr, result, m, '&');
1407  }
1408 }
1409 
1410 template <class EvalT>
1412 showFailLow(int result, Move m) const
1413 {
1414  if (this->root_ignore_moves)
1415  std::cerr << "[" << this->root_ignore_moves->size() << "] ";
1416  std::cerr << " <" << std::setfill(' ') << std::setw(5)
1417  << static_cast<int>(result*200.0/this->eval.captureValue(newPtypeO(WHITE,PAWN)))
1418  << " " << record::csa::show(m) << "\n";
1419 }
1420 
1421 template <class EvalT>
1423 showPV(std::ostream& os, int result, Move m, char stable_char) const
1424 {
1425  assert(m.isNormal()); // do not pass at root
1426  if (this->root_ignore_moves)
1427  os << "[" << this->root_ignore_moves->size() << "] ";
1428  os << stable_char;
1429  os << " " << std::setfill(' ') << std::setw(5)
1430  << static_cast<int>(result*200.0/this->eval.captureValue(newPtypeO(WHITE,PAWN))) << " ";
1431  BOOST_FOREACH(Move m, pv[0]) {
1432  os << record::csa::show(m);
1433  }
1434  const double elapsed = this->elapsed();
1435  if (elapsed > 1.0)
1436  os << " (" << elapsed << "s, " << OslConfig::memoryUseRatio()*100.0 << "%)";
1437  os << std::endl;
1438 #ifndef MINIMAL
1439 #ifndef _WIN32
1440  if (! OslConfig::usiMode())
1441  {
1442  NumEffectState state = this->state();
1443  std::string str; str.reserve(200); str = " ";
1444  for (size_t i=0; i<pv[0].size(); ++i) {
1445  str += record::ki2::show(pv[0][i], state, i ? pv[0][i-1] : Move());
1446  state.makeMove(pv[0][i]);
1447 
1448  // threatmate?
1449  const SimpleHashRecord *record
1450  = this->table->find(HashKey(state));
1451  if (record &&
1452  record->threatmate().isThreatmate(state.turn()))
1453  str += "(" K_TSUMERO ")";
1454  }
1455  std::string converted = misc::eucToLang(str);
1456  if (! converted.empty())
1457  os << converted << std::endl;
1458  }
1459 #endif
1460 #endif
1461 
1462 #ifdef DEBUG_PV
1463  NumEffectState s = state();
1464  for (size_t i=0; i<pv[0].size(); ++i) {
1465  if (! pv[0][i].isPass() && ! s.isValidMove(pv[0][i])) {
1466  std::cerr << "root pv error " << pv[0][i] << " " << i << "\n";
1467  break;
1468  }
1469  ApplyMoveOfTurn::doMove(s, pv[0][i]);
1470  }
1471 #endif
1472 }
1473 
1474 template <class EvalT>
1475 template <osl::Player P>
1476 struct osl::search::AlphaBeta2Tree<EvalT>::NextMove
1477 {
1481  int *result;
1482  bool in_pv;
1483  NextMove(AlphaBeta2Tree *s, const MoveLogProb& md, Window w, int *r,
1484  bool p)
1485  : searcher(s), moved(md), window(w), result(r), in_pv(p) {
1486  assert(P == md.player());
1487  }
1488  void operator()(Square /*last_to*/) {
1489 #ifndef NDEBUG
1490  const int cur_limit = searcher->curLimit();
1491 #endif
1492  *result =
1493  searcher->alphaBetaSearchAfterMove<P>(moved, window, in_pv);
1494  assert(cur_limit == searcher->curLimit() || searcher->SearchState2Core::abort());
1495  }
1496 };
1497 
1498 template <class EvalT>
1499 template <osl::Player P>
1501 alphaBetaSearch(const MoveLogProb& search_move, Window w, bool in_pv)
1502 {
1503  assert(w.alpha(P) % 2);
1504  assert(w.beta(P) % 2);
1505  const Move move = search_move.move();
1506  assert(P == move.player());
1507  assert(P == state().turn());
1508  assert(eval::notLessThan(P, w.beta(P), w.alpha(P)));
1509 
1510  testStop();
1511  pv[curDepth()+1].clear();
1512  // TODO: more efficient way to find foul
1513  if (! move.isPass() ){
1514  if(MoveStackRejections::probe<P>(state(),history(),curDepth(),move,w.alpha(P),repetitionCounter().checkCount(alt(P)))){
1515  return this->winByLoop(alt(P));
1516  }
1518  ::isMember(state(), move))
1519  return this->winByFoul(alt(P));
1520  }
1521 
1522  const HashKey new_hash = currentHash().newHashWithMove(move);
1523  assert(P == move.player());
1524 
1525  if (move.isPass())
1526  this->pass_count.inc(P);
1527 
1528  // 千日手確認
1529  if (! this->pass_count.loopByBothPass()) {
1530  const Sennichite next_sennichite
1531  = repetition_counter.isAlmostSennichite(new_hash);
1532  if (next_sennichite.isDraw())
1533  return this->drawValue();
1534  if (next_sennichite.hasWinner())
1535  return this->winByFoul(next_sennichite.winner());
1536  assert(next_sennichite.isNormal());
1537  }
1538 
1539  if (! move.isPass()) {
1540  // 優越関係確認
1541  const DominanceCheck::Result has_dominance
1542  = DominanceCheck::detect(repetition_counter.history(), new_hash);
1543  if (has_dominance == DominanceCheck::LOSE)
1544  return this->winByLoop(alt(P));
1545  if (has_dominance == DominanceCheck::WIN)
1546  return this->winByLoop(P);
1547  // 連続王手駒捨て
1548  if (! move.isCapture()) {
1549  const int sacrifice_count = countSacrificeCheck2(this->curDepth());
1550  if (sacrifice_count == 2) {
1551  // 3回目は指さない
1552  const Square to = move.to();
1553  int offence = state().countEffect(P, to) + (move.isDrop() ? 1 : 0);
1554  const int deffense = state().hasEffectAt(alt(P), to); // max1
1555  if (offence <= deffense)
1556  offence += AdditionalEffect::count2(state(), to, P);
1557  if (offence <= deffense) {
1558  return this->winByLoop(alt(P));
1559  }
1560  }
1561  }
1562  }
1563  // 探索
1564  int result;
1565  NextMove<P> helper(this, search_move, w, &result, in_pv);
1566 
1567  this->recorder.addNodeCount();
1568  const eval_t old_eval = this->eval;
1569  doUndoMoveOrPass<P,NextMove<P> >(new_hash, move, helper);
1570  this->eval = old_eval;
1571  if (move.isPass())
1572  this->pass_count.dec(P);
1573 
1574  return result;
1575 }
1576 
1577 template <class EvalT>
1578 template <osl::Player P>
1580 examineMovesRoot(const MoveLogProbVector& moves, size_t i, Window window,
1581  MoveLogProb& best_move, int& best_value)
1582 {
1583  for (;i<moves.size(); ++i) {
1584  testStop();
1585 
1586 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_ROOT)
1587  if (shared && i > 8
1588  && moves.size() > i+1) {
1589  int smp_idle;
1590  {
1591 # ifdef OSL_USE_RACE_DETECTOR
1592  boost::mutex::scoped_lock lk(shared->lock_smp);
1593 # endif
1594  smp_idle = shared->smp_idle;
1595  }
1596  if (smp_idle) {
1597  try {
1598  examineMovesRootPar<P>(moves, i, window, best_move, best_value);
1599  break;
1600  } catch (AlphaBeta2ParallelCommon::SplitFailed&) {
1601  }
1602  }
1603  }
1604 #endif
1605 
1606  const MoveLogProb& m = moves[i];
1607 #ifndef GPSONE
1608  if (this->elapsed() > 1.0)
1609  {
1610  boost::mutex::scoped_lock lk(OslConfig::lock_io);
1611  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
1612  this->monitors())
1613  monitor->rootMove(m.move());
1614  }
1615  if (this->multi_pv) {
1616  int width = this->multi_pv*this->eval.captureValue(newPtypeO(P, PAWN))/200;
1617  if (width % 2 == 0)
1618  width -= EvalTraits<P>::delta;
1619  window.alpha(P) = best_value + width;
1620  }
1621 #endif
1622  const int result = alphaBetaSearch<P>(m, window, false);
1623  if (eval::betterThan(P, result, best_value))
1624  {
1625  window.alpha(P) = result + EvalTraits<P>::delta;
1626  best_move = m;
1627  best_value = result;
1628  updateRootPV(P, std::cerr, result, m.move());
1629  if (eval::betterThan(P, result, window.beta(P))) {
1630  assert(! this->isWinValue(alt(P), result));
1631  break;
1632  }
1633  }
1634 #ifndef GPSONE
1635  else if (this->multi_pv && eval::betterThan(P, result, window.alpha(P)))
1636  {
1637  addMultiPV(P, result, m.move());
1638  }
1639 #endif
1640  if (this->root_limit >= 1600)
1641  this->checkmate_searcher->runGC(this->table->isVerbose(),
1642  lastMemoryUseRatio1000());
1643  }
1644 }
1645 
1646 /* ------------------------------------------------------------------------- */
1647 
1648 template <class EvalT>
1650 AlphaBeta2(const NumEffectState& s, checkmate_t& c,
1652  : AlphaBeta2Tree<EvalT>(s, c, t, r)
1653 {
1655 }
1656 
1657 template <class EvalT>
1660 {
1661 }
1662 
1663 template <class EvalT>
1665 findCheckmateInPV(int verify_node, CArray<bool,2>& king_in_threat)
1666 {
1667  king_in_threat.fill(false);
1668  if (this->shared_root->last_pv.empty())
1669  return PVStable;
1670  const SearchState2::PVVector& pv = this->shared_root->last_pv.back().pv;
1671  NumEffectState state = this->state();
1672  PathEncoding path = this->path();
1673  PVCheckmateStatus found = PVStable;
1674  SearchState2::checkmate_t *checkmate_searcher = this->checkmate_searcher;
1675  if (this->node_count < verify_node*pv.size())
1676  verify_node = this->node_count/(pv.size()+1)/4;
1677  for (size_t i=0; i<pv.size(); ++i)
1678  {
1679  this->checkmate_searcher->runGC(this->table->isVerbose(),
1680  this->lastMemoryUseRatio1000());
1681  assert(pv[i].isPass() || state.isValidMove(pv[i]));
1682  if (! pv[i].isPass() && ! state.isValidMove(pv[i]))
1683  {
1684  std::cerr << "pv error " << pv[i] << "\n" << state;
1685  return PVStable;
1686  }
1687  state.makeMove(pv[i]);
1688  path.pushMove(pv[i]);
1689  if (state.inCheck())
1690  continue;
1691  const HashKey key(state);
1692  SimpleHashRecord *record = this->table->allocate(key, 2000);
1693  if (! record)
1694  break;
1695  Move checkmate_move, threatmate_move;
1696  const bool old_win = this->isWinningState
1697  (*checkmate_searcher, state, key, path,
1698  0, checkmate_move, pv[i]);
1699  if (! old_win)
1700  {
1701  const bool new_win = this->isWinningState
1702  (*checkmate_searcher, state, key, path,
1703  verify_node, checkmate_move, pv[i], true);
1704  if (new_win)
1705  {
1706  found = PVCheckmate;
1707  this->recordWinByCheckmate(state.turn(), record, checkmate_move);
1708  king_in_threat[alt(state.turn())] = true;
1709  if (this->table->isVerbose())
1710  std::cerr << " pv checkmate " << record::csa::show(pv[i])
1711  << "(" << i << ")\n";
1712  }
1713  }
1714  state.changeTurn();
1715  const Player T = state.turn();
1716  const bool old_threatmate_in_record = record->threatmate().isThreatmate(alt(T));
1717  const bool old_threatmate = this->isWinningState
1718  (*checkmate_searcher, state, HashKey(state), PathEncoding(T),
1719  1, threatmate_move, Move::PASS(alt(T)));
1720  if (! old_threatmate)
1721  {
1722  const bool new_threatmate = this->isWinningState
1723  (*checkmate_searcher, state, HashKey(state), PathEncoding(T),
1724  verify_node, threatmate_move, Move::PASS(alt(T)), this->root_limit >= 1000 + this->rootLimitBias());
1725  if (new_threatmate)
1726  {
1727  record->threatmate().setThreatmate(alt(T), threatmate_move);
1728  king_in_threat[alt(T)] = true;
1729  if (! old_threatmate_in_record)
1730  found = PVThreatmate;
1731  else if (found == PVStable)
1732  found = PVThreatmateNotRecord;
1733  if (this->table->isVerbose())
1734  std::cerr << " pv threatmate " << record::csa::show(pv[i])
1735  << "(" << i << ")\n";
1736  }
1737  }
1738  state.changeTurn();
1739  }
1740  this->checkmate_searcher->runGC(this->table->isVerbose(),
1741  this->lastMemoryUseRatio1000());
1742  this->updateCheckmateCount();
1743  return found;
1744 }
1745 
1746 template <class EvalT>
1749 {
1750  const Player Turn = this->state().turn();
1751  Window root_window = this->fullWindow(Turn);
1752  return alphaBetaSearchRoot(root_window, best_move, limit);
1753 }
1754 
1755 template <class EvalT>
1757 computeBestMoveIteratively(int limit, const int step,
1758  int initial_limit, size_t node_limit,
1759  const TimeAssigned& assign,
1760  MoveWithComment *additional_info)
1761 {
1762  this->setStartTime(MilliSeconds::now());
1763  this->setTimeAssign(assign);
1764  if (this->table->verboseLevel() > 2)
1765  {
1766  const time_t now = time(0);
1767  char ctime_buf[64];
1768  std::cerr << "AlphaBeta2 " << ctime_r(&now, ctime_buf);
1769  }
1770  if (this->table->isVerbose()) {
1771  std::cerr << " time assign/max " << this->timeAssigned().standard.toSeconds()
1772  << "/" << this->timeAssigned().max.toSeconds()
1773  << " multipv " << this->multi_pv
1774  << " iteration " << this->nextIterationCoefficient()
1775  << " mem " << std::fixed << std::setprecision(2)
1776  << OslConfig::memoryUseRatio()*100.0 << "%";
1777  std::cerr << "\n";
1778  }
1779  initial_limit = std::min(initial_limit, limit);
1780 
1781  this->recorder.resetNodeCount();
1782 
1783  double last_iteration_consumed = 0;
1784  double total_consumed = 0;
1785  int limit_iterative = initial_limit;
1786  Move last_best_move = Move::INVALID();
1787  this->shared_root->last_pv.clear();
1788 
1789 #ifdef OSL_SMP
1790 # ifdef SPLIT_STAT
1791  if (this->shared) {
1792  this->shared->parallel_splits = 0;
1793  this->shared->cancelled_splits.setValue(0);
1794  this->shared->parallel_abort.setValue(0);
1795  }
1796 # endif
1797 #endif
1798  try
1799  {
1800  if (this->table->verboseLevel() > 1)
1801  {
1802  MoveVector moves;
1803  move_generator::LegalMoves::generate(this->state(), moves);
1804  BOOST_FOREACH(Move move, moves) {
1805  HashKey key = this->currentHash().newHashWithMove(move);
1806  const SimpleHashRecord *record = this->table->find(key);
1807  if (! record || record->lowerLimit() < SearchTable::HistorySpecialDepth)
1808  continue;
1809  std::cerr << "prebound value " << record::csa::show(move)
1810  << " " << record->lowerBound() << " " << record->upperBound() << "\n";
1811  }
1812  }
1813 
1814  MoveLogProb search_move;
1815  this->shared_root->root_values.push_back(alphaBetaSearchRoot(search_move, 0));
1816  this->shared_root->last_root_move = search_move.move();
1817  this->shared_root->best_move_for_iteration.push_back(search_move.move());
1818  if (this->table->verboseLevel() > 1)
1819  std::cerr << "=> quiesce "
1820  << record::csa::show(search_move.move()) << "\n";
1821  while (limit_iterative < limit && ! this->stopping())
1822  {
1823  if (this->table->verboseLevel() > 1)
1824  std::cerr << "=> iteration " << limit_iterative
1825  << " (" << last_iteration_consumed << ", " << total_consumed << " sec)"
1826  << " mem " << OslConfig::memoryUseRatio()*100.0 << "%\n";
1827  this->recorder.startSearch(limit_iterative);
1828  const int previous_node_count = this->nodeCount();
1829  try {
1830  for (int i=0; i<8; ++i)
1831  {
1832  this->shared_root->root_values.push_back(alphaBetaSearchRoot(search_move, limit_iterative+this->rootLimitBias()));
1833  this->shared_root->last_root_move = search_move.move();
1834  last_best_move = search_move.move();
1835  if (this->stopping())
1836  break;
1837  PVCheckmateStatus need_more_verify = PVStable;
1838  CArray<bool, 2> king_in_threat;
1839  int verify_node_limit = limit <= (1200 + this->rootLimitBias()) ? 10000 : 40000;
1840  if (this->timeAssigned().standard.toSeconds() < 20)
1841  verify_node_limit /= 4;
1842 #ifdef DONT_USE_CHECKMATE
1843  break;
1844 #endif
1845  need_more_verify = findCheckmateInPV(verify_node_limit, king_in_threat);
1846  if (need_more_verify == PVStable
1847  || (i > 0 && need_more_verify == PVThreatmateNotRecord))
1848  break;
1849  if (this->isStableNow())
1850  this->setStable(i > 0 && king_in_threat[this->state().turn()] == false);
1851  }
1852  } catch (...) {
1853  last_iteration_consumed = this->elapsed() - total_consumed;
1854  total_consumed += last_iteration_consumed;
1855  this->updateCheckmateCount();
1856  this->recorder.finishSearch(search_move.move(), total_consumed,
1857  this->table->verboseLevel());
1858  throw;
1859  }
1860 
1861  last_iteration_consumed = this->elapsed() - total_consumed;
1862  total_consumed += last_iteration_consumed;
1863  this->shared_root->best_move_for_iteration.push_back(last_best_move);
1864  this->shared_root->root_values_for_iteration.push_back
1865  (this->shared_root->root_values.back());
1866 
1867  this->updateCheckmateCount();
1868  if (this->table->verboseLevel() > 2) {
1869  std::cerr << "<= "
1870  << record::csa::show(search_move.move());
1871  std::cerr << std::setprecision(4) << " mpn " << this->mpn.getAverage()
1872  << " cut " << this->mpn_cut.getAverage()
1873  << " alpha " << this->alpha_update.getAverage()
1874  << " last " << this->last_alpha_update.getAverage()
1875  << " ext " << 100.0*this->ext.getAverage() << "%"
1876  << " ext_limit " << this->ext_limit.getAverage()
1877  << " mem " << OslConfig::memoryUseRatio()*100.0;
1878 #ifdef OSL_SMP
1879 # ifdef SPLIT_STAT
1880  if (this->shared) {
1881  std::cerr << " split " << this->shared->parallel_splits << " cancel " << this->shared->cancelled_splits.value()
1882  << " abort " << this->shared->parallel_abort.value();
1883  }
1884 # endif
1885 #endif
1886  std::cerr << "\n";
1887  }
1888  bool time_over = false;
1889  if (this->hasSchedule()) {
1890  const double elapsed = this->elapsed();
1891  const double current_time_left = this->timeAssigned().standard.toSeconds() - elapsed;
1892  double coef = this->nextIterationCoefficient();
1893  if (! this->isStableNow())
1894  coef = std::min(0.5, coef);
1895  else {
1896  const int same_best_moves = this->shared_root->sameBestMoves();
1897  if (same_best_moves == 0) {
1898  if (this->table->verboseLevel() > 2 && coef > 0.75)
1899  std::cerr << "info: " << coef << " -> 0.75 by bestmove update\n";
1900  coef = std::min(0.75, coef);
1901  }
1902  else if (same_best_moves >= 3) {
1903  const Move last_move = this->lastMove();
1904  if (last_move.isNormal() && last_best_move.isNormal()
1905  && last_move.to() == last_best_move.to()
1906  && isMajor(last_best_move.capturePtype())
1907  && isMajorNonPieceOK(last_move.capturePtype())) {
1908  if (coef < 5.0 && this->table->verboseLevel() > 2)
1909  std::cerr << "info: " << coef << " -> 5.0 by takeback major piece\n";
1910  coef = std::max(5.0, coef);
1911  }
1912  }
1913  }
1914  if (current_time_left
1915  < last_iteration_consumed * coef)
1916  time_over = true;
1917  if (! time_over) {
1918  SimpleHashRecord *record
1919  = this->table->find(this->currentHash());
1920  if (record) {
1921  record->addNodeCount(this->nodeCount() - previous_node_count);
1922  }
1923  }
1924  }
1925  bool node_limit_over = (this->recorder.nodeCount() *4 > node_limit);
1926  this->recorder.finishSearch(search_move.move(),
1927  total_consumed,
1928  (time_over || node_limit_over) && this->table->verboseLevel());
1929  if (time_over || node_limit_over || this->stopping()) {
1930  if (this->table->isVerbose()) {
1931  const char *reason = "other reason";
1932  if (this->stopReason() == SearchTimerCommon::NoMoreMemory)
1933  reason = "memory full";
1934  else if (time_over || this->stopReason() == SearchTimerCommon::NoMoreTime)
1935  reason = "time";
1936  else if (node_limit_over)
1937  reason = "node count";
1938  else if (this->stopReason() == SearchTimerCommon::StopByOutside)
1939  reason = "outside";
1940  std::cerr << "iteration stop at " << limit_iterative << " by "
1941  << reason << "\n";
1942  }
1943  goto finish;
1944  }
1945  this->testStop();
1946  limit_iterative += step;
1947  }
1948  if (this->table->verboseLevel() > 1)
1949  std::cerr << "=> final iteration " << limit_iterative
1950  << " (" << last_iteration_consumed << ", " << total_consumed << " sec)"
1951  << " mem " << OslConfig::memoryUseRatio()*100.0 << "%\n";
1952  while (true) {
1953  this->recorder.startSearch(limit);
1954  try {
1955  for (int i=0; i<8; ++i)
1956  {
1957  this->shared_root->root_values.push_back(alphaBetaSearchRoot(search_move, limit+this->rootLimitBias()));
1958  this->shared_root->last_root_move = search_move.move();
1959  last_best_move = search_move.move();
1960  if (this->stopping())
1961  break;
1962  PVCheckmateStatus need_more_verify = PVStable;
1963  CArray<bool, 2> king_in_threat;
1964  int verify_node_limit = limit <= (1200 + this->rootLimitBias()) ? 10000 : 40000;
1965  if (this->timeAssigned().standard.toSeconds() < 20)
1966  verify_node_limit /= 4;
1967 #ifdef DONT_USE_CHECKMATE
1968  break;
1969 #endif
1970  need_more_verify = findCheckmateInPV(verify_node_limit, king_in_threat);
1971  if (need_more_verify == PVStable
1972  || (i > 0 && need_more_verify == PVThreatmateNotRecord))
1973  break;
1974  if (this->isStableNow())
1975  this->setStable(i > 0 && king_in_threat[this->state().turn()] == false);
1976  }
1977  } catch (...) {
1978  last_iteration_consumed = this->elapsed() - total_consumed;
1979  total_consumed += last_iteration_consumed;
1980  this->updateCheckmateCount();
1981  this->recorder.finishSearch(search_move.move(), total_consumed,
1982  this->table->verboseLevel());
1983  throw;
1984  }
1985  last_iteration_consumed = this->elapsed() - total_consumed;
1986  total_consumed += last_iteration_consumed;
1987  this->updateCheckmateCount();
1988  this->recorder.finishSearch(search_move.move(), total_consumed,
1989  this->table->verboseLevel());
1990  this->shared_root->best_move_for_iteration.push_back(last_best_move);
1991  this->shared_root->root_values_for_iteration.push_back
1992  (this->shared_root->root_values.back());
1993 
1994  if (last_best_move.isNormal())
1995  break;
1996  this->testStop();
1997 
1998  // ほっておくと投了
1999  if (limit >= 2000 || this->root_ignore_moves)
2000  break;
2001 
2002  limit += 200;
2003  if (this->table->isVerbose())
2004  std::cerr << " extend limit to " << limit << " before resign\n";
2005  }
2006  }
2007  catch (std::exception& e)
2008  {
2009  if (! OslConfig::usiMode())
2010  std::cerr << "std exception " << e.what() << "\n";
2011  }
2012  catch (...)
2013  {
2014  std::cerr << "unknown exception\n";
2015 #ifndef NDEBUG
2016  throw;
2017 #endif
2018  }
2019 finish:
2020  if (this->table->verboseLevel() > 1) {
2021  std::cerr << "<= " << record::csa::show(last_best_move);
2022  std::cerr << std::setprecision(4) << " mpn " << this->mpn.getAverage()
2023  << " cut " << this->mpn_cut.getAverage()
2024  << " alpha " << this->alpha_update.getAverage()
2025  << " last " << this->last_alpha_update.getAverage()
2026  << " ext " << this->ext.getAverage()
2027  << " ext_limit " << this->ext_limit.getAverage()
2028  << " mem " << OslConfig::memoryUseRatio()*100.0;
2029 #ifdef OSL_SMP
2030 # ifdef SPLIT_STAT
2031  if (this->shared) {
2032  std::cerr << " split " << this->shared->parallel_splits << " cancel " << this->shared->cancelled_splits.value()
2033  << " abort " << this->shared->parallel_abort.value();
2034  }
2035 # endif
2036 #endif
2037  std::cerr << "\n";
2038  }
2039 
2040  if (additional_info) {
2041  additional_info->node_count = this->nodeCount();
2042  additional_info->elapsed = this->elapsed();
2043  additional_info->moves.clear();
2044  additional_info->root_limit = this->root_limit;
2045  }
2046  if (additional_info && this->shared_root->root_values.size() > 1) { // last_root_value[0] is for quiesce
2047  assert(last_best_move == this->shared_root->last_root_move);
2048  additional_info->move = last_best_move;
2049  const double scale = 200.0/this->eval.captureValue(newPtypeO(WHITE,PAWN));
2050  additional_info->value = static_cast<int>(this->shared_root->last_root_value_update * scale);
2051  if (!this->shared_root->last_pv.empty()) {
2052  for (size_t i=1; i<this->shared_root->last_pv.back().pv.size(); ++i) {
2053  additional_info->moves.push_back(this->shared_root->last_pv.back().pv[i]);
2054  }
2055  }
2056  }
2057 #ifndef GPSONE
2058  {
2059  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2060  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2061  this->monitors())
2062  monitor->searchFinished();
2063  }
2064 #endif
2065  return last_best_move;
2066 }
2067 
2068 template <class EvalT>
2069 template <osl::Player P>
2072 {
2073 #ifndef GPSONE
2074  {
2075  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2076  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2077  this->monitors())
2078  monitor->newDepth(limit/200);
2079  }
2080 #endif
2081  assert(P == this->state().turn());
2082  assert(window.alpha(P) % 2);
2083  assert(window.beta(P) % 2);
2084  setRoot(limit);
2085  assert(this->curDepth() == 0);
2086  this->node_type[this->curDepth()] = base_t::PvNode;
2087  this->checkmate_searcher->setRootPlayer(P);
2088 #ifdef OSL_SMP
2089  if (this->shared)
2090  this->shared->threadStart();
2091 #endif
2092  // まずテーブルを牽く
2093  SimpleHashRecord *record_in_table
2094  = this->table->allocate(this->currentHash(), limit);
2095  SimpleHashRecord *record = record_in_table;
2096  boost::scoped_ptr<SimpleHashRecord> record_if_not_allocated;
2097  if (! record)
2098  {
2099  record_if_not_allocated.reset(new SimpleHashRecord());
2100  record = record_if_not_allocated.get();
2101  }
2102  assert(record);
2103  this->setRootRecord(record);
2104  assert(this->rootRecord() == record);
2105  assert(this->hasLastRecord() && this->lastRecord() == record);
2106  record->setInCheck(this->state().inCheck());
2107 
2108  if (limit == 0) {
2109  int result = this->template quiesce<P>(fullWindow(P));
2110  best_move = MoveLogProb(record->qrecord.bestMove(), 100);
2111  if (this->root_ignore_moves
2112  && this->root_ignore_moves->isMember(best_move.move()))
2113  best_move = MoveLogProb();
2114 #ifndef GPSONE
2115  else if (this->hasMonitor() && !this->prediction_for_speculative_search)
2116  {
2117  const double scale = OslConfig::usiOutputPawnValue()*2.0
2118  / this->eval.captureValue(newPtypeO(alt(P),PAWN));
2119  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2120  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2121  this->monitors())
2122  monitor->showPV(1, this->recorder.allNodeCount(),
2123  this->elapsed(), static_cast<int>(result*scale),
2124  best_move.move(), 0, 0, 0, 0);
2125  }
2126 #endif
2127  return result;
2128  }
2129  if (record_in_table) {
2130  int table_value = 0;
2131  const MoveLogProb m = record_in_table->bestMove();
2132  if (! m.isNormal())
2133  record_in_table->resetValue();
2134  else if (record->hasGreaterLowerBound<P>(this->curLimit(), window.beta(P),
2135  table_value)) {
2136  if (! this->root_ignore_moves
2137  || ! this->root_ignore_moves->isMember(m.move())) {
2138  best_move = m;
2139  return table_value;
2140  }
2141  }
2142  }
2143 
2144  // gather all moves
2145  MoveLogProbVector moves;
2146  MoveGenerator& generator = this->makeGenerator();
2147  const MoveLogProb last_best_move = record->bestMove();
2148  {
2149  MoveLogProbVector raw_moves;
2150  assert(this->curLimit() > 0);
2151  const Move hash_move = last_best_move.isNormal()
2152  ? last_best_move.move() : record->qrecord.bestMove();
2153  generator.init(this->curLimit()+200, record, this->eval, this->state(), true, hash_move);
2154  if (last_best_move.isNormal())
2155  raw_moves.push_back(last_best_move);
2156  else if (record->qrecord.bestMove().isNormal())
2157  raw_moves.push_back(MoveLogProb(record->qrecord.bestMove(), 100));
2158  generator.generateAll<P>(*this, raw_moves);
2159 
2160  // clean up losing moves
2161  for (size_t i=0; i<raw_moves.size(); ++i) {
2162  const Move m = raw_moves[i].move();
2163  if (i > 0 && m == hash_move)
2164  continue;
2165  const HashKey key = this->currentHash().newHashWithMove(m);
2166  const SimpleHashRecord *record = this->table->find(key);
2167  assert(this->state().isValidMove(m));
2168  if (record) {
2170  && this->isWinValue(alt(P), record->upperBound()))
2171  continue;
2172  }
2173  if (this->root_ignore_moves && this->root_ignore_moves->isMember(m))
2174  continue;
2175  if (! m.isDrop() && m.ptype() != KING
2176  && move_classifier::KingOpenMove<P>::isMember(this->state(), m.ptype(), m.from(), m.to()))
2177  continue;
2179  ::isMember(this->state(), m))
2180  continue;
2181  raw_moves[i].setLogProbAtMost(limit);
2182  moves.push_back(raw_moves[i]);
2183  }
2184  }
2185 
2187  if (moves.size() == 1
2188  || (moves.size() == 2 && moves[0].move() == moves[1].move()))
2189  {
2190  best_move = moves[0];
2191 #ifndef GPSONE
2192  if (this->hasMonitor() && !this->prediction_for_speculative_search) {
2193  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2194  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2195  this->monitors())
2196  monitor->rootForcedMove(best_move.move());
2197  }
2198 #endif
2199  return 0; // XXX
2200  }
2201  }
2202 
2203 #ifndef DONT_USE_CHECKMATE
2204  // 詰将棋を呼んでみる root では沢山呼んでも問題ない
2205  int checkmate_node = 0;
2206  if (! this->prediction_for_speculative_search) {
2207  int checkmate_max = 30000*std::max(limit - 300 - this->rootLimitBias(), 0)/100;
2208  if (limit >= 1000 + this->rootLimitBias())
2209  checkmate_max = std::min(400000, 60000*(limit - 800 - this->rootLimitBias())/100);
2210  if (this->timeAssigned().standard.toSeconds() < 20) {
2211  checkmate_node /= 4;
2212  if (this->timeAssigned().standard.toSeconds() < 10)
2213  checkmate_node /= 2;
2214  }
2215  checkmate_node = record->qrecord.checkmateNodesLeft(checkmate_max);
2216 #ifdef CHECKMATE_COUNT
2217  std::cerr << "limit " << limit << " checkmate " << checkmate_node << "\n";
2218 #endif
2219  }
2220  if (checkmate_node > 0)
2221  {
2222  const bool my_king_in_check
2223  = this->state().hasEffectAt(alt(P),this->state().kingSquare(P));
2224  if (my_king_in_check)
2225  {
2226  // 相手から王手がかかっている
2227  this->recorder.gotoCheckmateSearch(this->state(), checkmate_node/8);
2228  const bool lose = this->template isLosingState<P>(checkmate_node/8);
2229  this->recorder.backFromCheckmateSearch();
2230  this->updateCheckmateCount();
2231  if (lose)
2232  {
2233  best_move = MoveLogProb(Move::INVALID(),100);
2234  this->recordLoseByCheckmate(P, record);
2235  this->shared_root->last_pv.clear();
2236  this->shared_root->last_root_move = Move();
2237  this->shared_root->last_root_value_update = this->winByCheckmate(alt(P));
2238 #ifndef GPSONE
2239  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2240  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2241  this->monitors())
2242  monitor->rootLossByCheckmate();
2243 #endif
2244  return this->winByCheckmate(alt(P));
2245  }
2246  }
2247  // 詰まされなければ,相手を詰ますことを考える
2248  {
2249  Move checkmate_move;
2250 #ifdef CHECKMATE_COUNT
2251  size_t count = this->checkmateSearcher().totalNodeCount();
2252 #endif
2253  this->recorder.gotoCheckmateSearch(this->state(), checkmate_node);
2254  const bool win = this->template isWinningState<P>
2255  (checkmate_node, checkmate_move, limit >= 1000 + this->rootLimitBias());
2256  this->recorder.backFromCheckmateSearch();
2257  this->updateCheckmateCount();
2258 #ifdef CHECKMATE_COUNT
2259  root_checkmate += this->checkmateSearcher().totalNodeCount() - count;
2260 #endif
2261  if (win)
2262  {
2263  best_move = MoveLogProb(checkmate_move,100);
2264  this->recordWinByCheckmate(P, record, checkmate_move);
2265  this->shared_root->last_pv.clear();
2266  this->shared_root->last_root_move = checkmate_move;
2267  this->shared_root->last_root_value_update = this->winByCheckmate(P);
2268  this->pv[1].clear();
2269  this->updateRootPV(P, std::cerr, this->winByCheckmate(P), checkmate_move);
2270  return this->winByCheckmate(P);
2271  }
2272  }
2273  // 詰めろを考える
2274  if ((! my_king_in_check)
2275  && (! (record->threatmate().isThreatmate(P))))
2276  {
2277  Move threatmate_move;
2278 #ifdef CHECKMATE_COUNT
2279  size_t count = this->checkmateSearcher().totalNodeCount();
2280 #endif
2281  this->recorder.gotoCheckmateSearch(this->state(), checkmate_node);
2282  const bool threatmate
2283  = this->template isThreatmateState<P>
2284  (checkmate_node, threatmate_move, limit >= 1000 + this->rootLimitBias());
2285 #ifdef CHECKMATE_COUNT
2286  root_checkmate += this->checkmateSearcher().totalNodeCount() - count;
2287 #endif
2288  this->recorder.backFromCheckmateSearch();
2289  this->updateCheckmateCount();
2290  if (threatmate)
2291  {
2292  if (record)
2293  record->threatmate().setThreatmate(P, threatmate_move);
2294  if (this->table->verboseLevel() > 1)
2295  std::cerr << " root threatmate " << threatmate_move << "\n";
2296  }
2297  BOOST_FOREACH(Ptype ptype, PieceStand::order)
2298  {
2299  this->testStop();
2300  if (! this->state().hasPieceOnStand(P, ptype))
2301  continue;
2302  NumEffectState state(this->state().emulateHandPiece(P, alt(P), ptype));
2303  state.setTurn(alt(P));
2304  Move hand_move;
2305  this->template isWinningState<PlayerTraits<P>::opponent>
2306  (*this->checkmate_searcher, state, HashKey(state), PathEncoding(alt(P)),
2307  checkmate_node, hand_move, Move::PASS(P), limit >= 1000 + this->rootLimitBias());
2308  }
2309  }
2310  this->testStop();
2311  }
2312  this->checkmate_searcher->runGC(this->table->isVerbose(),
2313  this->lastMemoryUseRatio1000());
2314 #endif
2315  const int ValueNone = window.alpha(P) - EvalTraits<P>::delta;
2316  int best_value = ValueNone;
2317  try {
2318  // first move
2319  size_t i=0;
2320  if (limit >= 1000 && ! moves.empty() && window == fullWindow(P))
2321  {
2322  // try aspiration window if we have sufficient limit
2323  const int root_alpha =
2324  this->rootAlpha(P, this->shared_root->root_values.size() ? this->shared_root->root_values.back() : 0,
2325  this->eval.progress16());
2326  if (EvalTraits<P>::betterThan(root_alpha, window.alpha(P))) {
2327  const Window window_copy = window;
2328  window.alpha(P) = root_alpha;
2329 #ifndef GPSONE
2330  {
2331  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2332  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2333  this->monitors())
2334  monitor->rootFirstMove(moves[0].move());
2335  }
2336 #endif
2337  const int result = this->template alphaBetaSearch<P>(moves[0], window, true);
2338  if (EvalTraits<P>::betterThan(result, root_alpha))
2339  {
2340  window.alpha(P) = result + EvalTraits<P>::delta;
2341  best_move = moves[0];
2342  best_value = result;
2343  this->updateRootPV(P, std::cerr, result, moves[0].move());
2344  ++i;
2345  }
2346  else
2347  {
2348  if (this->table->isVerbose())
2349  this->showFailLow(result, moves[0].move());
2350 #ifndef GPSONE
2351  if (this->hasMonitor() && !this->prediction_for_speculative_search) {
2352  const double scale = OslConfig::usiOutputPawnValue()*2.0
2353  / this->eval.captureValue(newPtypeO(alt(P),PAWN));
2354  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2355  this->monitors())
2356  monitor->showFailLow(this->root_limit/200, this->recorder.allNodeCount(),
2357  this->elapsed(),static_cast<int>(result*scale),
2358  moves[0].move());
2359  }
2360 #endif
2361  this->setStable(false);
2362  window = window_copy;
2363  }
2364  this->checkmate_searcher->runGC(this->table->isVerbose(),
2365  this->lastMemoryUseRatio1000());
2366  }
2367  }
2368  for (; i<moves.size() && best_value == ValueNone
2369  && window == fullWindow(P); ++i) {
2370  const MoveLogProb& m = moves[i];
2371 #ifndef GPSONE
2372  {
2373  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2374  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2375  this->monitors())
2376  monitor->rootMove(m.move());
2377  }
2378 #endif
2379  const int result = this->template alphaBetaSearch<P>(m, window, true);
2380  if (eval::betterThan(P, result, best_value)) {
2381  window.alpha(P) = result + EvalTraits<P>::delta;
2382  best_move = m;
2383  best_value = result;
2384  this->updateRootPV(P, std::cerr, result, m.move());
2385  if (eval::betterThan(P, result, window.beta(P))) {
2386  assert(! this->isWinValue(alt(P), result));
2387  }
2388  }
2389  else if (result == ValueNone)
2390  this->setStable(false);
2391  this->checkmate_searcher->runGC(this->table->isVerbose(),
2392  this->lastMemoryUseRatio1000());
2393  }
2394  // other moves
2395  if (! eval::betterThan(P, window.alpha(P), window.beta(P))) {
2396  this->template examineMovesRoot<P>(moves, i, window, best_move, best_value);
2397  }
2398  if (best_move.isNormal()) {
2399  if (best_value != ValueNone) {
2400  assert(! this->shared_root->last_pv.empty());
2401  assert(best_move.move() == this->shared_root->last_pv.back().pv[0]);
2402  }
2403  }
2404 #ifndef GPSONE
2405  {
2406  boost::mutex::scoped_lock lk(OslConfig::lock_io);
2407  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2408  this->monitors())
2409  monitor->depthFinishedNormally(limit/200);
2410  }
2411 #endif
2412  } catch (std::runtime_error& e) {
2413  if (this->table->isVerbose())
2414  std::cerr << e.what() << "\n";
2415  assert(best_value % 2 == 0);
2416  this->stopNow();
2417  this->restoreRootState();
2418  if (best_value != ValueNone)
2419  record->setLowerBound(P, this->curLimit(), best_move, best_value);
2420  if (best_move.validMove()
2421  && best_move.move() != last_best_move.move()) {
2422  if (this->table->verboseLevel() > 1) {
2423  std::cerr << "! use better move than the last best move\n";
2424  if (best_value != ValueNone) {
2425  assert(! this->shared_root->last_pv.empty() &&
2426  ! this->shared_root->last_pv.back().pv.empty());
2427  assert(best_move.move() == this->shared_root->last_pv.back().pv[0]);
2428  }
2429  }
2430  }
2431  else {
2432 #ifdef OSL_SMP
2433  if (this->shared)
2434  this->shared->waitAll();
2435 #endif
2436  throw;
2437  }
2438  }
2439 
2440  assert(best_value % 2 == 0);
2441  if (best_value != ValueNone)
2442  record->setLowerBound(P, this->curLimit(), best_move, best_value);
2443 #ifdef OSL_SMP
2444  if (this->shared)
2445  this->shared->waitAll();
2446 #endif
2447 #ifndef GPSONE
2448  if (best_value == ValueNone
2449  && this->hasMonitor() && !this->prediction_for_speculative_search)
2450  {
2451  const double scale = OslConfig::usiOutputPawnValue()*2.0
2452  / this->eval.captureValue(newPtypeO(alt(P),PAWN));
2453  const int value = this->winByCheckmate(alt(P));
2454  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
2455  this->monitors())
2456  monitor->showPV(limit/200, this->recorder.allNodeCount(),
2457  this->elapsed(), static_cast<int>(value*scale),
2458  Move::INVALID(), 0, 0, 0, 0);
2459  }
2460 #endif
2461  return best_value;
2462 }
2463 
2464 template <class EvalT>
2466 {
2467  SearchState2::setRoot(limit);
2468  SimpleHashRecord *record = this->table->allocate(this->currentHash(), std::max(1000,limit));
2469  assert(record);
2470  this->setRootRecord(record);
2471  this->move_type[this->curDepth()] = base_t::INITIAL;
2472 }
2473 
2474 template <class EvalT>
2476 {
2477  assert(this->state().isValidMove(move));
2478  SearchState2::makeMove(move);
2479  this->eval.update(this->state(), move);
2480 
2481  SimpleHashRecord *record
2482  = this->table->allocate(this->currentHash(), this->curLimit());
2483  assert(record);
2484  this->move_type[this->curDepth()] = base_t::INITIAL;
2485  record->setInCheck(this->state().inCheck());
2486  this->setCurrentRecord(record);
2487 }
2488 
2489 template <class EvalT>
2491 isReasonableMove(Move /*move*/, int /*pawn_sacrifice*/)
2492 {
2493  return true;
2494 }
2495 
2496 template <class EvalT>
2498 showNodeDepth(std::ostream& os)
2499 {
2500 #ifndef MINIMAL
2501  int max_depth=0;
2502  for (int i=base_t::MaxDepth-1; i>=0; --i) {
2503  if (base_t::depth_node_count[i] || base_t::depth_node_count_quiesce[i]) {
2504  max_depth = i;
2505  break;
2506  }
2507  }
2508  int max_count=0;
2509  for (int i=0; i<=max_depth; i+=2) {
2510  max_count = std::max(max_count,
2511  base_t::depth_node_count[i]+base_t::depth_node_count_quiesce[i]);
2512  }
2513 
2514  int unit = std::max(max_count/79, 100);
2515  for (int i=0; i<=max_depth; i+=2) {
2516  os << std::setw(3) << i << " "
2517  << std::string(base_t::depth_node_count[i]/unit, '*')
2518  << std::string(base_t::depth_node_count_quiesce[i]/unit, '+')
2519  << std::endl;
2520  }
2521 # ifdef CHECKMATE_COUNT
2522  std::cerr << "checkmate root " << root_checkmate << " quiesce " << quiesce_checkmate
2523  << "\nnormal before " << checkmate_before
2524  << " after " << checkmate_after << " threatmate " << count_threatmate
2525  << "\n";
2526 # endif
2527 #endif
2528 }
2529 
2530 template <class EvalT>
2533 {
2534 #ifndef MINIMAL
2535  base_t::depth_node_count.fill(0);
2536  base_t::depth_node_count_quiesce.fill(0);
2537 #endif
2538 }
2539 
2540 namespace osl
2541 {
2542  namespace search
2543  {
2544 #ifndef MINIMAL
2545  template class AlphaBeta2<eval::ProgressEval>;
2546  template class AlphaBeta2Tree<eval::ProgressEval>;
2547  template
2548  void AlphaBeta2Tree<eval::ProgressEval>::examineMovesRoot<BLACK>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
2549  template
2550  void AlphaBeta2Tree<eval::ProgressEval>::examineMovesRoot<WHITE>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
2551 #endif
2554  template
2555  void AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesRoot<BLACK>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
2556  template
2557  void AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesRoot<WHITE>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
2558  }
2559 }
2560 
2561 /* ------------------------------------------------------------------------- */
2562 // ;;; Local Variables:
2563 // ;;; mode:c++
2564 // ;;; c-basic-offset:2
2565 // ;;; End: