My Project
dfpn.cc
Go to the documentation of this file.
1 /* dfpn.cc
2  */
3 #include "osl/checkmate/dfpn.h"
20 #include "osl/csa.h"
21 
22 #include "osl/stat/ratio.h"
24 #include "osl/bits/align16New.h"
25 #include "osl/oslConfig.h"
26 #include <tuple>
27 #include <unordered_map>
28 #include <vector>
29 #include <forward_list>
30 #include <iostream>
31 #include <iomanip>
32 #include <bitset>
33 
34 // see dfpnRecord.h for #defined NAGAI_DAG_TEST
35 
36 #define GRAND_PARENT_SIMULATION
37 #define GRAND_PARENT_DELAY
38 
39 #define INITIAL_DOMINANCE
41 #define ROOT_PROOF_TOL 65536ul*1024
43 #define ROOT_DISPROOF_TOL 65536ul*1024
44 // #define DELAY_UPWARD
45 // #define NO_IMMEDIATE_CHECKMATE
46 #define CHECKMATE_D2
47 // #define CHECKMATE_A3
48 #define PROOF_AVERAGE
49 #define DISPROOF_AVERAGE
50 
51 #define KAKINOKI_FALSE_BRANCH_SEARCH
52 #define IGNORE_MONSTER_CHILD
53 #define KISHIMOTO_WIDEN_THRESHOLD
54 #define ADHOC_SUM_RESTRICTION
55 #define AGGRESSIVE_FIND_DAG
56 #define AGGRESSIVE_FIND_DAG2
57 #define CHECKMATE_A3_GOLD
58 #define CHECKMATE_A3_SIMULLATION
59 
60 // 何番目に生成された指手が解決済みかを記録。生成順序は駒番号に依存するので注意。
61 #define MEMORIZE_SOLVED_IN_BITSET
62 
63 // #define DFPN_STAT
64 
65 static const int UpwardWeight = 2, SacrificeBlockCount = 0, LongDropCount = 1;
66 #ifdef MINIMAL
67 static const int MaxDagTraceDepth = 64;
68 #else
69 static const int MaxDagTraceDepth = 1600;
70 #endif
71 static const unsigned int NoPromoeIgnoreProofThreshold = 100;
72 static const unsigned int NoPromoeIgnoreDisproofThreshold = 200;
73 static const unsigned int IgnoreUpwardProofThreshold = 100;
74 static const unsigned int IgnoreUpwardDisproofThreshold = 100;
75 #ifdef MEMORIZE_SOLVED_IN_BITSET
76 static const unsigned int InitialDominanceProofMax = 35;
77 #else
78 static const unsigned int InitialDominanceProofMax = 20;
79 #endif
80 static const unsigned int InitialDominanceDisproofMax = 110;
81 static const unsigned int DagFindThreshold = 64;
82 static const unsigned int DagFindThreshold2 = 256;
83 static const int EnableGCDepth = 512;
84 static const int AdHocSumScale = 128;
86 const int ProofSimulationTolerance = 1024;
87 
88 // #define DFPN_DEBUG
89 
90 #ifndef NDEBUG
91 static size_t timer = 0;
92 const size_t debug_time_start = 3851080;
93 #endif
94 /* ------------------------------------------------------------------------- */
95 
96 namespace osl
97 {
98  namespace checkmate
99  {
100  inline int log2(uint32_t n)
101  {
102  return (n <= 1) ? 1 : 32 - __builtin_clz(n);
103  }
104  inline int slow_increase(uint32_t n)
105  {
106  return log2(n);
107  }
108 #ifdef DFPN_DEBUG
109  struct NodeIDTable : public std::unordered_map<HashKey, int, std::hash<HashKey>>
110  {
111  size_t cur;
112  NodeIDTable() : cur(0) {}
113  int id(const HashKey& key)
114  {
115  int& ret = (*this)[key];
116  if (ret == 0)
117  ret = ++cur;
118  return ret;
119  }
120  } node_id_table;
121  CArray<int,3> debug_node = {{
122  }};
124  struct NodeCountTable : public std::unordered_map<int, std::pair<int,std::vector<Move> > >
125  {
126  typedef std::pair<int,std::vector<Move> > pair_t;
127  ~NodeCountTable()
128  {
129  std::cerr << "timer " << timer << "\n";
130  vector<std::pair<int,int> > all;
131  all.reserve(size());
132  for (const auto& v: *this)
133  all.push_back(std::make_pair(-v.second.first, v.first));
134  std::sort(all.begin(), all.end());
135  for (size_t i=0; i<std::min((size_t)10, size()); ++i){
136  std::cerr << "freq " << -all[i].first << " id " << std::setw(5) << all[i].second << ' ';
137  for (Move m: (*this)[all[i].second].second)
138  std::cerr << record::csa::show(m);
139  std::cerr << "\n";
140  }
141  }
142  } node_count_table;
143 #endif
144 
145  struct SimpleTwinList : std::forward_list<PathEncoding>
146  {
147  };
148 
150  {
151  static const int MaxDistance = 1024*128;
154  int distance;
155  bool visiting;
156  size_t node_count;
158  : distance(MaxDistance), visiting(false), node_count(0)
159  {
160  }
161  };
162  template <bool Enabled=true>
164  {
165  DfpnVisitLock(const DfpnVisitLock&) = delete;
167 
170  {
171  if (! Enabled) return;
172  assert(! record->visiting);
173  record->visiting = true;
174  }
176  {
177  if (! Enabled) return;
178  assert(record->visiting);
179  record->visiting = false;
180  }
181  };
183  struct DfpnPathList : public std::forward_list<std::pair<PieceStand, DfpnPathRecord>>
184  {
185  typedef std::forward_list<std::pair<PieceStand, DfpnPathRecord> > list_t;
186  private:
187  template <Player Attack>
188  iterator find(PieceStand black, LoopToDominance& loop)
189  {
190  loop = NoLoop;
191  iterator ret = end();
192  for (iterator p=begin(); p!=end(); ++p) {
193  if (p->first == black) {
194  assert(p->second.distance != DfpnPathRecord::MaxDistance);
195  ret = p;
196  if (loop || p->second.visiting) break;
197  }
198  if (! p->second.visiting)
199  continue;
200  if (p->first.isSuperiorOrEqualTo(black)) {
201  if (Attack == BLACK) {
202  loop = BadAttackLoop;
203  if (ret != end()) break;
204  }
205  }
206  else if (black.isSuperiorOrEqualTo(p->first)) {
207  if (Attack == WHITE) {
208  loop = BadAttackLoop;
209  if (ret != end()) break;
210  }
211  }
212  }
213  return ret;
214  }
215  public:
216  template <Player Attack>
218  size_t& size)
219  {
220  iterator ret = find<Attack>(black, loop);
221  if (ret != end()) {
222  ret->second.distance = std::min(depth, ret->second.distance);
223  return &(ret->second);
224  }
225  ++size;
226  push_front(std::make_pair(black, DfpnPathRecord()));
227  DfpnPathRecord *record = &(begin()->second);
228  assert(record->distance == DfpnPathRecord::MaxDistance);
229  record->distance = depth;
230  return record;
231  }
232  const DfpnPathRecord *probe(PieceStand black) const
233  {
234  for (const auto& v: *this) {
235  if (v.first == black)
236  return &(v.second);
237  }
238  return 0;
239  }
240  static bool precious(const DfpnPathRecord& record, size_t threshold)
241  {
242  return record.visiting
243  || record.node_count > threshold
244  || (! record.twin_list.empty() && record.node_count > threshold - 10);
245  }
246  size_t runGC(size_t threshold)
247  {
248  size_t removed = 0;
249  list_t::iterator p=begin();
250  while (p!=end()) {
251  list_t::iterator q=p;
252  ++q;
253  if (q == end())
254  break;
255  if (! precious(q->second, threshold)) {
256  erase_after(p);
257  ++removed;
258  continue;
259  }
260  p = q;
261  }
262  if (! empty() && ! precious(begin()->second, threshold)) {
263  pop_front(); // erase(begin());
264  ++removed;
265  }
266  return removed;
267  }
268  };
270  {
271  typedef std::unordered_map<BoardKey, DfpnPathList, std::hash<BoardKey>> table_t;
273  size_t total_size;
274  size_t gc_threshold;
275  public:
277  {
278  }
279  template <Player Attack>
280  DfpnPathRecord *allocate(const HashKey& key, int depth, LoopToDominance& loop)
281  {
282  DfpnPathList& l = table[key.boardKey()];
283  return l.allocate<Attack>(key.blackStand(), depth, loop,
284  total_size);
285  }
286  const DfpnPathRecord *probe(const HashKey& key) const
287  {
288  table_t::const_iterator p = table.find(key.boardKey());
289  if (p == table.end())
290  return 0;
291  return p->second.probe(key.blackStand());
292  }
293  void clear() { table.clear(); }
294  size_t runGC()
295  {
296  size_t removed = 0;
297  for (table_t::iterator p=table.begin(); p!=table.end(); ++p)
298  removed += p->second.runGC(gc_threshold);
299  total_size -= removed;
300  gc_threshold += 15;
301  static double memory_threshold = 0.8;
302  double memory = OslConfig::memoryUseRatio();
303  if (memory > memory_threshold) {
304  gc_threshold += 15;
305  memory_threshold += 1.0/128;
306  }
307  return removed;
308  }
309  size_t size() const { return total_size; }
310  void rehash(size_t bucket_size) { table.rehash(bucket_size); }
311  };
312 
313  int attackProofCost(Player attacker, const NumEffectState& state, Move move)
314  {
315  int proof = 0;
316  if (! move.isCapture())
317  {
318  const Square from=move.from(), to=move.to();
319  const int a = (state.countEffect(attacker,to)
320  + (from.isPieceStand() ? 1 : 0));
321  int d = state.countEffect(alt(attacker),to);
322  if (a <= d)
323  {
324  const Ptype ptype = move.ptype();
325  proof = PieceCost::attack_sacrifice_cost[ptype];
326  if ((d >= 2) && (a == d)) // 追加利きとか利きがずれたりとか
327  proof /= 2;
328  }
329  }
330  return proof;
331  }
332  }
333 }
334 
335 /* ------------------------------------------------------------------------- */
337 {
338  // input
344  // work or output
347 };
348 
350 {
356  size_t visit_time;
357 
358  const PieceStand nextWhiteStand(Player P, Move move) const
359  {
360  assert(move.player() == P);
361  return (P == WHITE) ? white_stand.nextStand(P, move) : white_stand;
362  }
363  void clear()
364  {
365  moves.clear();
366  proof_cost.clear();
367  children.clear();
368  children_path.clear();
369  }
370  void allocate(int n)
371  {
372  while (n--) {
374  children.push_back(DfpnRecord());
375  children_path.push_back(0);
376  }
377  }
379  {
380  assert(! (record.proof_disproof.isFinal()
383  path_record->twin_list.push_front(path);
384  }
385  const PathEncoding newPath(int c) const
386  {
387  PathEncoding n = path;
388  n.pushMove(moves[c]);
389  return n;
390  }
391  bool isLoop(int c) const
392  {
393  if (! children_path[c] || children[c].proof_disproof.isFinal())
394  return false;
395  if (children_path[c]->visiting)
396  return true;
397  const PathEncoding p = newPath(c);
398  const SimpleTwinList& tl = children_path[c]->twin_list;
399  return std::find(tl.begin(), tl.end(), p) != tl.end();
400  }
401  void setCheckmateAttack(Player attack, int best_i)
402  {
403  DfpnRecord& child = children[best_i];
404  assert(child.proof_disproof.isCheckmateSuccess());
406  record.best_move = moves[best_i];
407  const PieceStand proof_pieces
409  record.stands[attack]);
410  record.setProofPieces(proof_pieces);
411  }
413  {
414  DfpnRecord& child = children[best_i];
415  assert(child.proof_disproof.isCheckmateFail());
416  assert(! child.proof_disproof.isLoopDetection());
418  record.best_move = moves[best_i];
419  const PieceStand disproof_pieces
421  record.stands[alt(attack)]);
422  record.setDisproofPieces(disproof_pieces);
423  }
425  {
426  assert(moves.size());
428  record.proof_disproof = ProofDisproof::Checkmate(); // prevent backup of NoEscape
430  const Player defender = alt(attack);
431  if (! state.inUnblockableCheck(defender))
433  result);
434  record.setProofPieces(result);
435  }
437  {
438  assert(moves.size());
443  result);
444  record.setDisproofPieces(result);
445  }
447  {
448  assert(children[i].proof_disproof.isCheckmateSuccess());
449 #ifdef MEMORIZE_SOLVED_IN_BITSET
450  record.solved |= (1ull<<i);
451 #endif
452  record.min_pdp = std::min(record.min_pdp, children[i].proof_disproof.disproof());
454  = record.proof_pieces_candidate.max(children[i].proofPieces());
455  }
457  {
458  assert(children[i].proof_disproof.isCheckmateFail());
459 #ifdef MEMORIZE_SOLVED_IN_BITSET
460  record.solved |= (1ull<<i);
461 #endif
462  record.min_pdp = std::min(record.min_pdp, children[i].proof_disproof.proof());
464  = record.proof_pieces_candidate.max(children[i].disproofPieces());
465  }
466 };
467 
469 #if OSL_WORDSIZE == 32
470  : public misc::Align16New
471 #endif
472 {
474  int depth;
475 #ifdef MINIMAL
476  enum { MinimalMaxDepth = 256 };
477  Node node[MinimalMaxDepth];
478 #else
479  boost::scoped_array<Node> node;
480 #endif
481  const int MaxDepth;
482  Tree(int
483 #ifndef MINIMAL
484  max_depth
485 #endif
486  ) : state(SimpleState(HIRATE)),
487  MaxDepth(
488 #ifndef MINIMAL
489  max_depth
490 #else
491  MinimalMaxDepth
492 #endif
493  )
494  {
495 #ifndef MINIMAL
496  node.reset(new Node[max_depth]);
497 #endif
498  }
499  bool inCheck(Player P) const
500  {
501  return state.inCheck(P);
502  }
503  const Piece king(Player P) const { return state.kingPiece(P); }
504  void newVisit(Player P, Move move, const HashKey& next_hash)
505  {
506  assert(P == move.player());
507  const Node& node = this->node[depth];
508  assert(next_hash == node.hash_key.newHashWithMove(move));
509  Node& next = this->node[depth+1];
510  next.moved = move;
511  next.white_stand = node.nextWhiteStand(P, move);
512  next.path = node.path;
513  next.clear();
514  next.hash_key = next_hash;
515  }
516  void setNoCheckmateChildInAttack(size_t best_i)
517  {
518  Node &node = this->node[depth];
519  node.setNoCheckmateChildInAttack(best_i);
520  }
522  {
523  Node &node = this->node[depth];
524  node.setNoCheckmateDefense(attack, best_i);
525  }
526  void dump(int lines, int depth=0) const
527  {
528 #ifndef NDEBUG
529  if (depth == 0)
530  depth = this->depth;
531  for (int i=0; i<=depth; ++i) {
532  std::cerr << "history " << i << " " << node[i].moved << " ";
533  node[i].hash_key.dumpContentsCerr();
534  std::cerr << "\n";
535  }
536  const int my_distance = node[depth].path_record ? node[depth].path_record->distance : -1;
537  const Node &node = this->node[depth];
538  std::cerr << "time " << node.visit_time << " (" << timer << ") here " << lines << "\n" << state;
539  std::cerr << " false-branch? " << (bool)node.record.false_branch << "\n";
541  std::cerr << " solved " << std::bitset<32>(node.record.solved) << "\n";
542 #endif
543  std::cerr << " dags " << std::bitset<32>(node.record.solved) << "\n";
544  std::cerr << " last_to " << node.record.last_to
545  << " threshold " << node.threshold
546  << " my_distance " << my_distance << "\n";
547  for (size_t i=0; i<node.moves.size(); ++i) {
548  std::cerr << " " << i << " " << node.moves[i]
549  << " " << node.children[i].proof_disproof
550  << " " << (int)node.proof_cost[i]
551  << " " << node.children[i].best_move
552  << " depth " << (node.children_path[i] ? node.children_path[i]->distance : -1)
553  << " count " << node.children[i].node_count
554  << "\n";
555  }
556  std::cerr << node.record.proof_disproof << " " << node.record.best_move << "\n";
557  std::cerr << "path " << node.path << " twins ";
558  if (node.path_record) {
559  for (const auto& path: node.path_record->twin_list)
560  std::cerr << path << " ";
561  }
562  std::cerr << "\n";
563 #endif
564  }
565 #ifdef DFPN_DEBUG
566  void showPath(const char *message, size_t table_size) const
567  {
568  std::cerr << message << " depth " << depth << " node " << node_id_table.id(node[depth].hash_key)
569  << " time " << timer << " table " << table_size << ' ';
570  for (int i=0; i<=depth; ++i)
571  std::cerr << record::csa::show(node[i].moved);
572  std::cerr << "\n";
573  }
574  struct Logging
575  {
576  const Tree *tree;
577  const DfpnTable *table;
578  const size_t old_table_size;
579  Logging(Tree *tr, DfpnTable *tb, const char *message)
580  : tree(tr), table(tb), old_table_size(table->size())
581  {
582  if (timer < debug_time_start)
583  return;
584  tree->showPath(message, old_table_size);
585  }
586  ~Logging()
587  {
588  if (timer < debug_time_start)
589  return;
590  const Node& node = tree->node[tree->depth];
591  const int id = node_id_table.id(node.hash_key);
592  std::cerr << " node " << id << " " << node.threshold
593  << " " << node.record.proof_disproof << "\n";
594  if (std::find(debug_node.begin(), debug_node.end(), id)
595  != debug_node.end() && timer > debug_time_start)
596  tree->dump(__LINE__);
597  if (table->size() == old_table_size)
598  countImmediateReturns(id);
599  }
600  void countImmediateReturns(int id)
601  {
602  NodeCountTable::pair_t& p = node_count_table[id];
603  if (p.first == 0) {
604  for (int i=0; i<=tree->depth; ++i)
605  p.second.push_back(tree->node[i].moved);
606  }
607  ++(p.first);
608  }
609  };
610 #endif
611 };
612 
613 /* ------------------------------------------------------------------------- */
614 #ifdef DFPN_STAT
615 osl::CArray<osl::CArray<int,64>,2> count2proof, count2disproof, count2unknown;
616 #endif
617 
618 struct osl::checkmate::DfpnTable::List : public std::forward_list<DfpnRecord>
619 {
620  typedef std::forward_list<DfpnRecord> list_t;
621 #ifdef OSL_DFPN_SMP
622  mutable Mutex mutex;
623 #endif
624  List() {}
625  List(const List& src) : list_t(src) {}
626 
627  template <Player Attack>
628  const DfpnRecord probe(const HashKey& key, PieceStand white_stand) const;
629  template <Player Attack>
630  const DfpnRecord findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const;
631  template <Player Attack>
632  void showProofOracles(const HashKey& key, PieceStand white_stand, Move last_move) const;
633  bool store(DfpnRecord& value, int leaving_thread_id)
634  {
635 #ifdef USE_TBB_HASH
636  SCOPED_LOCK(lk,mutex);
637 #endif
638  for (DfpnRecord& record: *this) {
639  if (record.stands[BLACK] == value.stands[BLACK]) {
640 #ifdef OSL_DFPN_SMP
641  if (record.proof_disproof.isFinal()) {
642  value = record;
643  record.working_threads &= ~(1u << leaving_thread_id);
644  return false;
645  }
646  if (! value.proof_disproof.isFinal()) {
647  value.min_pdp = std::min(value.min_pdp, record.min_pdp);
650  value.dag_moves |= record.dag_moves;
651  value.solved |= record.solved;
652  value.false_branch |= record.false_branch;
653  }
654  value.working_threads = record.working_threads;
655  if (leaving_thread_id >= 0) {
656  assert(value.working_threads & (1u << leaving_thread_id));
657  value.working_threads &= ~(1u << leaving_thread_id);
658  }
659 #endif
660  record = value;
661  return false;
662  }
663  }
664  value.working_threads &= ~(1u << leaving_thread_id);
665  push_front(value);
666  return true;
667  }
668  void addDag(DfpnRecord& value)
669  {
670 #ifdef USE_TBB_HASH
671  SCOPED_LOCK(lk,mutex);
672 #endif
673  for (DfpnRecord& record: *this) {
674  if (record.stands[BLACK] == value.stands[BLACK]) {
675 #ifdef OSL_DFPN_SMP
676  value.min_pdp = std::min(value.min_pdp, record.min_pdp);
679  value.dag_moves |= record.dag_moves;
680  value.solved |= record.solved;
681  value.false_branch |= record.false_branch;
682  value.working_threads = record.working_threads;
683 #endif
684  record.dag_moves = value.dag_moves;
685  return;
686  }
687  }
688  }
689  bool setWorking(const DfpnRecord& value, int thread_id)
690  {
691 #ifdef USE_TBB_HASH
692  SCOPED_LOCK(lk,mutex);
693 #endif
694  for (DfpnRecord& record: *this) {
695  if (record.stands[BLACK] == value.stands[BLACK]) {
696  assert(! (value.working_threads & (1u << thread_id)));
697  record.working_threads |= 1u << thread_id;
698  return false;
699  }
700  }
701  push_front(value);
702  front().working_threads |= 1u << thread_id;
703  return true;
704  }
705  void leaveWorking(PieceStand black, int thread_id)
706  {
707 #ifdef USE_TBB_HASH
708  SCOPED_LOCK(lk,mutex);
709 #endif
710  for (DfpnRecord& record: *this) {
711  if (record.stands[BLACK] == black) {
712  // assert(p->working_threads & (1u << thread_id)); // fail when stop_all
713  record.working_threads &= ~(1u << thread_id);
714  return;
715  }
716  }
717  // assert(0); // fail when stop_all
718  }
719  void testTable(const BoardKey& /*key*/) const
720  {
721 #ifdef USE_TBB_HASH
722  SCOPED_LOCK(lk,mutex);
723 #endif
724  for (const DfpnRecord& record: *this) {
725  if (record.working_threads)
726  std::cerr << std::bitset<16>(record.working_threads) << "\n";
727  assert(record.working_threads == 0);
728 #ifdef DFPN_STAT
729  const int count = misc::BitOp::countBit(record.solved);
730  if (record.proof_disproof.isCheckmateSuccess())
731  count2proof[key.turn()][count]++;
732  else if (record.proof_disproof.isCheckmateFail())
733  count2disproof[key.turn()][count]++;
734  else
735  count2unknown[key.turn()][count]++;
736 #endif
737  }
738  }
739  size_t smallTreeGC(size_t threshold)
740  {
741  size_t removed = 0;
742 #ifdef USE_TBB_HASH
743  SCOPED_LOCK(lk,mutex);
744 #endif
745  list_t::iterator p=begin();
746  while (p!=end()) {
747  list_t::iterator q=p;
748  ++q;
749  if (q == end())
750  break;
751  if (! q->proof_disproof.isFinal()
752 #ifdef OSL_DFPN_SMP
753  && q->working_threads == 0
754 #endif
755  && q->node_count < threshold) {
756  erase_after(p);
757  ++removed;
758  continue;
759  }
760  p = q;
761  }
762  if (! empty() && ! begin()->proof_disproof.isFinal()
763 #ifdef OSL_DFPN_SMP
764  && begin()->working_threads == 0
765 #endif
766  && begin()->node_count < threshold) {
767  pop_front(); // erase(begin())
768  ++removed;
769  }
770  return removed;
771  }
772  size_t estimateNodeCount(const HashKey& key, bool dominance_max) const;
773 };
774 template <osl::Player A>
776 List::probe(const HashKey& key, PieceStand white_stand) const
777 {
778 #ifdef USE_TBB_HASH
779  SCOPED_LOCK(lk,mutex);
780 #endif
781  DfpnRecord result(key.blackStand(), white_stand);
782  const PieceStand attack_stand = (A == BLACK) ? key.blackStand() : white_stand;
783  const PieceStand defense_stand = (A == BLACK) ? white_stand : key.blackStand();
784 #ifdef INITIAL_DOMINANCE
785  unsigned int proof_ll = 1, disproof_ll = 1;
786 #endif
787  for (const DfpnRecord& record: *this) {
788  if (record.stands[BLACK] == key.blackStand()) {
789  result = record;
790  if (result.proof_disproof.isFinal())
791  break;
792  continue;
793  }
794  if (record.proof_disproof.isCheckmateSuccess()) {
795  if (attack_stand.isSuperiorOrEqualTo(record.proofPieces())) {
796  result.setFrom(record);
797  break;
798  }
799  }
800  else if (record.proof_disproof.isCheckmateFail()) {
801  if (defense_stand.isSuperiorOrEqualTo(record.disproofPieces())) {
802  result.setFrom(record);
803  break;
804  }
805  }
806 #ifdef INITIAL_DOMINANCE
807  else {
808  if (record.stands[A].isSuperiorOrEqualTo(attack_stand)) {
809  proof_ll = std::max(proof_ll, record.proof());
810  }
811  else if (attack_stand.isSuperiorOrEqualTo(record.stands[A])) {
812  disproof_ll = std::max(disproof_ll, record.disproof());
813  }
814  }
815 #endif
816  }
817 #ifdef INITIAL_DOMINANCE
818  if (result.proof_disproof == ProofDisproof(1,1)) {
820  std::min(disproof_ll, InitialDominanceDisproofMax));
821  result.node_count++; // not suitable for proof_average
822  }
823 #endif
824  return result;
825 }
826 
828 List::estimateNodeCount(const HashKey& key, bool dominance_max) const
829 {
830 #ifdef USE_TBB_HASH
831  SCOPED_LOCK(lk,mutex);
832 #endif
833  size_t node_count = 0, exact = 0;
834  for (const DfpnRecord& record: *this) {
835  if (node_count < record.node_count)
836  node_count = record.node_count;
837  if (key.blackStand() == record.stands[BLACK])
838  exact = record.node_count;
839  }
840  return dominance_max ? node_count : exact;
841 }
842 
843 template <osl::Player A>
845 List::findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const
846 {
847 #ifdef USE_TBB_HASH
848  SCOPED_LOCK(lk,mutex);
849 #endif
850  const PieceStand attack_stand = (A == BLACK) ? key.blackStand() : white_stand;
851  DfpnRecord result(key.blackStand(), white_stand);
852  for (const DfpnRecord& record: *this) {
853  if (! record.proof_disproof.isCheckmateSuccess())
854  continue;
855  if (attack_stand.isSuperiorOrEqualTo(record.proofPieces())) {
856  result.setFrom(record);
857  ++record.node_count;
858  if (record.last_move == last_move)
859  break;
860  }
861  }
862  return result;
863 }
864 
865 #ifndef MINIMAL
866 template <osl::Player A>
868 List::showProofOracles(const HashKey& key, PieceStand white_stand, Move last_move) const
869 {
870 #ifdef USE_TBB_HASH
871  SCOPED_LOCK(lk,mutex);
872 #endif
873  const PieceStand attack_stand = (A == BLACK) ? key.blackStand() : white_stand;
874  for (const DfpnRecord& record: *this) {
875  if (! record.proof_disproof.isCheckmateSuccess())
876  continue;
877  if (attack_stand.isSuperiorOrEqualTo(record.proofPieces())) {
878  std::cerr << record.last_move << " " << record.best_move << " " << record.node_count << " " << record.proofPieces()
879  << " " << record.stands[BLACK] << " " << record.stands[WHITE] << "\n";
880  }
881  }
882 }
883 #endif
884 
885 struct osl::checkmate::DfpnTable::Table : public std::unordered_map<BoardKey, List, std::hash<BoardKey>>
886 {
888  explicit Table(Player a=BLACK) : attack(a) {}
889 };
890 
891 
894  : table(new Table[DIVSIZE]), total_size(0), dfpn_max_depth(0),
895  growth_limit(GrowthLimitInfty),
896  gc_threshold(10)
897 {
898  setAttack(attack);
899 }
900 
903  : table(new Table[DIVSIZE]), total_size(0), dfpn_max_depth(0)
904 {
905 }
908 {
909 }
910 
912 DfpnTable::setGrowthLimit(size_t new_limit)
913 {
914  growth_limit = new_limit;
915  for (int i=0; i<DIVSIZE; ++i) {
916  table[i].rehash(new_limit/DIVSIZE+new_limit/DIVSIZE/128+1);
917  }
918 }
919 
921 DfpnTable::showStats() const
922 {
923  if (size()) {
924  std::cerr << "total " << total_size << "\n";
925  for (int i=0; i<DIVSIZE; ++i)
926  std::cerr << "DfpnTable " << i << " " << table[i].size() << "\n";
927  }
928 }
929 
931 DfpnTable::setMaxDepth(int new_depth)
932 {
933  dfpn_max_depth = new_depth;
934 }
936 DfpnTable::maxDepth() const
937 {
938  return dfpn_max_depth;
939 }
940 
943 {
944  assert(size() == 0);
945  for (int i=0; i<DIVSIZE; ++i)
946  table[i].attack = a;
947 }
948 
950 DfpnTable::attack() const
951 {
952  return table[0].attack;
953 }
954 
955 template <osl::Player Attack>
958 DfpnTable::find(const HashKey& key, int subindex)
959 {
960  assert(table[subindex].attack == Attack);
961 #ifdef USE_TBB_HASH
962  Table::accessor it;
963  if(!table[subindex].find(it,key.boardKey()))
964  return 0;
965  return &it->second;
966 #else
967  Table::iterator p = table[subindex].find(key.boardKey());
968  if (p == table[subindex].end())
969  return 0;
970  return &p->second;
971 #endif
972 }
973 
974 template <osl::Player Attack>
977 DfpnTable::find(const HashKey& key, int subindex) const
978 {
979  assert(table[subindex].attack == Attack);
980  return find(key, subindex);
981 }
982 
985 DfpnTable::find(const HashKey& key, int subindex) const
986 {
987 #ifdef USE_TBB_HASH
988  Table::accessor it;
989  if(!table[subindex].find(it,key.boardKey()))
990  return 0;
991  return &it->second;
992 #else
993  Table::const_iterator p = table[subindex].find(key.boardKey());
994  if (p == table[subindex].end())
995  return 0;
996  return &p->second;
997 #endif
998 }
999 
1000 template <osl::Player Attack>
1002 DfpnTable::probe(const HashKey& key, PieceStand white_stand) const
1003 {
1004  const int i=keyToIndex(key);
1005 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1006  SCOPED_LOCK(lk,mutex[i]);
1007 #endif
1008  const List *l = find<Attack>(key, i);
1009  if (l == 0)
1010  return DfpnRecord(key.blackStand(), white_stand);
1011  return l->probe<Attack>(key, white_stand);
1012 }
1013 
1015 DfpnTable::probe(const HashKey& key, PieceStand white_stand) const
1016 {
1017  if (table[0].attack == BLACK)
1018  return probe<BLACK>(key, white_stand);
1019  else
1020  return probe<WHITE>(key, white_stand);
1021 }
1022 template <osl::Player Attack>
1024 DfpnTable::findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const
1025 {
1026  const int i=keyToIndex(key);
1027 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1028  SCOPED_LOCK(lk,mutex[i]);
1029 #endif
1030  const List *l = find<Attack>(key, i);
1031  if (l == 0)
1032  return DfpnRecord(key.blackStand(), white_stand);
1033  return l->findProofOracle<Attack>(key, white_stand, last_move);
1034 }
1036 DfpnTable::findProofOracle(const HashKey& key, PieceStand white_stand, Move last_move) const
1037 {
1038  if (table[0].attack == BLACK)
1039  return findProofOracle<BLACK>(key, white_stand, last_move);
1040  else
1041  return findProofOracle<WHITE>(key, white_stand, last_move);
1042 }
1043 
1044 #ifndef MINIMAL
1045 template <osl::Player Attack>
1047 DfpnTable::showProofOracles(const HashKey& key, PieceStand white_stand, Move last_move) const
1048 {
1049  const int i=keyToIndex(key);
1050 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1051  SCOPED_LOCK(lk,mutex[i]);
1052 #endif
1053  const List *l = find<Attack>(key, i);
1054  if (l == 0)
1055  return;
1056  return l->showProofOracles<Attack>(key, white_stand, last_move);
1057 }
1058 #endif
1059 
1061 DfpnTable::estimateNodeCount(const HashKey& key, bool dominance_max) const
1062 {
1063  const int i=keyToIndex(key);
1064 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1065  SCOPED_LOCK(lk,mutex[i]);
1066 #endif
1067  const List *l = find(key, i);
1068  if (l == 0)
1069  return 0;
1070  return l->estimateNodeCount(key, dominance_max);
1071 }
1072 
1074 DfpnTable::store(const HashKey& key, DfpnRecord& value, int leaving_thread_id)
1075 {
1076  assert(key.blackStand() == value.stands[BLACK]);
1077  assert(! value.proof_disproof.isLoopDetection());
1078  const int i=keyToIndex(key);
1079 #ifdef USE_TBB_HASH
1080  Table::accessor it;
1081  table[i].insert(it,key.boardKey());
1082  List& l = it->second;
1083 #else
1084 # ifdef OSL_DFPN_SMP
1085  SCOPED_LOCK(lk,mutex[i]);
1086 # endif
1087  List& l = table[i][key.boardKey()];
1088 #endif
1089  if (l.store(value, leaving_thread_id)) {
1090 #ifdef OSL_USE_RACE_DETECTOR
1091  SCOPED_LOCK(lk,root_mutex);
1092  // __sync_fetch_and_add() ?
1093 #endif
1094  total_size += 1;
1095  }
1096 }
1098 DfpnTable::addDag(const HashKey& key, DfpnRecord& value)
1099 {
1100  assert(key.blackStand() == value.stands[BLACK]);
1101  assert(! value.proof_disproof.isLoopDetection());
1102  const int i=keyToIndex(key);
1103 #ifdef USE_TBB_HASH
1104  Table::accessor it;
1105  table[i].insert(it,key.boardKey());
1106  List& l = it->second;
1107 #else
1108 # ifdef OSL_DFPN_SMP
1109  SCOPED_LOCK(lk,mutex[i]);
1110 # endif
1111  List& l = table[i][key.boardKey()];
1112 #endif
1113  l.addDag(value);
1114 }
1115 
1117 DfpnTable::setWorking(const HashKey& key, const DfpnRecord& value, int thread_id)
1118 {
1119  assert(key.blackStand() == value.stands[BLACK]);
1120  const int i=keyToIndex(key);
1121 #ifdef USE_TBB_HASH
1122  Table::accessor it;
1123  table[i].insert(it,key.boardKey());
1124  List& l = it->second;
1125 #else
1126 # ifdef OSL_DFPN_SMP
1127  SCOPED_LOCK(lk,mutex[i]);
1128 # endif
1129  List& l = table[i][key.boardKey()];
1130 #endif
1131  if (l.setWorking(value, thread_id)) {
1132 #ifdef OSL_USE_RACE_DETECTOR
1133  SCOPED_LOCK(lk,root_mutex);
1134  // __sync_fetch_and_add() ?
1135 #endif
1136  total_size += 1;
1137  }
1138 }
1140 DfpnTable::leaveWorking(const HashKey& key, int thread_id)
1141 {
1142  const int i=keyToIndex(key);
1143 #ifdef USE_TBB_HASH
1144  Table::accessor it;
1145  table[i].insert(it,key.boardKey());
1146  List& l = it->second;
1147 #else
1148 # ifdef OSL_DFPN_SMP
1149  SCOPED_LOCK(lk,mutex[i]);
1150 # endif
1151  List& l = table[i][key.boardKey()];
1152 #endif
1153  l.leaveWorking(key.blackStand(), thread_id);
1154 }
1155 
1158 {
1159  total_size = 0;
1160  for (int i=0; i<DIVSIZE; ++i) {
1161 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1162  SCOPED_LOCK(lk,mutex[i]);
1163 #endif
1164  table[i].clear();
1165  }
1166 }
1167 
1170 {
1171  for (int i=0; i<DIVSIZE; ++i) {
1172 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1173  SCOPED_LOCK(lk,mutex[i]);
1174 #endif
1175  for (auto& v: table[i])
1176  v.second.testTable(v.first);
1177  }
1178 #ifdef DFPN_STAT
1179  for (int i=0; i<16; ++i) {
1180  for (int j=0; j<2; ++j)
1181  std::cout << std::setw(9) << count2proof[j][i]
1182  << std::setw(9) << count2disproof[j][i]
1183  << std::setw(9) << count2unknown[j][i]
1184  << " ";
1185  std::cout << "\n";
1186  }
1187 #endif
1188 }
1189 
1192 {
1193  size_t removed = 0;
1194  for (int i=0; i<DIVSIZE; ++i) {
1195 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1196  SCOPED_LOCK(lk,mutex[i]);
1197 #endif
1198  Table::iterator p=table[i].begin();
1199  while (p!=table[i].end()) {
1200  removed += p->second.smallTreeGC(threshold);
1201  Table::iterator q = p;
1202  ++p;
1203  if (q->second.empty()) {
1204 #ifdef USE_TBB_HASH
1205  table[i].erase(q->first);
1206 #else
1207  table[i].erase(q);
1208 #endif
1209  }
1210  }
1211  }
1212  total_size -= removed;
1213  return removed;
1214 }
1215 
1218 {
1219  const size_t before = total_size;
1220  if (! (before >= growth_limit || (growth_limit - before) < growth_limit/8))
1221  return false;
1222 
1223  std::cerr << "run GC " << before << ' ' << gc_threshold << "\n";
1224  const size_t removed = smallTreeGC(gc_threshold);
1225  double memory = OslConfig::memoryUseRatio();
1226  std::cerr << " GC " << removed
1227  << " entries "
1228  << "collected " << std::setprecision(3)
1229  << ((sizeof(HashKey)+sizeof(DfpnRecord)+sizeof(char*)*2)
1230  * removed / (1<<20)) << "MB "
1231  << 100.0*removed/before << "%"
1232  << " real " << memory*100 << "%"
1233  // << " (" << elapsed << " s)"
1234  << "\n";
1235  gc_threshold += 15;
1236  static double memory_limit = 0.75;
1237  if (memory > memory_limit) {
1238  growth_limit -= growth_limit/8;
1239  gc_threshold += 15 + gc_threshold/4;
1240  memory_limit += 0.01;
1241  }
1242  if (removed < before*2/3)
1243  gc_threshold += 15 + gc_threshold/2;
1244  if ((removed < before*3/5 && memory > 0.75) || removed < before/2)
1245  throw Dfpn::DepthLimitReached();
1246  return true;
1247 }
1248 
1249 
1251 DfpnTable::size() const
1252 {
1253  return total_size;
1254 }
1255 
1256 /* ------------------------------------------------------------------------- */
1257 
1258 template <osl::Player P>
1260 {
1263  {
1264  }
1265  void operator()(Square) const
1266  {
1267  search->attack<P>();
1268  }
1269 };
1270 
1271 template <osl::Player P>
1273 {
1276  {
1277  }
1278  void operator()(Square) const
1279  {
1280  search->defense<P>();
1281  }
1282 };
1283 
1284 /* ------------------------------------------------------------------------- */
1285 
1286 
1288  : table(0), tree(new Tree(OslConfig::dfpnMaxDepth())), path_table(new DfpnPathTable), parallel_shared(0),
1289  thread_id(-1), blocking_verify(true)
1290 {
1291 }
1293 {
1294 }
1295 
1297 {
1298  table = new_table;
1299  table->setMaxDepth(tree->MaxDepth);
1300  if (tree->MaxDepth > EnableGCDepth
1301  && table->growthLimit() < GrowthLimitInfty)
1302  path_table->rehash(parallel_shared ? table->growthLimit()/4 : table->growthLimit());
1303 }
1304 
1306 {
1307  path_table->clear();
1308 }
1309 
1310 
1312 {
1313  // path_table はDualDfpnでクリアされるのでこちらは現状ではおまじない
1314  LoopToDominance dummy;
1315  DfpnPathRecord *record = (table->attack() == BLACK)
1316  ? path_table->allocate<BLACK>(key, 0, dummy)
1317  : path_table->allocate<WHITE>(key, 0, dummy);
1318  record->visiting = true;
1319 
1320  // こちらが重要
1321  DfpnRecord result(key.blackStand(), white_stand);
1323  result.setDisproofPieces((table->attack() == WHITE) ? key.blackStand() : white_stand);
1324  table->store(key, result);
1325 }
1326 
1329 Dfpn::hasCheckmateMove(const NumEffectState& state, const HashKey& key,
1330  const PathEncoding& path, size_t limit, Move& best_move, Move last_move,
1331  std::vector<Move> *pv)
1332 {
1333  PieceStand dummy;
1334  return hasCheckmateMove(state, key, path, limit, best_move, dummy, last_move, pv);
1335 }
1336 
1339 Dfpn::hasCheckmateMove(const NumEffectState& state, const HashKey& key,
1340  const PathEncoding& path, size_t limit, Move& best_move, PieceStand& proof_pieces,
1341  Move last_move, std::vector<Move> *pv)
1342 {
1343  assert(table);
1344  if (! table)
1345  return ProofDisproof();
1346  path_table->clear();
1347 
1348  node_count = 0;
1349  node_count_limit = limit;
1350 
1351  Node& root = tree->node[0];
1352  try {
1353  tree->state.copyFrom(state);
1354  tree->depth = 0;
1355  root.hash_key = key;
1356  root.path = path;
1357  root.clear();
1359  root.white_stand = PieceStand(WHITE, state);
1360  root.moved = last_move;
1361  if (state.turn() == BLACK)
1362  attack<BLACK>();
1363  else
1364  attack<WHITE>();
1365  }
1366  catch (DepthLimitReached&) {
1367  for (int i=0; i<=tree->depth; ++i)
1368  table->leaveWorking(tree->node[i].hash_key, thread_id);
1369  return ProofDisproof();
1370  }
1371  if (root.path_record
1372  && (std::find(root.path_record->twin_list.begin(), root.path_record->twin_list.end(), path)
1373  != root.path_record->twin_list.end())) {
1374  if (parallel_shared)
1375  parallel_shared->stop_all = true;
1377  }
1378  if (parallel_shared && root.record.proof_disproof.isFinal())
1379  parallel_shared->stop_all = true;
1380  best_move = root.record.best_move;
1382  proof_pieces = root.record.proofPieces();
1383  // retrieve pv
1384  if (pv && root.record.proof_disproof.isCheckmateSuccess()) {
1385  ProofTreeDepthDfpn analyzer(*table);
1386  analyzer.retrievePV(state, true, *pv);
1387  }
1388  return root.record.proof_disproof;
1389 }
1390 
1393 Dfpn::tryProof(const NumEffectState& state, const HashKey& key,
1394  const PathEncoding& path, const ProofOracle& oracle, size_t oracle_id, Move& best_move,
1395  Move last_move)
1396 {
1397  return tryProofMain<true>(state, key, path, oracle, oracle_id, best_move, last_move);
1398 }
1401 Dfpn::tryProofLight(const NumEffectState& state, const HashKey& key,
1402  const PathEncoding& path, const ProofOracle& oracle, size_t oracle_id, Move& best_move,
1403  Move last_move)
1404 {
1405  return tryProofMain<false>(state, key, path, oracle, oracle_id, best_move, last_move);
1406 }
1407 
1408 static const size_t root_proof_simulation_limit = 999999999;// large enough
1409 
1410 template <bool UseTable>
1413 Dfpn::tryProofMain(const NumEffectState& state, const HashKey& key,
1414  const PathEncoding& path, const ProofOracle& oracle, size_t oracle_id, Move& best_move,
1415  Move last_move)
1416 {
1417  assert(table);
1418  if (! table)
1419  return ProofDisproof();
1420  path_table->clear();
1421 
1422  tree->state.copyFrom(state);
1423  node_count = tree->depth = 0;
1424  node_count_limit = root_proof_simulation_limit;
1425 
1426  Node& root = tree->node[0];
1427  root.hash_key = key;
1428  root.path = path;
1429  root.clear();
1431  root.white_stand = PieceStand(WHITE, state);
1432  root.moved = last_move;
1433 
1434  root.record = (state.turn() == BLACK)
1435  ? table->probe<BLACK>(root.hash_key, root.white_stand)
1436  : table->probe<WHITE>(root.hash_key, root.white_stand);
1437  if (root.record.proof_disproof.isFinal() || root.record.tried_oracle > oracle_id) {
1438  best_move = root.record.best_move;
1439  return root.record.proof_disproof;
1440  }
1441 
1442  try {
1443  if (state.turn() == BLACK)
1444  proofOracleAttack<BLACK,UseTable>(oracle, ProofSimulationTolerance);
1445  else
1446  proofOracleAttack<WHITE,UseTable>(oracle, ProofSimulationTolerance);
1447  }
1448  catch (DepthLimitReached&) {
1449  for (int i=0; i<=tree->depth; ++i)
1450  table->leaveWorking(tree->node[i].hash_key, thread_id);
1451  return ProofDisproof();
1452  }
1453  if (UseTable && root.path_record
1454  && (std::find(root.path_record->twin_list.begin(), root.path_record->twin_list.end(), path)
1455  != root.path_record->twin_list.end()))
1457  if (UseTable) {
1458  root.record.last_move = last_move;
1459  table->store(root.hash_key, root.record);
1460  }
1461  best_move = root.record.best_move;
1462  root.record.tried_oracle = oracle_id+1;
1463  return root.record.proof_disproof;
1464 }
1465 
1466 
1469 Dfpn::hasEscapeMove(const NumEffectState& state,
1470  const HashKey& key, const PathEncoding& path,
1471  size_t limit, Move last_move)
1472 {
1473  assert(table);
1474  if (! state.hasEffectAt(alt(state.turn()), state.kingSquare(state.turn())))
1475  return ProofDisproof::NoCheckmate();
1476  if (! table)
1477  return ProofDisproof();
1478  path_table->clear();
1479  node_count = tree->depth = 0;
1480  node_count_limit = limit;
1481 
1482  Node& root = tree->node[0];
1483  try {
1484  tree->state.copyFrom(state);
1485  tree->depth = 0;
1486  root.hash_key = key;
1487  root.path = path;
1488  root.moved = last_move;
1489  root.clear();
1491  root.white_stand = PieceStand(WHITE, state);
1492  if (state.turn() == BLACK)
1493  defense<WHITE>();
1494  else
1495  defense<BLACK>();
1496 
1497  if (root.record.need_full_width) {
1498  root.clear();
1499  if (state.turn() == BLACK)
1500  defense<WHITE>();
1501  else
1502  defense<BLACK>();
1503  }
1504  }
1505  catch (DepthLimitReached&) {
1506  return ProofDisproof();
1507  }
1509  && last_move.isNormal() && last_move.isDrop() && last_move.ptype() == PAWN)
1511  if (root.path_record) {
1512  const SimpleTwinList& tl = root.path_record->twin_list;
1513  if (std::find(tl.begin(), tl.end(), root.path) != tl.end())
1515  }
1516  return root.record.proof_disproof;
1517 }
1518 
1519 namespace osl
1520 {
1521  namespace
1522  {
1523  typedef std::tuple<int,int,int> tuple_t;
1524  template <Player Turn>
1525  struct move_compare
1526  {
1527  const NumEffectState *state;
1528  move_compare(const NumEffectState& s) : state(&s)
1529  {
1530  assert(Turn == state->turn());
1531  }
1532  tuple_t convert(Move m) const
1533  {
1534  const int a = state->countEffect(Turn, m.to()) + m.isDrop();
1535  const int d = state->countEffect(alt(Turn), m.to());
1536  const int to_y = sign(Turn)*m.to().y();
1537  const int to_x = (5 - abs(5-m.to().x()))*2 + (m.to().x() > 5);
1538  int from_to = (to_y*16+to_x)*256;
1539  if (m.isDrop())
1540  from_to += m.ptype();
1541  else
1542  from_to += m.from().index();
1543  return std::make_tuple(a > d, from_to, m.isPromotion());
1544  }
1545  bool operator()(Move l, Move r) const
1546  {
1547  return convert(l) > convert(r);
1548  }
1549  };
1550  }
1551 }
1552 
1553 template <osl::Player Turn>
1555 Dfpn::sort(const NumEffectState& state, DfpnMoveVector& moves)
1556 {
1557 #ifdef MEMORIZE_SOLVED_IN_BITSET
1558  int last_sorted = 0, cur = 0;
1559  Ptype last_ptype = PTYPE_EMPTY;
1560  for (;(size_t)cur < moves.size(); ++cur) {
1561  if (moves[cur].isDrop() || moves[cur].oldPtype() == last_ptype)
1562  continue;
1563  std::sort(moves.begin()+last_sorted, moves.begin()+cur, move_compare<Turn>(state));
1564  last_sorted = cur;
1565  last_ptype = moves[cur].oldPtype();
1566  }
1567  std::sort(moves.begin()+last_sorted, moves.begin()+cur, move_compare<Turn>(state));
1568 #endif
1569 }
1570 
1571 template <osl::Player P>
1573 Dfpn::generateCheck(const NumEffectState& state, DfpnMoveVector& moves, bool &has_pawn_checkmate)
1574 {
1575  assert(moves.empty());
1576  if (state.inCheck(P))
1577  {
1578  using namespace osl::move_classifier;
1581  for (Move move: escape) {
1582  if (MoveAdaptor<Check<P> >::isMember(state, move))
1583  moves.push_back(move);
1584  }
1585  }
1586  else
1587  {
1588  move_action::Store store(moves);
1590  (state,state.kingPiece(alt(P)).square(),store,has_pawn_checkmate);
1591  }
1592  for (Move move: moves)
1593  {
1594  if(move.hasIgnoredUnpromote<P>()){
1595  if(Ptype_Table.getEffect(unpromote(move.ptypeO()),move.to(),
1596  state.kingSquare(alt(P))).hasEffect()
1597  || (state.pinOrOpen(alt(P)).test
1598  (state.pieceAt(move.from()).number())))
1599  moves.push_back(move.unpromote());
1600  }
1601  }
1602  sort<P>(state, moves);
1603 }
1604 
1606 Dfpn::findDagSource(const HashKey& terminal_key,
1607  DfpnRecord& terminal_record,
1608  PieceStand terminal_stand, int offset)
1609 {
1610 #ifdef NAGAI_DAG_TEST
1611  PieceStand white_stand = terminal_stand;
1612  HashKey key = terminal_key;
1613  DfpnRecord cur = terminal_record;
1614 
1615  for (int d=offset; d<std::min(tree->MaxDepth,MaxDagTraceDepth); ++d) {
1616  if (! cur.last_move.isNormal())
1617  return;
1618  assert(key.turn() == alt(cur.last_move.player()));
1619  HashKey parent_key = key.newUnmakeMove(cur.last_move);
1620  white_stand = white_stand.previousStand(WHITE, cur.last_move);
1621  DfpnRecord parent = table->probe(parent_key, white_stand);
1622  // loop invariants
1623  // { parent, parent_key, white_stand } --(cur.last_move)-> { cur, key }
1624 
1625  // some implementation test (parent.best_move == cur.last_move) here
1626  // but it seems to be not suitable for gpsshogi
1627  for (int i=tree->depth - 4 - (d%2); i>=0; i-=2) {
1628  if (parent_key == tree->node[i].hash_key) {
1629  for (size_t m=0; m<std::min(tree->node[i].moves.size(), (size_t)64); ++m) {
1630  if (tree->node[i].moves[m] == tree->node[i+1].moved
1631  || tree->node[i].moves[m] == cur.last_move)
1632  tree->node[i].record.dag_moves |= (1ull << m);
1633  }
1634  if (parallel_shared)
1635  table->addDag(tree->node[i].hash_key, tree->node[i].record);
1636  terminal_record.dag_terminal = true;
1637  return;
1638  }
1639  }
1640  key = parent_key;
1641  cur = parent;
1642  }
1643 #endif
1644 }
1645 
1648 {
1649  findDagSource(tree->node[tree->depth].hash_key, tree->node[tree->depth].record,
1650  tree->node[tree->depth].white_stand, 1);
1651 }
1652 
1653 // P は攻撃側
1654 template <osl::Player P>
1656 Dfpn::attack()
1657 {
1658  assert(! tree->inCheck(alt(P)));
1659  Node& node = tree->node[tree->depth];
1660 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
1661  node.visit_time = ++timer;
1662 #endif
1663 #ifdef DFPN_DEBUG
1664  Tree::Logging logging(tree.get(), table, "attack");
1665 #endif
1666  const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.path.getDepth();
1667  LoopToDominance loop;
1668  DfpnVisitLock<> lk(node.path_record = path_table->allocate<P>(node.hash_key, my_distance, loop));
1669  DfpnRecord& record = node.record;
1670  record = DfpnRecord();
1671  if (loop == BadAttackLoop) {
1672  node.setLoopDetection();
1673  return;
1674  }
1675  assert(node.white_stand == PieceStand(WHITE, tree->state));
1676  const size_t node_count_org = node_count++;
1677 #if (! defined CHECKMATE_D2) && (! defined NO_IMMEDIATE_CHECKMATE)
1678  if (! tree->inCheck(P)
1679  && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.best_move)) {
1680  PieceStand proof_pieces; // Note: ImmediateCheckmate が合駒が必要な王手を使わないことに依存
1681  if (record.best_move.isDrop())
1682  proof_pieces.add(record.best_move.ptype());
1683  record.setProofPieces(proof_pieces);
1685  return;
1686  }
1687 #endif
1688  if (tree->depth + 2 >= tree->MaxDepth) {
1689  std::cerr << "throw " << thread_id << "\n";
1690  throw DepthLimitReached();
1691  }
1692  assert(tree->depth + 2 < tree->MaxDepth);
1693  record = table->probe<P>(node.hash_key, node.white_stand);
1694  assert(record.stands[BLACK] == node.hash_key.blackStand());
1695  assert(record.stands[WHITE] == node.white_stand);
1696  if (record.proof_disproof.isFinal())
1697  return;
1698  if (tree->depth == 0 && node_count_limit <= 50 && record.node_count >= node_count_limit)
1699  return;
1700  if (tree->depth == 0
1701 #ifdef CHECKMATE_A3
1702  || true
1703 #endif
1704 #ifdef CHECKMATE_A3_GOLD
1705  || (record.proof_disproof == ProofDisproof(1,1) && tree->state.hasPieceOnStand<GOLD>(P)
1706  && (tree->king(alt(P)).square().x() <= 3 || tree->king(alt(P)).square().x() >= 7
1707  || tree->king(alt(P)).square().template squareForBlack<P>().y() <= 3))
1708 #endif
1709  )
1710  {
1711 #ifdef DFPN_STAT
1712  static stat::Ratio oracle_success("a3-gold");
1713 #endif
1714  FixedDepthSolverExt fixed_solver(tree->state);
1715  PieceStand proof_pieces;
1716  ProofDisproof pdp = fixed_solver.hasCheckmateMove<P>(2, record.best_move, proof_pieces);
1717  ++node_count;
1718 #ifdef DFPN_STAT
1719  oracle_success.add(pdp.isCheckmateSuccess());
1720 #endif
1721  if (pdp.isCheckmateSuccess()) {
1722  record.node_count++;
1723  record.proof_disproof = pdp;
1724  record.setProofPieces(proof_pieces);
1725  record.last_move = node.moved;
1726  table->store(node.hash_key, record);
1727  return;
1728  }
1729  }
1730 #ifndef MINIMAL
1731  if (tree->MaxDepth > EnableGCDepth && thread_id <= 0) {
1732  try {
1733  const size_t removed = table->runGC();
1734  if (removed > 0) {
1735 #ifdef DFPN_DEBUG
1736  for (int i=1; i<tree->depth; ++i)
1737  std::cerr << tree->node[i].threshold.proof() << ' '
1738  << record::csa::show(tree->node[i].moved) << ' ';
1739  std::cerr << "\n";
1740 #endif
1741  }
1742  }
1743  catch (...) { // fail
1744  if (parallel_shared)
1745  parallel_shared->stop_all = true;
1746  throw;
1747  }
1748  }
1749  if (tree->MaxDepth > EnableGCDepth
1750  && (path_table->size() > table->growthLimit()
1751 #ifdef OSL_DFPN_SMP
1752  || (parallel_shared
1753  && path_table->size() > table->growthLimit()/4)
1754 #endif
1755  )) {
1756  const size_t before = path_table->size();
1757  const size_t removed = path_table->runGC();
1758  if (removed > 0) {
1759  if (thread_id <= 0)
1760  std::cerr << " GC-path collected "
1761  << std::setprecision(3)
1762  << ((sizeof(HashKey)+sizeof(DfpnPathRecord)+sizeof(char*)*2)
1763  * removed / (1<<20)) << "MB "
1764  << 100.0*removed/before << "%\n";
1765  for (int i=0; i<tree->depth; ++i) {
1766  for (size_t j=0; j<tree->node[i].moves.size(); ++j) {
1767  tree->node[i].children_path[j] = 0;
1768  }
1769  }
1770  }
1771  }
1772 #endif
1773  if (parallel_shared) {
1774  if (parallel_shared->stop_all) {
1775  // std::cerr << "throw " << thread_id << "\n";
1776  throw DepthLimitReached();
1777  }
1778  if (parallel_shared->data[thread_id].restart) {
1779  for (int i=0; i<tree->depth; ++i) {
1780  if (tree->node[i].hash_key
1781  == parallel_shared->data[thread_id].restart_key)
1782  return;
1783 #if 0
1784  if (tree->node[i].record.dag_terminal)
1785  break; // ignore
1786 #endif
1787  }
1788  // false alert
1789  parallel_shared->data[thread_id].clear();
1790  }
1791  }
1792 
1793  // move generation
1794  bool has_pawn_checkmate=false;
1795  generateCheck<P>(tree->state, node.moves,has_pawn_checkmate);
1796  if (node.moves.empty()) {
1797  record.setDisproofPieces(DisproofPieces::leaf(tree->state, alt(P),
1798  record.stands[alt(P)]));
1799  if(has_pawn_checkmate)
1801  else
1803  return;
1804  }
1805  // probe all
1806 #ifdef PROOF_AVERAGE
1807  int frontier_count = 0, sum_frontier_proof = 0;
1808 #endif
1809  assert(node.children.empty());
1810  {
1811  node.allocate(node.moves.size());
1812  const King8Info info_modified
1813  = Edge_Table.resetEdgeFromLiberty(alt(P), tree->king(alt(P)).square(), King8Info(tree->state.Iking8Info(alt(P))));
1814  for (size_t i=0; i<node.moves.size(); ++i) {
1815 #ifdef MEMORIZE_SOLVED_IN_BITSET
1816  if (record.solved & (1ull << i))
1817  continue;
1818 #endif
1819  const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
1820  node.children[i] = table->probe<P>(new_key, node.nextWhiteStand(P, node.moves[i]));
1821  if (node.children[i].proof_disproof == ProofDisproof(1,1)) {
1822  unsigned int proof, disproof;
1823  LibertyEstimator::attackH(P, tree->state, info_modified,
1824  node.moves[i], proof, disproof);
1825 #ifndef MINIMAL
1827  // randomness presented by Hoki2011 (zero by default)
1828  std::pair<char,char> randomness = HashRandomPair::value(new_key);
1829  proof += randomness.first;
1830  disproof += randomness.second;
1831  }
1832 #endif
1833  node.children[i].proof_disproof = ProofDisproof(proof, disproof);
1834  }
1835  if (node.children[i].proof_disproof == ProofDisproof::NoEscape()
1836  && node.moves[i].isDrop() && node.moves[i].ptype() == PAWN) {
1837  node.children[i].proof_disproof = ProofDisproof::PawnCheckmate();
1838 #ifdef MEMORIZE_SOLVED_IN_BITSET
1839  record.solved |= (1ull << i);
1840 #endif
1841  record.min_pdp = std::min(record.min_pdp, (unsigned int)ProofDisproof::PAWN_CHECK_MATE_PROOF);
1842  }
1843  else if (node.children[i].proof_disproof.isCheckmateFail())
1844  tree->setNoCheckmateChildInAttack(i);
1845  else if (node.children[i].proof_disproof.isCheckmateSuccess()) {
1846  record.node_count += node_count - node_count_org;
1847  node.setCheckmateAttack(P,i);
1848  record.last_move = node.moved;
1849  table->store(node.hash_key, record);
1850  node.path_record->node_count = 0;
1851  return;
1852  }
1853 #ifdef PROOF_AVERAGE
1854  else if (node.children[i].node_count == 0) {
1855  ++frontier_count;
1856  sum_frontier_proof += node.children[i].proof();
1857  assert(node.children[i].proof() < 128);
1858  }
1859 #endif
1860 #ifdef AGGRESSIVE_FIND_DAG2
1861  else if (!node.children[i].proof_disproof.isFinal()
1862  && std::max(node.children[i].proof(), node.children[i].disproof()) >= DagFindThreshold2
1863  && node.children[i].last_move.isNormal()
1864  && node.children[i].last_move != node.moves[i]) {
1865  findDagSource(node.hashes[i], node.children[i],
1866  node.nextWhiteStand(P, node.moves[i]));
1867  }
1868 #endif
1869  node.children_path[i] = path_table->probe(new_key);
1870  node.proof_cost[i] = attackProofCost(P, tree->state, node.moves[i]);
1871  }
1872  }
1873 
1874  // hereafter, call leaveWorking before returning
1875  if (parallel_shared)
1876  table->setWorking(node.hash_key, record, thread_id);
1877 
1878  const Move recorded_last_move = record.last_move;
1879  record.last_move = node.moved;
1880 
1881  assert(node.children.size() == node.moves.size());
1882 #ifdef PROOF_AVERAGE
1883  const size_t proof_average = frontier_count ? sum_frontier_proof/frontier_count : 1;
1884 #else
1885  const size_t proof_average = 1;
1886 #endif
1887  // main loop
1888 #ifdef DFPN_DEBUG
1889  if (std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.hash_key))
1890  != debug_node.end() && timer > debug_time_start)
1891  tree->dump(__LINE__);
1892 #endif
1893  for (int loop=0; true; ++loop) {
1894  unsigned int min_proof=record.min_pdp, min_proof2=record.min_pdp;
1895  size_t sum_disproof = 0, max_disproof = 0, max_disproof_dag = 0, next_i=node.children.size();
1896  size_t max_drop_disproof_rook = 0, max_drop_disproof_bishop = 0, max_drop_disproof_lance = 0;
1897  int max_children_depth = 0, upward_count = 0;
1898  for (size_t i=0; i<node.children.size(); ++i) {
1899 #ifdef MEMORIZE_SOLVED_IN_BITSET
1900  if (record.solved & (1ull << i))
1901  continue;
1902 #endif
1903  if (i > 0 && min_proof < ProofDisproof::PROOF_LIMIT
1904  && node.moves[i].fromTo() == node.moves[i-1].fromTo()
1905  && ! node.moves[i].isDrop()) {
1906  // ignore a no-promote move until it becomes the last one, if there is the corresponding promote move
1907  assert(node.moves[i].ptype() == node.moves[i-1].oldPtype());
1908  record.dag_moves |= ((1ull << i) | (1ull << (i-1)));
1911  continue;
1912  // fall through
1913  }
1914  size_t proof = node.children[i].proof();
1915  size_t disproof = node.children[i].disproof();
1916  if (proof && disproof) {
1917  proof += node.proof_cost[i];
1918 #ifdef OSL_DFPN_SMP
1919  if (parallel_shared && node.children[i].working_threads) {
1920  // proof += misc::BitOp::countBit(node.children[i].working_threads)/2+1;
1921  proof += misc::BitOp::countBit(node.children[i].working_threads);
1922  }
1923 #endif
1924  }
1925  if (node.children_path[i]) {
1926  if (node.isLoop(i)) {
1927  node.children[i].proof_disproof = ProofDisproof::LoopDetection();
1928  assert(proof < ProofDisproof::LOOP_DETECTION_PROOF);
1930  disproof = 0;
1931  }
1932  else if (! node.children[i].proof_disproof.isFinal()) {
1933  max_children_depth = std::max(max_children_depth, node.children_path[i]->distance);
1934 #ifdef NAGAI_DAG_TEST
1935  if (record.dag_moves & (1ull<<i)) {
1936  max_disproof_dag = std::max(max_disproof_dag, disproof);
1937  disproof = 0;
1938  }
1939  else
1940 #endif
1941 #ifdef DELAY_UPWARD
1942  if (node.children_path[i]->distance <= node.path_record->distance) {
1943  max_disproof = std::max(max_disproof, disproof);
1944  ++upward_count;
1945  disproof = UpwardWeight;
1946  }
1947  else
1948 #endif
1949  if (node.moves[i].isDrop()
1950  || (isMajor(node.moves[i].ptype())
1951  && ! node.moves[i].isCapture()
1952  && ! node.moves[i].isPromotion() && isPromoted(node.moves[i].ptype())
1953  && ! tree->state.hasEffectAt(alt(P), node.moves[i].to()))) {
1954  const EffectContent e
1955  = Ptype_Table.getEffect(node.moves[i].ptypeO(),
1956  Offset32(tree->king(alt(P)).square(), node.moves[i].to()));
1957  if (! e.hasUnblockableEffect()) {
1958  size_t *target = &max_drop_disproof_lance;
1959  if (unpromote(node.moves[i].ptype()) == ROOK)
1960  target = &max_drop_disproof_rook;
1961  else if (unpromote(node.moves[i].ptype()) == BISHOP)
1962  target = &max_drop_disproof_bishop;
1963  *target = std::max(*target, disproof);
1964  disproof = LongDropCount;
1965  }
1966  }
1967  } // ! isFinal
1968  }
1969  else {
1970  max_children_depth = node.path_record->distance+1;
1971  }
1972  if (proof < min_proof || (proof == min_proof && disproof && disproof < node.children[next_i].disproof())) {
1973  min_proof2 = min_proof;
1974  min_proof = proof;
1975  next_i = i;
1976  } else if (proof < min_proof2) {
1977  min_proof2 = proof;
1978  }
1979  sum_disproof += disproof;
1980  }
1981  sum_disproof += max_drop_disproof_rook + max_drop_disproof_bishop + max_drop_disproof_lance
1982  + max_disproof_dag;
1983  if (LongDropCount) {
1984  if (max_drop_disproof_rook) sum_disproof -= LongDropCount;
1985  if (max_drop_disproof_bishop) sum_disproof -= LongDropCount;
1986  if (max_drop_disproof_lance) sum_disproof -= LongDropCount;
1987  }
1988  if (upward_count) {
1989  if (sum_disproof == 0)
1990  sum_disproof = max_disproof;
1991  }
1992  if (node.path_record->distance >= max_children_depth) {
1993  node.path_record->distance = max_children_depth-1;
1994  }
1995 #ifdef KISHIMOTO_WIDEN_THRESHOLD
1996  if (loop == 0 && sum_disproof >= node.threshold.disproof() && sum_disproof > IgnoreUpwardDisproofThreshold)
1997  node.threshold = ProofDisproof(node.threshold.proof(), sum_disproof+1);
1998 #endif
1999 #ifdef ADHOC_SUM_RESTRICTION
2000  if (sum_disproof < ROOT_DISPROOF_TOL && min_proof > 0 && sum_disproof > min_proof*AdHocSumScale) {
2001  sum_disproof = min_proof*AdHocSumScale
2002  + slow_increase(sum_disproof-min_proof*AdHocSumScale);
2003  }
2004 #endif
2005  if (min_proof >= node.threshold.proof()
2006  || sum_disproof >= node.threshold.disproof()
2007  || next_i >= node.children.size()
2008  || node_count + min_proof >= node_count_limit) {
2009  record.proof_disproof = ProofDisproof(min_proof, sum_disproof);
2010  if (record.proof_disproof.isLoopDetection())
2011  node.setLoopDetection();
2012  else if (record.proof_disproof.isCheckmateFail()) {
2013  node.setNoCheckmateAttack(P, tree->state);
2014  } else if (! record.proof_disproof.isFinal()) {
2015  if (recorded_last_move.isNormal() && recorded_last_move != node.moved
2016  && std::max(record.proof(), record.disproof()) >= DagFindThreshold)
2017  findDagSource();
2018 #ifdef AGGRESSIVE_FIND_DAG
2019  if (std::max(node.children[next_i].proof(), node.children[next_i].disproof()) >= DagFindThreshold
2020  && node.children[next_i].last_move.isNormal()
2021  && node.children[next_i].last_move != node.moves[next_i]) {
2022  findDagSource(node.hashes[next_i], node.children[next_i],
2023  node.nextWhiteStand(P, node.moves[next_i]));
2024  node.children[next_i].last_move = node.moves[next_i];
2025  table->store(node.hashes[next_i], node.children[next_i]);
2026  }
2027 #endif
2028  }
2029  record.node_count += node_count - node_count_org;
2030  table->store(node.hash_key, record, thread_id);
2031  node.path_record->node_count = record.node_count;
2032  if (parallel_shared && record.proof_disproof.isFinal())
2033  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2034  return;
2035  }
2036 #ifdef MEMORIZE_SOLVED_IN_BITSET
2037  assert(! (record.solved & (1ull << next_i)));
2038 #endif
2039  record.best_move = node.moves[next_i];
2040  tree->newVisit(P, node.moves[next_i], node.hashes[next_i]);
2041  Node& next = tree->node[tree->depth+1];
2042  unsigned int disproof_c = node.threshold.disproof()
2043  - (sum_disproof - node.children[next_i].disproof());
2044 #ifdef ADHOC_SUM_RESTRICTION
2045  if (disproof_c > node.threshold.disproof())
2046  disproof_c = node.children[next_i].disproof()
2047  + (node.threshold.disproof() - sum_disproof);
2048 #endif
2049  next.threshold = ProofDisproof(std::min(min_proof2+proof_average, (size_t)node.threshold.proof())
2050  - node.proof_cost[next_i],
2051  disproof_c);
2052  CallDefense<P> helper(this);
2053  tree->depth += 1;
2054  next.path.pushMove(next.moved);
2055  tree->state.makeUnmakeMove(Player2Type<P>(), next.moved, helper);
2056  tree->depth -= 1;
2057  node.children[next_i] = next.record;
2058  node.children_path[next_i] = next.path_record;
2060  && next.moved.isDrop() && next.moved.ptype() == PAWN)
2061  node.children[next_i].proof_disproof = ProofDisproof::PawnCheckmate();
2062  if (node.children[next_i].proof_disproof.isCheckmateSuccess()) {
2063  node.setCheckmateAttack(P,next_i);
2064  record.node_count += node_count - node_count_org;
2065  record.last_move = node.moved;
2066  table->store(node.hash_key, record, thread_id);
2067  node.path_record->node_count = 0;
2068  if (parallel_shared)
2069  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2070  return;
2071  }
2072  else if (next.record.proof_disproof.isCheckmateFail()
2074  tree->setNoCheckmateChildInAttack(next_i);
2075  min_proof = std::min(min_proof2, node.children[next_i].proof());
2076  if (min_proof < ProofDisproof::PROOF_LIMIT
2077  && node_count + min_proof >= node_count_limit) {
2078  record.proof_disproof = ProofDisproof(min_proof, sum_disproof);
2079  record.node_count += node_count - node_count_org;
2080  table->store(node.hash_key, record, thread_id);
2081  node.path_record->node_count = record.node_count;
2082  if (parallel_shared)
2083  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2084  return;
2085  }
2086  if (parallel_shared && parallel_shared->data[thread_id].restart) {
2087  if (tree->depth == 0)
2088  parallel_shared->data[thread_id].clear();
2089  else {
2090  if (parallel_shared->data[thread_id].restart_key == node.hash_key) {
2091  record = table->probe<P>(node.hash_key, node.white_stand);
2092  if (! record.proof_disproof.isFinal())
2093  continue;
2094  parallel_shared->data[thread_id].clear();
2095  }
2096  table->leaveWorking(node.hash_key, thread_id);
2097  return;
2098  }
2099  }
2100  }
2101 }
2102 
2103 template <osl::Player P>
2105 Dfpn::generateEscape(const NumEffectState& state, bool need_full_width,
2106  Square last_to, DfpnMoveVector& moves)
2107 {
2108  assert(moves.empty());
2109  const Player AltP=alt(P);
2110 #ifdef GRAND_PARENT_DELAY
2111  const bool delay_node = last_to != Square()
2112  && state.hasEffectAt(alt(P), last_to)
2113  && (state.hasEffectNotBy(alt(P), state.kingPiece(alt(P)), last_to)
2114  || ! state.hasEffectAt(P, last_to));
2115  if (delay_node)
2116  {
2117  DfpnMoveVector all;
2119  generateCheapKingEscape(state, all);
2120 
2121  for (Move move: all) {
2122  if (move.to() == last_to) {
2123  moves.push_back(move);
2124  }
2125  }
2126 #ifdef MEMORIZE_SOLVED_IN_BITSET
2127  sort<AltP>(state, moves);
2128 #endif
2129  }
2130  else
2131 #endif
2132  {
2134  generateCheapKingEscape(state, moves);
2135 #ifdef MEMORIZE_SOLVED_IN_BITSET
2136  sort<AltP>(state, moves);
2137 #endif
2138  }
2139 
2140  if (need_full_width) {
2141  DfpnMoveVector others;
2143  generateKingEscape(state, others);
2144 #ifdef MEMORIZE_SOLVED_IN_BITSET
2145  sort<AltP>(state, others);
2146 #endif
2147  const int org_size = moves.size();
2148  for (Move move: others) {
2149  if (std::find(moves.begin(), moves.begin()+org_size, move) == moves.begin()+org_size)
2150  moves.push_back(move);
2151  }
2152  for (Move move: moves)
2153  {
2154  if(move.hasIgnoredUnpromote<AltP>())
2155  moves.push_back(move.unpromote());
2156  }
2157  }
2158  // TODO: 受け方の打歩詰め王手
2159 }
2160 
2163 {
2164 #ifdef GRAND_PARENT_SIMULATION
2165  Node& node = tree->node[tree->depth];
2166  if (tree->depth >= 2) {
2167  const Node& parent = tree->node[tree->depth-1];
2168  const Node& gparent = tree->node[tree->depth-2];
2169  const Move alm = node.moved; // attacker's last move
2170  const Move dlm = parent.moved; // defense's last move
2171  const Move alm2 = gparent.moved; // attacker's second-last move
2172  if (dlm.isNormal() && alm.to() == dlm.to() && ! dlm.isCapture()
2173  && alm2.isNormal() && alm2.to() == alm.from()) {
2174  return true;
2175  }
2176  }
2177 #endif
2178  return false;
2179 }
2180 
2181 template <osl::Player P>
2183 Dfpn::defense()
2184 {
2185 #if 0
2186  if (parallel_shared) {
2187  if (parallel_shared->stop_all)
2188  throw DepthLimitReached();
2189  if (parallel_shared->data[thread_id].restart) {
2190  for (int i=0; i<tree->depth; ++i) {
2191  if (tree->node[i].hash_key == parallel_shared->data[thread_id].restart_key)
2192  return;
2193 #if 0
2194  if (tree->node[i].record.dag_terminal)
2195  break;
2196 #endif
2197  }
2198  // false alert
2199  parallel_shared->data[thread_id].clear();
2200  }
2201  }
2202 #endif
2203  Node& node = tree->node[tree->depth];
2204 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
2205  node.visit_time = ++timer;
2206 #endif
2207 #ifdef DFPN_DEBUG
2208  Tree::Logging logging(tree.get(), table, "defens");
2209 #endif
2210  const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.path.getDepth();
2211  LoopToDominance loop;
2212  DfpnVisitLock<> lk(node.path_record = path_table->allocate<P>(node.hash_key, my_distance, loop));
2213  DfpnRecord& record = node.record;
2214  if (loop == BadAttackLoop) {
2215  record = DfpnRecord();
2216  node.setLoopDetection();
2217  return;
2218  }
2219  const size_t node_count_org = node_count++;
2220  assert(tree->inCheck(alt(P)));
2221  assert(node.white_stand == PieceStand(WHITE, tree->state));
2222 
2223  record = table->probe<P>(node.hash_key, node.white_stand);
2224  assert(record.stands[BLACK] == node.hash_key.blackStand());
2225  assert(record.stands[WHITE] == node.white_stand);
2226  if (record.proof_disproof.isFinal())
2227  return;
2228  const bool grand_parent_simulation = grandParentSimulationSuitable();
2229  if (record.last_to == Square())
2230  record.last_to = grand_parent_simulation ? node.moved.to() : tree->king(alt(P)).square();
2231  const Square grand_parent_delay_last_to
2232  = (record.last_to != tree->king(alt(P)).square()) ? record.last_to : Square();
2233 
2234  generateEscape<P>(tree->state, record.need_full_width, grand_parent_delay_last_to, node.moves);
2235  if (node.moves.empty() && ! record.need_full_width) {
2236  record.need_full_width = true;
2237  generateEscape<P>(tree->state, record.need_full_width, grand_parent_delay_last_to, node.moves);
2238  }
2239  if (node.moves.empty()) {
2240  record.setProofPieces(ProofPieces::leaf(tree->state, P, record.stands[P]));
2242  return;
2243  }
2244  // probe all
2245 #ifdef DISPROOF_AVERAGE
2246  int frontier_count = 0, sum_frontier_disproof = 0;
2247 #endif
2248  assert(node.children.empty());
2249  {
2250  node.allocate(node.moves.size());
2251  for (size_t i=0;i <node.moves.size(); ++i) {
2252 #ifdef MEMORIZE_SOLVED_IN_BITSET
2253  if (record.solved & (1ull << i))
2254  continue;
2255 #endif
2256  const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
2257  node.children[i] = table->probe<P>(new_key, node.nextWhiteStand(alt(P), node.moves[i]));
2258  if (node.children[i].proof_disproof.isCheckmateSuccess()) {
2259  node.setCheckmateChildInDefense(i);
2260  }
2261 #ifdef CHECKMATE_D2
2262  else if (node.children[i].proof_disproof == ProofDisproof(1,1)) {
2263  FixedDepthSolverExt fixed_solver(tree->state);
2264  PieceStand proof_pieces;
2265  Move check_move;
2266  node.children[i].proof_disproof
2267  = fixed_solver.hasEscapeByMove<P>(node.moves[i], 0, check_move, proof_pieces);
2268  ++node_count;
2269  if (node.children[i].proof_disproof.isCheckmateSuccess()) {
2270  node.children[i].best_move = check_move;
2271  node.children[i].setProofPieces(proof_pieces);
2272  node.children[i].node_count++;
2274  }
2275  else {
2276  if (node.children[i].proof_disproof.isCheckmateFail()) {
2277  node.children[i].proof_disproof = ProofDisproof(1,1);
2278  if (i) {
2279  node.moves[0] = node.moves[i];
2280  node.children[0] = node.children[i];
2281  node.children_path[0] = node.children_path[i];
2282  const int old_size = (int)node.moves.size();
2283  for (int j=1; j<old_size; ++j) {
2284  node.moves.pop_back();
2285  node.children.pop_back();
2286  node.children_path.pop_back();
2287  }
2288  }
2289  break;
2290  }
2291  else {
2292 #ifndef MINIMAL
2294  // randomness presented by Hoki2011 (zero by default)
2295  std::pair<char,char> randomness = HashRandomPair::value(new_key);
2296  if (randomness.first || randomness.second) {
2297  unsigned int proof = node.children[i].proof();
2298  unsigned int disproof = node.children[i].disproof();
2299  proof += randomness.first;
2300  disproof += randomness.second;
2301  node.children[i].proof_disproof = ProofDisproof( proof, disproof );
2302  }
2303  }
2304 #endif
2305  }
2306 #ifdef DISPROOF_AVERAGE
2307  ++frontier_count;
2308  sum_frontier_disproof += node.children[i].proof_disproof.disproof();
2309 #endif
2310  }
2311  // ++node_count;
2312  }
2313 #endif
2314  if (! node.children[i].proof_disproof.isCheckmateFail()) {
2315  node.children_path[i] = path_table->probe(new_key);
2316  if (node.isLoop(i)) {
2317  node.setLoopDetection();
2318  return;
2319  }
2320 #ifdef GRAND_PARENT_SIMULATION
2321  if (grand_parent_simulation && node.children[i].proof_disproof == ProofDisproof(1,1)) {
2322  const Node& gparent = tree->node[tree->depth-2];
2323  size_t gi=std::find(gparent.moves.begin(), gparent.moves.end(), node.moves[i]) - gparent.moves.begin();
2324  if (gi < gparent.moves.size()
2325  && (
2327  (gparent.record.solved & (1ull<<gi))
2328  ||
2329 #endif
2330  gparent.children[gi].proof_disproof.isCheckmateSuccess())) {
2331  grandParentSimulation<P>(i, gparent, gi);
2332  if (node.children[i].proof_disproof.isCheckmateSuccess())
2334  }
2335  }
2336 #endif
2337  }
2338  if (node.children[i].proof_disproof.isCheckmateFail()) {
2339  tree->setNoCheckmateDefense(P, i);
2340  table->store(node.hash_key, record);
2341  return;
2342  }
2343 #ifdef AGGRESSIVE_FIND_DAG2
2344  if (!node.children[i].proof_disproof.isFinal()
2345  && std::max(node.children[i].proof(),node.children[i].disproof()) >= DagFindThreshold2
2346  && node.children[i].last_move.isNormal()
2347  && node.children[i].last_move != node.moves[i]) {
2348  findDagSource(node.hashes[i], node.children[i],
2349  node.nextWhiteStand(alt(P), node.moves[i]));
2350  }
2351 #endif
2352  }
2353  if (record.need_full_width==1) {
2354  record.need_full_width++;
2355  for (size_t i=0;i <node.moves.size(); ++i) {
2356  if (
2358  ((record.solved & (1ull<<i))
2359  || (i >= 64 && node.children[i].proof_disproof.isCheckmateSuccess()))
2360 #else
2361  node.children[i].proof_disproof.isCheckmateSuccess()
2362 #endif
2363 
2364  && node.moves[i].isDrop()) {
2365  blockingSimulation<P>(i, ProofOracle(node.hash_key.newHashWithMove(node.moves[i]),
2366  node.nextWhiteStand(alt(P), node.moves[i])));
2367  }
2368  }
2369  }
2370  }
2371  assert(node.children.size() == node.moves.size());
2372 
2373  // hereafter, call leaveWorking before return
2374  if (parallel_shared)
2375  table->setWorking(node.hash_key, record, thread_id);
2376 
2377  // for dag analyses
2378  const Move recorded_last_move = node.moved;
2379  record.last_move = node.moved;
2380 
2381 #ifdef DISPROOF_AVERAGE
2382  const size_t disproof_average = frontier_count ? sum_frontier_disproof/frontier_count : 1;
2383 #else
2384  const size_t disproof_average = 1;
2385 #endif
2386  // main loop
2387 #ifdef DFPN_DEBUG
2388  if (std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.hash_key))
2389  != debug_node.end() && timer > debug_time_start)
2390  tree->dump(__LINE__);
2391 #endif
2393  for (int loop=0; true; ++loop) {
2394  std::fill(target.begin(), target.begin()+(int)node.moves.size(), false);
2395  unsigned int min_disproof=record.min_pdp, min_disproof2=record.min_pdp;
2396  size_t sum_proof = 0, max_upward_proof = 0, max_drop_proof = 0, next_i=node.children.size();
2397  size_t max_proof_dag = 0;
2398  int max_children_depth = 0, upward_count = 0;
2399 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2400  size_t max_proof = 0;
2401  bool false_branch_candidate = !record.false_branch;
2402 #endif
2403  for (size_t i=0; i<node.children.size(); ++i) {
2404 #ifdef MEMORIZE_SOLVED_IN_BITSET
2405  if (record.solved & (1ull << i))
2406  continue;
2407 #endif
2408  if (i > 0 && min_disproof < ProofDisproof::DISPROOF_LIMIT
2409  && node.moves[i].fromTo() == node.moves[i-1].fromTo()
2410  && ! node.moves[i].isDrop()) {
2411  // ignore a no-promote move until it becomes the last one, if there is the corresponding promote move
2412  assert(node.moves[i].ptype() == node.moves[i-1].oldPtype());
2413  continue;
2414  }
2415  size_t disproof = node.children[i].disproof();
2416  size_t proof = node.children[i].proof();
2417  if (node.children[i].proof_disproof.isCheckmateFail()) {
2418  // simulation で表を読んだら更新されていた等
2419  assert(! node.children[i].proof_disproof.isLoopDetection());
2420  tree->setNoCheckmateDefense(P, i);
2421  table->store(node.hash_key, record, thread_id);
2422  if (parallel_shared)
2423  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2424  return;
2425  }
2426 #ifdef OSL_DFPN_SMP
2427  if (proof && disproof) {
2428  if (parallel_shared && node.children[i].working_threads) {
2429  // disproof += misc::BitOp::countBit(node.children[i].working_threads)/2+1;
2430  disproof += misc::BitOp::countBit(node.children[i].working_threads);
2431  }
2432  }
2433 #endif
2434  if (node.children_path[i]) {
2435  if (node.isLoop(i)) {
2436  node.setLoopDetection();
2437  if (parallel_shared)
2438  table->leaveWorking(node.hash_key, thread_id);
2439  return;
2440  }
2441  if (! node.children[i].proof_disproof.isFinal()) {
2442  max_children_depth = std::max(max_children_depth, node.children_path[i]->distance);
2443 #ifdef IGNORE_MONSTER_CHILD
2444  if (node.children_path[i]->distance <= node.path_record->distance
2445  && (! record.need_full_width || min_disproof < ProofDisproof::DISPROOF_LIMIT) // todo: this condition is not accurate
2446  && node.children[i].proof_disproof.proof() >= node.threshold.proof()
2448  false_branch_candidate = false;
2449  continue; // ignore upward move with too much pdp, untill it becomes the last one
2450  }
2451  else
2452 #endif
2453 #ifdef NAGAI_DAG_TEST
2454  if (record.dag_moves & (1ull << i)) {
2455  max_proof_dag = std::max(max_proof_dag, proof);
2456  proof = 0;
2457  }
2458  else
2459 #endif
2460 #ifdef DELAY_UPWARD
2461  if (node.children_path[i]->distance <= node.path_record->distance) {
2462  max_upward_proof = std::max(max_upward_proof , proof);
2463  ++upward_count;
2464  proof = UpwardWeight;
2465  }
2466  else
2467 #endif
2468  if (node.moves[i].isDrop() && !tree->state.hasEffectAt(alt(P), node.moves[i].to())) {
2469  max_drop_proof = std::max(max_drop_proof, proof);
2470  proof = SacrificeBlockCount;
2471  }
2472  }
2473  }
2474  else {
2475  max_children_depth = node.path_record->distance+1;
2476  }
2477  target[i] = true;
2478  if (disproof < min_disproof
2479  || (disproof == min_disproof && proof && proof < node.children[next_i].proof())) {
2480  min_disproof2 = min_disproof;
2481  min_disproof = disproof;
2482  next_i = i;
2483  } else if (disproof < min_disproof2) {
2484  min_disproof2 = disproof;
2485  }
2486 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2487  if (false_branch_candidate && ! node.children[i].proof_disproof.isFinal()
2488  && (node.children[i].node_count == 0
2489  || ! node.children[i].best_move.isNormal()
2490  || ! (node.moves[i].ptype() == KING && ! node.moves[i].isCapture())))
2491  false_branch_candidate = false;
2492  max_proof = std::max(max_proof, proof);
2493 #endif
2494  sum_proof += proof;
2495  }
2496 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2497  if (false_branch_candidate) {
2498  record.false_branch = true;
2499  HashKey goal;
2500  for (size_t i=0; i<node.children.size(); ++i) {
2501  if (! target[i])
2502  continue;
2503  HashKey key = node.hashes[i];
2504  key = key.newHashWithMove(node.children[i].best_move);
2505  if (goal == HashKey()) {
2506  goal = key;
2507  continue;
2508  }
2509  if (goal != key) {
2510  record.false_branch = false;
2511  break;
2512  }
2513  }
2514  }
2515  if (record.false_branch)
2516  sum_proof = max_proof;
2517 #endif
2518  sum_proof += max_drop_proof + max_proof_dag;
2519  if (SacrificeBlockCount && max_drop_proof)
2520  sum_proof -= SacrificeBlockCount;
2521  if (upward_count) {
2522  if (sum_proof == 0)
2523  sum_proof = std::max(sum_proof, max_upward_proof);
2524  }
2525  if (node.path_record->distance >= max_children_depth) {
2526  node.path_record->distance = max_children_depth-1;
2527  }
2528  if (min_disproof >= ProofDisproof::DISPROOF_MAX) {
2529  assert(! record.need_full_width);
2530  record.proof_disproof = ProofDisproof(1,1);
2531  record.need_full_width = 1;
2532  table->store(node.hash_key, record, thread_id);
2533  return;
2534  }
2535 #ifdef KISHIMOTO_WIDEN_THRESHOLD
2536  if (loop == 0 && sum_proof >= node.threshold.proof() && sum_proof > IgnoreUpwardProofThreshold)
2537  node.threshold = ProofDisproof(sum_proof+1, node.threshold.disproof());
2538 #endif
2539 #ifdef ADHOC_SUM_RESTRICTION
2540  if (sum_proof < ROOT_PROOF_TOL && min_disproof > 0 && sum_proof > min_disproof*AdHocSumScale) {
2541  sum_proof = min_disproof*AdHocSumScale
2542  + slow_increase(sum_proof-min_disproof*AdHocSumScale);
2543  }
2544 #endif
2545  if (min_disproof >= node.threshold.disproof()
2546  || sum_proof >= node.threshold.proof()
2547  || next_i >= node.children.size()
2548  || node_count + sum_proof >= node_count_limit) {
2549  record.proof_disproof = ProofDisproof(sum_proof, min_disproof);
2550  if (record.proof_disproof.isLoopDetection())
2551  node.setLoopDetection();
2552  else if (record.proof_disproof.isCheckmateSuccess()) {
2553  if (blocking_verify && ! record.need_full_width) {
2554  // read again with full move generation
2555  record.need_full_width = 1;
2556  record.proof_disproof = ProofDisproof(1,1);
2557  table->store(node.hash_key, record, thread_id);
2558  return;
2559  }
2560  node.setCheckmateDefense(P, tree->state);
2561  } else if (! record.proof_disproof.isFinal()) {
2562  if (recorded_last_move.isNormal() && recorded_last_move != node.moved
2563  && std::max(record.proof(), record.disproof()) >= DagFindThreshold)
2564  findDagSource();
2565 #ifdef AGGRESSIVE_FIND_DAG
2566  if (std::max(node.children[next_i].proof(), node.children[next_i].disproof()) >= DagFindThreshold
2567  && node.children[next_i].last_move.isNormal()
2568  && node.children[next_i].last_move != node.moves[next_i]) {
2569  findDagSource(node.hashes[next_i], node.children[next_i],
2570  node.nextWhiteStand(alt(P), node.moves[next_i]));
2571  node.children[next_i].last_move = node.moves[next_i];
2572  table->store(node.hashes[next_i], node.children[next_i]);
2573  }
2574 #endif
2575  }
2576  record.node_count += node_count - node_count_org;
2577  table->store(node.hash_key, record, thread_id);
2578  node.path_record->node_count = record.node_count;
2579  if (parallel_shared && record.proof_disproof.isFinal())
2580  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2581  return;
2582  }
2583 #ifdef MEMORIZE_SOLVED_IN_BITSET
2584  assert(! (record.solved & (1ull << next_i)));
2585 #endif
2586  record.best_move = node.moves[next_i];
2587  tree->newVisit(alt(P), node.moves[next_i], node.hashes[next_i]);
2588  Node& next = tree->node[tree->depth+1];
2589  unsigned int proof_c = node.threshold.proof()
2590  - (sum_proof - node.children[next_i].proof());
2591 #ifdef ADHOC_SUM_RESTRICTION
2592  if (proof_c > node.threshold.proof())
2593  proof_c = node.children[next_i].proof()
2594  + (node.threshold.proof() - sum_proof);
2595 #endif
2596  next.threshold = ProofDisproof(proof_c,
2597  std::min(min_disproof2+disproof_average,
2598  (size_t)node.threshold.disproof()));
2599  CallAttack<P> helper(this);
2600  tree->depth += 1;
2601  next.path.pushMove(node.moves[next_i]);
2602  tree->state.makeUnmakeMove(Player2Type<alt(P)>(), node.moves[next_i], helper);
2603  tree->depth -= 1;
2604  if (parallel_shared && parallel_shared->data[thread_id].restart) {
2605  if (tree->depth == 0)
2606  parallel_shared->data[thread_id].clear();
2607  else {
2608  if (parallel_shared->data[thread_id].restart_key == node.hash_key) {
2609  record = table->probe<P>(node.hash_key, node.white_stand);
2610  assert(record.proof_disproof.isFinal());
2611  parallel_shared->data[thread_id].clear();
2612  }
2613  table->leaveWorking(node.hash_key, thread_id);
2614  return;
2615  }
2616  }
2617 
2618  node.children[next_i] = next.record;
2619  node.children_path[next_i] = next.path_record;
2620  if (next.record.proof_disproof.isCheckmateFail()) {
2621  if (record.proof_disproof.isLoopDetection())
2622  node.setLoopDetection();
2623  else
2624  tree->setNoCheckmateDefense(P, next_i);
2625  record.node_count += node_count - node_count_org;
2626  table->store(node.hash_key, record, thread_id);
2627  node.path_record->node_count = record.node_count;
2628  if (parallel_shared && record.proof_disproof.isFinal())
2629  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2630  return;
2631  }
2633  node.setCheckmateChildInDefense(next_i);
2634  if (node_count >= node_count_limit) {
2635  record.proof_disproof = ProofDisproof(sum_proof, min_disproof);
2636  record.node_count += node_count - node_count_org;
2637  table->store(node.hash_key, record, thread_id);
2638  node.path_record->node_count = record.node_count;
2639  if (parallel_shared && record.proof_disproof.isFinal())
2640  parallel_shared->restartThreads(node.hash_key, tree->depth, record.working_threads);
2641  return;
2642  }
2643  if (next.moved.isDrop() && next.record.proof_disproof.isCheckmateSuccess()) {
2644  blockingSimulation<P>(next_i, ProofOracle(next.hash_key, next.white_stand));
2645  }
2646  }
2647 }
2648 
2649 #if (!defined MINIMAL) || (defined DFPNSTATONE)
2651 Dfpn::analyze(const PathEncoding& path_src,
2652  const NumEffectState& src, const std::vector<Move>& moves) const
2653 {
2654  NumEffectState state(src);
2655  HashKey key(state);
2656  PathEncoding path(path_src);
2657  for (size_t i=0; i<moves.size(); ++i) {
2658  if (! state.isAlmostValidMove(moves[i]))
2659  break;
2660  state.makeMove(moves[i]);
2661  key = key.newMakeMove(moves[i]);
2662  path.pushMove(moves[i]);
2663  DfpnRecord record = table->probe(key, PieceStand(WHITE, state));
2664  const DfpnPathRecord *path_record = path_table->probe(key);
2665  std::cerr << i << ' ' << moves[i] << " " << path
2666  << ' ' << csa::show(record.best_move) << "\n";
2667  std::cerr << " " << record.proof_disproof << ' ' << record.node_count;
2668  if (path_record) {
2669  std::cerr << " distance " << path_record->distance << " twins";
2670  for (SimpleTwinList::const_iterator p=path_record->twin_list.begin();
2671  p!=path_record->twin_list.end(); ++p) {
2672  std::cerr << ' ' << *p;
2673  }
2674  }
2675  std::cerr << "\n";
2676  DfpnMoveVector moves;
2677  if (state.turn() == table->attack()) {
2678  bool has_pawn_checkmate=false;
2679  if (state.turn() == BLACK)
2680  generateCheck<BLACK>(state, moves, has_pawn_checkmate);
2681  else
2682  generateCheck<WHITE>(state, moves, has_pawn_checkmate);
2683  }
2684  else {
2685  const Square grand_parent_delay_last_to
2686  = (record.last_to != state.kingSquare(state.turn())) ? record.last_to : Square();
2687  if (state.turn() == BLACK)
2688  generateEscape<WHITE>(state, true, grand_parent_delay_last_to, moves);
2689  else
2690  generateEscape<BLACK>(state, true, grand_parent_delay_last_to, moves);
2691  }
2692  for (size_t i=0; i<moves.size(); ++i) {
2693  const Move m = moves[i];
2694  std::cerr << " " << m;
2695  DfpnRecord child = table->probe(key.newMakeMove(m),
2696  PieceStand(WHITE, state).nextStand(WHITE, m));
2697  std::cerr << ' ' << child.proof_disproof << ' ' << child.node_count;
2698  const DfpnPathRecord *child_path_record = path_table->probe(key.newMakeMove(m));
2699  if (child_path_record) {
2700  std::cerr << " d " << child_path_record->distance << " twins";
2701  for (const auto& path: child_path_record->twin_list) {
2702  std::cerr << ' ' << path;
2703  }
2704  }
2705  if (record.dag_moves & (1ull << i))
2706  std::cerr << " (*)";
2707  std::cerr << "\n";
2708  }
2709  }
2710  std::cerr << state;
2711 }
2712 #endif
2713 /* ------------------------------------------------------------------------- */
2714 template <osl::Player P, bool UseTable>
2716 {
2720  CallProofOracleAttack(Dfpn *s, const ProofOracle& o, int pl) : search(s), oracle(o), proof_limit(pl)
2721  {
2722  }
2723  void operator()(Square) const
2724  {
2725  search->proofOracleAttack<P,UseTable>(oracle, proof_limit);
2726  }
2727 };
2728 
2729 template <osl::Player P, bool UseTable>
2731 {
2735  CallProofOracleDefense(Dfpn *s, const ProofOracle& o, int pl) : search(s), oracle(o), proof_limit(pl)
2736  {
2737  }
2738  void operator()(Square) const
2739  {
2741  }
2742 };
2743 
2744 template <osl::Player P, bool UseTable>
2746 Dfpn::proofOracleAttack(const ProofOracle& key, int proof_limit)
2747 {
2748 #ifdef DFPN_DEBUG
2749  Tree::Logging logging(tree.get(), table, UseTable ? "tpatta" : "pattac");
2750 #endif
2751  assert(! tree->inCheck(alt(P)));
2752  const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
2753  Node& node = tree->node[tree->depth];
2754  DfpnRecord& record = node.record;
2755  LoopToDominance loop;
2756  DfpnVisitLock<UseTable> lk((node.path_record = (UseTable ? path_table->allocate<P>(node.hash_key, my_distance, loop) : 0)));
2757  if (UseTable && loop == BadAttackLoop) {
2758  record = DfpnRecord();
2759  node.setLoopDetection();
2760  return;
2761  }
2762  assert(node.white_stand == PieceStand(WHITE, tree->state));
2763  const size_t node_count_org = node_count++;
2764  if (node_count_limit == root_proof_simulation_limit
2765  && node_count > 100000) {
2766  std::cerr << "dfpn proof simulation > 100000 throw " << thread_id << "\n";
2767  throw DepthLimitReached();
2768  }
2769  assert(tree->depth + 2 < tree->MaxDepth);
2770  if (tree->depth + 2 >= tree->MaxDepth) {
2771  std::cerr << "throw " << thread_id << "\n";
2772  throw DepthLimitReached();
2773  }
2774  record = table->probe<P>(node.hash_key, node.white_stand);
2775  if (record.proof_disproof.isFinal())
2776  return;
2777 #if (defined CHECKMATE_A3_SIMULLATION) || (defined CHECKMATE_A3)
2778  if (record.node_count == 0)
2779  {
2780 #ifdef DFPN_STAT
2781  static stat::Ratio oracle_success("a3-simulation");
2782 #endif
2783  FixedDepthSolverExt fixed_solver(tree->state);
2784  PieceStand proof_pieces;
2785  ProofDisproof pdp = fixed_solver.hasCheckmateMove<P>(2, record.best_move, proof_pieces);
2786  ++node_count;
2787 #ifdef DFPN_STAT
2788  oracle_success.add(pdp.isCheckmateSuccess());
2789 #endif
2790  if (pdp.isCheckmateSuccess()) {
2791  record.proof_disproof = pdp;
2792  record.setProofPieces(proof_pieces);
2793  record.node_count++;
2794  return;
2795  }
2796  }
2797 #elif (!defined CHECKMATE_D2) && (!defined NO_IMMEDIATE_CHECKMATE)
2798  if (! tree->inCheck(P)
2799  && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.best_move)) {
2800  PieceStand proof_pieces; // Note: ImmediateCheckmate が合駒が必要な王手を使わないことに依存
2801  if (record.best_move.isDrop())
2802  proof_pieces.add(record.best_move.ptype());
2803  record.setProofPieces(proof_pieces);
2805  return;
2806  }
2807 #endif
2808 #ifdef DFPN_DEBUG
2809  if (tree->depth > 1000) {
2810  std::cerr << tree->state;
2811  node.hash_key.dumpContents(std::cerr);
2812  std::cerr << "\n";
2813  table->showProofOracles<P>(key.key, key.white_stand, node.moved);
2814  }
2815 #endif
2816  DfpnRecord oracle = table->findProofOracle<P>(key.key, key.white_stand, node.moved);
2817  if (! oracle.proof_disproof.isCheckmateSuccess() || ! oracle.best_move.isNormal())
2818  return;
2819  const Move check_move = OracleAdjust::attack(tree->state, oracle.best_move);
2820  if (! check_move.isNormal() || ! key.traceable(P, check_move))
2821  return;
2822 
2823  node.allocate(1);
2824  node.moves.clear();
2825  node.moves.push_back(check_move);
2826  const HashKey new_key = node.hash_key.newHashWithMove(node.moves[0]);
2827  if (UseTable) {
2828  node.children[0] = table->probe<P>(new_key, node.nextWhiteStand(P, node.moves[0]));
2829  node.children_path[0] = path_table->probe(new_key);
2830  if (node.isLoop(0))
2831  return;
2832  } else {
2833  node.children[0] = DfpnRecord();
2834  node.children_path[0] = 0;
2835  }
2836 
2837  if (! UseTable || ! node.children[0].proof_disproof.isFinal()) {
2838  Node& next = tree->node[tree->depth+1];
2839  tree->newVisit(P, node.moves[0], new_key);
2840 
2841  CallProofOracleDefense<P,UseTable> helper(this, key.newOracle(P, check_move), proof_limit);
2842  tree->depth += 1;
2843  next.path.pushMove(next.moved);
2844  tree->state.makeUnmakeMove(Player2Type<P>(), next.moved, helper);
2845  tree->depth -= 1;
2846  node.children[0] = next.record;
2847  node.children_path[0] = next.path_record;
2848 
2850  && next.moved.isDrop() && next.moved.ptype() == PAWN)
2851  node.children[0].proof_disproof = ProofDisproof::PawnCheckmate();
2852  }
2853  if (node.children[0].proof_disproof.isCheckmateSuccess()) {
2854  node.setCheckmateAttack(P,0);
2855  record.node_count += node_count - node_count_org;
2856  if (UseTable || node_count - node_count_org > 32) {
2857  record.last_move = node.moved;
2858  table->store(node.hash_key, record);
2859  }
2860  }
2861  else if (UseTable) {
2862  // dag analyses
2863  if (record.last_move.isNormal() && record.last_move != node.moved
2864  && std::max(record.proof(), record.disproof()) >= 128)
2865  findDagSource();
2866  record.last_move = node.moved;
2867  }
2868 }
2869 
2870 template <osl::Player P, bool UseTable>
2872 Dfpn::proofOracleDefense(const ProofOracle& key, int proof_limit)
2873 {
2874 #ifdef DFPN_DEBUG
2875  Tree::Logging logging(tree.get(), table, UseTable ? "tpdefe" : "pdefen");
2876 #endif
2877  const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
2878  Node& node = tree->node[tree->depth];
2879  LoopToDominance loop;
2880  DfpnVisitLock<UseTable> lk((node.path_record = (UseTable ? path_table->allocate<P>(node.hash_key, my_distance, loop) : 0)));
2881  DfpnRecord& record = node.record;
2882  if (UseTable && loop == BadAttackLoop) {
2883  record = DfpnRecord();
2884  node.setLoopDetection();
2885  return;
2886  }
2887  if (! UseTable && tree->depth >= 4) {
2888  if (tree->node[tree->depth-4].hash_key == node.hash_key
2889  || (tree->depth >= 6 && tree->node[tree->depth-6].hash_key == node.hash_key)) {
2890  record = DfpnRecord();
2891  return;
2892  }
2893  }
2894  const size_t node_count_org = node_count++;
2895  assert(node.white_stand == PieceStand(WHITE, tree->state));
2896  if (! tree->inCheck(alt(P)) || tree->inCheck(P)) {
2897  record = DfpnRecord();
2899  return;
2900  }
2901 
2902  record = table->probe<P>(node.hash_key, node.white_stand);
2903  if (record.proof_disproof.isFinal())
2904  return;
2905  if (proof_limit > ProofSimulationTolerance)
2906  proof_limit = ProofSimulationTolerance;
2907  // move generation
2908  const bool grand_parent_simulation = grandParentSimulationSuitable();
2909  if (record.last_to == Square())
2910  record.last_to = grand_parent_simulation ? node.moved.to() : tree->king(alt(P)).square();
2911  const Square grand_parent_delay_last_to
2912  = (record.last_to != tree->king(alt(P)).square()) ? record.last_to : Square();
2913  generateEscape<P>(tree->state, true, grand_parent_delay_last_to, node.moves);
2914  if (node.moves.empty()) {
2915  record.setProofPieces(ProofPieces::leaf(tree->state, P, record.stands[P]));
2917  return;
2918  }
2919 
2920  // probe all
2921  assert(node.children.empty());
2922  {
2923  node.allocate(node.moves.size());
2924  for (size_t i=0;i <node.moves.size(); ++i) {
2925 #ifdef MEMORIZE_SOLVED_IN_BITSET
2926  if (record.solved & (1ull << i))
2927  continue;
2928 #endif
2929  const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
2930  node.children[i] = UseTable
2931  ? table->probe<P>(new_key, node.nextWhiteStand(alt(P), node.moves[i]))
2932  : DfpnRecord();
2933  if (node.children[i].proof_disproof.isCheckmateSuccess()) {
2935  }
2936 #ifdef CHECKMATE_D2
2937  else if (node.record.node_count == 0 && node.children[i].node_count == 0) {
2938  FixedDepthSolverExt fixed_solver(tree->state);
2939  PieceStand proof_pieces;
2940  Move check_move;
2941  node.children[i].proof_disproof
2942  = fixed_solver.hasEscapeByMove<P>(node.moves[i], 0, check_move, proof_pieces);
2943  if (node.children[i].proof_disproof.isCheckmateSuccess()) {
2944  node.children[i].best_move = check_move;
2945  node.children[i].setProofPieces(proof_pieces);
2947  }
2948  else {
2949  if (node.children[i].proof_disproof.isCheckmateFail())
2950  node.children[i].proof_disproof = ProofDisproof(1,1);
2951  }
2952  ++node_count;
2953  }
2954 #endif
2955  if (node.children[i].proof_disproof.isCheckmateFail()) {
2956  tree->setNoCheckmateDefense(P, i);
2957  if (UseTable)
2958  table->store(node.hash_key, record);
2959  return;
2960  }
2961  node.children_path[i] = UseTable ? path_table->probe(new_key) : 0;
2962  }
2963  }
2964  assert(node.children.size() == node.moves.size());
2965  if (UseTable) {
2966  for (size_t i=0; i<node.children.size(); ++i) {
2967  if (node.isLoop(i)) {
2968  node.setLoopDetection();
2969  return;
2970  }
2971  }
2972  }
2973  unsigned int sum_proof=0, min_disproof=record.min_pdp;
2974  int num_proof = 0;
2975  for (size_t next_i=0; next_i<node.children.size(); ++next_i) {
2976 #ifdef MEMORIZE_SOLVED_IN_BITSET
2977  if (record.solved & (1ull << next_i))
2978  continue;
2979 #endif
2980  if (node.children[next_i].proof_disproof.isCheckmateSuccess()) {
2981  min_disproof = std::min(min_disproof, node.children[next_i].disproof());
2982  continue;
2983  }
2984  if (! key.traceable(alt(P), node.moves[next_i])) {
2985  ++sum_proof;
2986  min_disproof = 1;
2987  if (! UseTable)
2988  break;
2989  continue;
2990  }
2991  const Square next_to = node.moves[next_i].to();
2992  if (sum_proof && tree->state.hasEffectAt(P, next_to)
2993  && (! tree->state.hasEffectAt(alt(P), next_to)
2994  || (tree->state.countEffect(alt(P), next_to) == 1
2995  && ! node.moves[next_i].isDrop())))
2996  continue;
2997  assert(! node.isLoop(next_i));
2998  Node& next = tree->node[tree->depth+1];
2999 #ifdef MEMORIZE_SOLVED_IN_BITSET
3000  assert(! (record.solved & (1ull << next_i)));
3001 #endif
3002  tree->newVisit(alt(P), node.moves[next_i], node.hashes[next_i]);
3003 
3004  CallProofOracleAttack<P,UseTable> helper(this, key.newOracle(alt(P), node.moves[next_i]), proof_limit-sum_proof);
3005  tree->depth += 1;
3006  next.path.pushMove(node.moves[next_i]);
3007  tree->state.makeUnmakeMove(Player2Type<alt(P)>(), node.moves[next_i], helper);
3008  tree->depth -= 1;
3009 
3010  node.children[next_i] = next.record;
3011  node.children_path[next_i] = next.path_record;
3012  if (next.record.proof_disproof.isCheckmateFail()) {
3013  if (record.proof_disproof.isLoopDetection())
3014  node.setLoopDetection();
3015  else
3016  tree->setNoCheckmateDefense(P, next_i);
3017  record.node_count += node_count - node_count_org;
3018  if (UseTable)
3019  table->store(node.hash_key, record);
3020  return;
3021  }
3023  node.setCheckmateChildInDefense(next_i);
3024  ++num_proof;
3025  }
3026  sum_proof += next.record.proof();
3027  min_disproof = std::min(min_disproof, next.record.disproof());
3028  if ((sum_proof && ! UseTable) || (int)sum_proof > proof_limit)
3029  break;
3030  }
3031  if (sum_proof == 0) {
3032  node.record.proof_disproof = ProofDisproof(sum_proof, min_disproof);
3033  node.setCheckmateDefense(P, tree->state);
3034  }
3035  else if (UseTable) {
3036  // dag analyses
3037  if (record.last_move.isNormal() && record.last_move != node.moved
3038  && std::max(record.proof(), record.disproof()) >= 128)
3039  findDagSource();
3040  record.last_move = node.moved;
3041  }
3042 }
3043 
3044 template <osl::Player P>
3046 Dfpn::blockingSimulation(int oracle_i, const ProofOracle& oracle)
3047 {
3048 #ifdef DFPN_DEBUG
3049  Tree::Logging logging(tree.get(), table, "blocks");
3050 #endif
3051 #ifdef DFPN_STAT
3052  static stat::Ratio oracle_success("blocking proof");
3053 #endif
3054  Node& node = tree->node[tree->depth];
3055  Node& next = tree->node[tree->depth+1];
3056  const Move oracle_move = node.moves[oracle_i];
3057  const Square to = oracle_move.to();
3058  assert((node.record.solved & (1ull << oracle_i))
3059  || node.children[oracle_i].proof_disproof.isCheckmateSuccess());
3060  for (size_t i=0; i<node.moves.size(); ++i) {
3061 #ifdef MEMORIZE_SOLVED_IN_BITSET
3062  if (node.record.solved & (1ull << i))
3063  continue;
3064 #endif
3065  if (node.isLoop(i))
3066  break;
3067  if (node.children[i].proof_disproof.isFinal() || node.moves[i].to() != to)
3068  continue;
3069  if (! oracle.traceable(alt(P), node.moves[i]))
3070  continue;
3071 #ifdef MEMORIZE_SOLVED_IN_BITSET
3072  assert(! (node.record.solved & (1ull << i)));
3073 #endif
3074  tree->newVisit(alt(P), node.moves[i], node.hashes[i]);
3075  CallProofOracleAttack<P,true> helper(this, oracle, node.threshold.proof());
3076 
3077  tree->depth += 1;
3078  next.path.pushMove(node.moves[i]);
3079  tree->state.makeUnmakeMove(Player2Type<alt(P)>(), node.moves[i], helper);
3080  tree->depth -= 1;
3081 
3082  node.children[i] = next.record;
3083  node.children_path[i] = next.path_record;
3084 
3085 #ifdef DFPN_STAT
3086  oracle_success.add(next.record.proof_disproof.isCheckmateSuccess());
3087 #endif
3090  }
3091  }
3092 }
3093 
3094 template <osl::Player P>
3096 Dfpn::grandParentSimulation(int cur_i, const Node& gparent, int gp_i)
3097 {
3098 #ifdef DFPN_DEBUG
3099  Tree::Logging logging(tree.get(), table, "grands");
3100 #endif
3101 #ifdef DFPN_STAT
3102  static stat::Ratio oracle_success("grandparent proof", true);
3103 #endif
3104  Node& node = tree->node[tree->depth];
3105  Node& next = tree->node[tree->depth+1];
3106 
3107  const Move move = gparent.moves[gp_i];
3108  assert(move == node.moves[cur_i]);
3109  const HashKey& oracle_hash = (gparent.record.solved & (1ull << gp_i))
3110  ? gparent.hash_key.newHashWithMove(move)
3111  : gparent.hashes[gp_i];
3112  const ProofOracle oracle(oracle_hash, gparent.nextWhiteStand(alt(P), move));
3113 
3114  tree->newVisit(alt(P), node.moves[cur_i], node.hashes[cur_i]);
3115  CallProofOracleAttack<P,true> helper(this, oracle, gparent.threshold.proof());
3116 
3117  tree->depth += 1;
3118  next.path.pushMove(move);
3119  tree->state.makeUnmakeMove(Player2Type<alt(P)>(), move, helper);
3120  tree->depth -= 1;
3121 
3122  node.children[cur_i] = next.record;
3123  node.children_path[cur_i] = next.path_record;
3124 #ifdef DFPN_STAT
3125  oracle_success.add(next.record.proof_disproof.isCheckmateSuccess());
3126 #endif
3127 }
3128 
3129 // debug
3131 Dfpn::distance(const HashKey& key) const
3132 {
3133  const DfpnPathRecord *record = path_table->probe(key);
3134  if (record)
3135  return record->distance;
3136  return -1;
3137 }
3138 
3139 /* ------------------------------------------------------------------------- */
3140 // ;;; Local Variables:
3141 // ;;; mode:c++
3142 // ;;; c-basic-offset:2
3143 // ;;; End:
iterator begin()
Definition: container.h:64
bool hasUnblockableEffect() const
短い利きがある.長い利きの隣も含む
Definition: effectContent.h:38
size_t size() const
Definition: container.h:243
void push_back(const T &e)
Definition: container.h:204
圧縮していない moveの表現 .
Definition: basic_type.h:1052
bool isPromotion() const
Definition: basic_type.h:1147
Ptype ptype() const
Definition: basic_type.h:1155
Player player() const
Definition: basic_type.h:1195
bool isDrop() const
Definition: basic_type.h:1150
bool isNormal() const
INVALID でも PASS でもない.
Definition: basic_type.h:1088
bool isCapture() const
Definition: basic_type.h:1148
const Square to() const
Definition: basic_type.h:1132
const Square from() const
Definition: basic_type.h:1125
利きを持つ局面
bool hasEffectNotBy(Player player, Piece piece, Square target) const
対象とするマスにあるプレイヤーの(ただしある駒以外)利きがあるかどうか.
void makeMove(Move move)
int countEffect(Player player, Square target) const
利きの数を数える.
bool isAlmostValidMove(Move move) const
合法手かどうかを簡単に検査する.局面に依存するチェックのみ. ルール上指せない手である可能性がある場合は,isValidMove を用いる.
bool hasEffectAt(Square target) const
対象とするマスにあるプレイヤーの利きがあるかどうか.
bool inUnblockableCheck(Player target) const
target の王に合駒可能でない王手がかかっているかどうか.
bool inCheck(Player P) const
Pの玉が王手状態
PieceMask pinOrOpen(Player king) const
差が uniqになるような座標の差分.
Definition: offset32.h:17
int getDepth() const
Definition: pathEncoding.h:70
void pushMove(Move m)
Definition: pathEncoding.h:57
片方の手番の持駒の枚数を記録するクラス.
void add(Ptype type, unsigned int num=1)
const PieceStand nextStand(Player pl, Move move) const
bool isSuperiorOrEqualTo(PieceStand other) const
const PieceStand max(PieceStand other) const
種類毎に this と other の持駒の多い方を取る
const PieceStand previousStand(Player pl, Move move) const
int number() const
Definition: basic_type.h:828
const EffectContent getEffect(PtypeO ptypeo, Square from, Square to) const
fromにいるptypeoがtoに利きを持つか?
Definition: ptypeTable.h:112
const Piece kingPiece() const
Definition: simpleState.h:83
Player turn() const
Definition: simpleState.h:220
Square kingSquare() const
Definition: simpleState.h:94
const Piece pieceAt(Square sq) const
Definition: simpleState.h:167
unsigned int index() const
Definition: basic_type.h:572
bool isPieceStand() const
Definition: basic_type.h:576
int y() const
将棋としてのY座標を返す.
Definition: basic_type.h:567
int x() const
将棋としてのX座標を返す.
Definition: basic_type.h:563
unsigned int square
Definition: basic_type.h:533
size_t size() const
Definition: dfpn.cc:309
std::unordered_map< BoardKey, DfpnPathList, std::hash< BoardKey > > table_t
Definition: dfpn.cc:271
const DfpnPathRecord * probe(const HashKey &key) const
Definition: dfpn.cc:286
DfpnPathRecord * allocate(const HashKey &key, int depth, LoopToDominance &loop)
Definition: dfpn.cc:280
void rehash(size_t bucket_size)
Definition: dfpn.cc:310
const PieceStand disproofPieces() const
Definition: dfpnRecord.h:103
CArray< PieceStand, 2 > stands
Definition: dfpnRecord.h:60
unsigned int disproof() const
Definition: dfpnRecord.h:79
void setFrom(const DfpnRecordBase &src)
Definition: dfpnRecord.h:65
unsigned int proof() const
Definition: dfpnRecord.h:78
const PieceStand proofPieces() const
Definition: dfpnRecord.h:98
void setDisproofPieces(PieceStand a)
Definition: dfpnRecord.h:89
void setProofPieces(PieceStand a)
Definition: dfpnRecord.h:80
詰探索局面表 – 並列でも共有する部分
Definition: dfpn.h:30
size_t size() const
Definition: dfpn.cc:1251
size_t growthLimit() const
Definition: dfpn.h:73
void setMaxDepth(int)
Definition: dfpn.cc:931
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition: dfpn.cc:1074
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
int maxDepth() const
Definition: dfpn.cc:936
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
Definition: dfpn.cc:1047
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
Definition: dfpn.cc:1061
Player attack() const
Definition: dfpn.cc:950
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
Definition: dfpn.cc:1117
void addDag(const HashKey &key, DfpnRecord &value)
Definition: dfpn.cc:1098
List * find(const HashKey &key, int subindex)
void showStats() const
Definition: dfpn.cc:921
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
Definition: dfpn.cc:912
void leaveWorking(const HashKey &key, int thread_id)
Definition: dfpn.cc:1140
const DfpnRecord probe(const HashKey &key, PieceStand white) const
void setAttack(Player)
Definition: dfpn.cc:942
size_t smallTreeGC(size_t threshold=10)
Definition: dfpn.cc:1191
詰探索
Definition: dfpn.h:107
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
Definition: dfpn.cc:1573
int distance(const HashKey &) const
Definition: dfpn.cc:3131
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
Definition: dfpn.cc:2105
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2746
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition: dfpn.cc:1469
static void sort(const NumEffectState &, DfpnMoveVector &)
Definition: dfpn.cc:1555
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
Definition: dfpn.cc:2651
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
Definition: dfpn.cc:3096
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
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
Definition: dfpn.cc:2162
void setIllegal(const HashKey &key, PieceStand white)
Definition: dfpn.cc:1311
void blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
Definition: dfpn.cc:3046
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2872
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
const ProofDisproof tryProofMain(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move)
void setTable(DfpnTable *new_table)
Definition: dfpn.cc:1296
void findDagSource()
Definition: dfpn.cc:1647
const King8Info resetEdgeFromLiberty(Player king_player, Square king, King8Info info) const
liberty から盤の淵(xかyが1か9)を取り除く.
const ProofDisproof hasEscapeByMove(Move next_move, int depth, Move &check_move, PieceStand &proof_pieces)
next_move を指して逃げられるかどうかを調べる
const ProofDisproof hasCheckmateMove(int depth, Move &best_move, PieceStand &proof_pieces)
stateがPから詰む局面かを返す.
敵玉の8近傍の状態を表す.
Definition: king8Info.h:29
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:17
static const ProofDisproof PawnCheckmate()
Definition: proofDisproof.h:77
static const ProofDisproof LoopDetection()
Definition: proofDisproof.h:78
static const ProofDisproof NoEscape()
Definition: proofDisproof.h:74
static const ProofDisproof NoCheckmate()
Definition: proofDisproof.h:76
@ PROOF_LIMIT
通常の証明数の上限
Definition: proofDisproof.h:41
@ DISPROOF_LIMIT
通常の反証数の上限
Definition: proofDisproof.h:39
unsigned int disproof() const
Definition: proofDisproof.h:85
unsigned int proof() const
Definition: proofDisproof.h:84
static const ProofDisproof Checkmate()
Definition: proofDisproof.h:75
詰までの手数を数える.
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
const PieceStand blackStand() const
Definition: hashKey.h:64
Player turn() const
Definition: hashKey.h:105
const BoardKey96 boardKey() const
Definition: hashKey.h:53
const HashKey newMakeMove(Move) const
Definition: hashKey.cc:69
const HashKey newHashWithMove(Move move) const
Definition: hashKey.cc:63
void dumpContents(std::ostream &os) const
Definition: hashKey.cc:38
const HashKey newUnmakeMove(Move) const
Definition: hashKey.cc:96
static std::pair< char, char > value(size_t key)
利きをつける手を生成 利きを持つstateでしか使えない.
void add(bool success)
Definition: ratio.h:22
#define OSL_WORDSIZE
Definition: config.h:6
#define ROOT_DISPROOF_TOL
root で打切る反証数の閾値
Definition: dfpn.cc:43
#define CHECKMATE_A3_GOLD
Definition: dfpn.cc:57
static const unsigned int NoPromoeIgnoreProofThreshold
Definition: dfpn.cc:71
static const unsigned int IgnoreUpwardProofThreshold
Definition: dfpn.cc:73
static const size_t GrowthLimitInfty
Definition: dfpn.cc:85
static const unsigned int DagFindThreshold2
Definition: dfpn.cc:82
static size_t timer
Definition: dfpn.cc:91
const size_t debug_time_start
Definition: dfpn.cc:92
static const unsigned int DagFindThreshold
Definition: dfpn.cc:81
static const int LongDropCount
Definition: dfpn.cc:65
static const int MaxDagTraceDepth
Definition: dfpn.cc:69
static const int EnableGCDepth
Definition: dfpn.cc:83
static const unsigned int NoPromoeIgnoreDisproofThreshold
Definition: dfpn.cc:72
static const size_t root_proof_simulation_limit
Definition: dfpn.cc:1408
#define ROOT_PROOF_TOL
root で打切る証明数の閾値
Definition: dfpn.cc:41
static const int SacrificeBlockCount
Definition: dfpn.cc:65
static const unsigned int IgnoreUpwardDisproofThreshold
Definition: dfpn.cc:74
static const int AdHocSumScale
Definition: dfpn.cc:84
static const int UpwardWeight
Definition: dfpn.cc:65
static const unsigned int InitialDominanceProofMax
Definition: dfpn.cc:76
static const unsigned int InitialDominanceDisproofMax
Definition: dfpn.cc:80
const int ProofSimulationTolerance
Definition: dfpn.cc:86
#define MEMORIZE_SOLVED_IN_BITSET
Definition: dfpn.cc:61
static const osl::CArray2d< int, 8, 16 > threshold
Definition: featureSet.cc:518
#define SCOPED_LOCK(lock, m)
Definition: lightMutex.h:176
EdgeTable Edge_Table
int slow_increase(uint32_t n)
Definition: dfpn.cc:104
int log2(uint32_t n)
Definition: dfpn.cc:100
int attackProofCost(Player attacker, const NumEffectState &state, Move move)
Definition: dfpn.cc:313
@ BadAttackLoop
Definition: dfpn.cc:182
const std::string show(Move)
Definition: csa.cc:133
int max(Player p, int v1, int v2)
Definition: evalTraits.h:84
int min(Player p, int v1, int v2)
Definition: evalTraits.h:92
int convert(Player P, int value)
Definition: evalTraits.h:116
BoardKey96 BoardKey
Definition: hashKey.h:151
void escape(std::string &str)
URIやFile systemとして使えるように、文字をescape.
Definition: usiRecord.cc:12
Ptype
駒の種類を4ビットでコード化する
Definition: basic_type.h:84
@ ROOK
Definition: basic_type.h:100
@ BISHOP
Definition: basic_type.h:99
@ PAWN
Definition: basic_type.h:95
@ KING
Definition: basic_type.h:93
@ PTYPE_EMPTY
Definition: basic_type.h:85
@ GOLD
Definition: basic_type.h:94
const PtypeTable Ptype_Table
Definition: tables.cc:97
Ptype unpromote(Ptype ptype)
ptypeがpromote後の型の時に,promote前の型を返す. promoteしていない型の時はそのまま返す
Definition: basic_type.h:157
bool isPromoted(Ptype ptype)
ptypeがpromote後の型かどうかのチェック
Definition: basic_type.h:137
constexpr int sign(Player player)
Definition: basic_type.h:23
Player
Definition: basic_type.h:8
@ WHITE
Definition: basic_type.h:10
@ BLACK
Definition: basic_type.h:9
@ HIRATE
Definition: simpleState.h:21
bool isMajor(Ptype ptype)
Definition: basic_type.h:185
constexpr Player alt(Player player)
Definition: basic_type.h:13
osl の実行環境に関する指定
Definition: oslConfig.h:19
static double memoryUseRatio()
Definition: oslConfig.h:64
iterator find(PieceStand black, LoopToDominance &loop)
Definition: dfpn.cc:188
static bool precious(const DfpnPathRecord &record, size_t threshold)
Definition: dfpn.cc:240
size_t runGC(size_t threshold)
Definition: dfpn.cc:246
std::forward_list< std::pair< PieceStand, DfpnPathRecord > > list_t
Definition: dfpn.cc:185
const DfpnPathRecord * probe(PieceStand black) const
Definition: dfpn.cc:232
DfpnPathRecord * allocate(PieceStand black, int depth, LoopToDominance &loop, size_t &size)
Definition: dfpn.cc:217
int distance
distance from root
Definition: dfpn.cc:154
static const int MaxDistance
Definition: dfpn.cc:151
SimpleTwinList twin_list
Definition: dfpn.cc:152
PieceStand proof_pieces_candidate
solved のmax
Definition: dfpnRecord.h:31
uint64_t solved
手番に否定的に結果が判明したリスト loop は除く
Definition: dfpnRecord.h:19
Move last_move
合流検知+simulation中の簡易 無限ループ回避
Definition: dfpnRecord.h:29
uint64_t dag_moves
合流を引き起こす指手一覧
Definition: dfpnRecord.h:22
size_t estimateNodeCount(const HashKey &key, bool dominance_max) const
Definition: dfpn.cc:828
std::forward_list< DfpnRecord > list_t
Definition: dfpn.cc:620
size_t smallTreeGC(size_t threshold)
Definition: dfpn.cc:739
bool store(DfpnRecord &value, int leaving_thread_id)
Definition: dfpn.cc:633
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white_stand, Move last_move) const
bool setWorking(const DfpnRecord &value, int thread_id)
Definition: dfpn.cc:689
const DfpnRecord probe(const HashKey &key, PieceStand white_stand) const
void addDag(DfpnRecord &value)
Definition: dfpn.cc:668
List(const List &src)
Definition: dfpn.cc:625
void showProofOracles(const HashKey &key, PieceStand white_stand, Move last_move) const
Definition: dfpn.cc:868
void leaveWorking(PieceStand black, int thread_id)
Definition: dfpn.cc:705
void testTable(const BoardKey &) const
Definition: dfpn.cc:719
DfpnVisitLock(const DfpnVisitLock &)=delete
DfpnVisitLock(DfpnPathRecord *r)
Definition: dfpn.cc:169
DfpnPathRecord * record
Definition: dfpn.cc:168
DfpnVisitLock & operator=(const DfpnVisitLock &)=delete
void operator()(Square) const
Definition: dfpn.cc:1265
void operator()(Square) const
Definition: dfpn.cc:1278
CallProofOracleAttack(Dfpn *s, const ProofOracle &o, int pl)
Definition: dfpn.cc:2720
CallProofOracleDefense(Dfpn *s, const ProofOracle &o, int pl)
Definition: dfpn.cc:2735
DfpnPathRecord * path_record
Definition: dfpn.cc:346
ProofDisproof threshold
Definition: dfpn.cc:341
CArray< HashKey, DfpnMaxUniqMoves > hashes
Definition: dfpn.cc:354
void setCheckmateDefense(Player attack, const NumEffectState &state)
Definition: dfpn.cc:424
const PieceStand nextWhiteStand(Player P, Move move) const
Definition: dfpn.cc:358
void setNoCheckmateAttack(Player attack, const NumEffectState &state)
Definition: dfpn.cc:436
void setNoCheckmateDefense(Player attack, int best_i)
Definition: dfpn.cc:412
FixedCapacityVector< DfpnRecord, DfpnMaxUniqMoves > children
Definition: dfpn.cc:352
void setCheckmateChildInDefense(size_t i)
Definition: dfpn.cc:446
void setNoCheckmateChildInAttack(size_t i)
Definition: dfpn.cc:456
FixedCapacityVector< int8_t, DfpnMaxUniqMoves > proof_cost
Definition: dfpn.cc:355
DfpnMoveVector moves
Definition: dfpn.cc:351
void setCheckmateAttack(Player attack, int best_i)
Definition: dfpn.cc:401
FixedCapacityVector< const DfpnPathRecord *, DfpnMaxUniqMoves > children_path
Definition: dfpn.cc:353
const PathEncoding newPath(int c) const
Definition: dfpn.cc:385
bool isLoop(int c) const
Definition: dfpn.cc:391
void allocate(int n)
Definition: dfpn.cc:370
const ProofOracle newOracle(Player P, Move move) const
Definition: dfpn.h:219
bool traceable(Player P, Move move) const
Definition: dfpn.h:225
bool inCheck(Player P) const
Definition: dfpn.cc:499
void newVisit(Player P, Move move, const HashKey &next_hash)
Definition: dfpn.cc:504
Tree(int max_depth)
Definition: dfpn.cc:482
void dump(int lines, int depth=0) const
Definition: dfpn.cc:526
NumEffectState state
Definition: dfpn.cc:473
void setNoCheckmateChildInAttack(size_t best_i)
Definition: dfpn.cc:516
boost::scoped_array< Node > node
Definition: dfpn.cc:479
const Piece king(Player P) const
Definition: dfpn.cc:503
void setNoCheckmateDefense(Player attack, int best_i)
Definition: dfpn.cc:521
static const PieceStand leaf(const SimpleState &state, Player defender, const PieceStand max)
static const PieceStand defense(const PieceStand prev, Move move, const PieceStand max)
static void attackH(Player attacker, const State &, King8Info, Move move, unsigned int &proof_number, unsigned int &disproof_number)
攻撃側の move に対する proof_number と disproof_number を予想する
static const Move attack(const NumEffectState &state, Move check_move)
Definition: oracleAdjust.h:14
static const CArray< signed char, PTYPE_SIZE > attack_sacrifice_cost
Definition: pieceCost.h:17
static void addMonopolizedPieces(const SimpleState &state, Player player, const PieceStand max, PieceStand &out)
alt(player) が持っていない種類の持駒を playerが持っていたら out に独占分を加算する.
static const PieceStand leaf(const NumEffectState &state, Player attacker, const PieceStand max)
Definition: proofPieces.h:14
static const PieceStand attack(const PieceStand prev, Move move, const PieceStand max)
Definition: proofPieces.h:24
static int countBit(Integer mask)
Definition: mask.h:160
指手を MoveVector に保管
Definition: move_action.h:16
static void generateCheapKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
Definition: escape_.h:136
static void generateKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
不成の受けは作成しないので必要な場合はユーザが作成
Definition: escape_.h:130