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;
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()
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
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 {
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);
220# endif
221 }
223 {
224# ifdef OSL_SMP
225 std::lock_guard<std::mutex> lk(shared->mutex);
226 assert(shared->shared_table_user > 0);
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;
244 {
245#ifndef DFPN_SHARE_TABLE
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
277{
278}
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:
void fill(const T_simple &value=T_simple())
Definition: container.h:67
圧縮していない moveの表現 .
Definition: basic_type.h:1052
bool isNormal() const
INVALID でも PASS でもない.
Definition: basic_type.h:1088
利きを持つ局面
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: simpleState.h:220
詰探索局面表 – 並列でも共有する部分
Definition: dfpn.h:30
boost::scoped_array< Table > table
Definition: dfpn.h:33
void setAttack(Player)
Definition: dfpn.cc:942
詰探索
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).
Definition: proofDisproof.h:17
static const ProofDisproof LoopDetection()
Definition: proofDisproof.h:78
Move のstack.
Definition: moveStack.h:15
bool hasLastMove(size_t last=1) const
Definition: moveStack.h:27
const Move lastMove(size_t last=1) const
Definition: moveStack.h:28
static void addHashKey(HashKey &hk, Square sq, PtypeO ptypeo)
Definition: hashKey.h:172
const PieceStand blackStand() const
Definition: hashKey.h:64
const HashKey & top(size_t n=0) const
Definition: hashKeyStack.h:23
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
int min(Player p, int v1, int v2)
Definition: evalTraits.h:92
double elapsedSeconds(time_point start)
Definition: milliSeconds.h:29
std::chrono::time_point< clock > time_point
Definition: milliSeconds.h:18
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 const Square adjustCenter(Square src)
Definition: centering3x3.h:22
static const Square adjustCenter(Square src)
Definition: centering5x3.h:23
static const Offset blackOffset()
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
void add(const Element &e)
Definition: dualDfpn.cc:48
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