00001
00002
00003 #include "osl/checkmate/analyzer/disproofTreeTraverser.h"
00004 #include "osl/checkmate/analyzer/proofTreeTraverser.h"
00005 #include "osl/checkmate/checkHashRecord.h"
00006 #include "osl/checkmate/corruptCheckTable.h"
00007 #include "osl/checkmate/pawnCheckmateMoves.h"
00008 #include "osl/record/csa.h"
00009 #include <iostream>
00010
00011 osl::checkmate::analyzer::
00012 DisproofTreeTraverser::DisproofTreeTraverser(TreeWriter& w, const TwinTable& t,
00013 bool partial)
00014 : TreeTraverser(w, t), isPartialStack(partial)
00015 {
00016 }
00017 osl::checkmate::analyzer::
00018 DisproofTreeTraverser::~DisproofTreeTraverser()
00019 {
00020 }
00021
00022 void osl::checkmate::analyzer::
00023 DisproofTreeTraverser::orNode(Move last_move, const CheckHashRecord *record,
00024 const HashKey& key, const PathEncoding& path)
00025 {
00026 if (! visited.insert(record).second)
00027 {
00028 writer.writeln("confluence");
00029 if (! record->isConfluence)
00030 writer.writeln("UNRECOGNIZED confluence!");
00031 leaves.insert(record);
00032 return;
00033 }
00034
00035 if (analyzerStack.findNotLast(record) || record->isVisited)
00036 {
00037 writer.writeln("loop detection");
00038 leaves.insert(record);
00039 return;
00040 }
00041 if (record->finalByDominance())
00042 {
00043 writer.writeln("finalByDominance");
00044 leaves.insert(record);
00045 return;
00046 }
00047 if (! record->twins.empty())
00048 {
00049
00050 const Player attacker = alt(path.turn());
00051 if (analyzerStack.findCover(attacker, key, record) != analyzerStack.end())
00052 {
00053 writer.writeln("loop detection (drop)");
00054 leaves.insert(record);
00055 return;
00056 }
00057 }
00058
00059 const bool loopFound = record->findLoop(path, table);
00060 const bool loopToStackFound = findLoopToStack(record->twins);
00061 if ((! record->proofDisproof().isCheckmateFail())
00062 && (! loopFound) && (! loopToStackFound)
00063 && (! record->proofDisproof().isPawnDropFoul(last_move)))
00064 throw CorruptCheckTable(record, "! isCheckmateFail in disproof");
00065
00066
00067 if (record->moves.empty())
00068 {
00069 leaves.insert(record);
00070 return;
00071 }
00072
00073 const CheckMoveList& l = record->moves;
00074
00075 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
00076 {
00077 if (! p->record)
00078 continue;
00079 const PathEncoding newPath(path, p->move);
00080 if (p->record->proofDisproof().isCheckmateFail()
00081 || p->findLoop(path, table)
00082 || p->record->isVisited
00083 || findLoopToStack(p->record->twins)
00084 || analyzerStack.findNotLast(p->record))
00085 {
00086 writer.showMove(record, *p);
00087 writer.incDepth();
00088
00089 const HashKey newKey = key.newHashWithMove(p->move);
00090 analyzerStack.push_back(CheckStackEntry(&*p, "D-AND", p->record,
00091 newKey, newPath));
00092 DisproofTreeTraverser::andNode(p->move, p->record, newKey, newPath);
00093 analyzerStack.pop_back();
00094 writer.decDepth();
00095 return;
00096 }
00097 }
00098
00099
00100 if (isPartialStack && (loopFound || loopToStackFound))
00101 return;
00102 std::cerr << "corrupt (dis)proof tree\n";
00103 throw CorruptCheckTable(record, "best move not found in disproof or-node");
00104 }
00105
00106 void osl::checkmate::analyzer::
00107 DisproofTreeTraverser::andNode(Move, const CheckHashRecord *record,
00108 const HashKey& key, const PathEncoding& path)
00109 {
00110 if (! visited.insert(record).second)
00111 {
00112 writer.writeln("confluence");
00113 if (! record->isConfluence)
00114 writer.writeln("UNRECOGNIZED confluence!");
00115 leaves.insert(record);
00116 return;
00117 }
00118
00119 if (analyzerStack.findNotLast(record) || record->isVisited)
00120 {
00121 writer.writeln("loop detection");
00122 leaves.insert(record);
00123 return;
00124 }
00125 if (! record->twins.empty())
00126 {
00127 const Player attacker = path.turn();
00128 if (analyzerStack.findCover(attacker, key, record) != analyzerStack.end())
00129 {
00130 writer.writeln("loop detection (drop)");
00131 leaves.insert(record);
00132 return;
00133 }
00134 }
00135
00136 assert(record->proofDisproof().isCheckmateFail()
00137 || findLoopToStack(record->twins)
00138 || record->findLoop(path, table));
00139
00140 if (record->finalByDominance())
00141 {
00142 writer.writeln("finalByDominance");
00143 leaves.insert(record);
00144 return;
00145 }
00146
00147 const CheckMoveList& l = record->moves;
00148 if (l.empty())
00149 {
00150 leaves.insert(record);
00151 return;
00152 }
00153
00154 const bool nowLoopDetection = ! record->proofDisproof().isCheckmateFail();
00155
00156 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
00157 {
00158 if ((record->proofDisproof() != ProofDisproof::PawnCheckmate())
00159 && p->flags.isSet(MoveFlags::NoPromote))
00160 continue;
00161
00162 if (! p->record)
00163 {
00164 if (nowLoopDetection && isPartialStack)
00165 continue;
00166 }
00167
00168 if (analyzerStack.findLoop(p->record) != analyzerStack.end())
00169 continue;
00170 const bool loopToStack = findLoopToStack(p->record->twins);
00171
00172 if (p->record->proofDisproof().isPawnDropFoul(p->move))
00173 continue;
00174
00175
00176 if ((! p->flags.isSet(MoveFlags::Solved))
00177 && record->proofDisproof().isCheckmateFail()
00178 && (! loopToStack))
00179 {
00180 if (isPartialStack)
00181 continue;
00182 #ifdef CHECK_ABSORB_LOOP
00183 if (isCheckmateFail(p->record->proofDisproof()))
00184 {
00185
00186 }
00187 else
00188 #endif
00189 {
00190 csaShow(std::cerr, p->move);
00191 std::cerr << "\nUnexamined move in disproof tree?\n";
00192 record->dump();
00193 if (p->record)
00194 p->record->dump();
00195 writer.writeln("UNEXAMINED move!");
00196 writer.showMove(record, *p);
00197 writer.writeln("possible BUG\n");
00198 throw CorruptCheckTable(record, "unexamined move in disproof and-node");
00199 }
00200 }
00201
00202 const TwinEntry *loopInNextMove = p->findLoop(path, table);
00203
00204 if (p->record->proofDisproof().isCheckmateFail())
00205 {
00206 if ((! p->record->proofDisproof().isCheckmateFail())
00207 && (! loopToStack))
00208 {
00209 std::cerr << "path " << path << " -> " << PathEncoding(path, p->move)
00210 << "\n";
00211 std::cerr << "checkmate fail parent " << record << "\n";
00212 record->dump();
00213 std::cerr << "! checkmate fail child\n";
00214 std::cerr << "loopInNextMove " << loopInNextMove << "\n";
00215 if (loopInNextMove)
00216 std::cerr << "loopInNextMove->loopTo " << loopInNextMove->loopTo
00217 << "\n";
00218 p->record->dump();
00219 throw CorruptCheckTable(record, "bad aggregation in and-node");
00220 }
00221 }
00222 else
00223 {
00224
00225 if ((! loopInNextMove)
00226 && (! p->record->proofDisproof().isCheckmateFail())
00227 && (! loopToStack))
00228 {
00229
00230 if (isPartialStack)
00231 continue;
00232 std::cerr << "not confirmed in loop " << p->move << "\n";
00233 record->dump();
00234 if (PawnCheckmateMoves::effectiveOnlyIfPawnCheckmate(p->move))
00235 continue;
00236 if (p->record)
00237 p->record->dump();
00238 writer.showMove(record, *p);
00239 writer.writeln("possible BUG\n");
00240 throw CorruptCheckTable(record, "loop detection not confirmed in disproof and-node");
00241 }
00242 }
00243
00244 writer.showMove(record, *p);
00245 writer.incDepth();
00246
00247 PathEncoding newPath(path, p->move);
00248 const HashKey newKey = key.newHashWithMove(p->move);
00249 analyzerStack.push_back(CheckStackEntry(&*p, "D-OR ", p->record,
00250 newKey, newPath));
00251 DisproofTreeTraverser::orNode(p->move, p->record, newKey, newPath);
00252 analyzerStack.pop_back();
00253 writer.decDepth();
00254 }
00255 }
00256
00257
00258
00259
00260
00261