Debian Codegraph @

old-sample/legacy-checkmate/lib/analyzer/proofTreeDepth.cc

raw
1 #include "analyzer/proofTreeDepth.h"
2 #include "checkHashRecord.h"
3 #include "osl/stl/hash_map.h"
4 #include "osl/stl/pointerHash.h"
5
6 /**
7 * 深さを記憶するテーブル.
8 * -1 は探索中
9 */
10 struct osl::checkmate::analyzer::ProofTreeDepth::Table
11 : public osl::hash_map<const CheckHashRecord*, int>
12 {
13 };
14
15 osl::checkmate::analyzer::
16 ProofTreeDepth::ProofTreeDepth()
17 : table(new Table())
18 {
19 }
20
21 osl::checkmate::analyzer::
22 ProofTreeDepth::~ProofTreeDepth()
23 {
24 }
25
26 int osl::checkmate::analyzer::
27 ProofTreeDepth::depth(const CheckHashRecord *record, bool is_or_node) const
28 {
29 if (! record)
30 {
31 assert(is_or_node); // ImmediateCheckmate
32 return 1;
33 }
34 assert(record);
35 assert(record->proofDisproof().isCheckmateSuccess());
36 return (is_or_node ? orNode(record) : andNode(record));
37 }
38
39 int osl::checkmate::analyzer::
40 ProofTreeDepth::orNode(const CheckHashRecord *record) const
41 {
42 assert(record);
43 assert(record->proofDisproof().isCheckmateSuccess());
44 const Table::const_iterator p = table->find(record);
45 if (p != table->end())
46 return p->second;
47 (*table)[record] = -1;
48
49 if (record->bestMove && (! record->bestMove->record))
50 {
51 // ImmediateCheckmate
52 assert(record->bestMove->flags.isSet(MoveFlags::ImmediateCheckmate));
53 (*table)[record] = 1;
54 return 1;
55 }
56 const CheckMoveList& l = record->finalByDominance()
57 ? record->finalByDominance()->moves
58 : record->moves;
59 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
60 {
61 if (! p->record)
62 continue;
63 if (! p->record->proofDisproof().isCheckmateSuccess())
64 continue;
65 const int depth = andNode(p->record);
66 if (depth >= 0)
67 {
68 (*table)[record] = depth+1;
69 return (*table)[record];
70 }
71 }
72 if (! l.empty())
73 return -1; // ループ迷いこみ
74
75 (*table)[record] = 0;
76 return 0; // or node で指手がなくて詰 => 逃げてない
77 }
78
79 int osl::checkmate::analyzer::
80 ProofTreeDepth::andNode(const CheckHashRecord *record) const
81 {
82 assert(record);
83 assert(record->proofDisproof().isCheckmateSuccess());
84 const Table::const_iterator p = table->find(record);
85 if (p != table->end())
86 return p->second;
87 (*table)[record] = -1;
88
89 int result = 0; // and node で指手がなくて詰 => 逃げられない
90
91 const CheckMoveList& l = record->finalByDominance()
92 ? record->finalByDominance()->moves
93 : record->moves;
94 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
95 {
96 if (! p->record)
97 continue;
98 const int depth = orNode(p->record);
99 if (depth < 0)
100 return depth; // loop found
101 result = std::max(depth+1, result);
102 }
103
104 (*table)[record] = result;
105 return result;
106 }
107
108 /* ------------------------------------------------------------------------- */
109 // ;;; Local Variables:
110 // ;;; mode:c++
111 // ;;; c-basic-offset:2
112 // ;;; End: