00001
00002
00003 #include "osl/search/alphaBeta2.h"
00004 #ifdef OSL_SMP
00005 # include "osl/search/alphaBeta2Parallel.h"
00006 #endif
00007 #include "osl/search/simpleHashRecord.h"
00008 #include "osl/search/searchMoveVector.h"
00009 #include "osl/search/simpleHashTable.h"
00010 #include "osl/search/dominanceCheck.h"
00011 #include "osl/search/moveGenerator.h"
00012 #include "osl/search/realizationProbability.h"
00013 #include "osl/search/quiescenceSearch2.h"
00014 #include "osl/search/realizationProbability.h"
00015 #include "osl/checkmate/immediateCheckmate.h"
00016 #include "osl/record/csa.h"
00017 #include "osl/move_classifier/pawnDropCheckmate.h"
00018 #include "osl/move_classifier/check_.h"
00019 #include "osl/move_classifier/moveAdaptor.h"
00020 #include "osl/move_generator/legalMoves.h"
00021 #include "osl/effect_util/additionalEffect.h"
00022 #include "osl/misc/nonBlockDelete.h"
00023 #include "osl/enter_king/enterKing.h"
00024 #include <stdexcept>
00025 #include <iostream>
00026 #include <iomanip>
00027
00028 #define search_assert(x, m) assert((x) || SearchState2::abort(m))
00029
00030 typedef osl::search::RealizationProbability Probabilities_t;
00031
00032 #ifdef CHECKMATE_COUNT
00033 static size_t root_checkmate = 0, checkmate_before = 0, checkmate_after = 0,
00034 count_threatmate = 0, quiesce_checkmate=0;
00035 #endif
00036
00037
00038
00039
00040
00041
00042
00043 osl::CArray<int, osl::search::AlphaBeta2Tree::MaxDepth> osl::search::AlphaBeta2Tree::depth_node_count;
00044
00045 osl::search::AlphaBeta2Tree::
00046 AlphaBeta2Tree(const HashEffectState& s, checkmate_t& c,
00047 SimpleHashTable *t, CountRecorder& r)
00048 : SearchBase<eval::ProgressEval,SimpleHashTable,CountRecorder,RealizationProbability>(r, t),
00049 SearchState2(s, c), AlphaBeta2Common(s), node_count(0),
00050 stop_by_alarm(Alarm::UNAVAILABLE), has_stop_alarm(false)
00051 {
00052 #ifdef OSL_SMP
00053 try
00054 {
00055 shared.reset(new AlphaBeta2Parallel(this));
00056 }
00057 catch (std::bad_alloc&)
00058 {
00059 std::cerr << "panic. allocation of AlphaBeta2Parallel failed\n";
00060 }
00061 #endif
00062 }
00063
00064 osl::search::AlphaBeta2Tree::
00065 AlphaBeta2Tree(const AlphaBeta2Tree& src, AlphaBeta2Parallel *)
00066 : SearchBase<eval::ProgressEval,SimpleHashTable,CountRecorder,RealizationProbability>(src),
00067 SearchState2(src), HasTimer(src), AlphaBeta2Common(src),
00068 node_count(0), shared(src.shared), stop_by_alarm(Alarm::UNAVAILABLE), has_stop_alarm(false)
00069 {
00070 }
00071
00072 osl::search::AlphaBeta2Tree::
00073 ~AlphaBeta2Tree()
00074 {
00075 for (size_t i=0; i<generators.size(); ++i)
00076 dealloc(generators[i]);
00077 #ifdef OSL_SMP
00078 if (shared && shared.use_count() == 1)
00079 NonBlockDelete::reset(shared);
00080 #endif
00081 }
00082
00083 osl::search::MoveGenerator *
00084 osl::search::AlphaBeta2Tree::alloc()
00085 {
00086 try
00087 {
00088 return new MoveGenerator;
00089 }
00090 catch (std::bad_alloc&)
00091 {
00092 std::cerr << "panic. allocation of MoveGenerator failed\n";
00093 throw TableFull();
00094 }
00095 return 0;
00096 }
00097
00098 void osl::search::AlphaBeta2Tree::dealloc(MoveGenerator *p)
00099 {
00100 delete p;
00101 }
00102
00103 osl::search::MoveGenerator& osl::search::AlphaBeta2Tree::makeGenerator()
00104 {
00105 const size_t cur_depth = curDepth();
00106 while (generators.size() <= cur_depth)
00107 generators.push_back(0);
00108 if (generators[cur_depth] == 0)
00109 generators[cur_depth] = alloc();
00110 return *generators[cur_depth];
00111 }
00112
00113 volatile int& osl::search::
00114 AlphaBeta2Tree::stopByAlarm()
00115 {
00116 #ifdef OSL_SMP
00117 if (shared)
00118 return shared->stop_by_alarm;
00119 #endif
00120 return stop_by_alarm;
00121 }
00122
00123 const volatile int& osl::search::
00124 AlphaBeta2Tree::stopByAlarm() const
00125 {
00126 #ifdef OSL_SMP
00127 if (shared)
00128 return shared->stop_by_alarm;
00129 #endif
00130 return stop_by_alarm;
00131 }
00132
00133 void osl::search::
00134 AlphaBeta2Tree::setTimeOut(int seconds)
00135 {
00136 if (seconds <= 0)
00137 {
00138 if (seconds < 0)
00139 std::cerr << "warning: setTimeOut negative " << seconds << "\n";
00140 seconds = 1;
00141 }
00142 has_stop_alarm = Alarm::set(seconds, AlarmSwitch(&stopByAlarm()));
00143 if (! has_stop_alarm)
00144 {
00145 std::cerr << "warning: search without alarm\n";
00146 }
00147 }
00148 void osl::search::
00149 AlphaBeta2Tree::resetTimeOut()
00150 {
00151 if (has_stop_alarm)
00152 Alarm::reset(AlarmSwitch(&stopByAlarm()));
00153 }
00154
00155 void osl::search::
00156 AlphaBeta2Tree::throwStop()
00157 {
00158 if (stopByAlarm() == Alarm::TIMEOUT) {
00159 #ifdef DEBUG
00160 const time_t now = time(0);
00161 char ctime_buf[64];
00162 std::cerr << "throwTimeOut " << ctime_r(&now, ctime_buf);
00163 #endif
00164 resetTimeOut();
00165 throw misc::NoMoreTime();
00166 }
00167 assert(stop);
00168 throw BetaCut();
00169 }
00170
00171
00172
00173
00174
00175 template <osl::Player P>
00176 int osl::search::AlphaBeta2Tree::
00177 alphaBetaSearchAfterMove(const MoveLogProb& moved, Window w,
00178 bool in_pv)
00179 {
00180 assert(w.alpha(P) % 2);
00181 assert(w.beta(P) % 2);
00182 assert(alt(P) == state().getTurn());
00183 assert(P == moved.getMove().player());
00184 assert(eval::notLessThan(P, w.beta(P), w.alpha(P)));
00185
00186
00187 if (EffectUtil::isKingInCheck(P, state())) {
00188 return this->minusInfty(P);
00189 }
00190 eval.update(state(), moved.getMove());
00191 const Player Turn = PlayerTraits<P>::opponent;
00192 const size_t previous_node_count = nodeCount();
00193
00194 pv[curDepth()].clear();
00195
00196 int result;
00197
00198
00199 boost::scoped_ptr<SimpleHashRecord> record_if_unavailable;
00200 SimpleHashRecord *record
00201 = table->allocate(currentHash(), curLimit());
00202 const bool has_table_record = record;
00203 if (! record) {
00204 record_if_unavailable.reset(new SimpleHashRecord());
00205 record = record_if_unavailable.get();
00206 }
00207 setCurrentRecord(record);
00208 record->is_king_in_check = EffectUtil::isKingInCheck(Turn, state());
00209 #if 0
00210
00211 if (pass_count.loopByBothPass()) {
00212 return quiesce<Turn>(w);
00213 }
00214 #endif
00215 ++node_count;
00216 int consumption = moved.getLogProb();
00217
00218
00219 if (in_pv
00220 && (! record->bestMove().getMove().isNormal())) {
00221 assert(node_type[curDepth()] == PvNode);
00222 for (int limit = curLimit() - 200+1; limit > consumption+200;
00223 limit -= 200) {
00224 searchAllMoves<Turn>(moved.getMove(), limit,
00225 record, w);
00226 if (! record->bestMove().validMove()) {
00227 Move quiesce_best = record->qrecord.bestMove();
00228 if (quiesce_best.isNormal())
00229 record->setBestMove(SearchMove(MoveLogProb(quiesce_best, 100)));
00230 }
00231 }
00232 }
00233 if (! in_pv) {
00234
00235 if (node_type[curDepth()] == PvNode)
00236 node_type[curDepth()] = AllNode;
00237 result = searchAllMoves<Turn>
00238 (moved.getMove(), consumption, record,
00239 Window(w.alpha(P), w.alpha(P)));
00240 } else {
00241
00242 assert(node_type[curDepth()] == PvNode);
00243 result = searchAllMoves<Turn>(moved.getMove(), consumption,
00244 record, w);
00245 }
00246 bool extended = false;
00247
00248 if (eval::betterThan(P, result, w.alpha(P))) {
00249 const SimpleHashRecord *parent = lastRecord(1);
00250 int consumption_here = consumption+1;
00251 if (! w.null() && (! in_pv || consumption > 100))
00252 consumption_here = std::min(consumption, 100);
00253 else if (consumption > 100
00254 && (record->threatmate().status(P).status() == ThreatmateState::CHECK_AFTER_THREATMATE
00255 || record->threatmate().mayHaveCheckmate(P)))
00256 consumption_here = 100;
00257 else if (consumption > 150
00258 && ((parent && parent->is_king_in_check)
00259 || state().hasEffectBy(P, state().getKingPosition(alt(P)))))
00260 consumption_here = 150;
00261 if (consumption_here <= consumption) {
00262 node_type[curDepth()] = PvNode;
00263 extended = true;
00264 ext_limit.add(consumption - consumption_here);
00265 result = searchAllMoves<Turn>(moved.getMove(), consumption_here, record, w);
00266 }
00267 }
00268 ext.add(extended);
00269
00270 if (has_table_record)
00271 record->addNodeCount(nodeCount() - previous_node_count);
00272 return result;
00273 }
00274
00275 template <osl::Player Turn>
00276 int osl::search::AlphaBeta2Tree::
00277 searchAllMoves(Move m, int limit_consumption, SimpleHashRecord *record,
00278 Window w)
00279 {
00280 if (! w.null())
00281 assert(node_type[curDepth()] == PvNode);
00282 const Player P = PlayerTraits<Turn>::opponent;
00283 recorder.tryMove(MoveLogProb(m, limit_consumption),
00284 w.alpha(P), curLimit());
00285 subLimit(limit_consumption);
00286
00287 const int result = searchAllMoves<Turn>(record, w);
00288
00289 addLimit(limit_consumption);
00290 recorder.recordValue(MoveLogProb(m, limit_consumption),
00291 result,eval::betterThan(P, result, w.alpha(P)),
00292 curLimit());
00293 return result;
00294 }
00295
00296 template <osl::Player P>
00297 void osl::search::AlphaBeta2Tree::
00298 testThreatmate(SimpleHashRecord *record, bool in_pv)
00299 {
00300 if ((! record->is_king_in_check)
00301 && (! (record && record->threatmate().isThreatmate(P)))
00302 && tryThreatmate())
00303 {
00304 int threatmate_limit = 0;
00305
00306 threatmate_limit = 4500-curDepth()*1000;
00307 threatmate_limit = std::max(threatmate_limit, 100);
00308 if (! in_pv)
00309 threatmate_limit /= 2;
00310 if (root_limit < 800)
00311 threatmate_limit /= 2;
00312 #ifdef EXPERIMENTAL_QUIESCE
00313 if (curLimit() <= 400)
00314 threatmate_limit = 1;
00315 else if (curLimit() <= 500)
00316 threatmate_limit /= 16;
00317 else if (curLimit() <= 600)
00318 threatmate_limit /= 4;
00319 #endif
00320
00321 if (curLimit() >= table->minimumRecordLimit())
00322 {
00323 threatmate_limit = record->qrecord.threatmateNodesLeft(threatmate_limit);
00324 }
00325 else
00326 {
00327 threatmate_limit /= 2;
00328 }
00329
00330 Move threatmate_move;
00331 recorder.gotoCheckmateSearch(state(), threatmate_limit);
00332 #ifdef CHECKMATE_COUNT
00333 size_t count = checkmateSearcher().totalNodeCount();
00334 #endif
00335 bool threatmate
00336 = isThreatmateState<P>(threatmate_limit, threatmate_move,
00337 record->qrecord.threatmate_oracle);
00338 #ifdef CHECKMATE_COUNT
00339 count_threatmate += checkmateSearcher().totalNodeCount() - count;
00340 #endif
00341 recorder.backFromCheckmateSearch();
00342 if (!threatmate && threatmate_limit == 0
00343 && record->qrecord.threatmateNodesLeft(2)) {
00344 threatmate = isThreatmateStateShort<P>(2, threatmate_move);
00345 }
00346 if (threatmate)
00347 {
00348 record->threatmate().setThreatmate(P, threatmate_move);
00349 }
00350 }
00351 }
00352
00353 template <osl::Player P>
00354 bool osl::search::AlphaBeta2Tree::
00355 tryCheckmate(SimpleHashRecord *record, bool in_pv, Move& checkmate_move)
00356 {
00357 int checkmate_limit = 1;
00358 if (! in_pv) {
00359 const SimpleHashRecord *parent = lastRecord(1);
00360 if (! (record->threatmate().mayHaveCheckmate(alt(P))
00361 || (parent && parent->threatmate().maybeThreatmate(alt(P)))))
00362 return false;
00363
00364 }
00365 if (in_pv && root_limit >= 500) {
00366 int depth = curDepth();
00367 if (root_limit >= 700 && depth <= 3) {
00368 if ( (depth <= 1))
00369 checkmate_limit = checkmate::limitToCheckCount(3500);
00370 else if ( (depth == 2))
00371 checkmate_limit = 1000;
00372 else if ( (depth == 3))
00373 checkmate_limit = 200;
00374 }
00375 else if (((root_limit - curLimit()) <= 500) || (depth <= 5))
00376 {
00377 assert(static_cast<unsigned int>(curLimit()) < 4096);
00378 checkmate_limit = checkmate::limitToCheckCount(std::max(0,curLimit()-200));
00379 }
00380 const SimpleHashRecord *parent = lastRecord(1);
00381 if (record->threatmate().mayHaveCheckmate(alt(P))
00382 || (parent && parent->threatmate().maybeThreatmate(alt(P))))
00383 checkmate_limit += std::max(100, checkmate_limit);
00384 if (root_limit < 800)
00385 checkmate_limit /= 2;
00386 }
00387 if (curLimit() >= table->minimumRecordLimit())
00388 {
00389
00390 checkmate_limit = record->qrecord.checkmateNodesLeft(checkmate_limit);
00391 if (checkmate_limit <= 0)
00392 return false;
00393 }
00394 else
00395 {
00396 checkmate_limit /= 2;
00397 }
00398
00399
00400 #ifdef CHECKMATE_COUNT
00401 size_t count = checkmateSearcher().totalNodeCount();
00402 #endif
00403 recorder.gotoCheckmateSearch(state(), checkmate_limit);
00404 const bool win = isWinningState<P>
00405 (checkmate_limit, checkmate_move, record->qrecord.attack_oracle);
00406 recorder.backFromCheckmateSearch();
00407 #ifdef CHECKMATE_COUNT
00408 checkmate_before += checkmateSearcher().totalNodeCount() - count;
00409 #endif
00410 return win;
00411 }
00412
00413 template <osl::Player P>
00414 bool osl::search::AlphaBeta2Tree::
00415 tryCheckmateAgain(SimpleHashRecord *record, Move& checkmate_move,
00416 int node_count, int best_value)
00417 {
00418 int checkmate_limit = 1;
00419 if (record->threatmate().maybeThreatmate(P)) {
00420 if (EvalTraits<P>::betterThan(eval.captureValue(newPtypeO(P,KING)), best_value))
00421 checkmate_limit = node_count / 2;
00422 else
00423 checkmate_limit = node_count / 8;
00424 checkmate_limit += 100;
00425 } else if (record->threatmate().mayHaveCheckmate(alt(P))) {
00426 checkmate_limit = countCheckAfterThreatmate(alt(P),2)*320 + 100;
00427 }
00428 if (true )
00429 checkmate_limit = record->qrecord.checkmateNodesLeft(checkmate_limit);
00430
00431 #ifdef CHECKMATE_COUNT
00432 size_t count = checkmateSearcher().totalNodeCount();
00433 #endif
00434 recorder.gotoCheckmateSearch(state(), checkmate_limit);
00435 const bool win = isWinningState<P>
00436 (checkmate_limit, checkmate_move, record->qrecord.attack_oracle);
00437 recorder.backFromCheckmateSearch();
00438 #ifdef CHECKMATE_COUNT
00439 checkmate_after += checkmateSearcher().totalNodeCount() - count;
00440 #endif
00441
00442 return win;
00443 }
00444
00445 bool osl::search::
00446 AlphaBeta2Tree::tryPass(SimpleHashRecord *record, Player P) const
00447 {
00448 return ! record->is_king_in_check
00449 && ! record->threatmate().maybeThreatmate(P);
00450 }
00451
00452 template <osl::Player P>
00453 const osl::MoveLogProb osl::search::
00454 AlphaBeta2Tree::nextMove()
00455 {
00456 MoveGenerator& generator = makeGenerator();
00457 SimpleHashRecord *record = lastRecord();
00458 switch (move_type[curDepth()]) {
00459 case HASH:
00460 {
00461 if (curLimit() < leaf_limit) {
00462 move_type[curDepth()] = FINISH;
00463 break;
00464 }
00465 move_type[curDepth()] = TACTICAL;
00466 const MoveLogProb best_move_in_table = record->bestMove().moveLogProb();
00467 assert(curLimit() > 0);
00468 generator.init(curLimit(), record, eval, state(),
00469 node_type[curDepth()] != CutNode,
00470 best_move_in_table.getMove());
00471 if (best_move_in_table.validMove() &&
00472 validTableMove(state(), best_move_in_table, curLimit())) {
00473 return best_move_in_table;
00474 }
00475 }
00476
00477
00478 case TACTICAL:
00479 {
00480 MoveLogProb m = generator.nextTacticalMove<P>(*this);
00481 if (m.validMove())
00482 return m;
00483
00484 move_type[curDepth()] = KILLER;
00485 killers[curDepth()].clear();
00486 if ((! record->is_king_in_check)
00487 && ! record->threatmate().maybeThreatmate(P)
00488 && (curLimit() >= 300)) {
00489 MoveVector killer_moves;
00490 getKillerMoves(killer_moves);
00491 for (MoveVector::const_iterator p=killer_moves.begin();
00492 p!=killer_moves.end(); ++p) {
00493 assert(killers[curDepth()].size() < killers[curDepth()].capacity());
00494 killers[curDepth()].push_back(*p);
00495 }
00496 std::reverse(killers[curDepth()].begin(), killers[curDepth()].end());
00497 }
00498 }
00499 case KILLER:
00500 {
00501 killer_t& killers = this->killers[curDepth()];
00502 if (! killers.empty()) {
00503 Move m = killers[killers.size()-1];
00504 killers.pop_back();
00505 return MoveLogProb(m, 300);
00506 }
00507
00508 move_type[curDepth()] = PASS;
00509 }
00510 case PASS:
00511 assert(record->is_king_in_check == EffectUtil::isKingInCheck(P, state()));
00512 move_type[curDepth()] = ALL;
00513 if (tryPass(record, P)) {
00514 const int pass_consumption = (curLimit() >= 800) ? 300 : 200;
00515 return MoveLogProb(Move::PASS(P), pass_consumption);
00516 }
00517
00518
00519 case ALL:
00520 {
00521 MoveLogProb m = generator.nextMove<P>(*this);
00522 if (m.validMove())
00523 return m;
00524 move_type[curDepth()] = FINISH;
00525 }
00526 default:
00527 assert(move_type[curDepth()] == FINISH);
00528 }
00529 return MoveLogProb();
00530 }
00531
00532
00533 template <osl::Player P>
00534 int osl::search::AlphaBeta2Tree::
00535 searchAllMoves(SimpleHashRecord *record, Window w)
00536 {
00537 #ifndef NDEBUG
00538 checkPointSearchAllMoves();
00539 #endif
00540 assert(P == state().getTurn());
00541 search_assert(w.isConsistent(), lastMove());
00542 assert(curLimit() >= 0);
00543
00544 assert(hasLastRecord(1));
00545 const SimpleHashRecord *parent = lastRecord(1);
00546 const int node_count_at_beginning = nodeCount();
00547 depth_node_count[curDepth()]++;
00548
00549 move_type[curDepth()] = INITIAL;
00550 const bool in_pv = this->in_pv[curDepth()] = ! w.null();
00551
00552
00553 if (record) {
00554 if (in_pv) {
00555 if (record->hasLowerBound(SearchTable::CheckmateSpecialDepth)) {
00556 int lower_bound = record->lowerBound();
00557 if (isWinValue(P, lower_bound))
00558 return lower_bound;
00559 }
00560 if (record->hasUpperBound(SearchTable::CheckmateSpecialDepth)) {
00561 int upper_bound = record->upperBound();
00562 if (isWinValue(alt(P), upper_bound))
00563 return upper_bound;
00564 }
00565 }
00566 else {
00567 int table_value = 0;
00568 if (record->hasGreaterLowerBound<P>(curLimit(), w.alpha(P),
00569 table_value)) {
00570 assert(eval::isConsistentValue(table_value));
00571 w.alpha(P) = table_value + EvalTraits<P>::delta;
00572 if (EvalTraits<P>::betterThan(table_value, w.beta(P))) {
00573 recorder.tableHitLowerBound(P, table_value, w.beta(P), curLimit());
00574 return table_value;
00575 }
00576 }
00577 if (record->hasLesserUpperBound<P>(curLimit(), w.beta(P), table_value)) {
00578 assert(eval::isConsistentValue(table_value));
00579 w.beta(P) = table_value - EvalTraits<P>::delta;
00580 if (EvalTraits<P>::betterThan(w.alpha(P), table_value))
00581 {
00582 recorder.tableHitUpperBound(P, table_value, w.alpha(P), curLimit());
00583 return table_value;
00584 }
00585 }
00586 }
00587
00588 Move checkmate_move=Move::INVALID();
00589 if ((!record->is_king_in_check)
00590 && record->qrecord.checkmateNodesLeft(1)
00591 && isWinningStateShort<P>(2, checkmate_move))
00592 {
00593 recordWinByCheckmate(P, record, checkmate_move);
00594 return winByCheckmate(P);
00595 }
00596 #ifndef DONT_USE_CHECKMATE
00597 assert(record);
00598
00599 int additional_limit = 0;
00600 if (parent && parent->threatmate().maybeThreatmate(alt(P)))
00601 {
00602 additional_limit = std::max(100, parent->qrecord.threatmateNodes()/8);
00603 additional_limit = record->qrecord.checkmateNodesLeft(additional_limit);
00604 }
00605 recorder.gotoCheckmateSearch(state(), additional_limit);
00606 const bool win = isWinningState<P>(additional_limit, checkmate_move,
00607 record->qrecord.attack_oracle);
00608 recorder.backFromCheckmateSearch();
00609 if (win) {
00610 assert(checkmate_move.isValid());
00611 recordWinByCheckmate(P, record, checkmate_move);
00612 return winByCheckmate(P);
00613 }
00614 #endif
00615 }
00616
00617 search_assert(w.isConsistent(), lastMove());
00618 const int initial_alpha = w.alpha(P);
00619
00620 #ifndef DONT_USE_CHECKMATE
00621
00622 testThreatmate<P>(record, in_pv);
00623 #endif
00624
00625 record->threatmate().update(P, (parent ? &(parent->threatmate()) : 0),
00626 EffectUtil::isKingInCheck(P, state()));
00627
00628 MoveLogProb best_move;
00629 int best_value = minusInfty(P);
00630 int tried_moves = 0;
00631 int alpha_update = 0;
00632 int last_alpha_update = 0;
00633 #if (defined OSL_SMP)
00634 int last_smp_idle = 0;
00635 # if (! defined OSL_SMP_NO_SPLIT_INTERNAL)
00636 bool already_split = false;
00637 # endif
00638 #endif
00639
00640
00641 MoveLogProb m = nextMove<P>();
00642 ++tried_moves;
00643 if (! m.validMove() || m.getLogProb() > curLimit()) {
00644 goto move_generation_failure;
00645 }
00646 int first_move_node;
00647 {
00648 const int previous_node_count = nodeCount();
00649
00650 assert(eval::betterThan(P, w.alpha(P), best_value));
00651 const int result = alphaBetaSearch<P>(m, w, in_pv);
00652 if (eval::betterThan(P, result, best_value)) {
00653 best_value = result;
00654 best_move = m;
00655 if (eval::betterThan(P, best_value, w.alpha(P))) {
00656 w.alpha(P) = result + EvalTraits<P>::delta;;
00657 assert(best_move.validMove());
00658 ++alpha_update;
00659 last_alpha_update = 1;
00660 if (eval::betterThan(P, result, w.beta(P))) {
00661 mpn_cut.add(tried_moves);
00662 if (move_type[curDepth()] >= ALL)
00663 setKillerMove(best_move.getMove());
00664 assert(best_move.validMove());
00665 assert(! isWinValue(alt(P), best_value));
00666 goto register_table;
00667 } else {
00668 if (in_pv)
00669 makePV(m.getMove());
00670 }
00671 }
00672 }
00673 first_move_node = nodeCount() - previous_node_count;
00674 }
00675 testStop();
00676
00677 #ifndef DONT_USE_CHECKMATE
00678 if (in_pv)
00679 {
00680 Move checkmate_move;
00681 if (tryCheckmate<P>(record, in_pv, checkmate_move)) {
00682 assert(checkmate_move.isValid());
00683 best_value= winByCheckmate(P);
00684 recordWinByCheckmate(P, record, checkmate_move);
00685 return best_value;
00686 }
00687 }
00688 #endif
00689 search_assert(w.isConsistent(), lastMove());
00690 if (curLimit() < leaf_limit)
00691 goto move_generation_failure;
00692 while (true) {
00693 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
00694 const bool prefer_split = shared && curLimit() >= shared->split_min_limit
00695 && (curLimit() >= 600
00696
00697 || (first_move_node >= 30000));
00698 try {
00699 if (prefer_split && shared->smp_idle > last_smp_idle) {
00700 last_smp_idle = shared->smp_idle;
00701 assert(! already_split);
00702 already_split = true;
00703 if (examineMovesOther<P>(w, best_move, best_value, tried_moves,
00704 alpha_update, last_alpha_update)) {
00705 assert(best_move.validMove());
00706 assert(best_move.getMove().player() == P);
00707 if (move_type[curDepth()] >= ALL)
00708 setKillerMove(best_move.getMove());
00709 mpn_cut.add(tried_moves);
00710 goto register_table;
00711 }
00712 goto all_moves_done;
00713 }
00714 }
00715 catch(SplitFailed&) {
00716 already_split = false;
00717
00718 }
00719 #endif
00720 MoveLogProb m = nextMove<P>();
00721 if (! m.validMove())
00722 break;
00723 ++tried_moves;
00724
00725 assert(eval::betterThan(P, w.alpha(P), best_value));
00726 const int result = alphaBetaSearch<P>(m, w, in_pv && ! best_move.validMove());
00727 if (eval::betterThan(P, result, best_value)) {
00728 best_value = result;
00729 best_move = m;
00730 if (eval::betterThan(P, best_value, w.alpha(P))) {
00731 w.alpha(P) = result + EvalTraits<P>::delta;;
00732 assert(best_move.validMove());
00733 ++alpha_update;
00734 last_alpha_update = tried_moves;
00735 if (eval::betterThan(P, result, w.beta(P))) {
00736 assert(best_move.validMove());
00737 if (move_type[curDepth()] >= ALL)
00738 setKillerMove(best_move.getMove());
00739 mpn_cut.add(tried_moves);
00740 goto register_table;
00741 } else {
00742 if (in_pv)
00743 makePV(m.getMove());
00744 }
00745 }
00746 }
00747 }
00748 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_INTERNAL)
00749 all_moves_done:
00750 #endif
00751 if (tried_moves == 1 && tryPass(record, P)) {
00752
00753 goto move_generation_failure;
00754 }
00755 mpn.add(tried_moves);
00756 if (alpha_update) {
00757 this->alpha_update.add(alpha_update);
00758 this->last_alpha_update.add(last_alpha_update);
00759 }
00760
00761 if (((curDepth() % 2) == 0)
00762 && EnterKing::canDeclareWin<P>(state())) {
00763 best_value = brinkmatePenalty(alt(P), std::max(1,16-curDepth())*256)
00764 + eval.value();
00765 record->setAbsoluteValue(Move::DeclareWin(), best_value,
00766 SearchTable::CheckmateSpecialDepth);
00767 return best_value;
00768 }
00769 if (record) {
00770
00771 #ifndef DONT_USE_CHECKMATE
00772 Move checkmate_move=Move::INVALID();
00773 if (tryCheckmateAgain<P>(record, checkmate_move,
00774 nodeCount() - node_count_at_beginning,
00775 best_value)) {
00776 assert(checkmate_move.isValid());
00777 best_value= winByCheckmate(P);
00778 recordWinByCheckmate(P, record, checkmate_move);
00779 return best_value;
00780 }
00781 #endif
00782 }
00783 register_table:
00784 assert(best_value == minusInfty(P) || best_move.validMove());
00785 assert(eval::isConsistentValue(best_value));
00786 if (isWinValue(alt(P), best_value))
00787 {
00788
00789
00790 best_value = brinkmatePenalty(P, std::max(1,16-curDepth())*256) + eval.value();
00791
00792
00793 record->setAbsoluteValue(best_move, best_value, curLimit());
00794 return best_value;
00795 }
00796 else if (EvalTraits<P>::betterThan(w.alpha(P), initial_alpha)) {
00797 if (best_move.validMove()) {
00798 best_move.setLogProb(RealizationProbability::TableMove);
00799 assert(best_value % 2 == 0);
00800 record->setLowerBound(P, curLimit(),
00801 SearchMove(best_move), best_value);
00802 }
00803 }
00804 if (EvalTraits<P>::betterThan(w.beta(P), best_value)) {
00805 if (best_move.validMove()) {
00806 best_move.setLogProb(RealizationProbability::TableMove);
00807 record->setUpperBound(P, curLimit(),
00808 SearchMove(best_move), best_value);
00809 }
00810 }
00811 return best_value;
00812 move_generation_failure:
00813
00814
00815 best_value = quiesce<P>(w);
00816 if (record)
00817 {
00818 if (EvalTraits<P>::betterThan(best_value, initial_alpha)) {
00819 if (EvalTraits<P>::betterThan(w.beta(P), best_value)) {
00820 record->setAbsoluteValue(MoveLogProb(), best_value, curLimit());
00821 } else {
00822 recordLowerBound(P, record, curLimit(), SearchMove(), best_value);
00823 }
00824 }
00825 else
00826 {
00827 assert(EvalTraits<P>::betterThan(w.beta(P), best_value));
00828 recordUpperBound(P, record, curLimit(), SearchMove(), best_value);
00829 }
00830 }
00831 assert(eval::isConsistentValue(best_value));
00832 return best_value;
00833 }
00834
00835 template <osl::Player P>
00836 int osl::search::AlphaBeta2Tree::
00837 quiesce(Window w)
00838 {
00839 #ifdef EXPERIMENTAL_QUIESCE
00840 return quiesceExp<P>(w);
00841 #else
00842 return quiesceStable<P>(w);
00843 #endif
00844 }
00845
00846 template <osl::Player P>
00847 int osl::search::AlphaBeta2Tree::
00848 quiesceStable(Window w)
00849 {
00850 testStop();
00851 initPV();
00852
00853 typedef QuiescenceSearch2<eval::ProgressEval> qsearcher_t;
00854 qsearcher_t qs(*this, *table);
00855 Move last_move = lastMove();
00856 if (last_move.isInvalid())
00857 last_move = Move::PASS(alt(P));
00858 assert(w.alpha(P) % 2);
00859 assert(w.beta(P) % 2);
00860 #ifdef CHECKMATE_COUNT
00861 size_t count = checkmateSearcher().totalNodeCount();
00862 #endif
00863 const int result = qs.template search<P>(w.alpha(P), w.beta(P), eval, last_move, 4);
00864 node_count += qs.nodeCount();
00865 recorder.addQuiescenceCount(qs.nodeCount());
00866 #ifdef CHECKMATE_COUNT
00867 quiesce_checkmate += checkmateSearcher().totalNodeCount() - count;
00868 #endif
00869
00870 assert(result % 2 == 0);
00871 return result;
00872 }
00873
00874 template <osl::Player P>
00875 int osl::search::AlphaBeta2Tree::
00876 quiesceExp(Window w)
00877 {
00878 testStop();
00879
00880 SimpleHashRecord *record = lastRecord();
00881 assert(record);
00882 Move best_move;
00883 const int qdepth = 4;
00884 const int previous_node_count = nodeCount();
00885
00886 int result =
00887 quiesceRoot<P>(w, qdepth, best_move, record->threatmate());
00888
00889 const size_t qnode = nodeCount() - previous_node_count;
00890 recorder.addQuiescenceCount(qnode);
00891 record->qrecord.setLowerBound(qdepth, result, best_move);
00892 return result;
00893 }
00894
00895 template <osl::Player P>
00896 struct osl::search::AlphaBeta2Tree::NextQMove
00897 {
00898 AlphaBeta2Tree *searcher;
00899 Window window;
00900 const int depth;
00901 int *result;
00902 DualThreatmateState threatmate;
00903 NextQMove(AlphaBeta2Tree *s, Window w, int d, int *r,
00904 DualThreatmateState t)
00905 : searcher(s), window(w), depth(d), result(r), threatmate(t) {
00906 }
00907 void operator()(Position ) {
00908 searcher->eval.update(searcher->state(), searcher->lastMove());
00909 *result =
00910 searcher->quiesce<P>(window, depth, threatmate);
00911 }
00912 };
00913
00914 template <osl::Player P>
00915 bool osl::search::AlphaBeta2Tree::
00916 quiesceWithMove(Move move, Window& w, int depth_left, Move& best_move, int& best_value,
00917 const DualThreatmateState& threatmate)
00918 {
00919
00920 const bool in_pv = ! w.null();
00921 int result;
00922 typedef NextQMove<PlayerTraits<P>::opponent> next_t;
00923 next_t helper(this, w, depth_left, &result, threatmate);
00924
00925 const HashKey new_hash = currentHash().newHashWithMove(move);
00926 const eval_t old_eval = eval;
00927 doUndoMoveOrPass<P,next_t>(new_hash, move, helper);
00928 eval = old_eval;
00929
00930 if (eval::betterThan(P, result, best_value)) {
00931 best_value = result;
00932 best_move = move;
00933 if (eval::betterThan(P, best_value, w.alpha(P))) {
00934 w.alpha(P) = result + EvalTraits<P>::delta;
00935 if (in_pv)
00936 makePV(best_move);
00937 if (eval::betterThan(P, result, w.beta(P))) {
00938 return true;
00939 }
00940 }
00941 }
00942 return false;
00943 }
00944
00945 template <osl::Player P>
00946 int osl::search::AlphaBeta2Tree::
00947 quiesceRoot(Window w, int depth_left, Move& best_move, DualThreatmateState threatmate)
00948 {
00949 assert(! EffectUtil::isKingInCheck(alt(P), state()));
00950
00951 initPV();
00952
00953
00954
00955 SimpleHashRecord& record = *lastRecord();
00956 assert(record.is_king_in_check == EffectUtil::isKingInCheck(P, state()));
00957 assert(depth_left > 0);
00958
00959 int best_value = minusInfty(P);
00960
00961 if (! record.is_king_in_check) {
00962 if (! threatmate.maybeThreatmate(P)) {
00963 best_value = eval.value();
00964 } else {
00965 const int value = eval.value() + threatmatePenalty(P);
00966 best_value = EvalTraits<P>::max(best_value, value);
00967 }
00968 best_move = Move::PASS(P);
00969 if (EvalTraits<P>::betterThan(best_value, w.alpha(P))) {
00970 if (EvalTraits<P>::betterThan(best_value, w.beta(P)))
00971 return best_value;
00972 w.alpha(P) = best_value + EvalTraits<P>::delta;
00973 }
00974 }
00975
00976 Move prev_best = record.qrecord.bestMove();
00977 MoveGenerator& generator = makeGenerator();
00978 generator.init(200, &record, eval, state(),
00979 w.alpha(P) == w.beta(P),
00980 prev_best, true);
00981 int tried_moves = 0;
00982
00983 if (prev_best.isNormal()) {
00984 ++tried_moves;
00985 if (quiesceWithMove<P>(prev_best, w, depth_left-1, best_move, best_value,
00986 threatmate))
00987 goto finish;
00988 }
00989
00990
00991
00992 for (MoveLogProb m = generator.nextTacticalMove<P>(*this);
00993 m.validMove(); m = generator.nextTacticalMove<P>(*this)) {
00994 ++tried_moves;
00995 if (quiesceWithMove<P>(m.getMove(), w, depth_left-1, best_move, best_value,
00996 threatmate))
00997 goto finish;
00998 }
00999 for (MoveLogProb m = generator.nextMove<P>(*this);
01000 m.validMove(); m = generator.nextMove<P>(*this)) {
01001 ++tried_moves;
01002 if (quiesceWithMove<P>(m.getMove(), w, depth_left-1, best_move, best_value,
01003 threatmate))
01004 goto finish;
01005 }
01006
01007
01008 if (record.is_king_in_check) {
01009 if (tried_moves == 0) {
01010 if (lastMove().isNormal() && lastMove().ptype() == PAWN && lastMove().isDrop())
01011 return winByFoul(P);
01012 return winByCheckmate(alt(P));
01013 }
01014 goto finish;
01015 }
01016 finish:
01017 return best_value;
01018 }
01019
01020 template <osl::Player P>
01021 int osl::search::AlphaBeta2Tree::
01022 quiesce(Window w, int depth_left, DualThreatmateState parent_threatmate)
01023 {
01024 if (EffectUtil::isKingInCheck(alt(P), state())) {
01025 return this->minusInfty(alt(P));
01026 }
01027
01028 initPV();
01029 depth_node_count_quiesce[curDepth()]++;
01030 ++node_count;
01031
01032 SimpleHashRecord record;
01033 record.is_king_in_check = EffectUtil::isKingInCheck(P, state());
01034
01035 DualThreatmateState threatmate;
01036 threatmate.update(P, &parent_threatmate, record.is_king_in_check);
01037
01038 int best_value = minusInfty(P);
01039
01040 if (depth_left <= 0) {
01041 if (record.is_king_in_check) {
01042 if (lastMove().capturePtype() != PTYPE_EMPTY)
01043 depth_left +=2;
01044 else
01045 depth_left = 0;
01046 }
01047 else if (threatmate.maybeThreatmate(P)) {
01048 if (threatmate.mayHaveCheckmate(alt(P))) {
01049 Move checkmate_move;
01050 bool win = isWinningState<P>(10, checkmate_move, record.qrecord.attack_oracle);
01051 if (win)
01052 return winByCheckmate(P);
01053 }
01054 return eval.value() + threatmatePenalty(P);
01055 }
01056 else {
01057 if (threatmate.mayHaveCheckmate(alt(P)))
01058 return eval.value() + threatmatePenalty(alt(P));
01059 if (ImmediateCheckmate::hasCheckmateMove<P>(state()))
01060 return winByCheckmate(P);
01061 if (ImmediateCheckmate::hasCheckmateMove<PlayerTraits<P>::opponent>(state()))
01062 return eval.value() + threatmatePenalty(P);
01063 return eval.value();
01064 }
01065 }
01066
01067 if (! record.is_king_in_check) {
01068 if (ImmediateCheckmate::hasCheckmateMove<P>(state())) {
01069 return winByCheckmate(P);
01070 }
01071 }
01072 if (threatmate.mayHaveCheckmate(alt(P))) {
01073 Move checkmate_move;
01074 bool win = isWinningState<P>(10, checkmate_move, record.qrecord.attack_oracle);
01075 if (win)
01076 return winByCheckmate(P);
01077 }
01078 MoveGenerator& generator = makeGenerator();
01079 generator.init(200, &record, eval, state(),
01080 w.alpha(P) == w.beta(P),
01081 Move(), true);
01082 int tried_moves = 0;
01083 Move best_move;
01084
01085 if (! record.is_king_in_check) {
01086 if (! threatmate.maybeThreatmate(P)) {
01087 best_value = eval.value();
01088 } else {
01089 const int value = eval.value() + threatmatePenalty(P);
01090 best_value = EvalTraits<P>::max(best_value, value);
01091 }
01092 best_move = Move::PASS(P);
01093 if (EvalTraits<P>::betterThan(best_value, w.alpha(P))) {
01094 if (EvalTraits<P>::betterThan(best_value, w.beta(P)))
01095 return best_value;
01096 w.alpha(P) = best_value + EvalTraits<P>::delta;
01097 }
01098 }
01099
01100
01101 for (MoveLogProb m = generator.nextTacticalMove<P>(*this);
01102 m.validMove(); m = generator.nextTacticalMove<P>(*this)) {
01103 ++tried_moves;
01104 if (quiesceWithMove<P>(m.getMove(), w, depth_left-1, best_move, best_value,
01105 threatmate))
01106 goto finish;
01107 }
01108 for (MoveLogProb m = generator.nextMove<P>(*this);
01109 m.validMove(); m = generator.nextMove<P>(*this)) {
01110 ++tried_moves;
01111 if (quiesceWithMove<P>(m.getMove(), w, depth_left-1, best_move, best_value,
01112 threatmate))
01113 goto finish;
01114 }
01115
01116
01117 if (record.is_king_in_check) {
01118 if (tried_moves == 0) {
01119 if (lastMove().ptype() == PAWN && lastMove().isDrop())
01120 return winByFoul(P);
01121 return winByCheckmate(alt(P));
01122 }
01123 goto finish;
01124 }
01125 finish:
01126 return best_value;
01127 }
01128
01129 void osl::search::AlphaBeta2Tree::updateCheckmateCount()
01130 {
01131 #ifdef OSL_SMP
01132 if (shared) {
01133 recorder.setCheckmateCount(shared->checkmateCount());
01134 return;
01135 }
01136 #endif
01137 recorder.setCheckmateCount
01138 (checkmateSearcher().totalNodeCount());
01139 }
01140
01141 void osl::search::AlphaBeta2Tree::
01142 showPV(std::ostream& os, int result, Move m) const
01143 {
01144 #ifdef OSL_SMP
01145 boost::scoped_ptr<boost::mutex::scoped_lock> lk;
01146 if (shared)
01147 lk.reset(new boost::mutex::scoped_lock(shared->lock_io));
01148 #endif
01149 assert(m.isNormal());
01150 #ifdef SHOW_ALSO_OLD_PV
01151 MoveVector moves;
01152 size_t quiesce_start = (size_t)-1;
01153 moves.push_back(m);
01154 HashKey key = currentHash().newHashWithMove(m);
01155 table->getPV(key, moves, &quiesce_start);
01156 os << "! " << std::setfill(' ') << std::setw(5)
01157 << result*100/eval.captureValue(newPtypeO(WHITE,PAWN))*2 << " ";
01158 for (size_t i=0; i<moves.size(); ++i) {
01159 if (i == quiesce_start)
01160 os << " | ";
01161 os << record::csa::show(moves[i]);
01162 }
01163 os << std::endl;
01164 #endif
01165 if (root_ignore_moves)
01166 os << "[" << root_ignore_moves->size() << "] ";
01167 os << " " << std::setfill(' ') << std::setw(5)
01168 << result*100/eval.captureValue(newPtypeO(WHITE,PAWN))*2 << " ";
01169 for (size_t i=0; i<pv[0].size(); ++i) {
01170 os << record::csa::show(pv[0][i]);
01171 }
01172 os << std::endl;
01173 }
01174
01175 template <osl::Player P>
01176 struct osl::search::AlphaBeta2Tree::NextMove
01177 {
01178 AlphaBeta2Tree *searcher;
01179 const MoveLogProb& moved;
01180 Window window;
01181 int *result;
01182 bool in_pv;
01183 NextMove(AlphaBeta2Tree *s, const MoveLogProb& md, Window w, int *r,
01184 bool p)
01185 : searcher(s), moved(md), window(w), result(r), in_pv(p) {
01186 assert(P == md.getMove().player());
01187 }
01188 void operator()(Position ) {
01189 #ifndef NDEBUG
01190 const int cur_limit = searcher->curLimit();
01191 #endif
01192 *result =
01193 searcher->alphaBetaSearchAfterMove<P>(moved, window, in_pv);
01194 assert(cur_limit == searcher->curLimit() || searcher->SearchState2Core::abort());
01195 }
01196 };
01197
01198 template <osl::Player P>
01199 int osl::search::AlphaBeta2Tree::
01200 alphaBetaSearch(const MoveLogProb& search_move, Window w, bool in_pv)
01201 {
01202 assert(w.alpha(P) % 2);
01203 assert(w.beta(P) % 2);
01204 const Move move = search_move.getMove();
01205 assert(P == move.player());
01206 assert(P == state().getTurn());
01207 assert(eval::notLessThan(P, w.beta(P), w.alpha(P)));
01208
01209 if ((! timerAvailable()) && (! timer.isInvalid()) && (! timer.timeLeft()))
01210 throw misc::NoMoreTime();
01211
01212 if (! move.isPass()
01213 && (move_classifier::MoveAdaptor<move_classifier::PawnDropCheckmate<P> >
01214 ::isMember(state(), move))) {
01215 return winByFoul(alt(P));
01216 }
01217
01218 const HashKey new_hash = currentHash().newHashWithMove(move);
01219 assert(P == move.player());
01220
01221 if (move.isPass())
01222 pass_count.inc(P);
01223
01224
01225 if (! pass_count.loopByBothPass()) {
01226 const Sennichite next_sennichite
01227 = repetition_counter.isAlmostSennichite(new_hash);
01228 if (next_sennichite.isDraw())
01229 return drawValue();
01230 if (next_sennichite.hasWinner())
01231 return winByFoul(next_sennichite.winner());
01232 assert(next_sennichite.isNormal());
01233 }
01234
01235 if (! move.isPass()) {
01236
01237 const DominanceCheck::Result has_dominance
01238 = DominanceCheck::detect(repetition_counter.history(), new_hash);
01239 if (has_dominance == DominanceCheck::LOSE)
01240 return winByLoop(alt(P));
01241 if (has_dominance == DominanceCheck::WIN)
01242 return winByLoop(P);
01243
01244 if (move.capturePtype() == PTYPE_EMPTY) {
01245 const int sacrifice_count = countSacrificeCheck2(curDepth());
01246 if (sacrifice_count == 2) {
01247
01248 const Position to = move.to();
01249 int offence = state().countEffect(P, to) + (move.isDrop() ? 1 : 0);
01250 const int deffense = state().hasEffectBy(alt(P), to);
01251 if (offence <= deffense)
01252 offence += AdditionalEffect::count2(state(), to, P);
01253 if (offence <= deffense) {
01254 return winByLoop(alt(P));
01255 }
01256 }
01257 }
01258 }
01259
01260
01261 int result;
01262 NextMove<P> helper(this, search_move, w, &result, in_pv);
01263
01264 recorder.addNodeCount();
01265 const eval_t old_eval = eval;
01266 doUndoMoveOrPass<P,NextMove<P> >
01267 (new_hash, move, helper);
01268 eval = old_eval;
01269
01270 if (move.isPass())
01271 pass_count.dec(P);
01272
01273 return result;
01274 }
01275
01276 template <osl::Player P>
01277 void osl::search::AlphaBeta2Tree::
01278 examineMovesRoot(const MoveLogProbVector& moves, size_t i, Window window,
01279 MoveLogProb& best_move, int& best_value)
01280 {
01281 for (;i<moves.size(); ++i) {
01282 testStop();
01283
01284 #if (defined OSL_SMP) && (! defined OSL_SMP_NO_SPLIT_ROOT)
01285 if (shared && i > 8
01286 && moves.size() > i+1 && shared->smp_idle) {
01287 try {
01288 examineMovesRootPar<P>(moves, i, window, best_move, best_value);
01289 break;
01290 } catch (SplitFailed&) {
01291 }
01292 }
01293 #endif
01294
01295 const MoveLogProb& m = moves[i];
01296 const int result = alphaBetaSearch<P>(m, window, false);
01297 if (eval::betterThan(P, result, best_value)) {
01298 window.alpha(P) = result + EvalTraits<P>::delta;
01299 best_move = m;
01300 best_value = result;
01301 makePV(m.getMove());
01302 if (table->isVerbose()) {
01303 showPV(std::cerr, result, m.getMove());
01304 }
01305 if (eval::betterThan(P, result, window.beta(P))) {
01306 assert(! isWinValue(alt(P), result));
01307 break;
01308 }
01309 }
01310 }
01311 }
01312
01313
01314
01315 osl::search::AlphaBeta2::
01316 AlphaBeta2(const HashEffectState& s, checkmate_t& c,
01317 SimpleHashTable *t, CountRecorder& r)
01318 : AlphaBeta2Tree(s, c, t, r)
01319 {
01320 }
01321
01322 osl::search::AlphaBeta2::
01323 ~AlphaBeta2()
01324 {
01325 }
01326
01327 osl::Move osl::search::AlphaBeta2::
01328 computeBestMoveIteratively(int limit, const int step,
01329 int initial_limit, int node_limit,
01330 const misc::RealTime& initial_stop_shedule)
01331 {
01332 setStopSchedule(initial_stop_shedule);
01333 initial_limit = std::min(initial_limit, limit);
01334
01335 const bool use_signal_timer = hasSchedule();
01336 if (use_signal_timer)
01337 {
01338 this->timer = stopSchedule();
01339 setTimeOut(timer.getTimeLeftInSeconds());
01340 }
01341 else
01342 {
01343 this->timer = misc::RealTime(6000);
01344 }
01345
01346 recorder.resetNodeCount();
01347
01348 double last_iteration_consumed = 0;
01349 double total_consumed = 0;
01350 int limit_iterative = initial_limit;
01351 Move last_best_move = Move::INVALID();
01352
01353 #ifdef OSL_SMP
01354 # ifdef SPLIT_STAT
01355 if (shared) {
01356 shared->parallel_splits = 0;
01357 shared->cancelled_splits.setValue(0);
01358 shared->parallel_abort.setValue(0);
01359 }
01360 # endif
01361 #endif
01362 try
01363 {
01364 if (table->verboseLevel() > 1)
01365 {
01366 MoveVector moves;
01367 move_generator::LegalMoves::generate(state(), moves);
01368 for (size_t i=0; i<moves.size(); ++i) {
01369 HashKey key = currentHash().newHashWithMove(moves[i]);
01370 const SimpleHashRecord *record = table->find(key);
01371 if (! record || record->lowerLimit() < SearchTable::HistorySpecialDepth)
01372 continue;
01373 std::cerr << "prebound value " << record::csa::show(moves[i])
01374 << " " << record->lowerBound() << " " << record->upperBound() << "\n";
01375 }
01376 }
01377
01378 MoveLogProb search_move;
01379 alphaBetaSearchRoot(search_move, 0);
01380 if (table->verboseLevel() > 1)
01381 std::cerr << "=> quiesce "
01382 << record::csa::show(search_move.getMove()) << "\n";
01383 while (limit_iterative < limit)
01384 {
01385 this->timer = stopSchedule();
01386 if (table->verboseLevel() > 1)
01387 std::cerr << "=> iteration " << limit_iterative
01388 << " " << timer.getTimeLeftInDouble() << " left ("
01389 << last_iteration_consumed << ", " << total_consumed << ")" << "\n";
01390 recorder.startSearch(limit_iterative);
01391 const int previous_node_count = nodeCount();
01392 alphaBetaSearchRoot(search_move, limit_iterative);
01393
01394 last_best_move = search_move.getMove();
01395 last_iteration_consumed = timer.getConsumedInDouble() - total_consumed;
01396 total_consumed += last_iteration_consumed;
01397
01398 updateCheckmateCount();
01399 if (table->verboseLevel() > 1) {
01400 std::cerr << "<= "
01401 << record::csa::show(search_move.getMove());
01402 std::cerr << std::setprecision(3) << " mpn " << mpn.getAverage()
01403 << " cut " << mpn_cut.getAverage()
01404 << " alpha " << alpha_update.getAverage()
01405 << " last " << last_alpha_update.getAverage()
01406 << " ext " << 100.0*ext.getAverage() << "%"
01407 << " ext_limit " << ext_limit.getAverage();
01408 #ifdef OSL_SMP
01409 # ifdef SPLIT_STAT
01410 if (shared) {
01411 std::cerr << " split " << shared->parallel_splits << " cancel " << shared->cancelled_splits.value()
01412 << " abort " << shared->parallel_abort.value();
01413 }
01414 # endif
01415 #endif
01416 std::cerr << "\n";
01417 }
01418 bool time_over = false;
01419 if (hasSchedule()) {
01420 const double current_time_left = stopSchedule().getTimeLeftInDouble();
01421 const double coef = nextIterationCoefficient();
01422 if (current_time_left
01423 < last_iteration_consumed * coef)
01424 time_over = true;
01425 if (! time_over) {
01426 SimpleHashRecord *record
01427 = table->find(currentHash());
01428 if (record) {
01429 record->addNodeCount(nodeCount() - previous_node_count);
01430 }
01431 }
01432 }
01433 #ifdef OSL_SMP
01434 const size_t main_checkmate_count
01435 = shared ? shared->mainCheckmateCount() : checkmateSearcher().mainNodeCount();
01436 #else
01437 const size_t main_checkmate_count = checkmateSearcher().mainNodeCount();
01438 #endif
01439 const bool checkmate_over = main_checkmate_count > CHECKMATE_DEFAULT_TOTAL_NODE_LIMIT;
01440 bool node_limit_over = (recorder.nodeCount() *4 > node_limit)
01441 || checkmate_over;
01442 recorder.finishSearch(search_move.getMove(),
01443 total_consumed,
01444 (time_over || node_limit_over) && table->verboseLevel());
01445 if (time_over || node_limit_over) {
01446 if (table->isVerbose())
01447 std::cerr << "iteration stop at " << limit_iterative << " by "
01448 << (time_over ? "time" : (checkmate_over ? "checkmate count" : "node count")) << "\n";
01449 goto finish;
01450 }
01451 testStop();
01452 limit_iterative += step;
01453 }
01454 if (table->verboseLevel() > 1)
01455 std::cerr << "=> final iteration " << limit_iterative
01456 << " " << timer.getTimeLeftInDouble() << " left ("
01457 << last_iteration_consumed << ", " << total_consumed << ")" << "\n";
01458 while (true) {
01459 recorder.startSearch(limit);
01460 try {
01461 alphaBetaSearchRoot(search_move, limit);
01462 } catch (...) {
01463 updateCheckmateCount();
01464 last_iteration_consumed = timer.getConsumedInDouble() - total_consumed;
01465 total_consumed += last_iteration_consumed;
01466 recorder.finishSearch(search_move.getMove(), total_consumed,
01467 table->verboseLevel());
01468 throw;
01469 }
01470 last_iteration_consumed = timer.getConsumedInDouble() - total_consumed;
01471 total_consumed += last_iteration_consumed;
01472 updateCheckmateCount();
01473 recorder.finishSearch(search_move.getMove(), total_consumed,
01474 table->verboseLevel());
01475 last_best_move = search_move.getMove();
01476
01477 if (last_best_move.isNormal())
01478 break;
01479 testStop();
01480
01481
01482 if (limit >= 2000)
01483 break;
01484
01485 limit += 200;
01486 if (table->isVerbose())
01487 std::cerr << " extend limit to " << limit << " before resign\n";
01488 }
01489 }
01490 catch (std::exception& e)
01491 {
01492 std::cerr << "std exception " << e.what() << "\n";
01493 }
01494 catch (...)
01495 {
01496 std::cerr << "unknown exception\n";
01497 #ifndef NDEBUG
01498 throw;
01499 #endif
01500 }
01501 finish:
01502 if (use_signal_timer)
01503 resetTimeOut();
01504 if (table->verboseLevel() > 1) {
01505 std::cerr << "<= " << record::csa::show(last_best_move);
01506 std::cerr << " mpn " << mpn.getAverage()
01507 << " cut " << mpn_cut.getAverage()
01508 << " alpha " << alpha_update.getAverage()
01509 << " last " << last_alpha_update.getAverage()
01510 << " ext " << ext.getAverage()
01511 << " ext_limit " << ext_limit.getAverage();
01512 #ifdef OSL_SMP
01513 # ifdef SPLIT_STAT
01514 if (shared) {
01515 std::cerr << " split " << shared->parallel_splits << " cancel " << shared->cancelled_splits.value()
01516 << " abort " << shared->parallel_abort.value();
01517 }
01518 # endif
01519 #endif
01520 std::cerr << "\n";
01521 }
01522 return last_best_move;
01523 }
01524
01525 template <osl::Player P>
01526 int osl::search::AlphaBeta2::
01527 alphaBetaSearchRoot(Window window, MoveLogProb& best_move, int limit)
01528 {
01529 assert(P == state().getTurn());
01530 assert(window.alpha(P) % 2);
01531 assert(window.beta(P) % 2);
01532 setRoot(limit);
01533 assert(curDepth() == 0);
01534 node_type[curDepth()] = PvNode;
01535
01536 #ifdef OSL_SMP
01537 if (shared)
01538 shared->threadStart();
01539 #endif
01540
01541 SimpleHashRecord *record_in_table
01542 = table->allocate(currentHash(), limit);
01543 SimpleHashRecord *record = record_in_table;
01544 boost::scoped_ptr<SimpleHashRecord> record_if_not_allocated;
01545 if (! record)
01546 {
01547 record_if_not_allocated.reset(new SimpleHashRecord());
01548 record = record_if_not_allocated.get();
01549 }
01550 assert(record);
01551 setRootRecord(record);
01552 assert(rootRecord() == record);
01553 assert(hasLastRecord() && lastRecord() == record);
01554 record->is_king_in_check = EffectUtil::isKingInCheck(P, state());
01555
01556 if (limit == 0) {
01557 int result = quiesce<P>(fullWindow(P));
01558 best_move = MoveLogProb(record->qrecord.bestMove(), 100);
01559 if (root_ignore_moves
01560 && root_ignore_moves->isMember(best_move.getMove()))
01561 best_move = MoveLogProb();
01562 return result;
01563 }
01564 if (record_in_table) {
01565 int table_value = 0;
01566 const MoveLogProb m = record_in_table->bestMove().moveLogProb();
01567 if (! m.getMove().isNormal())
01568 record_in_table->resetValue();
01569 else if (record->hasGreaterLowerBound<P>(curLimit(), window.beta(P),
01570 table_value)) {
01571 if (! root_ignore_moves
01572 || ! root_ignore_moves->isMember(m.getMove())) {
01573 best_move = m;
01574 return table_value;
01575 }
01576 }
01577 }
01578
01579
01580 MoveLogProbVector moves;
01581 MoveGenerator& generator = makeGenerator();
01582 const MoveLogProb last_best_move = record->bestMove().moveLogProb();
01583 {
01584 MoveLogProbVector raw_moves;
01585 assert(curLimit() > 0);
01586 generator.init(curLimit()+200, record, eval, state(), true, last_best_move.getMove());
01587 if (last_best_move.getMove().isNormal())
01588 raw_moves.push_back(last_best_move);
01589 generator.generateAll<P>(*this, raw_moves);
01590
01591
01592 for (size_t i=0; i<raw_moves.size(); ++i) {
01593 const HashKey key = currentHash().newHashWithMove(raw_moves[i].getMove());
01594 const SimpleHashRecord *record = table->find(key);
01595 if (record) {
01596 if (record->hasLowerBound(SearchTable::CheckmateSpecialDepth)
01597 && isWinValue(alt(P), record->lowerBound()))
01598 continue;
01599 }
01600 if (root_ignore_moves && root_ignore_moves->isMember(raw_moves[i].getMove()))
01601 continue;
01602 raw_moves[i].setLogProbAtMost(limit);
01603 moves.push_back(raw_moves[i]);
01604 }
01605 }
01606
01607 if (moves.size() == 1) {
01608 best_move = moves[0];
01609 return (window.alpha(P)+window.beta(P))/2;
01610 }
01611
01612 #ifndef DONT_USE_CHECKMATE
01613
01614 int checkmate_node = 0;
01615 if (root_ignore_moves == 0) {
01616 int checkmate_max = 30000*std::max(limit - 300, 0)/100;
01617 if (limit >= 1000)
01618 checkmate_max = std::min(400000, 60000*(limit - 800)/100);
01619 checkmate_node = record->qrecord.checkmateNodesLeft(checkmate_max);
01620 #ifdef CHECKMATE_COUNT
01621 std::cerr << "limit " << limit << " checkmate " << checkmate_node << "\n";
01622 #endif
01623 }
01624 if (checkmate_node > 0)
01625 {
01626 const bool my_king_in_check
01627 = state().hasEffectBy(alt(P),state().getKingPosition(P));
01628 if (my_king_in_check)
01629 {
01630
01631 recorder.gotoCheckmateSearch(state(), checkmate_node);
01632 const bool lose = isLosingState<P>(checkmate_node/8);
01633 recorder.backFromCheckmateSearch();
01634 if (lose)
01635 {
01636 best_move = MoveLogProb(Move::INVALID(),100);
01637 recordLoseByCheckmate(P, record);
01638 return winByCheckmate(alt(P));
01639 }
01640 }
01641
01642 {
01643 Move checkmate_move;
01644 #ifdef CHECKMATE_COUNT
01645 size_t count = checkmateSearcher().totalNodeCount();
01646 #endif
01647 recorder.gotoCheckmateSearch(state(), checkmate_node);
01648 const bool win = isWinningState<P>
01649 (checkmate_node, checkmate_move, record->qrecord.attack_oracle);
01650 recorder.backFromCheckmateSearch();
01651 #ifdef CHECKMATE_COUNT
01652 root_checkmate += checkmateSearcher().totalNodeCount() - count;
01653 #endif
01654 if (win)
01655 {
01656 best_move = MoveLogProb(checkmate_move,100);
01657 recordWinByCheckmate(P, record, checkmate_move);
01658 return winByCheckmate(P);
01659 }
01660 }
01661
01662 if ((! my_king_in_check)
01663 && (! (record->threatmate().isThreatmate(P))))
01664 {
01665 Move threatmate_move;
01666 #ifdef CHECKMATE_COUNT
01667 size_t count = checkmateSearcher().totalNodeCount();
01668 #endif
01669 recorder.gotoCheckmateSearch(state(), checkmate_node);
01670 const bool threatmate
01671 = isThreatmateState<P>
01672 (checkmate_node, threatmate_move, record->qrecord.threatmate_oracle);
01673 #ifdef CHECKMATE_COUNT
01674 root_checkmate += checkmateSearcher().totalNodeCount() - count;
01675 #endif
01676 recorder.backFromCheckmateSearch();
01677 if (threatmate)
01678 {
01679 if (record)
01680 record->threatmate().setThreatmate(P, threatmate_move);
01681 if (table->verboseLevel() > 1)
01682 std::cerr << " root threatmate " << threatmate_move << "\n";
01683 }
01684 }
01685
01686 }
01687 #endif
01688
01689 const int ValueNone = window.alpha(P) - EvalTraits<P>::delta;
01690 int best_value = ValueNone;
01691 try {
01692
01693 size_t i=0;
01694 for (;i<moves.size() && best_value == ValueNone; ++i) {
01695 const MoveLogProb& m = moves[i];
01696 const int result = alphaBetaSearch<P>(m, window, true);
01697 if (eval::betterThan(P, result, best_value)) {
01698 window.alpha(P) = result + EvalTraits<P>::delta;
01699 best_move = m;
01700 best_value = result;
01701 makePV(m.getMove());
01702 if (table->isVerbose()) {
01703 showPV(std::cerr, result, m.getMove());
01704 }
01705 if (eval::betterThan(P, result, window.beta(P))) {
01706 assert(! isWinValue(alt(P), result));
01707 }
01708 }
01709 }
01710 if (! eval::betterThan(P, window.alpha(P), window.beta(P))) {
01711 examineMovesRoot<P>(moves, i, window, best_move, best_value);
01712 }
01713 } catch (misc::NoMoreTime&) {
01714 if (best_move.validMove()
01715 && best_move.getMove() != last_best_move.getMove()) {
01716 if (table->verboseLevel() > 1)
01717 std::cerr << "! use better move than the last best move\n";
01718 }
01719 else {
01720 #ifdef OSL_SMP
01721 if (shared)
01722 shared->waitAll();
01723 #endif
01724 throw;
01725 }
01726 }
01727
01728 assert(best_value % 2 == 0);
01729 record->setLowerBound(P, curLimit(), SearchMove(best_move),
01730 best_value);
01731 #ifdef OSL_SMP
01732 if (shared)
01733 shared->waitAll();
01734 #endif
01735 return best_value;
01736 }
01737
01738
01739 void osl::search::AlphaBeta2::setRoot(int limit)
01740 {
01741 SearchState2::setRoot(limit);
01742 SimpleHashRecord *record = table->allocate(currentHash(), std::max(1000,limit));
01743 assert(record);
01744 setRootRecord(record);
01745 move_type[curDepth()] = INITIAL;
01746 }
01747
01748 void osl::search::AlphaBeta2::makeMove(Move move)
01749 {
01750 assert(state().isValidMove(move));
01751 SearchState2::makeMove(move);
01752 eval.update(state(), move);
01753
01754 SimpleHashRecord *record
01755 = table->allocate(currentHash(), curLimit());
01756 assert(record);
01757 move_type[curDepth()] = INITIAL;
01758 record->is_king_in_check = EffectUtil::isKingInCheck(state().getTurn(), state());
01759 setCurrentRecord(record);
01760 }
01761
01762 bool osl::search::AlphaBeta2::
01763 isReasonableMove(Move , int )
01764 {
01765 return true;
01766 }
01767
01768
01769 void osl::search::AlphaBeta2::
01770 showNodeDepth(std::ostream& os)
01771 {
01772 int max_depth=0;
01773 for (int i=MaxDepth-1; i>=0; --i) {
01774 if (depth_node_count[i] || depth_node_count_quiesce[i]) {
01775 max_depth = i;
01776 break;
01777 }
01778 }
01779 int max_count=0;
01780 for (int i=0; i<=max_depth; i+=2) {
01781 max_count = std::max(max_count,
01782 depth_node_count[i]+depth_node_count_quiesce[i]);
01783 }
01784
01785 int unit = std::max(max_count/79, 100);
01786 for (int i=0; i<=max_depth; i+=2) {
01787 os << std::setw(3) << i << " "
01788 << std::string(depth_node_count[i]/unit, '*')
01789 << std::string(depth_node_count_quiesce[i]/unit, '+')
01790 << std::endl;
01791 }
01792 #ifdef CHECKMATE_COUNT
01793 std::cerr << "checkmate root " << root_checkmate << " quiesce " << quiesce_checkmate
01794 << "\nnormal before " << checkmate_before
01795 << " after " << checkmate_after << " threatmate " << count_threatmate
01796 << "\n";
01797 #endif
01798 }
01799
01800 void osl::search::AlphaBeta2::
01801 clearNodeDepth()
01802 {
01803 depth_node_count.fill(0);
01804 depth_node_count_quiesce.fill(0);
01805 }
01806
01807
01808 namespace osl
01809 {
01810 namespace search
01811 {
01812 template
01813 void AlphaBeta2Tree::examineMovesRoot<BLACK>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
01814 template
01815 void AlphaBeta2Tree::examineMovesRoot<WHITE>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
01816 }
01817 }
01818
01819
01820
01821
01822
01823