00001 #include "osl/search/searchMoveVector.h"
00002 #include "osl/search/searchMove.h"
00003 #include "osl/search/simpleHashRecord.h"
00004 #include "osl/eval/evalTraits.h"
00005 #include "osl/misc/fixedCapacityVector.h"
00006 #include "osl/misc/reorder.h"
00007 #include <algorithm>
00008 #include <iostream>
00009
00010 std::ostream& osl::search::operator<<(std::ostream& os,
00011 SearchMoveVector const& mv)
00012 {
00013 os<< "SearchMoveVector" << std::endl;
00014 for (SearchMoveVector::const_iterator p=mv.begin(); p!=mv.end(); ++p)
00015 {
00016 os << (*p)->moveLogProb() << " " << (*p)->record << std::endl;
00017 }
00018 return os << std::endl;
00019 }
00020
00021 namespace osl
00022 {
00023 namespace search
00024 {
00025 template <bool prefer_less>
00026 struct LogProbCompare
00027 {
00028 bool operator()(const SearchMove *l, const SearchMove *r) const
00029 {
00030 if (prefer_less)
00031 return l->getLogProb() < r->getLogProb();
00032 else
00033 return l->getLogProb() > r->getLogProb();
00034 }
00035 };
00036
00037 template <Player P>
00038 struct SearchValueCompare
00039 {
00040 const int default_value;
00041 explicit SearchValueCompare(int d) : default_value(d) {}
00042 int value(const SearchMove& move) const
00043 {
00044 const SimpleHashRecord *record = move.record;
00045 if (! record)
00046 return default_value;
00047 if (record->hasUpperBound(0))
00048 {
00049 const int upper = record->upperBound();
00050 if (record->hasLowerBound(0))
00051 return EvalTraits<P>::max(upper, record->lowerBound());
00052 return upper;
00053 }
00054 return (record->hasLowerBound(0) ? record->lowerBound() : default_value);
00055 }
00056 bool operator()(const SearchMove *l, const SearchMove *r) const
00057 {
00058 if (l->record == 0 && r->record == 0)
00059 {
00060 if (l->getLogProb() != r->getLogProb())
00061 return l->getLogProb() < r->getLogProb();
00062 }
00063 const int l_value = value(*l);
00064 const int r_value = value(*r);
00065 return EvalTraits<P>::betterThan(l_value, r_value);
00066 }
00067 };
00068 template <Player P>
00069 struct SearchValueIndexCompare
00070 {
00071 typedef FixedCapacityVector<std::pair<int,int>,Move::MaxUniqMoves> vector_t;
00072 vector_t *values;
00073 const int default_value;
00074
00075 explicit SearchValueIndexCompare(vector_t *v, int d)
00076 : values(v), default_value(d) {}
00077 int value(int index) const { return (*values)[index].first; }
00078 int logProb(int index) const { return (*values)[index].second; }
00079 bool operator()(int l, int r) const
00080 {
00081 const int l_value = value(l);
00082 const int r_value = value(r);
00083 if (l_value == default_value && r_value == default_value)
00084 {
00085 if (logProb(l) != logProb(r))
00086 return logProb(l) < logProb(r);
00087 }
00088 return EvalTraits<P>::betterThan(l_value, r_value);
00089 }
00090 };
00091
00092 template void SearchMoveVector::sortByValue<BLACK>(int);
00093 template void SearchMoveVector::sortByValue<WHITE>(int);
00094 }
00095 }
00096
00097 void osl::search::
00098 SearchMoveVector::sortByProbability()
00099 {
00100 std::sort(begin(), end(), LogProbCompare<true>());
00101 }
00102 void osl::search::
00103 SearchMoveVector::sortByProbabilityReverse()
00104 {
00105 std::sort(begin(), end(), LogProbCompare<false>());
00106 }
00107
00108 template <osl::Player P>
00109 void osl::search::
00110 SearchMoveVector::sortByValueUP(int default_value)
00111 {
00112
00113 std::sort(begin(), end(), SearchValueCompare<P>(default_value));
00114 }
00115
00116 template <osl::Player P>
00117 void osl::search::
00118 SearchMoveVector::sortByValueMP(int default_value)
00119 {
00120 if (empty())
00121 return;
00122
00123 FixedCapacityVector<std::pair<int,int>,Move::MaxUniqMoves> values;
00124 FixedCapacityVector<int,Move::MaxUniqMoves> indices;
00125 SearchValueCompare<P> comp(default_value);
00126 for (const_iterator p=begin(); p!=end(); ++p) {
00127 values.push_back(std::make_pair(comp.value(**p), (*p)->getLogProb()));
00128 indices.push_back(indices.size());
00129 }
00130 std::sort(indices.begin(), indices.end(),
00131 SearchValueIndexCompare<P>(&values, default_value));
00132
00133 misc::Reorder::reorder(begin(), end(), indices);
00134 }
00135
00136 template <osl::Player P>
00137 void osl::search::
00138 SearchMoveVector::sortByValue(int default_value)
00139 {
00140 #ifndef OSL_SMP
00141 sortByValueUP<P>(default_value);
00142 #else
00143 sortByValueMP<P>(default_value);
00144 #endif
00145 }
00146
00147
00148
00149
00150