35 #include <boost/foreach.hpp>
40 #define search_assert(x, m) assert((x) || SearchState2::abort(m))
44 #ifdef CHECKMATE_COUNT
45 static size_t root_checkmate = 0, checkmate_before = 0, checkmate_after = 0,
46 count_threatmate = 0, quiesce_checkmate=0;
56 std::cerr <<
last_pv[i].eval <<
' ';
69 template <
class EvalT>
73 template <
class EvalT>
81 for (
int i=0; i<4; ++i) {
87 catch (std::bad_alloc&)
89 std::cerr <<
"panic " << i <<
" allocation of AlphaBeta2Parallel failed\n";
91 boost::this_thread::sleep(boost::posix_time::seconds(1));
95 NonBlockDelete::deleteAll();
101 template <
class EvalT>
106 node_count(0), shared(src.shared), shared_root(src.shared_root)
112 template <
class EvalT>
119 if (shared && shared.use_count() == 1)
120 NonBlockDelete::reset(shared);
124 template <
class EvalT>
132 catch (std::bad_alloc&)
134 std::cerr <<
"panic. allocation of MoveGenerator failed\n";
140 template <
class EvalT>
146 template <
class EvalT>
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];
161 template <
class EvalT>
162 template <osl::Player P>
167 assert(w.
alpha(P) % 2);
168 assert(w.
beta(P) % 2);
169 assert(
alt(P) == state().turn());
170 assert(P == moved.
player());
174 if (state().inCheck(P)) {
175 return this->minusInfty(P);
177 this->eval.update(state(), moved.
move());
179 const size_t previous_node_count = nodeCount();
181 pv[this->curDepth()].clear();
186 boost::scoped_ptr<SimpleHashRecord> record_if_unavailable;
187 int alloc_limit = curLimit(), memory1000 = lastMemoryUseRatio1000();
189 const uint64_t table_use = this->table->memoryUse();
191 && memory1000 > 300 && (root_limit >= 1600 || memory1000 > 500)
192 && ! in_pv && ! state().inCheck() && (!parent||! parent->
inCheck()))
195 alloc_limit -=
std::max(root_limit - 1400, 200);
197 alloc_limit -=
std::max((root_limit - 1400)*3/4, 0);
198 if (memory1000 > 900)
200 else if (root_limit >= 1600 && memory1000 > 800)
202 else if (root_limit >= 1600 && memory1000 > 700)
204 alloc_limit =
std::max(0, alloc_limit);
207 = this->table->allocate(currentHash(), alloc_limit);
208 const bool has_table_record = record;
211 record = record_if_unavailable.get();
213 setCurrentRecord(record);
217 if (pass_count.loopByBothPass()) {
218 return quiesce<Turn>(w);
222 int consumption = moved.
logProb();
227 assert(node_type[this->curDepth()] == PvNode);
228 for (
int limit = curLimit() - 200+1;
limit > consumption+200;
230 searchAllMoves<Turn>(moved.
move(),
limit,
232 if (! record->bestMove().validMove()) {
233 Move quiesce_best = record->qrecord.bestMove();
235 record->setBestMove(quiesce_best, 200);
241 if (node_type[this->curDepth()] == PvNode)
242 node_type[this->curDepth()] = AllNode;
243 result = searchAllMoves<Turn>
244 (moved.
move(), consumption, record,
248 assert(node_type[this->curDepth()] == PvNode);
249 result = searchAllMoves<Turn>(moved.
move(), consumption,
252 bool extended =
false;
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
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;
271 ext_limit.add(consumption - consumption_here);
272 result = searchAllMoves<Turn>(moved.
move(), consumption_here, record, w);
277 if (has_table_record)
278 record->
addNodeCount(nodeCount() - previous_node_count);
282 template <
class EvalT>
283 template <osl::Player Turn>
289 assert(node_type[this->curDepth()] == PvNode);
291 this->recorder.tryMove(
MoveLogProb(m, limit_consumption),
292 w.
alpha(P), curLimit());
293 subLimit(limit_consumption);
295 const int result = searchAllMoves<Turn>(record, w);
297 addLimit(limit_consumption);
298 this->recorder.recordValue(
MoveLogProb(m, limit_consumption),
304 template <
class EvalT>
305 template <osl::Player P>
311 && (in_pv || (this->curDepth() > 0
312 && this->node_type[this->curDepth()-1] != CutNode))
315 int threatmate_limit = 0;
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);
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;
342 if (curLimit() >= this->table->minimumRecordLimit())
348 threatmate_limit /= 2;
351 Move threatmate_move;
352 this->recorder.gotoCheckmateSearch(state(), threatmate_limit);
353 #ifdef CHECKMATE_COUNT
354 size_t count = checkmateSearcher().totalNodeCount();
357 = isThreatmateState<P>(threatmate_limit, threatmate_move);
358 #ifdef CHECKMATE_COUNT
359 count_threatmate += checkmateSearcher().totalNodeCount() -
count;
361 if (threatmate_limit > 100) {
362 updateCheckmateCount();
365 this->recorder.backFromCheckmateSearch();
366 if (!threatmate && threatmate_limit == 0
368 threatmate = isThreatmateStateShort<P>(2, threatmate_move);
377 template <
class EvalT>
378 template <osl::Player P>
390 if (in_pv && root_limit >= 500+this->rootLimitBias()) {
391 int depth = this->curDepth();
392 if (root_limit >= 700+this->rootLimitBias() && depth <= 3) {
395 else if ( (depth == 2))
396 checkmate_limit = 1000;
397 else if ( (depth == 3))
398 checkmate_limit = 200;
400 else if (((root_limit - curLimit()) <= 500) || (depth <= 5))
402 assert(static_cast<unsigned int>(curLimit()) < 4096);
408 checkmate_limit +=
std::max(100, checkmate_limit);
411 if (root_limit < 800)
412 checkmate_limit /= 2;
414 if (curLimit() >= this->table->minimumRecordLimit())
418 if (checkmate_limit <= 0)
423 checkmate_limit /= 2;
427 #ifdef CHECKMATE_COUNT
428 size_t count = checkmateSearcher().totalNodeCount();
430 this->recorder.gotoCheckmateSearch(state(), checkmate_limit);
431 const bool win = isWinningState<P>
433 if (checkmate_limit > 100)
434 updateCheckmateCount();
435 this->recorder.backFromCheckmateSearch();
436 #ifdef CHECKMATE_COUNT
437 checkmate_before += checkmateSearcher().totalNodeCount() -
count;
439 if (this->root_limit >= 1600 && checkmate_limit >= 100)
440 this->checkmate_searcher->runGC(this->table->isVerbose(),
441 lastMemoryUseRatio1000());
445 template <
class EvalT>
446 template <osl::Player P>
449 int node_count,
int best_value)
454 checkmate_limit = node_count / 2;
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) {
463 checkmate_importance_wrt_root = checkmate_importance_wrt_root*7/8;
465 checkmate_importance_wrt_root /= 7;
467 checkmate_limit =
std::max(checkmate_limit, checkmate_importance_wrt_root);
470 checkmate_limit = countCheckAfterThreatmate(
alt(P),2)*320 + 100;
471 #ifdef MORE_CHECKMATE_IF_CAPTURE_MAJOR
473 && ! state().hasEffectAt(P, lastMove().to()))
474 checkmate_limit += 20000;
477 if (curDepth() == 1 && hasLastRecord(1)) {
484 int checkmate_afford = this->nodeAffordable();
486 checkmate_afford *= 1.5 / shared->max_threads;
488 if (checkmate_limit > 100 && checkmate_limit > checkmate_afford) {
490 if (checkmate_afford > 0 && this->timeAssigned().standard.toSeconds() >= 10.0)
491 std::cerr <<
"adjust checkmate near timeover " << checkmate_limit <<
" => " << checkmate_afford <<
"\n";
493 checkmate_limit = checkmate_afford;
499 #ifdef CHECKMATE_COUNT
500 size_t count = checkmateSearcher().totalNodeCount();
502 this->recorder.gotoCheckmateSearch(state(), checkmate_limit);
503 const bool win = isWinningState<P>
505 if (checkmate_limit > 100)
506 updateCheckmateCount();
507 this->recorder.backFromCheckmateSearch();
508 #ifdef CHECKMATE_COUNT
509 checkmate_after += checkmateSearcher().totalNodeCount() -
count;
511 if (this->root_limit >= 1600 && checkmate_limit >= 100)
512 this->checkmate_searcher->runGC(this->table->isVerbose(),
513 lastMemoryUseRatio1000());
517 template <
class EvalT>
525 template <
class EvalT>
526 template <osl::Player P>
532 switch (this->move_type[this->curDepth()]) {
535 if (curLimit() < this->leafLimit()) {
536 this->move_type[this->curDepth()] = common_t::FINISH;
539 this->move_type[this->curDepth()] = common_t::TACTICAL;
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());
546 this->validTableMove(state(), best_move_in_table, curLimit())) {
547 if (this->in_pv[this->curDepth()]
552 return best_move_in_table;
557 case common_t::TACTICAL:
563 this->move_type[this->curDepth()] = common_t::KILLER;
564 this->killers[this->curDepth()].clear();
567 && (curLimit() >= 300)) {
568 MoveVector killer_moves;
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);
574 std::reverse(this->killers[this->curDepth()].begin(), this->killers[this->curDepth()].end());
577 case common_t::KILLER:
580 if (! killers.empty()) {
581 Move m = killers[killers.size()-1];
586 this->move_type[this->curDepth()] = 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;
602 this->move_type[this->curDepth()] = common_t::FINISH;
605 assert(this->move_type[this->curDepth()] == common_t::FINISH);
610 template <
class EvalT>
611 template <osl::Player P>
616 checkPointSearchAllMoves();
618 assert(P == state().turn());
620 assert(curLimit() >= 0);
622 assert(hasLastRecord(1));
624 #ifndef DONT_USE_CHECKMATE
625 const int node_count_at_beginning = nodeCount();
627 #if (! defined OSL_USE_RACE_DETECTOR) && (! defined MINIMAL)
628 depth_node_count[this->curDepth()]++;
630 this->move_type[this->curDepth()] = common_t::INITIAL;
631 const bool in_pv = this->in_pv[this->curDepth()] = ! w.
null();
638 if (this->isWinValue(P, lower_bound)
645 if (this->isWinValue(
alt(P), upper_bound))
656 this->recorder.tableHitLowerBound(P, table_value, w.
beta(P), curLimit());
665 this->recorder.tableHitUpperBound(P, table_value, w.
alpha(P), curLimit());
674 && isWinningStateShort<P>(2, checkmate_move))
676 this->recordWinByCheckmate(P, record, checkmate_move);
677 return this->winByCheckmate(P);
679 #ifndef DONT_USE_CHECKMATE
682 int additional_limit = 0;
688 this->recorder.gotoCheckmateSearch(state(), additional_limit);
689 const bool win = isWinningState<P>(additional_limit, checkmate_move);
690 updateCheckmateCount();
691 this->recorder.backFromCheckmateSearch();
693 assert(checkmate_move.
isValid());
694 this->recordWinByCheckmate(P, record, checkmate_move);
695 return this->winByCheckmate(P);
701 const int initial_alpha = w.
alpha(P);
703 #ifndef DONT_USE_CHECKMATE
705 testThreatmate<P>(record, in_pv);
708 record->qrecord.updateThreatmate(P, (parent ? &(parent->
threatmate()) : 0),
712 int best_value = this->minusInfty(P);
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;
729 goto move_generation_failure;
731 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
735 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
736 const int previous_node_count = nodeCount();
739 const int result = alphaBetaSearch<P>(m, w, in_pv);
747 last_alpha_update = 1;
749 mpn_cut.add(tried_moves);
750 if (this->move_type[this->curDepth()] >= common_t::ALL) {
751 setKillerMove(best_move.
move());
755 const int d = (curLimit()+200)/100;
756 this->historyTable().add(best_move.
move(), d*d);
760 assert(! this->isWinValue(
alt(P), best_value));
768 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
769 first_move_node = nodeCount() - previous_node_count;
774 #ifndef DONT_USE_CHECKMATE
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);
787 if (curLimit() < this->leafLimit())
788 goto move_generation_failure;
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()
794 || (first_move_node >= 30000));
799 # ifdef OSL_USE_RACE_DETECTOR
800 boost::mutex::scoped_lock lk(shared->lock_smp);
802 cur_smp_idle = shared->smp_idle;
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;
810 if (examineMovesOther<P>(w, best_move, best_value, tried_moves,
811 alpha_update, last_alpha_update)) {
813 assert(best_move.
player() == P);
814 if (this->move_type[this->curDepth()] >= common_t::ALL) {
815 setKillerMove(best_move.
move());
819 const int d = (curLimit()+200)/100;
820 this->historyTable().add(best_move.
move(), d*d);
823 mpn_cut.add(tried_moves);
830 catch(AlphaBeta2ParallelCommon::SplitFailed&) {
831 # if (! defined NDEBUG)
832 already_split =
false;
843 const int result = alphaBetaSearch<P>(m, w, in_pv && ! best_move.
validMove());
851 last_alpha_update = tried_moves;
854 if (this->move_type[this->curDepth()] >= common_t::ALL) {
855 setKillerMove(best_move.
move());
859 const int d = (curLimit()+200)/100;
860 this->historyTable().add(best_move.
move(), d*d);
863 mpn_cut.add(tried_moves);
872 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
875 if (tried_moves == 1 && tryPass(record, P)) {
877 goto move_generation_failure;
879 mpn.add(tried_moves);
881 this->alpha_update.add(alpha_update);
882 this->last_alpha_update.add(last_alpha_update);
886 && EnterKing::canDeclareWin<P>(state())) {
887 best_value = this->brinkmatePenalty(
alt(P),
std::max(1,16-this->curDepth())*256)
888 + this->eval.value();
895 #ifndef DONT_USE_CHECKMATE
897 if (tryCheckmateAgain<P>(record, checkmate_move,
898 nodeCount() - node_count_at_beginning,
900 assert(checkmate_move.
isValid());
901 best_value= this->winByCheckmate(P);
902 this->recordWinByCheckmate(P, record, checkmate_move);
908 assert(best_value == this->minusInfty(P) || best_move.
validMove());
910 if (this->isWinValue(
alt(P), best_value))
914 best_value = this->brinkmatePenalty(P,
std::max(1,16-this->curDepth())*256) + this->eval.value();
917 record->setAbsoluteValue(best_move, best_value, curLimit());
922 assert(best_value % 2 == 0);
923 record->setLowerBound(P, curLimit(), best_move, best_value);
928 record->setUpperBound(P, curLimit(), best_move, best_value);
931 move_generation_failure:
932 pv[this->curDepth()].clear();
935 best_value = quiesce<P>(w);
940 record->setAbsoluteValue(
MoveLogProb(), best_value, curLimit());
942 record->setLowerBound(P, curLimit(),
MoveLogProb(), best_value);
948 record->setUpperBound(P, curLimit(),
MoveLogProb(), best_value);
955 template <
class EvalT>
956 template <osl::Player P>
960 #ifdef EXPERIMENTAL_QUIESCE
961 return quiesceExp<P>(w);
963 return quiesceStable<P>(w);
967 template <
class EvalT>
968 template <osl::Player P>
976 qsearcher_t qs(*
this, *this->table);
977 Move last_move = lastMove();
980 assert(w.
alpha(P) % 2);
981 assert(w.
beta(P) % 2);
982 #ifdef CHECKMATE_COUNT
983 size_t count = checkmateSearcher().totalNodeCount();
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;
992 assert(result % 2 == 0);
996 template <
class EvalT>
997 template <osl::Player P>
1006 const int qdepth = 4;
1007 const int previous_node_count = nodeCount();
1010 quiesceRoot<P>(w, qdepth, best_move, record->
threatmate());
1012 const size_t qnode = nodeCount() - previous_node_count;
1013 this->recorder.addQuiescenceCount(qnode);
1018 template <
class EvalT>
1019 template <osl::Player P>
1029 : searcher(s), window(w),
depth(d),
result(r), threatmate(t) {
1032 searcher->eval.update(searcher->state(), searcher->lastMove());
1034 searcher->quiesce<P>(window,
depth, threatmate);
1038 template <
class EvalT>
1039 template <osl::Player P>
1045 const bool in_pv = ! w.
null();
1048 next_t helper(
this, w, depth_left, &result, threatmate);
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;
1070 template <
class EvalT>
1071 template <osl::Player P>
1075 assert(! state().inCheck(
alt(P)));
1082 assert(record.
inCheck() == state().inCheck());
1083 assert(depth_left > 0);
1085 int best_value = this->minusInfty(P);
1089 best_value = this->eval.value();
1091 const int value = this->eval.value() + this->threatmatePenalty(P);
1104 generator.
init(200, &record, this->eval, state(),
1107 int tried_moves = 0;
1111 if (quiesceWithMove<P>(prev_best, w, depth_left-1, best_move, best_value,
1121 if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1128 if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
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));
1146 template <
class EvalT>
1147 template <osl::Player P>
1151 if (state().inCheck(
alt(P))) {
1152 return this->minusInfty(
alt(P));
1157 depth_node_count_quiesce[this->curDepth()]++;
1167 int best_value = this->minusInfty(P);
1169 if (depth_left <= 0) {
1171 if (lastMove().isCapture())
1178 Move checkmate_move;
1179 bool win = isWinningState<P>(10, checkmate_move);
1181 return this->winByCheckmate(P);
1183 return this->eval.value() + this->threatmatePenalty(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();
1197 if (ImmediateCheckmate::hasCheckmateMove<P>(state())) {
1198 return this->winByCheckmate(P);
1202 Move checkmate_move;
1203 bool win = isWinningState<P>(10, checkmate_move);
1205 return this->winByCheckmate(P);
1208 generator.
init(200, &record, this->eval, state(),
1211 int tried_moves = 0;
1216 best_value = this->eval.value();
1218 const int value = this->eval.value() + this->threatmatePenalty(P);
1233 if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1240 if (quiesceWithMove<P>(m.move(), w, depth_left-1, best_move, best_value,
1247 if (tried_moves == 0) {
1248 if (lastMove().ptype() ==
PAWN && lastMove().isDrop())
1249 return this->winByFoul(P);
1250 return this->winByCheckmate(
alt(P));
1258 template <
class EvalT>
1263 const size_t new_count = shared->checkmateCount();
1264 this->recorder.setCheckmateCount(new_count);
1268 this->recorder.setCheckmateCount
1269 (checkmateSearcher().totalNodeCount());
1272 template <
class EvalT>
1282 else if (progress.value() <= 1)
1286 else if (progress.value() <= 7)
1290 else if (progress.value() <= 9)
1294 else if (progress.value() <= 10)
1306 template <
class EvalT>
1327 CArray<bool, search::SearchState2::MaxDepth>& threatmate)
1329 for (
size_t i=0; i<pv.size(); ++i) {
1330 key = key.newMakeMove(pv[i]);
1332 threatmate[i] = record
1339 template <
class EvalT>
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);
1348 shared_root->last_root_value_update =
result;
1350 if (new_stable && m != shared_root->last_root_move
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);
1362 this->shared_root->last_pv.push_back(
RootPV(root_limit, pv[0], result));
1363 this->setStable(new_stable);
1365 if (this->hasMonitor() && !this->prediction_for_speculative_search) {
1368 CArray<bool, MaxDepth> threatmate = {{ 0 }};
1369 find_threatmate(*this->table, currentHash(), pv[0], threatmate);
1370 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
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());
1379 showPV(os, result, m, new_stable ?
' ' :
'*');
1383 template <
class EvalT>
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));
1392 if (this->hasMonitor() && !this->prediction_for_speculative_search) {
1395 CArray<bool, MaxDepth> threatmate = {{ 0 }};
1396 find_threatmate(*this->table, currentHash(), pv[0], threatmate);
1397 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
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());
1406 showPV(std::cerr, result, m,
'&');
1410 template <
class EvalT>
1414 if (this->root_ignore_moves)
1415 std::cerr <<
"[" << this->root_ignore_moves->size() <<
"] ";
1416 std::cerr <<
" <" << std::setfill(
' ') << std::setw(5)
1421 template <
class EvalT>
1426 if (this->root_ignore_moves)
1427 os <<
"[" << this->root_ignore_moves->size() <<
"] ";
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]) {
1434 const double elapsed = this->elapsed();
1442 NumEffectState state = this->state();
1443 std::string str; str.reserve(200); str =
" ";
1444 for (
size_t i=0; i<pv[0].size(); ++i) {
1446 state.makeMove(pv[0][i]);
1450 = this->table->
find(HashKey(state));
1456 if (! converted.empty())
1457 os << converted << std::endl;
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";
1469 ApplyMoveOfTurn::doMove(s, pv[0][i]);
1474 template <
class EvalT>
1475 template <osl::Player P>
1485 : searcher(s), moved(md), window(w),
result(r), in_pv(p) {
1486 assert(P == md.
player());
1490 const int cur_limit = searcher->curLimit();
1493 searcher->alphaBetaSearchAfterMove<P>(moved, window, in_pv);
1494 assert(cur_limit == searcher->curLimit() || searcher->SearchState2Core::abort());
1498 template <
class EvalT>
1499 template <osl::Player P>
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());
1511 pv[curDepth()+1].clear();
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));
1518 ::isMember(state(), move))
1519 return this->winByFoul(
alt(P));
1522 const HashKey new_hash = currentHash().newHashWithMove(move);
1523 assert(P == move.player());
1526 this->pass_count.inc(P);
1529 if (! this->pass_count.loopByBothPass()) {
1531 = repetition_counter.isAlmostSennichite(new_hash);
1532 if (next_sennichite.
isDraw())
1533 return this->drawValue();
1535 return this->winByFoul(next_sennichite.
winner());
1536 assert(next_sennichite.
isNormal());
1539 if (! move.isPass()) {
1544 return this->winByLoop(
alt(P));
1546 return this->winByLoop(P);
1548 if (! move.isCapture()) {
1549 const int sacrifice_count = countSacrificeCheck2(this->curDepth());
1550 if (sacrifice_count == 2) {
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);
1555 if (offence <= deffense)
1556 offence += AdditionalEffect::count2(state(), to, P);
1557 if (offence <= deffense) {
1558 return this->winByLoop(
alt(P));
1565 NextMove<P> helper(
this, search_move, w, &result, in_pv);
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;
1572 this->pass_count.dec(P);
1577 template <
class EvalT>
1578 template <osl::Player P>
1583 for (;i<moves.size(); ++i) {
1586 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_ROOT)
1588 && moves.size() > i+1) {
1591 # ifdef OSL_USE_RACE_DETECTOR
1592 boost::mutex::scoped_lock lk(shared->lock_smp);
1594 smp_idle = shared->smp_idle;
1598 examineMovesRootPar<P>(
moves, i, window, best_move, best_value);
1600 }
catch (AlphaBeta2ParallelCommon::SplitFailed&) {
1608 if (this->elapsed() > 1.0)
1611 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
1613 monitor->rootMove(m.
move());
1615 if (this->multi_pv) {
1622 const int result = alphaBetaSearch<P>(m, window,
false);
1628 updateRootPV(P, std::cerr, result, m.move());
1630 assert(! this->isWinValue(
alt(P), result));
1637 addMultiPV(P, result, m.move());
1640 if (this->root_limit >= 1600)
1641 this->checkmate_searcher->runGC(this->table->
isVerbose(),
1642 lastMemoryUseRatio1000());
1648 template <
class EvalT>
1657 template <
class EvalT>
1663 template <
class EvalT>
1667 king_in_threat.fill(
false);
1668 if (this->shared_root->last_pv.empty())
1671 NumEffectState state = this->state();
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)
1680 this->lastMemoryUseRatio1000());
1681 assert(pv[i].isPass() || state.isValidMove(pv[i]));
1682 if (! pv[i].isPass() && ! state.isValidMove(pv[i]))
1684 std::cerr <<
"pv error " << pv[i] <<
"\n" << state;
1687 state.makeMove(pv[i]);
1689 if (state.inCheck())
1691 const HashKey key(state);
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]);
1701 const bool new_win = this->isWinningState
1702 (*checkmate_searcher, state, key, path,
1703 verify_node, checkmate_move, pv[i],
true);
1706 found = PVCheckmate;
1707 this->recordWinByCheckmate(state.turn(), record, checkmate_move);
1708 king_in_threat[
alt(state.turn())] =
true;
1711 <<
"(" << i <<
")\n";
1715 const Player T = state.turn();
1717 const bool old_threatmate = this->isWinningState
1718 (*checkmate_searcher, state, HashKey(state),
PathEncoding(T),
1720 if (! old_threatmate)
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());
1728 king_in_threat[
alt(T)] =
true;
1729 if (! old_threatmate_in_record)
1730 found = PVThreatmate;
1731 else if (found == PVStable)
1732 found = PVThreatmateNotRecord;
1735 <<
"(" << i <<
")\n";
1741 this->lastMemoryUseRatio1000());
1742 this->updateCheckmateCount();
1746 template <
class EvalT>
1750 const Player Turn = this->state().turn();
1751 Window root_window = this->fullWindow(Turn);
1752 return alphaBetaSearchRoot(root_window, best_move, limit);
1755 template <
class EvalT>
1758 int initial_limit,
size_t node_limit,
1762 this->setStartTime(MilliSeconds::now());
1763 this->setTimeAssign(assign);
1766 const time_t now = time(0);
1768 std::cerr <<
"AlphaBeta2 " <<
ctime_r(&now, ctime_buf);
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)
1779 initial_limit =
std::min(initial_limit, limit);
1781 this->recorder.resetNodeCount();
1783 double last_iteration_consumed = 0;
1784 double total_consumed = 0;
1785 int limit_iterative = initial_limit;
1787 this->shared_root->last_pv.clear();
1792 this->shared->parallel_splits = 0;
1793 this->shared->cancelled_splits.setValue(0);
1794 this->shared->parallel_abort.setValue(0);
1804 BOOST_FOREACH(
Move move, moves) {
1805 HashKey key = this->currentHash().newHashWithMove(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());
1819 std::cerr <<
"=> quiesce "
1821 while (limit_iterative < limit && ! this->stopping())
1824 std::cerr <<
"=> iteration " << limit_iterative
1825 <<
" (" << last_iteration_consumed <<
", " << total_consumed <<
" sec)"
1827 this->recorder.startSearch(limit_iterative);
1828 const int previous_node_count = this->nodeCount();
1830 for (
int i=0; i<8; ++i)
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())
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
1845 need_more_verify = findCheckmateInPV(verify_node_limit, king_in_threat);
1846 if (need_more_verify == PVStable
1847 || (i > 0 && need_more_verify == PVThreatmateNotRecord))
1849 if (this->isStableNow())
1850 this->setStable(i > 0 && king_in_threat[this->state().turn()] ==
false);
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,
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());
1867 this->updateCheckmateCount();
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()
1881 std::cerr <<
" split " << this->shared->parallel_splits <<
" cancel " << this->shared->cancelled_splits.value()
1882 <<
" abort " << this->shared->parallel_abort.value();
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())
1896 const int same_best_moves = this->shared_root->sameBestMoves();
1897 if (same_best_moves == 0) {
1899 std::cerr <<
"info: " << coef <<
" -> 0.75 by bestmove update\n";
1902 else if (same_best_moves >= 3) {
1903 const Move last_move = this->lastMove();
1905 && last_move.
to() == last_best_move.
to()
1909 std::cerr <<
"info: " << coef <<
" -> 5.0 by takeback major piece\n";
1914 if (current_time_left
1915 < last_iteration_consumed * coef)
1919 = this->table->
find(this->currentHash());
1921 record->
addNodeCount(this->nodeCount() - previous_node_count);
1925 bool node_limit_over = (this->recorder.nodeCount() *4 > node_limit);
1926 this->recorder.finishSearch(search_move.
move(),
1928 (time_over || node_limit_over) && this->table->
verboseLevel());
1929 if (time_over || node_limit_over || this->stopping()) {
1931 const char *reason =
"other reason";
1933 reason =
"memory full";
1936 else if (node_limit_over)
1937 reason =
"node count";
1940 std::cerr <<
"iteration stop at " << limit_iterative <<
" by "
1946 limit_iterative += step;
1949 std::cerr <<
"=> final iteration " << limit_iterative
1950 <<
" (" << last_iteration_consumed <<
", " << total_consumed <<
" sec)"
1953 this->recorder.startSearch(limit);
1955 for (
int i=0; i<8; ++i)
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())
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
1970 need_more_verify = findCheckmateInPV(verify_node_limit, king_in_threat);
1971 if (need_more_verify == PVStable
1972 || (i > 0 && need_more_verify == PVThreatmateNotRecord))
1974 if (this->isStableNow())
1975 this->setStable(i > 0 && king_in_threat[this->state().turn()] ==
false);
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,
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,
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());
1999 if (limit >= 2000 || this->root_ignore_moves)
2004 std::cerr <<
" extend limit to " << limit <<
" before resign\n";
2007 catch (std::exception& e)
2010 std::cerr <<
"std exception " << e.what() <<
"\n";
2014 std::cerr <<
"unknown exception\n";
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()
2032 std::cerr <<
" split " << this->shared->parallel_splits <<
" cancel " << this->shared->cancelled_splits.value()
2033 <<
" abort " << this->shared->parallel_abort.value();
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;
2046 if (additional_info && this->shared_root->root_values.size() > 1) {
2047 assert(last_best_move == this->shared_root->last_root_move);
2048 additional_info->
move = last_best_move;
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]);
2060 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2062 monitor->searchFinished();
2065 return last_best_move;
2068 template <
class EvalT>
2069 template <osl::Player P>
2076 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2078 monitor->newDepth(limit/200);
2081 assert(P == this->state().turn());
2082 assert(window.
alpha(P) % 2);
2083 assert(window.
beta(P) % 2);
2085 assert(this->curDepth() == 0);
2086 this->node_type[this->curDepth()] = base_t::PvNode;
2087 this->checkmate_searcher->setRootPlayer(P);
2090 this->shared->threadStart();
2094 = this->table->
allocate(this->currentHash(), limit);
2096 boost::scoped_ptr<SimpleHashRecord> record_if_not_allocated;
2100 record = record_if_not_allocated.get();
2103 this->setRootRecord(record);
2104 assert(this->rootRecord() == record);
2105 assert(this->hasLastRecord() && this->lastRecord() == record);
2109 int result = this->
template quiesce<P>(fullWindow(P));
2111 if (this->root_ignore_moves
2112 && this->root_ignore_moves->isMember(best_move.move()))
2115 else if (this->hasMonitor() && !this->prediction_for_speculative_search)
2120 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2122 monitor->showPV(1, this->recorder.allNodeCount(),
2123 this->elapsed(),
static_cast<int>(result*scale),
2124 best_move.move(), 0, 0, 0, 0);
2129 if (record_in_table) {
2130 int table_value = 0;
2136 if (! this->root_ignore_moves
2137 || ! this->root_ignore_moves->isMember(m.
move())) {
2145 MoveLogProbVector
moves;
2149 MoveLogProbVector raw_moves;
2150 assert(this->curLimit() > 0);
2153 generator.
init(this->curLimit()+200, record, this->eval, this->state(),
true, hash_move);
2155 raw_moves.push_back(last_best_move);
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)
2165 const HashKey key = this->currentHash().newHashWithMove(m);
2167 assert(this->state().isValidMove(m));
2173 if (this->root_ignore_moves && this->root_ignore_moves->isMember(m))
2179 ::isMember(this->state(), m))
2181 raw_moves[i].setLogProbAtMost(limit);
2182 moves.push_back(raw_moves[i]);
2187 if (moves.size() == 1
2188 || (moves.size() == 2 && moves[0].move() == moves[1].move()))
2190 best_move = moves[0];
2192 if (this->hasMonitor() && !this->prediction_for_speculative_search) {
2194 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2196 monitor->rootForcedMove(best_move.
move());
2203 #ifndef DONT_USE_CHECKMATE
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;
2216 #ifdef CHECKMATE_COUNT
2217 std::cerr <<
"limit " << limit <<
" checkmate " << checkmate_node <<
"\n";
2220 if (checkmate_node > 0)
2222 const bool my_king_in_check
2223 = this->state().hasEffectAt(
alt(P),this->state().kingSquare(P));
2224 if (my_king_in_check)
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();
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));
2240 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2242 monitor->rootLossByCheckmate();
2244 return this->winByCheckmate(
alt(P));
2249 Move checkmate_move;
2250 #ifdef CHECKMATE_COUNT
2251 size_t count = this->checkmateSearcher().totalNodeCount();
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;
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);
2274 if ((! my_king_in_check)
2277 Move threatmate_move;
2278 #ifdef CHECKMATE_COUNT
2279 size_t count = this->checkmateSearcher().totalNodeCount();
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;
2288 this->recorder.backFromCheckmateSearch();
2289 this->updateCheckmateCount();
2295 std::cerr <<
" root threatmate " << threatmate_move <<
"\n";
2300 if (! this->state().hasPieceOnStand(P, ptype))
2302 NumEffectState state(this->state().emulateHandPiece(P,
alt(P), ptype));
2303 state.setTurn(
alt(P));
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());
2312 this->checkmate_searcher->runGC(this->table->
isVerbose(),
2313 this->lastMemoryUseRatio1000());
2316 int best_value = ValueNone;
2320 if (limit >= 1000 && ! moves.empty() && window == fullWindow(P))
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());
2327 const Window window_copy = window;
2328 window.
alpha(P) = root_alpha;
2332 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2334 monitor->rootFirstMove(moves[0].move());
2337 const int result = this->
template alphaBetaSearch<P>(moves[0], window,
true);
2341 best_move = moves[0];
2343 this->updateRootPV(P, std::cerr, result, moves[0].move());
2349 this->showFailLow(result, moves[0].move());
2351 if (this->hasMonitor() && !this->prediction_for_speculative_search) {
2354 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2356 monitor->showFailLow(this->root_limit/200, this->recorder.allNodeCount(),
2357 this->elapsed(),
static_cast<int>(result*scale),
2361 this->setStable(
false);
2362 window = window_copy;
2364 this->checkmate_searcher->runGC(this->table->
isVerbose(),
2365 this->lastMemoryUseRatio1000());
2368 for (; i<moves.size() && best_value == ValueNone
2369 && window == fullWindow(P); ++i) {
2374 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2376 monitor->rootMove(m.
move());
2379 const int result = this->
template alphaBetaSearch<P>(m, window,
true);
2384 this->updateRootPV(P, std::cerr, result, m.move());
2386 assert(! this->isWinValue(
alt(P), result));
2389 else if (result == ValueNone)
2390 this->setStable(
false);
2391 this->checkmate_searcher->runGC(this->table->
isVerbose(),
2392 this->lastMemoryUseRatio1000());
2396 this->
template examineMovesRoot<P>(
moves, i, window, best_move, best_value);
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]);
2407 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2409 monitor->depthFinishedNormally(limit/200);
2412 }
catch (std::runtime_error& e) {
2414 std::cerr << e.what() <<
"\n";
2415 assert(best_value % 2 == 0);
2417 this->restoreRootState();
2418 if (best_value != ValueNone)
2419 record->
setLowerBound(P, this->curLimit(), best_move, best_value);
2421 && best_move.
move() != last_best_move.
move()) {
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]);
2434 this->shared->waitAll();
2440 assert(best_value % 2 == 0);
2441 if (best_value != ValueNone)
2442 record->
setLowerBound(P, this->curLimit(), best_move, best_value);
2445 this->shared->waitAll();
2448 if (best_value == ValueNone
2449 && this->hasMonitor() && !this->prediction_for_speculative_search)
2453 const int value = this->winByCheckmate(
alt(P));
2454 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
2456 monitor->showPV(limit/200, this->recorder.allNodeCount(),
2457 this->elapsed(),
static_cast<int>(value*scale),
2464 template <
class EvalT>
2470 this->setRootRecord(record);
2471 this->move_type[this->curDepth()] = base_t::INITIAL;
2474 template <
class EvalT>
2477 assert(this->state().isValidMove(move));
2479 this->eval.update(this->state(), move);
2482 = this->table->
allocate(this->currentHash(), this->curLimit());
2484 this->move_type[this->curDepth()] = base_t::INITIAL;
2486 this->setCurrentRecord(record);
2489 template <
class EvalT>
2496 template <
class EvalT>
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]) {
2511 base_t::depth_node_count[i]+base_t::depth_node_count_quiesce[i]);
2514 int unit =
std::max(max_count/79, 100);
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,
'+')
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
2530 template <
class EvalT>
2535 base_t::depth_node_count.fill(0);
2536 base_t::depth_node_count_quiesce.fill(0);