00001
00002
00003 #ifndef _QUIESCENCESEARCH2_TCC
00004 #define _QUIESCENCESEARCH2_TCC
00005
00006 #include "osl/search/quiescenceSearch2.h"
00007 #include "osl/search/quiescenceGenerator.h"
00008 #include "osl/search/quiescenceLog.h"
00009 #include "osl/search/searchTable.h"
00010 #include "osl/search/simpleHashRecord.h"
00011 #include "osl/search/simpleHashTable.h"
00012 #include "osl/search/sortCaptureMoves.h"
00013 #include "osl/checkmate/immediateCheckmate.h"
00014 #include "osl/hash/hashCollision.h"
00015 #include "osl/apply_move/applyMove.h"
00016 #include "osl/apply_move/applyMoveWithPath.h"
00017 #include "osl/effect_util/effectUtil.h"
00018 #include "osl/move_order/captureSort.h"
00019 #include "osl/move_classifier/check_.h"
00020 #include "osl/move_classifier/moveAdaptor.h"
00021 #include "osl/move_classifier/pawnDropCheckmate.h"
00022 #include "osl/effect_util/unblockableEffect.h"
00023 #include "osl/effect_util/neighboring8Direct.h"
00024 #include "osl/eval/see.h"
00025 #include "osl/stat/ratio.h"
00026
00027 #ifdef STAT_WIDTH_VS_LIMIT
00028 # include "osl/stat/average.h"
00029 # include <iostream>
00030 #endif
00031
00032 #define quiecence_assert(x,m) assert((x) || state.abort(m))
00033
00034 #ifdef RICH_QSEARCH
00035
00036 # define QSEARCH_LAST_CHECK_PENALTY
00037
00038 # define QSEARCH_PESSIMISTIC_ESCAPE_THREAT
00039
00040 # define QSEARCH_THREATMATE
00041 #endif
00042
00043 #ifdef EXTRA_RICH_QSEARCH
00044
00045 # define QSEARCH_SET_MINIMUM_MOVES
00046 #endif
00047
00048
00049
00050
00051 const int allocate_depth_in_threatmate = 400;
00052
00053 namespace osl
00054 {
00055 namespace search
00056 {
00057 struct QSearch2PrivateTraits
00058 {
00059 enum {
00060 KnightCaptureDepth = 1,
00061 PawnCaptureDepth = 3,
00062 UtilizePromotedDepth = 5,
00063 AttackPinnedDepth = 6,
00064 };
00065 enum {
00066 EscapeDepthFromRoot = 1,
00067 EscapeFromLastMoveDepthFromRoot = 3,
00068 AttackKnightDepthFromRoot = 2,
00069 AttackGoldSilverDepthFromRoot = 2,
00070 DropDepthFromRoot = 2,
00071 AttackMajorPieceDepthFromRoot = 2,
00072 AdvanceBishopDepthFromRoot = 2,
00073 AttackKing8DepthFromRoot = 2,
00074 };
00075 enum {
00076 ThreatMateDepthFromRoot = 2,
00077 };
00078 enum {
00080 PassExtraDepth = 4,
00081 };
00082 enum {
00087 #ifdef QSEARCH_SET_MINIMUM_MOVES
00088 MinimumMoves = 6,
00089 #else
00090 MinimumMoves = 0,
00091 #endif
00092 };
00093 };
00094
00095 struct QSearch2HelperBase
00096 {
00097 int& result;
00098 int alpha, beta;
00099 Move last_move;
00100 QSearch2HelperBase(int& r, int a, int b, Move l)
00101 : result(r), alpha(a), beta(b), last_move(l)
00102 {
00103 }
00104 };
00105
00106 template <class QSearch2,Player P>
00107 struct QSearch2NextMove : public QSearch2HelperBase
00108 {
00109 typedef typename QSearch2::eval_t eval_t;
00110 QSearch2 *searcher;
00111 eval_t& ev;
00112 int additional_depth;
00113 QSearch2NextMove(int& r, QSearch2 *s, int a, int b, eval_t& e, Move l,
00114 int additional)
00115 : QSearch2HelperBase(r, a, b, l),
00116 searcher(s), ev(e), additional_depth(additional)
00117 {
00118 }
00119 void operator()(Position)
00120 {
00121 ev.update(searcher->currentState(), last_move);
00122 result = (*searcher).template searchInternal<PlayerTraits<P>::opponent>
00123 (beta, alpha, ev, last_move, additional_depth);
00124 }
00125 };
00126 template <class QSearch2,Player P>
00127 struct QSearch2NextTakeBack : QSearch2HelperBase
00128 {
00129 typedef typename QSearch2::eval_t eval_t;
00130 QSearch2 *searcher;
00131 eval_t& ev;
00132 QSearch2NextTakeBack(int& r, QSearch2 *s, int a, int b, eval_t& e, Move l)
00133 : QSearch2HelperBase(r, a, b, l), searcher(s), ev(e)
00134 {
00135 }
00136 void operator()(Position)
00137 {
00138 ev.update(searcher->currentState(), last_move);
00139 result = (*searcher).template takeBackValue<PlayerTraits<P>::opponent>
00140 (beta, alpha, ev, last_move);
00141 }
00142 };
00143 template <class QSearch2,Player P>
00144 struct QSearch2TakeBackOrChase : QSearch2HelperBase
00145 {
00146 typedef typename QSearch2::eval_t eval_t;
00147 QSearch2 *searcher;
00148 eval_t& ev;
00149 QSearch2TakeBackOrChase(int& r, QSearch2 *s, int a, int b, eval_t& e, Move l)
00150 : QSearch2HelperBase(r, a, b, l), searcher(s), ev(e)
00151 {
00152 }
00153 void operator()(Position)
00154 {
00155 ev.update(searcher->currentState(), last_move);
00156 result = (*searcher).template takeBackOrChase<PlayerTraits<P>::opponent>
00157 (beta, alpha, ev, last_move);
00158 }
00159 };
00160 template <class Eval, Player P>
00161 struct QSearch2SafeEscape
00162 {
00163 const NumEffectState *state;
00164 Eval& eval;
00165 Piece target;
00166 bool has_safe_escape;
00167 bool is_invalid;
00168 Move last_move;
00169 QSearch2SafeEscape(const NumEffectState *s, Piece t, Eval& e, Move l)
00170 : state(s), eval(e), target(t), has_safe_escape(false), is_invalid(false), last_move(l)
00171 {
00172 }
00173 void operator()(Position)
00174 {
00175 const Player Turn = PlayerTraits<P>::opponent;
00176 assert(state->getTurn() == Turn);
00177 if (EffectUtil::isKingInCheck(alt(Turn), *state))
00178 {
00179 is_invalid = true;
00180 return;
00181 }
00182 eval.update(*state, last_move);
00183 MoveVector dummy;
00184 has_safe_escape
00185 = QuiescenceGenerator<Turn>::escapeByMoveOnly(*state, target, dummy);
00186 }
00187 };
00188 template <bool has_record>
00189 struct QSearch2Util
00190 {
00191 template <class TYPE>
00192 static bool isRecorded(QuiescenceRecord *record, TYPE type)
00193 {
00194 return has_record && record->cacheFlags().isGenerated(type);
00195 }
00196 static bool moreMoves(const QuiescenceRecord *record)
00197 {
00198 if (! has_record)
00199 return false;
00200 assert(record);
00201 return (record->moves_size() < QSearch2PrivateTraits::MinimumMoves);
00202 }
00203 };
00204 }
00205 }
00206
00207
00208 template <class EvalT>
00209 template <osl::Player P>
00210 int osl::search::QuiescenceSearch2<EvalT>::
00211 searchProbCut(int alpha, int beta, eval_t const& ev, Move last_move)
00212 {
00213 if (alpha != beta) {
00214 max_depth = QSearchTraits::MaxDepth/2;
00215 const int pawn_value2 = EvalT::captureValue(newPtypeO(alt(P),PAWN));
00216 const int margin = pawn_value2/2;
00217 const int alpha4 = EvalTraits<P>::max(alpha-margin,
00218 base_t::winThreshold(alt(P)));
00219 assert(EvalTraits<P>::notLessThan(alpha, alpha4));
00220 const int beta4 = EvalTraits<P>::min(beta +margin,
00221 base_t::winThreshold(P));
00222 assert(EvalTraits<P>::notLessThan(beta4, beta));
00223 const int val4 = searchInternal<P>(alpha4, beta4, ev, last_move);
00224 if (EvalTraits<P>::betterThan(val4, beta4))
00225 return val4 - (beta4-beta);
00226 if (EvalTraits<P>::betterThan(alpha4, val4))
00227 return val4 - (alpha4-alpha);
00228 }
00229 max_depth = QSearchTraits::MaxDepth;
00230 return searchInternal<P>(alpha, beta, ev, last_move);
00231 }
00232
00233 template <class EvalT>
00234 template <osl::Player P, osl::Ptype PTYPE>
00235 inline
00236 bool osl::search::QuiescenceSearch2<EvalT>::
00237 generateAndExamineTakeBack2(MoveVector& moves,
00238 QuiescenceThreat& threat2,
00239 QuiescenceThreat& threat1,
00240 int beta1, int beta2, eval_t const& ev)
00241 {
00242 const int first = PtypeTraits<PTYPE>::indexMin;
00243 const int last = PtypeTraits<PTYPE>::indexLimit;
00244 for (int num=first; num<last; ++num)
00245 {
00246 const Piece target = state.state().getPieceOf(num);
00247 if (! target.isOnBoardByOwner<PlayerTraits<P>::opponent>())
00248 continue;
00249
00250 assert(moves.empty());
00251 QuiescenceGenerator<P>::capture(currentState(), target.position(), moves);
00252 SortCaptureMoves::sortByMovingPiece(moves);
00253 const bool result
00254 = examineTakeBack2<P,false,true>(moves, threat2, threat1,
00255 beta1, beta2, ev);
00256 moves.clear();
00257 if (result)
00258 return result;
00259 }
00260 return false;
00261 }
00262
00263
00264 template <class EvalT>
00265 template <osl::Player P, osl::Ptype PTYPE, bool has_record>
00266 inline
00267 bool osl::search::QuiescenceSearch2<EvalT>::
00268 examineCapture(QuiescenceRecord *record,
00269 int& cur_val, MoveVector& moves, int& alpha, int beta,
00270 eval_t const& ev, Piece last_move_piece, int additional_depth)
00271 {
00272 assert(alpha % 2);
00273 assert(beta % 2);
00274
00275 if (! QSearch2Util<has_record>::isRecorded(record, PTYPE))
00276 {
00277 moves.clear();
00278 if (has_record)
00279
00280 QuiescenceGenerator<P>::template capture<PTYPE,false>(state.state(), moves, last_move_piece);
00281 else
00282 QuiescenceGenerator<P>::template capture<PTYPE,true>(state.state(), moves, last_move_piece);
00283
00284 SortCaptureMoves::sortByTakeBack(state.state(), moves);
00285
00286 recordGeneration<has_record>(record, PTYPE, moves);
00287 return examineMoves<P,has_record,has_record,CAPTURE>
00288 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
00289 additional_depth, last_move_piece.position());
00290 }
00291 return false;
00292 }
00293
00294 #ifdef STAT_WIDTH_VS_LIMIT
00295 namespace osl
00296 {
00297 namespace
00298 {
00299 struct Reporter
00300 {
00301 stat::Average average;
00302 int count;
00303 Reporter() : count(0) {}
00304 ~Reporter()
00305 {
00306 std::cerr << "QuiescenceSearch2 " << average.getAverage() << std::endl;
00307 }
00308 void newRoot() { average.add(count); count=0; }
00309 void add() { ++count; }
00310 } _reporter;
00311 }
00312 }
00313 #endif
00314
00315 template <class EvalT>
00316 template <osl::Player P, bool has_record, bool has_dont_capture,
00317 osl::search::QSearchTraits::MoveType move_type>
00318 bool osl::search::QuiescenceSearch2<EvalT>::
00319 examineMoves(QuiescenceRecord *record, int& cur_val,
00320 const Move *first, const Move *last,
00321 int& alpha, int beta, eval_t const& ev,
00322 int additional_depth, Position dont_capture)
00323 {
00324 assert(alpha % 2);
00325 assert(beta % 2);
00326
00327 assert(EvalTraits<P>::notLessThan(alpha, cur_val));
00328 #if (! defined NDEBUG) && (! defined OSL_SMP)
00329 const bool in_pv = (alpha != beta);
00330 #endif
00331 while (first != last)
00332 {
00333 const Move move = *first++;
00334 if (move_type == CHECK)
00335 {
00336 if (depth() <= 0
00337 && move.capturePtype() == PTYPE_EMPTY
00338 && ! isMajor(move.ptype()))
00339 continue;
00340 }
00341
00342 if (has_dont_capture)
00343 {
00344 const Position to = move.to();
00345 if (to == dont_capture)
00346 continue;
00347 }
00348 assert((move_type == KING_ESCAPE) || (move_type == UNKNOWN)
00349 || (! ShouldPromoteCut::canIgnoreAndNotDrop<P>(move)));
00350
00351 #ifdef QSEARCH_DEBUG
00352 QuiescenceLog::pushMove(depth(), move, record);
00353 #endif
00354 const HashKey new_hash = state.currentHash().newHashWithMove(move);
00355 int result;
00356
00357 const Sennichite next_sennichite
00358 = state.repetitionCounter().isAlmostSennichite(new_hash);
00359 if (next_sennichite.isDraw())
00360 {
00361 result = base_t::drawValue();
00362 }
00363 else if (next_sennichite.hasWinner())
00364 {
00365 result = base_t::winByFoul(next_sennichite.winner());
00366 }
00367 else
00368 {
00369 eval_t new_ev = ev;
00370 #ifdef STAT_WIDTH_VS_LIMIT
00371 if (depthFromRoot() == 0)
00372 _reporter.add();
00373 #endif
00374 assert(next_sennichite.isNormal());
00375 typedef QSearch2NextMove<QuiescenceSearch2,P> helper_t;
00376 if (has_record && alpha != beta
00377 && record->bestMove().isNormal()) {
00378
00379 helper_t helper(result, this, alpha, alpha, new_ev, move,
00380 additional_depth);
00381 state.doUndoMoveOrPass<P,helper_t>(new_hash, move, helper);
00382 if (EvalTraits<P>::betterThan(result, alpha)) {
00383 new_ev = ev;
00384 helper_t helper(result, this, alpha, beta, new_ev, move,
00385 additional_depth);
00386 state.doUndoMoveOrPass<P,helper_t>(new_hash, move, helper);
00387 }
00388 }
00389 else {
00390
00391 helper_t helper(result, this, alpha, beta, new_ev, move,
00392 additional_depth);
00393 state.doUndoMoveOrPass<P,helper_t>(new_hash, move, helper);
00394 }
00395
00396
00397 if (base_t::isWinValue(P, result) && (! move.isPass())
00398 && move_classifier::MoveAdaptor<move_classifier::PawnDropCheckmate<P> >
00399 ::isMember(state.state(), move))
00400 {
00401 result = base_t::winByFoul(alt(P));
00402 }
00403 }
00404 if (EvalTraits<P>::betterThan(result, cur_val))
00405 {
00406 cur_val = result;
00407 if (EvalTraits<P>::betterThan(result, alpha))
00408 {
00409 alpha = result + EvalTraits<P>::delta;
00410 if (has_record)
00411 {
00412 if (base_t::isWinValue(P, cur_val))
00413 {
00414 Position king = state.state().getKingPosition(alt(P));
00415 if (Ptype_Table.hasUnblockableEffect(move.ptypeO(), move.to(), king)) {
00416 record->setLowerBound(QSearchTraits::CheckmateSpecialDepth, cur_val, move);
00417 }
00418 else {
00419
00420 record->setLowerBound(QSearchTraits::MaxDepth, cur_val, move);
00421 }
00422 assert(EvalTraits<P>::notLessThan(result, beta));
00423 return true;
00424 }
00425 else
00426 {
00427 #ifndef OSL_SMP
00428 assert((record->lowerDepth() < depth())
00429 || EvalTraits<P>::notLessThan(cur_val, record->lowerBound())
00430 || in_pv
00431 || state.abort(move));
00432 #endif
00433 record->setLowerBound(depth(), cur_val, move);
00434 }
00435 }
00436 if (EvalTraits<P>::notLessThan(result, beta))
00437 {
00438 state.setKillerMove(move);
00439 return true;
00440 }
00441 }
00442 }
00443 }
00444 return false;
00445 }
00446
00447 namespace osl
00448 {
00449 namespace search
00450 {
00451 inline QuiescenceRecord *qallocate(SimpleHashTable& table,
00452 const HashKey& key,
00453 int minusDepthFromRoot,
00454 SearchState2Core& state)
00455 {
00456 assert(minusDepthFromRoot <= 0 || minusDepthFromRoot == allocate_depth_in_threatmate);
00457 SimpleHashRecord *record
00458 = table.allocate(key, minusDepthFromRoot);
00459 if (record) {
00460 state.setCurrentRecord(record);
00461 return &record->qrecord;
00462 }
00463 return 0;
00464 }
00465 }
00466 }
00467
00468 template <class EvalT>
00469 template <osl::Player P, bool has_record>
00470 inline
00471 int osl::search::QuiescenceSearch2<EvalT>::
00472 staticValue(eval_t const& ev, int alpha, int beta, QuiescenceRecord *record)
00473 {
00474 const bool in_pv = (alpha != beta);
00475 #ifndef DONT_USE_CHECKMATE
00476 if (! in_pv) {
00477 bool in_threatmate = has_record && record->threatmate.maybeThreatmate(P);
00478 if (! in_threatmate
00479 && (state.hasLastRecord(1) && state.lastRecord(1)))
00480 in_threatmate
00481 = (state.lastRecord(1)->threatmate().status(P).status() == ThreatmateState::CHECK_AFTER_THREATMATE);
00482 if (in_threatmate) {
00483 const int result = ev.value() + base_t::threatmatePenalty(P);
00484 return result;
00485 }
00486 }
00487 if (in_pv) {
00488 const Move last_move = state.lastMove();
00489 const Position king = state.state().getKingPosition(P);
00490 const bool one_hop_prook
00491 = (last_move.isNormal() && last_move.ptype() == PROOK
00492 && (last_move.capturePtype() == GOLD
00493 || last_move.capturePtype() == SILVER)
00494 && ((king.y() == last_move.to().y()
00495 && abs(king.x() - last_move.to().x()) < 3)
00496 || (king.x() == last_move.to().x()
00497 && abs(king.y() - last_move.to().y()) < 3)));
00498 if (one_hop_prook && ! has_record) {
00499 record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
00500 }
00501 if (has_record || record) {
00502
00503 Move checkmate_move=Move::INVALID();
00504 int threatmate_node = 0;
00505 if (record && record->threatmate.maybeThreatmate(P)) {
00506 threatmate_node += 50;
00507 } else if (one_hop_prook) {
00508 threatmate_node += 20;
00509 }
00510 #ifdef QSEARCH_THREATMATE
00511 else if ((depthFromRoot() < QSearch2PrivateTraits::ThreatMateDepthFromRoot)
00512 && state.tryThreatmate())
00513 threatmate_node += 20;
00514 #endif
00515 bool lose = state.isThreatmateState<P>
00516 (record->threatmateNodesLeft(threatmate_node),
00517 checkmate_move, record->threatmate_oracle);
00518 if (! lose && record->threatmateNodesLeft(2))
00519 lose = state.isThreatmateStateShort<P>(2, checkmate_move);
00520 if (lose)
00521 {
00522 const int result = ev.value() + base_t::threatmatePenalty(P);
00523 assert(checkmate_move.isValid());
00524 record->threatmate.setThreatmate(P, checkmate_move);
00525 record->setStaticValue(QuiescenceRecord::EXACT, result,
00526 QSearchTraits::CheckmateSpecialDepth);
00527 assert(result % 2 == 0);
00528 return result;
00529 }
00530 }
00531 }
00532 #endif
00533 if (! in_pv && has_record) {
00534 if (record->hasStaticValue()) {
00535
00536 if (EvalTraits<P>::betterThan(alpha, record->staticValue())) {
00537 assert(record->staticValue() % 2 == 0);
00538 return record->staticValue();
00539 }
00540 if (record->staticValueType() == QuiescenceRecord::EXACT
00541 && (record->staticValueDepth() >= depth())) {
00542 assert(record->staticValue() % 2 == 0);
00543 return record->staticValue();
00544 }
00545 }
00546 }
00547 Move threatmate_move;
00548 if (ImmediateCheckmate::hasCheckmateMove<PlayerTraits<P>::opponent>
00549 (state.state(), threatmate_move))
00550 {
00551 const int result = ev.value() + base_t::threatmatePenalty(P);
00552 if (has_record)
00553 {
00554 record->threatmate.setThreatmate(P, threatmate_move);
00555 record->setStaticValue(QuiescenceRecord::EXACT, result,
00556 QSearchTraits::CheckmateSpecialDepth);
00557 }
00558 assert(result % 2 == 0);
00559 return result;
00560 }
00561 const int eval_alpha = alpha;
00562 QuiescenceThreat threat1, threat2;
00563 const int result = staticValueWithThreat<P>(ev, eval_alpha, threat1, threat2);
00564 if (has_record)
00565 {
00566 record->setStaticValue(EvalTraits<P>::betterThan(eval_alpha, result)
00567 ? QuiescenceRecord::UPPER_BOUND
00568 : QuiescenceRecord::EXACT,
00569 result, depth(),
00570 threat1, threat2);
00571 }
00572 assert(result % 2 == 0);
00573 return result;
00574 }
00575
00576 template <class EvalT>
00577 template <osl::Player P>
00578 int osl::search::QuiescenceSearch2<EvalT>::
00579 searchInternal(int alpha, int beta, eval_t const& ev, Move last_move,
00580 int additional_depth)
00581 {
00582 #ifdef STAT_WIDTH_VS_LIMIT
00583 if (depthFromRoot() == 0)
00584 _reporter.newRoot();
00585 #endif
00586 #ifdef QSEARCH_DEBUG
00587 if (depthFromRoot() == 0)
00588 QuiescenceLog::enter(state.state());
00589 #endif
00590 #ifdef MAKE_PV_IN_QUIESCE2
00591 state.initPV();
00592 #endif
00593 ++node_count;
00594 assert(alpha % 2);
00595 assert(beta % 2);
00596 quiecence_assert(EvalTraits<P>::notLessThan(beta, alpha), last_move);
00597 assert(EvalTraits<P>::notLessThan(alpha, base_t::winThreshold(alt(P))));
00598 assert(EvalTraits<P>::notLessThan(base_t::winThreshold(P), beta));
00599 assert(last_move.player() == alt(P));
00600
00601
00602 if (EffectUtil::isKingInCheck(alt(P), state.state()))
00603 return base_t::winByFoul(P);
00604
00605 assert(state.hasLastRecord());
00606 QuiescenceRecord *record
00607 = qallocate(table, state.currentHash(), depth()-QSearchTraits::MaxDepth,
00608 state);
00609 const QuiescenceRecord *parent
00610 = (state.hasLastRecord(1) && state.lastRecord(1))
00611 ? &(state.lastRecord(1)->qrecord) : 0;
00612 const bool near_checkmate = parent
00613 && (parent->threatmate.maybeThreatmate(alt(P))
00614 || parent->threatmate.mayHaveCheckmate(P)
00615 || (parent->threatmate.status(P).status()
00616 == ThreatmateState::CHECK_AFTER_THREATMATE));
00617 if (! record && near_checkmate)
00618 {
00619 const int depth = (alpha != beta) ? allocate_depth_in_threatmate : 0;
00620 record
00621 = qallocate(table, state.currentHash(), depth, state);
00622 }
00623 int result;
00624 if (! record) {
00625 result = searchMain<P,false>(0, alpha, beta, ev, last_move,
00626 additional_depth);
00627 if (near_checkmate) {
00628 if ((EvalTraits<P>::betterThan(alpha, result)
00629 && parent->threatmate.maybeThreatmate(alt(P)))
00630 || (EvalTraits<P>::betterThan(result, alpha)
00631 && parent->threatmate.status(P).status()
00632 == ThreatmateState::CHECK_AFTER_THREATMATE)) {
00633 record
00634 = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
00635 }
00636 }
00637 }
00638 if (record)
00639 {
00640 #ifndef OSL_SMP
00641 assert((! record->isVisited()) || state.abort(Move::INVALID()));
00642 #endif
00643 record->setVisited();
00644 const bool is_king_in_check = EffectUtil::isKingInCheck(P, state.state());
00645 record->threatmate.update(P, (parent ? &(parent->threatmate) : 0),
00646 is_king_in_check);
00647 result = searchMain<P,true>(record, alpha, beta, ev, last_move,
00648 additional_depth);
00649 record->setVisited(false);
00650 #ifdef MAKE_PV_IN_QUIESCE2
00651 if ((alpha != beta) && EvalTraits<P>::betterThan(result, alpha))
00652 state.makePV(record->bestMove());
00653 #endif
00654 }
00655 #ifdef QSEARCH_DEBUG
00656 QuiescenceLog::node(depth(), alpha, beta, result);
00657 #endif
00658 assert(result % 2 == 0);
00659 return result;
00660 }
00661
00662 template <class EvalT>
00663 template <bool has_record, class MOVE_TYPE>
00664 void osl::search::QuiescenceSearch2<EvalT>::
00665 recordGeneration(QuiescenceRecord *record, MOVE_TYPE type,
00666 const MoveVector& moves)
00667 {
00668 if (has_record && state.curDepth() == 0)
00669 {
00670 record->addMoves(type, moves);
00671 }
00672 }
00673
00674 template <class EvalT>
00675 int osl::search::QuiescenceSearch2<EvalT>::
00676 currentValueWithLastThreat(eval_t const& ev, Piece last_move_piece)
00677 {
00678 int static_value = ev.value();
00679 if (! (depthFromRoot() < QSearch2PrivateTraits::EscapeFromLastMoveDepthFromRoot))
00680 return static_value;
00681
00682 assert(last_move_piece.isPiece());
00683 const Player P = last_move_piece.owner();
00684 PieceVector targets;
00685 const Position from = last_move_piece.position();
00686 EffectUtil::findThreat(state.state(), from, last_move_piece.ptypeO(),
00687 targets);
00688 if (targets.empty())
00689 return static_value;
00690 if (targets[0].ptype() == KING)
00691 {
00692 if (targets.size() < 2)
00693 return static_value;
00694
00695 int threat = eval_t::captureValue(targets[1].ptypeO());
00696 if (state.state().hasEffectBy(alt(P), targets[1].position()))
00697 threat += eval_t::captureValue(last_move_piece.ptypeO());
00698 assert(eval::betterThan(P, threat, 0));
00699 return static_value + threat;
00700 }
00701 int first_threat = eval_t::captureValue(targets[0].ptypeO());
00702 if (state.state().hasEffectBy(alt(P), targets[0].position()))
00703 first_threat += eval_t::captureValue(last_move_piece.ptypeO());
00704 assert(eval::betterThan(P, first_threat, 0));
00705 first_threat /= SecondThreat;
00706 if (targets.size() < 2)
00707 return static_value + (first_threat & (~0x1));
00708
00709 int second_threat = eval_t::captureValue(targets[1].ptypeO());
00710 if (state.state().hasEffectBy(alt(P), targets[1].position()))
00711 second_threat += eval_t::captureValue(last_move_piece.ptypeO());
00712 assert(eval::betterThan(P, second_threat, 0));
00713 return static_value + ((first_threat + second_threat) & (~0x1));
00714 }
00715
00716 template <class EvalT>
00717 template <osl::Player P>
00718 int osl::search::QuiescenceSearch2<EvalT>::
00719 passValue(int alpha, int beta, eval_t const& ev)
00720 {
00721
00722
00723 BOOST_STATIC_ASSERT(QSearch2PrivateTraits::EscapeDepthFromRoot <= 2);
00724 const Move pass = Move::PASS(P);
00725 int result;
00726 typedef QSearch2NextMove<QuiescenceSearch2,P> helper_t;
00727 helper_t helper(result, this, alpha, beta, ev, pass, 0);
00728 const HashKey new_hash = state.currentHash().newHashWithMove(pass);
00729
00730 max_depth -= QSearch2PrivateTraits::PassExtraDepth;
00731 state.doUndoMoveOrPass<P,helper_t>(new_hash, pass, helper);
00732 max_depth += QSearch2PrivateTraits::PassExtraDepth;
00733
00734 return result;
00735 }
00736
00737 template <class EvalT>
00738 template <osl::Player P, bool has_record>
00739 int osl::search::QuiescenceSearch2<EvalT>::
00740 searchMain(QuiescenceRecord *record,
00741 int alpha, int beta, eval_t const& ev, Move last_move,
00742 int additional_depth)
00743 {
00744 const bool in_pv = (alpha != beta);
00745 #ifndef NDEBUG
00746 static stat::Ratio ratio("QSearch2: cut");
00747 #endif
00748 assert((! has_record) || record);
00749 assert(alpha % 2);
00750 assert(beta % 2);
00751 assert((last_move == state.lastMove())
00752 || ! last_move.isNormal() || ! state.lastMove().isNormal());
00753
00754 state.depth_node_count_quiesce[state.curDepth()]++;
00755
00756 const int node_count_before = node_count;
00757 const Position last_to = last_move.to();
00758 int cur_val = base_t::winByCheckmate(alt(P));
00759 if (has_record)
00760 {
00761 if ((! in_pv && record->lowerDepth() >= depth())
00762 || record->lowerDepth() >= QSearchTraits::HistorySpecialDepth)
00763 {
00764 if (EvalTraits<P>::notLessThan(record->lowerBound(), cur_val))
00765 {
00766 cur_val = record->lowerBound();
00767 if (EvalTraits<P>::betterThan(record->lowerBound(), alpha))
00768 {
00769 alpha = record->lowerBound() + EvalTraits<P>::delta;
00770 if (EvalTraits<P>::betterThan(record->lowerBound(), beta))
00771 {
00772 #ifndef NDEBUG
00773 ratio.add(true);
00774 #endif
00775 return record->lowerBound();
00776 }
00777 }
00778 }
00779 }
00780 #ifndef DONT_USE_CHECKMATE
00781 assert(record);
00782
00783 if (in_pv) {
00784 Move checkmate_move=Move::INVALID();
00785 bool win = state.isWinningState<P>
00786 (0, checkmate_move, record->attack_oracle);
00787 if (! win && record->threatmate.mayHaveCheckmate(alt(P))) {
00788 win = state.isWinningStateShort<P>(2, checkmate_move);
00789 }
00790 if (win) {
00791 const int result = base_t::winByCheckmate(P);
00792 assert(checkmate_move.isValid());
00793 assert(state.state().isValidMove(checkmate_move));
00794 record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
00795 result, checkmate_move);
00796 return result;
00797 }
00798 }
00799 #endif
00800 if ((! in_pv && record->upperDepth() >= depth())
00801 || record->upperDepth() >= QSearchTraits::HistorySpecialDepth)
00802 {
00803 if (EvalTraits<P>::betterThan(beta, record->upperBound()))
00804 {
00805 beta = record->upperBound() - EvalTraits<P>::delta;
00806 if (EvalTraits<P>::betterThan(alpha, record->upperBound()))
00807 {
00808 #ifndef NDEBUG
00809 ratio.add(true);
00810 #endif
00811 return record->upperBound();
00812 }
00813 }
00814 }
00815 #ifndef NDEBUG
00816 ratio.add(false);
00817 #endif
00818 }
00819 const bool is_king_in_check = EffectUtil::isKingInCheck(P, state.state());
00820 MoveVector moves;
00821 if (is_king_in_check)
00822 {
00823 if (last_move.isNormal() && last_move.capturePtype() != PTYPE_EMPTY
00824 && unpromote(last_move.capturePtype()) == ROOK
00825 && unpromote(last_move.ptype()) != ROOK)
00826 ++additional_depth;
00827 else
00828
00829 if (state.lastMove(2).isNormal()
00830 && state.lastMove(3).isNormal()
00831 && state.lastMove(4).isNormal()
00832 && state.lastMove(2).to() == last_move.to()
00833 && state.lastMove(3).to() == last_move.to()
00834 && state.lastMove(4).to() == last_move.to())
00835 ++additional_depth;
00836
00837 if (QSearch2Util<has_record>::isRecorded
00838 (record, QuiescenceFlags::KING_ESCAPE))
00839 {
00840 MoveVector record_moves;
00841 record->loadMoves(record_moves);
00842 examineMoves<P,has_record,false,KING_ESCAPE>
00843 (record, cur_val, &*record_moves.begin(),&*record_moves.end(),
00844 alpha, beta, ev, additional_depth);
00845 }
00846 else
00847 {
00848 QuiescenceGenerator<P>::escapeKing(state.state(), moves);
00849
00850 move_order::CaptureSort::sort(moves.begin(), moves.end());
00851 recordGeneration<has_record,QuiescenceFlags::Flags>
00852 (record, QuiescenceFlags::KING_ESCAPE, moves);
00853 examineMoves<P,has_record,false,KING_ESCAPE>
00854 (record, cur_val, &*moves.begin(), &*moves.end(),alpha, beta, ev,
00855 additional_depth);
00856 }
00857 if (has_record)
00858 {
00859 if (EvalTraits<P>::betterThan(beta, cur_val))
00860 record->setUpperBound(depth(), cur_val);
00861 }
00862 return cur_val;
00863 }
00864 assert(! is_king_in_check);
00865 King8Info king_info(0);
00866 PieceMask pins = ev.pins(alt(P));
00867 if (has_record)
00868 king_info = record->king8Info(state.state(), pins);
00869 else
00870 king_info = King8Info::makeWithPin(P, state.state(), pins);
00871 Move checkmate_move=Move::INVALID();
00872 Position kingPosition=state.state().template getKingPosition<PlayerTraits<P>::opponent>();
00873 if ((depth() <= 4)
00874 ? ImmediateCheckmate::hasCheckmateMove<P>(state.state(), king_info,kingPosition,checkmate_move)
00875 : state.isWinningStateShort<P>(2, checkmate_move)) {
00876 const int result = base_t::winByCheckmate(P);
00877 assert(checkmate_move.isValid());
00878 if(has_record)
00879 {
00880 assert(state.state().isValidMove(checkmate_move));
00881 record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
00882 result, checkmate_move);
00883 }
00884 return result;
00885 }
00886
00887 if (depth() <= 0 && has_record) {
00888 if (record->threatmate.maybeThreatmate(P))
00889 return ev.value() + base_t::threatmatePenalty(P);
00890 if (record->threatmate.mayHaveCheckmate(alt(P)))
00891 return ev.value() + base_t::threatmatePenalty(alt(P));
00892 }
00893
00894 const Ptype last_capture = last_move.isNormal()
00895 ? last_move.capturePtype() : PTYPE_EMPTY;
00896 const Ptype last_ptype = last_move.isNormal()
00897 ? last_move.ptype() : PTYPE_EMPTY;
00898 const bool king_escape = (last_ptype == KING) && last_capture == PTYPE_EMPTY;
00899
00900 if ((depth() + std::min(additional_depth,2) <= -2)
00901 || (depth() <= 0 && additional_depth == 0)
00902 || (! king_escape
00903 && ((depth() + additional_depth <= 0)
00904 || (depth() <= 0 && last_capture != PTYPE_EMPTY
00905 && last_ptype != KING))))
00906 {
00907 if (ev.progress16().value() == 15
00908 && state.tryThreatmate()
00909 && ImmediateCheckmate::hasCheckmateMove<PlayerTraits<P>::opponent>(state.state()))
00910 return ev.value() + base_t::threatmatePenalty(P);
00911 const int base = takeBackValue<P>(alpha, beta, ev, last_move);
00912 #ifdef QSEARCH_LAST_CHECK_PENALTY
00913 if ((last_move.ptype() == KING)
00914 && (last_capture == PTYPE_EMPTY))
00915 {
00916
00917
00918 return base+eval_t::captureValue(newPtypeO(alt(P), KNIGHT));
00919 }
00920 #endif
00921 return base;
00922 }
00923
00924 const int static_value
00925 = ((depth() <= 0)
00926 ? takeBackValue<P>(alpha, beta, ev, last_move)
00927 #ifdef QSEARCH_REAL_PASS
00928 : ((depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot)
00929 && (! last_move.isPass()))
00930 ? passValue<P>(alpha, beta, ev)
00931 #endif
00932 : staticValue<P,has_record>(ev, alpha, beta, record));
00933 assert(static_value % 2 == 0);
00934 assert(! isWinValue(alt(P), static_value));
00935 #ifdef QSEARCH_DEBUG
00936 QuiescenceLog::staticValue(depth(), static_value);
00937 #endif
00938 if (EvalTraits<P>::notLessThan(static_value, cur_val))
00939 {
00940 cur_val = static_value;
00941 if (EvalTraits<P>::betterThan(cur_val, alpha))
00942 {
00943 alpha = cur_val + EvalTraits<P>::delta;
00944 if (has_record)
00945 {
00946 #ifndef OSL_SMP
00947 assert((record->lowerDepth() < depth())
00948 || EvalTraits<P>::notLessThan(cur_val, record->lowerBound())
00949 || in_pv);
00950 #endif
00951 record->setLowerBound(depth(), cur_val, record->bestMove());
00952 }
00953 if (EvalTraits<P>::betterThan(cur_val, beta))
00954 return cur_val;
00955 }
00956 }
00957
00958
00959 assert(alpha == EvalTraits<P>::max(alpha, cur_val + EvalTraits<P>::delta));
00960 assert(EvalTraits<P>::notLessThan(beta, alpha));
00961
00962 Piece last_capture_piece = Piece::EMPTY();
00963 if (! has_record)
00964 {
00965 state.getBigramKillerMoves(moves);
00966 if (examineMoves<P,has_record,false,UNKNOWN>
00967 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
00968 additional_depth))
00969 return cur_val;
00970 moves.clear();
00971 }
00972 else
00973 {
00974
00975
00976 const Move bestmove_in_record=record->bestMove();
00977 if (bestmove_in_record.isNormal())
00978 {
00979 assert(state.state().template isAlmostValidMove<false>(record->bestMove()));
00980 assert(moves.empty());
00981 moves.push_back(bestmove_in_record);
00982 if (examineMoves<P,has_record,false,UNKNOWN>
00983 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
00984 additional_depth))
00985 return cur_val;
00986 moves.clear();
00987 last_capture_piece = state.state().getPieceOnBoard(bestmove_in_record.to());
00988 }
00989
00990 MoveVector killer_moves;
00991 state.getBigramKillerMoves(killer_moves);
00992 assert(moves.empty());
00993 MoveVector record_moves;
00994 record->loadMoves(record_moves);
00995 for (MoveVector::const_iterator p=killer_moves.begin();
00996 p!=killer_moves.end(); ++p)
00997 {
00998 if (std::find(record_moves.begin(), record_moves.end(), *p)
00999 == record_moves.end())
01000 moves.push_back(*p);
01001 }
01002 record->addKillerMoves(moves);
01003
01004 if (examineMoves<P,has_record,false,UNKNOWN>
01005 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
01006 additional_depth))
01007 return cur_val;
01008
01009 if (examineMoves<P,has_record,false,UNKNOWN>
01010 (record, cur_val, &*record_moves.begin(), &*record_moves.end(), alpha, beta, ev, additional_depth))
01011 return cur_val;
01012 moves.clear();
01013 }
01014
01015
01016 assert(moves.empty());
01017 if (((! has_record) || record->moves_size()==0)
01018 && (! last_to.isPieceStand()))
01019 {
01020 last_capture_piece = state.state().getPieceOnBoard(last_to);
01021 QuiescenceGenerator<P>::capture(state.state(),
01022 last_capture_piece.position(), moves);
01023 if (examineMoves<P,has_record,false,CAPTURE>
01024 (record, cur_val, &*moves.begin(), &*moves.end(),alpha, beta, ev,
01025 additional_depth))
01026 {
01027 if (has_record)
01028 {
01029
01030 record->addKillerMoves(moves);
01031 }
01032 return cur_val;
01033 }
01034 }
01035
01036
01037 const bool has_threatmate
01038 = has_record
01039 && record->threatmate.isThreatmate(P)
01040 && (! QSearch2Util<has_record>::
01041 isRecorded(record, QuiescenceFlags::BREAK_THREATMATE));
01042 if (has_threatmate)
01043 {
01044 moves.clear();
01045 QuiescenceGenerator<P>::breakThreatmate
01046 (state.state(), record->threatmate.threatmateMove(P), pins, moves);
01047 recordGeneration<has_record>(record, QuiescenceFlags::BREAK_THREATMATE,
01048 moves);
01049 if (examineMoves<P,has_record,false,KING_ESCAPE>
01050 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
01051 additional_depth))
01052 return cur_val;
01053 }
01054
01055
01056 if (examineCapture<P,ROOK,has_record>
01057 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01058 return cur_val;
01059 if (examineCapture<P,BISHOP,has_record>
01060 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01061 return cur_val;
01062 if (examineCapture<P,GOLD,has_record>
01063 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01064 return cur_val;
01065 if (examineCapture<P,SILVER,has_record>
01066 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01067 return cur_val;
01068 if ((depth() >= QSearch2PrivateTraits::KnightCaptureDepth)
01069 || max_depth <= 2
01070 || QSearch2Util<has_record>::moreMoves(record))
01071 {
01072 if (examineCapture<P,KNIGHT,has_record>
01073 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01074 return cur_val;
01075 if (examineCapture<P,LANCE,has_record>
01076 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01077 return cur_val;
01078 }
01079
01080
01081 const Move last2_move = state.lastMove(2);
01082 if ((depth() > 2
01083 || (depth() > 0 && !(has_record && record->threatmate.maybeThreatmate(P)))
01084 || (last2_move.isNormal() && last2_move.capturePtype() == ROOK))
01085 && ! (! in_pv && has_record && record->threatmate.maybeThreatmate(P))
01086 && ! QSearch2Util<has_record>::isRecorded(record, QuiescenceFlags::CHECK))
01087 {
01088 moves.clear();
01089
01090 if (has_record)
01091 QuiescenceGenerator<P>::check(state.state(), pins,
01092 (king_info.liberty() == 0),
01093 record->sendOffPosition<P>(state.state()),
01094 moves);
01095 else
01096 QuiescenceGenerator<P>::check(state.state(), pins, moves,
01097 (king_info.liberty() == 0));
01098 recordGeneration<has_record>(record, QuiescenceFlags::CHECK, moves);
01099 if (examineMoves<P,has_record,false,CHECK>
01100 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
01101 additional_depth))
01102 return cur_val;
01103 }
01104
01105 const Position my_king = state.state().template getKingPosition<P>();
01106
01107 if (depth() <= 0)
01108 goto finish;
01109
01110 if ((depth() >= QSearch2PrivateTraits::AttackPinnedDepth)
01111 || QSearch2Util<has_record>::moreMoves(record))
01112 {
01113 if (! QSearch2Util<has_record>::isRecorded
01114 (record, QuiescenceFlags::PINNED_ATTACK))
01115 {
01116 moves.clear();
01117 QuiescenceGenerator<P>::attackToPinned(state.state(), pins, moves);
01118 recordGeneration<has_record>(record, QuiescenceFlags::PINNED_ATTACK, moves);
01119 if (examineMoves<P,has_record,false,ATTACK>
01120 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
01121 additional_depth))
01122 return cur_val;
01123 }
01124 }
01125
01126 if ((depthFromRoot() < QSearch2PrivateTraits::DropDepthFromRoot)
01127 || (isMajorBasic(last2_move.capturePtype())
01128 && ((depthFromRoot() < QSearch2PrivateTraits::DropDepthFromRoot+2)
01129 || (has_record && record->moves_size() < 4)
01130 ))
01131 || QSearch2Util<has_record>::moreMoves(record))
01132 {
01133 if (! QSearch2Util<has_record>::isRecorded(record, QuiescenceFlags::DROP))
01134 {
01135 moves.clear();
01136 QuiescenceGenerator<P>::dropMajorPiece(state.state(), moves);
01137 if (last_move.isNormal() && isPiece(last_move.capturePtype())
01138 && unpromote(last_move.capturePtype())== BISHOP
01139 && last2_move.isNormal() && last2_move.capturePtype() == BISHOP
01140 && unpromote(last2_move.ptype()) == BISHOP)
01141 {
01142 const Position drop_again = last2_move.from();
01143 if (! state.state().template hasEffectBy<PlayerTraits<P>::opponent>(drop_again)
01144
01145 && state.state().getPieceOnBoard(drop_again) == Piece::EMPTY()
01146 && state.state().template hasPieceOnStand<P,BISHOP>())
01147 moves.push_back(Move(drop_again, BISHOP, P));
01148 }
01149
01150 recordGeneration<has_record>(record, QuiescenceFlags::DROP, moves);
01151 if (examineMoves<P,has_record,true,OTHER>
01152 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
01153 additional_depth))
01154 return cur_val;
01155 }
01156 }
01157 if ((depth() >= QSearch2PrivateTraits::PawnCaptureDepth)
01158 || max_depth <= 2
01159 || QSearch2Util<has_record>::moreMoves(record))
01160 {
01161 if (examineCapture<P,PAWN,has_record>
01162 (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
01163 return cur_val;
01164 }
01165 if (! QSearch2Util<has_record>::isRecorded(record, QuiescenceFlags::PROMOTE))
01166 {
01167 moves.clear();
01168 QuiescenceGenerator<P>::promote(state.state(), pins, moves);
01169 recordGeneration<has_record>(record, QuiescenceFlags::PROMOTE, moves);
01170 if (examineMoves<P,has_record,false,PROMOTE>
01171 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01172 return cur_val;
01173 }
01174 if (depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot)
01175 {
01176 if (! QSearch2Util<has_record>::isRecorded
01177 (record, QuiescenceFlags::ALL_ESCAPE))
01178 {
01179 moves.clear();
01180 QuiescenceGenerator<P>::escapeAll(state.state(), moves);
01181 recordGeneration<has_record>(record, QuiescenceFlags::ALL_ESCAPE, moves);
01182 if (examineMoves<P,has_record,false,ESCAPE>
01183 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01184 return cur_val;
01185 }
01186 }
01187 else if ((depthFromRoot() < QSearch2PrivateTraits::EscapeFromLastMoveDepthFromRoot)
01188 || (last_move.isDrop() && isMajorBasic(last_move.ptype()))
01189 || (last_move.isNormal() && last2_move.isNormal()
01190 && isMajor(last2_move.ptype())
01191 && state.state().hasEffectByPiece
01192 (state.state().getPieceOnBoard(last_to), last2_move.to()))
01193 || QSearch2Util<has_record>::moreMoves(record))
01194 {
01195 if (! QSearch2Util<has_record>::isRecorded
01196 (record, QuiescenceFlags::ESCAPE_FROM_LAST_MOVE))
01197 {
01198 moves.clear();
01199 QuiescenceGenerator<P>::escapeFromLastMove(state.state(), last_move, moves);
01200 recordGeneration<has_record>(record, QuiescenceFlags::ESCAPE_FROM_LAST_MOVE, moves);
01201 if (examineMoves<P,has_record,false,ESCAPE>
01202 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01203 return cur_val;
01204 }
01205 }
01206 if ((depthFromRoot() < QSearch2PrivateTraits::AttackMajorPieceDepthFromRoot)
01207 || (isMajor(last_move.ptype())
01208 && last_move.capturePtype() != PTYPE_EMPTY
01209 && last_to.template canPromote<P>())
01210 || (state.state().hasEffectBy(P, last_to)
01211 && (state.state().
01212 template hasEffectByPtype<ROOK>(alt(P), last_to)))
01213 || ((depthFromRoot() < QSearch2PrivateTraits::AttackMajorPieceDepthFromRoot+2)
01214 && ((last2_move.capturePtype()==KNIGHT)
01215 || (last2_move.capturePtype()==LANCE)
01216 || (last2_move.capturePtype()==BISHOP)))
01217 || QSearch2Util<has_record>::moreMoves(record))
01218 {
01219 if (! QSearch2Util<has_record>::isRecorded
01220 (record, QuiescenceFlags::MAJOR_PIECE_ATTACK))
01221 {
01222 moves.clear();
01223 QuiescenceGenerator<P>::attackMajorPiece(state.state(), pins, moves);
01224 recordGeneration<has_record>(record, QuiescenceFlags::MAJOR_PIECE_ATTACK,
01225 moves);
01226 if (examineMoves<P,has_record,true,ATTACK>
01227 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01228 return cur_val;
01229 }
01230 }
01231 {
01232 const QuiescenceRecord *parent
01233 = (state.hasLastRecord(1) && state.lastRecord(1))
01234 ? &(state.lastRecord(1)->qrecord) : 0;
01235 if ((depthFromRoot() < QSearch2PrivateTraits::AttackKing8DepthFromRoot)
01236 || (last_move.isNormal() && last_move.ptype() == KING
01237 && last_move.capturePtype() != PTYPE_EMPTY)
01238 || (((parent && parent->threatmate.isThreatmate(alt(P)))
01239 || (king_info.liberty() == 0))
01240 && depthFromRoot() < 2+QSearch2PrivateTraits::AttackKing8DepthFromRoot)
01241 || QSearch2Util<has_record>::moreMoves(record))
01242 {
01243 if (! QSearch2Util<has_record>::isRecorded
01244 (record, QuiescenceFlags::KING8_ATTACK))
01245 {
01246 moves.clear();
01247 QuiescenceGenerator<P>::attackKing8(state.state(), pins, moves);
01248 recordGeneration<has_record>(record, QuiescenceFlags::KING8_ATTACK, moves);
01249 if (examineMoves<P,has_record,false,ATTACK>
01250 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01251 return cur_val;
01252 }
01253 }
01254 }
01255 if ((depthFromRoot() < QSearch2PrivateTraits::AttackGoldSilverDepthFromRoot)
01256 || QSearch2Util<has_record>::moreMoves(record))
01257 {
01258 if (! QSearch2Util<has_record>::isRecorded
01259 (record, QuiescenceFlags::GOLDSILVER_ATTACK))
01260 {
01261 moves.clear();
01262 QuiescenceGenerator<P>::attackGoldWithPawn(state.state(), pins, moves);
01263 QuiescenceGenerator<P>::attackSilverWithPawn(state.state(), pins, moves);
01264 recordGeneration<has_record>(record, QuiescenceFlags::GOLDSILVER_ATTACK, moves);
01265 if (examineMoves<P,has_record,false,ATTACK>
01266 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01267 return cur_val;
01268 }
01269 }
01270 if ((depthFromRoot() < QSearch2PrivateTraits::AttackKnightDepthFromRoot)
01271 || QSearch2Util<has_record>::moreMoves(record))
01272 {
01273 if (! QSearch2Util<has_record>::isRecorded
01274 (record, QuiescenceFlags::KNIGHT_ATTACK))
01275 {
01276 moves.clear();
01277 QuiescenceGenerator<P>::attackKnightWithPawn(state.state(), pins, moves);
01278 recordGeneration<has_record>(record, QuiescenceFlags::KNIGHT_ATTACK, moves);
01279 if (examineMoves<P,has_record,false,ATTACK>
01280 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01281 return cur_val;
01282 }
01283 }
01284 if ((depth() >= QSearch2PrivateTraits::UtilizePromotedDepth)
01285 || QSearch2Util<has_record>::moreMoves(record))
01286 {
01287 if (! QSearch2Util<has_record>::isRecorded
01288 (record, QuiescenceFlags::UTILIZE_PROMOTED)
01289 && last2_move.isNormal())
01290 {
01291 const Piece last_piece = state.state().getPieceOnBoard(last2_move.to());
01292 assert(last_piece.isPiece());
01293 if (last_piece.owner() == P)
01294 {
01295 moves.clear();
01296 QuiescenceGenerator<P>::utilizePromoted(state.state(), last_piece, moves);
01297 recordGeneration<has_record>(record, QuiescenceFlags::UTILIZE_PROMOTED, moves);
01298 if (examineMoves<P,has_record,true,OTHER>
01299 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01300 return cur_val;
01301 }
01302 }
01303 }
01304
01305 if ((depthFromRoot() < QSearch2PrivateTraits::AdvanceBishopDepthFromRoot)
01306 || QSearch2Util<has_record>::moreMoves(record))
01307 {
01308 if (! QSearch2Util<has_record>::isRecorded
01309 (record, QuiescenceFlags::ADVANCE_BISHOP))
01310 {
01311 moves.clear();
01312 QuiescenceGenerator<P>::advanceBishop(state.state(), moves);
01313 recordGeneration<has_record>(record, QuiescenceFlags::ADVANCE_BISHOP, moves);
01314 if (examineMoves<P,has_record,true,OTHER>
01315 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01316 return cur_val;
01317 }
01318 }
01319
01320 if (has_threatmate
01321 || (! my_king.template canPromote<PlayerTraits<P>::opponent>()
01322 && last2_move.isNormal() && last2_move.ptype() == KING))
01323 {
01324 if (! QSearch2Util<has_record>::isRecorded
01325 (record, QuiescenceFlags::KING_WALK))
01326 {
01327 moves.clear();
01328 QuiescenceGenerator<P>::kingWalk(state.state(), moves);
01329 recordGeneration<has_record>(record, QuiescenceFlags::KING_WALK, moves);
01330 if (examineMoves<P,has_record,true,OTHER>
01331 (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
01332 return cur_val;
01333 }
01334 }
01335 finish:
01336
01337 assert(EvalTraits<P>::betterThan(beta, cur_val));
01338 assert(! isWinValue(alt(P), cur_val));
01339 #ifndef DONT_USE_CHECKMATE
01340 const bool threatmate
01341 = EvalTraits<P>::betterThan(ev.captureValue(newPtypeO(P,KING)), cur_val);
01342 int check_after_threatmate = 0;
01343 if (in_pv
01344 && (threatmate
01345 || (check_after_threatmate = state.countCheckAfterThreatmate(alt(P),2))))
01346 {
01347
01348 int checkmate_nodes = (node_count - node_count_before)/2;
01349 if (check_after_threatmate)
01350 {
01351 if (depthFromRoot() == 1)
01352 {
01353 const int sacrifice = state.countCheckAfterThreatmateSacrifice(alt(P),2);
01354 checkmate_nodes = std::max(checkmate_nodes,
01355 sacrifice*125+check_after_threatmate*50);
01356 }
01357 else
01358 {
01359 checkmate_nodes = std::max(50, checkmate_nodes);
01360 }
01361 }
01362 if (threatmate)
01363 {
01364 if (! has_record)
01365 record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
01366 checkmate_nodes = std::max(checkmate_nodes, 200);
01367 }
01368 Move check_move;
01369 const bool win = (record && checkmate_nodes >= 50)
01370 ? state.isWinningState<P>(record->checkmateNodesLeft(checkmate_nodes),
01371 checkmate_move, record->attack_oracle)
01372 : (((record && record->checkmateNodesLeft(2))
01373 || (! has_record && threatmate))
01374 ? state.isWinningStateShort<P>(2, checkmate_move)
01375 : false);
01376 if (win)
01377 {
01378 const int result = base_t::winByCheckmate(P);
01379 assert(checkmate_move.isValid());
01380 if (! has_record && ! record)
01381 record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
01382 if (has_record || record) {
01383 assert(state.state().isValidMove(checkmate_move));
01384 record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
01385 result, checkmate_move);
01386 }
01387 return result;
01388 }
01389 }
01390 #if 0
01391
01392
01393 if (! has_record)
01394 {
01395 assert(! record);
01396 Move checkmate_move=Move::INVALID();
01397 AttackOracleAges oracle_age_dummy;
01398 const bool win_found
01399 = state.isWinningState<P>
01400 (0, checkmate_move, oracle_age_dummy);
01401 if (win_found)
01402 {
01403 const int result = base_t::winByCheckmate(P);
01404 assert(checkmate_move.isValid());
01405 record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
01406 if (record)
01407 {
01408 #ifndef OSL_SMP
01409 assert(! record->isVisited());
01410 #endif
01411 record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
01412 result, checkmate_move);
01413 }
01414 return result;
01415 }
01416 }
01417 #endif
01418 #endif
01419
01420 if (has_record)
01421 {
01422 if (EvalTraits<P>::betterThan(beta, cur_val))
01423 record->setUpperBound(depth(), cur_val);
01424 }
01425 return cur_val;
01426 }
01427
01428 namespace osl
01429 {
01430 inline bool importantMove(const NumEffectState& state, Move move,
01431 Position my_king, Position op_king)
01432 {
01433 if (Neighboring8Direct::hasEffect(state, move.ptypeO(), move.to(), op_king))
01434 return true;
01435 return move.capturePtype() != PTYPE_EMPTY
01436 && Neighboring8Direct::hasEffect(state, move.capturePtypeO(), move.to(), my_king);
01437 }
01438 }
01439
01440 template <class EvalT>
01441 template <osl::Player P>
01442 bool osl::search::QuiescenceSearch2<EvalT>::
01443 examineTakeBack(const MoveVector& moves,
01444 int& cur_val, int& alpha, int beta, eval_t const& ev)
01445 {
01446 assert(alpha % 2);
01447 assert(beta % 2);
01448 assert(EvalTraits<P>::betterThan(alpha, cur_val));
01449 assert(EvalTraits<P>::notLessThan(beta, alpha));
01450
01451 const Position my_king = state.state().template getKingPosition<P>();
01452 const Position op_king = state.state().template getKingPosition<PlayerTraits<P>::opponent>();
01453
01454 for (MoveVector::const_iterator p=moves.begin(); p!=moves.end(); ++p)
01455 {
01456 #ifdef QSEARCH_DEBUG
01457 QuiescenceLog::pushMove(depth(), *p, 0);
01458 #endif
01459 const int see = See::see(state.state(), *p, ev.pins(P), ev.pins(alt(P)));
01460 int result;
01461 if (see > 0 && importantMove(state.state(), *p, my_king, op_king))
01462 {
01463 eval_t new_ev = ev;
01464
01465 typedef QSearch2NextTakeBack<QuiescenceSearch2,P> helper_t;
01466 helper_t helper(result, this, alpha, beta, new_ev, *p);
01467
01468 state.doUndoMoveLight<P,helper_t>(*p, helper);
01469 }
01470 else
01471 {
01472 result = ev.value() + see*eval_t::seeScale()*EvalTraits<P>::delta;
01473 }
01474
01475 if (! base_t::isWinValue(alt(P), result))
01476 {
01477 cur_val = EvalTraits<P>::max(cur_val, result);
01478 return EvalTraits<P>::notLessThan(result, beta);
01479 }
01480 }
01481 assert(EvalTraits<P>::betterThan(beta, cur_val));
01482 return false;
01483 }
01484
01485 template <class EvalT>
01486 template <osl::Player P, bool calm_move_only, bool first_normal_move_only>
01487 bool osl::search::QuiescenceSearch2<EvalT>::
01488 examineTakeBack2(const MoveVector& moves,
01489 QuiescenceThreat& threat2, QuiescenceThreat& threat1,
01490 int beta1, int beta2, eval_t const& ev)
01491 {
01492 if (moves.empty())
01493 return false;
01494
01495 using move_classifier::Check;
01496 using move_classifier::MoveAdaptor;
01497 assert(beta1 % 2);
01498 assert(beta2 % 2);
01499 assert(EvalTraits<P>::notLessThan(threat1.value, threat2.value));
01500 assert(EvalTraits<P>::betterThan(beta1, threat1.value));
01501 assert(EvalTraits<P>::betterThan(beta2, threat2.value));
01502 assert(EvalTraits<P>::notLessThan(beta1, beta2));
01503 assert(state.state().getTurn() == P);
01504
01505 const Position my_king = state.state().template getKingPosition<P>();
01506 const Position op_king = state.state().template getKingPosition<PlayerTraits<P>::opponent>();
01507
01508 int best_value = threat2.value;
01509 for (MoveVector::const_iterator p=moves.begin(); p!=moves.end(); ++p)
01510 {
01511 const Position to = p->to();
01512 assert(! ShouldPromoteCut::canIgnoreAndNotDrop<P>(*p));
01513 if (calm_move_only
01514 && (state.state().countEffect(alt(P),to) > state.state().countEffect(P,to)))
01515 continue;
01516 #ifdef QSEARCH_DEBUG
01517 QuiescenceLog::pushMove(depth(), *p, 0);
01518 #endif
01519 int result;
01520 const int see = See::see(state.state(), *p, ev.pins(P), ev.pins(alt(P)));
01521 if (see > 0 && importantMove(state.state(), *p, my_king, op_king))
01522 {
01523 eval_t new_ev = ev;
01524
01525 const int beta = EvalTraits<P>::notLessThan(threat1.value, beta2) ? beta2 : beta1;
01526 typedef QSearch2NextTakeBack<QuiescenceSearch2,P> helper_t;
01527 helper_t helper(result, this,
01528 threat2.value+EvalTraits<P>::delta, beta, new_ev, *p);
01529 state.doUndoMoveLight<P,helper_t>(*p, helper);
01530 }
01531 else
01532 {
01533 result = ev.value() + see*eval_t::seeScale()*EvalTraits<P>::delta;
01534 }
01535
01536 if (base_t::isWinValue(alt(P), result))
01537 continue;
01538
01539
01540 if (EvalTraits<P>::betterThan(result, best_value))
01541 {
01542 best_value = result;
01543 if (EvalTraits<P>::notLessThan(best_value, threat1.value))
01544 {
01545 threat2 = threat1;
01546 threat1 = QuiescenceThreat(best_value, *p);
01547 if (EvalTraits<P>::betterThan(threat1.value, beta1)
01548 || EvalTraits<P>::betterThan(threat2.value, beta2))
01549 return true;
01550 }
01551 else
01552 {
01553 assert(EvalTraits<P>::notLessThan(best_value, threat2.value));
01554 threat2 = QuiescenceThreat(best_value, *p);
01555 if (EvalTraits<P>::betterThan(threat2.value, beta2))
01556 return true;
01557 }
01558 }
01559 if (first_normal_move_only)
01560 break;
01561 }
01562
01563
01564
01565 assert(! moves.empty());
01566 if (! EvalTraits<P>::betterThan(best_value, threat2.value))
01567 return false;
01568 const Move threat_move = *moves.begin();
01569 if (! first_normal_move_only)
01570 {
01571 assert(state.lastMove().isPass());
01572 state.popPass();
01573 bool cut_by_threat2 = false;
01574
01575 const Player Opponent = PlayerTraits<P>::opponent;
01576 MoveVector moves;
01577 move_action::Store store(moves);
01578 move_generator::GenerateAddEffect<false>::generate<NumEffectState>
01579 (Opponent, state.state(), threat_move.to(), store);
01580 if (moves.empty())
01581 {
01582 threat2 = QuiescenceThreat(best_value, threat_move);
01583 if (EvalTraits<P>::betterThan(threat2.value, beta2))
01584 cut_by_threat2 = true;
01585 }
01586 state.pushPass();
01587 return cut_by_threat2;
01588 }
01589 else if ((depthFromRoot() < QSearch2PrivateTraits::EscapeFromLastMoveDepthFromRoot)
01590 || (unpromote(moves[0].capturePtype()) == ROOK)
01591 || (unpromote(moves[0].capturePtype()) == BISHOP))
01592 {
01593 assert(state.lastMove().isPass());
01594 state.popPass();
01595 bool cut_by_threat2 = false;
01596 const Position to = threat_move.to();
01597 const Piece target = state.state().getPieceOnBoard(to);
01598 bool tried_escape
01599 = (depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot);
01600 #ifdef QSEARCH_PESSIMISTIC_ESCAPE_THREAT
01601 if (state.lastMove().isNormal())
01602 {
01603
01604
01605 const Offset32 offset32(to, state.lastMove().to());
01606 const EffectContent effect
01607 = Ptype_Table.getEffect(state.lastMove().ptypeO(),offset32);
01608 tried_escape = effect.hasEffect();
01609 }
01610 #endif
01611 if (! tried_escape)
01612 {
01613 const Player Opponent = PlayerTraits<P>::opponent;
01614 MoveVector escape;
01615 const bool safe_escape
01616 = QuiescenceGenerator<Opponent>::escapeByMoveOnly(state.state(),
01617 target, escape);
01618 if (safe_escape)
01619 goto finish;
01620 for (MoveVector::const_iterator p=escape.begin(); p!=escape.end(); ++p)
01621 {
01622 eval_t new_ev = ev;
01623 int result;
01624 if (isMajor(p->ptype()))
01625 {
01626 typedef QSearch2TakeBackOrChase<QuiescenceSearch2,Opponent> helper_t;
01627 helper_t helper(result, this, best_value+EvalTraits<Opponent>::delta,
01628 threat2.value+EvalTraits<P>::delta, new_ev, *p);
01629 state.doUndoMoveLight<Opponent,helper_t>(*p, helper);
01630 }
01631 else
01632 {
01633 typedef QSearch2NextTakeBack<QuiescenceSearch2,Opponent> helper_t;
01634 helper_t helper(result, this, best_value+EvalTraits<Opponent>::delta,
01635 threat2.value+EvalTraits<P>::delta, new_ev, *p);
01636 state.doUndoMoveLight<Opponent,helper_t>(*p, helper);
01637 }
01638 if (EvalTraits<Opponent>::betterThan(result, best_value))
01639 {
01640 best_value = result;
01641 if (EvalTraits<Opponent>::notLessThan(result, threat2.value))
01642 break;
01643 }
01644 }
01645 }
01646 if (EvalTraits<P>::betterThan(best_value, threat2.value))
01647 {
01648 threat2 = QuiescenceThreat(best_value, threat_move);
01649 if (EvalTraits<P>::betterThan(threat2.value, beta2))
01650 {
01651 cut_by_threat2 = true;
01652 goto finish;
01653 }
01654 }
01655 finish:
01656 state.pushPass();
01657 return cut_by_threat2;
01658 }
01659 return false;
01660 }
01661
01662 template <class EvalT>
01663 template <osl::Player P>
01664 int osl::search::QuiescenceSearch2<EvalT>::
01665 takeBackOrChase(int alpha, int beta, eval_t const& ev, Move last_move)
01666 {
01667 assert(last_move.isNormal());
01668 int best_value = takeBackValue<P>(alpha, beta, ev, last_move);
01669 if (EvalTraits<P>::betterThan(best_value, beta))
01670 return best_value;
01671
01672 MoveVector moves;
01673 QuiescenceGenerator<P>::capture(state.state(), last_move.from(), moves);
01674 if (moves.empty())
01675 return best_value;
01676 SortCaptureMoves::sortByMovingPiece(moves);
01677 for (MoveVector::const_iterator p=moves.begin(); p!=moves.end(); ++p)
01678 {
01679 eval_t new_ev = ev;
01680
01681 typedef QSearch2SafeEscape<eval_t, P> helper_t;
01682 helper_t helper(&state.state(),
01683 state.state().getPieceOnBoard(last_move.to()),
01684 new_ev, *p);
01685 state.doUndoMoveLight<P,helper_t>(*p, helper);
01686 if (helper.is_invalid)
01687 continue;
01688
01689 int result = new_ev.value();
01690 if (! helper.has_safe_escape)
01691 result += new_ev.captureValue(last_move.ptypeO());
01692 if (state.state().template hasEffectByPtype<ROOK>(P, p->from()))
01693 result += (new_ev.captureValue(newPtypeO(alt(P),PROOK))
01694 - new_ev.captureValue(newPtypeO(alt(P),ROOK)));
01695 best_value = EvalTraits<P>::max(result, best_value);
01696 break;
01697 }
01698 return best_value;
01699 }
01700
01701 template <class EvalT>
01702 template <osl::Player P>
01703 int osl::search::QuiescenceSearch2<EvalT>::
01704 takeBackValue(int alpha, int beta, eval_t const& ev, Move last_move)
01705 {
01706 assert(alpha % 2);
01707 assert(beta % 2);
01708
01709 ++node_count;
01710 assert(EvalTraits<P>::notLessThan(beta, alpha));
01711 if (EffectUtil::isKingInCheck(alt(P), state.state()))
01712 return base_t::winByFoul(P);
01713 if (last_move.isPass())
01714 return ev.value();
01715
01716 const Position last_to = last_move.to();
01717 MoveVector moves;
01718 const Piece last_move_piece = state.state().getPieceOnBoard(last_to);
01719 const Piece king_attack_piece = EffectUtil::kingAttackPiece(P, state.state());
01720 const bool check_by_lance = (king_attack_piece.ptype() == LANCE);
01721 int cur_val;
01722 if (king_attack_piece != Piece::EMPTY())
01723 {
01724 const bool has_safe_move
01725 = QuiescenceGenerator<P>::escapeKingInTakeBack(state.state(), moves,
01726 check_by_lance);
01727 cur_val = (has_safe_move
01728 ? currentValueWithLastThreat(ev, last_move_piece)
01729 : base_t::winByCheckmate(alt(P)));
01730 assert(cur_val % 2 == 0);
01731 }
01732 else
01733 {
01734 cur_val = currentValueWithLastThreat(ev, last_move_piece);
01735 assert(cur_val % 2 == 0);
01736 if (EvalTraits<P>::betterThan(cur_val, beta))
01737 return cur_val;
01738 QuiescenceGenerator<P>::capture(state.state(),
01739 last_move_piece.position(), moves);
01740 SortCaptureMoves::sortByMovingPiece(moves);
01741 }
01742 if (EvalTraits<P>::betterThan(cur_val, alpha))
01743 {
01744 alpha = cur_val + EvalTraits<P>::delta;
01745 if (EvalTraits<P>::betterThan(cur_val, beta)) {
01746 return cur_val;
01747 }
01748 }
01749
01750 assert(EvalTraits<P>::betterThan(alpha, cur_val));
01751 if (examineTakeBack<P>(moves, cur_val, alpha, beta, ev)) {
01752 assert(cur_val % 2 == 0);
01753 return cur_val;
01754 }
01755
01756
01757 assert(cur_val % 2 == 0);
01758 return cur_val;
01759 }
01760
01761 template <class EvalT>
01762 template <osl::Player P>
01763 int osl::search::QuiescenceSearch2<EvalT>::
01764 staticValueWithThreat(eval_t const& ev, int alpha,
01765 QuiescenceThreat& threat1, QuiescenceThreat& threat2)
01766 {
01767 assert(alpha % 2);
01768 assert(! EffectUtil::isKingInCheck(P, state.state()));
01769 const int static_value = ev.value();
01770 if (EvalTraits<P>::notLessThan(alpha, static_value))
01771 return static_value;
01772 const Player O = PlayerTraits<P>::opponent;
01773 const int FirstThreat = QSearchTraits::FirstThreat;
01774 const int SecondThreat
01775 = (depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot)
01776 ? 1
01777 : QSearchTraits::SecondThreat;
01778
01779 const int o_beta1
01780 = (EvalTraits<O>::min(base_t::winByCheckmate(O),
01781 static_value - FirstThreat*(static_value - alpha))
01782 - ((FirstThreat % 2) ? 0 : EvalTraits<O>::delta));
01783 const int o_beta2
01784 = (EvalTraits<O>::min(base_t::winByCheckmate(O),
01785 static_value - SecondThreat*(static_value - alpha))
01786 - ((SecondThreat % 2) ? 0 : EvalTraits<O>::delta));
01787
01788 threat1.value = static_value;
01789 threat2.value = static_value;
01790
01791 assert(state.state().getTurn() == P);
01792 const Move last_move = state.lastMove();
01793 state.pushPass();
01794
01795 assert(! EffectUtil::isKingInCheck(O, state.state()));
01796
01797 assert(EvalTraits<O>::betterThan(o_beta1, threat1.value));
01798 assert(EvalTraits<O>::betterThan(o_beta2, threat1.value));
01799 assert(EvalTraits<O>::notLessThan(o_beta1, o_beta2));
01800 MoveVector moves;
01801 if (generateAndExamineTakeBack2<O,ROOK>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01802 goto finish;
01803 if (generateAndExamineTakeBack2<O,BISHOP>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01804 goto finish;
01805 if (generateAndExamineTakeBack2<O,GOLD>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01806 goto finish;
01807 if (generateAndExamineTakeBack2<O,SILVER>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01808 goto finish;
01809 if ((depth() >= QSearch2PrivateTraits::KnightCaptureDepth)
01810 || max_depth <= 2
01811 || (threat2.value == static_value
01812 && last_move.isNormal()
01813 && (isMajorBasic(last_move.oldPtype())
01814 && (last_move.isDrop() || last_move.isPromote()))))
01815 {
01816 if (generateAndExamineTakeBack2<O,KNIGHT>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01817 goto finish;
01818 if (generateAndExamineTakeBack2<O,LANCE>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01819 goto finish;
01820 }
01821
01822 QuiescenceGenerator<O>::template promote<ROOK>(state.state(), moves);
01823 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01824 goto finish;
01825 moves.clear();
01826 QuiescenceGenerator<O>::template promote<BISHOP>(state.state(), moves);
01827 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01828 goto finish;
01829 moves.clear();
01830 QuiescenceGenerator<O>::template promote<PAWN>(state.state(), moves);
01831 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01832 goto finish;
01833 moves.clear();
01834 if (depth() >= QSearch2PrivateTraits::PawnCaptureDepth
01835 || max_depth <= 2)
01836 {
01837 if (generateAndExamineTakeBack2<O,PAWN>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01838 goto finish;
01839 if (depth() >= QSearch2PrivateTraits::PawnCaptureDepth) {
01840 if (depthFromRoot() < QSearch2PrivateTraits::AttackGoldSilverDepthFromRoot)
01841 {
01842 moves.clear();
01843 QuiescenceGenerator<O>::attackGoldWithPawn(state.state(), PieceMask(), moves);
01844 QuiescenceGenerator<O>::attackSilverWithPawn(state.state(), PieceMask(), moves);
01845 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01846 goto finish;
01847 }
01848 if (depthFromRoot() < QSearch2PrivateTraits::AttackKnightDepthFromRoot)
01849 {
01850 moves.clear();
01851 QuiescenceGenerator<O>::attackKnightWithPawn(state.state(), PieceMask(), moves);
01852 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01853 goto finish;
01854 }
01855 }
01856 }
01857
01858 if (threat1.value == static_value)
01859 {
01860 moves.clear();
01861 QuiescenceGenerator<O>::template promote<SILVER>(state.state(), moves);
01862 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01863 goto finish;
01864 }
01865 if (threat1.value == static_value)
01866 {
01867 moves.clear();
01868 QuiescenceGenerator<O>::template promote<KNIGHT>(state.state(), moves);
01869 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01870 goto finish;
01871 }
01872 if (threat1.value == static_value)
01873 {
01874 moves.clear();
01875 QuiescenceGenerator<O>::template promote<LANCE>(state.state(), moves);
01876 if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev))
01877 goto finish;
01878 }
01879 finish:
01880 state.popPass();
01881
01882 if (threat1.move == threat2.move && threat1.move.isNormal()) {
01883 const Piece target = state.state().getPieceOnBoard(threat1.move.to());
01884 if (isMajorBasic(target.ptype())
01885 && target.position().template canPromote<O>()) {
01886 assert(alt(target.owner()) == O);
01887 assert(threat1.value % 2 == 0);
01888 return threat1.value;
01889 }
01890 }
01891
01892 const int result1 = (static_value - (static_value - threat1.value)/FirstThreat);
01893 const int result2 = (static_value - (static_value - threat2.value)/SecondThreat);
01894
01895 const int result = EvalTraits<O>::max(result1, result2) & (~0x1);
01896 assert(result % 2 == 0);
01897 return result;
01898 }
01899
01900 #endif
01901
01902
01903
01904