00001
00002
00003 #ifndef SEARCHSTATE_H
00004 #define SEARCHSTATE_H
00005
00006 #include "osl/search/killerMoveTable.h"
00007 #include "osl/search/bigramKillerMove.h"
00008 #include "osl/search/historyTable.h"
00009 #include "osl/search/recordStack.h"
00010 #include "osl/search/firstMoveThreatmate.h"
00011 #include "osl/checkmate/dualCheckmateSearcher.h"
00012 #include "osl/checkmate/fixedDepthSearcher.h"
00013 #include "osl/effect_util/neighboring8Direct.h"
00014 #include "osl/state/numEffectState.h"
00015 #include "osl/hash/hashKey.h"
00016 #include "osl/repetitionCounter.h"
00017 #include "osl/container/moveStack.h"
00018 #include "osl/apply_move/applyMoveWithPath.h"
00019 #include "osl/misc/alarm.h"
00020
00021 #ifdef OSL_SMP
00022 # include "osl/search/parallelSearch.h"
00023 #endif
00024
00025 #include <boost/shared_ptr.hpp>
00026 #include <boost/utility.hpp>
00027
00028 namespace osl
00029 {
00030 namespace search
00031 {
00032 class Worker;
00036 struct SearchStateShared : boost::noncopyable
00037 {
00038 BigramKillerMove bigram_killers;
00039 HistoryTable history_table;
00040
00041 SearchStateShared();
00042 ~SearchStateShared();
00043 };
00047 class SearchStateCore
00048 {
00049 public:
00050 typedef DualCheckmateSearcher<> checkmate_t;
00051 private:
00052 NumEffectState current_state;
00053 checkmate_t* checkmate_searcher;
00054 const Worker *worker_cache;
00055 #ifdef OSL_SMP
00056 public:
00057 void setCheckmateSearcher(checkmate_t *new_checkmate,
00058 const Worker *new_worker) {
00059 checkmate_searcher = new_checkmate;
00060 worker_cache = new_worker;
00061 }
00062 private:
00063 #endif
00064 PathEncoding current_path;
00065 MoveStack move_history;
00066 KillerMoveTable killer_moves;
00067 int root_depth;
00068 protected:
00069 RecordStack record_stack;
00070 RepetitionCounter repetition_counter;
00071 boost::shared_ptr<SearchStateShared> shared;
00075 volatile int stop_flag;
00076 public:
00077 SearchStateCore(const NumEffectState& s, checkmate_t& checker);
00078 virtual ~SearchStateCore();
00079 int curDepth() const { return history().size() - root_depth; }
00080
00081
00082 const AlarmSwitch alarmSwitch() { return AlarmSwitch(&stop_flag); }
00083 void setTimeOut(int seconds);
00084 void resetTimeOut();
00085 bool timerAvailable() const { return stop_flag == Alarm::WATCHING; }
00086 private:
00087 void throwTimeOut();
00088 public:
00089 void testTimeOut() {
00090 if (stop_flag == Alarm::TIMEOUT)
00091 throwTimeOut();
00092 #ifdef OSL_SMP
00093 if (worker_cache)
00094 worker_cache->checkStop();
00095 #endif
00096 }
00103 virtual void setState(const NumEffectState& s);
00104 void setHistory(const MoveStack& h);
00105 bool hasLastRecord(unsigned int n=0) const
00106 {
00107 return record_stack.hasLastRecord(n);
00108 }
00109 SimpleHashRecord** lastRecordPtr(unsigned int n=0)
00110 {
00111 return record_stack.lastRecordPtr(n);
00112 }
00113 SimpleHashRecord* lastRecord(unsigned int n=0)
00114 {
00115 return *lastRecordPtr(n);
00116 }
00117 SimpleHashRecord *rootRecord()
00118 {
00119 assert(! record_stack.empty());
00120 return *record_stack.lastRecordPtr(record_stack.size()-1);
00121 }
00122 void setRootRecord(SimpleHashRecord *root)
00123 {
00124 assert(! record_stack.empty());
00125 *record_stack.lastRecordPtr(record_stack.size()-1) = root;
00126 }
00127
00128
00129 void setKillerMove(Move best_move)
00130 {
00131 if (best_move.isPass())
00132 return;
00133 killer_moves.setMove(curDepth(), best_move);
00134 const Move last_move = lastMove();
00135 if (! last_move.isInvalid())
00136 {
00137 shared->bigram_killers.setMove(last_move, best_move);
00138 }
00139 }
00140 void getBigramKillerMoves(MoveVector& moves) const
00141 {
00142 shared->bigram_killers.getMove(state(), lastMove(), moves);
00143 #ifdef TRI_PLY_BIGRAM_KILLERS
00144 if (move_history.hasLastMove(3))
00145 shared->bigram_killers.getMove(state(), lastMove(3), moves);
00146 #endif
00147 }
00148 void getKillerMoves(MoveVector& moves) const
00149 {
00150 getBigramKillerMoves(moves);
00151 killer_moves.getMove(state(), curDepth(), moves);
00152 }
00153 const BigramKillerMove& bigramKillerMove() const {
00154 return shared->bigram_killers;
00155 }
00156 void setBigramKillerMove(const BigramKillerMove& killers);
00157 const HistoryTable& historyTable() const
00158 {
00159 return shared->history_table;
00160 }
00161
00162
00163 void pushPass()
00164 {
00165 const Move pass = Move::PASS(current_state.getTurn());
00166 current_state.changeTurn();
00167 current_path.pushMove(pass);
00168 move_history.push(pass);
00169 }
00170 void popPass()
00171 {
00172 const Move pass = Move::PASS(alt(current_state.getTurn()));
00173 current_state.changeTurn();
00174 current_path.popMove(pass);
00175 move_history.pop();
00176 }
00177 private:
00181 void pushBeforeApply(Move move, SimpleHashRecord**record)
00182 {
00183 move_history.push(move);
00184 record_stack.push(record);
00185 }
00186 struct Updator
00187 {
00188 const HashKey& new_hash;
00189 SearchStateCore *state;
00190 Updator(const HashKey& h, SearchStateCore *s)
00191 : new_hash(h), state(s)
00192 {
00193 }
00194 void update()
00195 {
00196 state->updateRepetitionCounterAfterMove(new_hash);
00197 }
00198 };
00199 template <class Function, class Eval>
00200 struct UpdateWrapper : public Updator
00201 {
00202 Function& function;
00203 Eval& eval;
00204 Move last_move;
00205 UpdateWrapper(const HashKey& h, SearchStateCore *s, Function& f, Eval& e, Move l)
00206 : Updator(h, s), function(f), eval(e), last_move(l)
00207 {
00208 }
00209 void operator()(Position to)
00210 {
00211 update();
00212 eval.update(state->state(), last_move);
00213 function(to);
00214 }
00215 };
00216 friend class Updator;
00220 void updateRepetitionCounterAfterMove(const HashKey& new_hash)
00221 {
00222 repetition_counter.push(new_hash, current_state);
00223 }
00227 void popAfterApply()
00228 {
00229 record_stack.pop();
00230 repetition_counter.pop();
00231 move_history.pop();
00232 }
00233 public:
00237 template <Player P, class Function, class Eval>
00238 void doUndoMoveOrPass(const HashKey& new_hash,
00239 Move move, SimpleHashRecord **move_record,
00240 Function& f, Eval& e)
00241 {
00242 pushBeforeApply(move, move_record);
00243 UpdateWrapper<Function, Eval> wrapper(new_hash, this, f, e, move);
00244 ApplyMoveWithPath<P>::doUndoMoveOrPass(current_state, current_path,
00245 move, wrapper);
00246 popAfterApply();
00247 }
00248 const Move lastMove(int i=1) const { return move_history.lastMove(i); }
00249 const MoveStack& history() const { return move_history; }
00250 const RecordStack& recordHistory() const { return record_stack; }
00251 const PathEncoding& path() const { return current_path; }
00252 const NumEffectState& state() const { return current_state; }
00253 const checkmate_t& checkmateSearcher() const { return *checkmate_searcher; }
00254 const RepetitionCounter& repetitionCounter() const {
00255 return repetition_counter;
00256 }
00257 const HashKey& currentHash() const
00258 {
00259 return repetition_counter.history().top();
00260 }
00261
00265 template <Player P, class Function>
00266 void doUndoMoveLight(Move move, Function& f)
00267 {
00268 ApplyMoveWithPath<P>::doUndoMoveOrPass
00269 (static_cast<NumEffectState&>(current_state), current_path,
00270 move, f);
00271 }
00272
00273 template <Player P>
00274 bool isLosingState(int node_limit)
00275 {
00276 assert(P == path().turn());
00277 const bool lose =
00278 checkmate_searcher->isLosingState<P>
00279 (node_limit, current_state, currentHash(), path(), lastMove());
00280 return lose;
00281 }
00282 public:
00283 template <Player P>
00284 bool isWinningState(int node_limit, Move& checkmate_move,
00285 AttackOracleAges& age)
00286 {
00287 assert(P == path().turn());
00288 const bool win = checkmate_searcher->isWinningState<P>
00289 (node_limit, current_state, currentHash(), path(), checkmate_move, age,
00290 lastMove());
00291 return win;
00292 }
00294 template <Player P>
00295 bool isWinningStateShort(int depth, Move& checkmate_move)
00296 {
00297 checkmate::FixedDepthSearcher searcher(current_state);
00298 const ProofDisproof pdp=searcher.hasCheckmateMove<P>(depth, checkmate_move);
00299 return pdp.isCheckmateSuccess();
00300 }
00304 template <Player P>
00305 bool isThreatmateState(int node_limit, Move& threatmate_move,
00306 AttackOracleAges& age)
00307 {
00308 assert(P == path().turn());
00309 current_state.changeTurn();
00310 HashKey threatmate_hash = currentHash();
00311 threatmate_hash.changeTurn();
00312 const PathEncoding threatmate_path(current_state.getTurn());
00313 const Player Opponent = PlayerTraits<P>::opponent;
00314 const bool threatmate
00315 = checkmate_searcher->template isWinningState<Opponent>
00316 (node_limit, current_state,
00317 threatmate_hash, threatmate_path, threatmate_move, age);
00318 current_state.changeTurn();
00319 return threatmate;
00320 }
00321 template <Player P>
00322 bool isThreatmateStateShort(int depth, Move& threatmate_move)
00323 {
00324 assert(P == path().turn());
00325 current_state.changeTurn();
00326
00327 const Player Opponent = PlayerTraits<P>::opponent;
00328
00329 checkmate::FixedDepthSearcher searcher(current_state);
00330 const ProofDisproof pdp
00331 = searcher.hasCheckmateMove<Opponent>(depth, threatmate_move);
00332
00333 current_state.changeTurn();
00334 return pdp.isCheckmateSuccess();
00335 }
00336 virtual bool abort(Move) const;
00337
00338 bool tryThreatmate() const
00339 {
00340 const Move last_move = lastMove();
00341 if (! last_move.isNormal())
00342 return false;
00343 const Position king = state().getKingPosition(state().getTurn());
00344 if (curDepth() == 1)
00345 return FirstMoveThreatmate::isMember(last_move, king);
00346 return Neighboring8Direct::hasEffect
00347 (state(), last_move.ptypeO(), last_move.to(), king);
00348
00349 }
00350
00351 };
00352
00356 class SearchState : public SearchStateCore
00357 {
00358 public:
00360 static const int ReSearchLimitMargin = 80;
00361 protected:
00362 int root_limit;
00363 int cur_limit;
00364 public:
00365 SearchState(const NumEffectState& s, checkmate_t& checker);
00366 virtual ~SearchState();
00367
00368 void setState(const NumEffectState& s);
00369 void setKillerMove(Move best_move)
00370 {
00371 if (best_move.isPass())
00372 return;
00373 shared->history_table.setMove(curLimit(), best_move);
00374 SearchStateCore::setKillerMove(best_move);
00375 }
00376
00377 int curLimit() const { return cur_limit; }
00378
00379 bool abort(Move) const;
00380
00381 protected:
00385 void setRoot(int limit)
00386 {
00387 root_limit = limit;
00388 cur_limit = limit;
00389 }
00390 void addLimit(int limit) { cur_limit += limit; assert(cur_limit >= 0); }
00391 void subLimit(int limit) { cur_limit -= limit; assert(cur_limit >= 0); }
00392
00396 int countSacrificeCheck2(int history_max) const;
00398 void checkPointSearchAllMoves();
00399 };
00400 }
00401 }
00402
00403 #endif
00404
00405
00406
00407