00001
00002
00003 #include "osl/search/analyzer/tableAnalyzer.h"
00004 #include "osl/search/analyzer/recordSet_.h"
00005 #include "osl/search/simpleHashTable.h"
00006 #include "osl/search/simpleHashRecord.h"
00007 #include "osl/search/searchMoveList.h"
00008 #include "osl/eval/evalCompareLarger.h"
00009 #include "osl/record/csa.h"
00010
00011 #include <map>
00012 #include <iostream>
00013 #include <sstream>
00014 #include <iomanip>
00015
00016 namespace osl
00017 {
00018 namespace search
00019 {
00020 namespace analyzer
00021 {
00022 const int INVALID_VALUE = -1;
00023 struct MoveEntry
00024 {
00025 Move best_move;
00026 int upper_bound, lower_bound;
00027 int upper_limit, lower_limit;
00028 const SimpleHashRecord *record;
00029 MoveEntry(Move b, const SimpleHashRecord *r)
00030 : best_move(b),
00031 upper_bound(INVALID_VALUE), lower_bound(INVALID_VALUE),
00032 upper_limit(0), lower_limit(0),
00033 record(r)
00034 {
00035 if (record)
00036 {
00037 upper_limit = record->upperLimit();
00038 if (upper_limit > 0)
00039 upper_bound = record->upperBound();
00040 lower_limit = record->lowerLimit();
00041 if (lower_limit > 0)
00042 lower_bound = record->lowerBound();
00043 }
00044 }
00045 };
00046 struct MoveMap
00047 : public std::multimap<int,MoveEntry,eval::EvalCompareLargerNT>
00048 {
00049 typedef std::multimap<int,MoveEntry,eval::EvalCompareLargerNT> map_t;
00050 explicit MoveMap(Player player) : map_t(player)
00051 {
00052 }
00053 };
00054
00055 struct TopLevelAnalyzer
00056 {
00057 const SimpleHashTable *table;
00058 MoveMap sorter;
00059 int num_print_moves;
00060 std::ostream& os;
00061 Player player;
00062 TopLevelAnalyzer(Player p,
00063 const SimpleHashTable *t, int num, std::ostream& o)
00064 : table(t), sorter(p), num_print_moves(num), os(o), player(p)
00065 {
00066 }
00067 void examineAll(const SimpleHashRecord *record);
00068 void showMoves();
00069 };
00070
00071 const std::string limitToString(int limit)
00072 {
00073 if (limit < 0)
00074 return "*";
00075 std::ostringstream ss;
00076 ss << limit;
00077 return ss.str();
00078 }
00079 const std::string valueToString(int value)
00080 {
00081 if (value == INVALID_VALUE)
00082 return "*";
00083 std::ostringstream ss;
00084 ss << value;
00085 return ss.str();
00086 }
00087
00088 }
00089 }
00090 }
00091
00092 void osl::search::analyzer::
00093 TopLevelAnalyzer::showMoves()
00094 {
00095 int num_printed = 0;
00096 for (MoveMap::const_iterator p=sorter.begin();
00097 (p!=sorter.end())&&(num_printed < num_print_moves); ++p, ++num_printed)
00098 {
00099 os
00100 #if 0
00101 << std::setw(5) << p->first << " "
00102 #endif
00103 << "["
00104 << std::setw(5) << valueToString(p->second.lower_bound) << "("
00105 << std::setw(4) << limitToString(p->second.lower_limit) << ") < "
00106 << std::setw(5) << valueToString(p->second.upper_bound) << "("
00107 << std::setw(4) << limitToString(p->second.upper_limit) << ") "
00108 << "] \t";
00109 csaShow(os, p->second.best_move);
00110 os << " ";
00111 SearchMoveList best_moves;
00112 TableAnalyzer::makeBestMoveList(p->second.record, best_moves, 16);
00113 for (SearchMoveList::const_iterator p=best_moves.begin();
00114 p!=best_moves.end(); ++p)
00115 {
00116 if (! p->getMove().isPass())
00117 {
00118 csaShow(os, p->getMove());
00119 os << " ";
00120 }
00121 else if (p->getLogProb() == SearchTable::CheckmateSpecialDepth)
00122 {
00123 os << "CHECKMATE";
00124 }
00125 else
00126 {
00127
00128 os << "*";
00129 }
00130 }
00131 os << "\n";
00132 }
00133 }
00134
00135 void osl::search::analyzer::
00136 TopLevelAnalyzer::examineAll(const SimpleHashRecord *record)
00137 {
00138 assert(record);
00139 const SearchMoveSet& moves = record->moves();
00140 {
00141 SearchMoveSet::const_range r(moves);
00142 for (SearchMoveSet::const_iterator p=r.first; p!=r.last; ++p)
00143 {
00144 const SearchMove& cur_move = *p;
00146 int value=INVALID_VALUE;
00147 const SimpleHashRecord *next_record = cur_move.record;
00148 if (cur_move.getMove() == record->bestMove().getMove())
00149 {
00150 if (next_record && next_record->hasUpperBound(1))
00151 value = next_record->upperBound() + eval::delta(player)*2;
00152 }
00153 else
00154 {
00155
00156 if (next_record && next_record->hasLowerBound(1))
00157 value = next_record->lowerBound();
00158 }
00159 if (value != INVALID_VALUE)
00160 sorter.insert(std::make_pair
00161 (value, MoveEntry(cur_move.getMove(), next_record)));
00162 }
00163 }
00164 showMoves();
00165 }
00166
00167 osl::search::analyzer::
00168 TableAnalyzer::TableAnalyzer(const SimpleHashTable& t, std::ostream& o)
00169 : table(t), os(o)
00170 {
00171 }
00172 osl::search::analyzer::
00173 TableAnalyzer::~TableAnalyzer()
00174 {
00175 }
00176
00177 void osl::search::analyzer::
00178 TableAnalyzer::examineTopLevel(const HashKey& key, int num_print_moves) const
00179 {
00180 os << "analysis of root node\n";
00181 const SimpleHashRecord *record = table.find(key);
00182 if (! record)
00183 {
00184 os << "record not found\n";
00185 return;
00186 }
00187
00188 if (record->lowerLimit() == SearchTable::CheckmateSpecialDepth)
00189 {
00190 if (! record->bestMove().getMove().isPass())
00191 os << "win by checkmate " << record->bestMove().getMove() << "\n";
00192 else
00193 os << "lose by checkmate\n";
00194 return;
00195 }
00196
00197 TopLevelAnalyzer helper(key.turn(), &table, num_print_moves, os);
00198 helper.examineAll(record);
00199 }
00200 void osl::search::analyzer::
00201 TableAnalyzer::examineUpperBounds(const HashKey& key, int num_print_moves) const
00202 {
00203 os << "analysis of a node after the best move\n";
00204 const SimpleHashRecord *record = table.find(key);
00205 if (! record)
00206 {
00207 os << "record not found\n";
00208 return;
00209 }
00210
00211 TopLevelAnalyzer helper(key.turn(), &table, num_print_moves, os);
00212 helper.examineAll(record);
00213 }
00214
00215 void osl::search::analyzer::
00216 TableAnalyzer::makeBestMoveList(const SimpleHashRecord *record, SearchMoveList& moves,
00217 int max)
00218 {
00219 RecordSet dejavu;
00220 for (int i=0; i<max; ++i)
00221 {
00222 if (! record)
00223 break;
00224 const SearchMove best_move = record->bestMove();
00225 if ((! best_move.validMove())
00226 || (dejavu.find(record) != dejavu.end()))
00227 break;
00228 moves.push_front(best_move);
00229 if (best_move.getMove().isPass())
00230 break;
00231 dejavu.insert(record);
00232 record = best_move.record;
00233 }
00234 moves.reverse();
00235 }
00236
00237
00238
00239
00240
00241