00001 #ifndef _CHECKMATE_SEARHCER_TCC
00002 #define _CHECKMATE_SEARHCER_TCC
00003
00004 #include "osl/checkmate/checkmateSearcher.h"
00005 #include "osl/checkmate/checkMoveList.h"
00006 #include "osl/checkmate/checkHashRecord.h"
00007 #include "osl/checkmate/checkmateRecorder.h"
00008 #include "osl/checkmate/checkHashTable.h"
00009 #include "osl/checkmate/checkMoveGenerator.h"
00010 #include "osl/checkmate/checkTableUtil.h"
00011 #include "osl/checkmate/libertyEstimator.h"
00012 #include "osl/checkmate/pieceCost.h"
00013 #include "osl/checkmate/oracleProver.h"
00014 #include "osl/checkmate/oracleDisprover.h"
00015 #include "osl/checkmate/sameBoardList.h"
00016 #include "osl/checkmate/blockingSimulation.h"
00017 #include "osl/checkmate/blockingSimulation.tcc"
00018 #include "osl/checkmate/defenseSimulation.h"
00019 #include "osl/checkmate/defenseSimulation.tcc"
00020 #include "osl/checkmate/pawnCheckmateMoves.h"
00021 #include "osl/checkmate/immediateCheckmate.h"
00022 #include "osl/checkmate/fixedDepthSearcher.tcc"
00023 #include "osl/apply_move/applyMoveWithPath.h"
00024 #include "osl/effect_util/effectUtil.h"
00025 #ifdef CHECKMATE_DEBUG
00026 # include "osl/stat/ratio.h"
00027 #endif
00028 #include <algorithm>
00029
00030
00031
00032 #define CHECKMATE_D2
00033
00034
00036 #define PROOF_SIMULATION
00037
00038 #define DISPROOF_SIMULATION
00039
00040 #define DISPROOF_TWIN_SIMULATION
00041
00043 #define ROOT_NOEXPAND_TOL 100u
00044
00045 #define ROOT_PROOF_TOL 65536ul*1024
00046
00047 #define ROOT_DISPROOF_TOL 65536ul*1024
00048
00049 namespace osl
00050 {
00051 namespace checkmate
00052 {
00053 template<Player P, class CheckmateSearcher>
00054 struct ChildDefenseHelper
00055 {
00056 typedef CheckmateSearcher searcher_t;
00057 searcher_t& searcher;
00058 int proof_number, disproof_number;
00059 CheckHashRecord *parent;
00060 CheckHashRecord *record;
00061 ChildDefenseHelper(searcher_t& s,int pn, int dn,
00062 CheckHashRecord *p, CheckHashRecord *r)
00063 : searcher(s),proof_number(pn),disproof_number(dn),
00064 parent(p), record(r)
00065 {
00066 check_assert(record && (! record->proofDisproof().isFinal()));
00067 }
00068 void operator()(Position)
00069 {
00070 searcher.template defense<P>
00071 (proof_number, disproof_number, parent, record);
00072 record->isVisited = false;
00073 }
00074 };
00075
00076 template <Player P, class CheckmateSearcher>
00077 struct ChildAttackHelper
00078 {
00079 typedef CheckmateSearcher searcher_t;
00080 searcher_t& searcher;
00081 int proof_number, disproof_number;
00082 CheckHashRecord *parent;
00083 CheckHashRecord *record;
00084 ChildAttackHelper(searcher_t& s,int pn, int dn,
00085 CheckHashRecord *p, CheckHashRecord *r)
00086 : searcher(s),proof_number(pn),disproof_number(dn),
00087 parent(p), record(r)
00088 {
00089 check_assert(record && (! record->proofDisproof().isFinal()));
00090 }
00091 void operator()(Position)
00092 {
00093 searcher.template attack<P>(proof_number,disproof_number,parent,record);
00094 record->isVisited = false;
00095 }
00096 };
00097
00098 inline
00099 unsigned int addWithSaturation(unsigned int limit,
00100 unsigned int l, unsigned int r)
00101 {
00102 if (limit < l)
00103 return limit;
00104 const unsigned int sum = l+r;
00105 if (limit < sum)
00106 return limit;
00107
00108 if (sum < l)
00109 return limit;
00110 check_assert(r < sum);
00111 return sum;
00112 }
00113
00114 }
00115 }
00116
00117 template <class Table,class HEstimator,class CostEstimator>
00118 osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00119 CheckmateSearcher(Player a, Table& t, size_t limit)
00120 : state(0), table(t), node_count(0), search_node_limit(0),
00121 total_node_count(0), total_node_limit(limit), verbose_destructor(false),
00122 attacker(a)
00123 {
00124 check_assert(t.getAttacker() == attacker);
00125 }
00126
00127 template <class Table,class HEstimator,class CostEstimator>
00128 osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00129 ~CheckmateSearcher()
00130 {
00131 clearNodeCount();
00132 if (verbose_destructor && total_node_count)
00133 CheckmateRecorder::stat("~CheckmateSearcher", attacker, table.size(),
00134 total_node_count, total_node_limit);
00135 }
00136
00137 template <class Table,class HEstimator,class CostEstimator>
00138 inline
00139 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00140 exceedNodeCount(unsigned int future_cost) const
00141 {
00142 return (node_count + future_cost > search_node_limit)
00143 || (node_count > search_node_limit);
00144 }
00145
00146 template <class Table,class HEstimator,class CostEstimator>
00147 template<osl::Player P>
00148 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00149 setUpAttackNode(CheckHashRecord *record)
00150 {
00151 check_assert(record->needMoveGeneration());
00152 const Position op_king_position
00153 =(*state).template getKingPosition<PlayerTraits<P>::opponent>();
00154 #ifndef NDEBUG
00155 check_assert(! state->hasEffectBy(P,op_king_position));
00156 #endif
00157 const bool in_check = EffectUtil::isKingInCheck(P, *state);
00158 King8Info info = King8Info::make<P>(*state, op_king_position);
00159 #if ((! defined CHECKMATE_A3) || (! defined CHECKMATE_D2))
00160
00161 Move check_move;
00162 if (in_check)
00163 record->updateBestResultInSolvedAttack(ProofDisproof::PawnCheckmate());
00164 if ((! in_check)
00165 && ImmediateCheckmate::hasCheckmateMove<P>(*state, info,
00166 op_king_position, check_move))
00167 {
00168 CheckMove best_move(check_move);
00169 best_move.flags.set(MoveFlags::ImmediateCheckmate);
00170 record->moves.setOne(best_move, table.listProvider());
00171 record->bestMove = &*(record->moves.begin());
00172 PieceStand proof_pieces;
00173 if (check_move.isDrop())
00174 proof_pieces.add(check_move.ptype());
00175 record->setProofPieces(proof_pieces);
00176 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00177 return true;
00178 }
00179 #endif
00180 CheckMoveGenerator<P>::generateAttack(*state, table.listProvider(),
00181 record->moves);
00182 for (CheckMoveList::iterator p=record->moves.begin(); p!=record->moves.end(); ++p)
00183 {
00184 CostEstimator::setAttackCost(P, *state, *p);
00185 {
00186 unsigned int proof, disproof;
00187 HEstimator::attackH(attacker, *state, info, p->move,
00188 proof, disproof);
00189 p->h_proof = proof;
00190 p->h_disproof = disproof;
00191 check_assert(p->h_proof && p->h_disproof);
00192 }
00193 }
00194 if (record->moves.empty())
00195 {
00196 record->setDisproofPieces(DisproofPieces::leaf(*state, alt(P),
00197 record->stand(alt(P))));
00198 record->propagateNoCheckmate<P>(in_check
00199 ? ProofDisproof::PawnCheckmate()
00200 : ProofDisproof::NoCheckmate());
00201 return true;
00202 }
00203 return false;
00204 }
00205
00206 template <class Table,class HEstimator,class CostEstimator>
00207 template<osl::Player P>
00208 void osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00209 attack(unsigned int proof_limit, unsigned int disproof_limit,
00210 CheckHashRecord *parent, CheckHashRecord *record)
00211 {
00212 #ifndef NDEBUG
00213 CheckmateRecorder::Tracer tracer("attack ", record, key, path,
00214 proof_limit, disproof_limit);
00215 #endif
00216 node_count++;
00217
00218 check_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
00219 check_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
00220 check_assert(record && parent && record->parent);
00221 check_assert(! record->isVisited);
00222 check_assert(! record->findLoop(path, table.getTwinTable()));
00223 check_assert(! record->proofDisproof().isFinal());
00224 check_assert((record->proof() < proof_limit));
00225 check_assert((record->disproof() < disproof_limit));
00226 check_assert(record->isConsistent());
00227
00228 record->confirmParent(parent);
00229 if (record->sameBoards)
00230 {
00231 const CheckHashRecord *loop =
00232 (*record->sameBoards).template
00233 findIneffectiveDropLoop<P>(key.blackStand());
00234 if (loop)
00235 {
00236 record->setLoopDetection(path, loop);
00237 CheckmateRecorder::setLeaveReason("loop confirmation (drop)");
00238 return;
00239 }
00240 }
00241 if (record->needMoveGeneration())
00242 {
00243 {
00244 Move check_move;
00245 #ifdef CHECKMATE_A3
00246 if (record->distance >= 0)
00247 {
00248 PieceStand proof_pieces;
00249 const ProofDisproof pdp
00250 = fixed_searcher.hasCheckmateMove<P>(2, check_move, proof_pieces);
00251 if (pdp.isCheckmateSuccess())
00252 {
00253 CheckMove best_move(check_move);
00254 best_move.flags.set(MoveFlags::ImmediateCheckmate);
00255 record->moves.push_back(best_move);
00256 record->bestMove = &*(record->moves.begin());
00257 record->setProofPieces(proof_pieces);
00258 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00259 return;
00260 }
00261 else if (pdp.isCheckmateFail())
00262 {
00263
00264 }
00265 else
00266 {
00267 assert(pdp.isUnknown());
00268 record->setProofDisproof(std::max(pdp.proof(), record->proof()),
00269 std::max(pdp.disproof(), record->disproof()));
00270 if ((pdp.proof() >= proof_limit)
00271 || (pdp.disproof() >= disproof_limit))
00272 return;
00273 }
00274 }
00275 #endif
00276 }
00277 if (record->needMoveGeneration() && setUpAttackNode<P>(record))
00278 return;
00279 }
00280 #ifdef DISPROOF_SIMULATION
00281 # ifdef DISPROOF_TWIN_SIMULATION
00282 if (! record->twins.empty())
00283 {
00284 # ifdef CHECKMATE_DEBUG
00285 static stat::Ratio ratio("disproof by twins (attack)");
00286 # endif
00287 TwinAgeEntry& age = table.allocateTwin(path);
00288 check_assert(! age.hasTwinEntry());
00289 for (TwinList::const_iterator p=record->twins.begin();
00290 (p!=record->twins.end()) && ((size_t)age.age < record->twins.size());
00291 ++p, ++age.age)
00292 {
00293 # ifdef CHECKMATE_DEBUG
00294 ratio.add(record->proofDisproof().isFinal()|| record->findLoop(path, table.getTwinTable()));
00295 # endif
00296 DisproofOracleAttack<P> oracle(record, p->path);
00297 assert(oracle.isValid());
00298 typedef OracleDisprover<Table> disprover_t;
00299 disprover_t disprover(table);
00300 const bool disproved = disprover.proofNoCheckmate(*state, key,
00301 path, oracle);
00302 # ifdef CHECKMATE_DEBUG
00303 ratio.add(disproved);
00304 # endif
00305 if (disproved)
00306 return;
00307 }
00308 }
00309 # endif
00310 #endif
00311 if (record->proofDisproof().isFinal())
00312 return;
00313
00314 check_assert(! record->needMoveGeneration());
00315 check_assert(! record->isVisited);
00316 check_assert(proof_limit && disproof_limit);
00317 record->isVisited = true;
00318 check_assert(record->isConsistent());
00319 for (;;)
00320 {
00321 check_assert(! record->findLoop(path, table.getTwinTable()));
00322 unsigned int child_best_proof_number, child_second_best_proof_number;
00323 unsigned int current_disproof_number, child_best_disproof_number;
00324 CheckMove *best_move;
00325 ProofDisproof bestResultInSolved;
00326 #ifdef CHECK_EXTRA_LIMIT_PROOF
00327 const unsigned int proof_average =
00328 #endif
00329 record->selectBestAttackMove(path, table.getTwinTable(),
00330 child_best_proof_number,
00331 child_second_best_proof_number,
00332 current_disproof_number, child_best_disproof_number,
00333 bestResultInSolved, best_move);
00334 if (! best_move)
00335 {
00336 if (! bestResultInSolved.isLoopDetection())
00337 {
00338 record->setDisproofPieces(DisproofPieces::attack(record->moves, *state,
00339 record->stand(alt(P))));
00340 record->twins.clear();
00341 record->propagateNoCheckmate<P>(bestResultInSolved);
00342 return;
00343 }
00344 else
00345 {
00346 record->setLoopDetectionInAttack<P>(path);
00347 return;
00348 }
00349 }
00350 check_assert(best_move);
00351 record->bestMove = best_move;
00352
00353 HashKey new_key = key.newHashWithMove(best_move->move);
00354 PathEncoding new_path = PathEncoding(path, best_move->move);
00355 if (! best_move->record)
00356 {
00357 CheckTableUtil::allocate(best_move->move, best_move->record, table,
00358 new_key, new_path, record);
00359 if (best_move->record->isVisited
00360 || best_move->findLoop(path, table.getTwinTable())
00361 || best_move->record->proofDisproof().isPawnDropFoul(best_move->move)
00362 || (best_move->record->proof()
00363 && ((best_move->record->proofDisproof()
00364 != CheckHashRecord::initialProofDisproof())
00365 || (best_move->record->distance <= record->distance))))
00366 continue;
00367 }
00368
00369 check_assert(best_move->record);
00370 check_assert(! best_move->record->isVisited);
00371 check_assert(! best_move->findLoop(path, table.getTwinTable()));
00372 check_assert(best_move->record->isConsistent());
00373 if (best_move->record->proof()==0)
00374 {
00375 check_assert(! (best_move->record->proofDisproof()
00376 .isPawnDropFoul(best_move->move)));
00377 if (record->bestMove == 0)
00378 record->bestMove = best_move;
00379 check_assert(best_move == record->bestMove);
00380 check_assert(best_move->record->hasProofPieces());
00381 record->setProofPiecesAttack(P);
00382 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00383 CheckmateRecorder::setLeaveReason("checkmate found");
00384 check_assert(record->isConsistent());
00385 return;
00386 }
00387
00388 if (child_best_proof_number>=proof_limit
00389 || current_disproof_number>=disproof_limit
00390 || current_disproof_number==0
00391 || exceedNodeCount(child_best_proof_number))
00392 {
00393 CheckmateRecorder::setLeaveReason("limit over");
00394 check_assert(current_disproof_number <= ProofDisproof::DISPROOF_LIMIT);
00395 check_assert(child_best_proof_number && current_disproof_number);
00396 record->setProofDisproof(child_best_proof_number, current_disproof_number);
00397 return;
00398 }
00399
00400 const ProofDisproof& pdp = best_move->record->proofDisproof();
00401 check_assert(! pdp.isFinal());
00402 check_assert(record->useMaxInsteadOfSum
00403 || (best_move->record->distance > record->distance));
00404 #ifdef CHECK_EXTRA_LIMIT_PROOF
00405 const unsigned int next_proof_limit
00406 = addWithSaturation(proof_limit, child_second_best_proof_number, proof_average)
00407 - best_move->cost_proof;
00408 #else
00409 const unsigned int next_proof_limit
00410 = ((proof_limit <= child_second_best_proof_number)
00411 ? proof_limit
00412 : child_second_best_proof_number +1)
00413 - best_move->cost_proof;
00414 #endif
00415 const unsigned int next_disproof_limit
00416 = disproof_limit-current_disproof_number+child_best_disproof_number;
00417 ChildDefenseHelper<P,CheckmateSearcher>
00418 helper(*this, next_proof_limit, next_disproof_limit,
00419 record, best_move->record);
00420 CheckmateRecorder::setNextMove(&*best_move);
00421
00422 std::swap(key, new_key);
00423 std::swap(path, new_path);
00424
00425 ApplyMove<P>::doUndoMove(*state, best_move->move, helper);
00426
00427 key = new_key;
00428 path = new_path;
00429
00430 check_assert(best_move->record->isConfluence
00431 || (best_move->record->parent == record));
00432 if (record->proofDisproof().isFinal())
00433 return;
00434 if (pdp.proof() == 0)
00435 {
00436 if (! pdp.isPawnDropFoul(best_move->move))
00437 {
00438 if (record->bestMove == 0)
00439 record->bestMove = best_move;
00440 check_assert(best_move == record->bestMove);
00441 check_assert(best_move->record->hasProofPieces());
00442 record->setProofPiecesAttack(P);
00443 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00444 CheckmateRecorder::setLeaveReason("checkmate found after move");
00445 return;
00446 }
00447
00448 record->addToSolvedInAttack(*best_move, ProofDisproof::PawnCheckmate());
00449 record->filter.addTarget(MoveFlags::NoPromote);
00450 }
00451 else if (pdp.disproof() == 0)
00452 {
00453 check_assert(! pdp.isLoopDetection());
00454 record->addToSolvedInAttack(*best_move, pdp);
00455 #ifdef DISPROOF_SIMULATION
00456 assert(best_move->move.isValid());
00457 if (best_move->move.isDrop())
00458 {
00459 const Ptype ptype = best_move->move.ptype();
00460 if ((ptype == ROOK) || (ptype == BISHOP))
00461 {
00462 DefenseSimulation<P>::disproofDropSibling
00463 (*state, key, path, record, table, *best_move, node_count);
00464 }
00465 }
00466 #endif
00467 }
00468 #ifdef PAWN_CHECKMATE_SENSITIVE
00469 const TwinEntry *loopDetected = best_move->findLoop(path, table.getTwinTable());
00470 if (((pdp == ProofDisproof::PawnCheckmate())
00471 || (loopDetected && loopDetected->move.record
00472 && (loopDetected->move.record->bestResultInSolved
00473 == ProofDisproof::PawnCheckmate())))
00474 && PawnCheckmateMoves::hasParingNoPromote(best_move->move))
00475 {
00476 const Move try_nopromote = best_move->move.noPromote();
00477 for (CheckMoveList::iterator p=record->moves.begin();
00478 p!=record->moves.end(); ++p)
00479 {
00480 if (p->move == try_nopromote)
00481 {
00482 if (! p->record)
00483 {
00484 p->flags.unset(MoveFlags::NoPromote);
00485 const HashKey new_key = key.newHashWithMove(try_nopromote);
00486 const PathEncoding new_path(path, try_nopromote);
00487 CheckTableUtil::allocate
00488 (p->move, p->record, table, new_key, new_path, record);
00489 #ifdef DISPROOF_SIMULATION
00490 DefenseSimulation<P>::disproofNoPromote
00491 (*state, new_key, new_path, record, table, *p, *best_move, node_count);
00492 #endif
00493 }
00494 break;
00495 }
00496 }
00497 }
00498 #endif
00499 }
00500 }
00501
00502 template <class Table,class HEstimator,class CostEstimator>
00503 template<osl::Player P>
00504 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00505 setUpDefenseNode(CheckHashRecord *record)
00506 {
00507 check_assert(record->needMoveGeneration());
00508 #ifdef CHECKMATE_DEBUG
00509 const Position op_king_position=(*state).template getKingPosition<P>();
00510
00511 check_assert(op_king_position.isPieceStand()
00512 || ! state->hasEffectBy(alt(P),op_king_position));
00513 #endif
00514 const unsigned int simple_king_moves =
00515 CheckMoveGenerator<P>::generateEscape(*state, table.listProvider(),
00516 record->moves,
00517 record->parent->bestMove->move);
00518 if (record->moves.empty()) {
00519 assert(! record->proofDisproof().isFinal());
00520 record->setProofPieces(ProofPieces::leaf(*state, P, record->stand(P)));
00521 record->propagateCheckmate<P>(ProofDisproof::NoEscape());
00522 check_assert(record->isConsistent());
00523 return true;
00524 }
00525 if (simple_king_moves == 2)
00526 record->false_branch_candidate = true;
00527
00528 for (CheckMoveList::iterator p=record->moves.begin();
00529 p!=record->moves.end(); ++p)
00530 {
00531 check_assert(p->move.isNormal());
00532 #ifdef CHECKMATE_D2
00533 PieceStand proof_pieces;
00534 Move check_move;
00535 const ProofDisproof pdp
00536 = fixed_searcher.hasEscapeByMove<P>(p->move, 0, check_move, proof_pieces);
00537
00538 if (pdp.isCheckmateSuccess())
00539 {
00540 CheckTableUtil::registerImmediateCheckmateInDefense<P,Table>
00541 (key, path, record, *p, pdp, check_move, proof_pieces, table);
00542 }
00543 else if (pdp.isCheckmateFail())
00544 {
00545 CheckMove best_move = *p;
00546 record->moves.setOne(best_move, table.listProvider());
00547 break;
00548 }
00549 else
00550 {
00551 p->h_proof = pdp.proof();
00552 p->h_disproof = pdp.disproof();
00553 }
00554 #endif
00555 #if (! defined CHECKMATE_D2)
00556 unsigned int proof, disproof;
00557 HEstimator::defenseH(attacker, *state, p->move,
00558 proof, disproof);
00559 p->h_proof = proof;
00560 p->h_disproof = disproof;
00561 #endif
00562 check_assert(p->h_proof && p->h_disproof);
00563 }
00564
00565 for (CheckMoveList::iterator p=record->moves.begin();
00566 p!=record->moves.end(); ++p)
00567 {
00568 CostEstimator::setDefenseCost(P, *state, *p);
00569 }
00570 return false;
00571 }
00572
00573 template <class Table,class HEstimator,class CostEstimator>
00574 template<osl::Player P>
00575 void osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00576 defense(unsigned int proof_limit, unsigned int disproof_limit,
00577 CheckHashRecord *parent, CheckHashRecord *record)
00578 {
00579 #ifndef NDEBUG
00580 CheckmateRecorder::Tracer tracer("defense", record, key, path,
00581 proof_limit, disproof_limit);
00582 #endif
00583 node_count++;
00584
00585 check_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
00586 check_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
00587 check_assert(record && parent && record->parent);
00588 check_assert(! record->findLoop(path, table.getTwinTable()));
00589 check_assert(! record->isVisited);
00590 check_assert(! record->proofDisproof().isFinal());
00591 check_assert(! (record->proof()>proof_limit));
00592 check_assert(! (record->disproof()>disproof_limit));
00593 check_assert(record->isConsistent());
00594
00595 record->confirmParent(parent);
00596 if (record->sameBoards)
00597 {
00598 const CheckHashRecord *loop =
00599 (*record->sameBoards).template
00600 findIneffectiveDropLoop<P>(key.blackStand());
00601 if (loop)
00602 {
00603 record->setLoopDetection(path, loop);
00604 CheckmateRecorder::setLeaveReason("loop confirmation (drop)");
00605 return;
00606 }
00607 }
00608 if (record->needMoveGeneration())
00609 {
00610 if (setUpDefenseNode<P>(record))
00611 return;
00612 }
00613 #ifdef DISPROOF_SIMULATION
00614 # ifdef DISPROOF_TWIN_SIMULATION
00615 if (! record->twins.empty())
00616 {
00617 # ifdef CHECKMATE_DEBUG
00618 static stat::Ratio ratio("disproof by twins (defense)");
00619 # endif
00620 TwinAgeEntry& age = table.allocateTwin(path);
00621 check_assert(! age.hasTwinEntry());
00622 for (TwinList::const_iterator p=record->twins.begin();
00623 (p!=record->twins.end()) && ((size_t)age.age < record->twins.size());
00624 ++p, ++age.age)
00625 {
00626 DisproofOracleDefense<P> oracle(record, p->path);
00627 assert(oracle.isValid());
00628 typedef OracleDisprover<Table> disprover_t;
00629 disprover_t prover(table);
00630 Move escape_move;
00631 const bool disproved
00632 = prover.proofEscape(*state, key, path, oracle, escape_move,
00633 record->parent->bestMove->move);
00634 # ifdef CHECKMATE_DEBUG
00635 ratio.add(disproved);
00636 # endif
00637 if (disproved)
00638 return;
00639 }
00640 }
00641 # endif
00642 #endif
00643 if (record->proofDisproof().isFinal())
00644 return;
00645
00646 check_assert(! record->needMoveGeneration());
00647 check_assert(proof_limit && disproof_limit);
00648 record->isVisited = true;
00649 check_assert(record->isConsistent());
00650 for (;;)
00651 {
00652 if (record->findLoop(path, table.getTwinTable()))
00653 return;
00654 unsigned int child_best_disproof_number, child_second_best_disproof_number;
00655 unsigned int current_proof_number, child_best_proof_number;
00656 ProofDisproof bestResultInSolved;
00657 CheckMove *best_move;
00658 #ifdef CHECK_EXTRA_LIMIT_DISPROOF
00659 const unsigned int disproof_average =
00660 #endif
00661 record->selectBestDefenseMove(path, table.getTwinTable(),
00662 child_best_disproof_number,
00663 child_second_best_disproof_number,
00664 current_proof_number, child_best_proof_number,
00665 bestResultInSolved, best_move);
00666 if (! best_move)
00667 {
00668 if (! record->filter.isTarget(MoveFlags::BlockingBySacrifice))
00669 {
00670 record->filter.addTarget(MoveFlags::BlockingBySacrifice);
00671 for (CheckMoveList::iterator p=record->moves.begin();
00672 p!=record->moves.end(); ++p)
00673 {
00674 if (p->flags.isSet(MoveFlags::BlockingBySacrifice))
00675 {
00676 const HashKey new_key = key.newHashWithMove(p->move);
00677 const PathEncoding new_path(path, p->move);
00678 if (! p->record)
00679 {
00680 CheckTableUtil::allocate
00681 (p->move, p->record, table, new_key, new_path, record);
00682 }
00683 #ifdef PROOF_SIMULATION
00684 if (BlockingSimulation<P>::proof(*state, new_key, new_path,
00685 record, table, *p, node_count))
00686 p->flags = MoveFlags::Solved;
00687 else
00688 #endif
00689 best_move = &*p;
00690 }
00691 }
00692 }
00693 if ((! best_move) && (! record->filter.isTarget(MoveFlags::Upward)))
00694 {
00695 record->filter.addTarget(MoveFlags::Upward);
00696 record->useMaxInsteadOfSum = true;
00697 continue;
00698 }
00699 if (! best_move)
00700 {
00701 CheckmateRecorder::setLeaveReason("no unsolved moves");
00702 check_assert(record->bestResultInSolved.proof() == 0);
00703 if (! record->proofDisproof().isCheckmateSuccess())
00704 {
00705 assert(! record->proofDisproof().isFinal());
00706 record->setProofPieces(ProofPieces::defense(record->moves, *state,
00707 record->stand(P)));
00708 record->propagateCheckmate<P>(record->bestResultInSolved);
00709 }
00710 return;
00711 }
00712 continue;
00713 }
00714 check_assert(best_move);
00715 record->bestMove = &*best_move;
00716
00717 HashKey new_key = key.newHashWithMove(best_move->move);
00718 PathEncoding new_path(path, best_move->move);
00719 if (! best_move->record)
00720 {
00721 CheckTableUtil::allocate(best_move->move, best_move->record, table,
00722 new_key, new_path, record);
00723 if ((! best_move->record->isVisited)
00724 && (! best_move->findLoop(path, table.getTwinTable()))
00725 && best_move->record->disproof()
00726 && ((best_move->record->proofDisproof()
00727 != CheckHashRecord::initialProofDisproof())
00728 || (best_move->record->distance <= record->distance)))
00729 continue;
00730 }
00731
00732 check_assert(best_move->record);
00733 if (best_move->record->disproof()==0)
00734 {
00735 record->setDisproofPiecesDefense(alt(P));
00736 record->twins.clear();
00737 record->propagateNoCheckmate<P>(best_move->record->proofDisproof());
00738 CheckmateRecorder::setLeaveReason("no checkmate found");
00739 return;
00740 }
00741 if (best_move->record->isVisited)
00742 {
00743 record->setLoopDetection(path, *best_move, best_move->record);
00744 CheckmateRecorder::setLeaveReason("loop to visited");
00745 return;
00746 }
00747 if (const TwinEntry *loop = best_move->findLoop(path, table.getTwinTable()))
00748 {
00749 record->setLoopDetectionTryMerge<P>
00750 (path, *best_move, loop->loopTo);
00751 CheckmateRecorder::setLeaveReason("loop found");
00752 return;
00753 }
00754
00755 if (child_best_disproof_number>=disproof_limit
00756 || current_proof_number>=proof_limit
00757 || exceedNodeCount(current_proof_number))
00758 {
00759 check_assert(current_proof_number);
00760 check_assert(current_proof_number<=ProofDisproof::PROOF_LIMIT);
00761 check_assert(child_best_disproof_number);
00762 record->setProofDisproof(current_proof_number, child_best_disproof_number);
00763 CheckmateRecorder::setLeaveReason("limit over");
00764 return;
00765 }
00766 check_assert(best_move->record && (! best_move->record->isVisited)
00767 && (! best_move->findLoop(path, table.getTwinTable())));
00768 check_assert(! best_move->record->proofDisproof().isFinal());
00769 const unsigned int next_proof_limit
00770 = proof_limit-current_proof_number+child_best_proof_number;
00771 #ifdef CHECK_EXTRA_LIMIT_DISPROOF
00772 const unsigned int next_disproof_limit
00773 = addWithSaturation(disproof_limit,
00774 child_second_best_disproof_number, disproof_average)
00775 - best_move->cost_disproof;
00776 #else
00777 const unsigned int next_disproof_limit
00778 = ((disproof_limit <= child_second_best_disproof_number)
00779 ? disproof_limit
00780 : child_second_best_disproof_number +1)
00781 - best_move->cost_disproof;
00782 #endif
00783 ChildAttackHelper<P,CheckmateSearcher>
00784 helper(*this, next_proof_limit, next_disproof_limit,
00785 record, best_move->record);
00786 CheckmateRecorder::setNextMove(&*best_move);
00787
00788 std::swap(key, new_key);
00789 std::swap(path, new_path);
00790 ApplyMove<PlayerTraits<P>::opponent>
00791 ::doUndoMove(*state,best_move->move,helper);
00792 key = new_key;
00793 path = new_path;
00794
00795 check_assert(best_move->record->isConfluence
00796 || (best_move->record->parent == record)
00797 || record->finalByDominance());
00798 if (record->proofDisproof().isFinal())
00799 return;
00800 if (best_move->record->disproof()==0)
00801 {
00802 record->setDisproofPiecesDefense(alt(P));
00803 record->twins.clear();
00804 record->propagateNoCheckmate<P>(best_move->record->proofDisproof());
00805 CheckmateRecorder::setLeaveReason("no checkmate after move");
00806 return;
00807 }
00808 #ifdef PROOF_SIMULATION
00809 if ((best_move->record->proof()==0)
00810 && best_move->move.isDrop())
00811 {
00812 BlockingSimulation<P>::proofSibling(*state, key, path, record, table,
00813 *best_move, node_count);
00814 }
00815 #endif
00816 }
00817 }
00818
00819 template <class Table,class HEstimator,class CostEstimator>
00820 inline
00821 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00822 exceedRootTolerance(unsigned int proof_number, unsigned int disproof_number,
00823 unsigned int continuousNoExpandLoop)
00824 {
00825 return (proof_number >= ROOT_PROOF_TOL)
00826 || (disproof_number >= ROOT_DISPROOF_TOL)
00827 || (continuousNoExpandLoop >= ROOT_NOEXPAND_TOL);
00828 }
00829
00830 template <class Table,class HEstimator,class CostEstimator>
00831 template<osl::Player P>
00832 const osl::checkmate::ProofDisproof osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00833 hasCheckmateMove(state_t& s, const HashKey& root_key,
00834 const PathEncoding& root_path,
00835 size_t search_node_limit, Move& best_move)
00836 {
00837 assert(P == attacker);
00838 check_assert(s.getTurn()==P);
00839 assert(node_count == 0);
00840 state = &s;
00841 path = root_path;
00842 key = root_key;
00843 CheckmateRecorder::setState(state);
00844 fixed_searcher.setState(*state);
00845
00846 CheckHashRecord *record = table.find(key);
00847 if (! record)
00848 {
00849 const PieceStand white_stand(WHITE, *state);
00850
00851 CheckHashRecord *root = table.root();
00852 root->distance = path.getDepth()-1;
00853 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
00854 }
00855 if (record->proofDisproof().isFinal())
00856 {
00857 if (record->hasBestMove())
00858 best_move = record->bestMove->move;
00859 check_assert((record->proof() != 0) ||
00860 (record->hasBestMove() && best_move.isValid()));
00861 return record->proofDisproof();
00862 }
00863 assert(record->parent);
00864 if (record->findLoop(path, table.getTwinTable()))
00865 return ProofDisproof::LoopDetection();
00866 if (total_node_count>total_node_limit)
00867 return ProofDisproof::Unknown();
00868 search_node_limit=std::min(search_node_limit,total_node_limit-total_node_count);
00869 this->search_node_limit = search_node_limit;
00870 unsigned int proof_number = record->proof();
00871 unsigned int disproof_number = record->disproof();
00872 if ((ROOT_PROOF_TOL <= proof_number)
00873 || (ROOT_DISPROOF_TOL <= disproof_number))
00874 return record->proofDisproof();
00875 size_t continuousNoExpandLoop = 0;
00876 CheckmateRecorder::rootLog("hasCheckmateMove start", table.size(),
00877 continuousNoExpandLoop);
00878
00879 if (record->isVisited)
00880 return ProofDisproof::LoopDetection();
00881 for (;;)
00882 {
00883 assert(path == root_path);
00884 const size_t nodeSizeAtRoot = table.size();
00885 CheckmateRecorder::setNextMove(0);
00886 attack<P>(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL, record->parent, record);
00887 record->isVisited = false;
00888 if (record->findLoop(path, table.getTwinTable()))
00889 {
00890 clearNodeCount();
00891 return ProofDisproof::LoopDetection();
00892 }
00893 proof_number=record->proof();
00894 disproof_number=record->disproof();
00895 check_assert(!(proof_number==0 && disproof_number==0));
00896 if (proof_number == 0 || disproof_number==0
00897 || exceedNodeCount(proof_number)
00898 || exceedRootTolerance(proof_number, disproof_number, continuousNoExpandLoop))
00899 {
00900 if (record->hasBestMove())
00901 {
00902 best_move = record->bestMove->move;
00903 check_assert((disproof_number == 0) || best_move.isValid());
00904 }
00905 check_assert((proof_number != 0) || (record->hasBestMove() && best_move.isValid()));
00906 clearNodeCount();
00907 return record->proofDisproof();
00908 }
00909 if (nodeSizeAtRoot == table.size())
00910 ++continuousNoExpandLoop;
00911 else
00912 continuousNoExpandLoop = 0;
00913 CheckmateRecorder::rootLog("hasCheckmateMove", table.size(), continuousNoExpandLoop);
00914 }
00915 }
00916
00917 template <class Table,class HEstimator,class CostEstimator>
00918 template<osl::Player P>
00919 const osl::checkmate::ProofDisproof osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
00920 hasEscapeMove(state_t& s, const HashKey& root_key, const PathEncoding& root_path,
00921 size_t search_node_limit, Move last_move)
00922 {
00923 assert(P == attacker);
00924 assert(s.getTurn()==alt(P));
00925 assert(node_count == 0);
00926 state = &s;
00927 path = root_path;
00928 key = root_key;
00929 CheckmateRecorder::setState(state);
00930 fixed_searcher.setState(*state);
00931 check_assert(state->hasEffectBy(P,(*state).template getKingPosition<PlayerTraits<P>::opponent>()));
00932
00933 CheckHashRecord *record = table.find(key);
00934 if (! record)
00935 {
00936 const PieceStand white_stand(WHITE, *state);
00937 CheckHashRecord *root = table.root();
00938 root->distance = path.getDepth()-1;
00939 root->moves.setOne(CheckMove(last_move), table.listProvider());
00940 root->bestMove = &*root->moves.begin();
00941 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
00942 }
00943 if (record->proofDisproof().isFinal())
00944 {
00945 if (record->proofDisproof().isPawnDropFoul(last_move))
00946 return ProofDisproof::PawnCheckmate();
00947 return record->proofDisproof();
00948 }
00949 if (record->findLoop(path, table.getTwinTable()))
00950 return ProofDisproof::LoopDetection();
00951 if (total_node_count>total_node_limit)
00952 return ProofDisproof::Unknown();
00953 search_node_limit=std::min(search_node_limit,total_node_limit-total_node_count);
00954 this->search_node_limit = search_node_limit;
00955
00956 unsigned int proof_number = record->proof();
00957 unsigned int disproof_number = record->disproof();
00958 if ((ROOT_PROOF_TOL <= proof_number)
00959 || (ROOT_DISPROOF_TOL <= disproof_number))
00960 return record->proofDisproof();
00961 size_t continuousNoExpandLoop = 0;
00962 CheckmateRecorder::rootLog("hasEscapeMove start", table.size(),
00963 continuousNoExpandLoop);
00964
00965 if (record->isVisited)
00966 return ProofDisproof::LoopDetection();
00967 for (;;)
00968 {
00969 const size_t nodeSizeAtRoot = table.size();
00970 check_assert(path == root_path);
00971 CheckmateRecorder::setNextMove(0);
00972 defense<P>(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL, record->parent, record);
00973 record->isVisited = false;
00974 proof_number=record->proof();
00975 disproof_number=record->disproof();
00976 check_assert(!(proof_number==0 && disproof_number==0));
00977 if (record->findLoop(path, table.getTwinTable()))
00978 {
00979 clearNodeCount();
00980 return ProofDisproof::LoopDetection();
00981 }
00982 if (record->proofDisproof().isFinal()
00983 || exceedNodeCount(proof_number)
00984 || exceedRootTolerance(proof_number, disproof_number, continuousNoExpandLoop))
00985 {
00986 clearNodeCount();
00987 if (record->proofDisproof().isPawnDropFoul(last_move))
00988 return ProofDisproof::PawnCheckmate();
00989 return record->proofDisproof();
00990 }
00991 if (nodeSizeAtRoot == table.size())
00992 ++continuousNoExpandLoop;
00993 else
00994 continuousNoExpandLoop = 0;
00995 CheckmateRecorder::rootLog("hasEscapeMove", table.size(), continuousNoExpandLoop);
00996 }
00997 }
00998
00999 #endif
01000
01001
01002
01003