00001
00002
00003 #ifndef _QUIESCENCESEARCH_H
00004 #define _QUIESCENCESEARCH_H
00005
00006 #include "osl/search/fixedEval.h"
00007 #include "osl/search/quiescenceRecord.h"
00008 #include "osl/search/searchState.h"
00009 #include "osl/eval/pieceEval.h"
00010 #include "osl/state/numEffectState.h"
00011 #include "osl/pathEncoding.h"
00012 namespace osl
00013 {
00014 namespace container
00015 {
00016 class MoveVector;
00017 }
00018 namespace hash
00019 {
00020 class HashKey;
00021 }
00022 namespace search
00023 {
00024 class SimpleHashTable;
00025
00040 template <class EvalT>
00041 class QuiescenceSearch : protected FixedEval, private QSearchTraits
00042 {
00043 typedef FixedEval base_t;
00044 SearchStateCore& state;
00045 SimpleHashTable& table;
00046 int root_depth;
00047 int max_depth;
00051 int node_count;
00053 int depthFromRoot() const
00054 {
00055 return state.path().getDepth() - root_depth;
00056 }
00058 int depth() const
00059 {
00060 return max_depth - depthFromRoot();
00061 }
00062 public:
00063 typedef EvalT eval_t;
00064 typedef NumEffectState effect_state_t;
00065 using base_t::isWinValue;
00066
00067 typedef container::MoveVector MoveVector;
00068
00069 QuiescenceSearch(SearchStateCore& s, SimpleHashTable& t)
00070 : state(s), table(t), root_depth(s.path().getDepth()),
00071 max_depth(QSearchTraits::MaxDepth), node_count(0)
00072 {
00073 }
00074 template <Player P>
00075 int search(eval_t const& ev, Move last_move,
00076 int depth=QSearchTraits::MaxDepth)
00077 {
00078 assert(last_move.player() == alt(P));
00079 assert(state.state().getTurn() == P);
00080 max_depth = depth;
00081 return searchInternal<P>(base_t::winThreshold(alt(P)),
00082 base_t::winThreshold(P),
00083 ev, last_move);
00084 }
00085 int search(Player P, eval_t const& ev, Move last_move,
00086 int depth=QSearchTraits::MaxDepth)
00087 {
00088 if (P == BLACK)
00089 return search<BLACK>(ev, last_move, depth);
00090 else
00091 return search<WHITE>(ev, last_move, depth);
00092 }
00093 template <Player P>
00094 int searchIteratively(eval_t const& ev, Move last_move,
00095 int depth=QSearchTraits::MaxDepth)
00096 {
00097 assert(last_move.player() == alt(P));
00098 assert(state.state().getTurn() == P);
00099 return searchIteratively<P>(base_t::winThreshold(alt(P)),
00100 base_t::winThreshold(P),
00101 ev, last_move, depth);
00102 }
00103 int searchIteratively(Player P, eval_t const& ev, Move last_move,
00104 int depth=QSearchTraits::MaxDepth)
00105 {
00106 if (P == BLACK)
00107 return searchIteratively<BLACK>(ev, last_move, depth);
00108 else
00109 return searchIteratively<WHITE>(ev, last_move, depth);
00110 }
00111
00112 template <Player P>
00113 int searchIteratively(int alpha, int beta, eval_t const& ev, Move last_move,
00114 int depth)
00115 {
00116 assert(depth >= 2);
00117 int result=0;
00118 for (int i=2; i<=depth; i+=2)
00119 {
00120 max_depth = i;
00121 result=searchInternal<P>(alpha, beta, ev, last_move);
00122 }
00123 return result;
00124 }
00125 template <Player P>
00126 int search(int alpha, int beta, eval_t const& ev, Move last_move,
00127 int depth=QSearchTraits::MaxDepth)
00128 {
00129 max_depth = depth;
00130 return searchInternal<P>(alpha, beta, ev, last_move);
00131 }
00132 int search(Player P, int alpha, int beta, eval_t const& ev, Move last_move, int depth){
00133 if (P == BLACK)
00134 return search<BLACK>(alpha, beta, ev, last_move, depth);
00135 else
00136 return search<WHITE>(alpha, beta, ev, last_move, depth);
00137 }
00138 template <Player P>
00139 int searchProbCut(int alpha, int beta, eval_t const& ev, Move last_move);
00140 int searchProbCut(Player P, int alpha, int beta, eval_t const& ev, Move last_move)
00141 {
00142 if (P == BLACK)
00143 return searchProbCut<BLACK>(alpha, beta, ev, last_move);
00144 else
00145 return searchProbCut<WHITE>(alpha, beta, ev, last_move);
00146 }
00147
00148 template <Player P>
00149 int searchInternal(int alpha, int beta, eval_t const& ev, Move last_move,
00150 int additional_depth=0);
00151 private:
00152 template <Player P, bool has_record>
00153 int searchMain(QuiescenceRecord *record,
00154 int alpha, int beta, eval_t const& ev, Move last_move,
00155 int additional_depth);
00156 template <bool has_record, class TYPE> inline
00157 void recordGeneration(QuiescenceRecord *record, TYPE type,
00158 const MoveVector& moves);
00163 template <Player P, Ptype PTYPE, bool has_record>
00164 bool examineCapture(QuiescenceRecord *record,
00165 int& curVal, MoveVector& working, int& alpha,
00166 int beta, eval_t const& ev, Piece last_piece,
00167 int additional_depth);
00168 template <Player P, bool has_record>
00169 int staticValue(eval_t const& ev, int alpha, QuiescenceRecord *record);
00170 template <Player P>
00171 int passValue(int alpha, int beta, eval_t const& ev);
00172 int currentValueWithLastThreat(eval_t const& ev, Piece last_move_piece);
00173 public:
00179 template <Player P, bool has_record, bool has_dont_capture, MoveType move_type>
00180 bool examineMoves(QuiescenceRecord *record, int& curVal,
00181 const Move *first, const Move *last,
00182 int& alpha, int beta, eval_t const& ev,
00183 int additional_depth,
00184 Position dont_capture=Position::STAND());
00191 template <Player P>
00192 int takeBackValue(int alpha, int beta, eval_t const& ev, Move last_move);
00193 template <Player P>
00194 bool examineTakeBack(const MoveVector& moves,
00195 int& cur_val, int& alpha, int beta, eval_t const& ev);
00196
00204 template <Player P, bool calm_move_only, bool first_nolmal_move_only>
00205 bool examineTakeBack2(const MoveVector& moves,
00206 QuiescenceThreat& threat2,
00207 QuiescenceThreat& threat1,
00208 int beta, int beta2, eval_t const& ev);
00212 template <Player P, Ptype PTYPE>
00213 bool generateAndExamineTakeBack2(MoveVector& moves,
00214 QuiescenceThreat& threat2,
00215 QuiescenceThreat& threat1,
00216 int beta1, int beta2, eval_t const& ev);
00217
00221 template <Player P>
00222 int takeBackOrChase(int alpha, int beta, eval_t const& ev, Move last_move);
00223
00224 template <Player P>
00225 int staticValueWithThreat(eval_t const& ev, int alpha,
00226 QuiescenceThreat& threat1,
00227 QuiescenceThreat& threat2);
00228 template <Player P>
00229 int staticValueWithThreat(eval_t const& ev)
00230 {
00231 QuiescenceThreat t1, t2;
00232 return staticValueWithThreat<P>(ev, base_t::winThreshold(alt(P)),
00233 t1, t2);
00234 }
00235 int staticValueWithThreat(eval_t const& ev)
00236 {
00237 if (state.state().getTurn() == BLACK)
00238 return staticValueWithThreat<BLACK>(ev);
00239 else
00240 return staticValueWithThreat<WHITE>(ev);
00241 }
00242 int nodeCount() const { return node_count; }
00243 const NumEffectState& currentState() const { return state.state(); }
00244 };
00245
00246 }
00247 using search::QuiescenceSearch;
00248 }
00249
00250
00251 #endif
00252
00253
00254
00255