00001 #ifndef _NULLWINDOW_SEARCH_TCC
00002 #define _NULLWINDOW_SEARCH_TCC
00003
00004 #include "osl/search/nullWindowSearch.h"
00005 #include "osl/search/nullWindowSearchPolicy.h"
00006 #include "osl/search/simpleHashRecord.h"
00007 #include "osl/search/searchFramework.tcc"
00008
00009
00010
00011
00012
00013
00014
00015
00016 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00017 osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00018 NullWindowSearch(const HashEffectState& s, typename framework_t::checkmate_t& c,
00019 Table *t, Recorder& r)
00020 : framework_t(s, c, t, r),
00021 black_lower_bound(framework_t::minusInfty(BLACK)),
00022 black_upper_bound(framework_t::minusInfty(WHITE)),
00023 null_window(0)
00024 {
00025 }
00026
00027 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00028 osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00029 ~NullWindowSearch()
00030 {
00031 }
00032
00033
00034
00035
00036
00037 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00038 int osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00039 nullWindowSearchOfTurn(int threshold, const SearchMove& move, int limit)
00040 {
00041 if (framework_t::state().getTurn() == BLACK)
00042 return nullWindowSearch<BLACK>(threshold, move, limit);
00043 else
00044 return nullWindowSearch<WHITE>(threshold, move, limit);
00045 }
00046
00047 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00048 template <osl::Player P>
00049 int osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00050 nullWindowSearch(int threshold, const SearchMove& move, int limit)
00051 {
00052 assert(threshold % 2);
00053 assert(! framework_t::isWinValue(BLACK, threshold));
00054 assert(! framework_t::isWinValue(WHITE, threshold));
00055 assert(EvalTraits<P>::betterThan(threshold, rootLowerBound(P)));
00056 assert(EvalTraits<P>::betterThan(rootUpperBound(P), threshold));
00057
00058 null_window = NullWindow(threshold);
00059 framework_t::setRoot(limit);
00060 assert(framework_t::curDepth() == 0);
00061 int max_value = framework_t::minusInfty(P);
00062 SearchMove best_move;
00063 nullWindowSearch<P,false>(move, max_value, best_move);
00064 return max_value;
00065 }
00066
00067
00068 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00069 template <osl::Player P, bool best_move_extension>
00070 bool osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00071 nullWindowSearch(const SearchMove& move, int& max_val, SearchMove& best_move)
00072 {
00073 assert(P == move.getMove().player());
00074 assert(P == framework_t::state().getTurn());
00075 assert(eval::betterThan(P, null_window.beta(), max_val));
00076
00077 typedef null_window::DoUndoNullWindow<NullWindowSearch,P,best_move_extension>
00078 helper_t;
00079 helper_t helper(this, move, max_val);
00080 const int value
00081 = framework_t::template searchWithMove<P,helper_t>(move, helper);
00082 if (eval::betterThan(P, value, max_val))
00083 {
00084 max_val = value;
00085 best_move = move;
00086 if (eval::betterThan(P, value, null_window.alpha()))
00087 return true;
00088 }
00089 return false;
00090 }
00091
00092 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00093 template <osl::Player P> inline
00094 int osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00095 normalSearch(const SearchMove& moved,
00096 int logprob, int base_value, SearchMove& best_move)
00097 {
00098 const Player Turn = PlayerTraits<P>::opponent;
00099 typedef null_window::NullWindowSearchPolicy<NullWindowSearch,Turn,false>
00100 normal_policy_t;
00101
00102 framework_t::recorder.tryMove(moved.moveLogProb(),
00103 null_window.alpha(),framework_t::curLimit());
00104 framework_t::subLimit(logprob);
00105
00106 normal_policy_t normalPolicy(this, nullWindow());
00107 const int val = framework_t::template searchAllMoves<Turn,normal_policy_t>
00108 (moved.record, normalPolicy, best_move);
00109
00110 framework_t::addLimit(logprob);
00111 framework_t::recorder.recordValue(moved.moveLogProb(),
00112 val,eval::betterThan(P, val,base_value),
00113 framework_t::curLimit());
00114 return val;
00115 }
00116
00117 template <class Eval,typename MoveGenerator, typename Table, typename Recorder, typename Probabilities>
00118 template <osl::Player P, bool best_move_extension>
00119 int osl::search::NullWindowSearch<Eval,MoveGenerator,Table,Recorder,Probabilities>::
00120 nullWindowSearchAfterMove(const SearchMove& moved, int base_value)
00121 {
00122 assert(alt(P) == framework_t::state().getTurn());
00123 assert(P == moved.getMove().player());
00124 assert(eval::betterThan(P, null_window.alpha(), base_value));
00125 assert(moved.getLogProb() <= framework_t::curLimit());
00126
00127 const Player Turn = PlayerTraits<P>::opponent;
00128 typedef null_window::NullWindowSearchPolicy<NullWindowSearch,Turn,true>
00129 extend_policy_t;
00130 SearchMove best_move;
00131 assert(EvalTraits<P>::betterThan(rootUpperBound(P), rootLowerBound(P)));
00132 const int extend_base = EvalTraits<P>::max(rootLowerBound(P), base_value);
00133
00134 int val = normalSearch<P>(moved, moved.getLogProb(), base_value, best_move);
00135
00136 if (! eval::betterThan(P, val, extend_base))
00137 return val;
00138 if ((! best_move_extension)
00139 && (! eval::betterThan(P, val, null_window.alpha())))
00140 return val;
00141
00142
00143
00144 if (moved.getLogProb()
00145 > Probabilities::ReSearch*4 + framework_t::ReSearchLimitMargin)
00146 {
00147 val = normalSearch<P>(moved, Probabilities::ReSearch*4, base_value, best_move);
00148 if (! eval::betterThan(P, val, extend_base))
00149 return val;
00150 if ((! best_move_extension)
00151 && (! eval::betterThan(P, val, null_window.alpha())))
00152 return val;
00153 }
00154 if (moved.getLogProb()
00155 > Probabilities::ReSearch*2 + framework_t::ReSearchLimitMargin)
00156 {
00157 val = normalSearch<P>(moved, Probabilities::ReSearch*2, base_value, best_move);
00158 if (! eval::betterThan(P, val, extend_base))
00159 return val;
00160 if ((! best_move_extension)
00161 && (! eval::betterThan(P, val, null_window.alpha())))
00162 return val;
00163 }
00164 if (moved.getLogProb()
00165 > Probabilities::ReSearch + framework_t::ReSearchLimitMargin)
00166 {
00167 val = normalSearch<P>(moved, Probabilities::ReSearch, base_value, best_move);
00168 }
00169
00170 if (best_move_extension)
00171 return val;
00172 if (! eval::betterThan(P, val, null_window.alpha()))
00173 return val;
00174
00175
00176 #ifndef NO_BEST_MOVE_EXTENSION
00177
00178 if (Probabilities::DefaultProb != Probabilities::ReSearch)
00179 {
00180 extend_policy_t extendPolicy(this, nullWindow());
00181
00182 framework_t::recorder.retryMove(moved.moveLogProb(), null_window.alpha(),
00183 framework_t::curLimit(),2);
00184 const int log_prob = std::min(moved.getLogProb(), (int)Probabilities::ReSearch);
00185 framework_t::subLimit(log_prob);
00186
00187 val = framework_t::template searchAllMoves<Turn,extend_policy_t>
00188 (moved.record, extendPolicy, best_move);
00189
00190 framework_t::addLimit(log_prob);
00191 framework_t::recorder.recordValue(moved.moveLogProb(), val,
00192 eval::betterThan(P, val,base_value),
00193 framework_t::curLimit());
00194 }
00195 #endif
00196 return val;
00197 }
00198
00199
00200
00201 #endif
00202
00203
00204
00205