00001
00002
00003 #include "osl/search/historyTable.h"
00004 #include "osl/misc/carray3d.h"
00005 #include "osl/move_generator/legalMoves.h"
00006 #include "osl/container/moveVector.h"
00007 #include <map>
00008 #include <cmath>
00009 #include <iostream>
00010
00011 const int osl::search::HistoryTable::maximum_logp;
00012
00013 struct osl::search::HistoryTable::Table
00014 {
00016 typedef CArray3d<double,2,Position::SIZE,Position::SIZE> array_t;
00017 array_t moves;
00018 double total;
00019 Table() : total(0.0)
00020 {
00021 moves.fill(0.0);
00022 }
00023 void clear()
00024 {
00025 moves.fill(0.0);
00026 total = 0.0;
00027 }
00028 static int fromIndex(Move move)
00029 {
00030 const Position from = move.from();
00031 return from.isPieceStand() ? (int)move.ptype() : (int)from.index();
00032 }
00033 double& count(Move move)
00034 {
00035 return moves[playerToIndex(move.player())][fromIndex(move)]
00036 [move.to().index()];
00037 }
00038 const double& count(Move move) const
00039 {
00040 return moves[playerToIndex(move.player())][fromIndex(move)]
00041 [move.to().index()];
00042 }
00043 };
00044
00045 osl::search::
00046 HistoryTable::HistoryTable()
00047 : table(new Table)
00048 {
00049 }
00050
00051 osl::search::
00052 HistoryTable::~HistoryTable()
00053 {
00054 }
00055
00056 osl::search::HistoryTable& osl::search::
00057 HistoryTable::operator=(const HistoryTable& o)
00058 {
00059 if (this != &o)
00060 *table = *o.table;
00061 return *this;
00062 }
00063
00064 void osl::search::
00065 HistoryTable::clear()
00066 {
00067 table->clear();
00068 }
00069
00070 void osl::search::
00071 HistoryTable::setMove(int depth_left, Move best_move)
00072 {
00073 const double count = depth_left*depth_left;
00074 table->count(best_move) += count;
00075 table->total += count;
00076 }
00077
00078 void osl::search::
00079 HistoryTable::getMoves(const NumEffectState& state,
00080 MoveLogProbVector& moves) const
00081 {
00082 MoveVector plain_moves;
00083 LegalMoves::generate(state, plain_moves);
00084
00085 typedef std::multimap<int, Move> sorter_t;
00086 sorter_t sorter;
00087 for (MoveVector::const_iterator p=plain_moves.begin();
00088 p!=plain_moves.end(); ++p)
00089 {
00090 const int logp = this->logp(*p);
00091 if (logp < maximum_logp)
00092 sorter.insert(std::make_pair(logp, *p));
00093 }
00094
00095 moves.clear();
00096 for (sorter_t::const_iterator p=sorter.begin();
00097 p!=sorter.end() && moves.size() < moves.capacity(); ++p)
00098 {
00099 moves.push_back(MoveLogProb(p->second, p->first));
00100 }
00101 }
00102
00103 int osl::search::
00104 HistoryTable::logp(double p)
00105 {
00106 return static_cast<int>(-log(p)/log(2.0)*100);
00107 }
00108
00109 int osl::search::
00110 HistoryTable::logp(Move move) const
00111 {
00112 const double& count = table->count(move);
00113 if (count < 1)
00114 return maximum_logp;
00115 return std::max(50,logp(sqrt(count) / sqrt(table->total)));
00116 }
00117
00118 double osl::search::
00119 HistoryTable::count(Move move) const
00120 {
00121 return table->count(move);
00122 }
00123
00124 namespace osl
00125 {
00126 namespace
00127 {
00128 const Move make_move(Player player, int i, int j)
00129 {
00130 const Position to = Position::makeDirect(j);
00131 Position from = Position::makeDirect(i);
00132 if (! from.isOnBoard())
00133 {
00134 const Ptype ptype = static_cast<Ptype>(i);
00135 assert(isBasic(ptype));
00136 return Move(to, ptype, player);
00137 }
00138 return Move(from, to, KING, PTYPE_EMPTY, false, player);
00139 }
00140 }
00141 }
00142
00143 void osl::search::
00144 HistoryTable::dump(std::ostream& os) const
00145 {
00146 typedef CArray3d<double,2,Position::SIZE,Position::SIZE> array_t;
00147 typedef std::multimap<int, Move> sorter_t;
00148 sorter_t sorter;
00149 const double denominator = sqrt(table->total);
00150 for (int i=0; i<Position::SIZE; ++i)
00151 {
00152 for (int j=0; j<Position::SIZE; ++j)
00153 {
00154 double count = table->moves[playerToIndex(BLACK)][i][j];
00155 if (count >= 1)
00156 {
00157 const int logp = HistoryTable::logp(sqrt(count)/denominator);
00158 sorter.insert(std::make_pair(logp, make_move(BLACK, i, j)));
00159 }
00160 count = table->moves[playerToIndex(WHITE)][i][j];
00161 if (count >= 1)
00162 {
00163 const int logp = HistoryTable::logp(sqrt(count)/denominator);
00164 sorter.insert(std::make_pair(logp, make_move(WHITE, i, j)));
00165 }
00166 }
00167 }
00168
00169 for (sorter_t::const_iterator p=sorter.begin(); p!=sorter.end(); ++p)
00170 {
00171 os << p->first << " " << p->second << "\n";
00172 }
00173 }
00174
00175
00176
00177
00178
00179