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