00001
00002
00003 #include "osl/checkmate/analyzer/proofTreeTraverser.h"
00004 #include "osl/checkmate/analyzer/disproofTreeTraverser.h"
00005 #include "osl/checkmate/checkHashRecord.h"
00006 #include "osl/checkmate/corruptCheckTable.h"
00007 #include "osl/record/csa.h"
00008 #include <iostream>
00009
00010 osl::checkmate::analyzer::
00011 ProofTreeTraverser::ProofTreeTraverser(TreeWriter& w, const TwinTable& t)
00012 : TreeTraverser(w, t)
00013 {
00014 }
00015 osl::checkmate::analyzer::
00016 ProofTreeTraverser::~ProofTreeTraverser()
00017 {
00018 }
00019
00020 void osl::checkmate::analyzer::
00021 ProofTreeTraverser::orNode(Move, const CheckHashRecord *record,
00022 const HashKey& key, const PathEncoding& path)
00023 {
00024 assert(! analyzerStack.findNotLast(record));
00025 assert(! record->isVisited);
00026
00027
00028
00029
00030
00031 if (! record->proofDisproof().isCheckmateSuccess())
00032 throw CorruptCheckTable(record, "! isCheckmateSuccess in proof");
00033
00034
00035 if (record->moves.empty())
00036 {
00037 leaves.insert(record);
00038 return;
00039 }
00040
00041 if (! visited.insert(record).second)
00042 {
00043 writer.writeln("confluence");
00044 if (! record->isConfluence)
00045 writer.writeln("UNRECOGNIZED confluence!");
00046 return;
00047 }
00048
00049 if (record->finalByDominance())
00050 {
00051 writer.writeln("finalByDominance");
00052 return;
00053 }
00054 if (! record->hasBestMove())
00055 throw CorruptCheckTable(record, "best move not recorded");
00056
00057 const CheckMoveList& l = record->moves;
00058
00059 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
00060 {
00061 const PathEncoding newPath(path, p->move);
00062 if (p->move == record->bestMove->move)
00063 {
00064 writer.showMove(record, *p);
00065 if (p->flags.isSet(MoveFlags::ImmediateCheckmate))
00066 return;
00067 assert(p->record);
00068 if (! p->record)
00069 return;
00070 writer.incDepth();
00071
00072 const HashKey newKey = key.newHashWithMove(p->move);
00073 analyzerStack.push_back(CheckStackEntry(&*p, "P-AND", p->record,
00074 newKey, newPath));
00075 ProofTreeTraverser::andNode(p->move, p->record, newKey, newPath);
00076 analyzerStack.pop_back();
00077
00078 writer.decDepth();
00079 writer.showMoveAfter(record, *p);
00080 return;
00081 }
00082 }
00083
00084
00085 std::cerr << "corrupt proof tree\n";
00086 throw CorruptCheckTable(record, "best move not found in proof or-node");
00087 }
00088
00089
00090 void osl::checkmate::analyzer::
00091 ProofTreeTraverser::andNode(Move, const CheckHashRecord *record,
00092 const HashKey& key, const PathEncoding& path)
00093 {
00094 if (! visited.insert(record).second)
00095 {
00096 writer.writeln("confluence");
00097 if (! record->isConfluence)
00098 writer.writeln("UNRECOGNIZED confluence!");
00099 return;
00100 }
00101
00102 assert(record->proofDisproof().isCheckmateSuccess());
00103 assert(! analyzerStack.findNotLast(record));
00104 assert(! record->isVisited);
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114 if (record->finalByDominance())
00115 {
00116 leaves.insert(record);
00117 writer.writeln("finalByDominance");
00118 return;
00119 }
00120
00121 const CheckMoveList& l = record->moves;
00122 if (l.empty())
00123 {
00124 leaves.insert(record);
00125 return;
00126 }
00127
00128 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p)
00129 {
00130 const bool loopToStack = p->record && findLoopToStack(p->record->twins);
00131 if (loopToStack)
00132 {
00133 std::cerr << "ineffective proof solution\n";
00134 }
00135 if (p->flags.isSet(MoveFlags::ImmediateCheckmate))
00136 continue;
00137 if ((! p->record) || (! p->flags.isSet(MoveFlags::Solved)))
00138 {
00139 csaShow(std::cerr, p->move);
00140 std::cerr << "\nUnexamined move in proof tree?\n";
00141 record->dump();
00142 writer.writeln("UNEXAMINED move!");
00143 writer.showMove(record, *p);
00144 writer.writeln("possible BUG\n");
00145 throw CorruptCheckTable(record, "unexamined move in proof and-node");
00146 }
00147 #ifndef NDEBUG
00148 const TwinEntry *loopInNextMove = p->findLoop(path, table);
00149 assert(! loopInNextMove);
00150 #endif
00151 writer.showMove(record, *p);
00152 writer.incDepth();
00153
00154 PathEncoding newPath(path, p->move);
00155 const HashKey newKey = key.newHashWithMove(p->move);
00156 analyzerStack.push_back(CheckStackEntry(&*p, "P-OR ", p->record,
00157 newKey, newPath));
00158 ProofTreeTraverser::orNode(p->move, p->record, newKey, newPath);
00159 analyzerStack.pop_back();
00160
00161 writer.decDepth();
00162 writer.showMoveAfter(record, *p);
00163 }
00164 }
00165
00166
00167
00168
00169
00170