00001 #ifndef _MTDF_TCC
00002 #define _MTDF_TCC
00003 #include "osl/search/mtdf.h"
00004 #include "osl/search/searchMoveVector.h"
00005 #include "osl/search/shouldPromoteCut.h"
00006 #include "osl/category/categoryListUtil.h"
00007 #include "osl/move_classifier/pawnDropCheckmate.h"
00008 #include "osl/move_classifier/moveAdaptor.h"
00009 #include "osl/record/csa.h"
00010 #ifdef OSL_SMP
00011 # include "osl/search/parallelSearch.h"
00012 # include "osl/misc/nonBlockDelete.h"
00013 #endif
00014 #include <stdexcept>
00015 #include <iostream>
00016
00017
00018
00019
00020
00021 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00022 osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00023 MTDF(const HashEffectState& s, checkmate_t& c, Table& t, Recorder& r)
00024 : base_t(r, &t), checkmate_searcher(&c),
00025 memory_tester(s, *checkmate_searcher, &t, r),
00026 timer(60), root_ignore_moves(0)
00027 {
00028 setInitialGuess();
00029 checkmate_searcher->setVerbose(base_t::table->isVerbose());
00030 #ifdef OSL_SMP
00031 parallelSearch.setVerbose(t.isVerbose());
00032 memory_tester.shareCheckmateHolder(checkmate_holder);
00033 #endif
00034 }
00035 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00036 osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00037 ~MTDF()
00038 {
00039 }
00040
00041 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00042 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00043 setInitialGuess(int guess)
00044 {
00045 threshold = (guess & (~1));
00046 threshold -= eval::delta(memory_tester.state().getTurn());
00047 assert(threshold % 2);
00048 }
00049
00050 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00051 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00052 setInitialGuess()
00053 {
00054 const Eval eval(memory_tester.state());
00055 setInitialGuess(eval.value());
00056 }
00057
00058 #ifdef OSL_SMP
00059 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00060 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00061 setCheckmateSearcher(checkmate_t * c, const Worker *w)
00062 {
00063 checkmate_searcher=c;
00064 memory_tester.setCheckmateSearcher(c, w);
00065 }
00066 #endif
00067
00068 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00069 bool osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00070 isReasonableMove(Move move, int pawn_sacrifice)
00071 {
00072 return memory_tester.isReasonableMove(move, pawn_sacrifice);
00073 }
00074
00075 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00076 const osl::misc::AlarmSwitch
00077 osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00078 alarmSwitch()
00079 {
00080 return memory_tester.alarmSwitch();
00081 }
00082 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00083 const osl::search::BigramKillerMove&
00084 osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00085 bigramKillerMove()
00086 {
00087 return memory_tester.bigramKillerMove();
00088 }
00089
00090 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00091 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00092 setBigramKillerMove(const BigramKillerMove& killers)
00093 {
00094 memory_tester.setBigramKillerMove(killers);
00095 }
00096
00097
00098
00099
00100
00101 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00102 const osl::Move osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00103 computeBestMove(int limit, const RealTime& shedule)
00104 {
00105 const bool use_signal_timer = ! shedule.isInvalid();
00106 if (use_signal_timer)
00107 {
00108 timer = shedule;
00109 memory_tester.setTimeOut(timer.getTimeLeftInSeconds());
00110 }
00111 else
00112 {
00113 timer = RealTime(6000);
00114 }
00115 Move best_move;
00116 #if OSL_SMP
00117 parallelSearch.setMasterAlarm(alarmSwitch());
00118 #endif
00119 try
00120 {
00121 if (memory_tester.state().getTurn()==BLACK)
00122 best_move = computeBestMoveOfPlayer<BLACK>(limit);
00123 else
00124 best_move = computeBestMoveOfPlayer<WHITE>(limit);
00125 }
00126 catch (...)
00127 {
00128 #ifdef OSL_SMP
00129 parallelSearch.waitAll();
00130 #endif
00131 if (use_signal_timer)
00132 memory_tester.resetTimeOut();
00133 throw;
00134 }
00135 #ifdef OSL_SMP
00136 parallelSearch.waitAll();
00137 #endif
00138 if (use_signal_timer)
00139 memory_tester.resetTimeOut();
00140 return best_move;
00141 }
00142
00143 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00144 const osl::Move osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00145 computeBestMoveIteratively(int limit, const int step,
00146 const int initial_limit, int node_limit,
00147 const RealTime& initial_stop_shedule)
00148 {
00149 setStopSchedule(initial_stop_shedule);
00150 double total_consumed = 0;
00151 double last_iteration_consumed = 0;
00152
00153 base_t::recorder.resetNodeCount();
00154 int limit_iterative=initial_limit;
00155 Move best_move = Move::INVALID();
00156 try
00157 {
00158 RealTime current_timer = stopSchedule();
00159 best_move = computeBestMove(0, current_timer);
00160 while (limit_iterative < limit)
00161 {
00162 current_timer = stopSchedule();
00163 if (base_t::table->isVerbose())
00164 std::cerr << "iteration " << limit_iterative
00165 << " " << current_timer.getTimeLeftInDouble() << " left\n"
00166 << std::flush;
00167 best_move = computeBestMove(limit_iterative, current_timer);
00168 if (base_t::table->isVerbose())
00169 std::cerr << "selected " << record::csa::show(best_move) << "\n";
00170 if (best_move.isNormal())
00171 {
00172 bool time_over = false;
00173 last_iteration_consumed = timer.getConsumedInDouble();
00174 total_consumed += last_iteration_consumed;
00175
00176 if (hasSchedule())
00177 {
00178 const double current_time_left
00179 = stopSchedule().getTimeLeftInDouble();
00180 if (current_time_left
00181 < last_iteration_consumed * nextIterationCoefficient())
00182 {
00183 time_over = true;
00184 if (base_t::table->isVerbose())
00185 std::cerr << "time limit " << current_time_left
00186 << " < " << last_iteration_consumed
00187 << " (*" << nextIterationCoefficient() << ")\n";
00188 }
00189 if (! time_over)
00190 {
00191 SimpleHashRecord *record
00192 = base_t::table->find(memory_tester.currentHash());
00193 if (record)
00194 {
00195 record->setSumNodeCountOfChildren();
00196 if (base_t::table->isVerbose())
00197 record->dumpNodeCount(std::cerr, 3);
00198 }
00199 }
00200 }
00201
00202
00203 if (time_over || (base_t::recorder.nodeCount() *8 > node_limit))
00204 {
00205 if (base_t::table->isVerbose())
00206 std::cerr << "iteration stop at " << limit_iterative << "\n";
00207 return best_move;
00208 }
00209 memory_tester.testTimeOut();
00210 }
00211 limit_iterative += step;
00212 }
00213 if (base_t::table->isVerbose())
00214 std::cerr << "final iteration " << limit
00215 << " " << stopSchedule().getTimeLeftInDouble() << " left\n";
00216 while (true)
00217 {
00218 best_move = computeBestMove(limit, stopSchedule());
00219 if (best_move.isNormal())
00220 break;
00221 memory_tester.testTimeOut();
00222
00223
00224 if (limit >= 2000)
00225 break;
00226
00227 limit += 200;
00228 if (base_t::table->isVerbose())
00229 std::cerr << "extend limit to " << limit << " before resign\n";
00230 }
00231 }
00232 catch (std::exception& e)
00233 {
00234 std::cerr << "std exception " << e.what() << "\n";
00235 }
00236 catch (...)
00237 {
00238 std::cerr << "unknown exception\n";
00239 #ifndef NDEBUG
00240 throw;
00241 #endif
00242 }
00243 if (base_t::table->isVerbose())
00244 std::cerr << "selected " << record::csa::show(best_move)
00245 << " at limit " << limit_iterative << "\n";
00246 return best_move;
00247 }
00248
00249 namespace osl
00250 {
00251 namespace search
00252 {
00253
00254
00255
00256 struct ResetRootRecord
00257 {
00258 SearchState *state;
00259 bool reset;
00260 ResetRootRecord(SearchState *s, bool r) : state(s), reset(r)
00261 {
00262 }
00263 ~ResetRootRecord()
00264 {
00265 if (reset)
00266 state->setRootRecord(0);
00267 }
00268 };
00269 }
00270 }
00271
00276 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00277 template <osl::Player P>
00278 const osl::Move osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00279 computeBestMoveOfPlayer(int limit)
00280 {
00281 if (base_t::isWinValue(P, threshold))
00282 {
00283 threshold = base_t::windowMax(P) - eval::delta(P);
00284 }
00285 assert(threshold % 2);
00286 base_t::recorder.startSearch(limit);
00287 if (base_t::table->isVerbose())
00288 std::cerr << "threshold " << threshold << "\n";
00289
00290 SimpleHashRecord *record_in_table
00291 = base_t::table->allocate(memory_tester.currentHash(), limit);
00292 SimpleHashRecord *record = record_in_table;
00293 boost::scoped_ptr<SimpleHashRecord> record_if_not_allocated;
00294 if (! record_in_table)
00295 {
00296 record_if_not_allocated.reset(new SimpleHashRecord());
00297 record = record_if_not_allocated.get();
00298 }
00299 ResetRootRecord reset_root_record_lock(&memory_tester, record_if_not_allocated.get());
00300 assert(record);
00301 assert(memory_tester.rootRecord() == 0
00302 || memory_tester.rootRecord() == record);
00303 memory_tester.setRootRecord(record);
00304
00305
00306 SearchMove best_move_in_table;
00307 if (record_in_table)
00308 {
00309 best_move_in_table = record->bestMove();
00310 if (best_move_in_table.getMove().isNormal())
00311 {
00312
00313 int table_value;
00314 if (record->template hasGreaterLowerBound<P>
00315 (limit, base_t::winThreshold(P), table_value))
00316 return best_move_in_table.getMove();
00317 }
00318 if ((! best_move_in_table.getMove().isNormal())
00319 || (best_move_in_table.record == 0))
00320 {
00321 best_move_in_table = SearchMove();
00322 }
00323 }
00324
00325
00326 SearchMoveSet& move_set = record->moves();
00327 while (true)
00328 {
00329 const category::CategoryEnv env(&memory_tester.state(), limit,
00330 &memory_tester.history(),
00331 memory_tester.getEval().progress32(),
00332 record, 0,
00333 &memory_tester.historyTable());
00334 CategoryListUtil::gatherAllMoves<MoveGenerator>(env, move_set);
00335 if (move_set.size() > 1 || limit > 2000 || limit == 0)
00336 break;
00337 limit += 100;
00338 }
00339 if (move_set.size() == 1)
00340 return move_set.front().getMove();
00341
00342 const bool my_king_in_check
00343 = memory_tester.state().hasEffectBy(alt(P),memory_tester.state().template getKingPosition<P>());
00344 #ifndef DONT_USE_CHECKMATE
00345
00346 if (record_in_table)
00347 {
00348 const int check_limit
00349 = ((limit < 500)
00350 ? 800
00351 : ((limit < 700) ? 3800 : 4000));
00352 const int checkmate_max = std::max((size_t)20000,
00353 checkmate::limitToCheckCount(check_limit));
00354 const int checkmate_node = record->qrecord.checkmateNodesLeft(checkmate_max);
00355 if (checkmate_node > 0)
00356 {
00357 PathEncoding path = memory_tester.path();
00358 if (my_king_in_check)
00359 {
00360
00361 base_t::recorder.gotoCheckmateSearch(memory_tester.state(), checkmate_node);
00362 const bool lose = memory_tester.template isLosingState<P>(checkmate_node);
00363 base_t::recorder.backFromCheckmateSearch();
00364 if (lose)
00365 {
00366 base_t::recordLoseByCheckmate(P, record);
00367 return Move::INVALID();
00368 }
00369 }
00370
00371 {
00372 Move checkmate_move;
00373 base_t::recorder.gotoCheckmateSearch(memory_tester.state(), checkmate_node);
00374 const bool win = memory_tester.template isWinningState<P>
00375 (checkmate_node, checkmate_move, record->qrecord.attack_oracle);
00376 base_t::recorder.backFromCheckmateSearch();
00377 if (win)
00378 {
00379 base_t::recordWinByCheckmate(P, record, checkmate_move);
00380 return checkmate_move;
00381 }
00382 }
00383
00384 if ((! my_king_in_check)
00385 && (! record->threatmate().isThreatmate(P)))
00386 {
00387 Move threatmate_move;
00388
00389 base_t::recorder.gotoCheckmateSearch(memory_tester.state(), checkmate_node);
00390 const bool threatmate
00391 = memory_tester.template isThreatmateState<P>
00392 (checkmate_node, threatmate_move, record->qrecord.threatmate_oracle);
00393 base_t::recorder.backFromCheckmateSearch();
00394 if (threatmate)
00395 {
00396 record->threatmate().setThreatmate(P, threatmate_move);
00397 if (base_t::table->isVerbose())
00398 std::cerr << "root threatmate " << threatmate_move << "\n";
00399 }
00400 }
00401 }
00402 }
00403 #endif
00404
00407 SearchMoveSorter<P> lower_moves, higher_moves;
00408
00413 int current_value = base_t::minusInfty(P);
00414 upper_bound = base_t::minusInfty(alt(P));
00415 lower_bound = base_t::minusInfty(P);
00416
00417 base_t::recorder.newCategory("table",limit);
00418 if (base_t::validTableMove(memory_tester.state(), best_move_in_table.moveLogProb(), limit)
00419 && (root_ignore_moves == 0 || ! root_ignore_moves->isMember(best_move_in_table.getMove())))
00420 {
00421 SearchMove trying_move = best_move_in_table;
00422 trying_move.setLogProbAtMost(Probabilities::TableMove);
00423 int val = base_t::minusInfty(P);
00424 for (int i=0; i<2; ++i)
00425 {
00426 if (i > 0)
00427 {
00428 if (base_t::isWinValue(alt(P), val))
00429 break;
00430 threshold = EvalTraits<P>::max(current_value - eval::delta(P)
00431 + Eval::captureValue(newPtypeO(P,PAWN)),
00432 base_t::winThreshold(alt(P)));
00433 current_value = base_t::minusInfty(P);
00434 }
00435 if (testMove<P>(trying_move, val, current_value, limit))
00436 {
00437 if (base_t::isWinValue(alt(P), current_value))
00438 return trying_move.getMove();
00439 threshold = current_value + eval::delta(P);
00440
00441 SearchMove *stored_move = move_set.find(trying_move.getMove());
00442 higher_moves.insert(std::make_pair(current_value, stored_move));
00443 break;
00444 }
00445 }
00446 if (higher_moves.empty() && (! base_t::isWinValue(alt(P), val)))
00447 {
00448 threshold = current_value - eval::delta(P);
00449 current_value = base_t::minusInfty(P);
00450 }
00451 }
00452
00453 const int qvalue
00454 = memory_tester.template quiescenceValue<P>(base_t::winThreshold(alt(P)),
00455 base_t::winThreshold(P));
00456 if (limit == 0)
00457 return record->qrecord.bestMove();
00458
00459 if (higher_moves.empty())
00460 {
00461 const int safe_threshold
00462 = qvalue + Eval::captureValue(newPtypeO(P,PAWN))*2 - eval::delta(P);
00463 if (EvalTraits<P>::betterThan(threshold, safe_threshold))
00464 {
00465 threshold = safe_threshold;
00466 current_value = base_t::minusInfty(P);
00467 threshold = EvalTraits<P>::max(threshold, current_value+eval::delta(P));
00468 }
00469 }
00470 if (record->qrecord.bestMove().isNormal())
00471 {
00472 const MoveLogProb quiescence_move(record->qrecord.bestMove(),
00473 Probabilities::KillerMove-1);
00474 move_set.assignIfBetter(quiescence_move);
00475 }
00476
00477 SearchMoveVector all_moves;
00478 {
00479 SearchMoveSet::range r(move_set);
00480 for (SearchMoveSet::iterator p=r.first; p!=r.last; ++p) {
00481 if (root_ignore_moves && root_ignore_moves->isMember(p->getMove()))
00482 continue;
00483 if (move_classifier::MoveAdaptor<move_classifier::PawnDropCheckmate<P> >
00484 ::isMember(memory_tester.state(), p->getMove()))
00485 continue;
00486 if (! my_king_in_check)
00487 if (p->getMove().isPass()
00488 || ShouldPromoteCut::canIgnoreAndNotDrop(p->getMove()))
00489 continue;
00490
00491 if (higher_moves.empty()
00492 || (p->getMove() != higher_moves.begin()->second->getMove()))
00493 {
00494 p->setLogProbAtMost(1000);
00495 if (p->getMove().isNormal() && (p->getLogProb() <= limit))
00496 all_moves.push_back(&*p);
00497 }
00498 }
00499 }
00500 all_moves.sortByValue<P>(threshold + Eval::captureValue(newPtypeO(P,PAWN))*2);
00501 Move best_move;
00502 examineMoves<P>("uniqued moves", current_value, limit, all_moves,
00503 lower_moves, higher_moves);
00504 if (higher_moves.empty())
00505 {
00506 best_move
00507 = retryByLowerF<P>(record_in_table, limit, lower_moves, higher_moves);
00508 }
00509 else
00510 {
00511
00512 best_move = selectBestMoveByHigherF<P>(record_in_table, limit,
00513 lower_moves, higher_moves);
00514 }
00515 #ifdef OSL_SMP
00516 base_t::recorder.setCheckmateCount(checkmate_holder->totalNodeCount());
00517 #else
00518 base_t::recorder.setCheckmateCount(checkmate_searcher->totalNodeCount());
00519 #endif
00520 const double consumed = timer.getConsumedInDouble();
00521 base_t::recorder.finishSearch(best_move, consumed,base_t::table->isVerbose());
00522 return best_move;
00523 }
00524
00525 #ifdef OSL_SMP
00526 namespace osl
00527 {
00528 namespace search
00529 {
00530 struct MtdfParShared
00531 {
00532 const SearchMoveVector moves;
00533 vector<int> values;
00534 vector<int> thresholds;
00535 int current_value;
00536 int threshold;
00537 int lower_bound;
00539 bool stopped;
00540
00541 LightMutex mutex;
00542
00543 MtdfParShared(const SearchMoveVector& m, int initial_values,
00544 int current_value, int threshold, int lb)
00545 : moves(m), values(moves.size(), initial_values),
00546 thresholds(moves.size(), 0), current_value(current_value),
00547 threshold(threshold), lower_bound(lb), stopped(false)
00548 {
00549 }
00550 };
00551
00552 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities,typename framework_t,Player Turn>
00553 class MtdfParHelper : public JobContent
00554 {
00555 framework_t f;
00556 typedef typename framework_t::checkmate_t checkmate_t;
00557 typedef CheckmateSearcherHolder<checkmate_t> holder_t;
00558 boost::shared_ptr<MtdfParShared> shared;
00559 holder_t *checkmate_holder;
00560 int limit;
00561 int index, last;
00562 public:
00563 MtdfParHelper(int priority,
00564 const boost::shared_ptr<MtdfParShared>& shared,
00565 framework_t const& f1, holder_t *holder,
00566 int limit, int index, int last)
00567 : JobContent(priority), f(f1), shared(shared),
00568 checkmate_holder(holder),
00569 limit(limit), index(index), last(last) {
00570 }
00571 void setIndex(int newIndex) { index=newIndex;}
00572 void operator()(void) {
00573 checkmate_t *my_checkmate = checkmate_holder->clone(getWorker());
00574 f.setCheckmateSearcher(my_checkmate, getWorker());
00575 f.template examineMovesParBlock<Turn>(shared, limit, index, last);
00576 setFinished(true);
00577 }
00578 };
00579 }
00580 }
00581
00582
00583 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00584 template <osl::Player P>
00585 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00586 examineMovesParBlock(const boost::shared_ptr<MtdfParShared>& shared,
00587 int limit, size_t index, size_t last)
00588 {
00589 assert(last <= shared->moves.size());
00590 assert(last - index > 0);
00591 int my_current_value;
00592 {
00593 LightMutex::scoped_lock lk(shared->mutex);
00594 threshold= shared->threshold;
00595 lower_bound = shared->lower_bound;
00596 my_current_value= shared->current_value;
00597 }
00598 if (base_t::isWinValue(P,my_current_value)) {
00599 shared->stopped = true;
00600 return;
00601 }
00602 const int relax_value = Eval::captureValue(newPtypeO(alt(P),PAWN))/2/8;
00603 if (last - index == 1) {
00604 int val;
00605 shared->thresholds[index]=threshold;
00606 if (EvalTraits<P>::betterThan(threshold, upper_bound))
00607 upper_bound = (threshold + relax_value)&(~1);
00608 if (testMove<P>(*(shared->moves[index]), val, my_current_value, limit))
00609 {
00610 threshold = my_current_value + eval::delta(P);
00611 {
00612 LightMutex::scoped_lock lk(shared->mutex);
00613 if(EvalTraits<P>::betterThan(threshold, shared->threshold))
00614 shared->threshold=threshold;
00615 if(EvalTraits<P>::betterThan(my_current_value, shared->current_value))
00616 shared->current_value=my_current_value;
00617 if(EvalTraits<P>::betterThan(lower_bound, shared->lower_bound))
00618 shared->lower_bound=lower_bound;
00619 }
00620 }
00621 shared->values[index]=val;
00622 return;
00623 }
00624 typedef MtdfParHelper<Eval,MoveGenerator,Table,Recorder,Probabilities,MTDF,P> helper_t;
00625 int priority=index;
00626 boost::shared_ptr<helper_t>
00627 helper(new helper_t(priority, shared, *this, checkmate_holder.get(),
00628 limit, index+1, last));
00629 Job job(helper);
00630 Worker *worker=parallelSearch.getWorker();
00631 {
00632 Job current = worker->getCurrentJob();
00633 current.addChildJob(helper);
00634 }
00635 while (last - index > 0) {
00636 int my_current_value;
00637 {
00638 LightMutex::scoped_lock lk(shared->mutex);
00639 my_current_value= shared->current_value;
00640 threshold= shared->threshold;
00641 lower_bound = shared->lower_bound;
00642 }
00643 if (base_t::isWinValue(P, my_current_value)){
00644 job.stopNow();
00645 shared->stopped = true;
00646 return;
00647 }
00648 if (last - index > 1)
00649 worker->push_back(job);
00650 int val;
00651 shared->thresholds[index]=threshold;
00652 bool ret=false;
00653 try {
00654 if (EvalTraits<P>::betterThan(threshold, upper_bound))
00655 upper_bound = (threshold + relax_value)&(~1);
00656 ret=testMove<P>(*(shared->moves[index]), val, my_current_value, limit);
00657 }
00658 catch (StopNow& e){
00659 shared->stopped = true;
00660 std::cerr << "break worker " << worker->threadId() << "\n";
00661 if (!worker->pop_back_job()) {
00662 job.stopNow();
00663 }
00664 throw e;
00665 }
00666 if (ret)
00667 {
00668 threshold = my_current_value + eval::delta(P);
00669 {
00670 LightMutex::scoped_lock lk(shared->mutex);
00671 if(EvalTraits<P>::betterThan(threshold, shared->threshold))
00672 shared->threshold=threshold;
00673 if(EvalTraits<P>::betterThan(my_current_value, shared->current_value))
00674 shared->current_value=my_current_value;
00675 if(EvalTraits<P>::betterThan(lower_bound, shared->lower_bound))
00676 shared->lower_bound=lower_bound;
00677 }
00678 }
00679 shared->values[index]=val;
00680 ++index;
00681 if (last - index > 0) {
00682 if (worker->pop_back_job()) {
00683 helper->setIndex(index+1);
00684 helper->setFinished(false);
00685 helper->setPriority(index);
00686 }
00687 else{
00688 #ifdef ONE_THREAD_PER_PROC
00689 DecActiveHelper dec_lock(parallelSearch);
00690 while (!helper->isFinished()) {
00691 Job another_job;
00692 try
00693 {
00694 another_job=parallelSearch.getJobNonBlock(worker);
00695 }
00696 catch (StopNow&)
00697 {
00698 helper->stopNow();
00699 throw;
00700 }
00701 if (! another_job.isNull()) {
00702 try{
00703 SetCurrentJobLock lk(*worker,another_job);
00704 IncActiveHelper inc_lock(parallelSearch);
00705 another_job();
00706 }
00707 catch (StopNow& e) {
00708 std::cerr << "ignore StopNow "
00709 << &another_job << "\n";
00710 }
00711 }
00712 else {
00713 boost::thread::yield();
00714 }
00715 }
00716 #else
00717 helper->waitResult();
00718 #endif
00719 return;
00720 }
00721 }
00722 }
00723 }
00724
00725 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00726 template <osl::Player P>
00727 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00728 examineMovesPar(int& current_value, int limit, const SearchMoveVector& moves,
00729 SearchMoveSorter<P>& lower_moves, SearchMoveSorter<P>& higher_moves)
00730 {
00731 boost::shared_ptr<MtdfParShared> shared
00732 (new MtdfParShared(moves, base_t::winThreshold(alt(P)), current_value,
00733 threshold, lower_bound));
00734 const int block_size = 8;
00735 for (size_t first=0; first<moves.size(); first+=block_size)
00736 {
00737 if (base_t::isWinValue(P, current_value))
00738 {
00739 assert(! higher_moves.empty());
00740 return;
00741 }
00742 const size_t last = std::min(moves.size(), first+block_size);
00743 examineMovesParBlock<P>(shared, limit, first, last);
00744 current_value= shared->current_value;
00745 threshold= shared->threshold;
00746 lower_bound = shared->lower_bound;
00747 bool all_even = true;
00748 for (size_t i=first; i<last; i++) {
00749 if (EvalTraits<P>::betterThan(shared->values[i],shared->thresholds[i]))
00750 higher_moves.insert(std::make_pair(shared->values[i], moves[i]));
00751 if (! shared->thresholds[i] % 2)
00752 all_even = false;
00753 }
00754 memory_tester.testTimeOut();
00755 assert(shared->stopped || all_even);
00756 if (higher_moves.empty())
00757 {
00758 for (size_t i=first; i<last; i++)
00759 lower_moves.insert(std::make_pair(shared->values[i], moves[i]));
00760 typename SearchMoveSorter<P>::const_reverse_iterator best = lower_moves.rbegin();
00761 #if (__GNUC__ >= 4) && ! (defined __APPLE__)
00762 assert(best != lower_moves.rend());
00763 #endif
00764 threshold = best->first - eval::delta(P);
00765 threshold += Eval::captureValue(newPtypeO(P,PAWN));
00766 threshold = EvalTraits<P>::max(threshold, base_t::winThreshold(alt(P)));
00767 current_value = threshold - eval::delta(P);
00768 }
00769 }
00770 }
00771
00772 #endif
00773
00774 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00775 template <osl::Player P>
00776 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00777 examineMoves(const char *category_name,
00778 int& current_value, int limit, const SearchMoveVector& moves,
00779 SearchMoveSorter<P>& lower_moves, SearchMoveSorter<P>& higher_moves)
00780 {
00781 base_t::recorder.newCategory(category_name, limit);
00782 #ifdef OSL_SMP
00783 if (moves.size()>1)
00784 {
00785 examineMovesPar<P>(current_value, limit, moves, lower_moves, higher_moves);
00786 return;
00787 }
00788 #endif
00789 for (SearchMoveVector::const_iterator p=moves.begin(); p!=moves.end(); ++p)
00790 {
00791 if (base_t::isWinValue(P, current_value))
00792 {
00793 assert(! higher_moves.empty());
00794 return;
00795 }
00796 int val;
00797 if (testMove<P>(**p, val, current_value, limit))
00798 {
00799 threshold = current_value + eval::delta(P);
00800 higher_moves.insert(std::make_pair(current_value, *p));
00801 if ((moves.size() > 30) && base_t::table->isVerbose())
00802 {
00803 std::cerr << ".";
00804 }
00805 }
00806 if (higher_moves.empty()
00807 && (! base_t::isWinValue(alt(P), val)))
00808 {
00809
00810 lower_moves.insert(std::make_pair(val, *p));
00811 threshold = val - eval::delta(P);
00812 threshold += Eval::captureValue(newPtypeO(P,PAWN));
00813 threshold = EvalTraits<P>::max(threshold, base_t::winThreshold(alt(P)));
00814 current_value = threshold - eval::delta(P);
00815 }
00816 }
00817 assert(higher_moves.isValidAll());
00818 }
00819
00825 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00826 template <osl::Player P>
00827 const osl::Move osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00828 retryByLowerF(SimpleHashRecord *record, int limit,
00829 SearchMoveSorter<P>& lower_moves, SearchMoveSorter<P>& higher_moves)
00830 {
00831 assert(higher_moves.empty());
00832 assert(lower_moves.isValidAll());
00833 SearchMoveVector moves;
00834 while (higher_moves.empty() && (lower_moves.size() > 1))
00835 {
00836 base_t::recorder.recordTopLevelLowFail(lower_moves.begin()->second->moveLogProb(),
00837 threshold);
00838 if (base_t::table->isVerbose())
00839 std::cerr << "low fail " << threshold << "\n";
00840 upper_bound = lower_moves.begin()->first;
00841 const int old_threshold = threshold;
00842 for (typename SearchMoveSorter<P>::const_iterator p=lower_moves.begin(); p!=lower_moves.end(); ++p)
00843 moves.push_back(p->second);
00844 lower_moves.clear();
00845
00846 int current_value = base_t::minusInfty(P);
00847 examineMoves<P>("low fail", current_value, limit,
00848 moves, lower_moves, higher_moves);
00849 moves.clear();
00850 threshold += Eval::captureValue(newPtypeO(P,PAWN))*4;
00851 threshold = EvalTraits<P>::max(threshold, base_t::winThreshold(alt(P)));
00852 if (old_threshold == threshold)
00853 return Move::INVALID();
00854 }
00855
00856 if (! higher_moves.empty())
00857 return selectBestMoveByHigherF<P>(record, limit,
00858 lower_moves, higher_moves);
00859
00860 if (lower_moves.size() == 0)
00861 return Move::INVALID();
00862
00863 assert(lower_moves.size() == 1);
00864 const SearchMove *best_move = lower_moves.begin()->second;
00865 const int val = lower_moves.begin()->first;
00866 assert(limit >= 0);
00867 if (record)
00868 base_t::recordLowerBound(P, record, limit, *best_move, val);
00869
00870
00871 return best_move->getMove();
00872 }
00873
00874 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00875 template <osl::Player P>
00876 const osl::Move osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00877 selectBestMoveByHigherF(SimpleHashRecord *record,
00878 int limit, SearchMoveSorter<P>& lower_moves,
00879 SearchMoveSorter<P>& higher_moves)
00880 {
00881 assert(higher_moves.isValidAll());
00882 assert(lower_moves.isValidAll());
00883 base_t::recorder.recordTopLevelHighFail(higher_moves.begin()->second->moveLogProb(),
00884 threshold);
00885
00886 {
00887 assert(! higher_moves.empty());
00888 int current_value = higher_moves.begin()->first;
00889 threshold = current_value + eval::delta(P);
00890 SearchMoveVector moves_maybe_beyond_f;
00891 for (typename SearchMoveSorter<P>::const_iterator p=lower_moves.begin();
00892 p!=lower_moves.end(); ++p)
00893 {
00894
00895 if (! EvalTraits<P>::betterThan(p->first, threshold))
00896 break;
00897 moves_maybe_beyond_f.push_back(p->second);
00898 }
00899 examineMoves<P>("high fail", current_value, limit,
00900 moves_maybe_beyond_f, lower_moves, higher_moves);
00901 }
00902 const int triage_value = Eval::captureValue(newPtypeO(alt(P),PAWN))/2;
00903 if (higher_moves.size() > 32)
00904 triageMovesSpeculatively<P>(higher_moves, limit, triage_value*8);
00905 if (higher_moves.size() > 16)
00906 triageMovesSpeculatively<P>(higher_moves, limit, triage_value*4);
00907 triageMovesSpeculatively<P>(higher_moves, limit, triage_value);
00908 triageMovesSpeculatively<P>(higher_moves, limit, triage_value/8);
00909
00910 while (higher_moves.size() > 1)
00911 {
00912 if (base_t::table->isVerbose())
00913 {
00914 std::cerr << "higher " << higher_moves.size() << ":\t";
00915 higher_moves.summary(4);
00916 }
00917 typename SearchMoveSorter<P>::iterator p = higher_moves.begin();
00918 int best_value = p->first;
00919 if (base_t::isWinValue(P, best_value))
00920 {
00921
00922 break;
00923 }
00924
00925 SearchMoveSorter<P> next_jobs;
00926 next_jobs.insert(*p);
00927 while (++p != higher_moves.end())
00928 {
00929 threshold = best_value + eval::delta(P);
00930 if (EvalTraits<P>::betterThan(threshold, upper_bound))
00931 {
00932
00933 upper_bound = (threshold + triage_value/8)&(~1);
00934 }
00935
00936 const SearchMove *target = p->second;
00937 SearchMove move_to_try = *target;
00938 if (higher_moves.size() <= 3)
00939 move_to_try.setLogProbAtMost(Probabilities::ReSearch);
00940
00941 int val,max_value=threshold-eval::delta(P);
00942 if (testMove<P>(move_to_try, val, max_value, limit))
00943 {
00944 best_value = val;
00945 next_jobs.insert(std::make_pair(val, target));
00946 if (base_t::isWinValue(P, best_value))
00947 {
00948
00949 break;
00950 }
00951 }
00952 }
00953 higher_moves.swap(next_jobs);
00954 }
00955 const SearchMove *best_move = higher_moves.begin()->second;
00956 const int best_value = higher_moves.begin()->first;
00957 assert(limit >= 0);
00958 if (record)
00959 {
00960 base_t::recordLowerBound(P, record, limit, *best_move, best_value);
00961 assert((record->bestMove().getMove() == best_move->getMove())
00962 || (record->lowerLimit() == limit && record->lowerBound() == best_value)
00963 || (limit <= std::max(record->lowerLimit(), record->upperLimit())));
00964 }
00965
00966
00967 return best_move->getMove();
00968 }
00969
00975 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00976 template <osl::Player P>
00977 void osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00978 triageMovesSpeculatively(SearchMoveSorter<P>& higher_moves, int limit,
00979 int jump)
00980 {
00981 while (higher_moves.size() > 1)
00982 {
00983 SearchMoveSorter<P> next_jobs;
00984 typename SearchMoveSorter<P>::iterator p = higher_moves.begin();
00985 const int best_value = p->first;
00986 threshold = best_value + jump + eval::delta(P);
00987 if (base_t::isWinValue(P, threshold)
00988 || EvalTraits<P>::betterThan(threshold, upper_bound))
00989 return;
00990
00991 if (base_t::table->isVerbose())
00992 {
00993 std::cerr << "triage " << higher_moves.size() << " " << threshold << ": ";
00994 higher_moves.summary(4);
00995 }
00996 next_jobs.insert(*p);
00997 while (++p != higher_moves.end())
00998 {
00999 const SearchMove *target = p->second;
01000 SearchMove move_to_try = *target;
01001 if (higher_moves.size() <= 3)
01002 move_to_try.setLogProbAtMost(Probabilities::ReSearch);
01003
01004 int val;
01005 int max_value=threshold-eval::delta(P);
01006 if (testMove<P>(move_to_try, val, max_value, limit))
01007 {
01008 next_jobs.insert(std::make_pair(val, target));
01009 next_jobs.insert(++p, higher_moves.end());
01010 break;
01011 }
01012 }
01013 if (next_jobs.size() <= 1)
01014 return;
01015
01016 higher_moves.swap(next_jobs);
01017 }
01018 }
01019
01020 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
01021 template <osl::Player P>
01022 bool osl::search::MTDF<Eval,MoveGenerator,Table,Recorder,Probabilities>::
01023 testMove(const SearchMove& move, int& val, int& max_value, int limit)
01024 {
01025 assert(P == move.getMove().player());
01026 assert(P == memory_tester.state().getTurn());
01027 assert(EvalTraits<P>::betterThan(threshold,max_value));
01028 assert(threshold % 2);
01029 assert(! base_t::isWinValue(BLACK, threshold));
01030 assert(! base_t::isWinValue(WHITE, threshold));
01031 assert(move.getMove().isNormal());
01032
01033 if ((! memory_tester.timerAvailable()) && (! timer.isInvalid()) && (! timer.timeLeft()))
01034 throw misc::NoMoreTime();
01035 #ifdef OSL_SMP
01036 parallelSearch.checkStop();
01037 #endif
01038
01039
01040 SearchMove adjusted_move = move;
01041 const int history_logp = memory_tester.historyTable().logp(move.getMove());
01042 if (history_logp < move.getLogProb())
01043 adjusted_move = SearchMove(MoveLogProb(move.getMove(), history_logp),
01044 move.record);
01045 lower_bound = EvalTraits<P>::min(lower_bound,
01046 Eval::captureValue(newPtypeO(alt(P),ROOK)));
01047 upper_bound = EvalTraits<P>::max(upper_bound,
01048 Eval::captureValue(newPtypeO(P,ROOK)));
01049 assert(EvalTraits<P>::betterThan(threshold, lower_bound));
01050 assert(EvalTraits<P>::betterThan(upper_bound, threshold));
01051 memory_tester.setRootBounds(P, lower_bound, upper_bound);
01052 val = memory_tester.template nullWindowSearch<P>(threshold, adjusted_move,
01053 limit);
01054 move.record = adjusted_move.record;
01055
01056 if (EvalTraits<P>::betterThan(val,max_value))
01057 {
01058 max_value = val;
01059 if (EvalTraits<P>::betterThan(val,threshold))
01060 {
01061 lower_bound = EvalTraits<P>::max(val, lower_bound);
01062 memory_tester.setKillerMove(move.getMove());
01063 return true;
01064 }
01065
01066 }
01067 return false;
01068 }
01069
01070 #endif
01071
01072
01073
01074