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
39 Element() : oracle(HashKey(), PieceStand()), id((unsigned int)-1), in_check(false)
42 Element(
const Dfpn::ProofOracle& o, PieceStand p,
size_t i,
bool c) : oracle(o), proof_pieces(p), id(i), in_check(c)
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;
64 defender = alt(attack);
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)
95 const Offset offset = DirectionTraits<DIR>::blackOffset();
97 const Piece piece = state.pieceOnBoard(target);
98 HashGenTable::addHashKey(key, target, piece.ptypeO());
100 template <Direction DIR, Direction DIR2>
101 static void addKey(HashKey& key,
const SimpleState& state, Square target)
103 const Offset offset = DirectionTraits<DIR>::blackOffset()
104 + DirectionTraits<DIR2>::blackOffset();
106 const Piece piece = state.pieceOnBoard(target);
107 HashGenTable::addHashKey(key, target, piece.ptypeO());
109 const HashKey
makeKey(
const SimpleState& state)
const
111 const Square target_king=state.kingSquare(defender);
112 const Square center = Centering3x3::adjustCenter(target_king);
114 HashGenTable::addHashKey(key, center,
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);
127 const Square center = Centering5x3::adjustCenter(target_king);
128 HashGenTable::addHashKey(key_large, center,
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;
165 Shared() : main_node_count(0), simulation_count(0), last_gc(0), gc_threshold(10),
166 shared_table_user(0), shared_table_gc_wait(0)
168 table[BLACK].setAttack(BLACK);
169 table[WHITE].setAttack(WHITE);
170 pool[BLACK].setAttack(BLACK);
171 pool[WHITE].setAttack(WHITE);
172 blocking_verify.fill(
true);
180 if (main_node_count || simulation_count) {
182 std::cerr <<
"shared " << main_node_count <<
" " << simulation_count <<
"\n";
183 for (stat::Average& a: proof_by_oracle)
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);;
198 main_node_count += add;
203 std::lock_guard<std::mutex> lk(mutex);;
205 simulation_count += add;
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
246 table[BLACK].setAttack(BLACK);
247 table[WHITE].setAttack(WHITE);
249 table_small[BLACK].setAttack(BLACK);
250 table_small[WHITE].setAttack(WHITE);
255 std::cerr <<
"local " << table_small[0].totalSize()
256 <<
" " << table_small[1].totalSize() <<
"\n";
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
313 time_point start = clock::now();
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();
365 const double elapsed = elapsedSeconds(start);
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";
376template <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();
500template <osl::Player P>
502DualDfpn::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);
537DualDfpn::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);
548template <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>
void push_back(const Element &e)
bool isNormal() const
INVALID でも PASS でもない.
bool inCheck(Player P) const
Pの玉が王手状態
bool isSuperiorOrEqualTo(PieceStand other) const
const PieceStand previousStand(Player pl, Move move) const
int checkCount(Player attack) const
const HashKeyStack & history() const
boost::scoped_array< Table > table
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
const ProofDisproof tryProofLight(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move=Move::INVALID())
void setIllegal(const HashKey &key, PieceStand white)
const ProofDisproof tryProof(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move=Move::INVALID())
const ProofDisproof hasCheckmateMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move &best_move, Move last_move=Move::INVALID(), std::vector< Move > *pv=0)
void setTable(DfpnTable *new_table)
void runGC(bool verbose=false, size_t memory_use_ratio_1000=0)
bool isLosingState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move last_move=Move::INVALID())
Dfpn & prepareDfpn(Player attack)
void setVerbose(int level=1)
bool isWinningState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move &best_move, Move last_move=Move::INVALID())
詰みを発見.
size_t totalNodeCount() const
Dfpn & prepareDfpnSmall(Player attack)
ProofDisproof findProof(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move &best_move, Move last_move=Move::INVALID())
size_t mainNodeCount() const
int distance(Player attack, const HashKey &key)
void writeRootHistory(const RepetitionCounter &counter, const MoveStack &moves, const SimpleState &state, Player attack)
void setRootPlayer(Player)
const DfpnTable & table(Player) const
DualDfpn(uint64_t ignored=std::numeric_limits< uint64_t >::max())
証明数(proof number)と反証数(disproof number).
static const ProofDisproof LoopDetection()
bool isCheckmateSuccess() const
bool isLoopDetection() const
bool hasLastMove(size_t last=1) const
const Move lastMove(size_t last=1) const
const PieceStand blackStand() const
const HashKey & top(size_t n=0) const
static const size_t local_table_growth_limit
static const int max_oracle_list_size
#define SCOPED_LOCK(lock, m)
constexpr Player alt(Player player)
static size_t memoryUseLimit()
CArray< DfpnTable, 2 > table_small
Element(const Dfpn::ProofOracle &o, PieceStand p, size_t i, bool c)
void add(const Element &e)
static void addKey(HashKey &key, const SimpleState &state, Square target)
const List probe(const NumEffectState &state) const
const std::pair< HashKey, HashKey > makeLargeKey(const SimpleState &state) const
std::unordered_map< HashKey, List, std::hash< HashKey > > table_t
void setAttack(Player attack)
const HashKey makeKey(const SimpleState &state) const
static void addKey(HashKey &key, const SimpleState &state, Square target)
void addProof(const NumEffectState &state, const HashKey &key, PieceStand proof_pieces)
TableUseLock(const TableUseLock &)=delete
TableUseLock & operator=(const TableUseLock &)=delete
CArray< OraclePool, 2 > pool
void addSimulationNodeCount(int add)
void addMainNodeCount(int add)
CArray< bool, 2 > blocking_verify
std::forward_list< PathEncoding > disproof_list_t
volatile int shared_table_user
volatile int shared_table_gc_wait
std::unordered_map< HashKey, disproof_list_t, std::hash< HashKey > > disproof_table_t
CArray< stat::Average, max_oracle_list_size > proof_by_oracle
disproof_table_t disproof_table
volatile size_t gc_threshold
CArray< DfpnTable, 2 > table