00001
00002
00003 #include "osl/ntesuki/ntesukiSearcher.h"
00004 #include "osl/ntesuki/ntesukiMove.h"
00005 #include "osl/ntesuki/ntesukiMoveList.h"
00006 #include "osl/ntesuki/ntesukiSimulationSearcher.h"
00007 #include "osl/apply_move/applyMoveWithPath.h"
00008 #include "osl/effect_util/effectUtil.h"
00009
00010 #ifdef NDEBUG
00011 # include "osl/ntesuki/ntesukiMove.tcc"
00012 # include "osl/ntesuki/ntesukiRecord.tcc"
00013 #endif
00014
00015 #include "osl/record/csaRecord.h"
00016 #include <climits>
00017
00018 using namespace osl;
00019 using namespace osl::ntesuki;
00020
00021
00022
00023
00024
00025 const int READ_ATTACK_BACK_LIMIT = 5120;
00026
00027 #ifndef NDEBUG
00028 #define RETURN(val) \
00029 if (record->getValueWithPath<A>(pass_left, path).proof() == 0)\
00030 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).disproof() > ProofDisproof::DISPROOF_LIMIT);\
00031 if (record->getValueWithPath<A>(pass_left, path).disproof() == 0)\
00032 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).proof() > ProofDisproof::PROOF_LIMIT);\
00033 ntesuki_assert(val.isFinal() == record->getValueWithPath<A>(pass_left, path).isFinal());\
00034 return val
00035 #else
00036 #define RETURN(val) return val
00037 #endif
00038
00039 #define RETURN_ON_STOP \
00040 if (node_count > read_node_limit || *stop_flag)\
00041 return
00042
00043
00044
00045
00046 static
00047 unsigned int addWithSaturation(unsigned int limit,
00048 unsigned int l, unsigned int r)
00049 {
00050 if (limit < l)
00051 return limit;
00052 const unsigned int sum = l+r;
00053 if (limit < sum)
00054 return limit;
00055
00056 if (sum < l)
00057 return limit;
00058 ntesuki_assert(r <= sum);
00059 return sum;
00060 }
00061
00062 struct PlayMoveLock
00063 {
00064 std::vector<Move>& mlist;
00065
00066 PlayMoveLock(std::vector<Move>& l,
00067 const osl::Move& m)
00068 : mlist(l)
00069 {
00070 mlist.push_back(m);
00071 }
00072
00073 ~PlayMoveLock()
00074 {
00075 mlist.pop_back();
00076 }
00077 };
00078
00079 struct LockGC
00080 {
00081 osl::ntesuki::NtesukiTable& table;
00082 LockGC(osl::ntesuki::NtesukiTable& t)
00083 : table(t)
00084 {
00085 table.lockGC();
00086 }
00087
00088 ~LockGC()
00089 {
00090 table.unlockGC();
00091 }
00092 };
00093
00094
00095
00096
00097 template <class Search,Player T>
00098 class
00099 osl::ntesuki::NtesukiSearcher::
00100 AttackHelper
00101 {
00102 unsigned int proof_limit, disproof_limit, pass_left;
00103 Search* searcher;
00104 NtesukiResult& result;
00105 NtesukiRecord* record;
00106 const NtesukiRecord* oracle_attack;
00107 const NtesukiRecord* oracle_defense;
00108 const Move last_move;
00109 public:
00110 AttackHelper(Search* searcher,
00111 NtesukiResult& result,
00112 NtesukiRecord* record,
00113 const NtesukiRecord* oracle_attack,
00114 const NtesukiRecord* oracle_defense,
00115 unsigned int proof_limit,
00116 unsigned int disproof_limit,
00117 unsigned int pass_left,
00118 const Move last_move)
00119 : proof_limit(proof_limit), disproof_limit(disproof_limit),
00120 pass_left(pass_left),
00121 searcher(searcher), result(result), record(record),
00122 oracle_attack(oracle_attack), oracle_defense(oracle_defense),
00123 last_move(last_move)
00124 {
00125 }
00126
00127 void operator()(Position last_to)
00128 {
00129 result = (*searcher).template defense<PlayerTraits<T>::opponent>
00130 (record, oracle_attack, oracle_defense,
00131 proof_limit, disproof_limit, pass_left, last_move);
00132 }
00133 };
00134
00135
00136
00137
00138 template <class Search,Player T>
00139 class
00140 osl::ntesuki::NtesukiSearcher::
00141 CallSimulationAttack
00142 {
00143 Search &simulator;
00144 NtesukiTable& table;
00145 NtesukiRecord *record;
00146 const NtesukiRecord *record_orig;
00147 unsigned int pass_left;
00148 bool& simulation_result;
00149 const Move last_move;
00150
00151 public:
00152 CallSimulationAttack(Search& simulator,
00153 NtesukiTable& table,
00154 NtesukiRecord *record,
00155 const NtesukiRecord *record_orig,
00156 unsigned int pass_left,
00157 bool& simulation_result,
00158 const Move last_move)
00159 : simulator(simulator), table(table),
00160 record(record), record_orig(record_orig),
00161 pass_left(pass_left),
00162 simulation_result(simulation_result),
00163 last_move(last_move)
00164 {
00165 }
00166
00167 void operator()(Position last_to)
00168 {
00169 LockGC glock(table);
00170 simulation_result = simulator.template
00171 startFromDefenseDisproof<PlayerTraits<T>::opponent>
00172 (record, record_orig, pass_left, last_move);
00173 }
00174 };
00175
00176
00177
00178
00179 template <class Search,Player T>
00180 class
00181 osl::ntesuki::NtesukiSearcher::
00182 DefenseHelper
00183 {
00184 unsigned int proof_limit, disproof_limit, pass_left;
00185 Search* searcher;
00186 NtesukiResult& result;
00187 NtesukiRecord* record;
00188 const NtesukiRecord* oracle_attack;
00189 const NtesukiRecord* oracle_defense;
00190 const Move last_move;
00191
00192 public:
00193 DefenseHelper(Search* searcher,
00194 NtesukiResult& result,
00195 NtesukiRecord* record,
00196 const NtesukiRecord* oracle_attack,
00197 const NtesukiRecord* oracle_defense,
00198 unsigned int proof_limit,
00199 unsigned int disproof_limit,
00200 unsigned int pass_left,
00201 const Move last_move)
00202 : proof_limit(proof_limit), disproof_limit(disproof_limit),
00203 pass_left(pass_left), searcher(searcher), result(result), record(record),
00204 oracle_attack(oracle_attack), oracle_defense(oracle_defense),
00205 last_move(last_move)
00206 {
00207 }
00208
00209 void operator()(Position p)
00210 {
00211 (*searcher).template attack<PlayerTraits<T>::opponent>
00212 (record, oracle_attack, oracle_defense,
00213 proof_limit, disproof_limit,
00214 pass_left, last_move);
00215 }
00216 };
00217
00218
00219
00220
00221 template <class Search,Player T>
00222 class
00223 osl::ntesuki::NtesukiSearcher::
00224 CallSimulationDefense
00225 {
00226 Search &simulator;
00227 NtesukiTable &table;
00228 NtesukiRecord *record;
00229 const NtesukiRecord *record_orig;
00230 unsigned int pass_left;
00231 bool& simulation_result;
00232 const Move last_move;
00233 public:
00234 CallSimulationDefense(Search& simulator,
00235 NtesukiTable& table,
00236 NtesukiRecord *record,
00237 const NtesukiRecord *record_orig,
00238 unsigned int pass_left,
00239 bool& simulation_result,
00240 const Move last_move)
00241 : simulator(simulator), table(table),
00242 record(record), record_orig(record_orig),
00243 pass_left(pass_left),
00244 simulation_result(simulation_result),
00245 last_move(last_move)
00246 {
00247 }
00248
00249 void operator()(Position last_to)
00250 {
00251 LockGC glock(table);
00252 simulation_result = simulator.template
00253 startFromAttackProof<PlayerTraits<T>::opponent>
00254 (record, record_orig, pass_left, last_move);
00255 }
00256 };
00257
00258
00259
00260
00261 template <class Search,Player T>
00262 class
00263 osl::ntesuki::NtesukiSearcher::
00264 CallSimulationDefenseDisproof
00265 {
00266 Search &simulator;
00267 NtesukiTable &table;
00268 NtesukiRecord *record;
00269 const NtesukiRecord *record_orig;
00270 unsigned int pass_left;
00271 bool& simulation_result;
00272 const Move last_move;
00273 public:
00274 CallSimulationDefenseDisproof(Search& simulator,
00275 NtesukiTable& table,
00276 NtesukiRecord *record,
00277 const NtesukiRecord *record_orig,
00278 unsigned int pass_left,
00279 bool& simulation_result,
00280 const Move last_move)
00281 : simulator(simulator), table(table),
00282 record(record), record_orig(record_orig),
00283 pass_left(pass_left),
00284 simulation_result(simulation_result),
00285 last_move(last_move)
00286 {
00287 }
00288
00289 void operator()(Position last_to)
00290 {
00291 LockGC glock(table);
00292 simulation_result = simulator.template
00293 startFromAttackDisproof<PlayerTraits<T>::opponent>
00294 (record, record_orig, pass_left, last_move);
00295 }
00296 };
00297
00298 template <Player T>
00299 void osl::ntesuki::NtesukiSearcher::
00300 simulateSiblingsFail(NtesukiRecord *record,
00301 NtesukiRecord *record_best,
00302 int pass_left,
00303 unsigned int& success_count,
00304 unsigned int& total_count)
00305 {
00306 LockGC glock(table);
00307
00308 const Player A = T;
00309 if (!record_best) return;
00310 ntesuki_assert(record_best);
00311
00312 NtesukiMoveList moves;
00313 mg->generate<T>(state, moves);
00314
00315 for (NtesukiMoveList::iterator move_it = moves.begin();
00316 move_it != moves.end(); move_it++)
00317 {
00318 NtesukiMove& move = *move_it;
00319 NtesukiRecord *record_child = table.allocateWithMove(record,
00320 move);
00321 if (record_child == 0)
00322 {
00323 *stop_flag = TableLimitReached;
00324 return;
00325 }
00326 ntesuki_assert(record_child);
00327 if (record_child == record_best) continue;
00328 if (record_child->isVisited()) continue;
00329 if (move.isCheckmateFail<A>(pass_left)) continue;
00330 const PathEncoding path_child(path, move.getMove());
00331 const NtesukiResult result_child = record_child->getValueWithPath<A>(pass_left,
00332 path_child);
00333 if (result_child.isFinal())
00334 {
00335 continue;
00336 }
00337
00338 bool simulation_result;
00339 total_count++;
00340 CallSimulationAttack<NtesukiSimulationSearcher, T>
00341 helper(simulator, table, record_child, record_best,
00342 pass_left, simulation_result, move.getMove());
00343 TRY_DFPN;
00344 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, move.getMove(), helper);
00345 CATCH_DFPN;
00346 RETURN_ON_STOP;
00347
00348 if (simulation_result)
00349 {
00350 success_count++;
00351 ntesuki_assert(record_child->getValueWithPath<A>(pass_left,
00352 path_child).isCheckmateFail());
00353 TRY_DFPN;
00354 move.setBySimulation();
00355 move.setCheckmateFail<A>(pass_left);
00356 CATCH_DFPN;
00357 }
00358 }
00359 }
00360
00361
00362
00363
00364 class CountChildLock
00365 {
00366 public:
00367 CountChildLock(NtesukiRecord* r,
00368 const NtesukiTable& t)
00369 : record(r), table(t)
00370 {
00371 size_start = table.size();
00372 }
00373
00374 ~CountChildLock()
00375 {
00376 record->addChildCount(table.size() - size_start);
00377 }
00378 private:
00379 osl::ntesuki::NtesukiRecord* record;
00380 const osl::ntesuki::NtesukiTable& table;
00381 unsigned int size_start;
00382 };
00383
00384
00385
00386
00387
00388 template <Player T>
00389 NtesukiResult osl::ntesuki::NtesukiSearcher::
00390 attack(NtesukiRecord* record,
00391 const NtesukiRecord* oracle_attack,
00392 const NtesukiRecord* oracle_defense,
00393 unsigned int proof_limit, unsigned int disproof_limit,
00394 const int pass_left, const Move last_move)
00395 {
00396 CountChildLock cclock(record, table);
00397 const Player A = T;
00398 #ifndef NDEBUG
00399 const Player D = PlayerTraits<T>::opponent;
00400 #endif
00401
00402 ntesuki_assert(T == state.getTurn());
00403 ntesuki_assert(!EffectUtil::isKingInCheck(D, state));
00404 ntesuki_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
00405 ntesuki_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
00406 ntesuki_assert(record->getValueOr<A>(pass_left, path, iwscheme).proof()
00407 < proof_limit);
00408 ntesuki_assert(record->getValueOr<A>(pass_left, path, iwscheme).disproof()
00409 < disproof_limit);
00410
00411 RETURN_ON_STOP (record->getValueOr<A>(pass_left, path, iwscheme));
00412
00413 ntesuki_assert(record->getValueOr<A>(pass_left, path, iwscheme).proof()
00414 < proof_limit);
00415 ntesuki_assert(record->getValueOr<A>(pass_left, path, iwscheme).disproof()
00416 < disproof_limit);
00417 ntesuki_assert(record->getBestMove<A>(pass_left).isInvalid());
00418
00419 ntesuki_assert(proof_limit > 0);
00420 ntesuki_assert(disproof_limit > 0);
00421
00422
00423
00424 TRY_DFPN;
00425 if (record->setUpNode<T>())
00426 {
00427 const NtesukiResult result_cur =
00428 record->getValueWithPath<A>(pass_left, path);
00429 if (result_cur.isCheckmateSuccess())
00430 {
00431
00432 ++immediate_win;
00433 RETURN (result_cur);
00434 }
00435 else if (result_cur.isCheckmateFail() && pass_left == 0)
00436 {
00437 RETURN (result_cur);
00438 }
00439 }
00440 CATCH_DFPN;
00441
00442
00443
00444 NtesukiResult result_cur = record->getValueOr<A>(pass_left, path, iwscheme);
00445 while ((result_cur.proof() < proof_limit) &&
00446 (result_cur.disproof() < disproof_limit))
00447 {
00448 if (iwscheme == NtesukiRecord::no_iw)
00449 {
00450
00451
00452 TRY_DFPN;
00453 attackWithOrder<T>(record, NULL, NULL,
00454 proof_limit, disproof_limit,
00455 pass_left, last_move);
00456
00457 CATCH_DFPN;
00458 RETURN_ON_STOP (result_cur);
00459 }
00460 else if (iwscheme == NtesukiRecord::strict_iw)
00461 {
00462
00463
00464 for (int pass_left_child = 0; pass_left_child <= pass_left; pass_left_child++)
00465 {
00466 NtesukiResult result_st = record->getValueWithPath<A>(pass_left_child, path);
00467 if (!result_st.isCheckmateFail())
00468 {
00469 ntesuki_assert(result_st.proof() < proof_limit);
00470 ntesuki_assert(result_st.disproof() < disproof_limit);
00471 TRY_DFPN;
00472 attackWithOrder<T>(record, NULL, NULL,
00473 proof_limit, disproof_limit,
00474 pass_left_child, last_move);
00475
00476 CATCH_DFPN;
00477 RETURN_ON_STOP (result_cur);
00478 break;
00479 }
00480 }
00481 }
00482 else if (iwscheme == NtesukiRecord::pn_iw)
00483 {
00484
00485
00486 unsigned int p_min = ProofDisproof::BigProofNumber,
00487 p_2nd = ProofDisproof::BigProofNumber;
00488 int pass_left_best = -1;
00489 for (int pass_left_child = 0; pass_left_child <= pass_left; pass_left_child++)
00490 {
00491 NtesukiResult result_st = record->getValueWithPath<A>(pass_left_child, path);
00492 if (result_st.isCheckmateFail()) continue;
00493
00494 const unsigned int proof = result_st.proof();
00495 if (proof < p_min)
00496 {
00497 pass_left_best = pass_left_child;
00498 p_2nd = p_min;
00499 p_min = proof;
00500 }
00501 else if (proof < p_2nd)
00502 {
00503 p_2nd = proof;
00504 }
00505 }
00506
00507 unsigned int proof_limit_child = std::min(proof_limit, p_2nd + 1);
00508 unsigned int disproof_limit_child = disproof_limit;
00509 TRY_DFPN;
00510 attackWithOrder<T>(record, NULL, NULL,
00511 proof_limit_child, disproof_limit_child,
00512 pass_left_best, last_move);
00513
00514 CATCH_DFPN;
00515 RETURN_ON_STOP (result_cur);
00516 }
00517 result_cur = record->getValueOr<A>(pass_left, path, iwscheme);
00518 }
00519 return result_cur;
00520 }
00521
00522 template <Player T>
00523 void osl::ntesuki::NtesukiSearcher::
00524 attackWithOrder(NtesukiRecord* record,
00525 const NtesukiRecord* oracle_attack,
00526 const NtesukiRecord* oracle_defense,
00527 unsigned int proof_limit, unsigned int disproof_limit,
00528 const int pass_left, const Move last_move)
00529 {
00530 ++node_count;
00531
00532 const Player A = T;
00533 #ifndef NDEBUG
00534 const Player D = PlayerTraits<T>::opponent;
00535 #endif
00536 ntesuki_assert(T == state.getTurn());
00537 ntesuki_assert(!EffectUtil::isKingInCheck(D, state));
00538 ntesuki_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
00539 ntesuki_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
00540
00541 RETURN_ON_STOP;
00542 const bool under_attack = EffectUtil::isKingInCheck(T, state);
00543
00544 ntesuki_assert (record->getValueWithPath<A>(pass_left, path).proof()
00545 < proof_limit);
00546 ntesuki_assert (record->getValueWithPath<A>(pass_left, path).disproof()
00547 < disproof_limit);
00548 ntesuki_assert(record->getBestMove<A>(pass_left).isInvalid());
00549
00550 NtesukiRecord::VisitLock visitLock(record);
00551
00552 ntesuki_assert(proof_limit > 0);
00553 ntesuki_assert(disproof_limit > 0);
00554
00555 NtesukiMoveList moves;
00556
00557
00558 TRY_DFPN;
00559 record->generateMoves<T>(moves, pass_left, false);
00560 CATCH_DFPN;
00561
00562
00563 ++attack_node_count;
00564 if (under_attack)
00565 {
00566 ++attack_node_under_attack_count;
00567 }
00568 attack_node_moves_count += moves.size();
00569
00570
00571 if (moves.empty())
00572 {
00573 if (pass_left != 0 &&
00574 record->rzone_move_generation)
00575 {
00576
00577 NtesukiResult r = record->getValueWithPath<A>(pass_left - 1, path);
00578
00579 if (r.isCheckmateFail())
00580 {
00581
00582 record->rzone_move_generation = false;
00583 TRY_DFPN;
00584 record->setResult<A>(pass_left, ProofDisproof(1,1),
00585 NtesukiMove::INVALID(), false);
00586 CATCH_DFPN;
00587 }
00588 else
00589 {
00590
00591 TRY_DFPN;
00592 record->setResult<A>(pass_left, ProofDisproof(r.proof() + 2,
00593 r.disproof() + 2),
00594 NtesukiMove::INVALID(), false);
00595 CATCH_DFPN;
00596 }
00597 return;
00598 }
00599 TRY_DFPN;
00600
00601
00602
00603 record->setResult<A>(pass_left, ProofDisproof::NoCheckmate(),
00604 NtesukiMove::INVALID(), false);
00605 CATCH_DFPN;
00606 return;
00607 }
00608
00609 ntesuki_assert(!moves.empty());
00610 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).proof() != 0);
00611 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).disproof() != 0);
00612
00613
00614
00615 for (;;)
00616 {
00617 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).proof() != 0);
00618 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).disproof() != 0);
00619
00620 unsigned int best_proof = ProofDisproof::BigProofNumber,
00621 best_disproof = 0,
00622 second_proof = ProofDisproof::BigProofNumber,
00623 sum_disproof = 0;
00624 unsigned int step_cost = 1;
00625
00626 NtesukiMove* best_move =
00627 selectMoveAttack<T>(record,
00628 best_proof, sum_disproof,
00629 second_proof, best_disproof,
00630 step_cost,
00631 moves,
00632 pass_left);
00633 if (best_move == NULL)
00634 {
00635 if (pass_left != 0 &&
00636 record->rzone_move_generation)
00637 {
00638
00639 NtesukiResult r = record->getValueWithPath<A>(pass_left - 1, path);
00640
00641 if (r.isCheckmateFail())
00642 {
00643
00644 record->rzone_move_generation = false;
00645 TRY_DFPN;
00646 record->setResult<A>(pass_left, ProofDisproof(1,1),
00647 NtesukiMove::INVALID(), false);
00648 CATCH_DFPN;
00649 }
00650 else
00651 {
00652
00653 TRY_DFPN;
00654 record->setResult<A>(pass_left, ProofDisproof(r.proof() + 2,
00655 r.disproof() + 2),
00656 NtesukiMove::INVALID(), false);
00657 CATCH_DFPN;
00658 }
00659 }
00660 else
00661 {
00662 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).disproof() == 0);
00663 }
00664 return;
00665 }
00666 else if (best_move->isCheckmateSuccess<A>(pass_left))
00667 {
00668 return;
00669 }
00670
00671
00672
00673 const NtesukiResult result_cur(best_proof, sum_disproof);
00674 record->setResult<A>(pass_left, result_cur,
00675 NtesukiMove::INVALID(), false);
00676
00677
00678
00679 if ((proof_limit <= best_proof) ||
00680 (disproof_limit <= sum_disproof))
00681 {
00682 ntesuki_assert(!result_cur.isFinal());
00683 return;
00684 }
00685
00686
00687
00688 unsigned int proof_child = std::min(proof_limit, second_proof + step_cost);
00689 ntesuki_assert(disproof_limit > sum_disproof);
00690 unsigned int disproof_child =
00691 addWithSaturation(ProofDisproof::DISPROOF_LIMIT,
00692 disproof_limit, best_disproof)
00693 - sum_disproof;
00694
00695 NtesukiRecord *record_child = table.allocateWithMove(record, *best_move);
00696 if (record_child == 0)
00697 {
00698 *stop_flag = TableLimitReached;
00699 return;
00700 }
00701 ntesuki_assert(record_child);
00702 const PathEncoding path_child(path, best_move->getMove());
00703 NtesukiResult result_child = record_child->getValueWithPath<A>(pass_left,
00704 path_child);
00705 if (!result_child.isFinal())
00706 {
00707 if (best_move->isCheck())
00708 {
00709 oracle_attack = NULL;
00710 }
00711 if (ptt_aunt &&
00712 pass_left != 0 &&
00713 record->getValueWithPath<A>(pass_left - 1, path).isCheckmateFail())
00714 {
00715 oracle_defense = record;
00716 }
00717
00718 AttackHelper<NtesukiSearcher, T> helper(this,
00719 result_child,
00720 record_child,
00721 oracle_attack,
00722 oracle_defense,
00723 proof_child,
00724 disproof_child,
00725 pass_left,
00726 best_move->getMove());
00727 PlayMoveLock pml(moves_played, best_move->getMove());
00728 TRY_DFPN;
00729 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, best_move->getMove(), helper);
00730 CATCH_DFPN;
00731 record->updateWithChild(record_child, pass_left);
00732 RETURN_ON_STOP;
00733
00734 const NtesukiResult result_cur = record->getValueWithPath<A>(pass_left, path_child);
00735 if (result_cur.isFinal())
00736 {
00737 return;
00738 }
00739 }
00740
00741 if (result_child.isPawnDropFoul(best_move->getMove()))
00742 {
00743 best_move->setPawnDropCheckmate();
00744 best_move->setCheckmateFail<A>(pass_left);
00745 }
00746 else if (result_child.isCheckmateSuccess())
00747 {
00748 best_move->setCheckmateSuccess<A>(pass_left);
00749 TRY_DFPN;
00750 record->setResult<A>(pass_left, ProofDisproof::Checkmate(),
00751 *best_move, false);
00752 CATCH_DFPN;
00753 return;
00754 }
00755 else if (result_child.isCheckmateFail())
00756 {
00757 if (result_child != ProofDisproof::LoopDetection())
00758 {
00759 best_move->setCheckmateFail<A>(pass_left);
00760 }
00761
00762 if (result_child == ProofDisproof::PawnCheckmate())
00763 {
00764 best_move->setPawnDropCheckmate();
00765 }
00766
00767 if (ptt_siblings_fail &&
00768 !best_move->isCheck() &&
00769 result_child != ProofDisproof::LoopDetection())
00770 {
00771 TRY_DFPN;
00772 simulateSiblingsFail<T>(record, record_child, pass_left,
00773 sibling_attack_success_count,
00774 sibling_attack_count);
00775 CATCH_DFPN;
00776 }
00777 }
00778 }
00779 }
00780
00781 template <Player T>
00782 osl::ntesuki::NtesukiMove * osl::ntesuki::NtesukiSearcher::
00783 selectMoveAttack(NtesukiRecord* record,
00784 unsigned int& best_proof,
00785 unsigned int& sum_disproof,
00786 unsigned int& second_proof,
00787 unsigned int& best_disproof,
00788 unsigned int& step_cost,
00789 NtesukiMoveList& moves,
00790 const int pass_left)
00791 {
00792 const Player A = T;
00793
00794 bool read_nopromote = false;
00795
00796 re_select_move_attack:
00797 NtesukiMove *best_move = NULL;
00798
00799 bool loop = false;
00800 bool pawn_checkmate = false;
00801 unsigned short min_child_age = SHRT_MAX;
00802
00803 int average_cost = 0;
00804 int average_cost_count = 0;
00805
00806
00807 best_proof = ProofDisproof::BigProofNumber;
00808 best_disproof = 0;
00809 second_proof = ProofDisproof::BigProofNumber;
00810 sum_disproof = 0;
00811
00812
00813
00814 for (NtesukiMoveList::iterator move_it = moves.begin();
00815 move_it != moves.end(); ++move_it)
00816 {
00817 NtesukiMove& move = *move_it;
00818 pawn_checkmate |= move.isPawnDropCheckmate();
00819
00820 if (move.isPass())
00821 {
00822 continue;
00823 }
00824
00825 if (!move.isCheck() && 0 == pass_left)
00826 {
00827 continue;
00828 }
00829
00830 if (move.isCheckmateFail<A>(pass_left))
00831 {
00832 continue;
00833 }
00834
00835 if (delay_nopromote &&
00836 !read_nopromote &&
00837 move.isNoPromote())
00838 {
00839 continue;
00840 }
00841
00842 if (delay_non_attack &&
00843 !record->readNonAttack(pass_left) &&
00844 ((move.getOrder() > pass_left) ||
00845 move.isLameLong())
00846 )
00847 {
00848 continue;
00849 }
00850
00851 unsigned int proof = move.h_a_proof;
00852 unsigned int disproof = move.h_a_disproof;
00853
00854 if (tsumero_estimate && !move.isCheck())
00855 {
00856 proof = tsumero_estimate;
00857 disproof = 1;
00858 }
00859
00860 average_cost += proof;
00861 average_cost_count++;
00862
00863 NtesukiRecord *record_child = table.findWithMove(record, move);
00864 if (record_child)
00865 {
00866 if (record_child->isVisited())
00867 {
00868
00869
00870
00871 loop = true;
00872 continue;
00873 }
00874
00875 const PathEncoding path_child(path, move.getMove());
00876 NtesukiResult result_child;
00877 TRY_DFPN;
00878 result_child =
00879 record_child->getValueAnd<A>(pass_left, path_child,
00880 iwscheme, psscheme);
00881 CATCH_DFPN;
00882 proof = result_child.proof();
00883 disproof = result_child.disproof();
00884
00885 if (0 == disproof)
00886 {
00887 if (result_child == ProofDisproof::LoopDetection())
00888 {
00889 loop = true;
00890 continue;
00891 }
00892 if (record_child->getValueWithPath<A>(pass_left, path_child) ==
00893 ProofDisproof::PawnCheckmate())
00894 {
00895 move.setPawnDropCheckmate();
00896 pawn_checkmate = true;
00897 }
00898
00899 ntesuki_assert(proof >= ProofDisproof::PROOF_LIMIT);
00900 move.setCheckmateFail<A>(pass_left);
00901
00902
00903 continue;
00904 }
00905 else if (0 == proof)
00906 {
00907
00908 if (record_child->getValueWithPath<A>(pass_left, path_child).
00909 isPawnDropFoul(move.getMove()))
00910 {
00911 move.setPawnDropCheckmate();
00912 move.setCheckmateFail<A>(pass_left);
00913 pawn_checkmate = true;
00914 continue;
00915 }
00916
00917
00918 ntesuki_assert(disproof >= ProofDisproof::DISPROOF_LIMIT);
00919 move.setCheckmateSuccess<A>(pass_left);
00920 TRY_DFPN;
00921 record->setResult<A>(pass_left, ProofDisproof::Checkmate(),
00922 move, false);
00923 CATCH_DFPN;
00924
00925 return &move;
00926 }
00927
00928 min_child_age = std::min(record_child->distance,
00929 min_child_age);
00930 if (record_child->distance <= record->distance)
00931 {
00932 if (!record->useOld<A>(pass_left))
00933 {
00934 continue;
00935 }
00936 }
00937
00938
00939
00940
00941
00942 }
00943
00944
00945 if (!move.isCheck())
00946 {
00947 ntesuki_assert(pass_left > 0);
00948 proof += tsumero_cost;
00949 disproof += tsumero_cost;
00950 }
00951
00952 if (!record->useOld<A>(pass_left))
00953 {
00954 if (NtesukiRecord::max_for_split && record->is_split)
00955 {
00956 sum_disproof = std::max(disproof, sum_disproof);
00957 }
00958 else
00959 {
00960 sum_disproof = addWithSaturation(ProofDisproof::DISPROOF_LIMIT,
00961 disproof, sum_disproof);
00962 }
00963 }
00964 else
00965 {
00966 sum_disproof = std::max(disproof, sum_disproof);
00967 }
00968
00969
00970 if (proof < best_proof)
00971 {
00972 best_move = &move;
00973 second_proof = best_proof;
00974 best_proof = proof;
00975 best_disproof = disproof;
00976 }
00977 else if (proof < second_proof)
00978 {
00979 second_proof = proof;
00980 }
00981 }
00982
00983
00984
00985 if (best_move == NULL)
00986 {
00987 if (false == record->useOld<A>(pass_left))
00988 {
00989 if (SHRT_MAX != min_child_age)
00990 {
00991 record->setUseOld<A>(pass_left, true);
00992
00993 ntesuki_assert(min_child_age <= record->distance);
00994 record->distance = min_child_age;
00995
00996 goto re_select_move_attack;
00997 }
00998 }
00999
01000 if (!record->readNonAttack(pass_left))
01001 {
01002 if (!read_attack_only)
01003 {
01004 record->setReadNonAttack(pass_left);
01005 if (ptt_non_attack &&
01006 pass_left != 0)
01007 {
01008 TRY_DFPN;
01009 handleNonAttack<T>(record, pass_left);
01010 CATCH_DFPN;
01011 RETURN_ON_STOP NULL;
01012 }
01013 record->setUseOld<A>(pass_left, false);
01014 goto re_select_move_attack;
01015 }
01016 }
01017
01018 if (delay_nopromote &&
01019 !read_nopromote &&
01020 (pass_left > 0 || pawn_checkmate))
01021 {
01022 read_nopromote = true;
01023 record->setUseOld<A>(pass_left, false);
01024 goto re_select_move_attack;
01025 }
01026
01027 ntesuki_assert(best_proof == ProofDisproof::BigProofNumber);
01028
01029 if (pass_left != 0 &&
01030 record->rzone_move_generation)
01031 {
01032
01033 return NULL;
01034 }
01035
01036 if (pawn_checkmate)
01037 {
01038 if (delay_nopromote) assert(read_nopromote);
01039
01040 TRY_DFPN;
01041 record->setResult<A>(pass_left, ProofDisproof::PawnCheckmate(),
01042 NtesukiMove::INVALID(), false);
01043 CATCH_DFPN;
01044 return NULL;
01045 }
01046
01047 else if (loop)
01048 {
01049 record->setLoopWithPath<A>(pass_left, path);
01050 TRY_DFPN;
01051 record->setResult<A>(pass_left, NtesukiResult(1, 1),
01052 NtesukiMove::INVALID(), false);
01053 CATCH_DFPN;
01054 return NULL;
01055 }
01056 else
01057 {
01058 TRY_DFPN;
01059 record->setResult<A>(pass_left, ProofDisproof::NoCheckmate(),
01060 NtesukiMove::INVALID(), false);
01061 CATCH_DFPN;
01062 return NULL;
01063 }
01064 }
01065
01066 ntesuki_assert(best_proof != 0);
01067 ntesuki_assert(sum_disproof != 0);
01068 ntesuki_assert(best_proof < ProofDisproof::PROOF_LIMIT);
01069 ntesuki_assert(sum_disproof < ProofDisproof::DISPROOF_LIMIT);
01070
01071 if (record->useOld<A>(pass_left))
01072 {
01073 ntesuki_assert(min_child_age != SHRT_MAX);
01074 record->distance = min_child_age;
01075 }
01076 average_cost /= average_cost_count;
01077 step_cost = std::max(average_cost, 1);
01078 return best_move;
01079 }
01080
01081 template <Player T>
01082 void osl::ntesuki::NtesukiSearcher::
01083 handleNonAttack(NtesukiRecord* record,
01084 int pass_left)
01085 {
01086 const Player A = T;
01087 ntesuki_assert(T == state.getTurn());
01088
01089 NtesukiMoveList moves;
01090 mg->generate<T>(state, moves);
01091
01092 for (NtesukiMoveList::iterator move_it = moves.begin();
01093 move_it != moves.end(); ++move_it)
01094 {
01095 NtesukiRecord *record_best = table.findWithMove(record,
01096 *move_it);
01097 const PathEncoding path_best(path, move_it->getMove());
01098 if (!record_best ||
01099 !record_best->getValueWithPath<A>(pass_left,
01100 path_best).isCheckmateFail()) continue;
01101
01102
01103 for (NtesukiMoveList::iterator move_it2 = moves.begin();
01104 move_it2 != moves.end(); ++move_it2)
01105 {
01106 if (move_it2->isPass())
01107 {
01108 continue;
01109 }
01110 if (*move_it2 == *move_it)
01111 {
01112 continue;
01113 }
01114 if (move_it2->isCheckmateFail<A>(pass_left))
01115 {
01116 continue;
01117 }
01118 NtesukiRecord *record_child = table.allocateWithMove(record,
01119 *move_it2);
01120 if (record_child == 0)
01121 {
01122 *stop_flag = TableLimitReached;
01123 return;
01124 }
01125 ntesuki_assert(record_child);
01126 const PathEncoding path_child(path, move_it->getMove());
01127 if(record_child->getValueWithPath<A>(pass_left,
01128 path_child).isFinal())
01129 {
01130 continue;
01131 }
01132
01133 if (record_child->isVisited())
01134 {
01135 TRY_DFPN;
01136 move_it2->setCheckmateFail<A>(pass_left);
01137 record->setLoopWithPath<A>(pass_left, path_child);
01138 CATCH_DFPN;
01139 continue;
01140 }
01141
01142 bool simulation_result;
01143 CallSimulationAttack<NtesukiSimulationSearcher, T>
01144 helper(simulator, table, record_child, record_best,
01145 pass_left, simulation_result, move_it2->getMove());
01146 TRY_DFPN;
01147 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, move_it2->getMove(), helper);
01148 CATCH_DFPN;
01149 RETURN_ON_STOP;
01150
01151 if (simulation_result)
01152 {
01153 move_it2->setBySimulation();
01154 move_it2->setCheckmateFail<A>(pass_left);
01155 }
01156 }
01157 }
01158 }
01159
01160
01161
01162
01163 template <Player T>
01164 NtesukiResult osl::ntesuki::NtesukiSearcher::
01165 defense(NtesukiRecord* record,
01166 const NtesukiRecord* oracle_attack,
01167 const NtesukiRecord* oracle_defense,
01168 unsigned int proof_limit, unsigned int disproof_limit,
01169 int pass_left,
01170 const Move last_move)
01171 {
01172 const Player A = PlayerTraits<T>::opponent;
01173 const Player D = T;
01174 CountChildLock cclock(record, table);
01175
01176 ntesuki_assert(T == state.getTurn());
01177 ntesuki_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
01178 ntesuki_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
01179 ntesuki_assert (record->getValueAnd<A>(pass_left, path,
01180 iwscheme, psscheme).proof()
01181 < proof_limit);
01182 ntesuki_assert (record->getValueAnd<A>(pass_left, path,
01183 iwscheme, psscheme).disproof()
01184 < disproof_limit);
01185
01186 ntesuki_assert(EffectUtil::isKingInCheck(T, state) || (pass_left > 0));
01187 ntesuki_assert(!EffectUtil::isKingInCheck(A, state));
01188
01189 ++node_count;
01190 RETURN_ON_STOP (record->getValueAnd<A>(pass_left, path,
01191 iwscheme, psscheme));
01192
01193 ntesuki_assert(record);
01194 ntesuki_assert(!record->getValueWithPath<A>(pass_left, path).isFinal());
01195 ntesuki_assert(record->getBestMove<A>(pass_left).isInvalid());
01196
01197 NtesukiRecord::VisitLock visitLock(record);
01198
01199
01200
01201 TRY_DFPN;
01202 if (record->setUpNode<T>())
01203 {
01204 const NtesukiResult r = record->getValueWithPath<A>(pass_left, path);
01205 if (r.isCheckmateFail())
01206 {
01207
01208 ++immediate_lose;
01209 RETURN (r);
01210 }
01211 else if (r.isFinal())
01212 {
01213 RETURN (r);
01214 }
01215 }
01216 CATCH_DFPN;
01217
01218
01219
01220 NtesukiResult result_cur = record->getValueAnd<A>(pass_left, path, iwscheme, psscheme);
01221 while ((result_cur.proof() < proof_limit) &&
01222 (result_cur.disproof() < disproof_limit))
01223 {
01224 bool read_attack_first = false;
01225 if (psscheme)
01226 {
01227
01228
01229
01230
01231
01232 if (pass_left > 0)
01233 {
01234 const NtesukiResult result_attacker =
01235 record->getValueWithPath<A>(pass_left, path);
01236 const NtesukiResult result_defender =
01237 record->getValueOr<D>(pass_left - 1, path, iwscheme);
01238 if (result_defender.proof() < result_attacker.disproof())
01239 {
01240 read_attack_first = true;
01241 }
01242 }
01243 }
01244
01245 if (read_attack_first)
01246 {
01247 NtesukiRecord::UnVisitLock unVisitLock(record);
01248
01249 TRY_DFPN;
01250 attack<T>(record, NULL, NULL,
01251 disproof_limit, proof_limit,
01252 pass_left - 1, last_move);
01253 CATCH_DFPN;
01254 RETURN_ON_STOP (result_cur);
01255 }
01256 else
01257 {
01258 TRY_DFPN;
01259 defenseWithPlayer<T>(record, oracle_attack, oracle_defense,
01260 proof_limit, disproof_limit,
01261 pass_left, last_move);
01262 CATCH_DFPN;
01263 RETURN_ON_STOP (result_cur);
01264 }
01265 result_cur = record->getValueAnd<A>(pass_left, path, iwscheme, psscheme);
01266 }
01267 return result_cur;
01268 }
01269
01270 template <Player T>
01271 void osl::ntesuki::NtesukiSearcher::
01272 defenseWithPlayer(NtesukiRecord* record,
01273 const NtesukiRecord* oracle_attack,
01274 const NtesukiRecord* oracle_defense,
01275 unsigned int proof_limit, unsigned int disproof_limit,
01276 int pass_left,
01277 const Move last_move)
01278 {
01279 const Player A = PlayerTraits<T>::opponent;
01280 const bool under_attack = EffectUtil::isKingInCheck(T, state);
01281
01282
01283
01284 NtesukiMoveList moves;
01285
01286 TRY_DFPN;
01287 record->generateMoves<T>(moves, pass_left, true);
01288 CATCH_DFPN;
01289
01290 if (moves.empty())
01291 {
01292 TRY_DFPN;
01293 record->setResult<A>(0, ProofDisproof::NoEscape(),
01294 NtesukiMove::INVALID(), false);
01295 CATCH_DFPN;
01296 return;
01297 }
01298
01299
01300 ++defense_node_count;
01301 if (under_attack)
01302 {
01303 ++defense_node_under_attack_count;
01304 }
01305 defense_node_moves_count += moves.size();
01306
01307 ntesuki_assert(!moves.empty());
01308 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).isUnknown());
01309
01310
01311 if (!under_attack &&
01312 record->do_oracle_aunt &&
01313 oracle_defense)
01314 {
01315 record->do_oracle_aunt = false;
01316
01317 NtesukiMove pass(Move::PASS(T));
01318 NtesukiRecord *record_pass = table.allocateWithMove(record,
01319 pass);
01320 if (record_pass == 0)
01321 {
01322 *stop_flag = TableLimitReached;
01323 return;
01324 }
01325 ntesuki_assert(record_pass);
01326
01327 if (record_pass->isVisited())
01328 {
01329
01330 record->setLoopWithPath<A>(pass_left, path);
01331 assert(record->isLoopWithPath<A>(pass_left, path));
01332 TRY_DFPN;
01333 record->setResult<A>(pass_left, NtesukiResult(1, 1),
01334 NtesukiMove::INVALID(), false);
01335 CATCH_DFPN;
01336 return;
01337 }
01338
01339 ntesuki_assert(record_pass);
01340 const PathEncoding path_pass(path, pass.getMove());
01341 const NtesukiResult result_pass = record_pass->getValueWithPath<A>(pass_left - 1,
01342 path_pass);
01343 if (!result_pass.isFinal())
01344 {
01345 bool simulation_result;
01346 CallSimulationDefenseDisproof<NtesukiSimulationSearcher, T>
01347 helper(simulator, table, record_pass, oracle_defense,
01348 pass_left - 1, simulation_result, pass.getMove());
01349 TRY_DFPN;
01350 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, pass.getMove(), helper);
01351 CATCH_DFPN;
01352 return;
01353
01354 if (simulation_result)
01355 {
01356 ntesuki_assert(record_pass->getValueWithPath<A>(pass_left - 1,
01357 path_pass).isCheckmateFail());
01358 pass.setBySimulation();
01359 pass.setCheckmateFail<A>(pass_left);
01360 }
01361 }
01362 }
01363
01364
01365 if (record->do_oracle_attack && oracle_attack)
01366 {
01367 record->do_oracle_attack = false;
01368
01369 ntesuki_assert(ptt_uncle && !under_attack);
01370 NtesukiMove pass(Move::PASS(T));
01371
01372 NtesukiRecord *record_pass = table.allocateWithMove(record,
01373 pass);
01374 if (record_pass == 0)
01375 {
01376 *stop_flag = TableLimitReached;
01377 return;
01378 }
01379 ntesuki_assert(record_pass);
01380
01381 if (record_pass->isVisited())
01382 {
01383
01384 record->setLoopWithPath<A>(pass_left, path);
01385 assert(record->isLoopWithPath<A>(pass_left, path));
01386 TRY_DFPN;
01387 record->setResult<A>(pass_left, NtesukiResult(1, 1),
01388 NtesukiMove::INVALID(), false);
01389 CATCH_DFPN;
01390 return;
01391 }
01392
01393 ntesuki_assert(record_pass);
01394 const PathEncoding path_pass(path, pass.getMove());
01395 const NtesukiResult result_pass = record_pass->getValueWithPath<A>(pass_left - 1,
01396 path_pass);
01397 if (!result_pass.isFinal())
01398 {
01399 ++isshogi_attack_count;
01400
01401 bool simulation_result;
01402 CallSimulationDefense<NtesukiSimulationSearcher, T>
01403 helper(simulator, table, record_pass, oracle_attack,
01404 pass_left - 1, simulation_result, pass.getMove());
01405 TRY_DFPN;
01406 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, pass.getMove(), helper);
01407 CATCH_DFPN;
01408 return;
01409
01410 if (simulation_result)
01411 {
01412 ++isshogi_attack_success_count;
01413 ntesuki_assert(record_pass->getValueWithPath<A>(pass_left - 1,
01414 path_pass).isCheckmateSuccess());
01415 pass.setBySimulation();
01416 pass.setCheckmateSuccess<A>(pass_left);
01417 record->setNtesuki<A>(pass_left);
01418
01419 if (ptt_invalid_defense)
01420 {
01421 TRY_DFPN;
01422 simulateSiblingsSuccess<T>(record, record_pass, pass_left,
01423 pass_success_count,
01424 pass_count);
01425 CATCH_DFPN;
01426 return;
01427 }
01428 }
01429 }
01430 }
01431
01432 for (;;)
01433 {
01434 unsigned int best_disproof = ProofDisproof::BigProofNumber,
01435 sum_proof = 0,
01436 second_disproof = ProofDisproof::BigProofNumber,
01437 best_proof = 0;
01438
01439 unsigned int step_cost = 1;
01440 NtesukiMove *best_move = NULL;
01441
01442 best_move = selectMoveDefense<T>(record,
01443 best_disproof,
01444 sum_proof,
01445 second_disproof,
01446 best_proof,
01447 step_cost,
01448 moves,
01449 pass_left,
01450 last_move);
01451 RETURN_ON_STOP;
01452 if (NULL == best_move)
01453 {
01454 ntesuki_assert(record->getValueWithPath<A>(pass_left, path).
01455 isCheckmateSuccess());
01456 return;
01457 }
01458 else if (best_disproof == 0)
01459 {
01460 ntesuki_assert(best_move->isCheckmateFail<A>(pass_left) ||
01461 record->isLoopWithPath<A>(pass_left, path));
01462 return;
01463 }
01464
01465 #ifndef NDEBUG
01466 {
01467 NtesukiRecord* best_child = table.findWithMove(record, *best_move);
01468 if (best_child)
01469 {
01470 const PathEncoding path_child(path, best_move->getMove());
01471 int pass_left_child = pass_left;
01472 if (best_move->isPass()) --pass_left_child;
01473 const NtesukiResult r =
01474 best_child->getValueOr<A>(pass_left_child, path_child,iwscheme);
01475 ntesuki_assert(r.disproof() == best_disproof);
01476 ntesuki_assert(r.proof() <= sum_proof);
01477 }
01478 }
01479 #endif
01480
01481
01482
01483 const NtesukiResult result_cur = ProofDisproof(sum_proof, best_disproof);
01484 record->setResult<A>(pass_left, result_cur,
01485 NtesukiMove::INVALID(), false);
01486
01487
01488
01489 if ((disproof_limit <= best_disproof) ||
01490 (proof_limit <= sum_proof))
01491 {
01492 ntesuki_assert(!result_cur.isFinal());
01493 return;
01494 }
01495
01496 unsigned int proof_child =
01497 addWithSaturation(ProofDisproof::DISPROOF_LIMIT,
01498 proof_limit, best_proof) - sum_proof;
01499 unsigned int disproof_child = std::min(disproof_limit,
01500 second_disproof + step_cost);
01501
01502
01503
01504 int pass_left_child = pass_left;
01505 if (best_move->isPass())
01506 {
01507 --pass_left_child;
01508 }
01509 NtesukiRecord *record_child =
01510 table.allocateWithMove(record, *best_move);
01511 if (record_child == 0)
01512 {
01513 *stop_flag = TableLimitReached;
01514 return;
01515 }
01516 ntesuki_assert(record_child);
01517 const PathEncoding path_child(path, best_move->getMove());
01518 ntesuki_assert(pass_left_child >= 0);
01519 NtesukiResult result_child =
01520 record_child->getValueOr<A>(pass_left_child,
01521 path_child,
01522 iwscheme);
01523
01524 if (!result_child.isFinal())
01525 {
01526 if (best_move->isCheck())
01527 {
01528 if (ptt_uncle &&
01529 !under_attack &&
01530 delay_non_pass)
01531 {
01532 NtesukiMove& pass = moves.front();
01533 ntesuki_assert(pass.isPass());
01534
01535 oracle_attack = table.findWithMove(record, pass);
01536 ntesuki_assert(oracle_attack);
01537 }
01538 }
01539
01540 if (result_child.proof() >= proof_child)
01541 {
01542 std::cerr << *record_child
01543 << result_child << "<- result \n"
01544 << proof_child << "/" << disproof_child << "<- limit\n"
01545 << *best_move << "\n"
01546 << sum_proof << "/" << best_disproof << " <- cur\n";
01547 }
01548 DefenseHelper<NtesukiSearcher, T> helper(this,
01549 result_child,
01550 record_child,
01551 oracle_attack,
01552 oracle_defense,
01553 proof_child,
01554 disproof_child,
01555 pass_left_child,
01556 best_move->getMove());
01557
01558 PlayMoveLock pml(moves_played, best_move->getMove());
01559 if (best_move->isPass())
01560 {
01561 NtesukiRecord::pass_count++;
01562 }
01563 TRY_DFPN;
01564 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, best_move->getMove(), helper);
01565 CATCH_DFPN;
01566
01567 if (best_move->isPass())
01568 {
01569 NtesukiRecord::pass_count--;
01570 }
01571 record->updateWithChild(record_child, pass_left);
01572 RETURN_ON_STOP;
01573
01574 if (record->getValueWithPath<A>(pass_left, path).isFinal())
01575 {
01576 return;
01577 }
01578 }
01579
01580
01581
01582 if (result_child.isCheckmateFail())
01583 {
01584 if (result_child == ProofDisproof::AttackBack())
01585 {
01586 ++disproof_by_inversion_count;
01587 }
01588 if (result_child == ProofDisproof::LoopDetection())
01589 {
01590 record->setLoopWithPath<A>(pass_left, path);
01591 TRY_DFPN;
01592 record->setResult<A>(pass_left, NtesukiResult(1, 1),
01593 NtesukiMove::INVALID(), false);
01594 CATCH_DFPN;
01595 return;
01596 }
01597
01598 best_move->setCheckmateFail<A>(pass_left);
01599 TRY_DFPN;
01600 record->setResult<A>(pass_left, result_child,
01601 *best_move, false);
01602 CATCH_DFPN;
01603 return;
01604 }
01605 else if (result_child.isCheckmateSuccess())
01606 {
01607 best_move->setCheckmateSuccess<A>(pass_left);
01608 NtesukiRecord *best_record = table.findWithMove(record, *best_move);
01609 if ((ptt_invalid_defense && best_move->isPass()) ||
01610 (ptt_siblings_success && !best_move->isCheck())
01611 )
01612 {
01613 TRY_DFPN;
01614 simulateSiblingsSuccess<T>(record, best_record, pass_left,
01615 sibling_defense_success_count,
01616 sibling_defense_count);
01617 CATCH_DFPN;
01618 RETURN_ON_STOP;
01619 }
01620 }
01621 }
01622 }
01623
01624 template <Player T>
01625 osl::ntesuki::NtesukiMove* osl::ntesuki::NtesukiSearcher::
01626 selectMoveDefense(NtesukiRecord* record,
01627 unsigned int& best_disproof,
01628 unsigned int& sum_proof,
01629 unsigned int& second_disproof,
01630 unsigned int& best_proof,
01631 unsigned int& step_cost,
01632 NtesukiMoveList& moves,
01633 const int pass_left,
01634 const Move last_move)
01635 {
01636 const Player A = PlayerTraits<T>::opponent;
01637 const bool under_attack = EffectUtil::isKingInCheck(T, state);
01638
01639 bool read_interpose = record->readInterpose(pass_left);
01640
01641
01642
01643 bool read_non_pass = under_attack;
01644 if (pass_left > 0 && !under_attack)
01645 {
01646 NtesukiMove pass(Move::PASS(T));
01647 NtesukiRecord *record_pass = table.findWithMove(record, pass);
01648 if (record_pass)
01649 {
01650 const PathEncoding path_child(path, pass.getMove());
01651 read_non_pass =
01652 record_pass->getValueWithPath<A>(pass_left - 1,
01653 path_child).isCheckmateSuccess();
01654 }
01655 }
01656 if (under_attack) ntesuki_assert(read_non_pass);
01657
01658 bool read_check_defense = record->readCheckDefense(pass_left);
01659 if (isscheme == NtesukiRecord::normal_is)
01660 {
01661 read_check_defense = true;
01662 }
01663
01664 re_select_move_defense:
01665 unsigned short min_child_age = SHRT_MAX;
01666 NtesukiMove *best_move = NULL;
01667
01668 int average_cost = 0;
01669 int average_cost_count = 0;
01670
01671
01672 best_disproof = ProofDisproof::BigProofNumber;
01673 sum_proof = 0;
01674 second_disproof = ProofDisproof::BigProofNumber;
01675 best_proof = 0;
01676
01677
01678
01679 for (NtesukiMoveList::iterator move_it = moves.begin();
01680 move_it != moves.end(); ++move_it)
01681 {
01682 NtesukiMove& move = *move_it;
01683 if (move.isCheckmateSuccess<A>(pass_left))
01684 {
01685 continue;
01686 }
01687 ntesuki_assert(!move.isCheckmateFail<A>(pass_left));
01688
01689 if (delay_non_pass &&
01690 !read_non_pass &&
01691 !move.isPass())
01692 {
01693 continue;
01694 }
01695
01696 if (delay_interpose &&
01697 (move.isInterpose() ||
01698 move.isLameLong()) &&
01699 !read_interpose)
01700 {
01701 continue;
01702 }
01703
01704 if (move.isCheck() &&
01705 !under_attack &&
01706 !read_check_defense)
01707 {
01708 continue;
01709 }
01710
01711 unsigned int proof = move.h_d_proof;
01712 unsigned int disproof = move.h_d_disproof;
01713
01714 average_cost += disproof;
01715 average_cost_count++;
01716
01717 NtesukiRecord *record_child = table.findWithMove(record, move);
01718 if (record_child)
01719 {
01720 int pass_left_child = pass_left;
01721 if (move.isPass()) --pass_left_child;
01722 const PathEncoding path_child(path, move.getMove());
01723 NtesukiResult result_child;
01724 TRY_DFPN;
01725 result_child =
01726 record_child->getValueOr<A>(pass_left_child, path_child,
01727 iwscheme);
01728 CATCH_DFPN;
01729
01730 if (record_child->isVisited())
01731 {
01732
01733 record->setLoopWithPath<A>(pass_left, path);
01734 ntesuki_assert(record->isLoopWithPath<A>(pass_left, path));
01735 TRY_DFPN;
01736 record->setResult<A>(pass_left, NtesukiResult(1, 1),
01737 NtesukiMove::INVALID(), false);
01738 CATCH_DFPN;
01739 best_disproof = 0;
01740 return &move;
01741 }
01742
01743 proof = result_child.proof();
01744 disproof = result_child.disproof();
01745
01746 if (result_child.isCheckmateSuccess())
01747 {
01748 ntesuki_assert(disproof >= ProofDisproof::DISPROOF_LIMIT);
01749 move.setCheckmateSuccess<A>(pass_left);
01750 if (move.isPass())
01751 {
01752
01753 record->setNtesuki<A>(pass_left);
01754
01755 if (ptt_invalid_defense)
01756 {
01757 TRY_DFPN;
01758 simulateSiblingsSuccess<T>(record, record_child, pass_left,
01759 pass_success_count,
01760 pass_count);
01761 CATCH_DFPN;
01762 RETURN_ON_STOP(NULL);
01763 goto re_select_move_defense;
01764 }
01765 }
01766 if (ptt_siblings_success && !move.isCheck())
01767 {
01768 TRY_DFPN;
01769 simulateSiblingsSuccess<T>(record, record_child, pass_left,
01770 sibling_defense_success_count,
01771 sibling_defense_count);
01772 CATCH_DFPN;
01773 RETURN_ON_STOP(NULL);
01774
01775 goto re_select_move_defense;
01776 }
01777 continue;
01778 }
01779 else if (result_child.isCheckmateFail())
01780 {
01781 if (move.isCheck() && read_check_defense)
01782 {
01783 ++disproof_by_inversion_count;
01784 }
01785 if (result_child == ProofDisproof::LoopDetection())
01786 {
01787 record->setLoopWithPath<A>(pass_left, path);
01788 TRY_DFPN;
01789 record->setResult<A>(pass_left, NtesukiResult(1, 1),
01790 NtesukiMove::INVALID(), false);
01791 CATCH_DFPN;
01792 best_disproof = 0;
01793 return &move;
01794 }
01795
01796 ntesuki_assert(proof >= ProofDisproof::PROOF_LIMIT);
01797 move.setCheckmateFail<A>(pass_left);
01798 TRY_DFPN;
01799 record->setResult<A>(pass_left, result_child,
01800 move, false);
01801 CATCH_DFPN;
01802 best_disproof = 0;
01803 return &move;
01804 }
01805
01806 min_child_age = std::min(min_child_age,
01807 record_child->distance);
01808 if ((record_child->distance <= record->distance) &&
01809 !move.isPass())
01810 {
01811 if (!record->useOld<A>(pass_left))
01812 {
01813 continue;
01814 }
01815 }
01816 }
01817
01818
01819
01820 if (record->useOld<A>(pass_left))
01821 {
01822 sum_proof = std::max(proof, sum_proof);
01823 }
01824 else if (NtesukiRecord::max_for_split && record->is_split)
01825 {
01826 sum_proof = std::max(proof, sum_proof);
01827 }
01828 else
01829 {
01830 sum_proof = addWithSaturation(ProofDisproof::PROOF_LIMIT,
01831 proof, sum_proof);
01832 }
01833
01834 if (disproof < best_disproof)
01835 {
01836 best_move = &move;
01837 second_disproof = best_disproof;
01838 best_disproof = disproof;
01839 best_proof = proof;
01840 }
01841 else if (disproof < second_disproof)
01842 {
01843 second_disproof = disproof;
01844 }
01845 }
01846
01847
01848
01849 if (NULL == best_move)
01850 {
01851 ntesuki_assert(sum_proof == 0);
01852
01853 if (delay_non_pass &&
01854 read_non_pass == false)
01855 {
01856 ntesuki_assert(!under_attack);
01857
01858 read_non_pass = true;
01859 record->setUseOld<A>(pass_left, false);
01860 record->setNtesuki<A>(pass_left);
01861
01862 if (ptt_invalid_defense)
01863 {
01864 NtesukiMove move_pass = moves.front();
01865 ntesuki_assert(move_pass.isPass());
01866 NtesukiRecord *record_pass = table.findWithMove(record, move_pass);
01867 const PathEncoding path_child(path, move_pass.getMove());
01868
01869 ntesuki_assert(record_pass->getValueWithPath<A>(pass_left - 1,
01870 path_child).isCheckmateSuccess());
01871 TRY_DFPN;
01872 simulateSiblingsSuccess<T>(record, record_pass, pass_left,
01873 pass_success_count,
01874 pass_count);
01875 CATCH_DFPN;
01876 RETURN_ON_STOP(NULL);
01877 }
01878 goto re_select_move_defense;
01879 }
01880
01881 if (!record->useOld<A>(pass_left))
01882 {
01883 if (SHRT_MAX != min_child_age)
01884 {
01885 record->setUseOld<A>(pass_left, true);
01886
01887 ntesuki_assert(min_child_age <= record->distance);
01888 record->distance = min_child_age;
01889
01890 goto re_select_move_defense;
01891 }
01892 }
01893
01894 if (delay_interpose &&
01895 read_interpose == false)
01896 {
01897 read_interpose = true;
01898 record->setUseOld<A>(pass_left, false);
01899 record->setReadInterpose(pass_left);
01900 TRY_DFPN;
01901 handleInterpose<T>(record, pass_left);
01902 CATCH_DFPN;
01903 RETURN_ON_STOP NULL;
01904
01905 goto re_select_move_defense;
01906 }
01907
01908
01909 switch(isscheme)
01910 {
01911 case NtesukiRecord::no_is:
01912 ntesuki_assert(read_check_defense == false);
01913 break;
01914 case NtesukiRecord::tonshi_is:
01915 handleTonshi<T>(record, pass_left, last_move);
01916 RETURN_ON_STOP NULL;
01917 break;
01918 case NtesukiRecord::delay_is:
01919 if (read_check_defense == false)
01920 {
01921 ++proof_without_inversion_count;
01922 read_check_defense = true;
01923 record->setReadCheckDefense(pass_left);
01924 goto re_select_move_defense;
01925 }
01926 break;
01927 case NtesukiRecord::normal_is:
01928 ntesuki_assert(read_check_defense == true);
01929 break;
01930 }
01931
01932
01933 TRY_DFPN;
01934 record->setResult<A>(pass_left, ProofDisproof::Checkmate(),
01935 NtesukiMove::INVALID(), false);
01936 CATCH_DFPN;
01937 return NULL;
01938 }
01939 ntesuki_assert(best_move);
01940 ntesuki_assert(sum_proof != 0);
01941 ntesuki_assert(best_disproof != 0);
01942
01943 if (record->useOld<A>(pass_left))
01944 {
01945 ntesuki_assert(min_child_age != SHRT_MAX);
01946 record->distance = min_child_age;
01947 }
01948 average_cost /= average_cost_count;
01949 step_cost = std::max(average_cost, 1);
01950 return best_move;
01951 }
01952
01953 template <Player T>
01954 void osl::ntesuki::NtesukiSearcher::
01955 handleTonshi(NtesukiRecord *record,
01956 int pass_left,
01957 const Move last_move)
01958 {
01959 const Player A = PlayerTraits<T>::opponent;
01960 const Player D = T;
01961
01962 if (pass_left > 0)
01963 {
01964 NtesukiResult result_defender =
01965 record->getValueWithPath<D>(pass_left - 1, path);
01966 if (!result_defender.isFinal())
01967 {
01968
01969
01970 record->setResult<A>(pass_left, ProofDisproof::Bottom(),
01971 NtesukiMove::INVALID(), false);
01972 const unsigned int read_node_limit_orig = read_node_limit;
01973 int ratio = 1;
01974
01975 if ((record->distance / 2) == 0)
01976 ratio = 8;
01977 else if ((record->distance / 2) == 1)
01978 ratio = 2;
01979
01980 read_node_limit = node_count + READ_ATTACK_BACK_LIMIT * ratio;
01981
01982 NtesukiRecord::UnVisitLock unVisitLock(record);
01983 TRY_DFPN;
01984 result_defender = attack<T>(record, NULL, NULL,
01985 INITIAL_PROOF_LIMIT, INITIAL_PROOF_LIMIT,
01986 pass_left - 1, last_move);
01987 CATCH_DFPN;
01988
01989 if (result_defender.isCheckmateSuccess())
01990 {
01991 ++attack_back_count;
01992 }
01993
01994 read_node_limit = read_node_limit_orig;
01995 RETURN_ON_STOP;
01996 }
01997
01998 if (result_defender.isFinal())
01999 {
02000 return;
02001 }
02002 }
02003 }
02004
02005 template <Player T>
02006 void osl::ntesuki::NtesukiSearcher::
02007 simulateSiblingsSuccess(NtesukiRecord *record,
02008 NtesukiRecord *record_best,
02009 int pass_left,
02010 unsigned int& success_count,
02011 unsigned int& total_count)
02012 {
02013 LockGC glock(table);
02014
02015 const Player A = PlayerTraits<T>::opponent;
02016 if (!record_best) return;
02017 ntesuki_assert(record_best);
02018 ntesuki_assert(record_best->getValue<A>(pass_left).isCheckmateSuccess());
02019
02020 NtesukiMoveList moves;
02021 mg->generate<T>(state, moves);
02022
02023 for (NtesukiMoveList::iterator move_it = moves.begin();
02024 move_it != moves.end(); ++move_it)
02025 {
02026 NtesukiMove& move = *move_it;
02027 NtesukiRecord *record_child = table.allocateWithMove(record,
02028 move);
02029 if (record_child == 0)
02030 {
02031 *stop_flag = TableLimitReached;
02032 return;
02033 }
02034 ntesuki_assert(record_child);
02035 if (record_child == record_best) continue;
02036 if (record_child->isVisited()) continue;
02037
02038 ntesuki_assert(record_child);
02039 const PathEncoding path_child(path, move.getMove());
02040 const NtesukiResult result_child = record_child->getValueWithPath<A>(pass_left,
02041 path_child);
02042 if (result_child.isFinal())
02043 {
02044 continue;
02045 }
02046
02047 bool simulation_result;
02048 total_count++;
02049 CallSimulationDefense<NtesukiSimulationSearcher, T>
02050 helper(simulator, table, record_child, record_best,
02051 pass_left, simulation_result, move.getMove());
02052 TRY_DFPN;
02053 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, move.getMove(), helper);
02054 CATCH_DFPN;
02055 RETURN_ON_STOP;
02056
02057 if (simulation_result)
02058 {
02059 success_count++;
02060 ntesuki_assert(record_child->getValueWithPath<A>(pass_left,
02061 path_child).isCheckmateSuccess());
02062 move.setBySimulation();
02063 move.setCheckmateSuccess<A>(pass_left);
02064 }
02065 }
02066 }
02067
02068 template <Player T>
02069 void osl::ntesuki::NtesukiSearcher::
02070 handleInterpose(NtesukiRecord* record,
02071 int pass_left)
02072 {
02073 const Player A = PlayerTraits<T>::opponent;
02074 ntesuki_assert(T == state.getTurn());
02075
02076 NtesukiMoveList moves;
02077 mg->generate<T>(state, moves);
02078
02079 for (NtesukiMoveList::iterator move_it = moves.begin();
02080 move_it != moves.end(); ++move_it)
02081 {
02082 if (move_it->isInterpose() &&
02083 !move_it->isCheckmateSuccess<A>(pass_left))
02084 {
02085 NtesukiRecord *record_child = table.allocateWithMove(record,
02086 *move_it);
02087 if (record_child == 0)
02088 {
02089 *stop_flag = TableLimitReached;
02090 return;
02091 }
02092 ntesuki_assert(record_child);
02093
02094 const PathEncoding path_child(path, move_it->getMove());
02095 if(record_child->getValueWithPath<A>(pass_left,
02096 path_child).isFinal())
02097 {
02098 continue;
02099 }
02100 ntesuki_assert(record_child->getBestMove<A>(pass_left).isInvalid());
02101
02102 NtesukiMoveList::iterator best_it = moves.begin();
02103 for (; best_it != moves.end(); ++best_it)
02104 {
02105 if (best_it->to() == move_it->to() &&
02106 best_it->isCheckmateSuccess<A>(pass_left)) break;
02107 }
02108 if (best_it == moves.end())
02109 {
02110 continue;
02111 }
02112 const NtesukiRecord* record_best = table.findWithMove(record, *best_it);
02113 ntesuki_assert(record_best);
02114
02115 bool simulation_result;
02116 CallSimulationDefense<NtesukiSimulationSearcher, T>
02117 helper(simulator, table, record_child, record_best,
02118 pass_left, simulation_result, move_it->getMove());
02119 TRY_DFPN;
02120 ApplyMoveWithPath<T>::doUndoMoveOrPass(state, path, move_it->getMove(), helper);
02121 CATCH_DFPN;
02122 RETURN_ON_STOP;
02123
02124 if (simulation_result)
02125 {
02126 move_it->setBySimulation();
02127 move_it->setCheckmateSuccess<A>(pass_left);
02128 }
02129 else if (record_child->getValue<A>(pass_left).isCheckmateFail())
02130 {
02131 break;
02132 }
02133 }
02134 }
02135 }
02136
02137
02138
02139 template <Player A>
02140 int osl::ntesuki::NtesukiSearcher::
02141 search()
02142 {
02143 NtesukiRecord::pass_count = 0;
02144 const Player D = PlayerTraits<A>::opponent;
02145 const HashKey key = HashKey::calcHash(state);
02146
02147 NtesukiRecord *record = table.allocateRoot(key, PieceStand(WHITE, state),
02148 0, &state);
02149 ntesuki_assert(record);
02150
02151 NtesukiResult result;
02152 if (A == state.getTurn())
02153 {
02154 const Player T = A;
02155 result = attack<T>(record, NULL, NULL,
02156 INITIAL_PROOF_LIMIT,
02157 INITIAL_DISPROOF_LIMIT,
02158 max_pass - 1, Move::INVALID());
02159 }
02160 else
02161 {
02162 const Player T = D;
02163 if (0 == (max_pass - 1) &&
02164 !EffectUtil::isKingInCheck(D, state))
02165 {
02166 if (verbose) std::cerr << "No Check" << std::endl;
02167 return NtesukiNotFound;
02168 }
02169 else
02170 {
02171 result = defense<T>(record, NULL, NULL,
02172 INITIAL_PROOF_LIMIT,
02173 INITIAL_DISPROOF_LIMIT,
02174 max_pass - 1,
02175 Move::INVALID());
02176 }
02177 }
02178
02179 if (node_count > read_node_limit || *stop_flag)
02180 {
02181 if (verbose) std::cerr << "Limit Reached\t" << result << std::endl;
02182 return ReadLimitReached;
02183 }
02184 else
02185 {
02186 if (verbose) std::cerr << "result:\t" << result << std::endl;
02187 if (result.isCheckmateSuccess())
02188 {
02189 for (unsigned int i = 0; i < max_pass; ++i)
02190 {
02191 if (record->getValue<A>(i).isCheckmateSuccess())
02192 {
02193 return i;
02194 }
02195 }
02196 }
02197 }
02198
02199 ntesuki_assert(result.isCheckmateFail());
02200 return NtesukiNotFound;
02201 }
02202
02203
02204
02205