All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
dualDfpn.cc
Go to the documentation of this file.
1 /* dualDfpn.cc
2  */
4 #include "osl/checkmate/dfpn.h"
6 #ifdef OSL_DFPN_SMP
8 #endif
10 #include "osl/stl/hash_map.h"
11 #include "osl/stl/slist.h"
12 #include "osl/stat/average.h"
13 #include "osl/centering3x3.h"
14 #include "osl/centering5x3.h"
15 #ifdef OSL_SMP
16 # include "osl/misc/lightMutex.h"
17 # include <boost/thread/condition.hpp>
18 #endif
19 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
20 # include "osl/stat/ratio.h"
21 #endif
22 #include "osl/misc/milliSeconds.h"
23 #include "osl/oslConfig.h"
24 #include <boost/foreach.hpp>
25 #include <iostream>
26 #include <iomanip>
27 
28 #define DFPN_SHARE_TABLE
29 
30 static const int max_oracle_list_size = 2;
31 static const size_t local_table_growth_limit = 40000;
33 {
34  struct Element
35  {
38  unsigned int id;
39  bool in_check;
40  Element() : oracle(HashKey(), PieceStand()), id((unsigned int)-1), in_check(false)
41  {
42  }
43  Element(const Dfpn::ProofOracle& o, PieceStand p, size_t i, bool c) : oracle(o), proof_pieces(p), id(i), in_check(c)
44  {
45  }
46  };
47  struct List : FixedCapacityVector<Element, max_oracle_list_size>
48  {
49  void add(const Element& e)
50  {
51  if (size() == capacity())
52  back() = e;
53  else
54  push_back(e);
55  }
56  };
57 #ifdef OSL_SMP
58  mutable boost::mutex mutex;
59 #endif
60  typedef hash_map<HashKey, List> table_t;
63  void setAttack(Player attack)
64  {
65  defender = alt(attack);
66  }
67  void addProof(const NumEffectState& state, const HashKey& key, PieceStand proof_pieces)
68  {
69  const Dfpn::ProofOracle oracle(key, PieceStand(WHITE, state));
70  const std::pair<HashKey,HashKey> king = makeLargeKey(state);
71 #ifdef OSL_SMP
72  boost::mutex::scoped_lock lk(mutex);;
73 #endif
74  const Element e(oracle, proof_pieces, table.size(), state.inCheck());
75  table[king.first].add(e);
76  table[king.second].add(e);
77  }
78  const List probe(const NumEffectState& state) const
79  {
80  const std::pair<HashKey,HashKey> key = makeLargeKey(state);
81 #ifdef OSL_SMP
82  boost::mutex::scoped_lock lk(mutex);;
83 #endif
84  table_t::const_iterator p = table.find(key.first);
85  if (p != table.end())
86  return p->second;
87  p = table.find(key.second);
88  if (p != table.end())
89  return p->second;
90  return List();
91  }
92 
93  template <Direction DIR>
94  static void addKey(HashKey& key, const SimpleState& state, Square target)
95  {
97  target += offset; // 8 近傍全て試すなら手番による符合変換は不要
98  const Piece piece = state.pieceOnBoard(target);
99  hash::Hash_Gen_Table.addHashKey(key, target, piece.ptypeO());
100  }
101  template <Direction DIR, Direction DIR2>
102  static void addKey(HashKey& key, const SimpleState& state, Square target)
103  {
106  target += offset;
107  const Piece piece = state.pieceOnBoard(target);
108  hash::Hash_Gen_Table.addHashKey(key, target, piece.ptypeO());
109  }
110  const HashKey makeKey(const SimpleState& state) const
111  {
112  const Square target_king=state.kingSquare(defender);
113  const Square center = Centering3x3::adjustCenter(target_king);
114  HashKey key;
115  hash::Hash_Gen_Table.addHashKey(key, center,
116  state.pieceOnBoard(center).ptypeO());
117  addKey<UL>(key, state, center); addKey<U> (key, state, center);
118  addKey<UR>(key, state, center);
119  addKey<L> (key, state, center); addKey<R> (key, state, center);
120  addKey<DL>(key, state, center); addKey<D> (key, state, center);
121  addKey<DR>(key, state, center);
122  return key;
123  }
124  const std::pair<HashKey,HashKey> makeLargeKey(const SimpleState& state) const
125  {
126  HashKey key_small = makeKey(state), key_large;
127  const Square target_king=state.kingSquare(defender);
128  const Square center = Centering5x3::adjustCenter(target_king);
129  hash::Hash_Gen_Table.addHashKey(key_large, center,
130  state.pieceOnBoard(center).ptypeO());
131  addKey<UL>(key_large, state, center); addKey<U> (key_large, state, center);
132  addKey<UR>(key_large, state, center);
133  addKey<L> (key_large, state, center); addKey<R> (key_large, state, center);
134  addKey<DL>(key_large, state, center); addKey<D> (key_large, state, center);
135  addKey<DR>(key_large, state, center);
136  addKey<L,UL>(key_large, state, center); addKey<L,L> (key_large, state, center);
137  addKey<L,DL>(key_large, state, center);
138  addKey<R,UR>(key_large, state, center); addKey<R,R> (key_large, state, center);
139  addKey<R,DR>(key_large, state, center);
140  return std::make_pair(key_large, key_small);
141  }
142 };
143 
145 {
146  CArray<DfpnTable,2> table;
147  CArray<OraclePool,2> pool;
150  volatile size_t last_gc, gc_threshold;
151  CArray<stat::Average,max_oracle_list_size> proof_by_oracle;
152  CArray<bool,2> blocking_verify;
153 #ifdef OSL_SMP
154  boost::mutex mutex;
155  boost::condition condition;
156  CArray<LightMutex,max_oracle_list_size> proof_by_oracle_mutex;
157 #endif
159 #ifdef OSL_DFPN_SMP
160  boost::scoped_ptr<DfpnParallel> parallel_search;
161 #endif
162  typedef slist<PathEncoding> disproof_list_t;
163  typedef hash_map<HashKey, disproof_list_t> disproof_table_t;
165 
168  {
169  table[BLACK].setAttack(BLACK);
170  table[WHITE].setAttack(WHITE);
171  pool[BLACK].setAttack(BLACK);
172  pool[WHITE].setAttack(WHITE);
173  blocking_verify.fill(true);
174  }
176  {
177  showStats();
178  }
179  void showStats()
180  {
182 #ifdef DFPN_DEBUG
183  std::cerr << "shared " << main_node_count << " " << simulation_count << "\n";
184  BOOST_FOREACH(stat::Average& a, proof_by_oracle)
185  std::cerr << a.getAverage()
186  << " " << (int)(a.getAverage()*a.numElements()) << "\n";
187  std::cerr << "oracles " << pool[BLACK].table.size() << " " << pool[WHITE].table.size() << "\n";
188  std::cerr << "table " << table[0].totalSize() << " " << table[1].totalSize() << "\n";
189  table[0].showStats();
190  table[1].showStats();
191 #endif
192  }
193  }
194  void addMainNodeCount(int add)
195  {
196 #ifdef OSL_SMP
197  boost::mutex::scoped_lock lk(mutex);;
198 #endif
199  main_node_count += add;
200  }
202  {
203 #ifdef OSL_SMP
204  boost::mutex::scoped_lock lk(mutex);;
205 #endif
206  simulation_count += add;
207  }
208  struct TableUseLock : boost::noncopyable
209  {
211  explicit TableUseLock(Shared *s) : shared(s)
212  {
213 # ifdef OSL_SMP
214  boost::mutex::scoped_lock lk(shared->mutex);
215  while (shared->shared_table_user < 0) // in gc
216  shared->condition.wait(lk);
218 # endif
219  }
221  {
222 # ifdef OSL_SMP
223  boost::mutex::scoped_lock lk(shared->mutex);
224  assert(shared->shared_table_user > 0);
227  shared->condition.notify_all();
228 # endif
229  }
230  };
231 };
232 
234 {
236 #ifndef DFPN_SHARE_TABLE
237  CArray<DfpnTable,2> table;
238 #endif
239  CArray<DfpnTable,2> table_small;
242  {
243 #ifndef DFPN_SHARE_TABLE
246 #endif
247  table_small[BLACK].setAttack(BLACK);
248  table_small[WHITE].setAttack(WHITE);
249  }
251  {
252 #ifdef DFPN_DEBUG
253  std::cerr << "local " << table_small[0].totalSize()
254  << " " << table_small[1].totalSize() << "\n";
255 #endif
256  }
257 };
258 
259 /* ------------------------------------------------------------------------- */
260 
262 DualDfpn::DualDfpn(uint64_t /*limit*/)
263  : shared(new Shared), local(new Local)
264 {
265 }
266 
269  : shared(src.shared), local(new Local)
270 {
271 }
272 
275 {
276 }
277 
280 {
281 #ifdef DFPN_SHARE_TABLE
282  local->dfpn.setTable(&(shared->table[attack]));
283 #else
284  local->dfpn.setTable(&(local->table[attack]));
285 #endif
286  local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
287  return local->dfpn;
288 }
289 
292 {
293  local->dfpn.setTable(&(local->table_small[attack]));
294  local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
295  return local->dfpn;
296 }
297 
298 void osl::checkmate::
299 DualDfpn::runGC(bool verbose, size_t memory_use_ratio_1000)
300 {
301 #ifdef DFPN_SHARE_TABLE
302  const size_t unit_size = (sizeof(HashKey)+sizeof(DfpnRecord)+sizeof(char*)*2);
303  size_t removed = 0;
304  size_t total = shared->table[BLACK].size() + shared->table[WHITE].size();
305  size_t current_use = memory_use_ratio_1000*(OslConfig::memoryUseLimit()/1000);
306  if (total < local_table_growth_limit*8
307  || total*unit_size*64 < OslConfig::memoryUseLimit()
308  || (total*unit_size*3 < current_use
309  && total*unit_size*8 < OslConfig::memoryUseLimit()))
310  return;
311  MilliSeconds start = MilliSeconds::now();
312  {
313  {
314 # ifdef OSL_SMP
315  boost::mutex::scoped_lock lk(shared->mutex);
316 # endif
317  total = shared->table[BLACK].size() + shared->table[WHITE].size();
318  if (total < local_table_growth_limit*8
319  || (total*unit_size*3 < current_use
320  && total*unit_size*6 < OslConfig::memoryUseLimit()))
321  return;
322  if (total < shared->last_gc + local_table_growth_limit*2)
323  return;
324  if (shared->shared_table_user > 0
325  && memory_use_ratio_1000 < 650
326  && total < shared->last_gc*2)
327  return;
328  if (shared->shared_table_user < 0 || shared->shared_table_gc_wait > 0)
329  return;
330 # ifdef OSL_SMP
331  while (shared->shared_table_user > 0) {
332  ++shared->shared_table_gc_wait;
333  shared->condition.wait(lk);
334  --shared->shared_table_gc_wait;
335  }
336  if (shared->shared_table_user < 0)
337  return;
338 # endif
339  shared->shared_table_user--;
340  }
341  removed += shared->table[BLACK].smallTreeGC(shared->gc_threshold);
342  removed += shared->table[WHITE].smallTreeGC(shared->gc_threshold);
343  {
344 # ifdef OSL_SMP
345  boost::mutex::scoped_lock lk(shared->mutex);
346 # endif
347  if (total > shared->last_gc*2) {
348  if (100.0*removed/total < 70)
349  shared->gc_threshold += 15;
350  else if (100.0*removed/total < 90)
351  shared->gc_threshold += 5;
352  }
353  shared->last_gc = total - removed;
354  shared->shared_table_user++;
355  assert(shared->shared_table_user == 0);
356 # ifdef OSL_SMP
357  shared->condition.notify_all();
358 # endif
359  }
360  }
361  if (! verbose)
362  return;
363  const double elapsed = start.elapsedSeconds();
364  if (removed > 10000 || elapsed > 0.1)
365  std::cerr << " GC " << removed
366  << " entries " << std::setprecision(3)
367  << (unit_size * removed / (1<<20)) << "MB "
368  << 100.0*removed/total << "%"
369  << " (" << elapsed << " s)\n";
370 #endif
371 }
372 
373 
374 template <osl::Player P>
376 DualDfpn::findProof(int node_limit, const NumEffectState& state,
377  const HashKey& key, const PathEncoding& path,
378  Move& best_move, Move last_move)
379 {
380  assert(state.turn() == P);
381  // oracle
382  Dfpn& dfpn = prepareDfpn(P);
383  const OraclePool::List l = shared->pool[P].probe(state);
384  const PieceStand attack_stand = (P==BLACK) ? key.blackStand() : PieceStand(WHITE, state);
385  int num_tried = 0;
386  for (size_t i=0; i<l.size(); ++i)
387  {
388  if (! attack_stand.isSuperiorOrEqualTo(l[i].proof_pieces)
389  || l[i].in_check != state.inCheck())
390  continue;
391  ++num_tried;
392  const ProofDisproof pdp = (node_limit > 20)
393  ? dfpn.tryProof(state, key, path, l[i].oracle, l[i].id, best_move, last_move)
394  : dfpn.tryProofLight(state, key, path, l[i].oracle, l[i].id, best_move, last_move);
395  const size_t count = dfpn.nodeCount();
396  local->local_node_count += count;
397  shared->addSimulationNodeCount(count);
398  if (count) {
399 #ifdef OSL_SMP
400  SCOPED_LOCK(lk,shared->proof_by_oracle_mutex[i]);
401 #endif
402  shared->proof_by_oracle[i].add(pdp.isCheckmateSuccess());
403  }
404  if (pdp.isCheckmateSuccess())
405  assert(best_move.isNormal());
406  if (pdp.isFinal())
407  return pdp;
408  }
409  if (node_limit == 0 && num_tried)
410  return ProofDisproof(1,1); // already tested table
411  const ProofDisproof table_pdp = dfpn.hasCheckmateMove(state, key, path, 0, best_move, last_move);
412  if (table_pdp.isCheckmateSuccess())
413  return table_pdp;
414  {
415 #ifdef OSL_SMP
416  boost::mutex::scoped_lock lk(shared->mutex);
417 #endif
418  Shared::disproof_table_t::const_iterator p = shared->disproof_table.find(key);
419  if (p != shared->disproof_table.end()) {
420  BOOST_FOREACH(const PathEncoding& ppath, p->second)
421  if (ppath == path)
423  }
424  }
425 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
426  static stat::Ratio migration_success("migration_success", true);
427  bool need_migration = false;
428 #endif
429  // local
430  if (node_limit < 80) {
431  if (local->table_small[P].totalSize() >= local_table_growth_limit) {
432  local->table_small[P].clear();
433  }
434  Dfpn& dfpn_small = prepareDfpnSmall(P);
435  const ProofDisproof pdp = dfpn_small.hasCheckmateMove(state, key, path, node_limit, best_move, last_move);
436  const size_t count = dfpn_small.nodeCount();
437  local->local_node_count += count;
438  shared->addMainNodeCount(count);
439  if (pdp.isLoopDetection()) {
440 #ifdef OSL_SMP
441  boost::mutex::scoped_lock lk(shared->mutex);
442 #endif
443  shared->disproof_table[key].push_front(path);
444  }
445  if (! pdp.isCheckmateSuccess())
446  return pdp;
447  assert(best_move.isNormal());
448  // fall through if checkmate success (TODO: efficient proof tree migration)
449 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
450  need_migration = true;
451 #endif
452  }
453  // main
454  Shared::TableUseLock lk(&*shared);
455  PieceStand proof_pieces;
456  const ProofDisproof pdp = dfpn.hasCheckmateMove(state, key, path, node_limit, best_move, proof_pieces, last_move);
457  const size_t count = dfpn.nodeCount();
458  local->local_node_count += count;
459  shared->addMainNodeCount(count);
460  if (pdp.isCheckmateSuccess())
461  shared->pool[P].addProof(state, key, proof_pieces);
462 #ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
463  if (need_migration)
464  migration_success.add(pdp.isCheckmateSuccess());
465 #endif
466  if (pdp.isLoopDetection()) {
467 #ifdef OSL_SMP
468  boost::mutex::scoped_lock lk(shared->mutex);
469 #endif
470  shared->disproof_table[key].push_front(path);
471  }
472  if (pdp.isCheckmateSuccess())
473  assert(best_move.isNormal());
474  return pdp;
475 }
476 
478 DualDfpn::findProof(int node_limit, const NumEffectState& state,
479  const HashKey& key, const PathEncoding& path,
480  Move& best_move, Move last_move)
481 {
482  if (state.turn() == BLACK)
483  return findProof<BLACK>(node_limit, state, key, path, best_move, last_move);
484  else
485  return findProof<WHITE>(node_limit, state, key, path, best_move, last_move);
486 }
487 
488 bool osl::checkmate::
489 DualDfpn::isWinningState(int node_limit, const NumEffectState& state,
490  const HashKey& key, const PathEncoding& path,
491  Move& best_move, Move last_move)
492 {
493  return findProof(node_limit, state, key, path, best_move, last_move)
494  .isCheckmateSuccess();
495 }
496 
497 #ifdef OSL_DFPN_SMP
498 template <osl::Player P>
499 bool osl::checkmate::
500 DualDfpn::isWinningStateParallel(int node_limit, const NumEffectState& state,
501  const HashKey& key, const PathEncoding& path,
502  Move& best_move, Move last_move)
503 {
504  PieceStand proof_pieces;
505  size_t count;
506  ProofDisproof pdp;
507  {
508 #ifdef OSL_SMP
509  boost::mutex::scoped_lock lk(shared->mutex);
510 #endif
511  if (! shared->parallel_search)
512  shared->parallel_search.reset(new DfpnParallel(std::min(OslConfig::numCPUs(), 8)));
513 #ifdef DFPN_SHARE_TABLE
514  shared->parallel_search->setTable(&(shared->table[P]));
515 #else
516  shared->parallel_search->setTable(&(local->table[P]));
517 #endif
518 
519  pdp = shared->parallel_search->hasCheckmateMove
520  (state, key, path, node_limit, best_move, proof_pieces, last_move);
521  count = shared->parallel_search->nodeCount();
522  }
523  shared->addMainNodeCount(count);
524  if (pdp.isCheckmateSuccess())
525  shared->pool[P].addProof(state, key, proof_pieces);
526  if (pdp.isLoopDetection()) {
527  shared->disproof_table[key].push_front(path);
528  }
529  if (pdp.isCheckmateSuccess())
530  assert(best_move.isNormal());
531  return pdp.isCheckmateSuccess();
532 }
533 
534 bool osl::checkmate::
535 DualDfpn::isWinningStateParallel(int node_limit, const NumEffectState& state,
536  const HashKey& key, const PathEncoding& path,
537  Move& best_move, Move last_move)
538 {
539  if (state.turn() == BLACK)
540  return isWinningStateParallel<BLACK>(node_limit, state, key, path, best_move, last_move);
541  else
542  return isWinningStateParallel<WHITE>(node_limit, state, key, path, best_move, last_move);
543 }
544 #endif
545 
546 template <osl::Player P>
547 bool
549 DualDfpn::isLosingState(int node_limit, const NumEffectState& state,
550  const HashKey& key, const PathEncoding& path,
551  Move last_move)
552 {
553  Shared::TableUseLock lk(&*shared);
554  assert(state.turn() == P);
555  Dfpn& dfpn = prepareDfpn(alt(P));
556  const ProofDisproof pdp = dfpn.hasEscapeMove(state, key, path, node_limit, last_move);
557  const size_t count = dfpn.nodeCount();
558  local->local_node_count += count;
559  shared->addMainNodeCount(count);
560  return pdp.isCheckmateSuccess();
561 }
562 
563 bool osl::checkmate::
564 DualDfpn::isLosingState(int node_limit, const NumEffectState& state,
565  const HashKey& key, const PathEncoding& path,
566  Move last_move)
567 {
568  if (state.turn() == BLACK)
569  return isLosingState<BLACK>(node_limit, state, key, path, last_move);
570  else
571  return isLosingState<WHITE>(node_limit, state, key, path, last_move);
572 }
573 
574 void osl::checkmate::
576  const MoveStack& moves,
577  const SimpleState& state, Player attack)
578 {
579  // TODO: 局面表をクリアしてしまうと忘れられる => DualDfpn 内で記憶した方が良い
580  Shared::TableUseLock lk(&*shared);
581  Dfpn& dfpn = prepareDfpn(attack);
582  PieceStand white_stand(WHITE, state);
583  for (int i=0; i<counter.checkCount(attack); ++i)
584  {
585  const HashKey& key = counter.history().top(i);
586  if (key != counter.history().top(0)) // ignore current state
587  {
588  dfpn.setIllegal(key, white_stand);
589  }
590  assert(moves.hasLastMove(i+1)); // oops, different index
591  if (! moves.hasLastMove(i+1))
592  break;
593  const Move last_move = moves.lastMove(i+1);
594  if (last_move.isNormal())
595  white_stand = white_stand.previousStand(WHITE, last_move);
596  }
597 }
598 
599 void osl::checkmate::
601 {
602  shared->blocking_verify[root] = true;
603  shared->blocking_verify[alt(root)] = true; // TODO: set false when issues around proof pieces are corrected
604 }
605 
606 void osl::checkmate::
607 DualDfpn::setVerbose(int /*level*/)
608 {
609 }
610 
612 DualDfpn::distance(Player attack, const HashKey& key)
613 {
614  Shared::TableUseLock lk(&*shared);
615  return prepareDfpn(attack).distance(key);
616 }
617 
618 size_t osl::checkmate::
620 {
621 #ifdef OSL_USE_RACE_DETECTOR
622  boost::mutex::scoped_lock lk(shared->mutex);
623 #endif
624  return shared->main_node_count;
625  // return shared->table[BLACK].totalSize() + shared->table[WHITE].totalSize();
626 }
627 
628 size_t osl::checkmate::
630 {
631 #ifdef OSL_USE_RACE_DETECTOR
632  boost::mutex::scoped_lock lk(shared->mutex);
633 #endif
634  return shared->main_node_count + shared->simulation_count;
635 }
636 
638 DualDfpn::table(Player attack) const
639 {
640  return shared->table[attack];
641 }
642 
643 namespace osl
644 {
645  template ProofDisproof checkmate::DualDfpn::findProof<BLACK>
646  (int, const NumEffectState&, const HashKey&, const PathEncoding&,
647  Move&, Move);
648  template ProofDisproof checkmate::DualDfpn::findProof<WHITE>
649  (int, const NumEffectState&, const HashKey&, const PathEncoding&,
650  Move&, Move);
651 
652 
653  template bool checkmate::DualDfpn::isLosingState<BLACK>
654  (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move);
655  template bool checkmate::DualDfpn::isLosingState<WHITE>
656  (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move);
657 
658 #ifdef OSL_DFPN_SMP
659  template bool checkmate::DualDfpn::isWinningStateParallel<BLACK>
660  (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move&, Move);
661  template bool checkmate::DualDfpn::isWinningStateParallel<WHITE>
662  (int, const NumEffectState&, const HashKey&, const PathEncoding&, Move&, Move);
663 #endif
664 }
665 
666 /* ------------------------------------------------------------------------- */
667 // ;;; Local Variables:
668 // ;;; mode:c++
669 // ;;; c-basic-offset:2
670 // ;;; End: