00001
00002
00003 #include "osl/checkmate/dfpn.h"
00004 #include "osl/checkmate/dfpnParallel.h"
00005 #include "osl/checkmate/dfpnRecord.h"
00006 #include "osl/checkmate/immediateCheckmate.h"
00007 #include "osl/checkmate/fixedDepthSolverExt.h"
00008 #include "osl/checkmate/libertyEstimator.h"
00009 #include "osl/checkmate/pieceCost.h"
00010 #include "osl/checkmate/proofPieces.h"
00011 #include "osl/checkmate/disproofPieces.h"
00012 #include "osl/checkmate/oracleAdjust.h"
00013 #include "osl/checkmate/pawnCheckmateMoves.h"
00014 #include "osl/checkmate/proofTreeDepthDfpn.h"
00015 #include "osl/move_generator/escape_.h"
00016 #include "osl/move_generator/addEffectWithEffect.h"
00017 #include "osl/move_classifier/check_.h"
00018 #include "osl/move_classifier/moveAdaptor.h"
00019 #include "osl/move_classifier/pawnDropCheckmate.h"
00020 #include "osl/csa.h"
00021
00022 #include "osl/stat/ratio.h"
00023 #include "osl/hash/hashRandomPair.h"
00024 #include "osl/bits/align16New.h"
00025 #include "osl/oslConfig.h"
00026 #include <tuple>
00027 #include <unordered_map>
00028 #include <vector>
00029 #include <forward_list>
00030 #include <iostream>
00031 #include <iomanip>
00032 #include <bitset>
00033
00034
00035
00036 #define GRAND_PARENT_SIMULATION
00037 #define GRAND_PARENT_DELAY
00038
00039 #define INITIAL_DOMINANCE
00040
00041 #define ROOT_PROOF_TOL 65536ul*1024
00042
00043 #define ROOT_DISPROOF_TOL 65536ul*1024
00044
00045
00046 #define CHECKMATE_D2
00047
00048 #define PROOF_AVERAGE
00049 #define DISPROOF_AVERAGE
00050
00051 #define KAKINOKI_FALSE_BRANCH_SEARCH
00052 #define IGNORE_MONSTER_CHILD
00053 #define KISHIMOTO_WIDEN_THRESHOLD
00054 #define ADHOC_SUM_RESTRICTION
00055 #define AGGRESSIVE_FIND_DAG
00056 #define AGGRESSIVE_FIND_DAG2
00057 #define CHECKMATE_A3_GOLD
00058 #define CHECKMATE_A3_SIMULLATION
00059
00060
00061 #define MEMORIZE_SOLVED_IN_BITSET
00062
00063
00064
00065 static const int UpwardWeight = 2, SacrificeBlockCount = 0, LongDropCount = 1;
00066 #ifdef MINIMAL
00067 static const int MaxDagTraceDepth = 64;
00068 #else
00069 static const int MaxDagTraceDepth = 1600;
00070 #endif
00071 static const unsigned int NoPromoeIgnoreProofThreshold = 100;
00072 static const unsigned int NoPromoeIgnoreDisproofThreshold = 200;
00073 static const unsigned int IgnoreUpwardProofThreshold = 100;
00074 static const unsigned int IgnoreUpwardDisproofThreshold = 100;
00075 #ifdef MEMORIZE_SOLVED_IN_BITSET
00076 static const unsigned int InitialDominanceProofMax = 35;
00077 #else
00078 static const unsigned int InitialDominanceProofMax = 20;
00079 #endif
00080 static const unsigned int InitialDominanceDisproofMax = 110;
00081 static const unsigned int DagFindThreshold = 64;
00082 static const unsigned int DagFindThreshold2 = 256;
00083 static const int EnableGCDepth = 512;
00084 static const int AdHocSumScale = 128;
00085 static const size_t GrowthLimitInfty = std::numeric_limits<size_t>::max();
00086 const int ProofSimulationTolerance = 1024;
00087
00088
00089
00090 #ifndef NDEBUG
00091 static size_t timer = 0;
00092 const size_t debug_time_start = 3851080;
00093 #endif
00094
00095
00096 namespace osl
00097 {
00098 namespace checkmate
00099 {
00100 inline int log2(uint32_t n)
00101 {
00102 return (n <= 1) ? 1 : 32 - __builtin_clz(n);
00103 }
00104 inline int slow_increase(uint32_t n)
00105 {
00106 return log2(n);
00107 }
00108 #ifdef DFPN_DEBUG
00109 struct NodeIDTable : public std::unordered_map<HashKey, int, std::hash<HashKey>>
00110 {
00111 size_t cur;
00112 NodeIDTable() : cur(0) {}
00113 int id(const HashKey& key)
00114 {
00115 int& ret = (*this)[key];
00116 if (ret == 0)
00117 ret = ++cur;
00118 return ret;
00119 }
00120 } node_id_table;
00121 CArray<int,3> debug_node = {{
00122 }};
00124 struct NodeCountTable : public std::unordered_map<int, std::pair<int,std::vector<Move> > >
00125 {
00126 typedef std::pair<int,std::vector<Move> > pair_t;
00127 ~NodeCountTable()
00128 {
00129 std::cerr << "timer " << timer << "\n";
00130 vector<std::pair<int,int> > all;
00131 all.reserve(size());
00132 for (const auto& v: *this)
00133 all.push_back(std::make_pair(-v.second.first, v.first));
00134 std::sort(all.begin(), all.end());
00135 for (size_t i=0; i<std::min((size_t)10, size()); ++i){
00136 std::cerr << "freq " << -all[i].first << " id " << std::setw(5) << all[i].second << ' ';
00137 for (Move m: (*this)[all[i].second].second)
00138 std::cerr << record::csa::show(m);
00139 std::cerr << "\n";
00140 }
00141 }
00142 } node_count_table;
00143 #endif
00144
00145 struct SimpleTwinList : std::forward_list<PathEncoding>
00146 {
00147 };
00148
00149 struct DfpnPathRecord
00150 {
00151 static const int MaxDistance = 1024*128;
00152 SimpleTwinList twin_list;
00154 int distance;
00155 bool visiting;
00156 size_t node_count;
00157 DfpnPathRecord()
00158 : distance(MaxDistance), visiting(false), node_count(0)
00159 {
00160 }
00161 };
00162 template <bool Enabled=true>
00163 struct DfpnVisitLock
00164 {
00165 DfpnVisitLock(const DfpnVisitLock&) = delete;
00166 DfpnVisitLock& operator=(const DfpnVisitLock&) = delete;
00167
00168 DfpnPathRecord *record;
00169 DfpnVisitLock(DfpnPathRecord *r) : record(r)
00170 {
00171 if (! Enabled) return;
00172 assert(! record->visiting);
00173 record->visiting = true;
00174 }
00175 ~DfpnVisitLock()
00176 {
00177 if (! Enabled) return;
00178 assert(record->visiting);
00179 record->visiting = false;
00180 }
00181 };
00182 enum LoopToDominance { NoLoop=0, BadAttackLoop };
00183 struct DfpnPathList : public std::forward_list<std::pair<PieceStand, DfpnPathRecord>>
00184 {
00185 typedef std::forward_list<std::pair<PieceStand, DfpnPathRecord> > list_t;
00186 private:
00187 template <Player Attack>
00188 iterator find(PieceStand black, LoopToDominance& loop)
00189 {
00190 loop = NoLoop;
00191 iterator ret = end();
00192 for (iterator p=begin(); p!=end(); ++p) {
00193 if (p->first == black) {
00194 assert(p->second.distance != DfpnPathRecord::MaxDistance);
00195 ret = p;
00196 if (loop || p->second.visiting) break;
00197 }
00198 if (! p->second.visiting)
00199 continue;
00200 if (p->first.isSuperiorOrEqualTo(black)) {
00201 if (Attack == BLACK) {
00202 loop = BadAttackLoop;
00203 if (ret != end()) break;
00204 }
00205 }
00206 else if (black.isSuperiorOrEqualTo(p->first)) {
00207 if (Attack == WHITE) {
00208 loop = BadAttackLoop;
00209 if (ret != end()) break;
00210 }
00211 }
00212 }
00213 return ret;
00214 }
00215 public:
00216 template <Player Attack>
00217 DfpnPathRecord *allocate(PieceStand black, int depth, LoopToDominance& loop,
00218 size_t& size)
00219 {
00220 iterator ret = find<Attack>(black, loop);
00221 if (ret != end()) {
00222 ret->second.distance = std::min(depth, ret->second.distance);
00223 return &(ret->second);
00224 }
00225 ++size;
00226 push_front(std::make_pair(black, DfpnPathRecord()));
00227 DfpnPathRecord *record = &(begin()->second);
00228 assert(record->distance == DfpnPathRecord::MaxDistance);
00229 record->distance = depth;
00230 return record;
00231 }
00232 const DfpnPathRecord *probe(PieceStand black) const
00233 {
00234 for (const auto& v: *this) {
00235 if (v.first == black)
00236 return &(v.second);
00237 }
00238 return 0;
00239 }
00240 static bool precious(const DfpnPathRecord& record, size_t threshold)
00241 {
00242 return record.visiting
00243 || record.node_count > threshold
00244 || (! record.twin_list.empty() && record.node_count > threshold - 10);
00245 }
00246 size_t runGC(size_t threshold)
00247 {
00248 size_t removed = 0;
00249 list_t::iterator p=begin();
00250 while (p!=end()) {
00251 list_t::iterator q=p;
00252 ++q;
00253 if (q == end())
00254 break;
00255 if (! precious(q->second, threshold)) {
00256 erase_after(p);
00257 ++removed;
00258 continue;
00259 }
00260 p = q;
00261 }
00262 if (! empty() && ! precious(begin()->second, threshold)) {
00263 pop_front();
00264 ++removed;
00265 }
00266 return removed;
00267 }
00268 };
00269 class DfpnPathTable
00270 {
00271 typedef std::unordered_map<BoardKey, DfpnPathList, std::hash<BoardKey>> table_t;
00272 table_t table;
00273 size_t total_size;
00274 size_t gc_threshold;
00275 public:
00276 DfpnPathTable() : total_size(0), gc_threshold(10)
00277 {
00278 }
00279 template <Player Attack>
00280 DfpnPathRecord *allocate(const HashKey& key, int depth, LoopToDominance& loop)
00281 {
00282 DfpnPathList& l = table[key.boardKey()];
00283 return l.allocate<Attack>(key.blackStand(), depth, loop,
00284 total_size);
00285 }
00286 const DfpnPathRecord *probe(const HashKey& key) const
00287 {
00288 table_t::const_iterator p = table.find(key.boardKey());
00289 if (p == table.end())
00290 return 0;
00291 return p->second.probe(key.blackStand());
00292 }
00293 void clear() { table.clear(); }
00294 size_t runGC()
00295 {
00296 size_t removed = 0;
00297 for (table_t::iterator p=table.begin(); p!=table.end(); ++p)
00298 removed += p->second.runGC(gc_threshold);
00299 total_size -= removed;
00300 gc_threshold += 15;
00301 static double memory_threshold = 0.8;
00302 double memory = OslConfig::memoryUseRatio();
00303 if (memory > memory_threshold) {
00304 gc_threshold += 15;
00305 memory_threshold += 1.0/128;
00306 }
00307 return removed;
00308 }
00309 size_t size() const { return total_size; }
00310 void rehash(size_t bucket_size) { table.rehash(bucket_size); }
00311 };
00312
00313 int attackProofCost(Player attacker, const NumEffectState& state, Move move)
00314 {
00315 int proof = 0;
00316 if (! move.isCapture())
00317 {
00318 const Square from=move.from(), to=move.to();
00319 const int a = (state.countEffect(attacker,to)
00320 + (from.isPieceStand() ? 1 : 0));
00321 int d = state.countEffect(alt(attacker),to);
00322 if (a <= d)
00323 {
00324 const Ptype ptype = move.ptype();
00325 proof = PieceCost::attack_sacrifice_cost[ptype];
00326 if ((d >= 2) && (a == d))
00327 proof /= 2;
00328 }
00329 }
00330 return proof;
00331 }
00332 }
00333 }
00334
00335
00336 struct osl::checkmate::Dfpn::NodeBase
00337 {
00338
00339 HashKey hash_key;
00340 PathEncoding path;
00341 ProofDisproof threshold;
00342 Move moved;
00343 PieceStand white_stand;
00344
00345 DfpnRecord record;
00346 DfpnPathRecord *path_record;
00347 };
00348
00349 struct osl::checkmate::Dfpn::Node : NodeBase
00350 {
00351 DfpnMoveVector moves;
00352 FixedCapacityVector<DfpnRecord,DfpnMaxUniqMoves> children;
00353 FixedCapacityVector<const DfpnPathRecord*,DfpnMaxUniqMoves> children_path;
00354 CArray<HashKey,DfpnMaxUniqMoves> hashes;
00355 FixedCapacityVector<int8_t,DfpnMaxUniqMoves> proof_cost;
00356 size_t visit_time;
00357
00358 const PieceStand nextWhiteStand(Player P, Move move) const
00359 {
00360 assert(move.player() == P);
00361 return (P == WHITE) ? white_stand.nextStand(P, move) : white_stand;
00362 }
00363 void clear()
00364 {
00365 moves.clear();
00366 proof_cost.clear();
00367 children.clear();
00368 children_path.clear();
00369 }
00370 void allocate(int n)
00371 {
00372 while (n--) {
00373 proof_cost.push_back(0);
00374 children.push_back(DfpnRecord());
00375 children_path.push_back(0);
00376 }
00377 }
00378 void setLoopDetection()
00379 {
00380 assert(! (record.proof_disproof.isFinal()
00381 && ! record.proof_disproof.isLoopDetection()));
00382 record.proof_disproof = ProofDisproof(1,1);
00383 path_record->twin_list.push_front(path);
00384 }
00385 const PathEncoding newPath(int c) const
00386 {
00387 PathEncoding n = path;
00388 n.pushMove(moves[c]);
00389 return n;
00390 }
00391 bool isLoop(int c) const
00392 {
00393 if (! children_path[c] || children[c].proof_disproof.isFinal())
00394 return false;
00395 if (children_path[c]->visiting)
00396 return true;
00397 const PathEncoding p = newPath(c);
00398 const SimpleTwinList& tl = children_path[c]->twin_list;
00399 return std::find(tl.begin(), tl.end(), p) != tl.end();
00400 }
00401 void setCheckmateAttack(Player attack, int best_i)
00402 {
00403 DfpnRecord& child = children[best_i];
00404 assert(child.proof_disproof.isCheckmateSuccess());
00405 record.proof_disproof = child.proof_disproof;
00406 record.best_move = moves[best_i];
00407 const PieceStand proof_pieces
00408 = ProofPieces::attack(child.proofPieces(), record.best_move,
00409 record.stands[attack]);
00410 record.setProofPieces(proof_pieces);
00411 }
00412 void setNoCheckmateDefense(Player attack, int best_i)
00413 {
00414 DfpnRecord& child = children[best_i];
00415 assert(child.proof_disproof.isCheckmateFail());
00416 assert(! child.proof_disproof.isLoopDetection());
00417 record.proof_disproof = child.proof_disproof;
00418 record.best_move = moves[best_i];
00419 const PieceStand disproof_pieces
00420 = DisproofPieces::defense(child.disproofPieces(), record.best_move,
00421 record.stands[alt(attack)]);
00422 record.setDisproofPieces(disproof_pieces);
00423 }
00424 void setCheckmateDefense(Player attack, const NumEffectState& state)
00425 {
00426 assert(moves.size());
00427 assert(record.proof_disproof.isCheckmateSuccess());
00428 record.proof_disproof = ProofDisproof::Checkmate();
00429 PieceStand result = record.proof_pieces_candidate;
00430 const Player defender = alt(attack);
00431 if (! state.inUnblockableCheck(defender))
00432 ProofPiecesUtil::addMonopolizedPieces(state, attack, record.stands[attack],
00433 result);
00434 record.setProofPieces(result);
00435 }
00436 void setNoCheckmateAttack(Player attack, const NumEffectState& state)
00437 {
00438 assert(moves.size());
00439 assert(record.proof_disproof.isCheckmateFail());
00440 assert(! record.proof_disproof.isLoopDetection());
00441 PieceStand result = record.proof_pieces_candidate;
00442 ProofPiecesUtil::addMonopolizedPieces(state, alt(attack), record.stands[alt(attack)],
00443 result);
00444 record.setDisproofPieces(result);
00445 }
00446 void setCheckmateChildInDefense(size_t i)
00447 {
00448 assert(children[i].proof_disproof.isCheckmateSuccess());
00449 #ifdef MEMORIZE_SOLVED_IN_BITSET
00450 record.solved |= (1ull<<i);
00451 #endif
00452 record.min_pdp = std::min(record.min_pdp, children[i].proof_disproof.disproof());
00453 record.proof_pieces_candidate
00454 = record.proof_pieces_candidate.max(children[i].proofPieces());
00455 }
00456 void setNoCheckmateChildInAttack(size_t i)
00457 {
00458 assert(children[i].proof_disproof.isCheckmateFail());
00459 #ifdef MEMORIZE_SOLVED_IN_BITSET
00460 record.solved |= (1ull<<i);
00461 #endif
00462 record.min_pdp = std::min(record.min_pdp, children[i].proof_disproof.proof());
00463 record.proof_pieces_candidate
00464 = record.proof_pieces_candidate.max(children[i].disproofPieces());
00465 }
00466 };
00467
00468 struct osl::checkmate::Dfpn::Tree
00469 #if OSL_WORDSIZE == 32
00470 : public misc::Align16New
00471 #endif
00472 {
00473 NumEffectState state;
00474 int depth;
00475 #ifdef MINIMAL
00476 enum { MinimalMaxDepth = 256 };
00477 Node node[MinimalMaxDepth];
00478 #else
00479 boost::scoped_array<Node> node;
00480 #endif
00481 const int MaxDepth;
00482 Tree(int
00483 #ifndef MINIMAL
00484 max_depth
00485 #endif
00486 ) : state(SimpleState(HIRATE)),
00487 MaxDepth(
00488 #ifndef MINIMAL
00489 max_depth
00490 #else
00491 MinimalMaxDepth
00492 #endif
00493 )
00494 {
00495 #ifndef MINIMAL
00496 node.reset(new Node[max_depth]);
00497 #endif
00498 }
00499 bool inCheck(Player P) const
00500 {
00501 return state.inCheck(P);
00502 }
00503 const Piece king(Player P) const { return state.kingPiece(P); }
00504 void newVisit(Player P, Move move, const HashKey& next_hash)
00505 {
00506 assert(P == move.player());
00507 const Node& node = this->node[depth];
00508 assert(next_hash == node.hash_key.newHashWithMove(move));
00509 Node& next = this->node[depth+1];
00510 next.moved = move;
00511 next.white_stand = node.nextWhiteStand(P, move);
00512 next.path = node.path;
00513 next.clear();
00514 next.hash_key = next_hash;
00515 }
00516 void setNoCheckmateChildInAttack(size_t best_i)
00517 {
00518 Node &node = this->node[depth];
00519 node.setNoCheckmateChildInAttack(best_i);
00520 }
00521 void setNoCheckmateDefense(Player attack, int best_i)
00522 {
00523 Node &node = this->node[depth];
00524 node.setNoCheckmateDefense(attack, best_i);
00525 }
00526 void dump(int lines, int depth=0) const
00527 {
00528 #ifndef NDEBUG
00529 if (depth == 0)
00530 depth = this->depth;
00531 for (int i=0; i<=depth; ++i) {
00532 std::cerr << "history " << i << " " << node[i].moved << " ";
00533 node[i].hash_key.dumpContentsCerr();
00534 std::cerr << "\n";
00535 }
00536 const int my_distance = node[depth].path_record ? node[depth].path_record->distance : -1;
00537 const Node &node = this->node[depth];
00538 std::cerr << "time " << node.visit_time << " (" << timer << ") here " << lines << "\n" << state;
00539 std::cerr << " false-branch? " << (bool)node.record.false_branch << "\n";
00540 #ifdef MEMORIZE_SOLVED_IN_BITSET
00541 std::cerr << " solved " << std::bitset<32>(node.record.solved) << "\n";
00542 #endif
00543 std::cerr << " dags " << std::bitset<32>(node.record.solved) << "\n";
00544 std::cerr << " last_to " << node.record.last_to
00545 << " threshold " << node.threshold
00546 << " my_distance " << my_distance << "\n";
00547 for (size_t i=0; i<node.moves.size(); ++i) {
00548 std::cerr << " " << i << " " << node.moves[i]
00549 << " " << node.children[i].proof_disproof
00550 << " " << (int)node.proof_cost[i]
00551 << " " << node.children[i].best_move
00552 << " depth " << (node.children_path[i] ? node.children_path[i]->distance : -1)
00553 << " count " << node.children[i].node_count
00554 << "\n";
00555 }
00556 std::cerr << node.record.proof_disproof << " " << node.record.best_move << "\n";
00557 std::cerr << "path " << node.path << " twins ";
00558 if (node.path_record) {
00559 for (const auto& path: node.path_record->twin_list)
00560 std::cerr << path << " ";
00561 }
00562 std::cerr << "\n";
00563 #endif
00564 }
00565 #ifdef DFPN_DEBUG
00566 void showPath(const char *message, size_t table_size) const
00567 {
00568 std::cerr << message << " depth " << depth << " node " << node_id_table.id(node[depth].hash_key)
00569 << " time " << timer << " table " << table_size << ' ';
00570 for (int i=0; i<=depth; ++i)
00571 std::cerr << record::csa::show(node[i].moved);
00572 std::cerr << "\n";
00573 }
00574 struct Logging
00575 {
00576 const Tree *tree;
00577 const DfpnTable *table;
00578 const size_t old_table_size;
00579 Logging(Tree *tr, DfpnTable *tb, const char *message)
00580 : tree(tr), table(tb), old_table_size(table->size())
00581 {
00582 if (timer < debug_time_start)
00583 return;
00584 tree->showPath(message, old_table_size);
00585 }
00586 ~Logging()
00587 {
00588 if (timer < debug_time_start)
00589 return;
00590 const Node& node = tree->node[tree->depth];
00591 const int id = node_id_table.id(node.hash_key);
00592 std::cerr << " node " << id << " " << node.threshold
00593 << " " << node.record.proof_disproof << "\n";
00594 if (std::find(debug_node.begin(), debug_node.end(), id)
00595 != debug_node.end() && timer > debug_time_start)
00596 tree->dump(__LINE__);
00597 if (table->size() == old_table_size)
00598 countImmediateReturns(id);
00599 }
00600 void countImmediateReturns(int id)
00601 {
00602 NodeCountTable::pair_t& p = node_count_table[id];
00603 if (p.first == 0) {
00604 for (int i=0; i<=tree->depth; ++i)
00605 p.second.push_back(tree->node[i].moved);
00606 }
00607 ++(p.first);
00608 }
00609 };
00610 #endif
00611 };
00612
00613
00614 #ifdef DFPN_STAT
00615 osl::CArray<osl::CArray<int,64>,2> count2proof, count2disproof, count2unknown;
00616 #endif
00617
00618 struct osl::checkmate::DfpnTable::List : public std::forward_list<DfpnRecord>
00619 {
00620 typedef std::forward_list<DfpnRecord> list_t;
00621 #ifdef OSL_DFPN_SMP
00622 mutable Mutex mutex;
00623 #endif
00624 List() {}
00625 List(const List& src) : list_t(src) {}
00626
00627 template <Player Attack>
00628 const DfpnRecord probe(const HashKey& key, PieceStand white_stand) const;
00629 template <Player Attack>
00630 const DfpnRecord findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const;
00631 template <Player Attack>
00632 void showProofOracles(const HashKey& key, PieceStand white_stand, Move last_move) const;
00633 bool store(DfpnRecord& value, int leaving_thread_id)
00634 {
00635 #ifdef USE_TBB_HASH
00636 SCOPED_LOCK(lk,mutex);
00637 #endif
00638 for (DfpnRecord& record: *this) {
00639 if (record.stands[BLACK] == value.stands[BLACK]) {
00640 #ifdef OSL_DFPN_SMP
00641 if (record.proof_disproof.isFinal()) {
00642 value = record;
00643 record.working_threads &= ~(1u << leaving_thread_id);
00644 return false;
00645 }
00646 if (! value.proof_disproof.isFinal()) {
00647 value.min_pdp = std::min(value.min_pdp, record.min_pdp);
00648 value.proof_pieces_candidate
00649 = value.proof_pieces_candidate.max(record.proof_pieces_candidate);
00650 value.dag_moves |= record.dag_moves;
00651 value.solved |= record.solved;
00652 value.false_branch |= record.false_branch;
00653 }
00654 value.working_threads = record.working_threads;
00655 if (leaving_thread_id >= 0) {
00656 assert(value.working_threads & (1u << leaving_thread_id));
00657 value.working_threads &= ~(1u << leaving_thread_id);
00658 }
00659 #endif
00660 record = value;
00661 return false;
00662 }
00663 }
00664 value.working_threads &= ~(1u << leaving_thread_id);
00665 push_front(value);
00666 return true;
00667 }
00668 void addDag(DfpnRecord& value)
00669 {
00670 #ifdef USE_TBB_HASH
00671 SCOPED_LOCK(lk,mutex);
00672 #endif
00673 for (DfpnRecord& record: *this) {
00674 if (record.stands[BLACK] == value.stands[BLACK]) {
00675 #ifdef OSL_DFPN_SMP
00676 value.min_pdp = std::min(value.min_pdp, record.min_pdp);
00677 value.proof_pieces_candidate
00678 = value.proof_pieces_candidate.max(record.proof_pieces_candidate);
00679 value.dag_moves |= record.dag_moves;
00680 value.solved |= record.solved;
00681 value.false_branch |= record.false_branch;
00682 value.working_threads = record.working_threads;
00683 #endif
00684 record.dag_moves = value.dag_moves;
00685 return;
00686 }
00687 }
00688 }
00689 bool setWorking(const DfpnRecord& value, int thread_id)
00690 {
00691 #ifdef USE_TBB_HASH
00692 SCOPED_LOCK(lk,mutex);
00693 #endif
00694 for (DfpnRecord& record: *this) {
00695 if (record.stands[BLACK] == value.stands[BLACK]) {
00696 assert(! (value.working_threads & (1u << thread_id)));
00697 record.working_threads |= 1u << thread_id;
00698 return false;
00699 }
00700 }
00701 push_front(value);
00702 front().working_threads |= 1u << thread_id;
00703 return true;
00704 }
00705 void leaveWorking(PieceStand black, int thread_id)
00706 {
00707 #ifdef USE_TBB_HASH
00708 SCOPED_LOCK(lk,mutex);
00709 #endif
00710 for (DfpnRecord& record: *this) {
00711 if (record.stands[BLACK] == black) {
00712
00713 record.working_threads &= ~(1u << thread_id);
00714 return;
00715 }
00716 }
00717
00718 }
00719 void testTable(const BoardKey& ) const
00720 {
00721 #ifdef USE_TBB_HASH
00722 SCOPED_LOCK(lk,mutex);
00723 #endif
00724 for (const DfpnRecord& record: *this) {
00725 if (record.working_threads)
00726 std::cerr << std::bitset<16>(record.working_threads) << "\n";
00727 assert(record.working_threads == 0);
00728 #ifdef DFPN_STAT
00729 const int count = misc::BitOp::countBit(record.solved);
00730 if (record.proof_disproof.isCheckmateSuccess())
00731 count2proof[key.turn()][count]++;
00732 else if (record.proof_disproof.isCheckmateFail())
00733 count2disproof[key.turn()][count]++;
00734 else
00735 count2unknown[key.turn()][count]++;
00736 #endif
00737 }
00738 }
00739 size_t smallTreeGC(size_t threshold)
00740 {
00741 size_t removed = 0;
00742 #ifdef USE_TBB_HASH
00743 SCOPED_LOCK(lk,mutex);
00744 #endif
00745 list_t::iterator p=begin();
00746 while (p!=end()) {
00747 list_t::iterator q=p;
00748 ++q;
00749 if (q == end())
00750 break;
00751 if (! q->proof_disproof.isFinal()
00752 #ifdef OSL_DFPN_SMP
00753 && q->working_threads == 0
00754 #endif
00755 && q->node_count < threshold) {
00756 erase_after(p);
00757 ++removed;
00758 continue;
00759 }
00760 p = q;
00761 }
00762 if (! empty() && ! begin()->proof_disproof.isFinal()
00763 #ifdef OSL_DFPN_SMP
00764 && begin()->working_threads == 0
00765 #endif
00766 && begin()->node_count < threshold) {
00767 pop_front();
00768 ++removed;
00769 }
00770 return removed;
00771 }
00772 size_t estimateNodeCount(const HashKey& key, bool dominance_max) const;
00773 };
00774 template <osl::Player A>
00775 const osl::checkmate::DfpnRecord osl::checkmate::DfpnTable::
00776 List::probe(const HashKey& key, PieceStand white_stand) const
00777 {
00778 #ifdef USE_TBB_HASH
00779 SCOPED_LOCK(lk,mutex);
00780 #endif
00781 DfpnRecord result(key.blackStand(), white_stand);
00782 const PieceStand attack_stand = (A == BLACK) ? key.blackStand() : white_stand;
00783 const PieceStand defense_stand = (A == BLACK) ? white_stand : key.blackStand();
00784 #ifdef INITIAL_DOMINANCE
00785 unsigned int proof_ll = 1, disproof_ll = 1;
00786 #endif
00787 for (const DfpnRecord& record: *this) {
00788 if (record.stands[BLACK] == key.blackStand()) {
00789 result = record;
00790 if (result.proof_disproof.isFinal())
00791 break;
00792 continue;
00793 }
00794 if (record.proof_disproof.isCheckmateSuccess()) {
00795 if (attack_stand.isSuperiorOrEqualTo(record.proofPieces())) {
00796 result.setFrom(record);
00797 break;
00798 }
00799 }
00800 else if (record.proof_disproof.isCheckmateFail()) {
00801 if (defense_stand.isSuperiorOrEqualTo(record.disproofPieces())) {
00802 result.setFrom(record);
00803 break;
00804 }
00805 }
00806 #ifdef INITIAL_DOMINANCE
00807 else {
00808 if (record.stands[A].isSuperiorOrEqualTo(attack_stand)) {
00809 proof_ll = std::max(proof_ll, record.proof());
00810 }
00811 else if (attack_stand.isSuperiorOrEqualTo(record.stands[A])) {
00812 disproof_ll = std::max(disproof_ll, record.disproof());
00813 }
00814 }
00815 #endif
00816 }
00817 #ifdef INITIAL_DOMINANCE
00818 if (result.proof_disproof == ProofDisproof(1,1)) {
00819 result.proof_disproof = ProofDisproof(std::min(proof_ll, InitialDominanceProofMax),
00820 std::min(disproof_ll, InitialDominanceDisproofMax));
00821 result.node_count++;
00822 }
00823 #endif
00824 return result;
00825 }
00826
00827 size_t osl::checkmate::DfpnTable::
00828 List::estimateNodeCount(const HashKey& key, bool dominance_max) const
00829 {
00830 #ifdef USE_TBB_HASH
00831 SCOPED_LOCK(lk,mutex);
00832 #endif
00833 size_t node_count = 0, exact = 0;
00834 for (const DfpnRecord& record: *this) {
00835 if (node_count < record.node_count)
00836 node_count = record.node_count;
00837 if (key.blackStand() == record.stands[BLACK])
00838 exact = record.node_count;
00839 }
00840 return dominance_max ? node_count : exact;
00841 }
00842
00843 template <osl::Player A>
00844 const osl::checkmate::DfpnRecord osl::checkmate::DfpnTable::
00845 List::findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const
00846 {
00847 #ifdef USE_TBB_HASH
00848 SCOPED_LOCK(lk,mutex);
00849 #endif
00850 const PieceStand attack_stand = (A == BLACK) ? key.blackStand() : white_stand;
00851 DfpnRecord result(key.blackStand(), white_stand);
00852 for (const DfpnRecord& record: *this) {
00853 if (! record.proof_disproof.isCheckmateSuccess())
00854 continue;
00855 if (attack_stand.isSuperiorOrEqualTo(record.proofPieces())) {
00856 result.setFrom(record);
00857 ++record.node_count;
00858 if (record.last_move == last_move)
00859 break;
00860 }
00861 }
00862 return result;
00863 }
00864
00865 #ifndef MINIMAL
00866 template <osl::Player A>
00867 void osl::checkmate::DfpnTable::
00868 List::showProofOracles(const HashKey& key, PieceStand white_stand, Move last_move) const
00869 {
00870 #ifdef USE_TBB_HASH
00871 SCOPED_LOCK(lk,mutex);
00872 #endif
00873 const PieceStand attack_stand = (A == BLACK) ? key.blackStand() : white_stand;
00874 for (const DfpnRecord& record: *this) {
00875 if (! record.proof_disproof.isCheckmateSuccess())
00876 continue;
00877 if (attack_stand.isSuperiorOrEqualTo(record.proofPieces())) {
00878 std::cerr << record.last_move << " " << record.best_move << " " << record.node_count << " " << record.proofPieces()
00879 << " " << record.stands[BLACK] << " " << record.stands[WHITE] << "\n";
00880 }
00881 }
00882 }
00883 #endif
00884
00885 struct osl::checkmate::DfpnTable::Table : public std::unordered_map<BoardKey, List, std::hash<BoardKey>>
00886 {
00887 Player attack;
00888 explicit Table(Player a=BLACK) : attack(a) {}
00889 };
00890
00891
00892 osl::checkmate::
00893 DfpnTable::DfpnTable(Player attack)
00894 : table(new Table[DIVSIZE]), total_size(0), dfpn_max_depth(0),
00895 growth_limit(GrowthLimitInfty),
00896 gc_threshold(10)
00897 {
00898 setAttack(attack);
00899 }
00900
00901 osl::checkmate::
00902 DfpnTable::DfpnTable()
00903 : table(new Table[DIVSIZE]), total_size(0), dfpn_max_depth(0)
00904 {
00905 }
00906 osl::checkmate::
00907 DfpnTable::~DfpnTable()
00908 {
00909 }
00910
00911 void osl::checkmate::
00912 DfpnTable::setGrowthLimit(size_t new_limit)
00913 {
00914 growth_limit = new_limit;
00915 for (int i=0; i<DIVSIZE; ++i) {
00916 table[i].rehash(new_limit/DIVSIZE+new_limit/DIVSIZE/128+1);
00917 }
00918 }
00919
00920 void osl::checkmate::
00921 DfpnTable::showStats() const
00922 {
00923 if (size()) {
00924 std::cerr << "total " << total_size << "\n";
00925 for (int i=0; i<DIVSIZE; ++i)
00926 std::cerr << "DfpnTable " << i << " " << table[i].size() << "\n";
00927 }
00928 }
00929
00930 void osl::checkmate::
00931 DfpnTable::setMaxDepth(int new_depth)
00932 {
00933 dfpn_max_depth = new_depth;
00934 }
00935 int osl::checkmate::
00936 DfpnTable::maxDepth() const
00937 {
00938 return dfpn_max_depth;
00939 }
00940
00941 void osl::checkmate::
00942 DfpnTable::setAttack(Player a)
00943 {
00944 assert(size() == 0);
00945 for (int i=0; i<DIVSIZE; ++i)
00946 table[i].attack = a;
00947 }
00948
00949 osl::Player osl::checkmate::
00950 DfpnTable::attack() const
00951 {
00952 return table[0].attack;
00953 }
00954
00955 template <osl::Player Attack>
00956 osl::checkmate::DfpnTable::List *
00957 osl::checkmate::
00958 DfpnTable::find(const HashKey& key, int subindex)
00959 {
00960 assert(table[subindex].attack == Attack);
00961 #ifdef USE_TBB_HASH
00962 Table::accessor it;
00963 if(!table[subindex].find(it,key.boardKey()))
00964 return 0;
00965 return &it->second;
00966 #else
00967 Table::iterator p = table[subindex].find(key.boardKey());
00968 if (p == table[subindex].end())
00969 return 0;
00970 return &p->second;
00971 #endif
00972 }
00973
00974 template <osl::Player Attack>
00975 const osl::checkmate::DfpnTable::List *
00976 osl::checkmate::
00977 DfpnTable::find(const HashKey& key, int subindex) const
00978 {
00979 assert(table[subindex].attack == Attack);
00980 return find(key, subindex);
00981 }
00982
00983 const osl::checkmate::DfpnTable::List *
00984 osl::checkmate::
00985 DfpnTable::find(const HashKey& key, int subindex) const
00986 {
00987 #ifdef USE_TBB_HASH
00988 Table::accessor it;
00989 if(!table[subindex].find(it,key.boardKey()))
00990 return 0;
00991 return &it->second;
00992 #else
00993 Table::const_iterator p = table[subindex].find(key.boardKey());
00994 if (p == table[subindex].end())
00995 return 0;
00996 return &p->second;
00997 #endif
00998 }
00999
01000 template <osl::Player Attack>
01001 const osl::checkmate::DfpnRecord osl::checkmate::
01002 DfpnTable::probe(const HashKey& key, PieceStand white_stand) const
01003 {
01004 const int i=keyToIndex(key);
01005 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01006 SCOPED_LOCK(lk,mutex[i]);
01007 #endif
01008 const List *l = find<Attack>(key, i);
01009 if (l == 0)
01010 return DfpnRecord(key.blackStand(), white_stand);
01011 return l->probe<Attack>(key, white_stand);
01012 }
01013
01014 const osl::checkmate::DfpnRecord osl::checkmate::
01015 DfpnTable::probe(const HashKey& key, PieceStand white_stand) const
01016 {
01017 if (table[0].attack == BLACK)
01018 return probe<BLACK>(key, white_stand);
01019 else
01020 return probe<WHITE>(key, white_stand);
01021 }
01022 template <osl::Player Attack>
01023 const osl::checkmate::DfpnRecord osl::checkmate::
01024 DfpnTable::findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const
01025 {
01026 const int i=keyToIndex(key);
01027 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01028 SCOPED_LOCK(lk,mutex[i]);
01029 #endif
01030 const List *l = find<Attack>(key, i);
01031 if (l == 0)
01032 return DfpnRecord(key.blackStand(), white_stand);
01033 return l->findProofOracle<Attack>(key, white_stand, last_move);
01034 }
01035 const osl::checkmate::DfpnRecord osl::checkmate::
01036 DfpnTable::findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const
01037 {
01038 if (table[0].attack == BLACK)
01039 return findProofOracle<BLACK>(key, white_stand, last_move);
01040 else
01041 return findProofOracle<WHITE>(key, white_stand, last_move);
01042 }
01043
01044 #ifndef MINIMAL
01045 template <osl::Player Attack>
01046 void osl::checkmate::
01047 DfpnTable::showProofOracles(const HashKey& key, PieceStand white_stand, Move last_move) const
01048 {
01049 const int i=keyToIndex(key);
01050 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01051 SCOPED_LOCK(lk,mutex[i]);
01052 #endif
01053 const List *l = find<Attack>(key, i);
01054 if (l == 0)
01055 return;
01056 return l->showProofOracles<Attack>(key, white_stand, last_move);
01057 }
01058 #endif
01059
01060 size_t osl::checkmate::
01061 DfpnTable::estimateNodeCount(const HashKey& key, bool dominance_max) const
01062 {
01063 const int i=keyToIndex(key);
01064 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01065 SCOPED_LOCK(lk,mutex[i]);
01066 #endif
01067 const List *l = find(key, i);
01068 if (l == 0)
01069 return 0;
01070 return l->estimateNodeCount(key, dominance_max);
01071 }
01072
01073 void osl::checkmate::
01074 DfpnTable::store(const HashKey& key, DfpnRecord& value, int leaving_thread_id)
01075 {
01076 assert(key.blackStand() == value.stands[BLACK]);
01077 assert(! value.proof_disproof.isLoopDetection());
01078 const int i=keyToIndex(key);
01079 #ifdef USE_TBB_HASH
01080 Table::accessor it;
01081 table[i].insert(it,key.boardKey());
01082 List& l = it->second;
01083 #else
01084 # ifdef OSL_DFPN_SMP
01085 SCOPED_LOCK(lk,mutex[i]);
01086 # endif
01087 List& l = table[i][key.boardKey()];
01088 #endif
01089 if (l.store(value, leaving_thread_id)) {
01090 #ifdef OSL_USE_RACE_DETECTOR
01091 SCOPED_LOCK(lk,root_mutex);
01092
01093 #endif
01094 total_size += 1;
01095 }
01096 }
01097 void osl::checkmate::
01098 DfpnTable::addDag(const HashKey& key, DfpnRecord& value)
01099 {
01100 assert(key.blackStand() == value.stands[BLACK]);
01101 assert(! value.proof_disproof.isLoopDetection());
01102 const int i=keyToIndex(key);
01103 #ifdef USE_TBB_HASH
01104 Table::accessor it;
01105 table[i].insert(it,key.boardKey());
01106 List& l = it->second;
01107 #else
01108 # ifdef OSL_DFPN_SMP
01109 SCOPED_LOCK(lk,mutex[i]);
01110 # endif
01111 List& l = table[i][key.boardKey()];
01112 #endif
01113 l.addDag(value);
01114 }
01115
01116 void osl::checkmate::
01117 DfpnTable::setWorking(const HashKey& key, const DfpnRecord& value, int thread_id)
01118 {
01119 assert(key.blackStand() == value.stands[BLACK]);
01120 const int i=keyToIndex(key);
01121 #ifdef USE_TBB_HASH
01122 Table::accessor it;
01123 table[i].insert(it,key.boardKey());
01124 List& l = it->second;
01125 #else
01126 # ifdef OSL_DFPN_SMP
01127 SCOPED_LOCK(lk,mutex[i]);
01128 # endif
01129 List& l = table[i][key.boardKey()];
01130 #endif
01131 if (l.setWorking(value, thread_id)) {
01132 #ifdef OSL_USE_RACE_DETECTOR
01133 SCOPED_LOCK(lk,root_mutex);
01134
01135 #endif
01136 total_size += 1;
01137 }
01138 }
01139 void osl::checkmate::
01140 DfpnTable::leaveWorking(const HashKey& key, int thread_id)
01141 {
01142 const int i=keyToIndex(key);
01143 #ifdef USE_TBB_HASH
01144 Table::accessor it;
01145 table[i].insert(it,key.boardKey());
01146 List& l = it->second;
01147 #else
01148 # ifdef OSL_DFPN_SMP
01149 SCOPED_LOCK(lk,mutex[i]);
01150 # endif
01151 List& l = table[i][key.boardKey()];
01152 #endif
01153 l.leaveWorking(key.blackStand(), thread_id);
01154 }
01155
01156 void osl::checkmate::
01157 DfpnTable::clear()
01158 {
01159 total_size = 0;
01160 for (int i=0; i<DIVSIZE; ++i) {
01161 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01162 SCOPED_LOCK(lk,mutex[i]);
01163 #endif
01164 table[i].clear();
01165 }
01166 }
01167
01168 void osl::checkmate::
01169 DfpnTable::testTable()
01170 {
01171 for (int i=0; i<DIVSIZE; ++i) {
01172 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01173 SCOPED_LOCK(lk,mutex[i]);
01174 #endif
01175 for (auto& v: table[i])
01176 v.second.testTable(v.first);
01177 }
01178 #ifdef DFPN_STAT
01179 for (int i=0; i<16; ++i) {
01180 for (int j=0; j<2; ++j)
01181 std::cout << std::setw(9) << count2proof[j][i]
01182 << std::setw(9) << count2disproof[j][i]
01183 << std::setw(9) << count2unknown[j][i]
01184 << " ";
01185 std::cout << "\n";
01186 }
01187 #endif
01188 }
01189
01190 size_t osl::checkmate::
01191 DfpnTable::smallTreeGC(size_t threshold)
01192 {
01193 size_t removed = 0;
01194 for (int i=0; i<DIVSIZE; ++i) {
01195 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
01196 SCOPED_LOCK(lk,mutex[i]);
01197 #endif
01198 Table::iterator p=table[i].begin();
01199 while (p!=table[i].end()) {
01200 removed += p->second.smallTreeGC(threshold);
01201 Table::iterator q = p;
01202 ++p;
01203 if (q->second.empty()) {
01204 #ifdef USE_TBB_HASH
01205 table[i].erase(q->first);
01206 #else
01207 table[i].erase(q);
01208 #endif
01209 }
01210 }
01211 }
01212 total_size -= removed;
01213 return removed;
01214 }
01215
01216 bool osl::checkmate::
01217 DfpnTable::runGC()
01218 {
01219 const size_t before = total_size;
01220 if (! (before >= growth_limit || (growth_limit - before) < growth_limit/8))
01221 return false;
01222
01223 std::cerr << "run GC " << before << ' ' << gc_threshold << "\n";
01224 const size_t removed = smallTreeGC(gc_threshold);
01225 double memory = OslConfig::memoryUseRatio();
01226 std::cerr << " GC " << removed
01227 << " entries "
01228 << "collected " << std::setprecision(3)
01229 << ((sizeof(HashKey)+sizeof(DfpnRecord)+sizeof(char*)*2)
01230 * removed / (1<<20)) << "MB "
01231 << 100.0*removed/before << "%"
01232 << " real " << memory*100 << "%"
01233
01234 << "\n";
01235 gc_threshold += 15;
01236 static double memory_limit = 0.75;
01237 if (memory > memory_limit) {
01238 growth_limit -= growth_limit/8;
01239 gc_threshold += 15 + gc_threshold/4;
01240 memory_limit += 0.01;
01241 }
01242 if (removed < before*2/3)
01243 gc_threshold += 15 + gc_threshold/2;
01244 if ((removed < before*3/5 && memory > 0.75) || removed < before/2)
01245 throw Dfpn::DepthLimitReached();
01246 return true;
01247 }
01248
01249
01250 size_t osl::checkmate::
01251 DfpnTable::size() const
01252 {
01253 return total_size;
01254 }
01255
01256
01257
01258 template <osl::Player P>
01259 struct osl::checkmate::Dfpn::CallAttack
01260 {
01261 Dfpn *search;
01262 CallAttack(Dfpn *s) : search(s)
01263 {
01264 }
01265 void operator()(Square) const
01266 {
01267 search->attack<P>();
01268 }
01269 };
01270
01271 template <osl::Player P>
01272 struct osl::checkmate::Dfpn::CallDefense
01273 {
01274 Dfpn *search;
01275 CallDefense(Dfpn *s) : search(s)
01276 {
01277 }
01278 void operator()(Square) const
01279 {
01280 search->defense<P>();
01281 }
01282 };
01283
01284
01285
01286
01287 osl::checkmate::Dfpn::Dfpn()
01288 : table(0), tree(new Tree(OslConfig::dfpnMaxDepth())), path_table(new DfpnPathTable), parallel_shared(0),
01289 thread_id(-1), blocking_verify(true)
01290 {
01291 }
01292 osl::checkmate::Dfpn::~Dfpn()
01293 {
01294 }
01295
01296 void osl::checkmate::Dfpn::setTable(DfpnTable *new_table)
01297 {
01298 table = new_table;
01299 table->setMaxDepth(tree->MaxDepth);
01300 if (tree->MaxDepth > EnableGCDepth
01301 && table->growthLimit() < GrowthLimitInfty)
01302 path_table->rehash(parallel_shared ? table->growthLimit()/4 : table->growthLimit());
01303 }
01304
01305 void osl::checkmate::Dfpn::clear()
01306 {
01307 path_table->clear();
01308 }
01309
01310
01311 void osl::checkmate::Dfpn::setIllegal(const HashKey& key, PieceStand white_stand)
01312 {
01313
01314 LoopToDominance dummy;
01315 DfpnPathRecord *record = (table->attack() == BLACK)
01316 ? path_table->allocate<BLACK>(key, 0, dummy)
01317 : path_table->allocate<WHITE>(key, 0, dummy);
01318 record->visiting = true;
01319
01320
01321 DfpnRecord result(key.blackStand(), white_stand);
01322 result.proof_disproof = ProofDisproof::NoCheckmate();
01323 result.setDisproofPieces((table->attack() == WHITE) ? key.blackStand() : white_stand);
01324 table->store(key, result);
01325 }
01326
01327 const osl::checkmate::ProofDisproof
01328 osl::checkmate::
01329 Dfpn::hasCheckmateMove(const NumEffectState& state, const HashKey& key,
01330 const PathEncoding& path, size_t limit, Move& best_move, Move last_move,
01331 std::vector<Move> *pv)
01332 {
01333 PieceStand dummy;
01334 return hasCheckmateMove(state, key, path, limit, best_move, dummy, last_move, pv);
01335 }
01336
01337 const osl::checkmate::ProofDisproof
01338 osl::checkmate::
01339 Dfpn::hasCheckmateMove(const NumEffectState& state, const HashKey& key,
01340 const PathEncoding& path, size_t limit, Move& best_move, PieceStand& proof_pieces,
01341 Move last_move, std::vector<Move> *pv)
01342 {
01343 assert(table);
01344 if (! table)
01345 return ProofDisproof();
01346 path_table->clear();
01347
01348 node_count = 0;
01349 node_count_limit = limit;
01350
01351 Node& root = tree->node[0];
01352 try {
01353 tree->state.copyFrom(state);
01354 tree->depth = 0;
01355 root.hash_key = key;
01356 root.path = path;
01357 root.clear();
01358 root.threshold = ProofDisproof(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL);
01359 root.white_stand = PieceStand(WHITE, state);
01360 root.moved = last_move;
01361 if (state.turn() == BLACK)
01362 attack<BLACK>();
01363 else
01364 attack<WHITE>();
01365 }
01366 catch (DepthLimitReached&) {
01367 for (int i=0; i<=tree->depth; ++i)
01368 table->leaveWorking(tree->node[i].hash_key, thread_id);
01369 return ProofDisproof();
01370 }
01371 if (root.path_record
01372 && (std::find(root.path_record->twin_list.begin(), root.path_record->twin_list.end(), path)
01373 != root.path_record->twin_list.end())) {
01374 if (parallel_shared)
01375 parallel_shared->stop_all = true;
01376 return ProofDisproof::LoopDetection();
01377 }
01378 if (parallel_shared && root.record.proof_disproof.isFinal())
01379 parallel_shared->stop_all = true;
01380 best_move = root.record.best_move;
01381 if (root.record.proof_disproof.isCheckmateSuccess())
01382 proof_pieces = root.record.proofPieces();
01383
01384 if (pv && root.record.proof_disproof.isCheckmateSuccess()) {
01385 ProofTreeDepthDfpn analyzer(*table);
01386 analyzer.retrievePV(state, true, *pv);
01387 }
01388 return root.record.proof_disproof;
01389 }
01390
01391 const osl::checkmate::ProofDisproof
01392 osl::checkmate::
01393 Dfpn::tryProof(const NumEffectState& state, const HashKey& key,
01394 const PathEncoding& path, const ProofOracle& oracle, size_t oracle_id, Move& best_move,
01395 Move last_move)
01396 {
01397 return tryProofMain<true>(state, key, path, oracle, oracle_id, best_move, last_move);
01398 }
01399 const osl::checkmate::ProofDisproof
01400 osl::checkmate::
01401 Dfpn::tryProofLight(const NumEffectState& state, const HashKey& key,
01402 const PathEncoding& path, const ProofOracle& oracle, size_t oracle_id, Move& best_move,
01403 Move last_move)
01404 {
01405 return tryProofMain<false>(state, key, path, oracle, oracle_id, best_move, last_move);
01406 }
01407
01408 static const size_t root_proof_simulation_limit = 999999999;
01409
01410 template <bool UseTable>
01411 const osl::checkmate::ProofDisproof
01412 osl::checkmate::
01413 Dfpn::tryProofMain(const NumEffectState& state, const HashKey& key,
01414 const PathEncoding& path, const ProofOracle& oracle, size_t oracle_id, Move& best_move,
01415 Move last_move)
01416 {
01417 assert(table);
01418 if (! table)
01419 return ProofDisproof();
01420 path_table->clear();
01421
01422 tree->state.copyFrom(state);
01423 node_count = tree->depth = 0;
01424 node_count_limit = root_proof_simulation_limit;
01425
01426 Node& root = tree->node[0];
01427 root.hash_key = key;
01428 root.path = path;
01429 root.clear();
01430 root.threshold = ProofDisproof(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL);
01431 root.white_stand = PieceStand(WHITE, state);
01432 root.moved = last_move;
01433
01434 root.record = (state.turn() == BLACK)
01435 ? table->probe<BLACK>(root.hash_key, root.white_stand)
01436 : table->probe<WHITE>(root.hash_key, root.white_stand);
01437 if (root.record.proof_disproof.isFinal() || root.record.tried_oracle > oracle_id) {
01438 best_move = root.record.best_move;
01439 return root.record.proof_disproof;
01440 }
01441
01442 try {
01443 if (state.turn() == BLACK)
01444 proofOracleAttack<BLACK,UseTable>(oracle, ProofSimulationTolerance);
01445 else
01446 proofOracleAttack<WHITE,UseTable>(oracle, ProofSimulationTolerance);
01447 }
01448 catch (DepthLimitReached&) {
01449 for (int i=0; i<=tree->depth; ++i)
01450 table->leaveWorking(tree->node[i].hash_key, thread_id);
01451 return ProofDisproof();
01452 }
01453 if (UseTable && root.path_record
01454 && (std::find(root.path_record->twin_list.begin(), root.path_record->twin_list.end(), path)
01455 != root.path_record->twin_list.end()))
01456 return ProofDisproof::LoopDetection();
01457 if (UseTable) {
01458 root.record.last_move = last_move;
01459 table->store(root.hash_key, root.record);
01460 }
01461 best_move = root.record.best_move;
01462 root.record.tried_oracle = oracle_id+1;
01463 return root.record.proof_disproof;
01464 }
01465
01466
01467 const osl::checkmate::ProofDisproof
01468 osl::checkmate::
01469 Dfpn::hasEscapeMove(const NumEffectState& state,
01470 const HashKey& key, const PathEncoding& path,
01471 size_t limit, Move last_move)
01472 {
01473 assert(table);
01474 if (! state.hasEffectAt(alt(state.turn()), state.kingSquare(state.turn())))
01475 return ProofDisproof::NoCheckmate();
01476 if (! table)
01477 return ProofDisproof();
01478 path_table->clear();
01479 node_count = tree->depth = 0;
01480 node_count_limit = limit;
01481
01482 Node& root = tree->node[0];
01483 try {
01484 tree->state.copyFrom(state);
01485 tree->depth = 0;
01486 root.hash_key = key;
01487 root.path = path;
01488 root.moved = last_move;
01489 root.clear();
01490 root.threshold = ProofDisproof(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL);
01491 root.white_stand = PieceStand(WHITE, state);
01492 if (state.turn() == BLACK)
01493 defense<WHITE>();
01494 else
01495 defense<BLACK>();
01496
01497 if (root.record.need_full_width) {
01498 root.clear();
01499 if (state.turn() == BLACK)
01500 defense<WHITE>();
01501 else
01502 defense<BLACK>();
01503 }
01504 }
01505 catch (DepthLimitReached&) {
01506 return ProofDisproof();
01507 }
01508 if (root.record.proof_disproof == ProofDisproof::NoEscape()
01509 && last_move.isNormal() && last_move.isDrop() && last_move.ptype() == PAWN)
01510 return ProofDisproof::PawnCheckmate();
01511 if (root.path_record) {
01512 const SimpleTwinList& tl = root.path_record->twin_list;
01513 if (std::find(tl.begin(), tl.end(), root.path) != tl.end())
01514 return ProofDisproof::LoopDetection();
01515 }
01516 return root.record.proof_disproof;
01517 }
01518
01519 namespace osl
01520 {
01521 namespace
01522 {
01523 typedef std::tuple<int,int,int> tuple_t;
01524 template <Player Turn>
01525 struct move_compare
01526 {
01527 const NumEffectState *state;
01528 move_compare(const NumEffectState& s) : state(&s)
01529 {
01530 assert(Turn == state->turn());
01531 }
01532 tuple_t convert(Move m) const
01533 {
01534 const int a = state->countEffect(Turn, m.to()) + m.isDrop();
01535 const int d = state->countEffect(alt(Turn), m.to());
01536 const int to_y = sign(Turn)*m.to().y();
01537 const int to_x = (5 - abs(5-m.to().x()))*2 + (m.to().x() > 5);
01538 int from_to = (to_y*16+to_x)*256;
01539 if (m.isDrop())
01540 from_to += m.ptype();
01541 else
01542 from_to += m.from().index();
01543 return std::make_tuple(a > d, from_to, m.isPromotion());
01544 }
01545 bool operator()(Move l, Move r) const
01546 {
01547 return convert(l) > convert(r);
01548 }
01549 };
01550 }
01551 }
01552
01553 template <osl::Player Turn>
01554 void osl::checkmate::
01555 Dfpn::sort(const NumEffectState& state, DfpnMoveVector& moves)
01556 {
01557 #ifdef MEMORIZE_SOLVED_IN_BITSET
01558 int last_sorted = 0, cur = 0;
01559 Ptype last_ptype = PTYPE_EMPTY;
01560 for (;(size_t)cur < moves.size(); ++cur) {
01561 if (moves[cur].isDrop() || moves[cur].oldPtype() == last_ptype)
01562 continue;
01563 std::sort(moves.begin()+last_sorted, moves.begin()+cur, move_compare<Turn>(state));
01564 last_sorted = cur;
01565 last_ptype = moves[cur].oldPtype();
01566 }
01567 std::sort(moves.begin()+last_sorted, moves.begin()+cur, move_compare<Turn>(state));
01568 #endif
01569 }
01570
01571 template <osl::Player P>
01572 void osl::checkmate::
01573 Dfpn::generateCheck(const NumEffectState& state, DfpnMoveVector& moves, bool &has_pawn_checkmate)
01574 {
01575 assert(moves.empty());
01576 if (state.inCheck(P))
01577 {
01578 using namespace osl::move_classifier;
01579 DfpnMoveVector escape;
01580 move_generator::GenerateEscape<P>::generateKingEscape(state, escape);
01581 for (Move move: escape) {
01582 if (MoveAdaptor<Check<P> >::isMember(state, move))
01583 moves.push_back(move);
01584 }
01585 }
01586 else
01587 {
01588 move_action::Store store(moves);
01589 move_generator::AddEffectWithEffect<move_action::Store>::template generate<P,true>
01590 (state,state.kingPiece(alt(P)).square(),store,has_pawn_checkmate);
01591 }
01592 for (Move move: moves)
01593 {
01594 if(move.hasIgnoredUnpromote<P>()){
01595 if(Ptype_Table.getEffect(unpromote(move.ptypeO()),move.to(),
01596 state.kingSquare(alt(P))).hasEffect()
01597 || (state.pinOrOpen(alt(P)).test
01598 (state.pieceAt(move.from()).number())))
01599 moves.push_back(move.unpromote());
01600 }
01601 }
01602 sort<P>(state, moves);
01603 }
01604
01605 void osl::checkmate::
01606 Dfpn::findDagSource(const HashKey& terminal_key,
01607 DfpnRecord& terminal_record,
01608 PieceStand terminal_stand, int offset)
01609 {
01610 #ifdef NAGAI_DAG_TEST
01611 PieceStand white_stand = terminal_stand;
01612 HashKey key = terminal_key;
01613 DfpnRecord cur = terminal_record;
01614
01615 for (int d=offset; d<std::min(tree->MaxDepth,MaxDagTraceDepth); ++d) {
01616 if (! cur.last_move.isNormal())
01617 return;
01618 assert(key.turn() == alt(cur.last_move.player()));
01619 HashKey parent_key = key.newUnmakeMove(cur.last_move);
01620 white_stand = white_stand.previousStand(WHITE, cur.last_move);
01621 DfpnRecord parent = table->probe(parent_key, white_stand);
01622
01623
01624
01625
01626
01627 for (int i=tree->depth - 4 - (d%2); i>=0; i-=2) {
01628 if (parent_key == tree->node[i].hash_key) {
01629 for (size_t m=0; m<std::min(tree->node[i].moves.size(), (size_t)64); ++m) {
01630 if (tree->node[i].moves[m] == tree->node[i+1].moved
01631 || tree->node[i].moves[m] == cur.last_move)
01632 tree->node[i].record.dag_moves |= (1ull << m);
01633 }
01634 if (parallel_shared)
01635 table->addDag(tree->node[i].hash_key, tree->node[i].record);
01636 terminal_record.dag_terminal = true;
01637 return;
01638 }
01639 }
01640 key = parent_key;
01641 cur = parent;
01642 }
01643 #endif
01644 }
01645
01646 void osl::checkmate::
01647 Dfpn::findDagSource()
01648 {
01649 findDagSource(tree->node[tree->depth].hash_key, tree->node[tree->depth].record,
01650 tree->node[tree->depth].white_stand, 1);
01651 }
01652
01653
01654 template <osl::Player P>
01655 void osl::checkmate::
01656 Dfpn::attack()
01657 {
01658 assert(! tree->inCheck(alt(P)));
01659 Node& node = tree->node[tree->depth];
01660 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
01661 node.visit_time = ++timer;
01662 #endif
01663 #ifdef DFPN_DEBUG
01664 Tree::Logging logging(tree.get(), table, "attack");
01665 #endif
01666 const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.path.getDepth();
01667 LoopToDominance loop;
01668 DfpnVisitLock<> lk(node.path_record = path_table->allocate<P>(node.hash_key, my_distance, loop));
01669 DfpnRecord& record = node.record;
01670 record = DfpnRecord();
01671 if (loop == BadAttackLoop) {
01672 node.setLoopDetection();
01673 return;
01674 }
01675 assert(node.white_stand == PieceStand(WHITE, tree->state));
01676 const size_t node_count_org = node_count++;
01677 #if (! defined CHECKMATE_D2) && (! defined NO_IMMEDIATE_CHECKMATE)
01678 if (! tree->inCheck(P)
01679 && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.best_move)) {
01680 PieceStand proof_pieces;
01681 if (record.best_move.isDrop())
01682 proof_pieces.add(record.best_move.ptype());
01683 record.setProofPieces(proof_pieces);
01684 record.proof_disproof = ProofDisproof::Checkmate();
01685 return;
01686 }
01687 #endif
01688 if (tree->depth + 2 >= tree->MaxDepth) {
01689 std::cerr << "throw " << thread_id << "\n";
01690 throw DepthLimitReached();
01691 }
01692 assert(tree->depth + 2 < tree->MaxDepth);
01693 record = table->probe<P>(node.hash_key, node.white_stand);
01694 assert(record.stands[BLACK] == node.hash_key.blackStand());
01695 assert(record.stands[WHITE] == node.white_stand);
01696 if (record.proof_disproof.isFinal())
01697 return;
01698 if (tree->depth == 0 && node_count_limit <= 50 && record.node_count >= node_count_limit)
01699 return;
01700 if (tree->depth == 0
01701 #ifdef CHECKMATE_A3
01702 || true
01703 #endif
01704 #ifdef CHECKMATE_A3_GOLD
01705 || (record.proof_disproof == ProofDisproof(1,1) && tree->state.hasPieceOnStand<GOLD>(P)
01706 && (tree->king(alt(P)).square().x() <= 3 || tree->king(alt(P)).square().x() >= 7
01707 || tree->king(alt(P)).square().template squareForBlack<P>().y() <= 3))
01708 #endif
01709 )
01710 {
01711 #ifdef DFPN_STAT
01712 static stat::Ratio oracle_success("a3-gold");
01713 #endif
01714 FixedDepthSolverExt fixed_solver(tree->state);
01715 PieceStand proof_pieces;
01716 ProofDisproof pdp = fixed_solver.hasCheckmateMove<P>(2, record.best_move, proof_pieces);
01717 ++node_count;
01718 #ifdef DFPN_STAT
01719 oracle_success.add(pdp.isCheckmateSuccess());
01720 #endif
01721 if (pdp.isCheckmateSuccess()) {
01722 record.node_count++;
01723 record.proof_disproof = pdp;
01724 record.setProofPieces(proof_pieces);
01725 record.last_move = node.moved;
01726 table->store(node.hash_key, record);
01727 return;
01728 }
01729 }
01730 #ifndef MINIMAL
01731 if (tree->MaxDepth > EnableGCDepth && thread_id <= 0) {
01732 try {
01733 const size_t removed = table->runGC();
01734 if (removed > 0) {
01735 #ifdef DFPN_DEBUG
01736 for (int i=1; i<tree->depth; ++i)
01737 std::cerr << tree->node[i].threshold.proof() << ' '
01738 << record::csa::show(tree->node[i].moved) << ' ';
01739 std::cerr << "\n";
01740 #endif
01741 }
01742 }
01743 catch (...) {
01744 if (parallel_shared)
01745 parallel_shared->stop_all = true;
01746 throw;
01747 }
01748 }
01749 if (tree->MaxDepth > EnableGCDepth
01750 && (path_table->size() > table->growthLimit()
01751 #ifdef OSL_DFPN_SMP
01752 || (parallel_shared
01753 && path_table->size() > table->growthLimit()/4)
01754 #endif
01755 )) {
01756 const size_t before = path_table->size();
01757 const size_t removed = path_table->runGC();
01758 if (removed > 0) {
01759 if (thread_id <= 0)
01760 std::cerr << " GC-path collected "
01761 << std::setprecision(3)
01762 << ((sizeof(HashKey)+sizeof(DfpnPathRecord)+sizeof(char*)*2)
01763 * removed / (1<<20)) << "MB "
01764 << 100.0*removed/before << "%\n";
01765 for (int i=0; i<tree->depth; ++i) {
01766 for (size_t j=0; j<tree->node[i].moves.size(); ++j) {
01767 tree->node[i].children_path[j] = 0;
01768 }
01769 }
01770 }
01771 }
01772 #endif
01773 if (parallel_shared) {
01774 if (parallel_shared->stop_all) {
01775
01776 throw DepthLimitReached();
01777 }
01778 if (parallel_shared->data[thread_id].restart) {
01779 for (int i=0; i<tree->depth; ++i) {
01780 if (tree->node[i].hash_key
01781 == parallel_shared->data[thread_id].restart_key)
01782 return;
01783 #if 0
01784 if (tree->node[i].record.dag_terminal)
01785 break;
01786 #endif
01787 }
01788
01789 parallel_shared->data[thread_id].clear();
01790 }
01791 }
01792
01793
01794 bool has_pawn_checkmate=false;
01795 generateCheck<P>(tree->state, node.moves,has_pawn_checkmate);
01796 if (node.moves.empty()) {
01797 record.setDisproofPieces(DisproofPieces::leaf(tree->state, alt(P),
01798 record.stands[alt(P)]));
01799 if(has_pawn_checkmate)
01800 record.proof_disproof = ProofDisproof::PawnCheckmate();
01801 else
01802 record.proof_disproof = ProofDisproof::NoCheckmate();
01803 return;
01804 }
01805
01806 #ifdef PROOF_AVERAGE
01807 int frontier_count = 0, sum_frontier_proof = 0;
01808 #endif
01809 assert(node.children.empty());
01810 {
01811 node.allocate(node.moves.size());
01812 const King8Info info_modified
01813 = Edge_Table.resetEdgeFromLiberty(alt(P), tree->king(alt(P)).square(), King8Info(tree->state.Iking8Info(alt(P))));
01814 for (size_t i=0; i<node.moves.size(); ++i) {
01815 #ifdef MEMORIZE_SOLVED_IN_BITSET
01816 if (record.solved & (1ull << i))
01817 continue;
01818 #endif
01819 const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
01820 node.children[i] = table->probe<P>(new_key, node.nextWhiteStand(P, node.moves[i]));
01821 if (node.children[i].proof_disproof == ProofDisproof(1,1)) {
01822 unsigned int proof, disproof;
01823 LibertyEstimator::attackH(P, tree->state, info_modified,
01824 node.moves[i], proof, disproof);
01825 #ifndef MINIMAL
01826 if (HashRandomPair::initialized()) {
01827
01828 std::pair<char,char> randomness = HashRandomPair::value(new_key);
01829 proof += randomness.first;
01830 disproof += randomness.second;
01831 }
01832 #endif
01833 node.children[i].proof_disproof = ProofDisproof(proof, disproof);
01834 }
01835 if (node.children[i].proof_disproof == ProofDisproof::NoEscape()
01836 && node.moves[i].isDrop() && node.moves[i].ptype() == PAWN) {
01837 node.children[i].proof_disproof = ProofDisproof::PawnCheckmate();
01838 #ifdef MEMORIZE_SOLVED_IN_BITSET
01839 record.solved |= (1ull << i);
01840 #endif
01841 record.min_pdp = std::min(record.min_pdp, (unsigned int)ProofDisproof::PAWN_CHECK_MATE_PROOF);
01842 }
01843 else if (node.children[i].proof_disproof.isCheckmateFail())
01844 tree->setNoCheckmateChildInAttack(i);
01845 else if (node.children[i].proof_disproof.isCheckmateSuccess()) {
01846 record.node_count += node_count - node_count_org;
01847 node.setCheckmateAttack(P,i);
01848 record.last_move = node.moved;
01849 table->store(node.hash_key, record);
01850 node.path_record->node_count = 0;
01851 return;
01852 }
01853 #ifdef PROOF_AVERAGE
01854 else if (node.children[i].node_count == 0) {
01855 ++frontier_count;
01856 sum_frontier_proof += node.children[i].proof();
01857 assert(node.children[i].proof() < 128);
01858 }
01859 #endif
01860 #ifdef AGGRESSIVE_FIND_DAG2
01861 else if (!node.children[i].proof_disproof.isFinal()
01862 && std::max(node.children[i].proof(), node.children[i].disproof()) >= DagFindThreshold2
01863 && node.children[i].last_move.isNormal()
01864 && node.children[i].last_move != node.moves[i]) {
01865 findDagSource(node.hashes[i], node.children[i],
01866 node.nextWhiteStand(P, node.moves[i]));
01867 }
01868 #endif
01869 node.children_path[i] = path_table->probe(new_key);
01870 node.proof_cost[i] = attackProofCost(P, tree->state, node.moves[i]);
01871 }
01872 }
01873
01874
01875 if (parallel_shared)
01876 table->setWorking(node.hash_key, record, thread_id);
01877
01878 const Move recorded_last_move = record.last_move;
01879 record.last_move = node.moved;
01880
01881 assert(node.children.size() == node.moves.size());
01882 #ifdef PROOF_AVERAGE
01883 const size_t proof_average = frontier_count ? sum_frontier_proof/frontier_count : 1;
01884 #else
01885 const size_t proof_average = 1;
01886 #endif
01887
01888 #ifdef DFPN_DEBUG
01889 if (std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.hash_key))
01890 != debug_node.end() && timer > debug_time_start)
01891 tree->dump(__LINE__);
01892 #endif
01893 for (int loop=0; true; ++loop) {
01894 unsigned int min_proof=record.min_pdp, min_proof2=record.min_pdp;
01895 size_t sum_disproof = 0, max_disproof = 0, max_disproof_dag = 0, next_i=node.children.size();
01896 size_t max_drop_disproof_rook = 0, max_drop_disproof_bishop = 0, max_drop_disproof_lance = 0;
01897 int max_children_depth = 0, upward_count = 0;
01898 for (size_t i=0; i<node.children.size(); ++i) {
01899 #ifdef MEMORIZE_SOLVED_IN_BITSET
01900 if (record.solved & (1ull << i))
01901 continue;
01902 #endif
01903 if (i > 0 && min_proof < ProofDisproof::PROOF_LIMIT
01904 && node.moves[i].fromTo() == node.moves[i-1].fromTo()
01905 && ! node.moves[i].isDrop()) {
01906
01907 assert(node.moves[i].ptype() == node.moves[i-1].oldPtype());
01908 record.dag_moves |= ((1ull << i) | (1ull << (i-1)));
01909 if (node.threshold.proof() < NoPromoeIgnoreProofThreshold
01910 && node.threshold.disproof() < NoPromoeIgnoreDisproofThreshold)
01911 continue;
01912
01913 }
01914 size_t proof = node.children[i].proof();
01915 size_t disproof = node.children[i].disproof();
01916 if (proof && disproof) {
01917 proof += node.proof_cost[i];
01918 #ifdef OSL_DFPN_SMP
01919 if (parallel_shared && node.children[i].working_threads) {
01920
01921 proof += misc::BitOp::countBit(node.children[i].working_threads);
01922 }
01923 #endif
01924 }
01925 if (node.children_path[i]) {
01926 if (node.isLoop(i)) {
01927 node.children[i].proof_disproof = ProofDisproof::LoopDetection();
01928 assert(proof < ProofDisproof::LOOP_DETECTION_PROOF);
01929 proof = ProofDisproof::LOOP_DETECTION_PROOF;
01930 disproof = 0;
01931 }
01932 else if (! node.children[i].proof_disproof.isFinal()) {
01933 max_children_depth = std::max(max_children_depth, node.children_path[i]->distance);
01934 #ifdef NAGAI_DAG_TEST
01935 if (record.dag_moves & (1ull<<i)) {
01936 max_disproof_dag = std::max(max_disproof_dag, disproof);
01937 disproof = 0;
01938 }
01939 else
01940 #endif
01941 #ifdef DELAY_UPWARD
01942 if (node.children_path[i]->distance <= node.path_record->distance) {
01943 max_disproof = std::max(max_disproof, disproof);
01944 ++upward_count;
01945 disproof = UpwardWeight;
01946 }
01947 else
01948 #endif
01949 if (node.moves[i].isDrop()
01950 || (isMajor(node.moves[i].ptype())
01951 && ! node.moves[i].isCapture()
01952 && ! node.moves[i].isPromotion() && isPromoted(node.moves[i].ptype())
01953 && ! tree->state.hasEffectAt(alt(P), node.moves[i].to()))) {
01954 const EffectContent e
01955 = Ptype_Table.getEffect(node.moves[i].ptypeO(),
01956 Offset32(tree->king(alt(P)).square(), node.moves[i].to()));
01957 if (! e.hasUnblockableEffect()) {
01958 size_t *target = &max_drop_disproof_lance;
01959 if (unpromote(node.moves[i].ptype()) == ROOK)
01960 target = &max_drop_disproof_rook;
01961 else if (unpromote(node.moves[i].ptype()) == BISHOP)
01962 target = &max_drop_disproof_bishop;
01963 *target = std::max(*target, disproof);
01964 disproof = LongDropCount;
01965 }
01966 }
01967 }
01968 }
01969 else {
01970 max_children_depth = node.path_record->distance+1;
01971 }
01972 if (proof < min_proof || (proof == min_proof && disproof && disproof < node.children[next_i].disproof())) {
01973 min_proof2 = min_proof;
01974 min_proof = proof;
01975 next_i = i;
01976 } else if (proof < min_proof2) {
01977 min_proof2 = proof;
01978 }
01979 sum_disproof += disproof;
01980 }
01981 sum_disproof += max_drop_disproof_rook + max_drop_disproof_bishop + max_drop_disproof_lance
01982 + max_disproof_dag;
01983 if (LongDropCount) {
01984 if (max_drop_disproof_rook) sum_disproof -= LongDropCount;
01985 if (max_drop_disproof_bishop) sum_disproof -= LongDropCount;
01986 if (max_drop_disproof_lance) sum_disproof -= LongDropCount;
01987 }
01988 if (upward_count) {
01989 if (sum_disproof == 0)
01990 sum_disproof = max_disproof;
01991 }
01992 if (node.path_record->distance >= max_children_depth) {
01993 node.path_record->distance = max_children_depth-1;
01994 }
01995 #ifdef KISHIMOTO_WIDEN_THRESHOLD
01996 if (loop == 0 && sum_disproof >= node.threshold.disproof() && sum_disproof > IgnoreUpwardDisproofThreshold)
01997 node.threshold = ProofDisproof(node.threshold.proof(), sum_disproof+1);
01998 #endif
01999 #ifdef ADHOC_SUM_RESTRICTION
02000 if (sum_disproof < ROOT_DISPROOF_TOL && min_proof > 0 && sum_disproof > min_proof*AdHocSumScale) {
02001 sum_disproof = min_proof*AdHocSumScale
02002 + slow_increase(sum_disproof-min_proof*AdHocSumScale);
02003 }
02004 #endif
02005 if (min_proof >= node.threshold.proof()
02006 || sum_disproof >= node.threshold.disproof()
02007 || next_i >= node.children.size()
02008 || node_count + min_proof >= node_count_limit) {
02009 record.proof_disproof = ProofDisproof(min_proof, sum_disproof);
02010 if (record.proof_disproof.isLoopDetection())
02011 node.setLoopDetection();
02012 else if (record.proof_disproof.isCheckmateFail()) {
02013 node.setNoCheckmateAttack(P, tree->state);
02014 } else if (! record.proof_disproof.isFinal()) {
02015 if (recorded_last_move.isNormal() && recorded_last_move != node.moved
02016 && std::max(record.proof(), record.disproof()) >= DagFindThreshold)
02017 findDagSource();
02018 #ifdef AGGRESSIVE_FIND_DAG
02019 if (std::max(node.children[next_i].proof(), node.children[next_i].disproof()) >= DagFindThreshold
02020 && node.children[next_i].last_move.isNormal()
02021 && node.children[next_i].last_move != node.moves[next_i]) {
02022 findDagSource(node.hashes[next_i], node.children[next_i],
02023 node.nextWhiteStand(P, node.moves[next_i]));
02024 node.children[next_i].last_move = node.moves[next_i];
02025 table->store(node.hashes[next_i], node.children[next_i]);
02026 }
02027 #endif
02028 }
02029 record.node_count += node_count - node_count_org;
02030 table->store(node.hash_key, record, thread_id);
02031 node.path_record->node_count = record.node_count;
02032 if (parallel_shared && record.proof_disproof.isFinal())
02033 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02034 return;
02035 }
02036 #ifdef MEMORIZE_SOLVED_IN_BITSET
02037 assert(! (record.solved & (1ull << next_i)));
02038 #endif
02039 record.best_move = node.moves[next_i];
02040 tree->newVisit(P, node.moves[next_i], node.hashes[next_i]);
02041 Node& next = tree->node[tree->depth+1];
02042 unsigned int disproof_c = node.threshold.disproof()
02043 - (sum_disproof - node.children[next_i].disproof());
02044 #ifdef ADHOC_SUM_RESTRICTION
02045 if (disproof_c > node.threshold.disproof())
02046 disproof_c = node.children[next_i].disproof()
02047 + (node.threshold.disproof() - sum_disproof);
02048 #endif
02049 next.threshold = ProofDisproof(std::min(min_proof2+proof_average, (size_t)node.threshold.proof())
02050 - node.proof_cost[next_i],
02051 disproof_c);
02052 CallDefense<P> helper(this);
02053 tree->depth += 1;
02054 next.path.pushMove(next.moved);
02055 tree->state.makeUnmakeMove(Player2Type<P>(), next.moved, helper);
02056 tree->depth -= 1;
02057 node.children[next_i] = next.record;
02058 node.children_path[next_i] = next.path_record;
02059 if (next.record.proof_disproof == ProofDisproof::NoEscape()
02060 && next.moved.isDrop() && next.moved.ptype() == PAWN)
02061 node.children[next_i].proof_disproof = ProofDisproof::PawnCheckmate();
02062 if (node.children[next_i].proof_disproof.isCheckmateSuccess()) {
02063 node.setCheckmateAttack(P,next_i);
02064 record.node_count += node_count - node_count_org;
02065 record.last_move = node.moved;
02066 table->store(node.hash_key, record, thread_id);
02067 node.path_record->node_count = 0;
02068 if (parallel_shared)
02069 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02070 return;
02071 }
02072 else if (next.record.proof_disproof.isCheckmateFail()
02073 && ! next.record.proof_disproof.isLoopDetection())
02074 tree->setNoCheckmateChildInAttack(next_i);
02075 min_proof = std::min(min_proof2, node.children[next_i].proof());
02076 if (min_proof < ProofDisproof::PROOF_LIMIT
02077 && node_count + min_proof >= node_count_limit) {
02078 record.proof_disproof = ProofDisproof(min_proof, sum_disproof);
02079 record.node_count += node_count - node_count_org;
02080 table->store(node.hash_key, record, thread_id);
02081 node.path_record->node_count = record.node_count;
02082 if (parallel_shared)
02083 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02084 return;
02085 }
02086 if (parallel_shared && parallel_shared->data[thread_id].restart) {
02087 if (tree->depth == 0)
02088 parallel_shared->data[thread_id].clear();
02089 else {
02090 if (parallel_shared->data[thread_id].restart_key == node.hash_key) {
02091 record = table->probe<P>(node.hash_key, node.white_stand);
02092 if (! record.proof_disproof.isFinal())
02093 continue;
02094 parallel_shared->data[thread_id].clear();
02095 }
02096 table->leaveWorking(node.hash_key, thread_id);
02097 return;
02098 }
02099 }
02100 }
02101 }
02102
02103 template <osl::Player P>
02104 void osl::checkmate::
02105 Dfpn::generateEscape(const NumEffectState& state, bool need_full_width,
02106 Square last_to, DfpnMoveVector& moves)
02107 {
02108 assert(moves.empty());
02109 const Player AltP=alt(P);
02110 #ifdef GRAND_PARENT_DELAY
02111 const bool delay_node = last_to != Square()
02112 && state.hasEffectAt(alt(P), last_to)
02113 && (state.hasEffectNotBy(alt(P), state.kingPiece(alt(P)), last_to)
02114 || ! state.hasEffectAt(P, last_to));
02115 if (delay_node)
02116 {
02117 DfpnMoveVector all;
02118 move_generator::GenerateEscape<AltP>::
02119 generateCheapKingEscape(state, all);
02120
02121 for (Move move: all) {
02122 if (move.to() == last_to) {
02123 moves.push_back(move);
02124 }
02125 }
02126 #ifdef MEMORIZE_SOLVED_IN_BITSET
02127 sort<AltP>(state, moves);
02128 #endif
02129 }
02130 else
02131 #endif
02132 {
02133 move_generator::GenerateEscape<AltP>::
02134 generateCheapKingEscape(state, moves);
02135 #ifdef MEMORIZE_SOLVED_IN_BITSET
02136 sort<AltP>(state, moves);
02137 #endif
02138 }
02139
02140 if (need_full_width) {
02141 DfpnMoveVector others;
02142 move_generator::GenerateEscape<AltP>::
02143 generateKingEscape(state, others);
02144 #ifdef MEMORIZE_SOLVED_IN_BITSET
02145 sort<AltP>(state, others);
02146 #endif
02147 const int org_size = moves.size();
02148 for (Move move: others) {
02149 if (std::find(moves.begin(), moves.begin()+org_size, move) == moves.begin()+org_size)
02150 moves.push_back(move);
02151 }
02152 for (Move move: moves)
02153 {
02154 if(move.hasIgnoredUnpromote<AltP>())
02155 moves.push_back(move.unpromote());
02156 }
02157 }
02158
02159 }
02160
02161 bool osl::checkmate::
02162 Dfpn::grandParentSimulationSuitable() const
02163 {
02164 #ifdef GRAND_PARENT_SIMULATION
02165 Node& node = tree->node[tree->depth];
02166 if (tree->depth >= 2) {
02167 const Node& parent = tree->node[tree->depth-1];
02168 const Node& gparent = tree->node[tree->depth-2];
02169 const Move alm = node.moved;
02170 const Move dlm = parent.moved;
02171 const Move alm2 = gparent.moved;
02172 if (dlm.isNormal() && alm.to() == dlm.to() && ! dlm.isCapture()
02173 && alm2.isNormal() && alm2.to() == alm.from()) {
02174 return true;
02175 }
02176 }
02177 #endif
02178 return false;
02179 }
02180
02181 template <osl::Player P>
02182 void osl::checkmate::
02183 Dfpn::defense()
02184 {
02185 #if 0
02186 if (parallel_shared) {
02187 if (parallel_shared->stop_all)
02188 throw DepthLimitReached();
02189 if (parallel_shared->data[thread_id].restart) {
02190 for (int i=0; i<tree->depth; ++i) {
02191 if (tree->node[i].hash_key == parallel_shared->data[thread_id].restart_key)
02192 return;
02193 #if 0
02194 if (tree->node[i].record.dag_terminal)
02195 break;
02196 #endif
02197 }
02198
02199 parallel_shared->data[thread_id].clear();
02200 }
02201 }
02202 #endif
02203 Node& node = tree->node[tree->depth];
02204 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
02205 node.visit_time = ++timer;
02206 #endif
02207 #ifdef DFPN_DEBUG
02208 Tree::Logging logging(tree.get(), table, "defens");
02209 #endif
02210 const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.path.getDepth();
02211 LoopToDominance loop;
02212 DfpnVisitLock<> lk(node.path_record = path_table->allocate<P>(node.hash_key, my_distance, loop));
02213 DfpnRecord& record = node.record;
02214 if (loop == BadAttackLoop) {
02215 record = DfpnRecord();
02216 node.setLoopDetection();
02217 return;
02218 }
02219 const size_t node_count_org = node_count++;
02220 assert(tree->inCheck(alt(P)));
02221 assert(node.white_stand == PieceStand(WHITE, tree->state));
02222
02223 record = table->probe<P>(node.hash_key, node.white_stand);
02224 assert(record.stands[BLACK] == node.hash_key.blackStand());
02225 assert(record.stands[WHITE] == node.white_stand);
02226 if (record.proof_disproof.isFinal())
02227 return;
02228 const bool grand_parent_simulation = grandParentSimulationSuitable();
02229 if (record.last_to == Square())
02230 record.last_to = grand_parent_simulation ? node.moved.to() : tree->king(alt(P)).square();
02231 const Square grand_parent_delay_last_to
02232 = (record.last_to != tree->king(alt(P)).square()) ? record.last_to : Square();
02233
02234 generateEscape<P>(tree->state, record.need_full_width, grand_parent_delay_last_to, node.moves);
02235 if (node.moves.empty() && ! record.need_full_width) {
02236 record.need_full_width = true;
02237 generateEscape<P>(tree->state, record.need_full_width, grand_parent_delay_last_to, node.moves);
02238 }
02239 if (node.moves.empty()) {
02240 record.setProofPieces(ProofPieces::leaf(tree->state, P, record.stands[P]));
02241 record.proof_disproof = ProofDisproof::NoEscape();
02242 return;
02243 }
02244
02245 #ifdef DISPROOF_AVERAGE
02246 int frontier_count = 0, sum_frontier_disproof = 0;
02247 #endif
02248 assert(node.children.empty());
02249 {
02250 node.allocate(node.moves.size());
02251 for (size_t i=0;i <node.moves.size(); ++i) {
02252 #ifdef MEMORIZE_SOLVED_IN_BITSET
02253 if (record.solved & (1ull << i))
02254 continue;
02255 #endif
02256 const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
02257 node.children[i] = table->probe<P>(new_key, node.nextWhiteStand(alt(P), node.moves[i]));
02258 if (node.children[i].proof_disproof.isCheckmateSuccess()) {
02259 node.setCheckmateChildInDefense(i);
02260 }
02261 #ifdef CHECKMATE_D2
02262 else if (node.children[i].proof_disproof == ProofDisproof(1,1)) {
02263 FixedDepthSolverExt fixed_solver(tree->state);
02264 PieceStand proof_pieces;
02265 Move check_move;
02266 node.children[i].proof_disproof
02267 = fixed_solver.hasEscapeByMove<P>(node.moves[i], 0, check_move, proof_pieces);
02268 ++node_count;
02269 if (node.children[i].proof_disproof.isCheckmateSuccess()) {
02270 node.children[i].best_move = check_move;
02271 node.children[i].setProofPieces(proof_pieces);
02272 node.children[i].node_count++;
02273 node.setCheckmateChildInDefense(i);
02274 }
02275 else {
02276 if (node.children[i].proof_disproof.isCheckmateFail()) {
02277 node.children[i].proof_disproof = ProofDisproof(1,1);
02278 if (i) {
02279 node.moves[0] = node.moves[i];
02280 node.children[0] = node.children[i];
02281 node.children_path[0] = node.children_path[i];
02282 const int old_size = (int)node.moves.size();
02283 for (int j=1; j<old_size; ++j) {
02284 node.moves.pop_back();
02285 node.children.pop_back();
02286 node.children_path.pop_back();
02287 }
02288 }
02289 break;
02290 }
02291 else {
02292 #ifndef MINIMAL
02293 if (HashRandomPair::initialized()) {
02294
02295 std::pair<char,char> randomness = HashRandomPair::value(new_key);
02296 if (randomness.first || randomness.second) {
02297 unsigned int proof = node.children[i].proof();
02298 unsigned int disproof = node.children[i].disproof();
02299 proof += randomness.first;
02300 disproof += randomness.second;
02301 node.children[i].proof_disproof = ProofDisproof( proof, disproof );
02302 }
02303 }
02304 #endif
02305 }
02306 #ifdef DISPROOF_AVERAGE
02307 ++frontier_count;
02308 sum_frontier_disproof += node.children[i].proof_disproof.disproof();
02309 #endif
02310 }
02311
02312 }
02313 #endif
02314 if (! node.children[i].proof_disproof.isCheckmateFail()) {
02315 node.children_path[i] = path_table->probe(new_key);
02316 if (node.isLoop(i)) {
02317 node.setLoopDetection();
02318 return;
02319 }
02320 #ifdef GRAND_PARENT_SIMULATION
02321 if (grand_parent_simulation && node.children[i].proof_disproof == ProofDisproof(1,1)) {
02322 const Node& gparent = tree->node[tree->depth-2];
02323 size_t gi=std::find(gparent.moves.begin(), gparent.moves.end(), node.moves[i]) - gparent.moves.begin();
02324 if (gi < gparent.moves.size()
02325 && (
02326 #ifdef MEMORIZE_SOLVED_IN_BITSET
02327 (gparent.record.solved & (1ull<<gi))
02328 ||
02329 #endif
02330 gparent.children[gi].proof_disproof.isCheckmateSuccess())) {
02331 grandParentSimulation<P>(i, gparent, gi);
02332 if (node.children[i].proof_disproof.isCheckmateSuccess())
02333 node.setCheckmateChildInDefense(i);
02334 }
02335 }
02336 #endif
02337 }
02338 if (node.children[i].proof_disproof.isCheckmateFail()) {
02339 tree->setNoCheckmateDefense(P, i);
02340 table->store(node.hash_key, record);
02341 return;
02342 }
02343 #ifdef AGGRESSIVE_FIND_DAG2
02344 if (!node.children[i].proof_disproof.isFinal()
02345 && std::max(node.children[i].proof(),node.children[i].disproof()) >= DagFindThreshold2
02346 && node.children[i].last_move.isNormal()
02347 && node.children[i].last_move != node.moves[i]) {
02348 findDagSource(node.hashes[i], node.children[i],
02349 node.nextWhiteStand(alt(P), node.moves[i]));
02350 }
02351 #endif
02352 }
02353 if (record.need_full_width==1) {
02354 record.need_full_width++;
02355 for (size_t i=0;i <node.moves.size(); ++i) {
02356 if (
02357 #ifdef MEMORIZE_SOLVED_IN_BITSET
02358 ((record.solved & (1ull<<i))
02359 || (i >= 64 && node.children[i].proof_disproof.isCheckmateSuccess()))
02360 #else
02361 node.children[i].proof_disproof.isCheckmateSuccess()
02362 #endif
02363
02364 && node.moves[i].isDrop()) {
02365 blockingSimulation<P>(i, ProofOracle(node.hash_key.newHashWithMove(node.moves[i]),
02366 node.nextWhiteStand(alt(P), node.moves[i])));
02367 }
02368 }
02369 }
02370 }
02371 assert(node.children.size() == node.moves.size());
02372
02373
02374 if (parallel_shared)
02375 table->setWorking(node.hash_key, record, thread_id);
02376
02377
02378 const Move recorded_last_move = node.moved;
02379 record.last_move = node.moved;
02380
02381 #ifdef DISPROOF_AVERAGE
02382 const size_t disproof_average = frontier_count ? sum_frontier_disproof/frontier_count : 1;
02383 #else
02384 const size_t disproof_average = 1;
02385 #endif
02386
02387 #ifdef DFPN_DEBUG
02388 if (std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.hash_key))
02389 != debug_node.end() && timer > debug_time_start)
02390 tree->dump(__LINE__);
02391 #endif
02392 CArray<char,DfpnMaxUniqMoves> target;
02393 for (int loop=0; true; ++loop) {
02394 std::fill(target.begin(), target.begin()+(int)node.moves.size(), false);
02395 unsigned int min_disproof=record.min_pdp, min_disproof2=record.min_pdp;
02396 size_t sum_proof = 0, max_upward_proof = 0, max_drop_proof = 0, next_i=node.children.size();
02397 size_t max_proof_dag = 0;
02398 int max_children_depth = 0, upward_count = 0;
02399 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
02400 size_t max_proof = 0;
02401 bool false_branch_candidate = !record.false_branch;
02402 #endif
02403 for (size_t i=0; i<node.children.size(); ++i) {
02404 #ifdef MEMORIZE_SOLVED_IN_BITSET
02405 if (record.solved & (1ull << i))
02406 continue;
02407 #endif
02408 if (i > 0 && min_disproof < ProofDisproof::DISPROOF_LIMIT
02409 && node.moves[i].fromTo() == node.moves[i-1].fromTo()
02410 && ! node.moves[i].isDrop()) {
02411
02412 assert(node.moves[i].ptype() == node.moves[i-1].oldPtype());
02413 continue;
02414 }
02415 size_t disproof = node.children[i].disproof();
02416 size_t proof = node.children[i].proof();
02417 if (node.children[i].proof_disproof.isCheckmateFail()) {
02418
02419 assert(! node.children[i].proof_disproof.isLoopDetection());
02420 tree->setNoCheckmateDefense(P, i);
02421 table->store(node.hash_key, record, thread_id);
02422 if (parallel_shared)
02423 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02424 return;
02425 }
02426 #ifdef OSL_DFPN_SMP
02427 if (proof && disproof) {
02428 if (parallel_shared && node.children[i].working_threads) {
02429
02430 disproof += misc::BitOp::countBit(node.children[i].working_threads);
02431 }
02432 }
02433 #endif
02434 if (node.children_path[i]) {
02435 if (node.isLoop(i)) {
02436 node.setLoopDetection();
02437 if (parallel_shared)
02438 table->leaveWorking(node.hash_key, thread_id);
02439 return;
02440 }
02441 if (! node.children[i].proof_disproof.isFinal()) {
02442 max_children_depth = std::max(max_children_depth, node.children_path[i]->distance);
02443 #ifdef IGNORE_MONSTER_CHILD
02444 if (node.children_path[i]->distance <= node.path_record->distance
02445 && (! record.need_full_width || min_disproof < ProofDisproof::DISPROOF_LIMIT)
02446 && node.children[i].proof_disproof.proof() >= node.threshold.proof()
02447 && node.threshold.proof() > IgnoreUpwardProofThreshold) {
02448 false_branch_candidate = false;
02449 continue;
02450 }
02451 else
02452 #endif
02453 #ifdef NAGAI_DAG_TEST
02454 if (record.dag_moves & (1ull << i)) {
02455 max_proof_dag = std::max(max_proof_dag, proof);
02456 proof = 0;
02457 }
02458 else
02459 #endif
02460 #ifdef DELAY_UPWARD
02461 if (node.children_path[i]->distance <= node.path_record->distance) {
02462 max_upward_proof = std::max(max_upward_proof , proof);
02463 ++upward_count;
02464 proof = UpwardWeight;
02465 }
02466 else
02467 #endif
02468 if (node.moves[i].isDrop() && !tree->state.hasEffectAt(alt(P), node.moves[i].to())) {
02469 max_drop_proof = std::max(max_drop_proof, proof);
02470 proof = SacrificeBlockCount;
02471 }
02472 }
02473 }
02474 else {
02475 max_children_depth = node.path_record->distance+1;
02476 }
02477 target[i] = true;
02478 if (disproof < min_disproof
02479 || (disproof == min_disproof && proof && proof < node.children[next_i].proof())) {
02480 min_disproof2 = min_disproof;
02481 min_disproof = disproof;
02482 next_i = i;
02483 } else if (disproof < min_disproof2) {
02484 min_disproof2 = disproof;
02485 }
02486 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
02487 if (false_branch_candidate && ! node.children[i].proof_disproof.isFinal()
02488 && (node.children[i].node_count == 0
02489 || ! node.children[i].best_move.isNormal()
02490 || ! (node.moves[i].ptype() == KING && ! node.moves[i].isCapture())))
02491 false_branch_candidate = false;
02492 max_proof = std::max(max_proof, proof);
02493 #endif
02494 sum_proof += proof;
02495 }
02496 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
02497 if (false_branch_candidate) {
02498 record.false_branch = true;
02499 HashKey goal;
02500 for (size_t i=0; i<node.children.size(); ++i) {
02501 if (! target[i])
02502 continue;
02503 HashKey key = node.hashes[i];
02504 key = key.newHashWithMove(node.children[i].best_move);
02505 if (goal == HashKey()) {
02506 goal = key;
02507 continue;
02508 }
02509 if (goal != key) {
02510 record.false_branch = false;
02511 break;
02512 }
02513 }
02514 }
02515 if (record.false_branch)
02516 sum_proof = max_proof;
02517 #endif
02518 sum_proof += max_drop_proof + max_proof_dag;
02519 if (SacrificeBlockCount && max_drop_proof)
02520 sum_proof -= SacrificeBlockCount;
02521 if (upward_count) {
02522 if (sum_proof == 0)
02523 sum_proof = std::max(sum_proof, max_upward_proof);
02524 }
02525 if (node.path_record->distance >= max_children_depth) {
02526 node.path_record->distance = max_children_depth-1;
02527 }
02528 if (min_disproof >= ProofDisproof::DISPROOF_MAX) {
02529 assert(! record.need_full_width);
02530 record.proof_disproof = ProofDisproof(1,1);
02531 record.need_full_width = 1;
02532 table->store(node.hash_key, record, thread_id);
02533 return;
02534 }
02535 #ifdef KISHIMOTO_WIDEN_THRESHOLD
02536 if (loop == 0 && sum_proof >= node.threshold.proof() && sum_proof > IgnoreUpwardProofThreshold)
02537 node.threshold = ProofDisproof(sum_proof+1, node.threshold.disproof());
02538 #endif
02539 #ifdef ADHOC_SUM_RESTRICTION
02540 if (sum_proof < ROOT_PROOF_TOL && min_disproof > 0 && sum_proof > min_disproof*AdHocSumScale) {
02541 sum_proof = min_disproof*AdHocSumScale
02542 + slow_increase(sum_proof-min_disproof*AdHocSumScale);
02543 }
02544 #endif
02545 if (min_disproof >= node.threshold.disproof()
02546 || sum_proof >= node.threshold.proof()
02547 || next_i >= node.children.size()
02548 || node_count + sum_proof >= node_count_limit) {
02549 record.proof_disproof = ProofDisproof(sum_proof, min_disproof);
02550 if (record.proof_disproof.isLoopDetection())
02551 node.setLoopDetection();
02552 else if (record.proof_disproof.isCheckmateSuccess()) {
02553 if (blocking_verify && ! record.need_full_width) {
02554
02555 record.need_full_width = 1;
02556 record.proof_disproof = ProofDisproof(1,1);
02557 table->store(node.hash_key, record, thread_id);
02558 return;
02559 }
02560 node.setCheckmateDefense(P, tree->state);
02561 } else if (! record.proof_disproof.isFinal()) {
02562 if (recorded_last_move.isNormal() && recorded_last_move != node.moved
02563 && std::max(record.proof(), record.disproof()) >= DagFindThreshold)
02564 findDagSource();
02565 #ifdef AGGRESSIVE_FIND_DAG
02566 if (std::max(node.children[next_i].proof(), node.children[next_i].disproof()) >= DagFindThreshold
02567 && node.children[next_i].last_move.isNormal()
02568 && node.children[next_i].last_move != node.moves[next_i]) {
02569 findDagSource(node.hashes[next_i], node.children[next_i],
02570 node.nextWhiteStand(alt(P), node.moves[next_i]));
02571 node.children[next_i].last_move = node.moves[next_i];
02572 table->store(node.hashes[next_i], node.children[next_i]);
02573 }
02574 #endif
02575 }
02576 record.node_count += node_count - node_count_org;
02577 table->store(node.hash_key, record, thread_id);
02578 node.path_record->node_count = record.node_count;
02579 if (parallel_shared && record.proof_disproof.isFinal())
02580 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02581 return;
02582 }
02583 #ifdef MEMORIZE_SOLVED_IN_BITSET
02584 assert(! (record.solved & (1ull << next_i)));
02585 #endif
02586 record.best_move = node.moves[next_i];
02587 tree->newVisit(alt(P), node.moves[next_i], node.hashes[next_i]);
02588 Node& next = tree->node[tree->depth+1];
02589 unsigned int proof_c = node.threshold.proof()
02590 - (sum_proof - node.children[next_i].proof());
02591 #ifdef ADHOC_SUM_RESTRICTION
02592 if (proof_c > node.threshold.proof())
02593 proof_c = node.children[next_i].proof()
02594 + (node.threshold.proof() - sum_proof);
02595 #endif
02596 next.threshold = ProofDisproof(proof_c,
02597 std::min(min_disproof2+disproof_average,
02598 (size_t)node.threshold.disproof()));
02599 CallAttack<P> helper(this);
02600 tree->depth += 1;
02601 next.path.pushMove(node.moves[next_i]);
02602 tree->state.makeUnmakeMove(Player2Type<alt(P)>(), node.moves[next_i], helper);
02603 tree->depth -= 1;
02604 if (parallel_shared && parallel_shared->data[thread_id].restart) {
02605 if (tree->depth == 0)
02606 parallel_shared->data[thread_id].clear();
02607 else {
02608 if (parallel_shared->data[thread_id].restart_key == node.hash_key) {
02609 record = table->probe<P>(node.hash_key, node.white_stand);
02610 assert(record.proof_disproof.isFinal());
02611 parallel_shared->data[thread_id].clear();
02612 }
02613 table->leaveWorking(node.hash_key, thread_id);
02614 return;
02615 }
02616 }
02617
02618 node.children[next_i] = next.record;
02619 node.children_path[next_i] = next.path_record;
02620 if (next.record.proof_disproof.isCheckmateFail()) {
02621 if (record.proof_disproof.isLoopDetection())
02622 node.setLoopDetection();
02623 else
02624 tree->setNoCheckmateDefense(P, next_i);
02625 record.node_count += node_count - node_count_org;
02626 table->store(node.hash_key, record, thread_id);
02627 node.path_record->node_count = record.node_count;
02628 if (parallel_shared && record.proof_disproof.isFinal())
02629 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02630 return;
02631 }
02632 if (next.record.proof_disproof.isCheckmateSuccess())
02633 node.setCheckmateChildInDefense(next_i);
02634 if (node_count >= node_count_limit) {
02635 record.proof_disproof = ProofDisproof(sum_proof, min_disproof);
02636 record.node_count += node_count - node_count_org;
02637 table->store(node.hash_key, record, thread_id);
02638 node.path_record->node_count = record.node_count;
02639 if (parallel_shared && record.proof_disproof.isFinal())
02640 parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
02641 return;
02642 }
02643 if (next.moved.isDrop() && next.record.proof_disproof.isCheckmateSuccess()) {
02644 blockingSimulation<P>(next_i, ProofOracle(next.hash_key, next.white_stand));
02645 }
02646 }
02647 }
02648
02649 #if (!defined MINIMAL) || (defined DFPNSTATONE)
02650 void osl::checkmate::
02651 Dfpn::analyze(const PathEncoding& path_src,
02652 const NumEffectState& src, const std::vector<Move>& moves) const
02653 {
02654 NumEffectState state(src);
02655 HashKey key(state);
02656 PathEncoding path(path_src);
02657 for (size_t i=0; i<moves.size(); ++i) {
02658 if (! state.isAlmostValidMove(moves[i]))
02659 break;
02660 state.makeMove(moves[i]);
02661 key = key.newMakeMove(moves[i]);
02662 path.pushMove(moves[i]);
02663 DfpnRecord record = table->probe(key, PieceStand(WHITE, state));
02664 const DfpnPathRecord *path_record = path_table->probe(key);
02665 std::cerr << i << ' ' << moves[i] << " " << path
02666 << ' ' << csa::show(record.best_move) << "\n";
02667 std::cerr << " " << record.proof_disproof << ' ' << record.node_count;
02668 if (path_record) {
02669 std::cerr << " distance " << path_record->distance << " twins";
02670 for (SimpleTwinList::const_iterator p=path_record->twin_list.begin();
02671 p!=path_record->twin_list.end(); ++p) {
02672 std::cerr << ' ' << *p;
02673 }
02674 }
02675 std::cerr << "\n";
02676 DfpnMoveVector moves;
02677 if (state.turn() == table->attack()) {
02678 bool has_pawn_checkmate=false;
02679 if (state.turn() == BLACK)
02680 generateCheck<BLACK>(state, moves, has_pawn_checkmate);
02681 else
02682 generateCheck<WHITE>(state, moves, has_pawn_checkmate);
02683 }
02684 else {
02685 const Square grand_parent_delay_last_to
02686 = (record.last_to != state.kingSquare(state.turn())) ? record.last_to : Square();
02687 if (state.turn() == BLACK)
02688 generateEscape<WHITE>(state, true, grand_parent_delay_last_to, moves);
02689 else
02690 generateEscape<BLACK>(state, true, grand_parent_delay_last_to, moves);
02691 }
02692 for (size_t i=0; i<moves.size(); ++i) {
02693 const Move m = moves[i];
02694 std::cerr << " " << m;
02695 DfpnRecord child = table->probe(key.newMakeMove(m),
02696 PieceStand(WHITE, state).nextStand(WHITE, m));
02697 std::cerr << ' ' << child.proof_disproof << ' ' << child.node_count;
02698 const DfpnPathRecord *child_path_record = path_table->probe(key.newMakeMove(m));
02699 if (child_path_record) {
02700 std::cerr << " d " << child_path_record->distance << " twins";
02701 for (const auto& path: child_path_record->twin_list) {
02702 std::cerr << ' ' << path;
02703 }
02704 }
02705 if (record.dag_moves & (1ull << i))
02706 std::cerr << " (*)";
02707 std::cerr << "\n";
02708 }
02709 }
02710 std::cerr << state;
02711 }
02712 #endif
02713
02714 template <osl::Player P, bool UseTable>
02715 struct osl::checkmate::Dfpn::CallProofOracleAttack
02716 {
02717 Dfpn *search;
02718 ProofOracle oracle;
02719 int proof_limit;
02720 CallProofOracleAttack(Dfpn *s, const ProofOracle& o, int pl) : search(s), oracle(o), proof_limit(pl)
02721 {
02722 }
02723 void operator()(Square) const
02724 {
02725 search->proofOracleAttack<P,UseTable>(oracle, proof_limit);
02726 }
02727 };
02728
02729 template <osl::Player P, bool UseTable>
02730 struct osl::checkmate::Dfpn::CallProofOracleDefense
02731 {
02732 Dfpn *search;
02733 ProofOracle oracle;
02734 int proof_limit;
02735 CallProofOracleDefense(Dfpn *s, const ProofOracle& o, int pl) : search(s), oracle(o), proof_limit(pl)
02736 {
02737 }
02738 void operator()(Square) const
02739 {
02740 search->proofOracleDefense<P,UseTable>(oracle, proof_limit);
02741 }
02742 };
02743
02744 template <osl::Player P, bool UseTable>
02745 void osl::checkmate::
02746 Dfpn::proofOracleAttack(const ProofOracle& key, int proof_limit)
02747 {
02748 #ifdef DFPN_DEBUG
02749 Tree::Logging logging(tree.get(), table, UseTable ? "tpatta" : "pattac");
02750 #endif
02751 assert(! tree->inCheck(alt(P)));
02752 const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
02753 Node& node = tree->node[tree->depth];
02754 DfpnRecord& record = node.record;
02755 LoopToDominance loop;
02756 DfpnVisitLock<UseTable> lk((node.path_record = (UseTable ? path_table->allocate<P>(node.hash_key, my_distance, loop) : 0)));
02757 if (UseTable && loop == BadAttackLoop) {
02758 record = DfpnRecord();
02759 node.setLoopDetection();
02760 return;
02761 }
02762 assert(node.white_stand == PieceStand(WHITE, tree->state));
02763 const size_t node_count_org = node_count++;
02764 if (node_count_limit == root_proof_simulation_limit
02765 && node_count > 100000) {
02766 std::cerr << "dfpn proof simulation > 100000 throw " << thread_id << "\n";
02767 throw DepthLimitReached();
02768 }
02769 assert(tree->depth + 2 < tree->MaxDepth);
02770 if (tree->depth + 2 >= tree->MaxDepth) {
02771 std::cerr << "throw " << thread_id << "\n";
02772 throw DepthLimitReached();
02773 }
02774 record = table->probe<P>(node.hash_key, node.white_stand);
02775 if (record.proof_disproof.isFinal())
02776 return;
02777 #if (defined CHECKMATE_A3_SIMULLATION) || (defined CHECKMATE_A3)
02778 if (record.node_count == 0)
02779 {
02780 #ifdef DFPN_STAT
02781 static stat::Ratio oracle_success("a3-simulation");
02782 #endif
02783 FixedDepthSolverExt fixed_solver(tree->state);
02784 PieceStand proof_pieces;
02785 ProofDisproof pdp = fixed_solver.hasCheckmateMove<P>(2, record.best_move, proof_pieces);
02786 ++node_count;
02787 #ifdef DFPN_STAT
02788 oracle_success.add(pdp.isCheckmateSuccess());
02789 #endif
02790 if (pdp.isCheckmateSuccess()) {
02791 record.proof_disproof = pdp;
02792 record.setProofPieces(proof_pieces);
02793 record.node_count++;
02794 return;
02795 }
02796 }
02797 #elif (!defined CHECKMATE_D2) && (!defined NO_IMMEDIATE_CHECKMATE)
02798 if (! tree->inCheck(P)
02799 && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.best_move)) {
02800 PieceStand proof_pieces;
02801 if (record.best_move.isDrop())
02802 proof_pieces.add(record.best_move.ptype());
02803 record.setProofPieces(proof_pieces);
02804 record.proof_disproof = ProofDisproof::Checkmate();
02805 return;
02806 }
02807 #endif
02808 #ifdef DFPN_DEBUG
02809 if (tree->depth > 1000) {
02810 std::cerr << tree->state;
02811 node.hash_key.dumpContents(std::cerr);
02812 std::cerr << "\n";
02813 table->showProofOracles<P>(key.key, key.white_stand, node.moved);
02814 }
02815 #endif
02816 DfpnRecord oracle = table->findProofOracle<P>(key.key, key.white_stand, node.moved);
02817 if (! oracle.proof_disproof.isCheckmateSuccess() || ! oracle.best_move.isNormal())
02818 return;
02819 const Move check_move = OracleAdjust::attack(tree->state, oracle.best_move);
02820 if (! check_move.isNormal() || ! key.traceable(P, check_move))
02821 return;
02822
02823 node.allocate(1);
02824 node.moves.clear();
02825 node.moves.push_back(check_move);
02826 const HashKey new_key = node.hash_key.newHashWithMove(node.moves[0]);
02827 if (UseTable) {
02828 node.children[0] = table->probe<P>(new_key, node.nextWhiteStand(P, node.moves[0]));
02829 node.children_path[0] = path_table->probe(new_key);
02830 if (node.isLoop(0))
02831 return;
02832 } else {
02833 node.children[0] = DfpnRecord();
02834 node.children_path[0] = 0;
02835 }
02836
02837 if (! UseTable || ! node.children[0].proof_disproof.isFinal()) {
02838 Node& next = tree->node[tree->depth+1];
02839 tree->newVisit(P, node.moves[0], new_key);
02840
02841 CallProofOracleDefense<P,UseTable> helper(this, key.newOracle(P, check_move), proof_limit);
02842 tree->depth += 1;
02843 next.path.pushMove(next.moved);
02844 tree->state.makeUnmakeMove(Player2Type<P>(), next.moved, helper);
02845 tree->depth -= 1;
02846 node.children[0] = next.record;
02847 node.children_path[0] = next.path_record;
02848
02849 if (next.record.proof_disproof == ProofDisproof::NoEscape()
02850 && next.moved.isDrop() && next.moved.ptype() == PAWN)
02851 node.children[0].proof_disproof = ProofDisproof::PawnCheckmate();
02852 }
02853 if (node.children[0].proof_disproof.isCheckmateSuccess()) {
02854 node.setCheckmateAttack(P,0);
02855 record.node_count += node_count - node_count_org;
02856 if (UseTable || node_count - node_count_org > 32) {
02857 record.last_move = node.moved;
02858 table->store(node.hash_key, record);
02859 }
02860 }
02861 else if (UseTable) {
02862
02863 if (record.last_move.isNormal() && record.last_move != node.moved
02864 && std::max(record.proof(), record.disproof()) >= 128)
02865 findDagSource();
02866 record.last_move = node.moved;
02867 }
02868 }
02869
02870 template <osl::Player P, bool UseTable>
02871 void osl::checkmate::
02872 Dfpn::proofOracleDefense(const ProofOracle& key, int proof_limit)
02873 {
02874 #ifdef DFPN_DEBUG
02875 Tree::Logging logging(tree.get(), table, UseTable ? "tpdefe" : "pdefen");
02876 #endif
02877 const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
02878 Node& node = tree->node[tree->depth];
02879 LoopToDominance loop;
02880 DfpnVisitLock<UseTable> lk((node.path_record = (UseTable ? path_table->allocate<P>(node.hash_key, my_distance, loop) : 0)));
02881 DfpnRecord& record = node.record;
02882 if (UseTable && loop == BadAttackLoop) {
02883 record = DfpnRecord();
02884 node.setLoopDetection();
02885 return;
02886 }
02887 if (! UseTable && tree->depth >= 4) {
02888 if (tree->node[tree->depth-4].hash_key == node.hash_key
02889 || (tree->depth >= 6 && tree->node[tree->depth-6].hash_key == node.hash_key)) {
02890 record = DfpnRecord();
02891 return;
02892 }
02893 }
02894 const size_t node_count_org = node_count++;
02895 assert(node.white_stand == PieceStand(WHITE, tree->state));
02896 if (! tree->inCheck(alt(P)) || tree->inCheck(P)) {
02897 record = DfpnRecord();
02898 record.proof_disproof = ProofDisproof::NoCheckmate();
02899 return;
02900 }
02901
02902 record = table->probe<P>(node.hash_key, node.white_stand);
02903 if (record.proof_disproof.isFinal())
02904 return;
02905 if (proof_limit > ProofSimulationTolerance)
02906 proof_limit = ProofSimulationTolerance;
02907
02908 const bool grand_parent_simulation = grandParentSimulationSuitable();
02909 if (record.last_to == Square())
02910 record.last_to = grand_parent_simulation ? node.moved.to() : tree->king(alt(P)).square();
02911 const Square grand_parent_delay_last_to
02912 = (record.last_to != tree->king(alt(P)).square()) ? record.last_to : Square();
02913 generateEscape<P>(tree->state, true, grand_parent_delay_last_to, node.moves);
02914 if (node.moves.empty()) {
02915 record.setProofPieces(ProofPieces::leaf(tree->state, P, record.stands[P]));
02916 record.proof_disproof = ProofDisproof::NoEscape();
02917 return;
02918 }
02919
02920
02921 assert(node.children.empty());
02922 {
02923 node.allocate(node.moves.size());
02924 for (size_t i=0;i <node.moves.size(); ++i) {
02925 #ifdef MEMORIZE_SOLVED_IN_BITSET
02926 if (record.solved & (1ull << i))
02927 continue;
02928 #endif
02929 const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
02930 node.children[i] = UseTable
02931 ? table->probe<P>(new_key, node.nextWhiteStand(alt(P), node.moves[i]))
02932 : DfpnRecord();
02933 if (node.children[i].proof_disproof.isCheckmateSuccess()) {
02934 node.setCheckmateChildInDefense(i);
02935 }
02936 #ifdef CHECKMATE_D2
02937 else if (node.record.node_count == 0 && node.children[i].node_count == 0) {
02938 FixedDepthSolverExt fixed_solver(tree->state);
02939 PieceStand proof_pieces;
02940 Move check_move;
02941 node.children[i].proof_disproof
02942 = fixed_solver.hasEscapeByMove<P>(node.moves[i], 0, check_move, proof_pieces);
02943 if (node.children[i].proof_disproof.isCheckmateSuccess()) {
02944 node.children[i].best_move = check_move;
02945 node.children[i].setProofPieces(proof_pieces);
02946 node.setCheckmateChildInDefense(i);
02947 }
02948 else {
02949 if (node.children[i].proof_disproof.isCheckmateFail())
02950 node.children[i].proof_disproof = ProofDisproof(1,1);
02951 }
02952 ++node_count;
02953 }
02954 #endif
02955 if (node.children[i].proof_disproof.isCheckmateFail()) {
02956 tree->setNoCheckmateDefense(P, i);
02957 if (UseTable)
02958 table->store(node.hash_key, record);
02959 return;
02960 }
02961 node.children_path[i] = UseTable ? path_table->probe(new_key) : 0;
02962 }
02963 }
02964 assert(node.children.size() == node.moves.size());
02965 if (UseTable) {
02966 for (size_t i=0; i<node.children.size(); ++i) {
02967 if (node.isLoop(i)) {
02968 node.setLoopDetection();
02969 return;
02970 }
02971 }
02972 }
02973 unsigned int sum_proof=0, min_disproof=record.min_pdp;
02974 int num_proof = 0;
02975 for (size_t next_i=0; next_i<node.children.size(); ++next_i) {
02976 #ifdef MEMORIZE_SOLVED_IN_BITSET
02977 if (record.solved & (1ull << next_i))
02978 continue;
02979 #endif
02980 if (node.children[next_i].proof_disproof.isCheckmateSuccess()) {
02981 min_disproof = std::min(min_disproof, node.children[next_i].disproof());
02982 continue;
02983 }
02984 if (! key.traceable(alt(P), node.moves[next_i])) {
02985 ++sum_proof;
02986 min_disproof = 1;
02987 if (! UseTable)
02988 break;
02989 continue;
02990 }
02991 const Square next_to = node.moves[next_i].to();
02992 if (sum_proof && tree->state.hasEffectAt(P, next_to)
02993 && (! tree->state.hasEffectAt(alt(P), next_to)
02994 || (tree->state.countEffect(alt(P), next_to) == 1
02995 && ! node.moves[next_i].isDrop())))
02996 continue;
02997 assert(! node.isLoop(next_i));
02998 Node& next = tree->node[tree->depth+1];
02999 #ifdef MEMORIZE_SOLVED_IN_BITSET
03000 assert(! (record.solved & (1ull << next_i)));
03001 #endif
03002 tree->newVisit(alt(P), node.moves[next_i], node.hashes[next_i]);
03003
03004 CallProofOracleAttack<P,UseTable> helper(this, key.newOracle(alt(P), node.moves[next_i]), proof_limit-sum_proof);
03005 tree->depth += 1;
03006 next.path.pushMove(node.moves[next_i]);
03007 tree->state.makeUnmakeMove(Player2Type<alt(P)>(), node.moves[next_i], helper);
03008 tree->depth -= 1;
03009
03010 node.children[next_i] = next.record;
03011 node.children_path[next_i] = next.path_record;
03012 if (next.record.proof_disproof.isCheckmateFail()) {
03013 if (record.proof_disproof.isLoopDetection())
03014 node.setLoopDetection();
03015 else
03016 tree->setNoCheckmateDefense(P, next_i);
03017 record.node_count += node_count - node_count_org;
03018 if (UseTable)
03019 table->store(node.hash_key, record);
03020 return;
03021 }
03022 if (next.record.proof_disproof.isCheckmateSuccess()) {
03023 node.setCheckmateChildInDefense(next_i);
03024 ++num_proof;
03025 }
03026 sum_proof += next.record.proof();
03027 min_disproof = std::min(min_disproof, next.record.disproof());
03028 if ((sum_proof && ! UseTable) || (int)sum_proof > proof_limit)
03029 break;
03030 }
03031 if (sum_proof == 0) {
03032 node.record.proof_disproof = ProofDisproof(sum_proof, min_disproof);
03033 node.setCheckmateDefense(P, tree->state);
03034 }
03035 else if (UseTable) {
03036
03037 if (record.last_move.isNormal() && record.last_move != node.moved
03038 && std::max(record.proof(), record.disproof()) >= 128)
03039 findDagSource();
03040 record.last_move = node.moved;
03041 }
03042 }
03043
03044 template <osl::Player P>
03045 void osl::checkmate::
03046 Dfpn::blockingSimulation(int oracle_i, const ProofOracle& oracle)
03047 {
03048 #ifdef DFPN_DEBUG
03049 Tree::Logging logging(tree.get(), table, "blocks");
03050 #endif
03051 #ifdef DFPN_STAT
03052 static stat::Ratio oracle_success("blocking proof");
03053 #endif
03054 Node& node = tree->node[tree->depth];
03055 Node& next = tree->node[tree->depth+1];
03056 const Move oracle_move = node.moves[oracle_i];
03057 const Square to = oracle_move.to();
03058 assert((node.record.solved & (1ull << oracle_i))
03059 || node.children[oracle_i].proof_disproof.isCheckmateSuccess());
03060 for (size_t i=0; i<node.moves.size(); ++i) {
03061 #ifdef MEMORIZE_SOLVED_IN_BITSET
03062 if (node.record.solved & (1ull << i))
03063 continue;
03064 #endif
03065 if (node.isLoop(i))
03066 break;
03067 if (node.children[i].proof_disproof.isFinal() || node.moves[i].to() != to)
03068 continue;
03069 if (! oracle.traceable(alt(P), node.moves[i]))
03070 continue;
03071 #ifdef MEMORIZE_SOLVED_IN_BITSET
03072 assert(! (node.record.solved & (1ull << i)));
03073 #endif
03074 tree->newVisit(alt(P), node.moves[i], node.hashes[i]);
03075 CallProofOracleAttack<P,true> helper(this, oracle, node.threshold.proof());
03076
03077 tree->depth += 1;
03078 next.path.pushMove(node.moves[i]);
03079 tree->state.makeUnmakeMove(Player2Type<alt(P)>(), node.moves[i], helper);
03080 tree->depth -= 1;
03081
03082 node.children[i] = next.record;
03083 node.children_path[i] = next.path_record;
03084
03085 #ifdef DFPN_STAT
03086 oracle_success.add(next.record.proof_disproof.isCheckmateSuccess());
03087 #endif
03088 if (next.record.proof_disproof.isCheckmateSuccess()) {
03089 node.setCheckmateChildInDefense(i);
03090 }
03091 }
03092 }
03093
03094 template <osl::Player P>
03095 void osl::checkmate::
03096 Dfpn::grandParentSimulation(int cur_i, const Node& gparent, int gp_i)
03097 {
03098 #ifdef DFPN_DEBUG
03099 Tree::Logging logging(tree.get(), table, "grands");
03100 #endif
03101 #ifdef DFPN_STAT
03102 static stat::Ratio oracle_success("grandparent proof", true);
03103 #endif
03104 Node& node = tree->node[tree->depth];
03105 Node& next = tree->node[tree->depth+1];
03106
03107 const Move move = gparent.moves[gp_i];
03108 assert(move == node.moves[cur_i]);
03109 const HashKey& oracle_hash = (gparent.record.solved & (1ull << gp_i))
03110 ? gparent.hash_key.newHashWithMove(move)
03111 : gparent.hashes[gp_i];
03112 const ProofOracle oracle(oracle_hash, gparent.nextWhiteStand(alt(P), move));
03113
03114 tree->newVisit(alt(P), node.moves[cur_i], node.hashes[cur_i]);
03115 CallProofOracleAttack<P,true> helper(this, oracle, gparent.threshold.proof());
03116
03117 tree->depth += 1;
03118 next.path.pushMove(move);
03119 tree->state.makeUnmakeMove(Player2Type<alt(P)>(), move, helper);
03120 tree->depth -= 1;
03121
03122 node.children[cur_i] = next.record;
03123 node.children_path[cur_i] = next.path_record;
03124 #ifdef DFPN_STAT
03125 oracle_success.add(next.record.proof_disproof.isCheckmateSuccess());
03126 #endif
03127 }
03128
03129
03130 int osl::checkmate::
03131 Dfpn::distance(const HashKey& key) const
03132 {
03133 const DfpnPathRecord *record = path_table->probe(key);
03134 if (record)
03135 return record->distance;
03136 return -1;
03137 }
03138
03139
03140
03141
03142
03143