00001 #ifndef _SEARCH_FRAMEWORK_TCC
00002 #define _SEARCH_FRAMEWORK_TCC
00003
00004 #include "osl/search/searchFramework.h"
00005 #include "osl/search/searchTable.h"
00006 #include "osl/search/simpleHashRecord.h"
00007 #include "osl/search/quiescenceSearch.h"
00008 #include "osl/search/shouldPromoteCut.h"
00009 #include "osl/search/searchMoveVector.h"
00010 #include "osl/search/dominanceCheck.h"
00011 #include "osl/search/simpleHashTable.h"
00012 #include "osl/search/quiescenceWindow.h"
00013 #include "osl/search/quiescenceWindow.tcc"
00014 #include "osl/checkmate/immediateCheckmate.h"
00015 #include "osl/move_classifier/pawnDropCheckmate.h"
00016 #include "osl/move_classifier/moveAdaptor.h"
00017 #include "osl/category/categoryListUtil.h"
00018 #include "osl/record/csa.h"
00019 #include "osl/container/moveStack.h"
00020 #include "osl/container/moveLogProbSet.h"
00021 #include "osl/container/moveLogProbVector.h"
00022 #include "osl/effect_util/effectUtil.h"
00023 #include "osl/effect_util/additionalEffect.h"
00024
00025 #ifdef OSL_SMP
00026 # include "osl/search/parallelSearch.h"
00027 #endif
00028 #include <iostream>
00029
00030 #define search_assert(x, m) assert((x) || abort(m))
00031
00032
00033
00034
00035
00036 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00037 osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00038 SearchFramework(const HashEffectState& s, checkmate_t& c,
00039 Table *t, Recorder& r)
00040 : base_t(r, t), SearchState(s, c), eval(s), node_count(0)
00041 {
00042 #ifdef OSL_SMP
00043 checkmate_holder.reset(new CheckmateSearcherHolder<checkmate_t>
00044 (checkmateSearcher()));
00045 #endif
00046 }
00047
00048 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00049 osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00050 SearchFramework(const SearchFramework& src)
00051 : base_t(src), SearchState(src), eval(src.eval), pass_count(src.pass_count),
00052 node_count(0)
00053 {
00054 #ifdef OSL_SMP
00055 checkmate_holder = src.checkmate_holder;
00056 #endif
00057 }
00058
00059 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00060 osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00061 ~SearchFramework()
00062 {
00063 }
00064
00065 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00066 bool osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00067 abort(Move best_move) const
00068 {
00069 return SearchState::abort(best_move);
00070 }
00071
00072 #ifdef OSL_SMP
00073 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00074 void osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00075 shareCheckmateHolder(boost::shared_ptr<holder_t>& share)
00076 {
00077 share = checkmate_holder;
00078 }
00079 #endif
00080
00081
00082
00083
00084
00085
00086 namespace osl
00087 {
00088 namespace search
00089 {
00090 namespace framework
00091 {
00097 template <Player P, class Policy>
00098 struct CategoryHelper
00099 {
00100 const Policy& policy;
00101 SearchMove *best_move;
00102 int *max_val;
00103 SearchMoveSet *tried;
00104 CategoryHelper(const Policy& h, SearchMove *b, int *m,
00105 SearchMoveSet *t=0)
00106 : policy(h), best_move(b), max_val(m), tried(t)
00107 {
00108 }
00109 template <bool isKingEscape>
00110 bool operator()(const char *category_name, MoveLogProbVector& moves)
00111 {
00112 assert(tried);
00113 return (*policy.searcher).template examineMoves<P,Policy,isKingEscape>
00114 (category_name, moves, policy, *best_move, *max_val, *tried);
00115 }
00116 };
00117 }
00118 }
00119 }
00120
00121 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00122 template <osl::Player P, class Helper>
00123 int osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00124 searchWithMove(const SearchMove& search_move, Helper& helper)
00125 {
00126 const Move move = search_move.getMove();
00127 const HashKey new_hash = currentHash().newHashWithMove(move);
00128 assert(P == move.player());
00129
00130 if (move.isPass())
00131 pass_count.inc(P);
00132
00133
00134 if (! pass_count.loopByBothPass())
00135 {
00136 const Sennichite next_sennichite
00137 = repetition_counter.isAlmostSennichite(new_hash);
00138 if (next_sennichite.isDraw())
00139 return base_t::drawValue();
00140 if (next_sennichite.hasWinner())
00141 return base_t::winByFoul(next_sennichite.winner());
00142 assert(next_sennichite.isNormal());
00143 }
00144
00145 if (! move.isPass())
00146 {
00147
00148 const DominanceCheck::Result has_dominance
00149 = DominanceCheck::detect(repetition_counter.history(), new_hash);
00150 if (has_dominance == DominanceCheck::LOSE)
00151 return base_t::winByLoop(alt(P));
00152 if (has_dominance == DominanceCheck::WIN)
00153 return base_t::winByLoop(P);
00154
00155 if (move.capturePtype() == PTYPE_EMPTY)
00156 {
00157 const int sacrifice_count = countSacrificeCheck2(curDepth());
00158 if (sacrifice_count == 2)
00159 {
00160
00161 const Position to = move.to();
00162 int offence = state().countEffect(P, to) + (move.isDrop() ? 1 : 0);
00163 const int deffense = state().hasEffectBy(alt(P), to);
00164 if (offence <= deffense)
00165 offence += AdditionalEffect::count2(state(), to, P);
00166 if (offence <= deffense)
00167 {
00168 return base_t::winByLoop(alt(P));
00169 }
00170 }
00171 }
00172 }
00173
00174
00175 int result;
00176 helper.setResultAddress(&result);
00177 base_t::recorder.addNodeCount();
00178
00179 const size_t previous_node_count = nodeCount();
00180 ++node_count;
00181
00182 const eval_t old_eval = eval;
00183 doUndoMoveOrPass<P,Helper>(new_hash, move, &search_move.record, helper, eval);
00184 eval = old_eval;
00185
00186 if (search_move.record)
00187 search_move.record->addNodeCount(nodeCount() - previous_node_count);
00188
00189 if (move.isPass())
00190 pass_count.dec(P);
00191
00192
00193 if ((! move.isPass())
00194 && move_classifier::MoveAdaptor<move_classifier::PawnDropCheckmate<P> >
00195 ::isMember(state(), move))
00196 return base_t::winByFoul(alt(P));
00197
00198 return result;
00199 }
00200
00201 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00202 template <osl::Player Turn, class Policy, bool isKingEscape>
00203 bool osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00204 examineMoves(const char *category_name, const MoveLogProbVector& moves,
00205 const Policy& policy,
00206 SearchMove& best_move, int& max_val, SearchMoveSet& triedMoves)
00207 {
00208 assert(Turn == state().getTurn());
00209 base_t::recorder.newCategory(category_name, curLimit());
00210 bool try_next = true;
00211 for (MoveLogProbVector::const_iterator p=moves.begin(); p!=moves.end(); p++)
00212 {
00213 SearchMove *next_move = 0;
00214 if ((! isKingEscape) && (! p->getMove().isPass())
00215 && ShouldPromoteCut::canIgnoreAndNotDrop<Turn>(p->getMove()))
00216 continue;
00217 if (! isKingEscape)
00218 {
00219 next_move = triedMoves.assignIfBetter(*p, ReSearchLimitMargin);
00220 }
00221 else
00222 {
00223
00224 next_move = triedMoves.assignIfBetter(*p, 0);
00225 }
00226 if (! next_move)
00227 continue;
00228 assert(next_move->getMove().isPass()
00229 || this->state().isValidMove(next_move->getMove()));
00230 if (try_next)
00231 {
00232 try_next = (! policy.searchWithMove(*next_move, max_val, best_move));
00233 assert(try_next || (! base_t::isWinValue(alt(Turn),max_val))
00234 || abort(best_move.getMove()));
00235
00236
00237 }
00238 }
00239 return try_next;
00240 }
00241
00242 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00243 template <osl::Player Turn, class Policy>
00244 inline
00245 bool osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00246 examineMoves(const char *category_name, const SearchMoveVector& moves,
00247 const Policy& policy, SearchMove& best_move, int& max_val)
00248 {
00249 assert(Turn == state().getTurn());
00250 base_t::recorder.newCategory(category_name, curLimit());
00251 #ifdef OSL_SMP
00252 if (moves.size() > 1 && parallelSearch.numCpus() > 1)
00253 {
00254 boost::shared_ptr<SearchMoveVector> shared(new SearchMoveVector(moves));
00255 return examineMovesPar<Turn,Policy>(shared,0,policy,best_move,max_val);
00256 }
00257 #endif
00258 for (SearchMoveVector::const_iterator p=moves.begin(); p!=moves.end(); p++)
00259 {
00260 if (! examineOneMove<Turn,Policy>(**p, policy, best_move, max_val))
00261 {
00262 assert(! base_t::isWinValue(alt(Turn),max_val));
00263 return false;
00264 }
00265 }
00266 return true;
00267 }
00268
00269 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00270 template <osl::Player Turn, class Policy>
00271 inline
00272 bool osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00273 examineOneMove(const SearchMove& move,
00274 const Policy& policy, SearchMove& best_move, int& max_val)
00275 {
00276 assert(move.getMove().isPass() || this->state().isValidMove(move.getMove()));
00277 return !policy.searchWithMove(move, max_val, best_move);
00278 }
00279
00280 #ifdef OSL_SMP
00281 namespace osl
00282 {
00283 namespace search
00284 {
00285 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities,typename Policy,typename Framework,osl::Player Turn>
00286 class ParHelper : public JobContent
00287 {
00288 Framework f;
00289 typedef typename Framework::checkmate_t checkmate_t;
00290 typedef CheckmateSearcherHolder<checkmate_t> holder_t;
00291 holder_t *checkmate_holder;
00292 boost::shared_ptr<SearchMoveVector> moves;
00293 int index;
00294 Policy policy;
00295 SearchMove best_move;
00296 int max_val;
00297 bool result;
00298 public:
00299 ParHelper(int priority,Framework const& f1, holder_t *holder,
00300 boost::shared_ptr<osl::search::SearchMoveVector> moves,
00301 int index,
00302 Policy policy1,int max_val)
00303 : JobContent(priority),f(f1),checkmate_holder(holder),
00304 moves(moves),index(index),policy(policy1),max_val(max_val),result(true) {
00305 policy.setSearcher(&f);
00306 }
00307 void setIndex(int newIndex) { index=newIndex;}
00308 void operator()(void) {
00309 checkmate_t *my_checkmate = checkmate_holder->clone(getWorker());
00310 f.setCheckmateSearcher(my_checkmate, getWorker());
00311 result=f.template examineMovesPar<Turn,Policy>(moves,index,policy,best_move,max_val);
00312 assert(result || best_move.validMove());
00313 setFinished(true);
00314 }
00315 bool getResult() const{
00316 assert(isFinished());
00317 return result;
00318 }
00319 const SearchMove getBestMove() const{
00320 assert(isFinished());
00321 return best_move;
00322 }
00323 int getMaxVal() const{
00324 return max_val;
00325 }
00326 size_t nodeCount() const { return f.nodeCount(); }
00327 };
00328 }
00329 }
00330
00331 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00332 template <osl::Player Turn, class Policy>
00333 bool osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00334 examineMovesPar(boost::shared_ptr<SearchMoveVector> moves, size_t index,
00335 const Policy& policy, SearchMove& best_move, int& max_val)
00336 {
00337 if (moves->size()-index==0)
00338 return true;
00339 if (moves->size()-index==1) {
00340 const bool try_next
00341 =examineOneMove<Turn,Policy>(*((*moves)[index]),policy,best_move,max_val);
00342 assert (try_next || best_move.validMove());
00343 return try_next;
00344 }
00345 typedef typename Policy::searcher_t framework_t;
00346 typedef ParHelper<Eval,MoveGenerator,Table,Recorder,Probabilities,Policy,framework_t,Turn> helper_t;
00347 const int priority=curDepth()*100+index;
00348
00349 boost::shared_ptr<helper_t>
00350 helper(new helper_t(priority,dynamic_cast<framework_t const&>(*this),checkmate_holder.get(), moves,index+1,policy,max_val));
00351 Job job(helper);
00352 Worker *worker=parallelSearch.getWorker();
00353 worker->checkStop();
00354 {
00355 Job current = worker->getCurrentJob();
00356 current.addChildJob(helper);
00357 }
00358 while (moves->size()-index>1) {
00359 testTimeOut();
00360 worker->push_back(job);
00361 bool ret=false;
00362 try {
00363 ret=examineOneMove<Turn,Policy>(*((*moves)[index]),policy,best_move,max_val);
00364 }
00365 catch (StopNow& e){
00366 if (!worker->pop_back_job()) {
00367 job.stopNow();
00368 }
00369 throw e;
00370 }
00371 if (!ret) {
00372 assert(best_move.validMove());
00373 if (!worker->pop_back_job()) {
00374 if (helper->isFinished()) {
00375 const int new_max_val=helper->getMaxVal();
00376 #ifndef NDEBUG
00377 const bool has_result=helper->getResult();
00378 #endif
00379 if (eval::betterThan(Turn, new_max_val, max_val)) {
00380 assert(!has_result);
00381 assert(helper->getBestMove().validMove());
00382 best_move= helper->getBestMove();
00383 max_val= new_max_val;
00384 }
00385 }
00386 node_count += helper->nodeCount();
00387 job.stopNow();
00388 }
00389 return false;
00390 }
00391 index++;
00392 if (worker->pop_back_job()) {
00393 parallelSearch.checkStop();
00394 helper->setIndex(index+1);
00395 helper->setFinished(false);
00396
00397 helper->setPriority(curDepth()*100+index);
00398 }
00399 else{
00400 #ifdef ONE_THREAD_PER_PROC
00401 {
00402 DecActiveHelper dec_lock(parallelSearch);
00403 while (!helper->isFinished()) {
00404 testTimeOut();
00405 Job another_job;
00406 try
00407 {
00408 another_job=parallelSearch.getJobNonBlock(worker);
00409 }
00410 catch (StopNow&)
00411 {
00412 helper->stopNow();
00413 throw;
00414 }
00415 if (! another_job.isNull()) {
00416 try{
00417 SetCurrentJobLock lk(*worker,another_job);
00418 IncActiveHelper inc_lock(parallelSearch);
00419 another_job();
00420 }
00421 catch (StopNow& e) {
00422 std::cerr << "catch StopNow "
00423 << &another_job << "\n";
00424 }
00425 }
00426 else {
00427 boost::thread::yield();
00428 }
00429 }
00430 }
00431 #else
00432 helper->waitResult();
00433 #endif
00434 node_count += helper->nodeCount();
00435 assert(helper->isFinished());
00436 const int new_max_val=helper->getMaxVal();
00437 const bool has_result=helper->getResult();
00438 if (EvalTraits<Turn>::betterThan(new_max_val, max_val) || !has_result) {
00439 best_move= helper->getBestMove();
00440 assert(best_move.validMove());
00441 max_val= new_max_val;
00442 }
00443 return has_result;
00444 }
00445 }
00446 bool ret=examineOneMove<Turn,Policy>(*((*moves)[index]),policy,best_move,max_val);
00447 assert(ret || best_move.validMove());
00448 return ret;
00449 }
00450 #endif
00451
00452 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00453 template <osl::Player P, class Policy>
00454 int osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00455 searchAllMoves(SimpleHashRecord *& record_memorize,
00456 const Policy& policy, SearchMove& best_move)
00457 {
00458 #ifndef NDEBUG
00459 checkPointSearchAllMoves();
00460 #endif
00461 assert(P == state().getTurn());
00462 search_assert(policy.window().isConsistent(P), lastMove());
00463 #ifndef NDEBUG
00464 const int MaxLimit = 4096;
00465 #endif
00466 assert(curLimit() < MaxLimit);
00467 assert(curLimit() >= 0);
00468
00469 if (pass_count.loopByBothPass())
00470 return quiescenceValue<P,Policy>(policy);
00471
00472 int max_val=base_t::minusInfty(P);
00473 const Player Opponent = PlayerTraits<P>::opponent;
00474
00475 if (EffectUtil::isKingInCheck(Opponent, state())) {
00476 max_val = base_t::minusInfty(alt(P));
00477 return max_val;
00478 }
00479
00480 boost::scoped_ptr<SimpleHashRecord> record_if_unavailable;
00481
00482 SimpleHashRecord *record = record_memorize;
00483 if (! record)
00484 record = record_memorize
00485 = base_t::table->allocate(currentHash(), curLimit());
00486 if (! record)
00487 {
00488 record_if_unavailable.reset(new SimpleHashRecord());
00489 record = record_if_unavailable.get();
00490 }
00491 assert(hasLastRecord(1));
00492 const SimpleHashRecord *parent = lastRecord(1);
00493 record->is_king_in_check = EffectUtil::isKingInCheck(P, state());
00494
00495 if (record_memorize)
00496 {
00497 const TableHit hit = policy.isOutOfWindow(P, *record, curLimit(),
00498 max_val, base_t::recorder);
00499 if (hit == LOWER_HIT)
00500 return max_val;
00501 Move checkmate_move=Move::INVALID();
00502 if ((!record->is_king_in_check)
00503 && record->qrecord.checkmateNodesLeft(1)
00504 && (checkmate::ImmediateCheckmate::hasCheckmateMove<P>
00505 (state(), checkmate_move)))
00506 {
00507 max_val= base_t::winByCheckmate(P);
00508 base_t::recordWinByCheckmate(P, record, checkmate_move);
00509 return max_val;
00510 }
00511 #ifndef DONT_USE_CHECKMATE
00512 assert(record);
00513
00514 int additional_limit = 0;
00515 if (parent && parent->threatmate().maybeThreatmate(alt(P)))
00516 {
00517 additional_limit = std::max(100, parent->qrecord.threatmateNodes()/8);
00518 additional_limit = record->qrecord.checkmateNodesLeft(additional_limit);
00519 }
00520 base_t::recorder.gotoCheckmateSearch(state(), additional_limit);
00521 const bool win = isWinningState<P>(additional_limit, checkmate_move,
00522 record->qrecord.attack_oracle);
00523 base_t::recorder.backFromCheckmateSearch();
00524 if (win)
00525 {
00526 assert(checkmate_move.isValid());
00527 max_val= base_t::winByCheckmate(P);
00528 base_t::recordWinByCheckmate(P, record, checkmate_move);
00529 setKillerMove(checkmate_move);
00530 return max_val;
00531 }
00532 #endif
00533 if (hit == UPPER_HIT)
00534 return max_val;
00535 assert(hit == NO_HIT);
00536 assert(max_val == base_t::minusInfty(P));
00537 }
00538 #ifdef OSL_SMP
00539 parallelSearch.checkStop();
00540 #endif
00541
00542 search_assert(policy.window().isConsistent(P), lastMove());
00543
00544 #ifndef DONT_USE_CHECKMATE
00545
00546 if ((! record->is_king_in_check)
00547 && (! (record && record->threatmate().isThreatmate(P)))
00548 && tryThreatmate())
00549 {
00550 int threatmate_limit = 4500-curDepth()*1000;
00551 threatmate_limit = std::max(threatmate_limit, 100);
00552 if (record_memorize)
00553 {
00554 threatmate_limit = record->qrecord.threatmateNodesLeft(threatmate_limit);
00555 }
00556 else
00557 {
00558 threatmate_limit /= 2;
00559 }
00560 Move threatmate_move;
00561 base_t::recorder.gotoCheckmateSearch(state(), threatmate_limit);
00562 const bool threatmate
00563 = isThreatmateState<P>(threatmate_limit, threatmate_move,
00564 record->qrecord.threatmate_oracle);
00565 base_t::recorder.backFromCheckmateSearch();
00566 if (threatmate)
00567 {
00568 record->threatmate().setThreatmate(P, threatmate_move);
00569 #ifndef NDEBUG
00570 if (base_t::table->isVerbose() && curDepth() < 3)
00571 {
00572 std::cerr << "threatmate by " << record::csa::show(threatmate_move)
00573 << " ";
00574 history().dump(curDepth());
00575 }
00576 #endif
00577 }
00578 }
00579 #endif
00580
00582 int checkmate_limit = 1;
00583 best_move = SearchMove();
00584
00585 record->threatmate().update(P, (parent ? &(parent->threatmate()) : 0),
00586 EffectUtil::isKingInCheck(P, state()));
00587
00588
00589 if (record_memorize) {
00590 const SearchMove *best_move_in_table = 0;
00591 const SearchMove best_move_in_table_content = record->bestMove();
00592 if (best_move_in_table_content.validMove()) {
00593 #ifdef OSL_SMP
00594 best_move_in_table
00595 = record->moves().find(best_move_in_table_content.getMove());
00596 if (! best_move_in_table)
00597 {
00598 const TableHit hit = policy.isOutOfWindow(P, *record, curLimit(),
00599 max_val, base_t::recorder);
00600 assert(hit == LOWER_HIT);
00601 if (hit == LOWER_HIT)
00602 return max_val;
00603 }
00604 #else
00605 best_move_in_table = &best_move_in_table_content;
00606 assert(best_move_in_table);
00607 #endif
00608 }
00609 if (best_move_in_table &&
00610 base_t::validTableMove(state(), best_move_in_table->moveLogProb(),
00611 curLimit())) {
00612 base_t::recorder.newCategory("table", curLimit());
00613 #ifdef OSL_SMP
00614 const bool try_next = examineOneMove<P,Policy>
00615 (*best_move_in_table, policy, best_move, max_val);
00616 #else
00617 MoveLogProb ml=best_move_in_table->moveLogProb();
00618 assert(ml.getLogProb() >= Probabilities_t::TableMove);
00619 if (Policy::isBestMoveExtension)
00620 ml.setLogProbAtMost(Probabilities_t::ReSearch);
00621 SearchMove trying_move(ml, best_move_in_table->record);
00622 const bool try_next = examineOneMove<P,Policy>
00623 (trying_move, policy, best_move, max_val);
00624 #endif
00625 if (! try_next)
00626 {
00627 assert(best_move.validMove());
00628 assert(! base_t::isWinValue(alt(P),max_val));
00629 goto register_table;
00630 }
00631 }
00632 }
00633
00634 if (curDepth() <= 1)
00635 {
00636 quiescenceValue<P>(base_t::winThreshold(alt(P)), base_t::winThreshold(P));
00637 }
00638 else
00639 {
00640 #if defined(GUIDE_BY_QSEARCH_FULL)
00641
00642 quiescenceValue<P>(base_t::winThreshold(alt(P)), base_t::winThreshold(P), 4);
00643 #elif defined(GUIDE_BY_QSEARCH_LIMITED)
00644
00645 const int pawn_value2 = Eval::captureValue(newPtypeO(alt(P),PAWN));
00646 const int current = policy.window().beta();
00647 int alpha = policy.window().alpha();
00648 int beta = policy.window().beta();
00649 if (EvalTraits<P>::notLessThan(alpha, beta))
00650 {
00651 const std::pair<int,int> alpha_beta
00652 = NullWindowToQWindow::halfPawn(current, pawn_value2*4);
00653 alpha = eval::max(P, FixedEval::winThreshold(alt(P)),
00654 alpha_beta.first);
00655 beta = eval::min(P, FixedEval::winThreshold(P),
00656 alpha_beta.second);
00657 }
00658 quiescenceValue<P>(alpha, beta);
00659 #endif
00660 }
00661
00662 if ((! record->is_king_in_check)
00663 && ! record->threatmate().maybeThreatmate(P)
00664 && (curLimit() >= Probabilities_t::KillerMove))
00665 {
00666
00667 MoveLogProbVector moves;
00668 MoveVector killer_moves;
00669 getKillerMoves(killer_moves);
00670 for (MoveVector::const_iterator p=killer_moves.begin();
00671 p!=killer_moves.end(); ++p)
00672 {
00673 assert(p->player() == state().getTurn());
00674 assert(p->player() == P);
00675 moves.push_back(MoveLogProb(*p, Probabilities_t::KillerMove));
00676 }
00677
00678 if (record->qrecord.bestMove().isNormal())
00679 {
00680 assert(this->state().isValidMove(record->qrecord.bestMove()));
00681 const MoveLogProb quiescence_move(record->qrecord.bestMove(),
00682 Probabilities_t::KillerMove);
00683 moves.push_back(quiescence_move);
00684 }
00685 if (! moves.empty())
00686 {
00687 const bool try_next
00688 = examineMoves<P,Policy,false>
00689 ("killer move", moves, policy, best_move, max_val,record->moves());
00690 if (! try_next)
00691 {
00692 assert(best_move.validMove());
00693 assert(! base_t::isWinValue(alt(P),max_val));
00694 goto register_table;
00695 }
00696 }
00697 }
00698
00699 testTimeOut();
00700
00701 #ifndef DONT_USE_CHECKMATE
00702 if (root_limit >= 500)
00703 {
00704 int depth = curDepth();
00705 if (record_memorize && (depth <= 1))
00706 checkmate_limit = checkmate::limitToCheckCount(3500);
00707 else if (record_memorize && (depth == 2))
00708 checkmate_limit = 1000;
00709 else if (record_memorize && (depth == 3))
00710 checkmate_limit = 200;
00711 else if (((root_limit - curLimit()) <= 600) || (depth <= 5))
00712 {
00713 assert(static_cast<unsigned int>(curLimit()) < 4096);
00714 checkmate_limit = checkmate::limitToCheckCount(curLimit());
00715 }
00716 if (record->threatmate().mayHaveCheckmate(alt(P))
00717 || (parent && parent->threatmate().maybeThreatmate(alt(P))))
00718 checkmate_limit += std::max(100, checkmate_limit);
00719 if (root_limit < 600)
00720 checkmate_limit /= 2;
00721 }
00722 if (record_memorize)
00723 {
00724
00725 checkmate_limit = record->qrecord.checkmateNodesLeft(checkmate_limit);
00726 if (checkmate_limit <= 0)
00727 goto checkmate_done;
00728 }
00729 else
00730 {
00731 checkmate_limit /= 2;
00732 }
00733
00734
00735 {
00736 Move checkmate_move=Move::INVALID();
00737 base_t::recorder.gotoCheckmateSearch(state(), checkmate_limit);
00738 const bool win = isWinningState<P>
00739 (checkmate_limit, checkmate_move, record->qrecord.attack_oracle);
00740 base_t::recorder.backFromCheckmateSearch();
00741 if (win)
00742 {
00743 assert(checkmate_move.isValid());
00744 max_val= base_t::winByCheckmate(P);
00745 base_t::recordWinByCheckmate(P, record, checkmate_move);
00746 setKillerMove(checkmate_move);
00747 return max_val;
00748 }
00749 }
00750 checkmate_done:
00751 #endif
00752 search_assert(policy.window().isConsistent(P), lastMove());
00753 if (curLimit() < 200)
00754 goto move_generation_failure;
00755
00756
00757 if (record_memorize && (! record->moves().hasOnlyPass()))
00758 {
00759 SearchMoveVector moves;
00760 assert(record->moves().isValidAll());
00761 {
00762 SearchMoveSet::range r(record->moves());
00763 for (SearchMoveSet::const_iterator p=r.first; p!=r.last; ++p)
00764 {
00765 if (p->getLogProb() <= curLimit())
00766 moves.push_back(&*p);
00767 }
00768 }
00769
00770
00771 const int default_value
00772 = ((policy.window().alpha()+policy.window().beta())/2
00773 + Eval::captureValue(newPtypeO(P,PAWN)));
00774 moves.sortByValue<P>(default_value);
00775 const bool try_next
00776 = examineMoves<P,Policy>("recorded", moves, policy, best_move, max_val);
00777 if (! try_next)
00778 {
00779 assert(best_move.validMove());
00780 assert((! base_t::isWinValue(alt(P),max_val)));
00781 goto register_table;
00782 }
00783 }
00784 search_assert(policy.window().isConsistent(P), lastMove());
00785
00786 {
00787 const category::CategoryEnv env(&state(), curLimit(), &history(),
00788 eval.progress32(),
00789 record, curDepth(), &historyTable());
00790 bool cut_occurred;
00791 category::CategoryFlags& category_cache =
00792 record->prepareGenerate(curLimit(), ReSearchLimitMargin);
00793 cut_occurred = CategoryListUtil::forEachCategory
00794 (MoveGenerator(), env,
00795 framework::CategoryHelper<P,Policy>
00796 (policy, &best_move, &max_val, &record->moves()), category_cache);
00797 if (! best_move.validMove())
00798 {
00799 assert(! cut_occurred);
00800 search_assert(policy.window().isConsistent(P), lastMove());
00801 goto move_generation_failure;
00802 }
00803 }
00804 if (record->moves().hasOnlyPass())
00805 {
00806
00807
00808 goto move_generation_failure;
00809 }
00810 register_table:
00811 assert(best_move.validMove());
00812 assert(eval::isConsistentValue(max_val));
00813
00814 if (record && record->threatmate().maybeThreatmate(P))
00815 {
00816
00817 #ifndef DONT_USE_CHECKMATE
00818 if (EvalTraits<P>::betterThan(eval.captureValue(newPtypeO(P,KING)), max_val))
00819
00820 checkmate_limit = record->sumOfNodeCountOfChildren() / 2;
00821 else
00822 checkmate_limit = record->sumOfNodeCountOfChildren() / 8;
00823 {
00824 Move checkmate_move=Move::INVALID();
00825 checkmate_limit += 100;
00826 if (record_memorize)
00827 checkmate_limit = record->qrecord.checkmateNodesLeft(checkmate_limit*2);
00828 base_t::recorder.gotoCheckmateSearch(state(), checkmate_limit);
00829 const bool win = isWinningState<P>
00830 (checkmate_limit, checkmate_move, record->qrecord.attack_oracle);
00831 base_t::recorder.backFromCheckmateSearch();
00832 if (win)
00833 {
00834 assert(checkmate_move.isValid());
00835 max_val= base_t::winByCheckmate(P);
00836 base_t::recordWinByCheckmate(P, record, checkmate_move);
00837 setKillerMove(checkmate_move);
00838 return max_val;
00839 }
00840 }
00841 }
00842 #endif
00843 if (base_t::isWinValue(alt(P),max_val))
00844 {
00845
00846
00847 max_val = brinkmatePenalty(P, curLimit()) + eval.value();
00848 if (record_memorize)
00849 {
00850
00851 record_memorize->setLowerBound(P, curLimit(), best_move, max_val);
00852 record_memorize->setUpperBound(P, curLimit(), best_move, max_val);
00853 }
00854 return max_val;
00855 }
00856 else
00857 {
00858 setKillerMove(best_move.getMove());
00859 }
00860 if (record_memorize)
00861 policy.recordToTable(P, record_memorize, curLimit(), best_move, max_val);
00862 return max_val;
00863 move_generation_failure:
00864
00865
00866 max_val = quiescenceValue<P,Policy>(policy);
00867 if (record_memorize)
00868 {
00869
00870 policy.recordToTable(P, record_memorize, curLimit(), SearchMove(), max_val);
00871 }
00872 assert(eval::isConsistentValue(max_val));
00873 return max_val;
00874 }
00875
00876 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00877 template <osl::Player P>
00878 int osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00879 quiescenceValue(int alpha, int beta, int depth)
00880 {
00881 testTimeOut();
00882 typedef QuiescenceSearch<eval_t> qsearcher_t;
00883 qsearcher_t qs(static_cast<SearchStateCore&>(*this), *base_t::table);
00884 Move last_move = lastMove();
00885 if (last_move.isInvalid())
00886 last_move = Move::PASS(alt(P));
00887 int result;
00888 #ifdef DONT_USE_QSEARCH_PROBCUT
00889 const bool probcut_suitable = false;
00890 #else
00891 const Position my_king = state().getKingPosition(P);
00892 const bool probcut_suitable
00893 = (! last_move.isNormal())
00894 || (! Neighboring8Direct::hasEffect(state(), last_move.ptypeO(),
00895 last_move.to(), my_king));
00896 #endif
00897 if (probcut_suitable)
00898 {
00899 if (depth >= 8)
00900 result = qs.template searchProbCut<P>(alpha, beta, eval, last_move);
00901 else
00902 result = qs.template search<P>(alpha, beta, eval, last_move, depth);
00903 }
00904 else
00905 {
00906 result = qs.template search<P>(alpha, beta, eval, last_move, depth);
00907 }
00908 node_count += qs.nodeCount();
00909 base_t::recorder.addQuiescenceCount(qs.nodeCount());
00910 return result;
00911 }
00912
00913 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00914 template <osl::Player P, class Policy>
00915 inline
00916 int osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00917 quiescenceValue(const Policy& policy)
00918 {
00919 typedef typename Policy::window_t window_t;
00920 const std::pair<int,int> alpha_beta
00921 = (policy.window().isConsistent(P)
00922 ? QuiescenceWindow<window_t>::make(P, policy.window(), eval)
00923 : QuiescenceWindow<NullWindow>::make(P, NullWindow(policy.window().beta()), eval));
00924 return quiescenceValue<P>(alpha_beta.first, alpha_beta.second);
00925 }
00926
00927 namespace osl
00928 {
00929 namespace search
00930 {
00931 template <Player P, class Searcher>
00932 struct NextQuiescenceFramework
00933 {
00934 Searcher *searcher;
00935 const int alpha, beta;
00936 int result;
00937 void operator()(Position)
00938 {
00939 result =
00940 searcher->template quiescenceValue<P>(alpha, beta);
00941 }
00942 };
00943 }
00944 }
00945
00946 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00947 bool osl::search::SearchFramework<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00948 isReasonableMove(Move move, int pawn_sacrifice)
00949 {
00950 const Player turn = state().getTurn();
00951 assert(move.player() == turn);
00952 const int alpha = base_t::winThreshold(alt(turn));
00953 const int beta = base_t::winThreshold(turn);
00954 const int current = (turn == BLACK)
00955 ? quiescenceValue<BLACK>(alpha, beta)
00956 : quiescenceValue<WHITE>(alpha, beta);
00957 const int pawn_value = Eval::captureValue(newPtypeO(turn, PAWN))*pawn_sacrifice;
00958
00959 const HashKey new_hash = currentHash().newHashWithMove(move);
00960 int result;
00961 SimpleHashRecord *record = 0;
00962 Eval new_eval = eval;
00963 if (turn == BLACK)
00964 {
00965 NextQuiescenceFramework<WHITE,SearchFramework> helper = {this, beta, alpha, 0};
00966 doUndoMoveOrPass<BLACK>(new_hash, move, &record, helper, new_eval);
00967 result = helper.result;
00968 }
00969 else
00970 {
00971 NextQuiescenceFramework<BLACK,SearchFramework> helper = {this, beta, alpha, 0};
00972 doUndoMoveOrPass<WHITE>(new_hash, move, &record, helper, new_eval);
00973 result = helper.result;
00974 }
00975 return eval::betterThan(turn, result, current + pawn_value);
00976 }
00977
00978
00979
00980 #endif
00981
00982
00983
00984