00001
00002
00003 #include "osl/ntesuki/ntesukiSimulationSearcher.h"
00004 #include "osl/ntesuki/oracleProverLight.h"
00005 #include "osl/ntesuki/ntesukiExceptions.h"
00006 #include "osl/ntesuki/ntesukiRecord.h"
00007 #include "osl/container/moveVector.h"
00008 #include "osl/move_classifier/safeMove.h"
00009 #include "osl/apply_move/applyMoveWithPath.h"
00010 #include "osl/checkmate/immediateCheckmate.h"
00011 #include "osl/effect_util/effectUtil.h"
00012 #ifdef NDEBUG
00013 # include "osl/ntesuki/ntesukiMove.tcc"
00014 # include "osl/ntesuki/ntesukiRecord.tcc"
00015
00016 #endif
00017
00018 using namespace osl;
00019 using namespace osl::ntesuki;
00020
00021 #ifndef RETURN
00022 #ifndef NDEBUG
00023 #define RETURN \
00024 ntesuki_assert(result.isCheckmateSuccess() ==\
00025 record->getValueWithPath<A>(pass_left, path).isCheckmateSuccess());\
00026 if (record->getValueWithPath<A>(pass_left, path).proof() == 0)\
00027 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).disproof() > ProofDisproof::DISPROOF_LIMIT);\
00028 if (record->getValueWithPath<A>(pass_left, path).disproof() == 0)\
00029 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).proof() > ProofDisproof::PROOF_LIMIT);\
00030 return
00031 #else
00032 #define RETURN return
00033 #endif
00034 #endif
00035
00036
00037
00038
00039 template <class Searcher, Player P>
00040 class
00041 NtesukiSimulationSearcher::
00042 AttackHelperProof
00043 {
00044 Searcher* searcher;
00045 NtesukiRecord *record;
00046 const NtesukiRecord *record_orig;
00047 unsigned int pass_left;
00048 const Move last_move;
00049 public:
00050 AttackHelperProof(Searcher* searcher,
00051 NtesukiRecord* record,
00052 const NtesukiRecord* record_orig,
00053 unsigned int pass_left,
00054 const Move last_move)
00055 : searcher(searcher),
00056 record(record), record_orig(record_orig),
00057 pass_left(pass_left),
00058 last_move(last_move)
00059 {}
00060
00061 void operator()(Position p)
00062 {
00063 (*searcher).template defenseForProof<PlayerTraits<P>::opponent>
00064 (record, record_orig, pass_left, last_move);
00065 }
00066 };
00067
00068 template <class Searcher, Player P>
00069 class NtesukiSimulationSearcher::
00070 DefenseHelperProof
00071 {
00072 Searcher* searcher;
00073 NtesukiRecord *record;
00074 const NtesukiRecord *record_orig;
00075 unsigned int pass_left;
00076 const Move last_move;
00077 public:
00078 DefenseHelperProof(Searcher* searcher,
00079 NtesukiRecord* record,
00080 const NtesukiRecord* record_orig,
00081 unsigned int pass_left,
00082 const Move last_move)
00083 : searcher(searcher),
00084 record(record), record_orig(record_orig),
00085 pass_left(pass_left),
00086 last_move(last_move)
00087 {}
00088
00089 void operator()(Position p)
00090 {
00091 (*searcher).template attackForProof<PlayerTraits<P>::opponent>
00092 (record, record_orig, pass_left, last_move);
00093 }
00094 };
00095
00096
00097
00098
00099 class CountChildLock
00100 {
00101 public:
00102 CountChildLock(NtesukiRecord* r,
00103 const NtesukiTable& t)
00104 : record(r), table(t)
00105 {
00106 size_start = table.size();
00107 }
00108
00109 ~CountChildLock()
00110 {
00111 record->addChildCount(table.size() - size_start);
00112 }
00113 private:
00114 osl::ntesuki::NtesukiRecord* record;
00115 const osl::ntesuki::NtesukiTable& table;
00116 unsigned int size_start;
00117 };
00118
00119
00120
00121
00122
00123
00127 template <Player P>
00128 bool
00129 NtesukiSimulationSearcher::
00130 isSafeMove(const Move move,
00131 int pass_left)
00132 {
00133 if (!state.isValidMove(move, false)) return false;
00134
00135 if (move.isDrop()) return true;
00136
00137 return move_classifier::SafeMove<P>::isMember(state, move.ptype(), move.from(), move.to());
00138 }
00139
00140 template <Player P>
00141 void
00142 NtesukiSimulationSearcher::
00143 attackForProof(NtesukiRecord* record,
00144 const NtesukiRecord* record_orig,
00145 const unsigned int pass_left,
00146 const Move last_move)
00147 {
00148 CountChildLock cclock(record, table);
00149 const Player A = P;
00150 #ifndef NDEBUG
00151 const Player O = PlayerTraits<P>::opponent;
00152 #endif
00153 ++node_count;
00154 ntesuki_assert(P == state.getTurn());
00155
00156 ntesuki_assert(record);
00157 ntesuki_assert(!record->getValueWithPath<A>(pass_left, path).isFinal());
00158 ntesuki_assert(record->getBestMove<A>(pass_left).isInvalid());
00159
00160 ntesuki_assert(record_orig);
00161 ntesuki_assert(record_orig->getValueWithPath<A>(pass_left, path).isCheckmateSuccess());
00162 ntesuki_assert(record_orig->getBestMove<A>(pass_left).isValid());
00163
00164 ntesuki_assert(!EffectUtil::isKingInCheck(O, state));
00165
00166 if (record->isVisited())
00167 {
00168 result = ProofDisproof::LoopDetection();
00169 RETURN;
00170 }
00171
00172
00173 if (record->setUpNode<P>())
00174 {
00175 const NtesukiResult result_cur = record->getValueWithPath<A>(pass_left, path);
00176 if (result_cur.isCheckmateSuccess())
00177 {
00178
00179 result = ProofDisproof::Checkmate();
00180 RETURN;
00181 }
00182 else if (result_cur.isFinal())
00183 {
00184 result = result_cur;
00185 RETURN;
00186 }
00187 }
00188
00189
00190 const NtesukiMove best_move_orig = record_orig->getBestMove<A>(pass_left);
00191 if (best_move_orig.isImmediateCheckmate())
00192 {
00193 result = ProofDisproof::NoCheckmate();
00194 RETURN;
00195 }
00196
00197 NtesukiRecord::VisitLock visitLock(record);
00198
00199 if ((pass_left > 0) &&
00200 record_orig->getValueWithPath<A>(pass_left - 1, path)
00201 .isCheckmateSuccess())
00202 {
00203 if (record->getValueWithPath<A>(pass_left - 1, path)
00204 .isCheckmateFail())
00205 {
00206 result = ProofDisproof::NoCheckmate();
00207 RETURN;
00208 }
00209
00210 ntesuki_assert(!record->getValueWithPath<A>(pass_left - 1, path)
00211 .isFinal());
00212 NtesukiRecord::UnVisitLock unVisitLock(record);
00213
00214 TRY_DFPN;
00215 attackForProof<P>(record, record_orig, pass_left - 1, last_move);
00216 CATCH_DFPN;
00217 RETURN;
00218 }
00219
00220 const Move move = adjustMove<P>(best_move_orig.getMove());
00221
00222
00223 if (!move.isValid() ||
00224 !isSafeMove<P>(move, pass_left))
00225 {
00226 result = ProofDisproof::NoCheckmate();
00227 RETURN;
00228 }
00229
00230 const bool move_is_check = (move_classifier::PlayerMoveAdaptor<move_classifier::Check>::
00231 isMember(state, move));
00232 if (0 == pass_left && !move_is_check)
00233 {
00234 result = ProofDisproof::NoCheckmate();
00235 RETURN;
00236 }
00237 if (move_is_check != best_move_orig.isCheck())
00238 {
00239 result = ProofDisproof::NoCheckmate();
00240 RETURN;
00241 }
00242
00243
00244
00245 NtesukiRecord *record_child = table.allocateWithMove(record, move);
00246 if (record_child == 0)
00247 {
00248 result = ProofDisproof::NoCheckmate();
00249 RETURN;
00250 }
00251 const NtesukiRecord* record_child_orig = table.findWithMoveConst(record_orig,
00252 best_move_orig);
00253 if (!record_child_orig)
00254 {
00255 result = ProofDisproof::NoCheckmate();
00256 RETURN;
00257 }
00258
00259 result = record_child->getValueWithPath<A>(pass_left, path);
00260 if (result.isUnknown())
00261 {
00262 AttackHelperProof<NtesukiSimulationSearcher, P> helper(this,
00263 record_child,
00264 record_child_orig,
00265 pass_left,
00266 move);
00267 TRY_DFPN;
00268 ApplyMoveWithPath<P>::doUndoMove(state, path, move, helper);
00269 if (record->getValueWithPath<A>(pass_left, path).isFinal())
00270 {
00271 result = record->getValueWithPath<A>(pass_left, path);
00272 RETURN;
00273 }
00274 CATCH_DFPN;
00275 }
00276
00277 if (result.isPawnDropFoul(move))
00278 {
00279 result = ProofDisproof::PawnCheckmate();
00280 RETURN;
00281 }
00282 else if (result.isCheckmateSuccess())
00283 {
00284 result = ProofDisproof::Checkmate();
00285 NtesukiMove best_move(move);
00286
00287 TRY_DFPN;
00288 best_move.setCheckmateSuccess<A>(pass_left);
00289 record->setResult<A>(pass_left, result, best_move, true);
00290 CATCH_DFPN;
00291 RETURN;
00292 }
00293 else if (result == ProofDisproof::LoopDetection())
00294 {
00295 result = ProofDisproof::NoCheckmate();
00296 }
00297
00298 ntesuki_assert(result.isCheckmateFail());
00299 RETURN;
00300 }
00301
00302 template <Player P>
00303 void NtesukiSimulationSearcher::
00304 defenseForProof(NtesukiRecord* record,
00305 const NtesukiRecord* record_orig,
00306 const unsigned int pass_left,
00307 const Move last_move)
00308 {
00309 CountChildLock cclock(record, table);
00310 const Player A = PlayerTraits<P>::opponent;
00311 const Player O = PlayerTraits<P>::opponent;
00312
00313 ++node_count;
00314 ntesuki_assert(P == state.getTurn());
00315
00316 ntesuki_assert(record);
00317 if (!record_orig)
00318 {
00319 result = ProofDisproof::NoCheckmate();
00320 return;
00321 }
00322
00323 if (EffectUtil::isKingInCheck(O, state))
00324 {
00325
00326 result = ProofDisproof::NoCheckmate();
00327 return;
00328 }
00329
00330
00331 if (record->setUpNode<P>())
00332 {
00333 result = record->getValueWithPath<A>(pass_left, path);
00334 if (result.isFinal())
00335 {
00336 return;
00337 }
00338 }
00339
00340
00341 if (!record_orig->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
00342 {
00343 result = ProofDisproof::NoCheckmate();
00344 return;
00345 }
00346
00347 if (record->isVisited())
00348 {
00349 result = ProofDisproof::LoopDetection();
00350 RETURN;
00351 }
00352 NtesukiRecord::VisitLock visitLock(record);
00353
00354
00355 const bool invalidAttack = EffectUtil::isKingInCheck(PlayerTraits<P>::opponent, state);
00356 if (invalidAttack)
00357 {
00358 result = ProofDisproof::AttackBack();
00359 RETURN;
00360 }
00361
00362
00363 if (pass_left > 0 &&
00364 record_orig->getValueWithPath<A>(pass_left - 1, path)
00365 .isCheckmateSuccess())
00366 {
00367 result = (record->getValueWithPath<A>(pass_left - 1, path));
00368 if(result.isCheckmateFail())
00369 {
00370 RETURN;
00371 }
00372 ntesuki_assert(!record->getValueWithPath<A>(pass_left - 1, path)
00373 .isFinal());
00374 NtesukiRecord::UnVisitLock unVisitLock(record);
00375
00376 TRY_DFPN;
00377 defenseForProof<P>(record, record_orig, pass_left - 1, last_move);
00378 CATCH_DFPN;
00379 RETURN;
00380 }
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390 NtesukiMoveList moves;
00391 record->generateMoves<P>(moves, 0, true);
00392 result = ProofDisproof::Checkmate();
00393
00394 if (moves.empty())
00395 {
00396 result = ProofDisproof::NoEscape();
00397 TRY_DFPN;
00398 record->setResult<A>(pass_left, result,
00399 NtesukiMove::INVALID(), false);
00400
00401 CATCH_DFPN;
00402 RETURN;
00403 }
00404
00405 bool some_moves_not_generated = false;
00406 for (NtesukiMoveList::iterator move_it = moves.begin();
00407 move_it != moves.end(); move_it++)
00408 {
00409 NtesukiMove& move = *move_it;
00410 if (move.isCheckmateSuccess<A>(pass_left)) continue;
00411
00412
00413 if (isscheme != NtesukiRecord::normal_is &&
00414 isscheme != NtesukiRecord::delay_is &&
00415 move.isCheck() && pass_left > 0) continue;
00416
00417
00418 const NtesukiRecord* record_child_orig = table.findWithMoveConst(record_orig, move);
00419 if (!record_child_orig ||
00420 !record_child_orig->getValue<A>(pass_left).isCheckmateSuccess())
00421 {
00422 some_moves_not_generated = true;
00423 continue;
00424 }
00425
00426 NtesukiRecord *record_child = table.allocateWithMove(record, move);
00427 if (record_child == 0)
00428 {
00429 result = ProofDisproof::NoCheckmate();
00430 RETURN;
00431 }
00432
00433 if(record_child->isVisited())
00434 {
00435 result = ProofDisproof::LoopDetection();
00436 record->setLoopWithPath<A>(pass_left, path);
00437 TRY_DFPN;
00438 record->setResult<A>(pass_left, NtesukiResult(1, 1),
00439 NtesukiMove::INVALID(), false);
00440 CATCH_DFPN;
00441 RETURN;
00442 }
00443
00444 int pass_left_child = pass_left;
00445 if (move.isPass()) --pass_left_child;
00446 const PathEncoding path_child(path, move.getMove());
00447 result = record_child->getValueWithPath<A>(pass_left_child, path_child);
00448 if (result.isUnknown())
00449 {
00450 DefenseHelperProof<NtesukiSimulationSearcher, P> helper(this,
00451 record_child,
00452 record_child_orig,
00453 pass_left_child,
00454 move.getMove());
00455 TRY_DFPN;
00456 ApplyMoveWithPath<P>::doUndoMoveOrPass(state, path,
00457 move.getMove(),
00458 helper);
00459 CATCH_DFPN;
00460 if (record->getValueWithPath<A>(pass_left, path).isFinal())
00461 {
00462 result = record->getValueWithPath<A>(pass_left, path);
00463 RETURN;
00464 }
00465 }
00466
00467 if (result.isCheckmateFail())
00468 {
00469 RETURN;
00470 }
00471 }
00472
00473 ntesuki_assert(result.isCheckmateSuccess());
00474
00475 if (some_moves_not_generated)
00476 {
00477 result = ProofDisproof::NoCheckmate();
00478 }
00479 else
00480 {
00481 TRY_DFPN;
00482 record->setResult<A>(pass_left, result,
00483 NtesukiMove::INVALID(), true);
00484 CATCH_DFPN;
00485 }
00486 RETURN;
00487 }
00488
00489
00490
00491 template <Player P>
00492 bool
00493 NtesukiSimulationSearcher::
00494 startFromAttackProof(NtesukiRecord* record,
00495 const NtesukiRecord* record_orig,
00496 const unsigned int pass_left,
00497 const Move last_move)
00498 {
00499 assert(P == state.getTurn());
00500
00501 const Player A = P;
00502 ntesuki_assert(record);
00503 if (!record_orig)
00504 {
00505 return false;
00506 }
00507
00508 if (!record_orig->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
00509 {
00510 return false;
00511 }
00512
00513 if (!record->isDominatedByProofPieces<A>(record_orig, pass_left))
00514 {
00515 return false;
00516 }
00517
00518 TRY_DFPN;
00519 if (record->setUpNode<P>())
00520 {
00521 if (record->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
00522 {
00523
00524 result = ProofDisproof::Checkmate();
00525 return true;
00526 }
00527 else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
00528 {
00529 result = ProofDisproof::NoCheckmate();
00530 return false;
00531 }
00532 }
00533 CATCH_DFPN;
00534
00535 TRY_DFPN;
00536 const NtesukiMove m = (record_orig->getBestMove<A>(pass_left));
00537 if (m.isImmediateCheckmate()) return false;
00538 CATCH_DFPN;
00539
00540 ++proof_count;
00541
00542 TRY_DFPN;
00543 OracleProverLight light(state, mg, path, table,isscheme);
00544 if (light.startFromAttack<P>(record, record_orig, pass_left))
00545 {
00546 ++proof_success_count;
00547 ++light_proof_success_count;
00548 ntesuki_assert(record->getValueWithPath<A>(pass_left, path)
00549 .isCheckmateSuccess());
00550 return true;
00551 }
00552 else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
00553 {
00554 result = ProofDisproof::NoCheckmate();
00555 return false;
00556 }
00557 CATCH_DFPN;
00558
00559 TRY_DFPN;
00560 attackForProof<P>(record, record_orig, pass_left, last_move);
00561 CATCH_DFPN;
00562 if (result.isCheckmateSuccess())
00563 {
00564 ++proof_success_count;
00565 return true;
00566 }
00567 return false;
00568 }
00569
00570 template <Player P>
00571 bool
00572 NtesukiSimulationSearcher::
00573 startFromDefenseProof(NtesukiRecord* record,
00574 const NtesukiRecord* record_orig,
00575 const unsigned int pass_left,
00576 const Move last_move)
00577 {
00578 assert(P == state.getTurn());
00579
00580 const Player A = PlayerTraits<P>::opponent;
00581 ntesuki_assert(record);
00582 if (!record_orig ||
00583 !record_orig->getValueWithPath<A>(pass_left, path).
00584 isCheckmateSuccess())
00585 {
00586 return false;
00587 }
00588
00589 if (!record->isDominatedByProofPieces<A>(record_orig, pass_left))
00590 {
00591 return false;
00592 }
00593
00594 if (record->setUpNode<P>())
00595 {
00596 if (record->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
00597 {
00598
00599 result = ProofDisproof::Checkmate();
00600 return true;
00601 }
00602 else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
00603 {
00604 result = ProofDisproof::NoCheckmate();
00605 return false;
00606 }
00607 }
00608
00609 const NtesukiMove m = (record_orig->getBestMove<A>(pass_left));
00610 if (m.isImmediateCheckmate()) return false;
00611
00612 ++proof_count;
00613
00614 OracleProverLight light(state, mg, path, table, isscheme);
00615 TRY_DFPN;
00616 if (light.startFromDefense<P>(record, record_orig, pass_left))
00617 {
00618 ++proof_success_count;
00619 ++light_proof_success_count;
00620 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).
00621 isCheckmateSuccess());
00622 return true;
00623 }
00624 else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
00625 {
00626 result = ProofDisproof::NoCheckmate();
00627 return false;
00628 }
00629 CATCH_DFPN;
00630
00631 TRY_DFPN;
00632 defenseForProof<P>(record, record_orig, pass_left, last_move);
00633 CATCH_DFPN;
00634
00635 if (result.isCheckmateSuccess())
00636 {
00637 ++proof_success_count;
00638 return true;
00639 }
00640 return false;
00641 }
00642
00643 #undef RETURN
00644
00645
00646
00647
00648