All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
alphaBeta2.h
Go to the documentation of this file.
1 /* alphaBeta2.h
2  */
3 #ifndef OSL_ALPHA_BETA2_H
4 #define OSL_ALPHA_BETA2_H
5 
10 #include "osl/search/passCounter.h"
12 #include "osl/search/searchTimer.h"
13 #include "osl/eval/evalTraits.h"
15 #include "osl/eval/progressEval.h"
18 #include "osl/stat/average.h"
19 #include "osl/oslConfig.h"
20 #include <boost/scoped_array.hpp>
21 #include <boost/noncopyable.hpp>
22 #include <iosfwd>
23 
24 namespace osl
25 {
26  namespace search
27  {
28  class SimpleHashRecord;
29  class SimpleHashTable;
30  class MoveGenerator;
31  struct MoveWithComment;
32 
34  {
35  CArray<int,2> values;
36  public:
37  explicit AlphaBeta2Window(int a=0) { values.fill(a); }
38  AlphaBeta2Window(int a, int b)
39  {
40  values[0] = a;
41  values[1] = b;
42  }
43  AlphaBeta2Window(Player P, int a=0, int b=0)
44  {
45  alpha(P) = a;
46  beta(P) = b;
47  }
48  int& alpha(Player P) { return values[P]; }
49  int& beta(Player P) { return values[alt(P)]; }
50 
51  int alpha(Player P) const { return values[P]; }
52  int beta(Player P) const { return values[alt(P)]; }
53  bool isConsistent() const {
55  }
56  bool null() const { return values[0] == values[1]; }
57  bool operator==(const AlphaBeta2Window& r) const
58  {
59  return values == r.values;
60  }
61  };
62 
66  template <class EvalT>
68 #if OSL_WORDSIZE == 32
69  : public misc::Align16New
70 #endif
71  {
72  static int rootLimitBias()
73  {
74  return 0;
75  }
76  static int leafLimit()
77  {
78  static int value = 300 + rootLimitBias();
79  return value;
80  }
81 
82  enum { MaxDepth = SearchState2Core::MaxDepth };
83  EvalT eval;
85  enum MoveType { INITIAL, HASH=INITIAL, TACTICAL, KILLER, PASS, ALL, FINISH };
87  CArray<MoveType, MaxDepth> move_type;
88  CArray<bool, MaxDepth> in_pv;
89  typedef FixedCapacityVector<Move,4> killer_t;
90  CArray<killer_t, MaxDepth> killers;
91  const MoveVector *root_ignore_moves; // acquaintance
94  int multi_pv;
95 
96  explicit AlphaBeta2Common(const NumEffectState& s)
97  : eval(s), root_ignore_moves(0), prediction_for_speculative_search(false),
98  multi_pv(0)
99  {
100  in_pv[0] = true;
101  }
102  };
103  struct RootPV
104  {
106  int depth, eval;
107  RootPV(int root_limit, const SearchState2::PVVector &p, int v)
108  : pv(p), depth(root_limit), eval(v)
109  {
110  }
111  };
113  {
118  vector<RootPV> last_pv;
124  {
125  }
126  void showLastPv(int limit) const;
127  int sameBestMoves() const
128  {
129  int ret = 0;
130  for (int i=best_move_for_iteration.size()-2; i>=0; --i, ++ret)
132  break;
133  return ret;
134  }
135  };
136 
137  template <class EvalT> struct AlphaBeta2Parallel;
141  template <class EvalT>
143  : public SearchBase<EvalT,SimpleHashTable,CountRecorder,RealizationProbability>,
144  public SearchState2, public SearchTimer, protected AlphaBeta2Common<EvalT>, boost::noncopyable
145  {
146  public:
147  typedef EvalT eval_t;
150  protected:
152  size_t node_count;
153  FixedCapacityVector<MoveGenerator*, MaxDepth> generators;
156  boost::shared_ptr<AlphaBeta2Parallel<EvalT> > shared;
157  boost::shared_ptr<AlphaBeta2SharedRoot> shared_root;
158  protected:
159  static CArray<int, SearchState2Core::MaxDepth> depth_node_count;
160  AlphaBeta2Tree(const NumEffectState& s, checkmate_t& checker,
162  // share parallel data for split
164  ~AlphaBeta2Tree();
165  private:
166  void throwStop();
167  public:
168  struct BetaCut {};
169  bool stopping() const
170  {
171  return stop_tree || SearchTimer::stopping();
172  }
173  void testStop() {
175  if (stop_tree)
176  throw BetaCut();
177  }
178  public:
180  size_t nodeCount() const { return node_count; }
181  static int rootAlpha(Player P, int last_value, Progress16 progress);
182  static int stableThreshold(Player P, int last_value);
183 
184  template <Player P>
185  const MoveLogProb nextMove();
186  protected:
187  void updateRootPV(Player P, std::ostream&, int, Move);
188  void addMultiPV(Player P, int, Move);
189  bool isStable(Player P, int new_value) const;
190  void showFailLow(int result, Move m) const;
191  private:
192  void showPV(std::ostream&, int, Move, char stable) const;
193  public:
194  template <Player P> struct NextMove;
195  friend struct NextMove<BLACK>;
196  friend struct NextMove<WHITE>;
197  template <Player P> struct NextQMove;
198  friend struct NextQMove<BLACK>;
199  friend struct NextQMove<WHITE>;
200  protected:
209  template <Player P>
210  int alphaBetaSearch(const MoveLogProb& move, Window window,
211  bool in_pv);
212  template <Player P>
213  int alphaBetaSearchAfterMove(const MoveLogProb& move,
214  Window window, bool in_pv);
215  template <Player P> int quiesce(Window);
216  template <Player P> int quiesceStable(Window);
217  template <Player P> int quiesceExp(Window);
218 
219  template <Player P>
221  template <Player P>
222  int searchAllMoves(Move m, int limit_consumption,
224 
226  template <Player P>
227  bool tryCheckmate(SimpleHashRecord *record, bool in_pv, Move& checkmate_move);
229  template <Player P>
230  bool tryCheckmateAgain(SimpleHashRecord *record, Move& checkmate_move,
231  int node_count,
232  int best_value);
233 
235  template <Player P>
236  void testThreatmate(SimpleHashRecord *record, bool in_pv);
237 
239  template <Player P>
240  void examineMovesRoot(const MoveLogProbVector&, size_t, Window,
241  MoveLogProb&, int&);
242 
243  template <Player P> int quiesceRoot(Window, int depth_left, Move& best_move, DualThreatmateState);
244  template <Player P> int quiesce(Window, int depth_left, DualThreatmateState);
245  template <Player P>
246  bool quiesceWithMove(Move, Window&, int, Move&, int&, const DualThreatmateState&);
247 
248  void updateCheckmateCount();
249  bool tryPass(SimpleHashRecord *record, Player P) const;
251  static MoveGenerator *alloc();
252  static void dealloc(MoveGenerator *);
253 #ifdef OSL_SMP
254  public:
255  friend struct AlphaBeta2Parallel<EvalT>;
256  struct NodeProperty;
257  template <Player P> struct SearchJob;
258  struct SearchJobData;
259  struct Shared;
260  friend struct Shared;
261  friend struct SearchJob<BLACK>;
262  friend struct SearchJob<WHITE>;
263  protected:
264  template <Player P>
265  void examineMovesRootPar(const MoveLogProbVector&, size_t, Window,
266  MoveLogProb&, int&);
267  void examineMovesRootPar(int tree_id);
268  template <Player P>
269  void testMoveRoot(int tree_id, const MoveLogProb&);
270 
271  template <Player P>
272  bool examineMovesOther(Window& w, MoveLogProb& best_move, int& best_value,
273  int& tried_moves, int& alpha_update, int& last_alpha_update);
274  void examineMovesOther(int tree_id);
275  template <Player P>
276  bool testMoveOther(int tree_id, const MoveLogProb&, size_t index, bool in_pv);
277 #endif
278  };
279 
283  template <class EvalT>
285  : public AlphaBeta2Tree<EvalT>
286  {
287  public:
290  typedef typename base_t::Window Window;
291  public:
292  AlphaBeta2(const NumEffectState& s, checkmate_t& checker,
294  ~AlphaBeta2();
295 
302  template <Player P>
303  int alphaBetaSearchRoot(Window window, MoveLogProb& best_move,
304  int limit);
305  static const Window fullWindow(Player P)
306  {
308  }
309  int alphaBetaSearchRoot(Window window, MoveLogProb& best_move, int limit)
310  {
311  const Player P = this->state().turn();
312  if (P == BLACK)
313  return alphaBetaSearchRoot<BLACK>(window, best_move, limit);
314  else
315  return alphaBetaSearchRoot<WHITE>(window, best_move, limit);
316  }
317  int alphaBetaSearchRoot(MoveLogProb& best_move, int limit);
318 
323  const int step=100,
324  int initialLimit=600,
325  size_t nodeLimit=1600000,
326  const TimeAssigned& assign=TimeAssigned(MilliSeconds::Interval(60*1000)),
327  MoveWithComment *additional_info=0);
328  bool isReasonableMove(Move move, int pawn_sacrifice=1);
329  void setRootIgnoreMoves(const MoveVector *rim, bool prediction)
330  {
331  assert(!prediction || rim);
332  this->root_ignore_moves = rim;
333  this->prediction_for_speculative_search = prediction;
334  }
335 
336  static void showNodeDepth(std::ostream&);
337  static void clearNodeDepth();
338  void enableMultiPV(unsigned int width) { this->multi_pv = width; }
339  const AlphaBeta2SharedRoot sharedRootInfo() const { return *(this->shared_root); }
340  public:
341  void setRoot(int limit);
342  void makeMove(Move);
343  private:
346  };
347  PVCheckmateStatus findCheckmateInPV(int verify_node, CArray<bool,2>& king_in_threat);
348  }; // class AlphaBeta2
349 
350  } // namespace search
353 } // namespace osl
354 
355 #endif /* OSL_ALPHA_BETA2_H */
356 // ;;; Local Variables:
357 // ;;; mode:c++
358 // ;;; c-basic-offset:2
359 // ;;; End: