00001
00002
00003 #include "osl/search/analyzer/dotAnalyzerProof.h"
00004 #include "osl/search/analyzer/dotWriter.h"
00005 #include "osl/search/simpleHashTable.h"
00006 #include "osl/search/simpleHashRecord.h"
00007 #include "osl/hash/hashKey.h"
00008 #include "osl/moveLogProb.h"
00009 #include <iostream>
00010 #include <sstream>
00011 osl::search::analyzer::DotAnalyzerProof::
00012 DotAnalyzerProof(const SimpleHashTable& t, std::ostream& o)
00013 : DotAnalyzer(t, o)
00014 {
00015 }
00016
00017 osl::search::analyzer::DotAnalyzerProof::
00018 ~DotAnalyzerProof()
00019 {
00020 }
00021
00022 void osl::search::analyzer::DotAnalyzerProof::
00023 absoluteBound(unsigned int depth, bool is_lower, int bound, Player turn,
00024 int limit, const SimpleHashRecord *from,
00025 const SimpleHashRecord *record, const MoveLogProb& move)
00026 {
00027 if (! record)
00028 return;
00029 const bool or_node = ((turn == BLACK) ^ is_lower);
00030 if (move.validMove())
00031 {
00032 limit -= move.getLogProb();
00033 if (limit < 0)
00034 return;
00035 }
00036
00037 const SearchMoveSet& moves = record->moves();
00038 LogWriter::NodeType type = LogWriter::NORMAL;
00039 int new_bound = bound;
00040 if (is_lower)
00041 {
00042 if (! (record->hasAbsoluteLowerBound(turn, limit)
00043 && (record->absoluteLowerBound(turn) >= bound)))
00044 {
00045 if (moves.empty() || or_node)
00046 return;
00047 std::cerr << "warning: lower bound proof failure at "
00048 << depth << " " << record << "\n";
00049 type = LogWriter::ABNORMAL;
00050 }
00051 else
00052 {
00053 new_bound = record->absoluteLowerBound(turn);
00054 }
00055 }
00056 else
00057 {
00058 if (! (record->hasAbsoluteUpperBound(turn, limit)
00059 && (record->absoluteUpperBound(turn)-1 <= bound)))
00060 {
00061 if (moves.empty() || or_node || (depth == 1))
00062 return;
00063 std::cerr << "warning: upper bound proof failure at "
00064 << depth << " " << record << "\n";
00065 type = LogWriter::ABNORMAL;
00066 }
00067 else
00068 {
00069 new_bound = record->absoluteUpperBound(turn)-1;
00070 }
00071 }
00072
00073 if (! moves.empty())
00074 {
00075 {
00076 std::stringstream debug;
00077 debug << depth << " " << (or_node ? "or" : "and")
00078 << (is_lower ? " > " : " < ") << bound << " -> " << new_bound;
00079 writer->showComment(debug.str().c_str());
00080 }
00081 if (from)
00082 writer->showArc(from, record, move, false);
00083 writer->showNode(turn, record, limit, type);
00084 if (type == LogWriter::ABNORMAL)
00085 return;
00086 bound = new_bound;
00087 const MoveLogProb best_move = record->bestMove().moveLogProb();
00088
00089 {
00090 SearchMoveSet::const_range r(moves);
00091 for (SearchMoveSet::const_iterator p=r.first; p!=r.last; ++p)
00092 {
00093 assert(turn == p->getMove().player());
00094 if (p->getMove() == best_move.getMove())
00095 {
00096
00097 absoluteBound(depth+1, is_lower, bound, alt(turn), limit, record,
00098 p->record, best_move);
00099 }
00100 else
00101 {
00102 absoluteBound(depth+1, is_lower, bound, alt(turn), limit, record,
00103 p->record, p->moveLogProb());
00104 }
00105 }
00106 }
00107 }
00108 else
00109 {
00110 #ifdef WRITE_QUIESCENCE
00111
00112 if (from)
00113 writer->showArc(from, record, move, false);
00114 writer->showNodeQuiescence(turn, record, limit, false);
00115 #endif
00116 }
00117 }
00118
00119 void osl::search::analyzer::DotAnalyzerProof::
00120 analyzeQuiescence(const HashKey& root)
00121 {
00122 MoveLogProb dummy;
00123 analyze(root, 0);
00124 }
00125
00126 void osl::search::analyzer::DotAnalyzerProof::
00127 analyze(const HashKey& key, int limit)
00128 {
00129 const SimpleHashRecord *record = table.find(key);
00130 if (! record)
00131 return;
00132 const Player turn = key.turn();
00133 const bool is_black_turn = (turn == BLACK);
00134 const int bound
00135 = (is_black_turn ? record->lowerBound() : record->upperBound());
00136 const int bound_minus_one = bound - 1;
00137 MoveLogProb dummy;
00138 absoluteBound(0, true, (is_black_turn ? bound : bound_minus_one),
00139 turn, limit, 0, record, dummy);
00140 absoluteBound(0, false, (is_black_turn ? bound_minus_one : bound),
00141 turn, limit, 0, record, dummy);
00142 }
00143
00144
00145
00146
00147
00148