15 # include <condition_variable>
17 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
22 #include <unordered_map>
23 #include <forward_list>
27 #define DFPN_SHARE_TABLE
46 struct List : FixedCapacityVector<Element, max_oracle_list_size>
57 mutable std::mutex mutex;
59 typedef std::unordered_map<HashKey, List, std::hash<HashKey>>
table_t;
66 void addProof(
const NumEffectState& state,
const HashKey& key, PieceStand proof_pieces)
68 const Dfpn::ProofOracle oracle(key, PieceStand(
WHITE, state));
69 const std::pair<HashKey,HashKey> king =
makeLargeKey(state);
71 std::lock_guard<std::mutex> lk(mutex);;
73 const Element e(oracle, proof_pieces,
table.size(), state.inCheck());
74 table[king.first].add(e);
75 table[king.second].add(e);
77 const List
probe(
const NumEffectState& state)
const
79 const std::pair<HashKey,HashKey> key =
makeLargeKey(state);
81 std::lock_guard<std::mutex> lk(mutex);;
83 table_t::const_iterator p =
table.find(key.first);
86 p =
table.find(key.second);
92 template <Direction DIR>
93 static void addKey(HashKey& key,
const SimpleState& state, Square target)
97 const Piece piece = state.pieceOnBoard(target);
100 template <Direction DIR, Direction DIR2>
101 static void addKey(HashKey& key,
const SimpleState& state, Square target)
106 const Piece piece = state.pieceOnBoard(target);
109 const HashKey
makeKey(
const SimpleState& state)
const
111 const Square target_king=state.kingSquare(
defender);
115 state.pieceOnBoard(center).ptypeO());
116 addKey<UL>(key, state, center); addKey<U> (key, state, center);
117 addKey<UR>(key, state, center);
118 addKey<L> (key, state, center); addKey<R> (key, state, center);
119 addKey<DL>(key, state, center); addKey<D> (key, state, center);
120 addKey<DR>(key, state, center);
123 const std::pair<HashKey,HashKey>
makeLargeKey(
const SimpleState& state)
const
125 HashKey key_small =
makeKey(state), key_large;
126 const Square target_king=state.kingSquare(
defender);
129 state.pieceOnBoard(center).ptypeO());
130 addKey<UL>(key_large, state, center); addKey<U> (key_large, state, center);
131 addKey<UR>(key_large, state, center);
132 addKey<L> (key_large, state, center); addKey<R> (key_large, state, center);
133 addKey<DL>(key_large, state, center); addKey<D> (key_large, state, center);
134 addKey<DR>(key_large, state, center);
135 addKey<L,UL>(key_large, state, center); addKey<L,L> (key_large, state, center);
136 addKey<L,DL>(key_large, state, center);
137 addKey<R,UR>(key_large, state, center); addKey<R,R> (key_large, state, center);
138 addKey<R,DR>(key_large, state, center);
139 return std::make_pair(key_large, key_small);
154 std::condition_variable condition;
155 CArray<LightMutex,max_oracle_list_size> proof_by_oracle_mutex;
159 std::unique_ptr<DfpnParallel> parallel_search;
184 std::cerr << a.getAverage()
185 <<
" " << (int)(a.getAverage()*a.numElements()) <<
"\n";
186 std::cerr <<
"oracles " <<
pool[
BLACK].table.size() <<
" " <<
pool[
WHITE].table.size() <<
"\n";
187 std::cerr <<
"table " <<
table[0].totalSize() <<
" " <<
table[1].totalSize() <<
"\n";
188 table[0].showStats();
189 table[1].showStats();
196 std::lock_guard<std::mutex> lk(mutex);;
203 std::lock_guard<std::mutex> lk(mutex);;
216 std::unique_lock<std::mutex> lk(
shared->mutex);
218 shared->condition.wait(lk);
225 std::lock_guard<std::mutex> lk(
shared->mutex);
229 shared->condition.notify_all();
238 #ifndef DFPN_SHARE_TABLE
239 CArray<DfpnTable,2>
table;
245 #ifndef DFPN_SHARE_TABLE
255 std::cerr <<
"local " <<
table_small[0].totalSize()
265 : shared(new Shared), local(new Local)
271 : shared(src.shared), local(new Local)
283 #ifdef DFPN_SHARE_TABLE
284 local->dfpn.
setTable(&(shared->table[attack]));
286 local->dfpn.setTable(&(local->table[attack]));
288 local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
295 local->dfpn.
setTable(&(local->table_small[attack]));
296 local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
303 #ifdef DFPN_SHARE_TABLE
306 size_t total = shared->table[
BLACK].size() + shared->table[
WHITE].size();
310 || (total*unit_size*3 < current_use
317 std::unique_lock<std::mutex> lk(shared->mutex);
319 total = shared->table[
BLACK].size() + shared->table[
WHITE].size();
321 || (total*unit_size*3 < current_use
326 if (shared->shared_table_user > 0
327 && memory_use_ratio_1000 < 650
328 && total < shared->last_gc*2)
330 if (shared->shared_table_user < 0 || shared->shared_table_gc_wait > 0)
333 while (shared->shared_table_user > 0) {
334 ++shared->shared_table_gc_wait;
335 shared->condition.wait(lk);
336 --shared->shared_table_gc_wait;
338 if (shared->shared_table_user < 0)
341 shared->shared_table_user--;
343 removed += shared->table[
BLACK].smallTreeGC(shared->gc_threshold);
344 removed += shared->table[
WHITE].smallTreeGC(shared->gc_threshold);
347 std::lock_guard<std::mutex> lk(shared->mutex);
349 if (total > shared->last_gc*2) {
350 if (100.0*removed/total < 70)
351 shared->gc_threshold += 15;
352 else if (100.0*removed/total < 90)
353 shared->gc_threshold += 5;
355 shared->last_gc = total - removed;
356 shared->shared_table_user++;
357 assert(shared->shared_table_user == 0);
359 shared->condition.notify_all();
366 if (removed > 10000 || elapsed > 0.1)
367 std::cerr <<
" GC " << removed
368 <<
" entries " << std::setprecision(3)
369 << (unit_size * removed / (1<<20)) <<
"MB "
370 << 100.0*removed/total <<
"%"
371 <<
" (" << elapsed <<
" s)\n";
376 template <osl::Player P>
382 assert(state.
turn() == P);
384 Dfpn& dfpn = prepareDfpn(P);
385 const OraclePool::List l(shared->pool[P].probe(state));
388 for (
size_t i=0; i<l.size(); ++i)
391 || l[i].in_check != state.
inCheck())
395 ? dfpn.
tryProof(state, key, path, l[i].oracle, l[i].id, best_move, last_move)
396 : dfpn.
tryProofLight(state, key, path, l[i].oracle, l[i].
id, best_move, last_move);
398 local->local_node_count += count;
399 shared->addSimulationNodeCount(count);
411 if (node_limit == 0 && num_tried)
418 std::lock_guard<std::mutex> lk(shared->mutex);
420 Shared::disproof_table_t::const_iterator p = shared->disproof_table.find(key);
421 if (p != shared->disproof_table.end()) {
422 for (
const auto& ppath: p->second)
427 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
428 static stat::Ratio migration_success(
"migration_success",
true);
429 bool need_migration =
false;
432 if (node_limit < 80) {
434 local->table_small[P].clear();
436 Dfpn& dfpn_small = prepareDfpnSmall(P);
438 const size_t count = dfpn_small.
nodeCount();
439 local->local_node_count += count;
440 shared->addMainNodeCount(count);
443 std::lock_guard<std::mutex> lk(shared->mutex);
445 shared->disproof_table[key].push_front(path);
451 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
452 need_migration =
true;
456 Shared::TableUseLock lk(&*shared);
460 local->local_node_count += count;
461 shared->addMainNodeCount(count);
463 shared->pool[P].addProof(state, key, proof_pieces);
464 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
470 std::lock_guard<std::mutex> lk(shared->mutex);
472 shared->disproof_table[key].push_front(path);
485 return findProof<BLACK>(node_limit, state, key, path, best_move, last_move);
487 return findProof<WHITE>(node_limit, state, key, path, best_move, last_move);
495 return findProof(node_limit, state, key, path, best_move, last_move)
496 .isCheckmateSuccess();
500 template <osl::Player P>
501 bool osl::checkmate::
502 DualDfpn::isWinningStateParallel(
int node_limit,
const NumEffectState& state,
511 std::lock_guard<std::mutex> lk(shared->mutex);
513 if (! shared->parallel_search)
515 #ifdef DFPN_SHARE_TABLE
516 shared->parallel_search->setTable(&(shared->table[P]));
518 shared->parallel_search->setTable(&(local->table[P]));
521 pdp = shared->parallel_search->hasCheckmateMove
522 (state, key, path, node_limit, best_move, proof_pieces, last_move);
523 count = shared->parallel_search->nodeCount();
525 shared->addMainNodeCount(count);
527 shared->pool[P].addProof(state, key, proof_pieces);
529 shared->disproof_table[key].push_front(path);
536 bool osl::checkmate::
537 DualDfpn::isWinningStateParallel(
int node_limit,
const NumEffectState& state,
539 Move& best_move, Move last_move)
541 if (state.turn() ==
BLACK)
542 return isWinningStateParallel<BLACK>(node_limit, state, key, path, best_move, last_move);
544 return isWinningStateParallel<WHITE>(node_limit, state, key, path, best_move, last_move);
548 template <osl::Player P>
555 Shared::TableUseLock lk(&*shared);
556 assert(state.
turn() == P);
557 Dfpn& dfpn = prepareDfpn(
alt(P));
560 local->local_node_count += count;
561 shared->addMainNodeCount(count);
571 return isLosingState<BLACK>(node_limit, state, key, path, last_move);
573 return isLosingState<WHITE>(node_limit, state, key, path, last_move);
582 Shared::TableUseLock lk(&*shared);
583 Dfpn& dfpn = prepareDfpn(attack);
585 for (
int i=0; i<counter.
checkCount(attack); ++i)
604 shared->blocking_verify[root] =
true;
605 shared->blocking_verify[
alt(root)] =
true;
616 Shared::TableUseLock lk(&*shared);
617 return prepareDfpn(attack).distance(key);
623 #ifdef OSL_USE_RACE_DETECTOR
624 std::lock_guard<std::mutex> lk(shared->mutex);
626 return shared->main_node_count;
633 #ifdef OSL_USE_RACE_DETECTOR
634 std::lock_guard<std::mutex> lk(shared->mutex);
636 return shared->main_node_count + shared->simulation_count;
642 return shared->
table[attack];
655 template bool checkmate::DualDfpn::isLosingState<BLACK>
657 template bool checkmate::DualDfpn::isLosingState<WHITE>
661 template bool checkmate::DualDfpn::isWinningStateParallel<BLACK>
663 template bool checkmate::DualDfpn::isWinningStateParallel<WHITE>