00001
00002
00003 #ifndef SEARCHSTATE2_H
00004 #define SEARCHSTATE2_H
00005
00006 #include "osl/search/killerMoveTable.h"
00007 #include "osl/search/bigramKillerMove.h"
00008 #include "osl/search/firstMoveThreatmate.h"
00009 #include "osl/search/simpleHashRecord.h"
00010 #include "osl/checkmate/dualCheckmateSearcher.h"
00011 #include "osl/checkmate/fixedDepthSearcher.h"
00012 #include "osl/effect_util/neighboring8Direct.h"
00013 #include "osl/state/numEffectState.h"
00014 #include "osl/hash/hashKey.h"
00015 #include "osl/repetitionCounter.h"
00016 #include "osl/container/moveStack.h"
00017 #include "osl/apply_move/applyMoveWithPath.h"
00018 #include "osl/misc/alarm.h"
00019 #include "osl/misc/fixedCapacityVector.h"
00020
00021 #include <boost/shared_ptr.hpp>
00022 #include <boost/utility.hpp>
00023
00024 namespace osl
00025 {
00026 namespace search
00027 {
00032 class RecordStack2
00033 {
00034 static const int SEARCH_DEPTH_MAX = 64;
00035 FixedCapacityVector<SimpleHashRecord*, SEARCH_DEPTH_MAX> data;
00036 public:
00037 RecordStack2();
00038 void clear();
00039 void push(SimpleHashRecord *r) { data.push_back(r); }
00040 void pop() { assert(size() > 1); data.pop_back(); }
00041
00042 SimpleHashRecord* lastRecord(unsigned int n=0) const
00043 {
00044 assert(size() > n);
00045 return data[size()-1-n];
00046 }
00047 SimpleHashRecord* rootRecord() const
00048 {
00049 assert(! empty());
00050 return data[0];
00051 }
00052 void setRootRecord(SimpleHashRecord *root) { data[0] = root; }
00053 void setLastRecord(SimpleHashRecord *r) {
00054 assert(size() > 0);
00055 data[size()-1] = r;
00056 }
00057
00058 size_t size() const { return data.size(); }
00059 bool empty() const { return data.empty(); }
00060 bool hasLastRecord(unsigned int n=0) const
00061 {
00062 return size() > n;
00063 }
00064
00065 void dump() const;
00066 };
00067
00068 class Worker;
00072 struct SearchState2Shared : boost::noncopyable
00073 {
00074 BigramKillerMove bigram_killers;
00075 KillerMoveTable killer_moves;
00076
00077 SearchState2Shared();
00078 ~SearchState2Shared();
00079 };
00080 #define search_assert(x) assert(((x) || (SearchState2Core::abort())))
00081 #define search_assert2(x, m) assert(((x) || (SearchState2Core::abort(m))))
00082 class AlphaBeta2Parallel;
00085 class SearchState2Core
00086 {
00087 friend class AlphaBeta2Parallel;
00088 public:
00089 enum { MaxDepth = 64 };
00090 typedef DualCheckmateSearcher<> checkmate_t;
00091 private:
00092 NumEffectState current_state;
00093 checkmate_t* checkmate_searcher;
00094 #ifdef OSL_SMP
00095 public:
00096 void setCheckmateSearcher(checkmate_t *new_checkmate) {
00097 checkmate_searcher = new_checkmate;
00098 }
00099 private:
00100 #endif
00101 PathEncoding current_path;
00102 MoveStack move_history;
00103 int root_depth;
00104 protected:
00105 RecordStack2 record_stack;
00106 RepetitionCounter repetition_counter;
00107 boost::shared_ptr<SearchState2Shared> shared;
00108 typedef FixedCapacityVector<Move,MaxDepth> PVVector;
00109 CArray<PVVector,MaxDepth> pv;
00110 enum NodeType { PvNode = 0, AllNode = 1, CutNode = -1, };
00111 CArray<NodeType,MaxDepth> node_type;
00112 public:
00113 volatile bool stop;
00114 static CArray<int, MaxDepth> depth_node_count_quiesce;
00115 SearchState2Core(const NumEffectState& s, checkmate_t& checker);
00116 virtual ~SearchState2Core();
00117 int curDepth() const { return history().size() - root_depth; }
00118
00125 virtual void setState(const NumEffectState& s);
00126 void setHistory(const MoveStack& h);
00127 bool hasLastRecord(unsigned int n=0) const
00128 {
00129 return record_stack.hasLastRecord(n);
00130 }
00131 SimpleHashRecord* lastRecord(unsigned int n=0)
00132 {
00133 return record_stack.lastRecord(n);
00134 }
00135 const SimpleHashRecord* lastRecord(unsigned int n=0) const
00136 {
00137 return record_stack.lastRecord(n);
00138 }
00139 SimpleHashRecord *rootRecord()
00140 {
00141 return record_stack.rootRecord();
00142 }
00143 void setCurrentRecord(SimpleHashRecord *r)
00144 {
00145 search_assert((int)record_stack.size() == curDepth()+1);
00146 record_stack.setLastRecord(r);
00147 }
00148 void setRootRecord(SimpleHashRecord *root)
00149 {
00150 search_assert(record_stack.size() == 1);
00151 search_assert(curDepth() == 0);
00152 record_stack.setRootRecord(root);
00153 }
00154
00155
00156 void setKillerMove(Move best_move)
00157 {
00158 if (best_move.isPass())
00159 return;
00160 shared->killer_moves.setMove(curDepth(), best_move);
00161 const Move last_move = lastMove();
00162 if (! last_move.isInvalid()) {
00163 search_assert(best_move.player() != last_move.player());
00164 shared->bigram_killers.setMove(last_move, best_move);
00165 }
00166 }
00167 void getBigramKillerMoves(MoveVector& moves) const
00168 {
00169 shared->bigram_killers.getMove(state(), lastMove(), moves);
00170 #ifdef TRI_PLY_BIGRAM_KILLERS
00171 if (move_history.hasLastMove(3))
00172 shared->bigram_killers.getMove(state(), lastMove(3), moves);
00173 #endif
00174 }
00175 void getKillerMoves(MoveVector& moves) const
00176 {
00177 getBigramKillerMoves(moves);
00178 shared->killer_moves.getMove(state(), curDepth(), moves);
00179 }
00180 const BigramKillerMove& bigramKillerMove() const {
00181 return shared->bigram_killers;
00182 }
00183 void setBigramKillerMove(const BigramKillerMove& killers);
00184
00185
00186 void pushPass()
00187 {
00188 const Move pass = Move::PASS(current_state.getTurn());
00189 current_state.changeTurn();
00190 current_path.pushMove(pass);
00191 move_history.push(pass);
00192 }
00193 void popPass()
00194 {
00195 const Move pass = Move::PASS(alt(current_state.getTurn()));
00196 current_state.changeTurn();
00197 current_path.popMove(pass);
00198 move_history.pop();
00199 }
00200 private:
00204 void pushBeforeApply(Move move)
00205 {
00206 move_history.push(move);
00207 record_stack.push(0);
00208 assert(curDepth() > 0);
00209 node_type[curDepth()] = static_cast<NodeType>(-node_type[curDepth()-1]);
00210 }
00211 struct Updator
00212 {
00213 const HashKey& new_hash;
00214 SearchState2Core *state;
00215 Updator(const HashKey& h, SearchState2Core *s)
00216 : new_hash(h), state(s)
00217 {
00218 }
00219 void update()
00220 {
00221 state->updateRepetitionCounterAfterMove(new_hash);
00222 }
00223 };
00224 template <class Function>
00225 struct UpdateWrapper : public Updator
00226 {
00227 Function& function;
00228 UpdateWrapper(const HashKey& h, SearchState2Core *s, Function& f)
00229 : Updator(h, s), function(f)
00230 {
00231 }
00232 void operator()(Position to)
00233 {
00234 update();
00235 function(to);
00236 }
00237 };
00238 friend class Updator;
00242 void updateRepetitionCounterAfterMove(const HashKey& new_hash)
00243 {
00244 repetition_counter.push(new_hash, current_state);
00245 }
00249 void popAfterApply()
00250 {
00251 record_stack.pop();
00252 repetition_counter.pop();
00253 move_history.pop();
00254 }
00255 public:
00259 template <Player P, class Function>
00260 void doUndoMoveOrPass(const HashKey& new_hash,
00261 Move move, Function& f)
00262 {
00263 pushBeforeApply(move);
00264 UpdateWrapper<Function> wrapper(new_hash, this, f);
00265 ApplyMoveWithPath<P>::doUndoMoveOrPass(current_state, current_path,
00266 move, wrapper);
00267 popAfterApply();
00268 }
00269 void makeMove(Move move)
00270 {
00271 HashKey new_hash = currentHash().newHashWithMove(move);
00272 pushBeforeApply(move);
00273 ApplyMoveOfTurn::doMove(current_state, move);
00274 updateRepetitionCounterAfterMove(new_hash);
00275 }
00276
00277 const Move lastMove(int i=1) const { return move_history.lastMove(i); }
00278 const MoveStack& history() const { return move_history; }
00279 const RecordStack2& recordHistory() const { return record_stack; }
00280 const PathEncoding& path() const { return current_path; }
00281 const NumEffectState& state() const { return current_state; }
00282 const checkmate_t& checkmateSearcher() const { return *checkmate_searcher; }
00283 const RepetitionCounter& repetitionCounter() const {
00284 return repetition_counter;
00285 }
00286 const HashKey& currentHash() const
00287 {
00288 return repetition_counter.history().top();
00289 }
00290
00294 template <Player P, class Function>
00295 void doUndoMoveLight(Move move, Function& f)
00296 {
00297 ApplyMoveWithPath<P>::doUndoMoveOrPass
00298 (static_cast<NumEffectState&>(current_state), current_path,
00299 move, f);
00300 }
00301
00302 template <Player P>
00303 bool isLosingState(int node_limit)
00304 {
00305 search_assert(P == path().turn());
00306 const bool lose =
00307 checkmate_searcher->isLosingState<P>
00308 (node_limit, current_state, currentHash(), path(), lastMove());
00309 return lose;
00310 }
00311 public:
00312 template <Player P>
00313 bool isWinningState(int node_limit, Move& checkmate_move,
00314 AttackOracleAges& age)
00315 {
00316 search_assert(P == path().turn());
00317 const bool win = checkmate_searcher->isWinningState<P>
00318 (node_limit, current_state, currentHash(), path(), checkmate_move, age,
00319 lastMove());
00320 return win;
00321 }
00323 template <Player P>
00324 bool isWinningStateShort(int depth, Move& checkmate_move)
00325 {
00326 checkmate::FixedDepthSearcher searcher(current_state);
00327 const ProofDisproof pdp=searcher.hasCheckmateMove<P>(depth, checkmate_move);
00328 return pdp.isCheckmateSuccess();
00329 }
00333 template <Player P>
00334 bool isThreatmateState(int node_limit, Move& threatmate_move,
00335 AttackOracleAges& age)
00336 {
00337 search_assert(P == path().turn());
00338 current_state.changeTurn();
00339 HashKey threatmate_hash = currentHash();
00340 threatmate_hash.changeTurn();
00341 const PathEncoding threatmate_path(current_state.getTurn());
00342 const Player Opponent = PlayerTraits<P>::opponent;
00343 const bool threatmate
00344 = checkmate_searcher->template isWinningState<Opponent>
00345 (node_limit, current_state,
00346 threatmate_hash, threatmate_path, threatmate_move, age);
00347 current_state.changeTurn();
00348 return threatmate;
00349 }
00350 template <Player P>
00351 bool isThreatmateStateShort(int depth, Move& threatmate_move)
00352 {
00353 search_assert(P == path().turn());
00354 current_state.changeTurn();
00355
00356 const Player Opponent = PlayerTraits<P>::opponent;
00357
00358 checkmate::FixedDepthSearcher searcher(current_state);
00359 const ProofDisproof pdp
00360 = searcher.hasCheckmateMove<Opponent>(depth, threatmate_move);
00361
00362 current_state.changeTurn();
00363 return pdp.isCheckmateSuccess();
00364 }
00365 bool abort() const;
00366 virtual bool abort(Move) const;
00367
00368 bool tryThreatmate() const
00369 {
00370 const Move last_move = lastMove();
00371 if (! last_move.isNormal())
00372 return false;
00373 const Position king = state().getKingPosition(state().getTurn());
00374 if (curDepth() == 1)
00375 return FirstMoveThreatmate::isMember(last_move, king);
00376 return Neighboring8Direct::hasEffect
00377 (state(), last_move.ptypeO(), last_move.to(), king);
00378
00379 }
00380
00381 void makePV(Move m)
00382 {
00383 const int depth = curDepth();
00384 makePV(pv[depth], m, pv[depth+1]);
00385 }
00386 void initPV()
00387 {
00388 const int depth = curDepth();
00389 pv[depth].clear();
00390 }
00391 static void makePV(PVVector& parent, Move m, PVVector& pv);
00393 int countCheckAfterThreatmate(Player turn, int depth=1) const
00394 {
00395 assert(((depth % 2) && state().getTurn() == turn)
00396 || ((depth % 2) == 0 && state().getTurn() != turn));
00397 int result = 0;
00398 for (int i=depth;; i+=2) {
00399 if (! hasLastRecord(i) || ! lastRecord(i))
00400 break;
00401 if (lastRecord(i)->qrecord.threatmate.status(turn).status()
00402 != ThreatmateState::CHECK_AFTER_THREATMATE)
00403 break;
00404 ++result;
00405 }
00406 return result;
00407 }
00408 int countCheckAfterThreatmateSacrifice(Player turn, int depth=1) const
00409 {
00410 assert(((depth % 2) && state().getTurn() == turn)
00411 || ((depth % 2) == 0 && state().getTurn() != turn));
00412 assert(depth > 0);
00413 int result = 0;
00414 for (int i=depth;; i+=2) {
00415 if (! hasLastRecord(i) || ! lastRecord(i))
00416 break;
00417 if (lastRecord(i)->qrecord.threatmate.status(turn).status()
00418 != ThreatmateState::CHECK_AFTER_THREATMATE)
00419 break;
00420 if (lastMove(i-1).capturePtype() != PTYPE_EMPTY)
00421 ++result;
00422 }
00423 return result;
00424 }
00425 };
00426
00427 #undef search_assert
00428 #undef search_assert2
00429 #define search_assert(x) assert((x) || SearchState2Core::abort())
00430 #define search_assert2(x, m) assert((x) || SearchState2Core::abort(m))
00431
00434 class SearchState2 : public SearchState2Core
00435 {
00436 public:
00438 static const int ReSearchLimitMargin = 80;
00439 protected:
00440 int root_limit;
00441 int cur_limit;
00442 public:
00443 SearchState2(const NumEffectState& s, checkmate_t& checker);
00444 virtual ~SearchState2();
00445
00446 void setState(const NumEffectState& s);
00447 void setKillerMove(Move best_move)
00448 {
00449 if (best_move.isPass())
00450 return;
00451 SearchState2Core::setKillerMove(best_move);
00452 }
00453
00454 int curLimit() const { return cur_limit; }
00455
00456 bool abort(Move) const;
00457
00458 protected:
00462 void setRoot(int limit)
00463 {
00464 root_limit = limit;
00465 cur_limit = limit;
00466 }
00467 void addLimit(int limit) { cur_limit += limit; search_assert(cur_limit >= 0); }
00468 void subLimit(int limit) { cur_limit -= limit; search_assert(cur_limit >= 0); }
00469
00473 int countSacrificeCheck2(int history_max) const;
00475 void checkPointSearchAllMoves();
00476 };
00477 }
00478 }
00479
00480 #undef search_assert
00481 #undef search_assert2
00482
00483 #endif
00484
00485
00486
00487