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