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
40 
41 #define ROOT_PROOF_TOL 65536ul*1024
42 
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;
166  DfpnVisitLock& operator=(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;
272  table_t table;
273  size_t total_size;
274  size_t gc_threshold;
275  public:
276  DfpnPathTable() : total_size(0), gc_threshold(10)
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--) {
373  proof_cost.push_back(0);
374  children.push_back(DfpnRecord());
375  children_path.push_back(0);
376  }
377  }
379  {
380  assert(! (record.proof_disproof.isFinal()
381  && ! record.proof_disproof.isLoopDetection()));
382  record.proof_disproof = ProofDisproof(1,1);
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());
405  record.proof_disproof = child.proof_disproof;
406  record.best_move = moves[best_i];
407  const PieceStand proof_pieces
408  = ProofPieces::attack(child.proofPieces(), record.best_move,
409  record.stands[attack]);
410  record.setProofPieces(proof_pieces);
411  }
412  void setNoCheckmateDefense(Player attack, int best_i)
413  {
414  DfpnRecord& child = children[best_i];
415  assert(child.proof_disproof.isCheckmateFail());
416  assert(! child.proof_disproof.isLoopDetection());
417  record.proof_disproof = child.proof_disproof;
418  record.best_move = moves[best_i];
419  const PieceStand disproof_pieces
420  = DisproofPieces::defense(child.disproofPieces(), record.best_move,
421  record.stands[alt(attack)]);
422  record.setDisproofPieces(disproof_pieces);
423  }
424  void setCheckmateDefense(Player attack, const NumEffectState& state)
425  {
426  assert(moves.size());
427  assert(record.proof_disproof.isCheckmateSuccess());
428  record.proof_disproof = ProofDisproof::Checkmate(); // prevent backup of NoEscape
429  PieceStand result = record.proof_pieces_candidate;
430  const Player defender = alt(attack);
431  if (! state.inUnblockableCheck(defender))
432  ProofPiecesUtil::addMonopolizedPieces(state, attack, record.stands[attack],
433  result);
434  record.setProofPieces(result);
435  }
436  void setNoCheckmateAttack(Player attack, const NumEffectState& state)
437  {
438  assert(moves.size());
439  assert(record.proof_disproof.isCheckmateFail());
440  assert(! record.proof_disproof.isLoopDetection());
441  PieceStand result = record.proof_pieces_candidate;
442  ProofPiecesUtil::addMonopolizedPieces(state, alt(attack), record.stands[alt(attack)],
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());
453  record.proof_pieces_candidate
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());
463  record.proof_pieces_candidate
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)) {
819  result.proof_disproof = ProofDisproof(std::min(proof_ll, InitialDominanceProofMax),
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 
904 {
905 }
908 {
909 }
910 
911 void osl::checkmate::
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 
920 void osl::checkmate::
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 
930 void osl::checkmate::
932 {
933  dfpn_max_depth = new_depth;
934 }
937 {
938  return dfpn_max_depth;
939 }
940 
941 void osl::checkmate::
943 {
944  assert(size() == 0);
945  for (int i=0; i<DIVSIZE; ++i)
946  table[i].attack = a;
947 }
948 
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>
1046 void osl::checkmate::
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 
1060 size_t osl::checkmate::
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 
1073 void osl::checkmate::
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 }
1097 void osl::checkmate::
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 
1116 void osl::checkmate::
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 }
1139 void osl::checkmate::
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 
1156 void osl::checkmate::
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 
1168 void osl::checkmate::
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 
1190 size_t osl::checkmate::
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 
1216 bool osl::checkmate::
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) {
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 
1250 size_t osl::checkmate::
1252 {
1253  return total_size;
1254 }
1255 
1256 /* ------------------------------------------------------------------------- */
1257 
1258 template <osl::Player P>
1260 {
1262  CallAttack(Dfpn *s) : search(s)
1263  {
1264  }
1265  void operator()(Square) const
1266  {
1267  search->attack<P>();
1268  }
1269 };
1270 
1271 template <osl::Player P>
1273 {
1275  CallDefense(Dfpn *s) : search(s)
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
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 
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 
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  }
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;
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 
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>
1554 void osl::checkmate::
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>
1572 void osl::checkmate::
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 
1605 void osl::checkmate::
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 
1646 void osl::checkmate::
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>
1655 void osl::checkmate::
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)));
1909  if (node.threshold.proof() < NoPromoeIgnoreProofThreshold
1910  && node.threshold.disproof() < NoPromoeIgnoreDisproofThreshold)
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>
2104 void osl::checkmate::
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 
2161 bool osl::checkmate::
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>
2182 void osl::checkmate::
2184 {
2185 #if 0
2186  if (parallel_shared) {
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  && (
2326 #ifdef MEMORIZE_SOLVED_IN_BITSET
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)
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)
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())
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  }
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())
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())
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)
2650 void osl::checkmate::
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  {
2740  search->proofOracleDefense<P,UseTable>(oracle, proof_limit);
2741  }
2742 };
2743 
2744 template <osl::Player P, bool UseTable>
2745 void osl::checkmate::
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++;
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>
2871 void osl::checkmate::
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  }
3022  if (next.record.proof_disproof.isCheckmateSuccess()) {
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>
3045 void osl::checkmate::
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>
3095 void osl::checkmate::
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
3130 int osl::checkmate::
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:
DfpnMoveVector moves
Definition: dfpn.cc:351
Ptype unpromote(Ptype ptype)
ptypeがpromote後の型の時に,promote前の型を返す. promoteしていない型の時はそのまま返す ...
Definition: basic_type.h:157
bool hasUnblockableEffect() const
短い利きがある.長い利きの隣も含む
Definition: effectContent.h:38
void push_back(const T &e)
Definition: container.h:204
int countEffect(Player player, Square target) const
利きの数を数える.
static const unsigned int IgnoreUpwardDisproofThreshold
Definition: dfpn.cc:74
iterator begin()
Definition: container.h:64
void setCheckmateDefense(Player attack, const NumEffectState &state)
Definition: dfpn.cc:424
static const PieceStand leaf(const SimpleState &state, Player defender, const PieceStand max)
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
int max(Player p, int v1, int v2)
Definition: evalTraits.h:84
bool isSuperiorOrEqualTo(PieceStand other) const
void add(Ptype type, unsigned int num=1)
static const PieceStand defense(const PieceStand prev, Move move, const PieceStand max)
const int ProofSimulationTolerance
Definition: dfpn.cc:86
iterator find(PieceStand black, LoopToDominance &loop)
Definition: dfpn.cc:188
bool hasEffectAt(Square target) const
対象とするマスにあるプレイヤーの利きがあるかどうか.
void restartThreads(const HashKey &key, int depth, unsigned int threads)
Definition: dfpnParallel.h:40
bool isMajor(Ptype ptype)
Definition: basic_type.h:185
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white_stand, Move last_move) const
void setDisproofPieces(PieceStand a)
Definition: dfpnRecord.h:89
PieceMask pinOrOpen(Player king) const
void setTable(DfpnTable *new_table)
Definition: dfpn.cc:1296
const HashKey newMakeMove(Move) const
Definition: hashKey.cc:69
const PieceStand disproofPieces() const
Definition: dfpnRecord.h:103
constexpr Player alt(Player player)
Definition: basic_type.h:13
int slow_increase(uint32_t n)
Definition: dfpn.cc:104
const BoardKey96 boardKey() const
Definition: hashKey.h:53
bool store(DfpnRecord &value, int leaving_thread_id)
Definition: dfpn.cc:633
const PathEncoding newPath(int c) const
Definition: dfpn.cc:385
static const unsigned int InitialDominanceProofMax
Definition: dfpn.cc:76
const ProofOracle newOracle(Player P, Move move) const
Definition: dfpn.h:219
int min(Player p, int v1, int v2)
Definition: evalTraits.h:92
bool inUnblockableCheck(Player target) const
target の王に合駒可能でない王手がかかっているかどうか.
static const ProofDisproof LoopDetection()
Definition: proofDisproof.h:78
void setCheckmateChildInDefense(size_t i)
Definition: dfpn.cc:446
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
static int countBit(Integer mask)
Definition: mask.h:160
void testTable(const BoardKey &) const
Definition: dfpn.cc:719
static const unsigned int InitialDominanceDisproofMax
Definition: dfpn.cc:80
static void generateKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
不成の受けは作成しないので必要な場合はユーザが作成
Definition: escape_.h:130
EdgeTable Edge_Table
詰までの手数を数える.
bool inCheck(Player P) const
Definition: dfpn.cc:499
void addDag(DfpnRecord &value)
Definition: dfpn.cc:668
const Piece pieceAt(Square sq) const
Definition: simpleState.h:167
bool isNormal() const
INVALID でも PASS でもない.
Definition: basic_type.h:1088
bool traceable(Player P, Move move) const
Definition: dfpn.h:225
static const ProofDisproof PawnCheckmate()
Definition: proofDisproof.h:77
size_t growthLimit() const
Definition: dfpn.h:73
int y() const
将棋としてのY座標を返す.
Definition: basic_type.h:567
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
Definition: dfpn.cc:2105
List * find(const HashKey &key, int subindex)
static const ProofDisproof NoCheckmate()
Definition: proofDisproof.h:76
static const CArray< signed char, PTYPE_SIZE > attack_sacrifice_cost
Definition: pieceCost.h:17
size_t node_count_limit
Definition: dfpn.h:122
uint64_t dag_moves
合流を引き起こす指手一覧
Definition: dfpnRecord.h:22
bool test(int num) const
Definition: pieceMask.h:45
static const int UpwardWeight
Definition: dfpn.cc:65
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
Definition: dfpn.cc:2162
static const int LongDropCount
Definition: dfpn.cc:65
const PieceStand nextStand(Player pl, Move move) const
const PieceStand blackStand() const
Definition: hashKey.h:64
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 blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
Definition: dfpn.cc:3046
static const PieceStand attack(const PieceStand prev, Move move, const PieceStand max)
Definition: proofPieces.h:24
int x() const
将棋としてのX座標を返す.
Definition: basic_type.h:563
FixedCapacityVector< int8_t, DfpnMaxUniqMoves > proof_cost
Definition: dfpn.cc:355
static const size_t root_proof_simulation_limit
Definition: dfpn.cc:1408
Offset32Base< 8, 9 > Offset32
Definition: offset32.h:63
std::forward_list< std::pair< PieceStand, DfpnPathRecord > > list_t
Definition: dfpn.cc:185
void setAttack(Player)
Definition: dfpn.cc:942
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
詰探索局面表 – 並列でも共有する部分
Definition: dfpn.h:29
int distance
distance from root
Definition: dfpn.cc:154
PieceStand proof_pieces_candidate
solved のmax
Definition: dfpnRecord.h:31
static const unsigned int NoPromoeIgnoreProofThreshold
Definition: dfpn.cc:71
void findDagSource()
Definition: dfpn.cc:1647
#define CHECKMATE_A3_GOLD
Definition: dfpn.cc:57
Ptype
駒の種類を4ビットでコード化する
Definition: basic_type.h:83
static const int DIVSIZE
Definition: dfpn.h:88
void allocate(int n)
Definition: dfpn.cc:370
List(const List &src)
Definition: dfpn.cc:625
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
Definition: dfpn.cc:1061
void showProofOracles(const HashKey &key, PieceStand white_stand, Move last_move) const
Definition: dfpn.cc:868
FixedCapacityVector< DfpnRecord, DfpnMaxUniqMoves > children
Definition: dfpn.cc:352
Square kingSquare() const
Definition: simpleState.h:94
Ptype ptype() const
Definition: basic_type.h:1155
static const int EnableGCDepth
Definition: dfpn.cc:83
boost::scoped_array< Table > table
Definition: dfpn.h:32
static const unsigned int IgnoreUpwardProofThreshold
Definition: dfpn.cc:73
int convert(Player P, int value)
Definition: evalTraits.h:116
unsigned int proof() const
Definition: proofDisproof.h:84
const PtypeTable Ptype_Table
Definition: tables.cc:97
指手を MoveVector に保管
Definition: move_action.h:15
static std::pair< char, char > value(size_t key)
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
Definition: dfpn.cc:3096
#define OSL_WORDSIZE
Definition: config.h:6
ProofDisproof threshold
Definition: dfpn.cc:341
int attackProofCost(Player attacker, const NumEffectState &state, Move move)
Definition: dfpn.cc:313
CallProofOracleAttack(Dfpn *s, const ProofOracle &o, int pl)
Definition: dfpn.cc:2720
const Square from() const
Definition: basic_type.h:1125
const DfpnPathRecord * probe(PieceStand black) const
Definition: dfpn.cc:232
圧縮していない moveの表現 .
Definition: basic_type.h:1051
unsigned int disproof() const
Definition: dfpnRecord.h:79
const DfpnPathRecord * probe(const HashKey &key) const
Definition: dfpn.cc:286
DfpnShared * parallel_shared
Definition: dfpn.h:123
void leaveWorking(PieceStand black, int thread_id)
Definition: dfpn.cc:705
static const unsigned int DagFindThreshold
Definition: dfpn.cc:81
static void addMonopolizedPieces(const SimpleState &state, Player player, const PieceStand max, PieceStand &out)
alt(player) が持っていない種類の持駒を playerが持っていたら out に独占分を加算する. ...
static void attackH(Player attacker, const State &, King8Info, Move move, unsigned int &proof_number, unsigned int &disproof_number)
攻撃側の move に対する proof_number と disproof_number を予想する
const EffectContent getEffect(PtypeO ptypeo, Square from, Square to) const
fromにいるptypeoがtoに利きを持つか?
Definition: ptypeTable.h:112
void setProofPieces(PieceStand a)
Definition: dfpnRecord.h:80
void setNoCheckmateDefense(Player attack, int best_i)
Definition: dfpn.cc:521
敵玉の8近傍の状態を表す.
Definition: king8Info.h:28
static const osl::CArray2d< int, 8, 16 > threshold
Definition: featureSet.cc:518
const PieceStand previousStand(Player pl, Move move) const
unsigned int moves() const
Definition: king8Info.h:77
size_t smallTreeGC(size_t threshold)
Definition: dfpn.cc:739
void setNoCheckmateChildInAttack(size_t best_i)
Definition: dfpn.cc:516
Move last_move
合流検知+simulation中の簡易 無限ループ回避
Definition: dfpnRecord.h:29
void makeMove(Move move)
unsigned int index() const
Definition: basic_type.h:572
Player player() const
Definition: basic_type.h:1195
DfpnTable * table
Definition: dfpn.h:115
#define SCOPED_LOCK(lock, m)
Definition: lightMutex.h:176
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
Definition: dfpn.cc:1047
static const int AdHocSumScale
Definition: dfpn.cc:84
static bool precious(const DfpnPathRecord &record, size_t threshold)
Definition: dfpn.cc:240
Player turn() const
Definition: simpleState.h:220
osl の実行環境に関する指定
Definition: oslConfig.h:18
bool isAlmostValidMove(Move move) const
合法手かどうかを簡単に検査する.局面に依存するチェックのみ. ルール上指せない手である可能性がある場合...
#define ROOT_DISPROOF_TOL
root で打切る反証数の閾値
Definition: dfpn.cc:43
constexpr int sign(Player player)
Definition: basic_type.h:23
int distance(const HashKey &) const
Definition: dfpn.cc:3131
CArray< HashKey, DfpnMaxUniqMoves > hashes
Definition: dfpn.cc:354
bool setWorking(const DfpnRecord &value, int thread_id)
Definition: dfpn.cc:689
DfpnPathRecord * allocate(PieceStand black, int depth, LoopToDominance &loop, size_t &size)
Definition: dfpn.cc:217
#define MEMORIZE_SOLVED_IN_BITSET
Definition: dfpn.cc:61
#define ROOT_PROOF_TOL
root で打切る証明数の閾値
Definition: dfpn.cc:41
CArray< PieceStand, 2 > stands
Definition: dfpnRecord.h:60
const Piece king(Player P) const
Definition: dfpn.cc:503
DfpnPathRecord * allocate(const HashKey &key, int depth, LoopToDominance &loop)
Definition: dfpn.cc:280
size_t smallTreeGC(size_t threshold=10)
Definition: dfpn.cc:1191
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
Definition: dfpn.cc:2651
static void sort(const NumEffectState &, DfpnMoveVector &)
Definition: dfpn.cc:1555
BoardKey96 BoardKey
Definition: hashKey.h:151
利きを持つ局面
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition: dfpn.cc:1469
bool inCheck(Player P) const
Pの玉が王手状態
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition: dfpn.cc:1074
const PieceStand nextWhiteStand(Player P, Move move) const
Definition: dfpn.cc:358
void setNoCheckmateDefense(Player attack, int best_i)
Definition: dfpn.cc:412
size_t runGC(size_t threshold)
Definition: dfpn.cc:246
static const ProofDisproof NoEscape()
Definition: proofDisproof.h:74
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2872
const ProofDisproof hasEscapeByMove(Move next_move, int depth, Move &check_move, PieceStand &proof_pieces)
next_move を指して逃げられるかどうかを調べる
static const Move attack(const NumEffectState &state, Move check_move)
Definition: oracleAdjust.h:14
DfpnPathRecord * record
Definition: dfpn.cc:168
Tree(int max_depth)
Definition: dfpn.cc:482
size_t size() const
Definition: container.h:243
CallProofOracleDefense(Dfpn *s, const ProofOracle &o, int pl)
Definition: dfpn.cc:2735
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
void escape(std::string &str)
URIやFile systemとして使えるように、文字をescape.
Definition: usiRecord.cc:12
詰探索
Definition: dfpn.h:106
void setFrom(const DfpnRecordBase &src)
Definition: dfpnRecord.h:65
bool isDrop() const
Definition: basic_type.h:1150
const HashKey newHashWithMove(Move move) const
Definition: hashKey.cc:63
const Square to() const
Definition: basic_type.h:1132
unsigned int proof() const
Definition: dfpnRecord.h:78
void setIllegal(const HashKey &key, PieceStand white)
Definition: dfpn.cc:1311
void leaveWorking(const HashKey &key, int thread_id)
Definition: dfpn.cc:1140
const PieceStand proofPieces() const
Definition: dfpnRecord.h:98
void operator()(Square) const
Definition: dfpn.cc:1278
static size_t timer
Definition: dfpn.cc:91
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
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:16
size_t size() const
Definition: dfpn.cc:309
void newVisit(Player P, Move move, const HashKey &next_hash)
Definition: dfpn.cc:504
size_t node_count
Definition: dfpn.h:121
void dump(int lines, int depth=0) const
Definition: dfpn.cc:526
void setNoCheckmateChildInAttack(size_t i)
Definition: dfpn.cc:456
const std::string show(Move)
Definition: csa.cc:133
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2746
void rehash(size_t bucket_size)
Definition: dfpn.cc:310
bool isPromoted(Ptype ptype)
ptypeがpromote後の型かどうかのチェック
Definition: basic_type.h:137
const HashKey newUnmakeMove(Move) const
Definition: hashKey.cc:96
Player turn() const
Definition: hashKey.h:105
const DfpnRecord probe(const HashKey &key, PieceStand white) const
bool isPromotion() const
Definition: basic_type.h:1147
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
Definition: dfpn.cc:1573
const ProofDisproof hasCheckmateMove(int depth, Move &best_move, PieceStand &proof_pieces)
stateがPから詰む局面かを返す.
static int keyToIndex(const HashKey &key)
Definition: dfpn.h:90
static void generateCheapKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
Definition: escape_.h:136
bool hasEffectNotBy(Player player, Piece piece, Square target) const
対象とするマスにあるプレイヤーの(ただしある駒以外)利きがあるかどうか.
DfpnPathRecord * path_record
Definition: dfpn.cc:346
Player
Definition: basic_type.h:8
利きをつける手を生成 利きを持つstateでしか使えない.
static const int MaxDistance
Definition: dfpn.cc:151
static const int MaxDagTraceDepth
Definition: dfpn.cc:69
const PieceStand max(PieceStand other) const
種類毎に this と other の持駒の多い方を取る
size_t size() const
Definition: dfpn.cc:1251
void setNoCheckmateAttack(Player attack, const NumEffectState &state)
Definition: dfpn.cc:436
通常の証明数の上限
Definition: proofDisproof.h:41
const Piece kingPiece() const
Definition: simpleState.h:83
static const ProofDisproof Checkmate()
Definition: proofDisproof.h:75
CArray< ThreadData, 32 > data
Definition: dfpnParallel.h:36
NumEffectState state
Definition: dfpn.cc:473
const King8Info resetEdgeFromLiberty(Player king_player, Square king, King8Info info) const
liberty から盤の淵(xかyが1か9)を取り除く.
static const size_t GrowthLimitInfty
Definition: dfpn.cc:85
static const unsigned int NoPromoeIgnoreDisproofThreshold
Definition: dfpn.cc:72
FixedCapacityVector< const DfpnPathRecord *, DfpnMaxUniqMoves > children_path
Definition: dfpn.cc:353
片方の手番の持駒の枚数を記録するクラス.
static const int SacrificeBlockCount
Definition: dfpn.cc:65
bool isPieceStand() const
Definition: basic_type.h:576
void showStats() const
Definition: dfpn.cc:921
void setCheckmateAttack(Player attack, int best_i)
Definition: dfpn.cc:401
bool isLoop(int c) const
Definition: dfpn.cc:391
void operator()(Square) const
Definition: dfpn.cc:1265
uint64_t solved
手番に否定的に結果が判明したリスト loop は除く
Definition: dfpnRecord.h:19
void dumpContents(std::ostream &os) const
Definition: hashKey.cc:38
std::unique_ptr< DfpnPathTable > path_table
Definition: dfpn.h:120
static const unsigned int DagFindThreshold2
Definition: dfpn.cc:82
void addDag(const HashKey &key, DfpnRecord &value)
Definition: dfpn.cc:1098
const size_t debug_time_start
Definition: dfpn.cc:92
SimpleTwinList twin_list
Definition: dfpn.cc:152
std::unordered_map< BoardKey, DfpnPathList, std::hash< BoardKey > > table_t
Definition: dfpn.cc:271
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
Definition: dfpn.cc:1117
void add(bool success)
Definition: ratio.h:22
static const PieceStand leaf(const NumEffectState &state, Player attacker, const PieceStand max)
Definition: proofPieces.h:14
int getDepth() const
Definition: pathEncoding.h:70
size_t estimateNodeCount(const HashKey &key, bool dominance_max) const
Definition: dfpn.cc:828
unsigned int disproof() const
Definition: proofDisproof.h:85
static double memoryUseRatio()
Definition: oslConfig.h:64
int log2(uint32_t n)
Definition: dfpn.cc:100
std::forward_list< DfpnRecord > list_t
Definition: dfpn.cc:620
bool blocking_verify
Definition: dfpn.h:125
boost::scoped_array< Node > node
Definition: dfpn.cc:479
std::unique_ptr< Tree > tree
Definition: dfpn.h:118
Player attack() const
Definition: dfpn.cc:950
void pushMove(Move m)
Definition: pathEncoding.h:57
const DfpnRecord probe(const HashKey &key, PieceStand white_stand) const
bool isCapture() const
Definition: basic_type.h:1148
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
Definition: dfpn.cc:912
int maxDepth() const
Definition: dfpn.cc:936
void setMaxDepth(int)
Definition: dfpn.cc:931
DfpnVisitLock(DfpnPathRecord *r)
Definition: dfpn.cc:169