17 # include <boost/thread/condition.hpp>
19 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
24 #include <boost/foreach.hpp>
28 #define DFPN_SHARE_TABLE
47 struct List : FixedCapacityVector<Element, max_oracle_list_size>
51 if (size() == capacity())
58 mutable boost::mutex mutex;
70 const std::pair<HashKey,HashKey> king =
makeLargeKey(state);
72 boost::mutex::scoped_lock lk(mutex);;
74 const Element e(oracle, proof_pieces,
table.size(), state.inCheck());
75 table[king.first].add(e);
76 table[king.second].add(e);
80 const std::pair<HashKey,HashKey> key =
makeLargeKey(state);
82 boost::mutex::scoped_lock lk(mutex);;
84 table_t::const_iterator p =
table.find(key.first);
87 p =
table.find(key.second);
93 template <Direction DIR>
98 const Piece piece = state.pieceOnBoard(target);
101 template <Direction DIR, Direction DIR2>
107 const Piece piece = state.pieceOnBoard(target);
110 const HashKey
makeKey(
const SimpleState& state)
const
116 state.pieceOnBoard(center).ptypeO());
117 addKey<UL>(key, state,
center); addKey<U> (key, state,
center);
118 addKey<UR>(key, state,
center);
119 addKey<L> (key, state,
center); addKey<R> (key, state,
center);
120 addKey<DL>(key, state,
center); addKey<D> (key, state,
center);
121 addKey<DR>(key, state,
center);
124 const std::pair<HashKey,HashKey>
makeLargeKey(
const SimpleState& state)
const
126 HashKey key_small =
makeKey(state), key_large;
130 state.pieceOnBoard(center).ptypeO());
131 addKey<UL>(key_large, state,
center); addKey<U> (key_large, state,
center);
132 addKey<UR>(key_large, state,
center);
133 addKey<L> (key_large, state,
center); addKey<R> (key_large, state,
center);
134 addKey<DL>(key_large, state,
center); addKey<D> (key_large, state,
center);
135 addKey<DR>(key_large, state,
center);
136 addKey<L,UL>(key_large, state,
center); addKey<L,L> (key_large, state,
center);
137 addKey<L,DL>(key_large, state,
center);
138 addKey<R,UR>(key_large, state,
center); addKey<R,R> (key_large, state,
center);
139 addKey<R,DR>(key_large, state,
center);
140 return std::make_pair(key_large, key_small);
155 boost::condition condition;
156 CArray<LightMutex,max_oracle_list_size> proof_by_oracle_mutex;
160 boost::scoped_ptr<DfpnParallel> parallel_search;
187 std::cerr <<
"oracles " <<
pool[
BLACK].table.size() <<
" " <<
pool[
WHITE].table.size() <<
"\n";
188 std::cerr <<
"table " <<
table[0].totalSize() <<
" " <<
table[1].totalSize() <<
"\n";
189 table[0].showStats();
190 table[1].showStats();
197 boost::mutex::scoped_lock lk(mutex);;
204 boost::mutex::scoped_lock lk(mutex);;
214 boost::mutex::scoped_lock lk(
shared->mutex);
216 shared->condition.wait(lk);
223 boost::mutex::scoped_lock lk(
shared->mutex);
227 shared->condition.notify_all();
236 #ifndef DFPN_SHARE_TABLE
237 CArray<DfpnTable,2>
table;
243 #ifndef DFPN_SHARE_TABLE
253 std::cerr <<
"local " <<
table_small[0].totalSize()
269 : shared(src.shared), local(new
Local)
281 #ifdef DFPN_SHARE_TABLE
282 local->dfpn.
setTable(&(shared->table[attack]));
284 local->dfpn.setTable(&(local->table[attack]));
286 local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
293 local->dfpn.
setTable(&(local->table_small[attack]));
294 local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
301 #ifdef DFPN_SHARE_TABLE
302 const size_t unit_size = (
sizeof(HashKey)+
sizeof(
DfpnRecord)+
sizeof(
char*)*2);
304 size_t total = shared->table[
BLACK].size() + shared->table[
WHITE].size();
308 || (total*unit_size*3 < current_use
311 MilliSeconds start = MilliSeconds::now();
315 boost::mutex::scoped_lock lk(shared->mutex);
317 total = shared->table[
BLACK].size() + shared->table[
WHITE].size();
319 || (total*unit_size*3 < current_use
324 if (shared->shared_table_user > 0
325 && memory_use_ratio_1000 < 650
326 && total < shared->last_gc*2)
328 if (shared->shared_table_user < 0 || shared->shared_table_gc_wait > 0)
331 while (shared->shared_table_user > 0) {
332 ++shared->shared_table_gc_wait;
333 shared->condition.wait(lk);
334 --shared->shared_table_gc_wait;
336 if (shared->shared_table_user < 0)
339 shared->shared_table_user--;
341 removed += shared->table[
BLACK].smallTreeGC(shared->gc_threshold);
342 removed += shared->table[
WHITE].smallTreeGC(shared->gc_threshold);
345 boost::mutex::scoped_lock lk(shared->mutex);
347 if (total > shared->last_gc*2) {
348 if (100.0*removed/total < 70)
349 shared->gc_threshold += 15;
350 else if (100.0*removed/total < 90)
351 shared->gc_threshold += 5;
353 shared->last_gc = total - removed;
354 shared->shared_table_user++;
355 assert(shared->shared_table_user == 0);
357 shared->condition.notify_all();
363 const double elapsed = start.elapsedSeconds();
364 if (removed > 10000 || elapsed > 0.1)
365 std::cerr <<
" GC " << removed
366 <<
" entries " << std::setprecision(3)
367 << (unit_size * removed / (1<<20)) <<
"MB "
368 << 100.0*removed/total <<
"%"
369 <<
" (" << elapsed <<
" s)\n";
374 template <osl::Player P>
380 assert(state.turn() == P);
382 Dfpn& dfpn = prepareDfpn(P);
386 for (
size_t i=0; i<l.size(); ++i)
389 || l[i].in_check != state.inCheck())
393 ? dfpn.tryProof(state, key, path, l[i].oracle, l[i].id, best_move, last_move)
394 : dfpn.tryProofLight(state, key, path, l[i].oracle, l[i].
id, best_move, last_move);
395 const size_t count = dfpn.nodeCount();
396 local->local_node_count +=
count;
397 shared->addSimulationNodeCount(count);
409 if (node_limit == 0 && num_tried)
411 const ProofDisproof table_pdp = dfpn.hasCheckmateMove(state, key, path, 0, best_move, last_move);
416 boost::mutex::scoped_lock lk(shared->mutex);
418 Shared::disproof_table_t::const_iterator p = shared->disproof_table.find(key);
419 if (p != shared->disproof_table.end()) {
425 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
426 static stat::Ratio migration_success(
"migration_success",
true);
427 bool need_migration =
false;
430 if (node_limit < 80) {
432 local->table_small[P].clear();
434 Dfpn& dfpn_small = prepareDfpnSmall(P);
437 local->local_node_count +=
count;
438 shared->addMainNodeCount(count);
441 boost::mutex::scoped_lock lk(shared->mutex);
443 shared->disproof_table[key].push_front(path);
449 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
450 need_migration =
true;
456 const ProofDisproof pdp = dfpn.hasCheckmateMove(state, key, path, node_limit, best_move, proof_pieces, last_move);
457 const size_t count = dfpn.nodeCount();
458 local->local_node_count +=
count;
459 shared->addMainNodeCount(count);
461 shared->pool[P].addProof(state, key, proof_pieces);
462 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
468 boost::mutex::scoped_lock lk(shared->mutex);
470 shared->disproof_table[key].push_front(path);
482 if (state.turn() ==
BLACK)
483 return findProof<BLACK>(node_limit, state, key, path, best_move, last_move);
485 return findProof<WHITE>(node_limit, state, key, path, best_move, last_move);
493 return findProof(node_limit, state, key, path, best_move, last_move)
494 .isCheckmateSuccess();
498 template <osl::Player P>
499 bool osl::checkmate::
500 DualDfpn::isWinningStateParallel(
int node_limit,
const NumEffectState& state,
509 boost::mutex::scoped_lock lk(shared->mutex);
511 if (! shared->parallel_search)
513 #ifdef DFPN_SHARE_TABLE
514 shared->parallel_search->setTable(&(shared->table[P]));
516 shared->parallel_search->setTable(&(local->table[P]));
519 pdp = shared->parallel_search->hasCheckmateMove
520 (state, key, path, node_limit, best_move, proof_pieces, last_move);
521 count = shared->parallel_search->nodeCount();
523 shared->addMainNodeCount(count);
525 shared->pool[P].addProof(state, key, proof_pieces);
527 shared->disproof_table[key].push_front(path);
534 bool osl::checkmate::
535 DualDfpn::isWinningStateParallel(
int node_limit,
const NumEffectState& state,
536 const HashKey& key,
const PathEncoding& path,
537 Move& best_move, Move last_move)
539 if (state.turn() ==
BLACK)
540 return isWinningStateParallel<BLACK>(node_limit, state, key, path, best_move, last_move);
542 return isWinningStateParallel<WHITE>(node_limit, state, key, path, best_move, last_move);
546 template <osl::Player P>
554 assert(state.turn() == P);
555 Dfpn& dfpn = prepareDfpn(
alt(P));
556 const ProofDisproof pdp = dfpn.hasEscapeMove(state, key, path, node_limit, last_move);
557 const size_t count = dfpn.nodeCount();
558 local->local_node_count +=
count;
559 shared->addMainNodeCount(count);
568 if (state.turn() ==
BLACK)
569 return isLosingState<BLACK>(node_limit, state, key, path, last_move);
571 return isLosingState<WHITE>(node_limit, state, key, path, last_move);
576 const MoveStack&
moves,
577 const SimpleState& state,
Player attack)
581 Dfpn& dfpn = prepareDfpn(attack);
583 for (
int i=0; i<counter.
checkCount(attack); ++i)
585 const HashKey& key = counter.
history().top(i);
586 if (key != counter.
history().top(0))
590 assert(moves.hasLastMove(i+1));
591 if (! moves.hasLastMove(i+1))
593 const Move last_move = moves.lastMove(i+1);
602 shared->blocking_verify[root] =
true;
603 shared->blocking_verify[
alt(root)] =
true;
615 return prepareDfpn(attack).distance(key);
621 #ifdef OSL_USE_RACE_DETECTOR
622 boost::mutex::scoped_lock lk(shared->mutex);
624 return shared->main_node_count;
631 #ifdef OSL_USE_RACE_DETECTOR
632 boost::mutex::scoped_lock lk(shared->mutex);
634 return shared->main_node_count + shared->simulation_count;
640 return shared->
table[attack];
646 (int,
const NumEffectState&,
const HashKey&,
const PathEncoding&,
649 (int,
const NumEffectState&,
const HashKey&,
const PathEncoding&,
653 template bool checkmate::DualDfpn::isLosingState<BLACK>
655 template bool checkmate::DualDfpn::isLosingState<WHITE>
659 template bool checkmate::DualDfpn::isWinningStateParallel<BLACK>
661 template bool checkmate::DualDfpn::isWinningStateParallel<WHITE>