00001
00002
00003 #ifndef _ALPHA_BETA2_H
00004 #define _ALPHA_BETA2_H
00005
00006 #include "osl/search/realizationProbability.h"
00007 #include "osl/search/searchBase.h"
00008 #include "osl/search/searchState2.h"
00009 #include "osl/search/searchRecorder.h"
00010 #include "osl/search/passCounter.h"
00011 #include "osl/search/killerMoveTable.h"
00012 #include "osl/search/hasTimer.h"
00013 #include "osl/checkmate/dualCheckmateSearcher.h"
00014 #include "osl/eval/evalTraits.h"
00015 #include "osl/eval/progressEval.h"
00016 #include "osl/misc/realTime.h"
00017 #include "osl/container/moveStack.h"
00018 #include "osl/container/moveLogProbVector.h"
00019 #include "osl/stat/average.h"
00020 #include "osl/oslConfig.h"
00021 #include <boost/scoped_array.hpp>
00022 #include <boost/noncopyable.hpp>
00023 #include <iosfwd>
00024
00025 namespace osl
00026 {
00027 namespace search
00028 {
00029 class SimpleHashRecord;
00030 class SimpleHashTable;
00031 class MoveGenerator;
00032
00036 struct AlphaBeta2Common
00037 {
00038 static const int leaf_limit = 300;
00039
00040 enum { MaxDepth = SearchState2Core::MaxDepth };
00041 eval::ProgressEval eval;
00042 PassCounter pass_count;
00043 misc::RealTime timer;
00044 enum MoveType { INITIAL, HASH=INITIAL, TACTICAL, KILLER, PASS, ALL, FINISH };
00046 CArray<MoveType, MaxDepth> move_type;
00047 CArray<bool, MaxDepth> in_pv;
00048 typedef FixedCapacityVector<Move,4> killer_t;
00049 CArray<killer_t, MaxDepth> killers;
00050 uint64_t blocking;
00051 const MoveVector *root_ignore_moves;
00052
00053 explicit AlphaBeta2Common(const NumEffectState& s)
00054 : eval(s), timer(60), blocking(0), root_ignore_moves(0)
00055 {
00056 }
00057 };
00058
00059 class AlphaBeta2Parallel;
00063 class AlphaBeta2Tree
00064 : public SearchBase<eval::ProgressEval,SimpleHashTable,CountRecorder,RealizationProbability>,
00065 public SearchState2, public HasTimer, protected AlphaBeta2Common, boost::noncopyable
00066 {
00067 public:
00068 typedef eval::ProgressEval eval_t;
00069 enum { MaxDepth = SearchState2Core::MaxDepth };
00070 protected:
00072 size_t node_count;
00073 FixedCapacityVector<MoveGenerator*, MaxDepth> generators;
00074 stat::Average mpn, mpn_cut, alpha_update, last_alpha_update;
00075 stat::Average ext, ext_limit;
00076 boost::shared_ptr<AlphaBeta2Parallel> shared;
00077 protected:
00078 static CArray<int, MaxDepth> depth_node_count;
00079 AlphaBeta2Tree(const HashEffectState& s, checkmate_t& checker,
00080 SimpleHashTable *t, CountRecorder&);
00081
00082 AlphaBeta2Tree(const AlphaBeta2Tree& src, AlphaBeta2Parallel*);
00083 ~AlphaBeta2Tree();
00084
00085 private:
00086
00090 volatile int stop_by_alarm;
00091 bool has_stop_alarm;
00092 volatile int& stopByAlarm();
00093 const volatile int& stopByAlarm() const;
00094 public:
00095 const AlarmSwitch alarmSwitch() { return AlarmSwitch(&stopByAlarm()); }
00096 void setTimeOut(int seconds);
00097 void resetTimeOut();
00098 bool timerAvailable() const { return stopByAlarm() == Alarm::WATCHING; }
00099 private:
00100 void throwStop();
00101 public:
00102 struct BetaCut {};
00103 bool stopping() const
00104 {
00105 return stop || stopByAlarm() == Alarm::TIMEOUT;
00106 }
00107 void testStop() {
00108 if (stopping())
00109 throwStop();
00110 }
00111 public:
00112 class Window
00113 {
00114 CArray<int,2> values;
00115 public:
00116 explicit Window(int a=0) { values.fill(a); }
00117 Window(int a, int b)
00118 {
00119 values[0] = a;
00120 values[1] = b;
00121 }
00122 Window(Player P, int a=0, int b=0)
00123 {
00124 alpha(P) = a;
00125 beta(P) = b;
00126 }
00127 int& alpha(Player P) {
00128 return values[playerToIndex(P)];
00129 }
00130 int& beta(Player P) {
00131 return values[playerToIndex(alt(P))];
00132 }
00133
00134 int alpha(Player P) const {
00135 return values[playerToIndex(P)];
00136 }
00137 int beta(Player P) const {
00138 return values[playerToIndex(alt(P))];
00139 }
00140 bool isConsistent() const {
00141 return eval::notLessThan(BLACK, beta(BLACK), alpha(BLACK));
00142 }
00143 bool null() const { return values[0] == values[1]; }
00144 };
00145
00146 size_t nodeCount() const { return node_count; }
00147 void showPV(std::ostream&, int, Move) const;
00148
00149 template <Player P>
00150 const MoveLogProb nextMove();
00151 protected:
00152 template <Player P> class NextMove;
00153 friend class NextMove<BLACK>;
00154 friend class NextMove<WHITE>;
00155 template <Player P> class NextQMove;
00156 friend class NextQMove<BLACK>;
00157 friend class NextQMove<WHITE>;
00158
00167 template <Player P>
00168 int alphaBetaSearch(const MoveLogProb& move, Window window,
00169 bool in_pv);
00170 template <Player P>
00171 int alphaBetaSearchAfterMove(const MoveLogProb& move,
00172 Window window, bool in_pv);
00173 template <Player P> int quiesce(Window);
00174 template <Player P> int quiesceStable(Window);
00175 template <Player P> int quiesceExp(Window);
00176
00177 template <Player P>
00178 int searchAllMoves(SimpleHashRecord*, Window w);
00179 template <Player P>
00180 int searchAllMoves(Move m, int limit_consumption,
00181 SimpleHashRecord*, Window w);
00182
00184 template <Player P>
00185 bool tryCheckmate(SimpleHashRecord *record, bool in_pv, Move& checkmate_move);
00187 template <Player P>
00188 bool tryCheckmateAgain(SimpleHashRecord *record, Move& checkmate_move,
00189 int node_count,
00190 int best_value);
00191
00193 template <Player P>
00194 void testThreatmate(SimpleHashRecord *record, bool in_pv);
00195
00197 template <Player P>
00198 void examineMovesRoot(const MoveLogProbVector&, size_t, Window,
00199 MoveLogProb&, int&);
00200
00201 template <Player P> int quiesceRoot(Window, int depth_left, Move& best_move, DualThreatmateState);
00202 template <Player P> int quiesce(Window, int depth_left, DualThreatmateState);
00203 template <Player P>
00204 bool quiesceWithMove(Move, Window&, int, Move&, int&, const DualThreatmateState&);
00205
00206 void updateCheckmateCount();
00207 bool tryPass(SimpleHashRecord *record, Player P) const;
00208 MoveGenerator& makeGenerator();
00209 static MoveGenerator *alloc();
00210 static void dealloc(MoveGenerator *);
00211 #ifdef OSL_SMP
00212 public:
00213 friend class AlphaBeta2Parallel;
00214 struct NodeProperty;
00215 template <Player P> struct SearchJob;
00216 struct SearchJobData;
00217 struct Shared;
00218 friend class Shared;
00219 friend class SearchJob<BLACK>;
00220 friend class SearchJob<WHITE>;
00221 protected:
00222 template <Player P>
00223 void examineMovesRootPar(const MoveLogProbVector&, size_t, Window,
00224 MoveLogProb&, int&);
00225 void examineMovesRootPar(int tree_id);
00226 template <Player P>
00227 void testMoveRoot(int tree_id, const MoveLogProb&);
00228
00229 template <Player P>
00230 bool examineMovesOther(Window& w, MoveLogProb& best_move, int& best_value,
00231 int& tried_moves, int& alpha_update, int& last_alpha_update);
00232 void examineMovesOther(int tree_id);
00233 template <Player P>
00234 bool testMoveOther(int tree_id, const MoveLogProb&, size_t index, bool in_pv);
00235 #endif
00236 };
00237
00241 class AlphaBeta2
00242 : public AlphaBeta2Tree
00243 {
00244 public:
00245 AlphaBeta2(const HashEffectState& s, checkmate_t& checker,
00246 SimpleHashTable *t, CountRecorder&);
00247 ~AlphaBeta2();
00248
00255 template <Player P>
00256 int alphaBetaSearchRoot(Window window, MoveLogProb& best_move,
00257 int limit);
00258 static const Window fullWindow(Player P)
00259 {
00260 return Window(P, winThreshold(alt(P)), winThreshold(P));
00261 }
00262 int alphaBetaSearchRoot(Window window, MoveLogProb& best_move, int limit)
00263 {
00264 const Player P = state().getTurn();
00265 if (P == BLACK)
00266 return alphaBetaSearchRoot<BLACK>(window, best_move, limit);
00267 else
00268 return alphaBetaSearchRoot<WHITE>(window, best_move, limit);
00269 }
00270 int alphaBetaSearchRoot(MoveLogProb& best_move, int limit)
00271 {
00272 Window full_window = fullWindow(state().getTurn());
00273 return alphaBetaSearchRoot(full_window, best_move, limit);
00274 }
00275
00279 Move computeBestMoveIteratively(int limit,
00280 const int step=100,
00281 const int initialLimit=600,
00282 int nodeLimit=1600000,
00283 const misc::RealTime& timer
00284 =misc::RealTime(60));
00285 bool isReasonableMove(Move move, int pawn_sacrifice=1);
00286 void setRootIgnoreMoves(const MoveVector *rim) { root_ignore_moves = rim; }
00287
00288 static void showNodeDepth(std::ostream&);
00289 static void clearNodeDepth();
00290 public:
00291 void setRoot(int limit);
00292 void makeMove(Move);
00293 };
00294
00295 }
00296 using search::AlphaBeta2;
00297 }
00298
00299 #endif
00300
00301
00302
00303