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