00001
00002
00003 #ifndef _ORACLEPROVER_TCC
00004 #define _ORACLEPROVER_TCC
00005
00006 #include "osl/checkmate/oracleProver.h"
00007 #include "osl/checkmate/checkHashTable.h"
00008 #include "osl/checkmate/checkMoveGenerator.h"
00009 #include "osl/checkmate/checkTableUtil.h"
00010 #include "osl/checkmate/checkmateRecorder.h"
00011 #include "osl/checkmate/proofPieces.h"
00012 #include "osl/checkmate/immediateCheckmate.h"
00013 #include "osl/checkmate/fixedDepthSearcher.tcc"
00014 #include "osl/checkmate/oracleAdjust.h"
00015 #include "osl/apply_move/applyMoveWithPath.h"
00016 #include "osl/effect_util/effectUtil.h"
00017
00018
00019
00020 namespace osl
00021 {
00022 namespace checkmate
00023 {
00027 template <Player P, class Prover>
00028 struct OracleProverDefense
00029 {
00030 Prover *prover;
00031 CheckHashRecord *record;
00032 ProofOracleDefense<P> oracle;
00033 OracleProverDefense(Prover *p,
00034 CheckHashRecord *r, ProofOracleDefense<P> o)
00035 : prover(p), record(r), oracle(o)
00036 {
00037 }
00038 void operator()(Position)
00039 {
00040 (*prover).template defense<P>(record, oracle);
00041 record->isVisited = false;
00042 }
00043 };
00044
00048 template <Player P, class Prover>
00049 struct OracleProverAttack
00050 {
00051 Prover *prover;
00052 CheckHashRecord *record;
00053 ProofOracleAttack<P> oracle;
00054 OracleProverAttack(Prover *p,
00055 CheckHashRecord *r, ProofOracleAttack<P> o)
00056 : prover(p), record(r), oracle(o)
00057 {
00058 }
00059 void operator()(Position)
00060 {
00061 (*prover).template attack<P>(record, oracle);
00062 record->isVisited = false;
00063 }
00064 };
00065
00066 }
00067 }
00068
00069 template <class Table>
00070 template <osl::Player P>
00071 bool osl::checkmate::OracleProver<Table>::
00072 proofWin(state_t& state, const HashKey& key, const PathEncoding& root_path,
00073 ProofOracleAttack<P> oracle, Move& best_move)
00074 {
00075 check_assert(oracle.isValid());
00076 check_assert(state.getTurn() == P);
00077 path = root_path;
00078 this->state = &state;
00079 fixed_searcher.setState(state);
00080 CheckmateRecorder::setState(&state);
00081 this->key = key;
00082
00083 CheckHashRecord *record = table.find(key);
00084 if (! record)
00085 {
00086 const PieceStand white_stand(WHITE, state);
00087 CheckHashRecord *root = table.root();
00088 root->distance = path.getDepth()-1;
00089 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
00090 }
00091 if (! record->proofDisproof().isFinal()
00092 && (! record->findLoop(path, table.getTwinTable())))
00093 {
00094 const bool visitedBeforeAttack = record->isVisited;
00095 CheckmateRecorder::setNextMove(0);
00096 record->isVisited = false;
00097 attack<P>(record, oracle);
00098 record->isVisited = visitedBeforeAttack;
00099 }
00100 if (record->proofDisproof().isCheckmateSuccess())
00101 {
00102 check_assert(record->hasBestMove());
00103 best_move = record->getBestMove()->move;
00104 check_assert(best_move.isValid());
00105 check_assert(best_move.player() == P);
00106 assert(state.isValidMove(best_move));
00107 return true;
00108 }
00109 return false;
00110 }
00111
00112 template <class Table>
00113 template <osl::Player P>
00114 bool osl::checkmate::OracleProver<Table>::
00115 proofLose(state_t& state, const HashKey& key, const PathEncoding& root_path,
00116 ProofOracleDefense<P> oracle, Move last_move)
00117 {
00118 check_assert(oracle.isValid());
00119 check_assert(state.getTurn() == alt(P));
00120 path = root_path;
00121 this->state = &state;
00122 fixed_searcher.setState(state);
00123 CheckmateRecorder::setState(&state);
00124 this->key = key;
00125
00126 CheckHashRecord *record = table.find(key);
00127 if (! record)
00128 {
00129 const PieceStand white_stand(WHITE, state);
00130 CheckHashRecord *root = table.root();
00131 root->distance = path.getDepth()-1;
00132 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
00133 }
00134 if (record->findLoop(path, table.getTwinTable()))
00135 return false;
00136 if (! record->proofDisproof().isFinal())
00137 {
00138 const bool visitedBeforeDefense = record->isVisited;
00139 CheckmateRecorder::setNextMove(0);
00140 record->isVisited = false;
00141 defense<P>(record, oracle);
00142 record->isVisited = visitedBeforeDefense;
00143 }
00144 if (record->proofDisproof().isPawnDropFoul(last_move))
00145 return false;
00146 return record->proofDisproof().isCheckmateSuccess();
00147 }
00148
00149 template <class Table>
00150 template <osl::Player P>
00151 void osl::checkmate::OracleProver<Table>::
00152 testFixedDepthAttack(CheckHashRecord *record, Move guide)
00153 {
00154 PieceStand proof_pieces;
00155 ProofDisproof pdp;
00156 if (guide.isNormal())
00157 pdp = fixed_searcher.hasCheckmateWithGuide<P>(2, guide, proof_pieces);
00158 else
00159 pdp = fixed_searcher.hasCheckmateMove<P>(2, guide, proof_pieces);
00160 if (pdp.isCheckmateSuccess())
00161 {
00162 CheckMove *attack = record->moves.find(guide);
00163 if (attack == 0) {
00164 CheckMove best_move(guide);
00165 record->moves.setOne(best_move, table.listProvider());
00166 attack = &*(record->moves.begin());
00167 }
00168 attack->flags.set(MoveFlags::ImmediateCheckmate);
00169 record->bestMove = attack;
00170 record->setProofPieces(proof_pieces);
00171 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00172 }
00173 else if (pdp.isCheckmateFail())
00174 {
00175
00176 }
00177 else
00178 {
00179 assert(pdp.isUnknown());
00180 record->setProofDisproof(std::max(pdp.proof(), record->proof()),
00181 std::max(pdp.disproof(), record->disproof()));
00182 }
00183 }
00184
00185 template <class Table>
00186 template <osl::Player P>
00187 void osl::checkmate::OracleProver<Table>::
00188 testFixedDepthDefense(CheckHashRecord *record, CheckMove& next_move)
00189 {
00190 PieceStand proof_pieces;
00191 Move check_move;
00192 const ProofDisproof pdp
00193 = fixed_searcher.hasEscapeByMove<P>(next_move.move, 2, check_move,
00194 proof_pieces);
00195 if (pdp.isCheckmateSuccess())
00196 {
00197 CheckTableUtil::registerImmediateCheckmateInDefense<P,Table>
00198 (key, path, record, next_move, pdp, check_move, proof_pieces, table);
00199 }
00200 else if (pdp.isCheckmateFail())
00201 {
00202
00203 }
00204 else
00205 {
00206 assert(pdp.isUnknown());
00207 record->setProofDisproof(std::max(pdp.proof(), record->proof()),
00208 std::max(pdp.disproof(), record->disproof()));
00209 }
00210 }
00211
00212 template <class Table>
00213 template <osl::Player P>
00214 void osl::checkmate::OracleProver<Table>::
00215 attack(CheckHashRecord *record, ProofOracleAttack<P> oracle)
00216 {
00217 ++node_count;
00218 #ifndef NDEBUG
00219 CheckmateRecorder::Tracer tracer("oracle attack ", record,
00220 key, path, 0, 0);
00221 #endif
00222 check_assert(state->getTurn() == P);
00223 check_assert(record);
00224 check_assert(! record->proofDisproof().isFinal());
00225 check_assert(! record->findLoop(path, table.getTwinTable()));
00226 check_assert(! record->isVisited);
00227 check_assert(oracle.isValid());
00228 record->isVisited = true;
00229 #ifdef CHECKMATE_DEBUG
00230 const Position targetKingPosition
00231 =(*state).template getKingPosition<PlayerTraits<P>::opponent>();
00232 check_assert(! state->hasEffectBy(P,targetKingPosition));
00233 #endif
00234 if (record->needMoveGeneration())
00235 {
00236 Move check_move;
00237 if ((! EffectUtil::isKingInCheck(P, *state))
00238 && ImmediateCheckmate::hasCheckmateMove<P>(*state, check_move))
00239 {
00240 CheckMove best_move(check_move);
00241 best_move.flags.set(MoveFlags::ImmediateCheckmate);
00242 record->moves.setOne(best_move, table.listProvider());
00243 record->bestMove = &*(record->moves.begin());
00244 PieceStand proof_pieces;
00245 if (check_move.isDrop())
00246 proof_pieces.add(check_move.ptype());
00247 record->setProofPieces(proof_pieces);
00248 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00249 return;
00250 }
00251 if (oracle.guide && oracle.guide->hasBestMove()
00252 && oracle.guide->getBestMove()->flags.isSet(MoveFlags::ImmediateCheckmate))
00253 {
00254 testFixedDepthAttack<P>(record, oracle.guide->getBestMove()->move);
00255 return;
00256 }
00257 }
00258 ProofOracleDefense<P> new_oracle = oracle.expandOracle();
00259 if (! new_oracle.isValid()) {
00260 testFixedDepthAttack<P>(record, Move::INVALID());
00261 return;
00262 }
00263 check_assert(oracle.oracle().player() == P);
00264 Move check_move = OracleAdjust::attack(*state, oracle.oracle());
00265 if (! check_move.isNormal())
00266 return;
00267 if (record->moves.empty())
00268 CheckMoveGenerator<P>::generateAttack(*state, table.listProvider(),
00269 record->moves);
00270
00271 record->bestMove = 0;
00272 for (CheckMoveList::iterator p=record->moves.begin();
00273 p!=record->moves.end(); ++p)
00274 {
00275 if (p->move == check_move)
00276 {
00277 if (! p->flags.isSet(MoveFlags::Solved))
00278 record->bestMove = &*p;
00279 break;
00280 }
00281 }
00282 unsigned int best_move_proof = 1;
00283 unsigned int best_move_disproof = 1;
00284 HashKey new_key;
00285 PathEncoding new_path;
00286
00287 if (! record->hasBestMove())
00288 goto failure_end;
00289
00290 check_assert(record->hasBestMove()
00291 && (record->getBestMove()->move == check_move));
00292 new_key = key.newHashWithMove(check_move);
00293 new_path = PathEncoding(path, check_move);
00294
00295 if (! record->getBestMove()->record)
00296 {
00297 CheckTableUtil::allocate(check_move, record->getBestMove()->record, table,
00298 new_key, new_path, record);
00299 if (record->proofDisproof().isFinal())
00300 {
00301 if (record->proofDisproof().isCheckmateSuccess())
00302 check_assert(record->hasBestMove());
00303 return;
00304 }
00305 }
00306
00307 if ((! record->getBestMove()->record->isVisited)
00308 && (! record->getBestMove()->findLoop(path, table.getTwinTable())))
00309 {
00310 const ProofDisproof& pdp = record->getBestMove()->record->proofDisproof();
00311 if (! pdp.isFinal())
00312 {
00313 OracleProverDefense<P,OracleProver>
00314 oracle_prover(this, record->getBestMove()->record, new_oracle);
00315 CheckmateRecorder::setNextMove(&*record->getBestMove());
00316
00317 std::swap(key, new_key);
00318 std::swap(path, new_path);
00319
00320 ApplyMove<P>::doUndoMove(*state, check_move, oracle_prover);
00321
00322 key = new_key;
00323 path = new_path;
00324
00325 if (record->proofDisproof().isFinal())
00326 {
00327 if (record->proofDisproof().isCheckmateSuccess())
00328 check_assert(record->hasBestMove());
00329 return;
00330 }
00331 }
00332 if (pdp.isCheckmateSuccess() && (! pdp.isPawnDropFoul(check_move)))
00333 {
00334 if (! record->proofDisproof().isCheckmateSuccess())
00335 {
00336 check_assert(record->bestMove->record->hasProofPieces());
00337 record->setProofPiecesAttack(P);
00338 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
00339 check_assert(record->isConsistent());
00340 }
00341 return;
00342 }
00343 if (! pdp.isFinal())
00344 {
00345
00346 best_move_proof = pdp.proof();
00347 best_move_disproof = pdp.disproof();
00348 }
00349 }
00350 record->bestMove = 0;
00351 failure_end:
00352 if (record->moves.empty())
00353 {
00354 record->setDisproofPieces(DisproofPieces::leaf(*state, alt(P),
00355 record->stand(alt(P))));
00356 record->propagateNoCheckmate<P>(ProofDisproof::NoCheckmate());
00357 }
00358 else
00359 {
00360 check_assert(best_move_proof < ProofDisproof::PROOF_LIMIT);
00361 check_assert(best_move_disproof < ProofDisproof::DISPROOF_LIMIT);
00362 check_assert(! record->proofDisproof().isFinal());
00363 record->setProofDisproof(std::max(record->proof(),
00364 best_move_proof/4),
00365 std::max((size_t)record->disproof(),
00366 best_move_disproof + record->moves.size()));
00367 }
00368 return;
00369 }
00370
00371 template <class Table>
00372 template <osl::Player P>
00373 void osl::checkmate::OracleProver<Table>::
00374 defense(CheckHashRecord *record, ProofOracleDefense<P> oracle)
00375 {
00376 ++node_count;
00377 #ifndef NDEBUG
00378 CheckmateRecorder::Tracer tracer("oracle defense", record,
00379 key, path, 0, 0);
00380 #endif
00381 check_assert(oracle.isValid());
00382 check_assert(record);
00383 check_assert(! record->findLoop(path, table.getTwinTable()));
00384 check_assert(! record->proofDisproof().isFinal());
00385 check_assert(! record->isVisited);
00386 record->isVisited = true;
00387 #ifndef NDEBUG
00388 const Position attack_king_position=(*state).template getKingPosition<P>();
00389 const Position defense_king_position=(*state).template getKingPosition<PlayerTraits<P>::opponent>();
00390
00391
00392 check_assert((attack_king_position.isPieceStand()
00393 || ! state->hasEffectBy(alt(P),attack_king_position))
00394 && state->hasEffectBy(P,defense_king_position));
00395 #endif
00396 if (record->needMoveGeneration())
00397 {
00398 CheckMoveGenerator<P>::generateEscape(*state, table.listProvider(),
00399 record->moves);
00400 if (record->moves.empty())
00401 {
00402 record->setProofPieces(ProofPieces::leaf(*state, P, record->stand(P)));
00403 record->propagateCheckmate<P>(ProofDisproof::NoEscape());
00404 check_assert(record->isConsistent());
00405 return;
00406 }
00407 check_assert(record->moves.size());
00408 record->setProofDisproof(std::max((size_t)record->proofDisproof().proof(),
00409 record->moves.size()),
00410 record->proofDisproof().disproof());
00411 }
00412 examine_moves:
00413 int proved = 0;
00414 unsigned int sum_proof = 0;
00415 unsigned int min_disproof = ProofDisproof::DISPROOF_LIMIT;
00416 for (CheckMoveList::iterator p=record->moves.begin();
00417 p!=record->moves.end(); ++p)
00418 {
00419 check_assert(p->move.player() == alt(P));
00420 if (! record->filter.isTarget(p->flags))
00421 continue;
00422
00423 HashKey new_key = key.newHashWithMove(p->move);
00424 PathEncoding new_path(path, p->move);
00425 if (! p->record)
00426 {
00427 CheckTableUtil::allocate(p->move, p->record, table,
00428 new_key, new_path, record);
00429 }
00430 if (p->record->isVisited)
00431 {
00432 record->bestMove = &*p;
00433 record->setLoopDetection(path, *p, p->record);
00434 return;
00435 }
00436 if (const TwinEntry *loop = p->findLoop(path, table.getTwinTable()))
00437 {
00438 record->bestMove = &*p;
00439 record->setLoopDetectionTryMerge<P>(path, *p, loop->loopTo);
00440 return;
00441 }
00442 const ProofDisproof& pdp = p->record->proofDisproof();
00443 if (! pdp.isFinal())
00444 {
00445 ProofOracleAttack<P> new_oracle = oracle.expandOracle(p->move);
00446 if (! new_oracle.isValid()) {
00447 testFixedDepthDefense<P>(record, *p);
00448 if (record->proofDisproof().isCheckmateSuccess())
00449 continue;
00450 return;
00451 }
00452 OracleProverAttack<P,OracleProver>
00453 oracle_prover(this, p->record, new_oracle);
00454 CheckmateRecorder::setNextMove(&*p);
00455
00456 std::swap(key, new_key);
00457 std::swap(path, new_path);
00458
00459 ApplyMove<PlayerTraits<P>::opponent>::
00460 doUndoMove(*state, p->move, oracle_prover);
00461
00462 key = new_key;
00463 path = new_path;
00464 }
00465 if (! pdp.isCheckmateSuccess())
00466 {
00467 record->bestMove = &*p;
00468 if (pdp.isCheckmateFail())
00469 {
00470 if (! record->proofDisproof().isCheckmateFail())
00471 {
00472 assert(! pdp.isLoopDetection());
00473 record->setDisproofPiecesDefense(alt(P));
00474 record->propagateNoCheckmate<P>(pdp);
00475 }
00476 return;
00477 }
00478 if (const TwinEntry *loop = p->findLoop(path, table.getTwinTable()))
00479 {
00480 record->bestMove = &*p;
00481 record->setLoopDetectionTryMerge<P>(path, *p, loop->loopTo);
00482 return;
00483 }
00484 sum_proof += pdp.proof();
00485 min_disproof = std::min(min_disproof, pdp.disproof());
00486 continue;
00487 }
00488 ++proved;
00489 record->addToSolvedInDefense(*p, p->record->proofDisproof());
00490 }
00491 if (sum_proof && (proved == 0))
00492 {
00493 CheckmateRecorder::setLeaveReason("no checkmate found");
00494 assert(min_disproof < ProofDisproof::DISPROOF_LIMIT);
00495 assert(sum_proof < ProofDisproof::PROOF_LIMIT);
00496 check_assert(! record->proofDisproof().isFinal());
00497 record->setProofDisproof(std::max(record->proof(), sum_proof),
00498 std::max(record->disproof(), min_disproof));
00499 return;
00500 }
00501 if (sum_proof)
00502 goto examine_moves;
00503 if (! record->filter.isTarget(MoveFlags::BlockingBySacrifice))
00504 {
00505 record->filter.addTarget(MoveFlags::BlockingBySacrifice);
00506 goto examine_moves;
00507 }
00508 if (! record->filter.isTarget(MoveFlags::Upward))
00509 {
00510 record->filter.addTarget(MoveFlags::Upward);
00511 record->useMaxInsteadOfSum = true;
00512 goto examine_moves;
00513 }
00514
00515 if (! record->proofDisproof().isCheckmateSuccess())
00516 {
00517 record->setProofPieces(ProofPieces::defense(record->moves, *state,
00518 record->stand(P)));
00519 record->propagateCheckmate<P>(record->bestResultInSolved);
00520 }
00521 check_assert(record->proofDisproof().isCheckmateSuccess());
00522 check_assert(record->isConsistent());
00523 return;
00524 }
00525
00526 template <class Table>
00527 bool osl::checkmate::OracleProver<Table>::
00528 proofWin(state_t& state, const PathEncoding& path,
00529 const CheckHashRecord *record, Move& best_move)
00530 {
00531 const HashKey key = HashKey::calcHash(state);
00532 if (state.getTurn() == BLACK)
00533 {
00534 ProofOracleAttack<BLACK> oracle(record);
00535 return proofWin(state, key, path, oracle, best_move);
00536 }
00537 else
00538 {
00539 ProofOracleAttack<WHITE> oracle(record);
00540 return proofWin(state, key, path, oracle, best_move);
00541 }
00542 }
00543
00544 template <class Table>
00545 bool osl::checkmate::OracleProver<Table>::
00546 proofLose(state_t& state, const PathEncoding& path,
00547 const CheckHashRecord *record, Move last_move)
00548 {
00549 const HashKey key = HashKey::calcHash(state);
00550 if (state.getTurn() == BLACK)
00551 {
00552 ProofOracleDefense<WHITE> oracle(record);
00553 return proofLose(state, key, path, oracle, last_move);
00554 }
00555 else
00556 {
00557 ProofOracleDefense<BLACK> oracle(record);
00558 return proofLose(state, key, path, oracle, last_move);
00559 }
00560 }
00561
00562
00563 #endif
00564
00565
00566
00567