Debian Codegraph @

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

raw
1 /* disproofTreeTraverser.cc
2 */
3 #include "analyzer/disproofTreeTraverser.h"
4 #include "analyzer/proofTreeTraverser.h"
5 #include "checkHashRecord.h"
6 #include "corruptCheckTable.h"
7 #include "osl/checkmate/pawnCheckmateMoves.h"
8 #include "osl/record/csa.h"
9 #include <iostream>
10
11 osl::checkmate::analyzer::
12 DisproofTreeTraverser::DisproofTreeTraverser(TreeWriter& w, const TwinTable& t,
13 bool partial)
14 : TreeTraverser(w, t), isPartialStack(partial)
15 {
16 }
17 osl::checkmate::analyzer::
18 DisproofTreeTraverser::~DisproofTreeTraverser()
19 {
20 }
21
22 void osl::checkmate::analyzer::
23 DisproofTreeTraverser::orNode(Move last_move, const CheckHashRecord *record,
24 const HashKey& key, const PathEncoding& path)
25 {
26 if (! visited.insert(record).second)
27 {
28 writer.writeln("confluence");
29 if (! record->isConfluence)
30 writer.writeln("UNRECOGNIZED confluence!");
31 leaves.insert(record);
32 return;
33 }
34
35 if (analyzerStack.findNotLast(record) || record->isVisited)
36 {
37 writer.writeln("loop detection");
38 leaves.insert(record);
39 return;
40 }
41 if (record->finalByDominance())
42 {
43 writer.writeln("finalByDominance");
44 leaves.insert(record);
45 return;
46 }
47 if (! record->twins.empty())
48 {
49 // stack 中に優越関係がある局面があれば,不詰
50 const Player attacker = alt(path.turn());
51 if (analyzerStack.findCover(attacker, key, record) != analyzerStack.end())
52 {
53 writer.writeln("loop detection (drop)");
54 leaves.insert(record);
55 return;
56 }
57 }
58
59 const bool loopFound = record->findLoop(path, table);
60 const bool loopToStackFound = findLoopToStack(record->twins);
61 if ((! record->proofDisproof().isCheckmateFail())
62 && (! loopFound) && (! loopToStackFound)
63 && (! record->proofDisproof().isPawnDropFoul(last_move)))
64 throw CorruptCheckTable(record, "! isCheckmateFail in disproof");
65
66 // 指手がない時は信用
67 if (record->moves.empty())
68 {
69 leaves.insert(record);
70 return;
71 }
72
73 const CheckMoveList& l = record->moves;
74 // ここはOrNode なのでどれか一つを選ぶ
75 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
76 {
77 if (! p->record)
78 continue;
79 const PathEncoding newPath(path, p->move);
80 if (p->record->proofDisproof().isCheckmateFail()
81 || p->findLoop(path, table)
82 || p->record->isVisited
83 || findLoopToStack(p->record->twins)
84 || analyzerStack.findNotLast(p->record))
85 {
86 writer.showMove(record, *p);
87 writer.incDepth();
88
89 const HashKey newKey = key.newHashWithMove(p->move);
90 analyzerStack.push_back(CheckStackEntry(&*p, "D-AND", p->record,
91 newKey, newPath));
92 DisproofTreeTraverser::andNode(p->move, p->record, newKey, newPath);
93 analyzerStack.pop_back();
94 writer.decDepth();
95 return;
96 }
97 }
98
99 // 反証に必要な指手を見つけられなかった
100 if (isPartialStack && (loopFound || loopToStackFound))
101 return; // 反証した時には p->record->isVisited だったと思われる
102 std::cerr << "corrupt (dis)proof tree\n";
103 throw CorruptCheckTable(record, "best move not found in disproof or-node");
104 }
105
106 void osl::checkmate::analyzer::
107 DisproofTreeTraverser::andNode(Move, const CheckHashRecord *record,
108 const HashKey& key, const PathEncoding& path)
109 {
110 if (! visited.insert(record).second)
111 {
112 writer.writeln("confluence");
113 if (! record->isConfluence)
114 writer.writeln("UNRECOGNIZED confluence!");
115 leaves.insert(record);
116 return;
117 }
118
119 if (analyzerStack.findNotLast(record) || record->isVisited)
120 {
121 writer.writeln("loop detection");
122 leaves.insert(record);
123 return;
124 }
125 if (! record->twins.empty())
126 {
127 const Player attacker = path.turn();
128 if (analyzerStack.findCover(attacker, key, record) != analyzerStack.end())
129 {
130 writer.writeln("loop detection (drop)");
131 leaves.insert(record);
132 return;
133 }
134 }
135
136 assert(record->proofDisproof().isCheckmateFail()
137 || findLoopToStack(record->twins)
138 || record->findLoop(path, table));
139
140 if (record->finalByDominance())
141 {
142 writer.writeln("finalByDominance");
143 leaves.insert(record);
144 return;
145 }
146
147 const CheckMoveList& l = record->moves;
148 if (l.empty())
149 {
150 leaves.insert(record);
151 return;
152 }
153
154 const bool nowLoopDetection = ! record->proofDisproof().isCheckmateFail();
155
156 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
157 {
158 if ((record->proofDisproof() != ProofDisproof::PawnCheckmate())
159 && p->flags.isSet(MoveFlags::NoPromote))
160 continue; // NoPromote は試す必要がない
161
162 if (! p->record)
163 {
164 if (nowLoopDetection && isPartialStack)
165 continue; // ここで visited だったはず
166 }
167
168 if (analyzerStack.findLoop(p->record) != analyzerStack.end())
169 continue;
170 const bool loopToStack = findLoopToStack(p->record->twins);
171
172 if (p->record->proofDisproof().isPawnDropFoul(p->move))
173 continue;
174
175 // 基本的に Solved マークがついているはず
176 if ((! p->flags.isSet(MoveFlags::Solved))
177 && record->proofDisproof().isCheckmateFail()
178 && (! loopToStack))
179 {
180 if (isPartialStack)
181 continue; // 本来はloopToStack だった可能性あり
182 #ifdef CHECK_ABSORB_LOOP
183 if (isCheckmateFail(p->record->proofDisproof()))
184 {
185 // CHECK_ABSORB_LOOP 関係で Solved をつけ忘れることがあるらしい
186 }
187 else
188 #endif
189 {
190 csaShow(std::cerr, p->move);
191 std::cerr << "\nUnexamined move in disproof tree?\n";
192 record->dump();
193 if (p->record)
194 p->record->dump();
195 writer.writeln("UNEXAMINED move!");
196 writer.showMove(record, *p);
197 writer.writeln("possible BUG\n");
198 throw CorruptCheckTable(record, "unexamined move in disproof and-node");
199 }
200 }
201
202 const TwinEntry *loopInNextMove = p->findLoop(path, table);
203 // isCheckmateFail だったら子供もそうあるべき
204 if (p->record->proofDisproof().isCheckmateFail())
205 {
206 if ((! p->record->proofDisproof().isCheckmateFail())
207 && (! loopToStack))
208 {
209 std::cerr << "path " << path << " -> " << PathEncoding(path, p->move)
210 << "\n";
211 std::cerr << "checkmate fail parent " << record << "\n";
212 record->dump();
213 std::cerr << "! checkmate fail child\n";
214 std::cerr << "loopInNextMove " << loopInNextMove << "\n";
215 if (loopInNextMove)
216 std::cerr << "loopInNextMove->loopTo " << loopInNextMove->loopTo
217 << "\n";
218 p->record->dump();
219 throw CorruptCheckTable(record, "bad aggregation in and-node");
220 }
221 }
222 else
223 {
224 // ループによる反証
225 if ((! loopInNextMove)
226 && (! p->record->proofDisproof().isCheckmateFail())
227 && (! loopToStack))
228 {
229 // loop detection は isPartialStack の時は確認できなくてもしょうがない
230 if (isPartialStack)
231 continue; // 反証した時には p->record->isVisited だったと思われる
232 std::cerr << "not confirmed in loop " << p->move << "\n";
233 record->dump();
234 if (PawnCheckmateMoves::effectiveOnlyIfPawnCheckmate(p->move))
235 continue; // GHI + NoPromote と信じる
236 if (p->record)
237 p->record->dump();
238 writer.showMove(record, *p);
239 writer.writeln("possible BUG\n");
240 throw CorruptCheckTable(record, "loop detection not confirmed in disproof and-node");
241 }
242 }
243
244 writer.showMove(record, *p);
245 writer.incDepth();
246
247 PathEncoding newPath(path, p->move);
248 const HashKey newKey = key.newHashWithMove(p->move);
249 analyzerStack.push_back(CheckStackEntry(&*p, "D-OR ", p->record,
250 newKey, newPath));
251 DisproofTreeTraverser::orNode(p->move, p->record, newKey, newPath);
252 analyzerStack.pop_back();
253 writer.decDepth();
254 }
255 }
256
257 /* ------------------------------------------------------------------------- */
258 // ;;; Local Variables:
259 // ;;; mode:c++
260 // ;;; c-basic-offset:2
261 // ;;; End: