My Project
dualDfpn.cc
Go to the documentation of this file.
1/* dualDfpn.cc
2 */
6#ifdef OSL_DFPN_SMP
8#endif
10#include "osl/stat/average.h"
11#include "osl/centering3x3.h"
13#ifdef OSL_SMP
14# include "osl/misc/lightMutex.h"
15# include <condition_variable>
16#endif
17#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
18# include "osl/stat/ratio.h"
19#endif
21#include "osl/oslConfig.h"
22#include <unordered_map>
23#include <forward_list>
24#include <iostream>
25#include <iomanip>
26
27#define DFPN_SHARE_TABLE
28
29static const int max_oracle_list_size = 2;
30static const size_t local_table_growth_limit = 40000;
32{
33 struct Element
34 {
35 Dfpn::ProofOracle oracle;
36 PieceStand proof_pieces;
37 unsigned int id;
39 Element() : oracle(HashKey(), PieceStand()), id((unsigned int)-1), in_check(false)
40 {
41 }
42 Element(const Dfpn::ProofOracle& o, PieceStand p, size_t i, bool c) : oracle(o), proof_pieces(p), id(i), in_check(c)
43 {
44 }
45 };
46 struct List : FixedCapacityVector<Element, max_oracle_list_size>
47 {
48 void add(const Element& e)
49 {
50 if (size() == capacity())
51 back() = e;
52 else
53 push_back(e);
54 }
55 };
56#ifdef OSL_SMP
57 mutable std::mutex mutex;
58#endif
59 typedef std::unordered_map<HashKey, List, std::hash<HashKey>> table_t;
61 Player defender;
62 void setAttack(Player attack)
63 {
64 defender = alt(attack);
65 }
66 void addProof(const NumEffectState& state, const HashKey& key, PieceStand proof_pieces)
67 {
68 const Dfpn::ProofOracle oracle(key, PieceStand(WHITE, state));
69 const std::pair<HashKey,HashKey> king = makeLargeKey(state);
70#ifdef OSL_SMP
71 std::lock_guard<std::mutex> lk(mutex);;
72#endif
73 const Element e(oracle, proof_pieces, table.size(), state.inCheck());
74 table[king.first].add(e);
75 table[king.second].add(e);
76 }
77 const List probe(const NumEffectState& state) const
78 {
79 const std::pair<HashKey,HashKey> key = makeLargeKey(state);
80#ifdef OSL_SMP
81 std::lock_guard<std::mutex> lk(mutex);;
82#endif
83 table_t::const_iterator p = table.find(key.first);
84 if (p != table.end())
85 return p->second;
86 p = table.find(key.second);
87 if (p != table.end())
88 return p->second;
89 return List();
90 }
91
92 template <Direction DIR>
93 static void addKey(HashKey& key, const SimpleState& state, Square target)
94 {
95 const Offset offset = DirectionTraits<DIR>::blackOffset();
96 target += offset; // 8 近傍全て試すなら手番による符合変換は不要
97 const Piece piece = state.pieceOnBoard(target);
98 HashGenTable::addHashKey(key, target, piece.ptypeO());
99 }
100 template <Direction DIR, Direction DIR2>
101 static void addKey(HashKey& key, const SimpleState& state, Square target)
102 {
103 const Offset offset = DirectionTraits<DIR>::blackOffset()
104 + DirectionTraits<DIR2>::blackOffset();
105 target += offset;
106 const Piece piece = state.pieceOnBoard(target);
107 HashGenTable::addHashKey(key, target, piece.ptypeO());
108 }
109 const HashKey makeKey(const SimpleState& state) const
110 {
111 const Square target_king=state.kingSquare(defender);
112 const Square center = Centering3x3::adjustCenter(target_king);
113 HashKey key;
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);
121 return key;
122 }
123 const std::pair<HashKey,HashKey> makeLargeKey(const SimpleState& state) const
124 {
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);
140 }
141};
142
144{
145 CArray<DfpnTable,2> table;
146 CArray<OraclePool,2> pool;
149 volatile size_t last_gc, gc_threshold;
150 CArray<stat::Average,max_oracle_list_size> proof_by_oracle;
151 CArray<bool,2> blocking_verify;
152#ifdef OSL_SMP
153 std::mutex mutex;
154 std::condition_variable condition;
155 CArray<LightMutex,max_oracle_list_size> proof_by_oracle_mutex;
156#endif
158#ifdef OSL_DFPN_SMP
159 std::unique_ptr<DfpnParallel> parallel_search;
160#endif
161 typedef std::forward_list<PathEncoding> disproof_list_t;
162 typedef std::unordered_map<HashKey, disproof_list_t, std::hash<HashKey>> disproof_table_t;
164
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)
167 {
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);
173 }
175 {
176 showStats();
177 }
179 {
180 if (main_node_count || simulation_count) {
181#ifdef DFPN_DEBUG
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();
190#endif
191 }
192 }
193 void addMainNodeCount(int add)
194 {
195#ifdef OSL_SMP
196 std::lock_guard<std::mutex> lk(mutex);;
197#endif
198 main_node_count += add;
199 }
201 {
202#ifdef OSL_SMP
203 std::lock_guard<std::mutex> lk(mutex);;
204#endif
205 simulation_count += add;
206 }
208 {
209 TableUseLock(const TableUseLock&) = delete;
211
213 explicit TableUseLock(Shared *s) : shared(s)
214 {
215# ifdef OSL_SMP
216 std::unique_lock<std::mutex> lk(shared->mutex);
217 while (shared->shared_table_user < 0) // in gc
218 shared->condition.wait(lk);
219 shared->shared_table_user++;
220# endif
221 }
223 {
224# ifdef OSL_SMP
225 std::lock_guard<std::mutex> lk(shared->mutex);
226 assert(shared->shared_table_user > 0);
227 shared->shared_table_user--;
228 if (shared->shared_table_user == 0 && shared->shared_table_gc_wait)
229 shared->condition.notify_all();
230# endif
231 }
232 };
233};
234
236{
237 Dfpn dfpn;
238#ifndef DFPN_SHARE_TABLE
239 CArray<DfpnTable,2> table;
240#endif
241 CArray<DfpnTable,2> table_small;
243 Local() : local_node_count(0)
244 {
245#ifndef DFPN_SHARE_TABLE
246 table[BLACK].setAttack(BLACK);
247 table[WHITE].setAttack(WHITE);
248#endif
249 table_small[BLACK].setAttack(BLACK);
250 table_small[WHITE].setAttack(WHITE);
251 }
253 {
254#ifdef DFPN_DEBUG
255 std::cerr << "local " << table_small[0].totalSize()
256 << " " << table_small[1].totalSize() << "\n";
257#endif
258 }
259};
260
261/* ------------------------------------------------------------------------- */
262
264DualDfpn::DualDfpn(uint64_t /*limit*/)
265 : shared(new Shared), local(new Local)
266{
267}
268
271 : shared(src.shared), local(new Local)
272{
273}
274
279
282{
283#ifdef DFPN_SHARE_TABLE
284 local->dfpn.setTable(&(shared->table[attack]));
285#else
286 local->dfpn.setTable(&(local->table[attack]));
287#endif
288 local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
289 return local->dfpn;
290}
291
294{
295 local->dfpn.setTable(&(local->table_small[attack]));
296 local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
297 return local->dfpn;
298}
299
301DualDfpn::runGC(bool verbose, size_t memory_use_ratio_1000)
302{
303#ifdef DFPN_SHARE_TABLE
304 const size_t unit_size = (sizeof(HashKey)+sizeof(DfpnRecord)+sizeof(char*)*2);
305 size_t removed = 0;
306 size_t total = shared->table[BLACK].size() + shared->table[WHITE].size();
307 size_t current_use = memory_use_ratio_1000*(OslConfig::memoryUseLimit()/1000);
308 if (total < local_table_growth_limit*8
309 || total*unit_size*64 < OslConfig::memoryUseLimit()
310 || (total*unit_size*3 < current_use
311 && total*unit_size*8 < OslConfig::memoryUseLimit()))
312 return;
313 time_point start = clock::now();
314 {
315 {
316# ifdef OSL_SMP
317 std::unique_lock<std::mutex> lk(shared->mutex);
318# endif
319 total = shared->table[BLACK].size() + shared->table[WHITE].size();
320 if (total < local_table_growth_limit*8
321 || (total*unit_size*3 < current_use
322 && total*unit_size*6 < OslConfig::memoryUseLimit()))
323 return;
324 if (total < shared->last_gc + local_table_growth_limit*2)
325 return;
326 if (shared->shared_table_user > 0
327 && memory_use_ratio_1000 < 650
328 && total < shared->last_gc*2)
329 return;
330 if (shared->shared_table_user < 0 || shared->shared_table_gc_wait > 0)
331 return;
332# ifdef OSL_SMP
333 while (shared->shared_table_user > 0) {
334 ++shared->shared_table_gc_wait;
335 shared->condition.wait(lk);
336 --shared->shared_table_gc_wait;
337 }
338 if (shared->shared_table_user < 0)
339 return;
340# endif
341 shared->shared_table_user--;
342 }
343 removed += shared->table[BLACK].smallTreeGC(shared->gc_threshold);
344 removed += shared->table[WHITE].smallTreeGC(shared->gc_threshold);
345 {
346# ifdef OSL_SMP
347 std::lock_guard<std::mutex> lk(shared->mutex);
348# endif
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;
354 }
355 shared->last_gc = total - removed;
356 shared->shared_table_user++;
357 assert(shared->shared_table_user == 0);
358# ifdef OSL_SMP
359 shared->condition.notify_all();
360# endif
361 }
362 }
363 if (! verbose)
364 return;
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";
372#endif
373}
374
375
376template <osl::Player P>
378DualDfpn::findProof(int node_limit, const NumEffectState& state,
379 const HashKey& key, const PathEncoding& path,
380 Move& best_move, Move last_move)
381{
382 assert(state.turn() == P);
383 // oracle
384 Dfpn& dfpn = prepareDfpn(P);
385 const OraclePool::List l(shared->pool[P].probe(state));
386 const PieceStand attack_stand = (P==BLACK) ? key.blackStand() : PieceStand(WHITE, state);
387 int num_tried = 0;
388 for (size_t i=0; i<l.size(); ++i)
389 {
390 if (! attack_stand.isSuperiorOrEqualTo(l[i].proof_pieces)
391 || l[i].in_check != state.inCheck())
392 continue;
393 ++num_tried;
394 const ProofDisproof pdp = (node_limit > 20)
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);
397 const size_t count = dfpn.nodeCount();
398 local->local_node_count += count;
399 shared->addSimulationNodeCount(count);
400 if (count) {
401#ifdef OSL_SMP
402 SCOPED_LOCK(lk,shared->proof_by_oracle_mutex[i]);
403#endif
404 shared->proof_by_oracle[i].add(pdp.isCheckmateSuccess());
405 }
406 if (pdp.isCheckmateSuccess())
407 assert(best_move.isNormal());
408 if (pdp.isFinal())
409 return pdp;
410 }
411 if (node_limit == 0 && num_tried)
412 return ProofDisproof(1,1); // already tested table
413 const ProofDisproof table_pdp = dfpn.hasCheckmateMove(state, key, path, 0, best_move, last_move);
414 if (table_pdp.isCheckmateSuccess())
415 return table_pdp;
416 {
417#ifdef OSL_SMP
418 std::lock_guard<std::mutex> lk(shared->mutex);
419#endif
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)
423 if (ppath == path)
425 }
426 }
427#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
428 static stat::Ratio migration_success("migration_success", true);
429 bool need_migration = false;
430#endif
431 // local
432 if (node_limit < 80) {
433 if (local->table_small[P].totalSize() >= local_table_growth_limit) {
434 local->table_small[P].clear();
435 }
436 Dfpn& dfpn_small = prepareDfpnSmall(P);
437 const ProofDisproof pdp = dfpn_small.hasCheckmateMove(state, key, path, node_limit, best_move, last_move);
438 const size_t count = dfpn_small.nodeCount();
439 local->local_node_count += count;
440 shared->addMainNodeCount(count);
441 if (pdp.isLoopDetection()) {
442#ifdef OSL_SMP
443 std::lock_guard<std::mutex> lk(shared->mutex);
444#endif
445 shared->disproof_table[key].push_front(path);
446 }
447 if (! pdp.isCheckmateSuccess())
448 return pdp;
449 assert(best_move.isNormal());
450 // fall through if checkmate success (TODO: efficient proof tree migration)
451#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
452 need_migration = true;
453#endif
454 }
455 // main
456 Shared::TableUseLock lk(&*shared);
457 PieceStand proof_pieces;
458 const ProofDisproof pdp = dfpn.hasCheckmateMove(state, key, path, node_limit, best_move, proof_pieces, last_move);
459 const size_t count = dfpn.nodeCount();
460 local->local_node_count += count;
461 shared->addMainNodeCount(count);
462 if (pdp.isCheckmateSuccess())
463 shared->pool[P].addProof(state, key, proof_pieces);
464#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
465 if (need_migration)
466 migration_success.add(pdp.isCheckmateSuccess());
467#endif
468 if (pdp.isLoopDetection()) {
469#ifdef OSL_SMP
470 std::lock_guard<std::mutex> lk(shared->mutex);
471#endif
472 shared->disproof_table[key].push_front(path);
473 }
474 if (pdp.isCheckmateSuccess())
475 assert(best_move.isNormal());
476 return pdp;
477}
478
480DualDfpn::findProof(int node_limit, const NumEffectState& state,
481 const HashKey& key, const PathEncoding& path,
482 Move& best_move, Move last_move)
483{
484 if (state.turn() == BLACK)
485 return findProof<BLACK>(node_limit, state, key, path, best_move, last_move);
486 else
487 return findProof<WHITE>(node_limit, state, key, path, best_move, last_move);
488}
489
491DualDfpn::isWinningState(int node_limit, const NumEffectState& state,
492 const HashKey& key, const PathEncoding& path,
493 Move& best_move, Move last_move)
494{
495 return findProof(node_limit, state, key, path, best_move, last_move)
496 .isCheckmateSuccess();
497}
498
499#ifdef OSL_DFPN_SMP
500template <osl::Player P>
501bool osl::checkmate::
502DualDfpn::isWinningStateParallel(int node_limit, const NumEffectState& state,
503 const HashKey& key, const PathEncoding& path,
504 Move& best_move, Move last_move)
505{
506 PieceStand proof_pieces;
507 size_t count;
508 ProofDisproof pdp;
509 {
510#ifdef OSL_SMP
511 std::lock_guard<std::mutex> lk(shared->mutex);
512#endif
513 if (! shared->parallel_search)
514 shared->parallel_search.reset(new DfpnParallel(std::min(OslConfig::concurrency(), 8)));
515#ifdef DFPN_SHARE_TABLE
516 shared->parallel_search->setTable(&(shared->table[P]));
517#else
518 shared->parallel_search->setTable(&(local->table[P]));
519#endif
520
521 pdp = shared->parallel_search->hasCheckmateMove
522 (state, key, path, node_limit, best_move, proof_pieces, last_move);
523 count = shared->parallel_search->nodeCount();
524 }
525 shared->addMainNodeCount(count);
526 if (pdp.isCheckmateSuccess())
527 shared->pool[P].addProof(state, key, proof_pieces);
528 if (pdp.isLoopDetection()) {
529 shared->disproof_table[key].push_front(path);
530 }
531 if (pdp.isCheckmateSuccess())
532 assert(best_move.isNormal());
533 return pdp.isCheckmateSuccess();
534}
535
536bool osl::checkmate::
537DualDfpn::isWinningStateParallel(int node_limit, const NumEffectState& state,
538 const HashKey& key, const PathEncoding& path,
539 Move& best_move, Move last_move)
540{
541 if (state.turn() == BLACK)
542 return isWinningStateParallel<BLACK>(node_limit, state, key, path, best_move, last_move);
543 else
544 return isWinningStateParallel<WHITE>(node_limit, state, key, path, best_move, last_move);
545}
546#endif
547
548template <osl::Player P>
549bool
551DualDfpn::isLosingState(int node_limit, const NumEffectState& state,
552 const HashKey& key, const PathEncoding& path,
553 Move last_move)
554{
555 Shared::TableUseLock lk(&*shared);
556 assert(state.turn() == P);
557 Dfpn& dfpn = prepareDfpn(alt(P));
558 const ProofDisproof pdp = dfpn.hasEscapeMove(state, key, path, node_limit, last_move);
559 const size_t count = dfpn.nodeCount();
560 local->local_node_count += count;
561 shared->addMainNodeCount(count);
562 return pdp.isCheckmateSuccess();
563}
564
566DualDfpn::isLosingState(int node_limit, const NumEffectState& state,
567 const HashKey& key, const PathEncoding& path,
568 Move last_move)
569{
570 if (state.turn() == BLACK)
571 return isLosingState<BLACK>(node_limit, state, key, path, last_move);
572 else
573 return isLosingState<WHITE>(node_limit, state, key, path, last_move);
574}
575
578 const MoveStack& moves,
579 const SimpleState& state, Player attack)
580{
581 // TODO: 局面表をクリアしてしまうと忘れられる => DualDfpn 内で記憶した方が良い
582 Shared::TableUseLock lk(&*shared);
583 Dfpn& dfpn = prepareDfpn(attack);
584 PieceStand white_stand(WHITE, state);
585 for (int i=0; i<counter.checkCount(attack); ++i)
586 {
587 const HashKey& key = counter.history().top(i);
588 if (key != counter.history().top(0)) // ignore current state
589 {
590 dfpn.setIllegal(key, white_stand);
591 }
592 assert(moves.hasLastMove(i+1)); // oops, different index
593 if (! moves.hasLastMove(i+1))
594 break;
595 const Move last_move = moves.lastMove(i+1);
596 if (last_move.isNormal())
597 white_stand = white_stand.previousStand(WHITE, last_move);
598 }
599}
600
603{
604 shared->blocking_verify[root] = true;
605 shared->blocking_verify[alt(root)] = true; // TODO: set false when issues around proof pieces are corrected
606}
607
609DualDfpn::setVerbose(int /*level*/)
610{
611}
612
614DualDfpn::distance(Player attack, const HashKey& key)
615{
616 Shared::TableUseLock lk(&*shared);
617 return prepareDfpn(attack).distance(key);
618}
619
622{
623#ifdef OSL_USE_RACE_DETECTOR
624 std::lock_guard<std::mutex> lk(shared->mutex);
625#endif
626 return shared->main_node_count;
627 // return shared->table[BLACK].totalSize() + shared->table[WHITE].totalSize();
628}
629
632{
633#ifdef OSL_USE_RACE_DETECTOR
634 std::lock_guard<std::mutex> lk(shared->mutex);
635#endif
636 return shared->main_node_count + shared->simulation_count;
637}
638
640DualDfpn::table(Player attack) const
641{
642 return shared->table[attack];
643}
644
645namespace osl
646{
647 template ProofDisproof checkmate::DualDfpn::findProof<BLACK>
648 (int, const NumEffectState&, const HashKey&, const PathEncoding&,
649 Move&, Move);
650 template ProofDisproof checkmate::DualDfpn::findProof<WHITE>
651 (int, const NumEffectState&, const HashKey&, const PathEncoding&,
652 Move&, Move);
653
654
655 template bool checkmate::DualDfpn::isLosingState<BLACK>
656 (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move);
657 template bool checkmate::DualDfpn::isLosingState<WHITE>
658 (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move);
659
660#ifdef OSL_DFPN_SMP
661 template bool checkmate::DualDfpn::isWinningStateParallel<BLACK>
662 (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move&, Move);
663 template bool checkmate::DualDfpn::isWinningStateParallel<WHITE>
664 (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move&, Move);
665#endif
666}
667
668/* ------------------------------------------------------------------------- */
669// ;;; Local Variables:
670// ;;; mode:c++
671// ;;; c-basic-offset:2
672// ;;; End:
圧縮していない moveの表現 .
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
Player turn() const
詰探索局面表 – 並列でも共有する部分
Definition dfpn.h:30
boost::scoped_array< Table > table
Definition dfpn.h:33
詰探索
Definition dfpn.h:107
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition dfpn.cc:1469
size_t nodeCount() const
Definition dfpn.h:152
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())
Definition dfpn.cc:1401
void setIllegal(const HashKey &key, PieceStand white)
Definition dfpn.cc:1311
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())
Definition dfpn.cc:1393
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)
Definition dfpn.cc:1329
void setTable(DfpnTable *new_table)
Definition dfpn.cc:1296
一般用詰み探索: 先手後手の詰みを別々に管理
Definition dualDfpn.h:29
void runGC(bool verbose=false, size_t memory_use_ratio_1000=0)
Definition dualDfpn.cc:301
bool isLosingState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move last_move=Move::INVALID())
Definition dualDfpn.cc:551
Dfpn & prepareDfpn(Player attack)
Definition dualDfpn.cc:281
void setVerbose(int level=1)
Definition dualDfpn.cc:609
bool isWinningState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move &best_move, Move last_move=Move::INVALID())
詰みを発見.
Definition dualDfpn.h:51
size_t totalNodeCount() const
Definition dualDfpn.cc:631
Dfpn & prepareDfpnSmall(Player attack)
Definition dualDfpn.cc:293
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
Definition dualDfpn.cc:621
int distance(Player attack, const HashKey &key)
Definition dualDfpn.cc:614
void writeRootHistory(const RepetitionCounter &counter, const MoveStack &moves, const SimpleState &state, Player attack)
Definition dualDfpn.cc:577
void setRootPlayer(Player)
Definition dualDfpn.cc:602
const DfpnTable & table(Player) const
Definition dualDfpn.cc:640
DualDfpn(uint64_t ignored=std::numeric_limits< uint64_t >::max())
Definition dualDfpn.cc:264
証明数(proof number)と反証数(disproof number).
static const ProofDisproof LoopDetection()
bool hasLastMove(size_t last=1) const
Definition moveStack.h:27
const Move lastMove(size_t last=1) const
Definition moveStack.h:28
const PieceStand blackStand() const
Definition hashKey.h:64
const HashKey & top(size_t n=0) const
void add(bool success)
Definition ratio.h:22
static const size_t local_table_growth_limit
Definition dualDfpn.cc:30
static const int max_oracle_list_size
Definition dualDfpn.cc:29
#define SCOPED_LOCK(lock, m)
Definition lightMutex.h:176
Player
Definition basic_type.h:8
@ WHITE
Definition basic_type.h:10
@ BLACK
Definition basic_type.h:9
constexpr Player alt(Player player)
Definition basic_type.h:13
static int concurrency()
Definition oslConfig.cc:133
static size_t memoryUseLimit()
Definition oslConfig.h:59
CArray< DfpnTable, 2 > table_small
Definition dualDfpn.cc:241
Element(const Dfpn::ProofOracle &o, PieceStand p, size_t i, bool c)
Definition dualDfpn.cc:42
static void addKey(HashKey &key, const SimpleState &state, Square target)
Definition dualDfpn.cc:101
const List probe(const NumEffectState &state) const
Definition dualDfpn.cc:77
const std::pair< HashKey, HashKey > makeLargeKey(const SimpleState &state) const
Definition dualDfpn.cc:123
std::unordered_map< HashKey, List, std::hash< HashKey > > table_t
Definition dualDfpn.cc:59
void setAttack(Player attack)
Definition dualDfpn.cc:62
const HashKey makeKey(const SimpleState &state) const
Definition dualDfpn.cc:109
static void addKey(HashKey &key, const SimpleState &state, Square target)
Definition dualDfpn.cc:93
void addProof(const NumEffectState &state, const HashKey &key, PieceStand proof_pieces)
Definition dualDfpn.cc:66
TableUseLock(const TableUseLock &)=delete
TableUseLock & operator=(const TableUseLock &)=delete
CArray< OraclePool, 2 > pool
Definition dualDfpn.cc:146
void addSimulationNodeCount(int add)
Definition dualDfpn.cc:200
void addMainNodeCount(int add)
Definition dualDfpn.cc:193
CArray< bool, 2 > blocking_verify
Definition dualDfpn.cc:151
std::forward_list< PathEncoding > disproof_list_t
Definition dualDfpn.cc:161
volatile int shared_table_user
Definition dualDfpn.cc:157
volatile int shared_table_gc_wait
Definition dualDfpn.cc:157
std::unordered_map< HashKey, disproof_list_t, std::hash< HashKey > > disproof_table_t
Definition dualDfpn.cc:162
volatile size_t last_gc
Definition dualDfpn.cc:149
CArray< stat::Average, max_oracle_list_size > proof_by_oracle
Definition dualDfpn.cc:150
disproof_table_t disproof_table
Definition dualDfpn.cc:163
volatile size_t gc_threshold
Definition dualDfpn.cc:149
CArray< DfpnTable, 2 > table
Definition dualDfpn.cc:145