My Project
dualDfpn.cc
Go to the documentation of this file.
1 /* dualDfpn.cc
2  */
4 #include "osl/checkmate/dfpn.h"
6 #ifdef OSL_DFPN_SMP
8 #endif
10 #include "osl/stat/average.h"
11 #include "osl/centering3x3.h"
12 #include "osl/bits/centering5x3.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
20 #include "osl/misc/milliSeconds.h"
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 
29 static const int max_oracle_list_size = 2;
30 static 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;
38  bool in_check;
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  }
178  void showStats()
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 
264 DualDfpn::DualDfpn(uint64_t /*limit*/)
265  : shared(new Shared), local(new Local)
266 {
267 }
268 
270 DualDfpn::DualDfpn(const DualDfpn& src)
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 
301 DualDfpn::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 
376 template <osl::Player P>
378 DualDfpn::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 
480 DualDfpn::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 
491 DualDfpn::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
500 template <osl::Player P>
501 bool osl::checkmate::
502 DualDfpn::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 
536 bool osl::checkmate::
537 DualDfpn::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 
548 template <osl::Player P>
549 bool
551 DualDfpn::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 
566 DualDfpn::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 
609 DualDfpn::setVerbose(int /*level*/)
610 {
611 }
612 
614 DualDfpn::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 
640 DualDfpn::table(Player attack) const
641 {
642  return shared->table[attack];
643 }
644 
645 namespace 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:
dualDfpn.h
checkmate::DualDfpn::Shared::proof_by_oracle
CArray< stat::Average, max_oracle_list_size > proof_by_oracle
Definition: dualDfpn.cc:150
osl::checkmate::DualDfpn::setVerbose
void setVerbose(int level=1)
Definition: dualDfpn.cc:609
osl::checkmate::DfpnTable::table
boost::scoped_array< Table > table
Definition: dfpn.h:32
repetitionCounter.h
checkmate::DualDfpn::Shared::shared_table_gc_wait
volatile int shared_table_gc_wait
Definition: dualDfpn.cc:157
checkmate::DualDfpn::Shared::~Shared
~Shared()
Definition: dualDfpn.cc:174
checkmate::DualDfpn::Shared::TableUseLock
Definition: dualDfpn.cc:208
osl::Centering3x3::adjustCenter
static const Square adjustCenter(Square src)
Definition: centering3x3.h:22
osl::eval::min
int min(Player p, int v1, int v2)
Definition: evalTraits.h:92
osl::FixedCapacityVector< Element, max_oracle_list_size >::size
size_t size() const
Definition: container.h:243
osl::checkmate::ProofDisproof::isCheckmateSuccess
bool isCheckmateSuccess() const
Definition: proofDisproof.h:86
checkmate::DualDfpn::Local::table_small
CArray< DfpnTable, 2 > table_small
Definition: dualDfpn.cc:241
checkmate::DualDfpn::OraclePool::Element::Element
Element()
Definition: dualDfpn.cc:39
ratio.h
checkmate::DualDfpn::OraclePool::List::add
void add(const Element &e)
Definition: dualDfpn.cc:48
osl::WHITE
@ WHITE
Definition: basic_type.h:10
osl::checkmate::DfpnRecord
Definition: dfpnRecord.h:58
centering5x3.h
osl::alt
constexpr Player alt(Player player)
Definition: basic_type.h:13
checkmate::DualDfpn::OraclePool::defender
Player defender
Definition: dualDfpn.cc:61
osl::DirectionTraits::blackOffset
static const Offset blackOffset()
Definition: directionTraits.h:231
checkmate::DualDfpn::Shared::shared_table_user
volatile int shared_table_user
Definition: dualDfpn.cc:157
osl::Centering5x3::adjustCenter
static const Square adjustCenter(Square src)
Definition: centering5x3.h:23
osl::checkmate::Dfpn
詰探索
Definition: dfpn.h:107
osl::checkmate::ProofDisproof::isLoopDetection
bool isLoopDetection() const
Definition: proofDisproof.h:97
checkmate::DualDfpn::Shared::TableUseLock::TableUseLock
TableUseLock(Shared *s)
Definition: dualDfpn.cc:213
PathEncoding
Definition: pathEncoding.cc:12
checkmate::DualDfpn::Shared::main_node_count
size_t main_node_count
Definition: dualDfpn.cc:147
centering3x3.h
osl::FixedCapacityVector< Element, max_oracle_list_size >::capacity
size_t capacity() const
Definition: container.h:245
osl::PieceStand::isSuperiorOrEqualTo
bool isSuperiorOrEqualTo(PieceStand other) const
Definition: bits/pieceStand.h:138
checkmate::DualDfpn::Shared
Definition: dualDfpn.cc:144
osl::Move
圧縮していない moveの表現 .
Definition: basic_type.h:1052
lightMutex.h
checkmate::DualDfpn::OraclePool::makeKey
const HashKey makeKey(const SimpleState &state) const
Definition: dualDfpn.cc:109
osl::checkmate::Dfpn::tryProof
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
osl::checkmate::Dfpn::hasEscapeMove
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition: dfpn.cc:1469
osl::container::MoveStack::lastMove
const Move lastMove(size_t last=1) const
Definition: moveStack.h:28
dfpn.h
osl::checkmate::DfpnTable::setAttack
void setAttack(Player)
Definition: dfpn.cc:942
osl::SimpleState
Definition: simpleState.h:35
osl::hash::HashKey128::blackStand
const PieceStand blackStand() const
Definition: hashKey.h:64
checkmate::DualDfpn::Shared::disproof_table_t
std::unordered_map< HashKey, disproof_list_t, std::hash< HashKey > > disproof_table_t
Definition: dualDfpn.cc:162
checkmate::DualDfpn::Shared::Shared
Shared()
Definition: dualDfpn.cc:165
average.h
osl::checkmate::DualDfpn::isLosingState
bool isLosingState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move last_move=Move::INVALID())
Definition: dualDfpn.cc:551
checkmate::DualDfpn::Shared::table
CArray< DfpnTable, 2 > table
Definition: dualDfpn.cc:145
osl::checkmate::ProofDisproof::isFinal
bool isFinal() const
Definition: proofDisproof.h:88
checkmate::DualDfpn::Shared::disproof_table
disproof_table_t disproof_table
Definition: dualDfpn.cc:163
checkmate::DualDfpn::OraclePool::addProof
void addProof(const NumEffectState &state, const HashKey &key, PieceStand proof_pieces)
Definition: dualDfpn.cc:66
checkmate::DualDfpn::OraclePool::probe
const List probe(const NumEffectState &state) const
Definition: dualDfpn.cc:77
osl::NumEffectState::inCheck
bool inCheck(Player P) const
Pの玉が王手状態
Definition: numEffectState.h:88
checkmate::DualDfpn::OraclePool
Definition: dualDfpn.cc:32
checkmate::DualDfpn::Shared::showStats
void showStats()
Definition: dualDfpn.cc:178
checkmate::DualDfpn::Shared::addMainNodeCount
void addMainNodeCount(int add)
Definition: dualDfpn.cc:193
checkmate::DualDfpn::Local::Local
Local()
Definition: dualDfpn.cc:243
osl::hash::HashKey
Definition: hashKey.h:153
osl::checkmate::DualDfpn::mainNodeCount
size_t mainNodeCount() const
Definition: dualDfpn.cc:621
milliSeconds.h
osl::hash::HashGenTable::addHashKey
static void addHashKey(HashKey &hk, Square sq, PtypeO ptypeo)
Definition: hashKey.h:172
osl::checkmate::ProofDisproof::LoopDetection
static const ProofDisproof LoopDetection()
Definition: proofDisproof.h:78
osl::container::MoveStack
Move のstack.
Definition: moveStack.h:15
checkmate::DualDfpn::Shared::TableUseLock::shared
Shared * shared
Definition: dualDfpn.cc:212
checkmate::DualDfpn::Shared::TableUseLock::~TableUseLock
~TableUseLock()
Definition: dualDfpn.cc:222
checkmate::DualDfpn::OraclePool::setAttack
void setAttack(Player attack)
Definition: dualDfpn.cc:62
checkmate::DualDfpn::OraclePool::table
table_t table
Definition: dualDfpn.cc:60
checkmate::DualDfpn::Shared::blocking_verify
CArray< bool, 2 > blocking_verify
Definition: dualDfpn.cc:151
osl::checkmate::DualDfpn::isWinningState
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
osl::checkmate::DualDfpn::prepareDfpnSmall
Dfpn & prepareDfpnSmall(Player attack)
Definition: dualDfpn.cc:293
checkmate::DualDfpn::OraclePool::Element::in_check
bool in_check
Definition: dualDfpn.cc:38
osl::stat::Ratio
Definition: ratio.h:13
osl::OslConfig::concurrency
static int concurrency()
Definition: oslConfig.cc:133
osl::checkmate::Dfpn::setTable
void setTable(DfpnTable *new_table)
Definition: dfpn.cc:1296
osl::PieceStand
片方の手番の持駒の枚数を記録するクラス.
Definition: bits/pieceStand.h:38
osl::CArray::fill
void fill(const T_simple &value=T_simple())
Definition: container.h:67
checkmate::DualDfpn::OraclePool::Element
Definition: dualDfpn.cc:34
checkmate::DualDfpn::OraclePool::addKey
static void addKey(HashKey &key, const SimpleState &state, Square target)
Definition: dualDfpn.cc:93
checkmate::DualDfpn::Shared::gc_threshold
volatile size_t gc_threshold
Definition: dualDfpn.cc:149
osl::RepetitionCounter::history
const HashKeyStack & history() const
Definition: repetitionCounter.h:95
checkmate::DualDfpn::Shared::pool
CArray< OraclePool, 2 > pool
Definition: dualDfpn.cc:146
osl::checkmate::Dfpn::hasCheckmateMove
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
oslConfig.h
osl::Move::isNormal
bool isNormal() const
INVALID でも PASS でもない.
Definition: basic_type.h:1088
checkmate::DualDfpn::OraclePool::Element::Element
Element(const Dfpn::ProofOracle &o, PieceStand p, size_t i, bool c)
Definition: dualDfpn.cc:42
osl::hash::HashKeyStack::top
const HashKey & top(size_t n=0) const
Definition: hashKeyStack.h:23
osl::OslConfig::memoryUseLimit
static size_t memoryUseLimit()
Definition: oslConfig.h:59
osl::NumEffectState
利きを持つ局面
Definition: numEffectState.h:34
osl::PieceStand::previousStand
const PieceStand previousStand(Player pl, Move move) const
Definition: bits/pieceStand.h:226
checkmate::DualDfpn::Local::local_node_count
size_t local_node_count
Definition: dualDfpn.cc:242
osl::FixedCapacityVector< Element, max_oracle_list_size >::back
Element & back()
Definition: container.h:202
checkmate::DualDfpn::Shared::simulation_count
size_t simulation_count
Definition: dualDfpn.cc:148
dfpnRecord.h
osl::checkmate::DualDfpn::~DualDfpn
~DualDfpn()
Definition: dualDfpn.cc:276
checkmate::DualDfpn::OraclePool::Element::proof_pieces
PieceStand proof_pieces
Definition: dualDfpn.cc:36
osl::checkmate::DualDfpn::table
const DfpnTable & table(Player) const
Definition: dualDfpn.cc:640
dfpnParallel.h
local_table_growth_limit
static const size_t local_table_growth_limit
Definition: dualDfpn.cc:30
osl::BLACK
@ BLACK
Definition: basic_type.h:9
osl::checkmate::DualDfpn
一般用詰み探索: 先手後手の詰みを別々に管理
Definition: dualDfpn.h:29
osl::RepetitionCounter::checkCount
int checkCount(Player attack) const
Definition: repetitionCounter.h:91
checkmate::DualDfpn::Shared::TableUseLock::TableUseLock
TableUseLock(const TableUseLock &)=delete
checkmate::DualDfpn::OraclePool::List
Definition: dualDfpn.cc:47
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:17
checkmate::DualDfpn::Shared::last_gc
volatile size_t last_gc
Definition: dualDfpn.cc:149
max_oracle_list_size
static const int max_oracle_list_size
Definition: dualDfpn.cc:29
checkmate::DualDfpn::OraclePool::table_t
std::unordered_map< HashKey, List, std::hash< HashKey > > table_t
Definition: dualDfpn.cc:59
osl::checkmate::DualDfpn::runGC
void runGC(bool verbose=false, size_t memory_use_ratio_1000=0)
Definition: dualDfpn.cc:301
osl::checkmate::DualDfpn::setRootPlayer
void setRootPlayer(Player)
Definition: dualDfpn.cc:602
osl::checkmate::Dfpn::tryProofLight
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
osl::checkmate::DualDfpn::writeRootHistory
void writeRootHistory(const RepetitionCounter &counter, const MoveStack &moves, const SimpleState &state, Player attack)
Definition: dualDfpn.cc:577
osl::checkmate::DfpnTable
詰探索局面表 – 並列でも共有する部分
Definition: dfpn.h:30
osl::SimpleState::turn
Player turn() const
Definition: simpleState.h:220
osl::misc::time_point
std::chrono::time_point< clock > time_point
Definition: milliSeconds.h:18
osl::Player
Player
Definition: basic_type.h:8
osl::RepetitionCounter
千日手の検出.
Definition: repetitionCounter.h:21
osl::checkmate::DualDfpn::DualDfpn
DualDfpn(uint64_t ignored=std::numeric_limits< uint64_t >::max())
Definition: dualDfpn.cc:264
checkmate::DualDfpn::Shared::disproof_list_t
std::forward_list< PathEncoding > disproof_list_t
Definition: dualDfpn.cc:161
osl::checkmate::DualDfpn::findProof
ProofDisproof findProof(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move &best_move, Move last_move=Move::INVALID())
checkmate::DualDfpn::OraclePool::addKey
static void addKey(HashKey &key, const SimpleState &state, Square target)
Definition: dualDfpn.cc:101
checkmate::DualDfpn::OraclePool::Element::oracle
Dfpn::ProofOracle oracle
Definition: dualDfpn.cc:35
osl::container::MoveStack::hasLastMove
bool hasLastMove(size_t last=1) const
Definition: moveStack.h:27
SCOPED_LOCK
#define SCOPED_LOCK(lock, m)
Definition: lightMutex.h:176
checkmate::DualDfpn::Local
Definition: dualDfpn.cc:236
checkmate::DualDfpn::OraclePool::makeLargeKey
const std::pair< HashKey, HashKey > makeLargeKey(const SimpleState &state) const
Definition: dualDfpn.cc:123
osl::stat::Ratio::add
void add(bool success)
Definition: ratio.h:22
checkmate::DualDfpn::Local::~Local
~Local()
Definition: dualDfpn.cc:252
checkmate::DualDfpn::Local::dfpn
Dfpn dfpn
Definition: dualDfpn.cc:237
osl::checkmate::DualDfpn::totalNodeCount
size_t totalNodeCount() const
Definition: dualDfpn.cc:631
checkmate::DualDfpn::Shared::addSimulationNodeCount
void addSimulationNodeCount(int add)
Definition: dualDfpn.cc:200
osl::checkmate::DualDfpn::distance
int distance(Player attack, const HashKey &key)
Definition: dualDfpn.cc:614
osl::checkmate::Dfpn::nodeCount
size_t nodeCount() const
Definition: dfpn.h:152
osl::FixedCapacityVector< Element, max_oracle_list_size >::push_back
void push_back(const Element &e)
Definition: container.h:204
checkmate::DualDfpn::Shared::TableUseLock::operator=
TableUseLock & operator=(const TableUseLock &)=delete
osl::checkmate::Dfpn::setIllegal
void setIllegal(const HashKey &key, PieceStand white)
Definition: dfpn.cc:1311
osl::checkmate::DualDfpn::prepareDfpn
Dfpn & prepareDfpn(Player attack)
Definition: dualDfpn.cc:281
checkmate::DualDfpn::OraclePool::Element::id
unsigned int id
Definition: dualDfpn.cc:37
osl
Definition: additionalEffect.h:6
osl::misc::elapsedSeconds
double elapsedSeconds(time_point start)
Definition: milliSeconds.h:29