00001
00002
00003 #include "osl/ntesuki/ntesukiSimulationSearcher.h"
00004 #include "osl/state/hashEffectState.h"
00005
00006 #include "osl/ntesuki/ntesukiRecord.h"
00007 #include "osl/ntesuki/ntesukiExceptions.h"
00008 #include "osl/container/moveVector.h"
00009 #include "osl/move_classifier/moveAdaptor.h"
00010 #include "osl/apply_move/applyMoveWithPath.h"
00011
00012 #ifndef NDEBUG
00013 #define RETURN \
00014 TRY_DFPN;\
00015 ntesuki_assert(result.isFinal());\
00016 CATCH_DFPN; \
00017 return
00018 #else
00019 #define RETURN return
00020 #endif
00021
00022 using namespace osl;
00023 using namespace osl::ntesuki;
00024
00025 template <class Searcher, Player P>
00026 class
00027 NtesukiSimulationSearcher::
00028 AttackHelperDisproof
00029 {
00030 Searcher* searcher;
00031 NtesukiRecord* record;
00032 const NtesukiRecord* record_orig;
00033 unsigned int pass_left;
00034 const Move last_move;
00035
00036 public:
00037 AttackHelperDisproof(Searcher* searcher,
00038 NtesukiRecord* record,
00039 const NtesukiRecord* record_orig,
00040 unsigned int pass_left,
00041 const Move last_move)
00042 : searcher(searcher),
00043 record(record), record_orig(record_orig),
00044 pass_left(pass_left),
00045 last_move(last_move)
00046 {}
00047
00048 void operator()(Position p)
00049 {
00050 (*searcher).template defenseForDisproof<PlayerTraits<P>::opponent>
00051 (record, record_orig, pass_left, last_move);
00052 }
00053 };
00054
00055 template <class Searcher, Player P>
00056 class NtesukiSimulationSearcher::
00057 DefenseHelperDisproof
00058 {
00059 Searcher* searcher;
00060 NtesukiRecord* record;
00061 const NtesukiRecord* record_orig;
00062 unsigned int pass_left;
00063 const Move last_move;
00064 public:
00065 DefenseHelperDisproof(Searcher* searcher,
00066 NtesukiRecord* record,
00067 const NtesukiRecord* record_orig,
00068 unsigned int pass_left,
00069 const Move last_move)
00070 : searcher(searcher),
00071 record(record), record_orig(record_orig),
00072 pass_left(pass_left),
00073 last_move(last_move)
00074 {}
00075
00076
00077 void operator()(Position p)
00078 {
00079 (*searcher).template attackForDisproof<PlayerTraits<P>::opponent>
00080 (record, record_orig, pass_left, last_move);
00081 }
00082 };
00083
00084
00085
00086
00087
00088
00089 template <Player P>
00090 void
00091 NtesukiSimulationSearcher::
00092 attackForDisproof(NtesukiRecord* record,
00093 const NtesukiRecord* record_orig,
00094 const unsigned int pass_left,
00095 const Move last_move)
00096 {
00097 const Player attacker = P;
00098 ++node_count;
00099 ntesuki_assert(P == state.getTurn());
00100
00101 ntesuki_assert(record);
00102 ntesuki_assert(record->getBestMove<attacker>(pass_left).isInvalid());
00103 ntesuki_assert(record_orig);
00104
00105 const bool invalid_defense = EffectUtil::isKingInCheck(PlayerTraits<P>::opponent, state);
00106 if (invalid_defense)
00107 {
00108 result = ProofDisproof::Checkmate();
00109 RETURN;
00110 }
00111
00112 ntesuki_assert (!record->isVisited());
00113 NtesukiRecord::VisitLock visitLock(record);
00114
00115 if (record->setUpNode<P>())
00116 {
00117 result = record->getValueWithPath<attacker>(pass_left, path);
00118 if (result.isFinal())
00119 {
00120
00121 RETURN;
00122 }
00123 }
00124
00125
00126 if (pass_left > 0)
00127 {
00128 result = record->getValueWithPath<attacker>(pass_left - 1, path);
00129 if (!result.isFinal())
00130 {
00131 NtesukiRecord::UnVisitLock unVisitLock(record);
00132 attackForDisproof<P>(record, record_orig, pass_left - 1, last_move);
00133 }
00134
00135 if (!result.isCheckmateFail())
00136 {
00137 RETURN;
00138 }
00139 ntesuki_assert(result.isCheckmateFail());
00140 }
00141
00142
00143
00144 NtesukiMoveList moves;
00145 record->generateMoves<P>(moves, pass_left, false);
00146
00147
00148
00149 bool has_loop = false;
00150 bool disproof_failed = false;
00151 for (NtesukiMoveList::iterator move_it = moves.begin();
00152 move_it != moves.end(); move_it++)
00153 {
00154 NtesukiMove& move = *move_it;
00155
00156 if (move.isPass()) continue;
00157 if (move.isCheckmateFail<attacker>(pass_left)) continue;
00158 if (!move.isCheck() && 0 == pass_left) continue;
00159
00160
00161 if (move.isNoPromote()) continue;
00162
00163 NtesukiRecord *record_child = table.allocateWithMove(record, move);
00164 if (record_child == 0)
00165 {
00166 result = ProofDisproof::Checkmate();
00167 RETURN;
00168 }
00169 ntesuki_assert(record_child);
00170 if(record_child->isVisited())
00171 {
00172
00173 has_loop = true;
00174 continue;
00175 }
00176
00177 PathEncoding path_child(path, move.getMove());
00178 result = record_child->getValueWithPath<attacker>(pass_left, path_child);
00179
00180 if(result.isUnknown())
00181 {
00182 const NtesukiRecord* record_child_orig = table.findWithMoveConst(record_orig, move);
00183 if (!record_child_orig ||
00184 !record_child_orig->getValue<attacker>(pass_left).isCheckmateFail())
00185 {
00186
00187
00188
00189 result = ProofDisproof::Checkmate();
00190 RETURN;
00191 }
00192
00193 AttackHelperDisproof<NtesukiSimulationSearcher, P> helper(this,
00194 record_child,
00195 record_child_orig,
00196 pass_left,
00197 move.getMove());
00198 TRY_DFPN;
00199 ApplyMoveWithPath<P>::doUndoMove(state, path, move.getMove(), helper);
00200 CATCH_DFPN;
00201 if (record->getValueWithPath<attacker>(pass_left, path).isFinal())
00202 {
00203 result = record->getValueWithPath<attacker>(pass_left, path);
00204 RETURN;
00205 }
00206 }
00207
00208 if (result.isCheckmateSuccess())
00209 {
00210 disproof_failed = true;
00211 continue;
00212 }
00213 else if (result == ProofDisproof::LoopDetection())
00214 {
00215 has_loop = true;
00216 }
00217
00218 ntesuki_assert(result.isCheckmateFail());
00219 move.setCheckmateFail<attacker>(pass_left);
00220 }
00221
00222 if (disproof_failed)
00223 {
00224 result = ProofDisproof::Checkmate();
00225 RETURN;
00226 }
00227
00228
00229 if (has_loop)
00230 {
00231 record->setLoopWithPath<attacker>(pass_left, path);
00232 result = ProofDisproof::LoopDetection();
00233 TRY_DFPN;
00234 record->setResult<attacker>(pass_left, NtesukiResult(1, 1),
00235 NtesukiMove::INVALID(), false);
00236 CATCH_DFPN;
00237 }
00238 else
00239 {
00240 result = ProofDisproof::NoCheckmate();
00241 TRY_DFPN;
00242 record->setResult<attacker>(pass_left, result,
00243 NtesukiMove::INVALID(), true);
00244 CATCH_DFPN;
00245 }
00246 RETURN;
00247 }
00248
00249 template <Player P>
00250 void
00251 NtesukiSimulationSearcher::
00252 defenseForDisproof(NtesukiRecord* record,
00253 const NtesukiRecord* record_orig,
00254 const unsigned int pass_left,
00255 const Move last_move)
00256 {
00257 const Player attacker = PlayerTraits<P>::opponent;
00258 ++node_count;
00259 ntesuki_assert(P == state.getTurn());
00260
00261 ntesuki_assert(EffectUtil::isKingInCheck(P, state) || (pass_left > 0));
00262
00263 ntesuki_assert(record);
00264 ntesuki_assert(record->getBestMove<attacker>(pass_left).isInvalid());
00265 ntesuki_assert(record_orig);
00266 ntesuki_assert(!record->isVisited());
00267 ntesuki_assert(record_orig->getValue<attacker>(pass_left).
00268 isCheckmateFail());
00269 NtesukiRecord::VisitLock visitLock(record);
00270
00271 if (record->setUpNode<P>())
00272 {
00273 result = record->getValueWithPath<attacker>(pass_left, path);
00274 if (result.isFinal())
00275 {
00276
00277 RETURN;
00278 }
00279 }
00280
00281 #ifndef NDEBUG
00282
00283 ntesuki_assert(!EffectUtil::isKingInCheck(attacker, state));
00284 #endif
00285
00286
00287
00288 const NtesukiMove best_move =
00289 record_orig->getBestMove<attacker>(pass_left);
00290 if (best_move.isInvalid())
00291 {
00292
00293 result = ProofDisproof::Checkmate();
00294 RETURN;
00295 }
00296 const NtesukiRecord *record_child_orig = table.findWithMoveConst(record_orig, best_move);
00297 if (!record_child_orig ||
00298 !record_child_orig->getValue<attacker>(pass_left).isCheckmateFail())
00299 {
00300
00301 result = ProofDisproof::Checkmate();
00302 RETURN;
00303 }
00304 ntesuki_assert(record_child_orig);
00305
00306 if (!best_move.isPass() &&
00307 !state.template isAlmostValidMove<false>(best_move.getMove()))
00308 {
00309 result = ProofDisproof::Checkmate();
00310 RETURN;
00311 }
00312
00313 NtesukiRecord *record_child = table.allocateWithMove(record, best_move);
00314 if (record_child == 0)
00315 {
00316 result = ProofDisproof::Checkmate();
00317 RETURN;
00318 }
00319 ntesuki_assert(record_child);
00320
00321 int pass_left_child = pass_left;
00322 if (best_move.isPass()) --pass_left_child;
00323
00324 if (record_child->isVisited())
00325 {
00326 TRY_DFPN;
00327 result = ProofDisproof::LoopDetection();
00328 record->setLoopWithPath<attacker>(pass_left, path);
00329 record->setResult<attacker>(pass_left, NtesukiResult(1, 1),
00330 NtesukiMove::INVALID(), false);
00331 CATCH_DFPN;
00332 RETURN;
00333 }
00334 else if (!record_child_orig->getValue<attacker>(pass_left_child).isCheckmateFail())
00335 {
00336 result = ProofDisproof::Checkmate();
00337 RETURN;
00338 }
00339
00340 const PathEncoding path_child(path, best_move.getMove());
00341 result = record_child->getValueWithPath<attacker>(pass_left_child, path_child);
00342
00343 if (result.isUnknown())
00344 {
00345 DefenseHelperDisproof<NtesukiSimulationSearcher, P> helper(this,
00346 record_child,
00347 record_child_orig,
00348 pass_left_child,
00349 best_move.getMove());
00350 TRY_DFPN;
00351 ApplyMoveWithPath<P>::doUndoMoveOrPass(state, path, best_move.getMove(), helper);
00352 CATCH_DFPN;
00353 if (record->getValueWithPath<attacker>(pass_left, path).isFinal())
00354 {
00355 result = record->getValueWithPath<attacker>(pass_left, path);
00356 RETURN;
00357 }
00358 }
00359
00360 if (result == ProofDisproof::LoopDetection())
00361 {
00362 TRY_DFPN;
00363 record->setLoopWithPath<attacker>(pass_left, path);
00364 record->setResult<attacker>(pass_left, NtesukiResult(1, 1),
00365 NtesukiMove::INVALID(), false);
00366 CATCH_DFPN;
00367 RETURN;
00368 }
00369 else if (result.isCheckmateFail())
00370 {
00371 NtesukiMove move(best_move.getMove());
00372 TRY_DFPN;
00373 move.setCheckmateFail<attacker>(pass_left);
00374 record->setResult<attacker>(pass_left, result, move, true);
00375 CATCH_DFPN;
00376 RETURN;
00377 }
00378 else
00379 {
00380
00381
00382
00383
00384
00385 result = ProofDisproof::Checkmate();
00386 RETURN;
00387 }
00388 }
00389
00390
00391
00392
00393 template <Player P>
00394 bool
00395 NtesukiSimulationSearcher::
00396 startFromAttackDisproof(NtesukiRecord *record,
00397 const NtesukiRecord *record_orig,
00398 const unsigned int pass_left,
00399 const Move last_move)
00400 {
00401 ++disproof_count;
00402 const Player attacker = P;
00403 ntesuki_assert(record_orig);
00404 if (!record_orig->getValue<attacker>(pass_left).isCheckmateFail())
00405 return false;
00406
00407 TRY_DFPN;
00408 attackForDisproof<P>(record, record_orig, pass_left, last_move);
00409 CATCH_DFPN;
00410 if (result.isCheckmateFail())
00411 {
00412 ++disproof_success_count;
00413 return true;
00414 }
00415 return false;
00416 }
00417
00418
00419
00420
00421 template <Player P>
00422 bool
00423 NtesukiSimulationSearcher::
00424 startFromDefenseDisproof(NtesukiRecord *record,
00425 const NtesukiRecord *record_orig,
00426 const unsigned int pass_left,
00427 const Move last_move)
00428 {
00429 ntesuki_assert (P == state.getTurn());
00430 ++disproof_count;
00431 const Player attacker = PlayerTraits<P>::opponent;
00432 ntesuki_assert(record_orig);
00433 if (!record_orig->getValue<attacker>(pass_left).isCheckmateFail())
00434 return false;
00435
00436 TRY_DFPN;
00437 defenseForDisproof<P>(record, record_orig, pass_left, last_move);
00438 CATCH_DFPN;
00439 if (result.isCheckmateFail())
00440 {
00441 ++disproof_success_count;
00442 return true;
00443 }
00444 return false;
00445 }
00446
00447 #undef RETURN
00448
00449
00450
00451
00452