All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
searchState2.h
Go to the documentation of this file.
1 /* searchState2.h
2  */
3 #ifndef OSL_SEARCHSTATE2_H
4 #define OSL_SEARCHSTATE2_H
5 
11 #include "osl/checkmate/dualDfpn.h"
15 #include "osl/hash/hashKey.h"
16 #include "osl/repetitionCounter.h"
19 #include "osl/misc/align16New.h"
20 
21 #include <boost/shared_ptr.hpp>
22 #include <boost/utility.hpp>
23 
24 namespace osl
25 {
26  namespace search
27  {
33  {
34  static const int SEARCH_DEPTH_MAX = 64;
35  FixedCapacityVector<SimpleHashRecord*, SEARCH_DEPTH_MAX> data;
36  public:
37  RecordStack2();
38  void clear();
39  void push(SimpleHashRecord *r) { data.push_back(r); }
40  void pop() { assert(size() > 1); data.pop_back(); }
41 
42  SimpleHashRecord* lastRecord(unsigned int n=0) const
43  {
44  assert(size() > n);
45  return data[size()-1-n];
46  }
48  {
49  assert(! empty());
50  return data[0];
51  }
52  void setRootRecord(SimpleHashRecord *root) { data[0] = root; }
54  assert(size() > 0); // 1 for root
55  data[size()-1] = r;
56  }
57 
58  size_t size() const { return data.size(); }
59  bool empty() const { return data.empty(); }
60  bool hasLastRecord(unsigned int n=0) const
61  {
62  return size() > n;
63  }
64 
65  void dump() const;
66  };
67 
68  class Worker;
72  struct SearchState2Shared : boost::noncopyable
73  {
77 
80  };
81 #define search_assert(x) assert(((x) || (SearchState2Core::abort())))
82 #define search_assert2(x, m) assert(((x) || (SearchState2Core::abort(m))))
83  struct AlphaBeta2ParallelCommon;
87 #if OSL_WORDSIZE == 32
88  : public misc::Align16New
89 #endif
90  {
91  friend struct AlphaBeta2ParallelCommon;
92  public:
93  enum { MaxDepth = 64 };
95  protected:
96  NumEffectState current_state, root_state;
97  checkmate_t* checkmate_searcher;
98 #ifdef OSL_SMP
99  public:
100  void setCheckmateSearcher(checkmate_t *new_checkmate) {
101  checkmate_searcher = new_checkmate;
102  }
103  private:
104 #endif
106  MoveStack move_history;
108  protected:
111  boost::shared_ptr<SearchState2Shared> shared;
112  public:
113  typedef FixedCapacityVector<Move,MaxDepth> PVVector;
114  protected:
115  CArray<PVVector,MaxDepth> pv;
116  enum NodeType { PvNode = 0, AllNode = 1, CutNode = -1, };
117  CArray<NodeType,MaxDepth> node_type;
118  public:
120  volatile bool stop_tree;
121 #ifndef MINIMAL
122  static CArray<int, MaxDepth> depth_node_count_quiesce;
123 #endif
124  SearchState2Core(const NumEffectState& s, checkmate_t& checker);
125  virtual ~SearchState2Core();
126  int curDepth() const { return history().size() - root_depth; }
127 
134  virtual void setState(const NumEffectState& s);
135  void setHistory(const MoveStack& h);
136  bool hasLastRecord(unsigned int n=0) const
137  {
138  return record_stack.hasLastRecord(n);
139  }
140  SimpleHashRecord* lastRecord(unsigned int n=0)
141  {
142  return record_stack.lastRecord(n);
143  }
144  const SimpleHashRecord* lastRecord(unsigned int n=0) const
145  {
146  return record_stack.lastRecord(n);
147  }
149  {
150  return record_stack.rootRecord();
151  }
153  {
154  search_assert((int)record_stack.size() == curDepth()+1);
155  record_stack.setLastRecord(r);
156  }
158  {
159  search_assert(record_stack.size() == 1);
160  search_assert(curDepth() == 0);
161  record_stack.setRootRecord(root);
162  }
163 
164  // killer move
165  void setKillerMove(Move best_move)
166  {
167  if (best_move.isPass())
168  return;
169  shared->killer_moves.setMove(curDepth(), best_move);
170  const Move last_move = lastMove();
171  if (! last_move.isInvalid()) {
172  search_assert(best_move.player() != last_move.player());
173  shared->bigram_killers.setMove(last_move, best_move);
174  }
175  }
176  void getBigramKillerMoves(MoveVector& moves) const
177  {
178  shared->bigram_killers.getMove(state(), lastMove(), moves);
179 #ifdef TRI_PLY_BIGRAM_KILLERS
180  if (move_history.hasLastMove(3))
181  shared->bigram_killers.getMove(state(), lastMove(3), moves);
182 #endif
183  }
184  void getKillerMoves(MoveVector& moves) const
185  {
186  getBigramKillerMoves(moves);
187  shared->killer_moves.getMove(state(), curDepth(), moves);
188  }
190  return shared->bigram_killers;
191  }
192  void setBigramKillerMove(const BigramKillerMove& killers);
193  HistoryTable& historyTable() { return shared->history_table; }
194  const HistoryTable& historyTable() const { return shared->history_table; }
195  // doUndo
196  void pushPass()
197  {
198  const Move pass = Move::PASS(current_state.turn());
199  current_state.changeTurn();
200  current_path.pushMove(pass);
201  move_history.push(pass);
202  }
203  void popPass()
204  {
205  const Move pass = Move::PASS(alt(current_state.turn()));
206  current_state.changeTurn();
207  current_path.popMove(pass);
208  move_history.pop();
209  }
210  private:
215  {
216  move_history.push(move);
217  record_stack.push(0);
218  assert(curDepth() > 0);
219  node_type[curDepth()] = static_cast<NodeType>(-node_type[curDepth()-1]);
220  }
221  struct Updator
222  {
223  const HashKey& new_hash;
225  Updator(const HashKey& h, SearchState2Core *s)
226  : new_hash(h), state(s)
227  {
228  }
229  void update()
230  {
231  state->updateRepetitionCounterAfterMove(new_hash);
232  }
233  };
234  template <class Function>
235  struct UpdateWrapper : public Updator
236  {
237  Function& function;
238  UpdateWrapper(const HashKey& h, SearchState2Core *s, Function& f)
239  : Updator(h, s), function(f)
240  {
241  }
243  {
244  update();
245  function(to);
246  }
247  };
248  friend struct Updator;
252  void updateRepetitionCounterAfterMove(const HashKey& new_hash)
253  {
254  repetition_counter.push(new_hash, current_state);
255  }
260  {
261  record_stack.pop();
262  repetition_counter.pop();
263  move_history.pop();
264  }
265 #ifndef NDEBUG
266  void makeMoveHook(Move);
267 #endif
268  public:
272  template <Player P, class Function>
273  void doUndoMoveOrPass(const HashKey& new_hash,
274  Move move, Function& f)
275  {
276  pushBeforeApply(move);
277  UpdateWrapper<Function> wrapper(new_hash, this, f);
278  current_path.pushMove(move);
279  current_state.makeUnmakeMove(Player2Type<P>(), move, wrapper);
280  current_path.popMove(move);
281  popAfterApply();
282  }
283  void makeMove(Move move) // for debug
284  {
285  HashKey new_hash = currentHash().newHashWithMove(move);
286  pushBeforeApply(move);
287  current_state.makeMove(move);
288  updateRepetitionCounterAfterMove(new_hash);
289  }
290 
291  const Move lastMove(int i=1) const { return move_history.lastMove(i); }
292  const MoveStack& history() const { return move_history; }
293  const RecordStack2& recordHistory() const { return record_stack; }
294  const PathEncoding& path() const { return current_path; }
295  const NumEffectState& state() const { return current_state; }
296  const NumEffectState& rootState() const { return root_state; }
297  void restoreRootState();
298  const checkmate_t& checkmateSearcher() const { return *checkmate_searcher; }
300  return repetition_counter;
301  }
302  const HashKey& currentHash() const
303  {
304  return repetition_counter.history().top();
305  }
306 
310  template <Player P, class Function>
311  void doUndoMoveLight(Move move, Function& f)
312  {
313  current_path.pushMove(move);
314  current_state.makeUnmakeMove(Player2Type<P>(), move, f);
315  current_path.popMove(move);
316  }
317 
318  template <Player P>
319  bool isLosingState(int node_limit)
320  {
321  search_assert(P == path().turn());
322  const bool lose =
323  checkmate_searcher->isLosingState<P>
324  (node_limit, current_state, currentHash(), path(), lastMove());
325  return lose;
326  }
327  public:
328  template <Player P>
329  static bool isWinningState(checkmate_t& search, NumEffectState& state,
330  const HashKey& key, PathEncoding path,
331  int node_limit, Move& checkmate_move,
332  Move last_move, bool
333 #ifdef OSL_DFPN_SMP_SEARCH
334  parallel
335 #endif
336  =false
337  )
338  {
339  assert(P == path.turn());
340 #ifdef OSL_DFPN_SMP_SEARCH
341  if (parallel)
342  return search.isWinningStateParallel<P>
343  (node_limit, state, key, path, checkmate_move, last_move);
344 #endif
345  const bool win = search.isWinningState<P>
346  (node_limit, state, key, path, checkmate_move, last_move);
347  return win;
348  }
349  static bool isWinningState(checkmate_t& search, NumEffectState& state,
350  const HashKey& key, PathEncoding path,
351  int node_limit, Move& checkmate_move,
352  Move last_move, bool parallel=false)
353  {
354  if (state.turn() == BLACK)
355  return isWinningState<BLACK>
356  (search, state, key, path, node_limit, checkmate_move, last_move, parallel);
357  else
358  return isWinningState<WHITE>
359  (search, state, key, path, node_limit, checkmate_move, last_move, parallel);
360  }
361  template <Player P>
362  bool isWinningState(int node_limit, Move& checkmate_move, bool parallel=false)
363  {
364  search_assert(P == path().turn());
365  return isWinningState<P>(*checkmate_searcher, current_state, currentHash(),
366  path(), node_limit, checkmate_move, lastMove(), parallel);
367  }
369  template <Player P>
370  bool isWinningStateShort(int depth, Move& checkmate_move)
371  {
372  checkmate::FixedDepthSearcher searcher(current_state);
373  const ProofDisproof pdp=searcher.hasCheckmateMove<P>(depth, checkmate_move);
374  return pdp.isCheckmateSuccess();
375  }
379  template <Player P>
380  bool isThreatmateState(int node_limit, Move& threatmate_move, bool
381 #ifdef OSL_DFPN_SMP_SEARCH
382  parallel
383 #endif
384  =false)
385  {
386  search_assert(P == path().turn());
387  current_state.changeTurn();
388  HashKey threatmate_hash = currentHash();
389  threatmate_hash.changeTurn();
390  const PathEncoding threatmate_path(current_state.turn());
391  const Player Opponent = PlayerTraits<P>::opponent;
392  bool threatmate;
393 #ifdef OSL_DFPN_SMP_SEARCH
394  if (parallel)
395  threatmate = checkmate_searcher->template isWinningStateParallel<Opponent>
396  (node_limit, current_state,
397  threatmate_hash, threatmate_path, threatmate_move, Move::PASS(P));
398  else
399 #endif
400  threatmate
401  = checkmate_searcher->template isWinningState<Opponent>
402  (node_limit, current_state,
403  threatmate_hash, threatmate_path, threatmate_move, Move::PASS(P));
404  current_state.changeTurn();
405  return threatmate;
406  }
407  template <Player P>
408  bool isThreatmateStateShort(int depth, Move& threatmate_move)
409  {
410  search_assert(P == path().turn());
411  current_state.changeTurn();
412 
413  const Player Opponent = PlayerTraits<P>::opponent;
414 
415  checkmate::FixedDepthSearcher searcher(current_state);
416  const ProofDisproof pdp
417  = searcher.hasCheckmateMove<Opponent>(depth, threatmate_move);
418 
419  current_state.changeTurn();
420  return pdp.isCheckmateSuccess();
421  }
422  bool abort() const;
423  virtual bool abort(Move) const;
424 
425  bool tryThreatmate() const
426  {
427  const Move last_move = lastMove();
428  if (! last_move.isNormal())
429  return false;
430  const Square king = state().kingSquare(state().turn());
431  if (curDepth() == 1)
432  return FirstMoveThreatmate::isMember(last_move, king);
434  (state(), last_move.ptypeO(), last_move.to(), king);
435 
436  }
437 
438  void makePV(Move m)
439  {
440  const int depth = curDepth();
441  makePV(pv[depth], m, pv[depth+1]);
442  }
443  void initPV()
444  {
445  const int depth = curDepth();
446  pv[depth].clear();
447  }
448  void makePV(PVVector& parent, Move m, PVVector& pv) const;
450  int
451 #ifdef __GNUC__
452  __attribute__ ((pure))
453 #endif
455  {
456  assert(((depth % 2) && state().turn() == turn)
457  || ((depth % 2) == 0 && state().turn() != turn));
458  int result = 0;
459  for (int i=depth;; i+=2) {
460  if (! hasLastRecord(i) || ! lastRecord(i))
461  break;
462  if (lastRecord(i)->qrecord.threatmate.status(turn).status()
464  break;
465  ++result;
466  }
467  return result;
468  }
470  {
471  assert(((depth % 2) && state().turn() == turn)
472  || ((depth % 2) == 0 && state().turn() != turn));
473  assert(depth > 0);
474  int result = 0;
475  for (int i=depth;; i+=2) {
476  if (! hasLastRecord(i) || ! lastRecord(i))
477  break;
478  if (lastRecord(i)->qrecord.threatmate.status(turn).status()
480  break;
481  if (lastMove(i-1).isCapture())
482  ++result;
483  }
484  return result;
485  }
486  };
487 
488 #undef search_assert
489 #undef search_assert2
490 #define search_assert(x) assert((x) || SearchState2Core::abort())
491 #define search_assert2(x, m) assert((x) || SearchState2Core::abort(m))
492 
496  {
497  public:
499  static const int ReSearchLimitMargin = 80;
500  protected:
503  public:
504  SearchState2(const NumEffectState& s, checkmate_t& checker);
505  virtual ~SearchState2();
506 
507  void setState(const NumEffectState& s);
508  void setKillerMove(Move best_move)
509  {
510  if (best_move.isPass())
511  return;
513  }
514 
515  int curLimit() const { return cur_limit; }
516 
517  bool abort(Move) const;
518 
519  protected:
523  void setRoot(int limit)
524  {
525  root_limit = limit;
526  cur_limit = limit;
527  }
530 
534  int countSacrificeCheck2(int history_max) const;
537  };
538  } // namespace search
539 } // namespace osl
540 
541 #undef search_assert
542 #undef search_assert2
543 
544 #endif /* OSL_SEARCHSTATE2_H */
545 // ;;; Local Variables:
546 // ;;; mode:c++
547 // ;;; c-basic-offset:2
548 // ;;; End: