Debian Codegraph @

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

raw
1 /* proofTreeTraverser.cc
2 */
3 #include "analyzer/proofTreeTraverser.h"
4 #include "analyzer/disproofTreeTraverser.h"
5 #include "checkHashRecord.h"
6 #include "corruptCheckTable.h"
7 #include "osl/record/csa.h"
8 #include <iostream>
9
10 osl::checkmate::analyzer::
11 ProofTreeTraverser::ProofTreeTraverser(TreeWriter& w, const TwinTable& t)
12 : TreeTraverser(w, t)
13 {
14 }
15 osl::checkmate::analyzer::
16 ProofTreeTraverser::~ProofTreeTraverser()
17 {
18 }
19
20 void osl::checkmate::analyzer::
21 ProofTreeTraverser::orNode(Move, const CheckHashRecord *record,
22 const HashKey& key, const PathEncoding& path)
23 {
24 assert(! analyzerStack.findNotLast(record));
25 assert(! record->isVisited);
26 // stack 中に優越関係がある局面があれば,不詰と判断することが妥当だが,
27 // 優越関係を使わずに探索した場合は,そのような証明木を得ることがあるので
28 // ここでは確認しない.
29
30 // 証明木の条件
31 if (! record->proofDisproof().isCheckmateSuccess())
32 throw CorruptCheckTable(record, "! isCheckmateSuccess in proof");
33
34 // 指手がない時は信用
35 if (record->moves.empty())
36 {
37 leaves.insert(record);
38 return; // isproof で,前の手が逃げる手になっていなかった時とか
39 }
40
41 if (! visited.insert(record).second)
42 {
43 writer.writeln("confluence");
44 if (! record->isConfluence)
45 writer.writeln("UNRECOGNIZED confluence!");
46 return;
47 }
48
49 if (record->finalByDominance())
50 {
51 writer.writeln("finalByDominance");
52 return;
53 }
54 if (! record->hasBestMove())
55 throw CorruptCheckTable(record, "best move not recorded");
56
57 const CheckMoveList& l = record->moves;
58 // ここはOrNode なのでどれか一つを選ぶ
59 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
60 {
61 const PathEncoding newPath(path, p->move);
62 if (p->move == record->bestMove->move)
63 {
64 writer.showMove(record, *p);
65 if (p->flags.isSet(MoveFlags::ImmediateCheckmate))
66 return;
67 assert(p->record);
68 if (! p->record)
69 return;
70 writer.incDepth();
71
72 const HashKey newKey = key.newHashWithMove(p->move);
73 analyzerStack.push_back(CheckStackEntry(&*p, "P-AND", p->record,
74 newKey, newPath));
75 ProofTreeTraverser::andNode(p->move, p->record, newKey, newPath);
76 analyzerStack.pop_back();
77
78 writer.decDepth();
79 writer.showMoveAfter(record, *p);
80 return;
81 }
82 }
83
84 // 証明に必要な指手を見つけられなかった
85 std::cerr << "corrupt proof tree\n";
86 throw CorruptCheckTable(record, "best move not found in proof or-node");
87 }
88
89
90 void osl::checkmate::analyzer::
91 ProofTreeTraverser::andNode(Move, const CheckHashRecord *record,
92 const HashKey& key, const PathEncoding& path)
93 {
94 if (! visited.insert(record).second)
95 {
96 writer.writeln("confluence");
97 if (! record->isConfluence)
98 writer.writeln("UNRECOGNIZED confluence!");
99 return;
100 }
101
102 assert(record->proofDisproof().isCheckmateSuccess());
103 assert(! analyzerStack.findNotLast(record));
104 assert(! record->isVisited);
105 // TODO: 追及 path によっては詰になるノードを詰と扱って弊害があるグ
106 // ラフはあるか? あるとするとアルゴリズムの変更が必要
107 // 825棋譜の104手付近でおこる
108 // assert(! record->findLoop(path));
109
110 // stack 中に優越関係がある局面があれば,不詰と判断することが妥当だが,
111 // 優越関係を使わずに探索した場合は,そのような証明木を得ることがあるので
112 // ここでは確認しない.
113
114 if (record->finalByDominance())
115 {
116 leaves.insert(record);
117 writer.writeln("finalByDominance");
118 return;
119 }
120
121 const CheckMoveList& l = record->moves;
122 if (l.empty())
123 {
124 leaves.insert(record);
125 return;
126 }
127
128 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
129 {
130 const bool loopToStack = p->record && findLoopToStack(p->record->twins);
131 if (loopToStack)
132 {
133 std::cerr << "ineffective proof solution\n";
134 }
135 if (p->flags.isSet(MoveFlags::ImmediateCheckmate))
136 continue;
137 if ((! p->record) || (! p->flags.isSet(MoveFlags::Solved)))
138 {
139 csaShow(std::cerr, p->move);
140 std::cerr << "\nUnexamined move in proof tree?\n";
141 record->dump();
142 writer.writeln("UNEXAMINED move!");
143 writer.showMove(record, *p);
144 writer.writeln("possible BUG\n");
145 throw CorruptCheckTable(record, "unexamined move in proof and-node");
146 }
147 #ifndef NDEBUG
148 const TwinEntry *loopInNextMove = p->findLoop(path, table);
149 assert(! loopInNextMove);
150 #endif
151 writer.showMove(record, *p);
152 writer.incDepth();
153
154 PathEncoding newPath(path, p->move);
155 const HashKey newKey = key.newHashWithMove(p->move);
156 analyzerStack.push_back(CheckStackEntry(&*p, "P-OR ", p->record,
157 newKey, newPath));
158 ProofTreeTraverser::orNode(p->move, p->record, newKey, newPath);
159 analyzerStack.pop_back();
160
161 writer.decDepth();
162 writer.showMoveAfter(record, *p);
163 }
164 }
165
166 /* ------------------------------------------------------------------------- */
167 // ;;; Local Variables:
168 // ;;; mode:c++
169 // ;;; c-basic-offset:2
170 // ;;; End: