All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
quiescenceSearch2.tcc
Go to the documentation of this file.
1 /* quiescenceSearch2.tcc
2  */
3 #ifndef OSL_QUIESCENCESEARCH2_TCC
4 #define OSL_QUIESCENCESEARCH2_TCC
5 
15 #include "osl/hash/hashCollision.h"
24 #include "osl/eval/see.h"
25 #include "osl/stat/ratio.h"
26 #include "osl/hash/hashRandom.h"
27 #include "osl/oslConfig.h"
28 #include "osl/centering3x3.h"
29 
30 #ifdef STAT_WIDTH_VS_LIMIT
31 # include "osl/stat/average.h"
32 # include <iostream>
33 #endif
34 
35 #define quiecence_assert(x,m) assert((x) || state.abort(m))
36 
37 #ifdef RICH_QSEARCH
38 // 増減1割
39 # define QSEARCH_LAST_CHECK_PENALTY
40 // 5-20%
41 # define QSEARCH_PESSIMISTIC_ESCAPE_THREAT
42 // 8%
43 # define QSEARCH_THREATMATE
44 #endif
45 
46 #ifdef EXTRA_RICH_QSEARCH
47 // 2倍
48 # define QSEARCH_SET_MINIMUM_MOVES
49 #endif
50 
51 // recordがないと意味があまりない
52 // #define MAKE_PV_IN_QUIESCE2
53 
55 
56 namespace osl
57 {
58  namespace search
59  {
61  {
62  enum {
68  };
69  enum {
78  };
79  enum {
81  };
82  enum {
85  };
86  enum {
91 #ifdef QSEARCH_SET_MINIMUM_MOVES
92  MinimumMoves = 6,
93 #else
95 #endif
96  };
97  };
98 
100  {
101  int& result;
102  int alpha, beta;
104  QSearch2HelperBase(int& r, int a, int b, Move l)
105  : result(r), alpha(a), beta(b), last_move(l)
106  {
107  }
108  };
109 
110  template <class QSearch2,Player P>
112  {
113  typedef typename QSearch2::eval_t eval_t;
114  QSearch2 *searcher;
117  QSearch2NextMove(int& r, QSearch2 *s, int a, int b, eval_t& e, Move l,
118  int additional)
119  : QSearch2HelperBase(r, a, b, l),
120  searcher(s), ev(e), additional_depth(additional)
121  {
122  }
124  {
125  result = (*searcher).template searchInternal<PlayerTraits<P>::opponent>
126  (beta, alpha, ev, last_move, additional_depth, QSearch2::BeforeUpdate);
127  }
128  };
129  template <class QSearch2,Player P>
131  {
132  typedef typename QSearch2::eval_t eval_t;
133  QSearch2 *searcher;
135  QSearch2NextTakeBack(int& r, QSearch2 *s, int a, int b, eval_t& e, Move l)
136  : QSearch2HelperBase(r, a, b, l), searcher(s), ev(e)
137  {
138  }
140  {
141  ev.update(searcher->currentState(), last_move);
142  result = (*searcher).template takeBackValue<PlayerTraits<P>::opponent>
143  (beta, alpha, ev, last_move);
144  }
145  };
146  template <class QSearch2,Player P>
148  {
149  typedef typename QSearch2::eval_t eval_t;
150  QSearch2 *searcher;
152  QSearch2TakeBackOrChase(int& r, QSearch2 *s, int a, int b, eval_t& e, Move l)
153  : QSearch2HelperBase(r, a, b, l), searcher(s), ev(e)
154  {
155  }
157  {
158  ev.update(searcher->currentState(), last_move);
159  result = (*searcher).template takeBackOrChase<PlayerTraits<P>::opponent>
160  (beta, alpha, ev, last_move);
161  }
162  };
163  template <class Eval, Player P>
165  {
166  const NumEffectState *state;
167  Eval& eval;
172  QSearch2SafeEscape(const NumEffectState *s, Piece t, Eval& e, Move l)
173  : state(s), eval(e), target(t), has_safe_escape(false), is_invalid(false), last_move(l)
174  {
175  }
177  {
178  const Player Turn = PlayerTraits<P>::opponent;
179  assert(state->turn() == Turn);
180  if (state->inCheck(alt(Turn)))
181  {
182  is_invalid = true;
183  return;
184  }
185  eval.update(*state, last_move);
186  MoveVector dummy;
189  }
190  };
191  template <bool has_record>
193  {
194  static bool moreMoves(const QuiescenceRecord *)
195  {
196  return false;
197  // TODO: count number of moves outside of record
198  // return (record->moves_size() < QSearch2PrivateTraits::MinimumMoves);
199  }
200  };
201  } // namespace search
202 } // namespace osl
203 
204 
205 template <class EvalT>
206 template <osl::Player P>
208 searchProbCut(int alpha, int beta, eval_t& ev, Move last_move)
209 {
210  if (alpha != beta) {
211  max_depth = QSearchTraits::MaxDepth/2;
212  const int pawn_value2 = EvalT::captureValue(newPtypeO(alt(P),PAWN));
213  const int margin = pawn_value2/2;
214  const int alpha4 = EvalTraits<P>::max(alpha-margin,
215  base_t::winThreshold(alt(P)));
216  assert(EvalTraits<P>::notLessThan(alpha, alpha4));
217  const int beta4 = EvalTraits<P>::min(beta +margin,
218  base_t::winThreshold(P));
219  assert(EvalTraits<P>::notLessThan(beta4, beta));
220  const int val4 = searchInternal<P>(alpha4, beta4, ev, last_move);
221  if (EvalTraits<P>::betterThan(val4, beta4))
222  return val4 - (beta4-beta);
223  if (EvalTraits<P>::betterThan(alpha4, val4))
224  return val4 - (alpha4-alpha);
225  }
226  max_depth = QSearchTraits::MaxDepth;
227  return searchInternal<P>(alpha, beta, ev, last_move);
228 }
229 
230 template <class EvalT>
231 template <osl::Player P, osl::Ptype PTYPE>
232 inline
235  QuiescenceThreat& threat2,
236  QuiescenceThreat& threat1,
237  int beta1, int beta2, eval_t const& ev)
238 {
239  mask_t pieces = state.state().effectedMask(P).template selectBit<PTYPE>()
240  & state.state().piecesOnBoard(alt(P)).getMask(PtypeFuns<PTYPE>::indexNum);
241  if (PTYPE == PAWN || PTYPE == LANCE || PTYPE == KNIGHT)
242  pieces &= ~state.state().effectedMask(alt(P)).getMask(PtypeFuns<PTYPE>::indexNum);
243  while (pieces.any())
244  {
245  const Piece target = state.state().pieceOf(pieces.takeOneBit()+PtypeFuns<PTYPE>::indexNum*32);
247  assert(moves.empty());
248  QuiescenceGenerator<P>::capture1(currentState(), target.square(), moves);
249  const bool result
250  = examineTakeBack2<P,false,true>(moves, threat2, threat1,
251  beta1, beta2, ev);
252  moves.clear();
253  if (result)
254  return result;
255  }
256  return false;
257 }
258 
259 
260 template <class EvalT>
261 template <osl::Player P, osl::Ptype PTYPE, bool has_record>
262 inline
265  int& cur_val, MoveVector& moves, int& alpha, int beta,
266  eval_t const& ev, Piece last_move_piece, int additional_depth)
267 {
268  assert(alpha % 2);
269  assert(beta % 2);
270 
271  {
272  moves.clear();
273  QuiescenceGenerator<P>::template capture<PTYPE,true>(state.state(), moves, last_move_piece);
274 
275  SortCaptureMoves::sortByTakeBack(state.state(), moves);
276 
277  return examineMoves<P,has_record,has_record,CAPTURE>
278  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
279  additional_depth, last_move_piece.square());
280  }
281  return false;
282 }
283 
284 #ifdef STAT_WIDTH_VS_LIMIT
285 namespace osl
286 {
287  namespace
288  {
289  struct Reporter
290  {
291  stat::Average average;
292  int count;
293  Reporter() : count(0) {}
294  ~Reporter()
295  {
296  std::cerr << "QuiescenceSearch2 " << average.getAverage() << std::endl;
297  }
298  void newRoot() { average.add(count); count=0; }
299  void add() { ++count; }
300  } _reporter;
301  }
302 }
303 #endif
304 
305 template <class EvalT>
306 template <osl::Player P, bool has_record, bool has_dont_capture,
309 examineMoves(QuiescenceRecord *record, int& cur_val,
310  const Move *first, const Move *last,
311  int& alpha, int beta, eval_t const& ev,
312  int additional_depth, Square dont_capture)
313 {
314  assert(alpha % 2);
315  assert(beta % 2);
316 
317  assert(EvalTraits<P>::notLessThan(alpha, cur_val));
318 #if (! defined NDEBUG) && (! defined OSL_SMP)
319  const bool in_pv = (alpha != beta);
320 #endif
321  while (first != last)
322  {
323  const Move move = *first++;
324  if (move_type == CHECK)
325  {
326  if (depth() <= 0
327  && ! move.isCapture() && ! isMajor(move.ptype()))
328  continue;
329  }
330 
331  if (has_dont_capture)
332  {
333  const Square to = move.to();
334  if (to == dont_capture)
335  continue;
336  }
337  assert((move_type == KING_ESCAPE) || (move_type == UNKNOWN)
338  || (! ShouldPromoteCut::canIgnoreAndNotDrop<P>(move)));
339 
340  if(MoveStackRejections::probe<P>(state.state(),state.history(),state.curDepth(),move,alpha,state.repetitionCounter().checkCount(alt(P)))){
341  continue;
342  }
343 #ifdef QSEARCH_DEBUG
344  QuiescenceLog::pushMove(depth(), move, record);
345 #endif
346  const HashKey new_hash = state.currentHash().newHashWithMove(move);
347  int result;
348  // 千日手確認
349  const Sennichite next_sennichite
350  = state.repetitionCounter().isAlmostSennichite(new_hash);
351  if (next_sennichite.isDraw())
352  {
353  result = base_t::drawValue();
354  }
355  else if (next_sennichite.hasWinner())
356  {
357  result = base_t::winByFoul(next_sennichite.winner());
358  }
359  else
360  {
361  eval_t new_ev = ev;
362 #ifdef STAT_WIDTH_VS_LIMIT
363  if (depthFromRoot() == 0)
364  _reporter.add();
365 #endif
366  assert(next_sennichite.isNormal());
367  typedef QSearch2NextMove<QuiescenceSearch2,P> helper_t;
368  if (has_record && alpha != beta
369  && record->bestMove().isNormal()) {
370  // cut node
371  helper_t helper(result, this, alpha, alpha, new_ev, move,
372  additional_depth);
373  state.doUndoMoveOrPass<P,helper_t>(new_hash, move, helper);
374  if (EvalTraits<P>::betterThan(result, alpha)) {
375  new_ev = ev;
376  helper_t helper(result, this, alpha, beta, new_ev, move,
377  additional_depth);
378  state.doUndoMoveOrPass<P,helper_t>(new_hash, move, helper);
379  }
380  }
381  else {
382  // pv or all node
383  helper_t helper(result, this, alpha, beta, new_ev, move,
384  additional_depth);
385  state.doUndoMoveOrPass<P,helper_t>(new_hash, move, helper);
386  }
387 
388  // 打歩詰を厳密に
389  if (base_t::isWinValue(P, result) && (! move.isPass())
391  ::isMember(state.state(), move))
392  {
393  result = base_t::winByFoul(alt(P));
394  }
395  }
396  if (EvalTraits<P>::betterThan(result, cur_val))
397  {
398  cur_val = result;
399  if (EvalTraits<P>::betterThan(result, alpha))
400  {
401  alpha = result + EvalTraits<P>::delta;
402  if (has_record)
403  {
404  if (base_t::isWinValue(P, cur_val))
405  {
406  Square king = state.state().kingSquare(alt(P));
407  if (Ptype_Table.hasUnblockableEffect(move.ptypeO(), move.to(), king)) {
408  record->setLowerBound(QSearchTraits::CheckmateSpecialDepth, cur_val, move);
409  }
410  else {
411  // 現在は取り合いの結果詰でも本当に詰とは限らない c.f. 中合い
412  record->setLowerBound(QSearchTraits::MaxDepth, cur_val, move);
413  }
414  assert(EvalTraits<P>::notLessThan(result, beta));
415  return true;
416  }
417  else
418  {
419 #ifndef OSL_SMP
420  assert((record->lowerDepth() < depth())
421  || EvalTraits<P>::notLessThan(cur_val, record->lowerBound())
422  || in_pv
423  || state.abort(move));
424 #endif
425  record->setLowerBound(depth(), cur_val, move);
426  }
427  }
428  if (EvalTraits<P>::notLessThan(result, beta))
429  {
430  state.setKillerMove(move);
431  if (! move.isCapture())
432  {
433  const int d = depth();
434  state.historyTable().add(move, d*d);
435  }
436  return true;
437  }
438  }
439  }
440  }
441  return false;
442 }
443 
444 namespace osl
445 {
446  namespace search
447  {
449  const HashKey& key,
450  int minusDepthFromRoot,
451  SearchState2Core& state)
452  {
453  assert(minusDepthFromRoot <= 0 || minusDepthFromRoot == allocate_depth_in_threatmate);
454  SimpleHashRecord *record
455  = table.allocate(key, minusDepthFromRoot);
456  if (record) {
457  state.setCurrentRecord(record);
458  return &record->qrecord;
459  }
460  return 0;
461  }
462  }
463 }
464 
465 template <class EvalT>
466 template <osl::Player P, bool has_record>
467 inline
469 staticValue(eval_t const& ev, int alpha, int beta, QuiescenceRecord *record)
470 {
471  const bool in_pv = (alpha != beta);
472 #ifndef DONT_USE_CHECKMATE
473  if (! in_pv) {
474  bool in_threatmate = has_record && record->threatmate.maybeThreatmate(P);
475  if (! in_threatmate
476  && (state.hasLastRecord(1) && state.lastRecord(1)))
477  in_threatmate
478  = (state.lastRecord(1)->threatmate().status(P).status() == ThreatmateState::CHECK_AFTER_THREATMATE);
479  if (in_threatmate) {
480  const int result = ev.value() + base_t::threatmatePenalty(P);
481  return result;
482  }
483  }
484  if (in_pv) {
485  const Move last_move = state.lastMove();
486  const Square king = state.state().kingSquare(P);
487  const bool one_hop_prook
488  = (last_move.isNormal() && last_move.ptype() == PROOK
489  && (last_move.capturePtype() == GOLD
490  || last_move.capturePtype() == SILVER)
491  && ((king.y() == last_move.to().y()
492  && abs(king.x() - last_move.to().x()) < 3)
493  || (king.x() == last_move.to().x()
494  && abs(king.y() - last_move.to().y()) < 3)));
495  if (one_hop_prook && ! has_record) {
496  record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
497  }
498  if (has_record || record) {
499  // try simulation if record exists
500  Move checkmate_move=Move::INVALID();
501  int threatmate_node = 0;
502  if (record && record->threatmate.maybeThreatmate(P)) {
503  threatmate_node += 50;
504  } else if (one_hop_prook) {
505  threatmate_node += 20;
506  }
507 #ifdef QSEARCH_THREATMATE
508  else if ((depthFromRoot() < QSearch2PrivateTraits::ThreatMateDepthFromRoot)
509  && state.tryThreatmate())
510  threatmate_node += 20;
511 #endif
512  bool lose = state.isThreatmateState<P>
513  (record->threatmateNodesLeft(threatmate_node),
514  checkmate_move);
515  if (! lose && record->threatmateNodesLeft(2))
516  lose = state.isThreatmateStateShort<P>(2, checkmate_move);
517  if (lose)
518  {
519  const int result = ev.value() + base_t::threatmatePenalty(P);
520  assert(checkmate_move.isValid());
521  record->threatmate.setThreatmate(P, checkmate_move);
522  record->setStaticValue(QuiescenceRecord::EXACT, result,
523  QSearchTraits::CheckmateSpecialDepth);
524  assert(result % 2 == 0);
525  return result;
526  }
527  }
528  }
529 #endif
530  if (! in_pv && has_record) {
531  int static_value, static_value_depth;
533  if (record->hasStaticValue(static_value, static_value_depth, type)) {
534  // upper bound は depth に因らない
535  if (EvalTraits<P>::betterThan(alpha, static_value)) {
536  assert(static_value % 2 == 0);
537  return static_value;
538  }
539  if (type == QuiescenceRecord::EXACT
540  && (static_value_depth >= depth())) {
541  assert(static_value % 2 == 0);
542  return static_value;
543  }
544  }
545  }
546  Move threatmate_move;
547  if (ImmediateCheckmate::hasCheckmateMove<PlayerTraits<P>::opponent>
548  (state.state(), threatmate_move))
549  {
550  const int result = ev.value() + base_t::threatmatePenalty(P);
551  if (has_record)
552  {
553  record->threatmate.setThreatmate(P, threatmate_move);
554  record->setStaticValue(QuiescenceRecord::EXACT, result,
555  QSearchTraits::CheckmateSpecialDepth);
556  }
557  assert(result % 2 == 0);
558  return result;
559  }
560  if (alpha == beta && EvalTraits<P>::betterThan(ev.value(), beta)) {
561  // futility pruning of threat
562  int expect = ev.value() + ev.captureValue(newPtypeO(P, GOLD));
563  Piece threat = state.state().findThreatenedPiece(P);
564  if (threat.isPiece())
565  expect += ev.captureValue(threat.ptypeO());
566  if (EvalTraits<P>::betterThan(expect, beta))
567  return expect;
568  }
569  const int eval_alpha = alpha;
570  QuiescenceThreat threat1, threat2;
571  const int result = staticValueWithThreat<P>(ev, eval_alpha, threat1, threat2);
572  if (has_record)
573  {
574  record->setStaticValue(EvalTraits<P>::betterThan(eval_alpha, result)
575  ? QuiescenceRecord::UPPER_BOUND
576  : QuiescenceRecord::EXACT,
577  result, depth(),
578  threat1, threat2);
579  }
580  assert(result % 2 == 0);
581  return result;
582 }
583 
584 template <class EvalT>
585 template <osl::Player P>
587 searchInternal(int alpha, int beta, eval_t& ev, Move last_move,
588  int additional_depth, EvalUpdateState need_eval_update)
589 {
590 #ifdef STAT_WIDTH_VS_LIMIT
591  if (depthFromRoot() == 0)
592  _reporter.newRoot();
593 #endif
594 #ifdef QSEARCH_DEBUG
595  if (depthFromRoot() == 0)
596  QuiescenceLog::enter(state.state());
597 #endif
598 #ifdef MAKE_PV_IN_QUIESCE2
599  state.initPV();
600 #endif
601  ++node_count;
602  assert(alpha % 2);
603  assert(beta % 2);
604  quiecence_assert(EvalTraits<P>::notLessThan(beta, alpha), last_move);
605  assert(EvalTraits<P>::notLessThan(alpha, base_t::winThreshold(alt(P))));
606  assert(EvalTraits<P>::notLessThan(base_t::winThreshold(P), beta));
607  assert(last_move.player() == alt(P));
608 
609  // 自殺手を手生成でフィルタすると遅くなるので動かしてからチェック
610  if (state.state().inCheck(alt(P)))
611  return base_t::winByFoul(P);
612 
613  assert(state.hasLastRecord());
614  QuiescenceRecord *record
615  = qallocate(table, state.currentHash(), depth()-QSearchTraits::MaxDepth,
616  state);
617  const QuiescenceRecord *parent
618  = (state.hasLastRecord(1) && state.lastRecord(1))
619  ? &(state.lastRecord(1)->qrecord) : 0;
620  const bool near_checkmate = parent
621  && (parent->threatmate.maybeThreatmate(alt(P))
622  || parent->threatmate.mayHaveCheckmate(P)
623  || (parent->threatmate.status(P).status()
624  == ThreatmateState::CHECK_AFTER_THREATMATE));
625  if (! record && near_checkmate)
626  {
627  const int depth = (alpha != beta) ? allocate_depth_in_threatmate : 0;
628  record
629  = qallocate(table, state.currentHash(), depth, state);
630  }
631  int result;
632  if (! record) {
633  result = searchMain<P,false>(0, alpha, beta, ev, last_move,
634  additional_depth, need_eval_update);
635  if (near_checkmate) {
636  if ((EvalTraits<P>::betterThan(alpha, result)
637  && parent->threatmate.maybeThreatmate(alt(P)))
638  || (EvalTraits<P>::betterThan(result, alpha)
639  && parent->threatmate.status(P).status()
640  == ThreatmateState::CHECK_AFTER_THREATMATE)) {
641  record
642  = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
643  }
644  }
645  }
646  if (record)
647  {
648  const bool is_king_in_check = state.state().inCheck();
649  record->updateThreatmate(P, (parent ? &(parent->threatmate) : 0),
650  is_king_in_check);
651  result = searchMain<P,true>(record, alpha, beta, ev, last_move,
652  additional_depth, need_eval_update);
653 #ifdef MAKE_PV_IN_QUIESCE2
654  if ((alpha != beta) && EvalTraits<P>::betterThan(result, alpha))
655  state.makePV(record->bestMove());
656 #endif
657  }
658 #ifdef QSEARCH_DEBUG
659  QuiescenceLog::node(depth(), alpha, beta, result);
660 #endif
661  assert(result % 2 == 0);
662  return result;
663 }
664 
665 template <class EvalT>
667 currentValueWithLastThreat(eval_t const& ev, Piece last_move_piece)
668 {
669  int static_value = ev.value();
670  if (! (depthFromRoot() < QSearch2PrivateTraits::EscapeFromLastMoveDepthFromRoot))
671  return static_value;
672 
673  assert(last_move_piece.isPiece());
674  const Player P = last_move_piece.owner();
675  PieceVector targets;
676  const Square from = last_move_piece.square();
677  EffectUtil::findThreat<EvalT>(state.state(), from, last_move_piece.ptypeO(),
678  targets);
679  if (targets.empty())
680  return static_value;
681  if (targets[0].ptype() == KING)
682  {
683  if (targets.size() < 2)
684  return static_value;
685  // 王手の両取り
686  int threat = eval_t::captureValue(targets[1].ptypeO());
687  if (state.state().hasEffectAt(alt(P), targets[1].square()))
688  threat += eval_t::captureValue(last_move_piece.ptypeO());
689  assert(eval::betterThan(P, threat, 0));
690  return static_value + threat;
691  }
692  int first_threat = eval_t::captureValue(targets[0].ptypeO());
693  if (state.state().hasEffectAt(alt(P), targets[0].square()))
694  first_threat += eval_t::captureValue(last_move_piece.ptypeO());
695  assert(eval::betterThan(P, first_threat, 0));
696  first_threat /= SecondThreat;
697  if (targets.size() < 2)
698  return static_value + (first_threat & (~0x1));
699 
700  int second_threat = eval_t::captureValue(targets[1].ptypeO());
701  if (state.state().hasEffectAt(alt(P), targets[1].square()))
702  second_threat += eval_t::captureValue(last_move_piece.ptypeO());
703  assert(eval::betterThan(P, second_threat, 0));
704  return static_value + ((first_threat + second_threat) & (~0x1));
705 }
706 
707 template <class EvalT>
708 template <osl::Player P>
710 passValue(int alpha, int beta, eval_t const& ev)
711 {
712  // TODO:
713  // - pass pass を許すならloop確認
714  BOOST_STATIC_ASSERT(QSearch2PrivateTraits::EscapeDepthFromRoot <= 2);
715  const Move pass = Move::PASS(P);
716  int result;
717  typedef QSearch2NextMove<QuiescenceSearch2,P> helper_t;
718  helper_t helper(result, this, alpha, beta, ev, pass, 0);
719  const HashKey new_hash = state.currentHash().newHashWithMove(pass);
720 
721  max_depth -= QSearch2PrivateTraits::PassExtraDepth;
722  state.doUndoMoveOrPass<P,helper_t>(new_hash, pass, helper);
723  max_depth += QSearch2PrivateTraits::PassExtraDepth;
724 
725  return result;
726 }
727 
728 template <class EvalT>
729 template <osl::Player P, bool has_record>
732  int alpha, int beta, eval_t& ev, Move last_move,
733  int additional_depth, EvalUpdateState& need_eval_update)
734 {
735  const bool in_pv = (alpha != beta);
736 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
737  static stat::Ratio ratio("QSearch2: cut");
738 #endif
739  assert((! has_record) || record);
740  assert(alpha % 2);
741  assert(beta % 2);
742  assert((last_move == state.lastMove())
743  || ! last_move.isNormal() || ! state.lastMove().isNormal());
744 #if (!defined OSL_USE_RACE_DETECTOR) && (!defined MINIMAL)
745  state.depth_node_count_quiesce[state.curDepth()]++;
746 #endif
747 #ifndef DONT_USE_CHECKMATE
748  const int node_count_before = node_count;
749 #endif
750  const Square last_to = last_move.to();
751  int cur_val = base_t::winByCheckmate(alt(P));
752  if (has_record)
753  {
754  if ((! in_pv && record->lowerDepth() >= depth())
755  || record->lowerDepth() >= QSearchTraits::HistorySpecialDepth)
756  {
757  if (EvalTraits<P>::notLessThan(record->lowerBound(), cur_val))
758  {
759  cur_val = record->lowerBound();
760  if (EvalTraits<P>::betterThan(record->lowerBound(), alpha))
761  {
762  alpha = record->lowerBound() + EvalTraits<P>::delta;
763  if (EvalTraits<P>::betterThan(record->lowerBound(), beta))
764  {
765 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
766  ratio.add(true);
767 #endif
768  return record->lowerBound();
769  }
770  }
771  }
772  }
773 #ifndef DONT_USE_CHECKMATE
774  assert(record);
775  // try simulation if record exists
776  if (in_pv) {
777  Move checkmate_move=Move::INVALID();
778  if (need_eval_update == BeforeUpdate) {
779  ev.update(state.state(), last_move);
780  need_eval_update = AfterUpdate;
781  }
782  bool win = state.isWinningState<P>
783  (0, checkmate_move);
784  if (! win && record->threatmate.mayHaveCheckmate(alt(P))) {
785  win = state.isWinningStateShort<P>(2, checkmate_move);
786  }
787  if (win) {
788  const int result = base_t::winByCheckmate(P);
789  assert(checkmate_move.isValid());
790  assert(state.state().isValidMove(checkmate_move));
791  record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
792  result, checkmate_move);
793  return result;
794  }
795  }
796 #endif
797  if ((! in_pv && record->upperDepth() >= depth())
798  || record->upperDepth() >= QSearchTraits::HistorySpecialDepth)
799  {
800  if (EvalTraits<P>::betterThan(beta, record->upperBound()))
801  {
802  beta = record->upperBound() - EvalTraits<P>::delta;
803  if (EvalTraits<P>::betterThan(alpha, record->upperBound()))
804  {
805 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
806  ratio.add(true);
807 #endif
808  return record->upperBound();
809  }
810  }
811  }
812 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
813  ratio.add(false);
814 #endif
815  }
816  if (need_eval_update == BeforeUpdate) {
817  ev.update(state.state(), last_move);
818  need_eval_update = AfterUpdate;
819  }
820  const bool is_king_in_check = state.state().inCheck();
822  if (is_king_in_check)
823  {
824  if (last_move.isNormal() && last_move.isCapture()
825  && unpromote(last_move.capturePtype()) == ROOK
826  && unpromote(last_move.ptype()) != ROOK)
827  ++additional_depth;
828  else
829  // 王手でのtakebackの応酬の延長
830  if (state.lastMove(2).isNormal() // hasLastMove(3)を兼ねる
831  && state.lastMove(3).isNormal()
832  && state.lastMove(4).isNormal()
833  && state.lastMove(2).to() == last_move.to()
834  && state.lastMove(3).to() == last_move.to()
835  && state.lastMove(4).to() == last_move.to())
836  ++additional_depth;
837  // 王手がかかっている時はきちんと逃げる
838  {
840  // GenerateEscape は玉で取る手が逃げる手より後回しになることがあるので
841  move_order::CaptureSort::sort(moves.begin(), moves.end());
842  examineMoves<P,has_record,false,KING_ESCAPE>
843  (record, cur_val, &*moves.begin(), &*moves.end(),alpha, beta, ev,
844  additional_depth);
845  }
846  if (has_record)
847  {
848  if (EvalTraits<P>::betterThan(beta, cur_val))
849  record->setUpperBound(depth(), cur_val);
850  }
851  return cur_val;
852  }
853  assert(! is_king_in_check);
854  King8Info king_info(state.state().Iking8Info(alt(P)));
855  PieceMask pins = state.state().pin(alt(P));
856  Move checkmate_move=Move::INVALID();
857  Square kingSquare=state.state().template kingSquare<PlayerTraits<P>::opponent>();
858  if ((depth() <= 4)
859  ? ImmediateCheckmate::hasCheckmateMove<P>(state.state(), king_info,kingSquare,checkmate_move)
860  : state.isWinningStateShort<P>(2, checkmate_move)) {
861  const int result = base_t::winByCheckmate(P);
862  assert(checkmate_move.isValid());
863  if(has_record)
864  {
865  assert(state.state().isValidMove(checkmate_move));
866  record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
867  result, checkmate_move);
868  }
869  return result;
870  }
871  // assert(ev.value() == eval_t(state.state()).value()); // !!! SLOW !!!
872 
873  if (depth() <= 0 && has_record) {
874  if (record->threatmate.maybeThreatmate(P))
875  return ev.value() + base_t::threatmatePenalty(P);
876  if (record->threatmate.mayHaveCheckmate(alt(P)))
877  return ev.value() + base_t::threatmatePenalty(alt(P));
878  }
879 
880  const Ptype last_capture = last_move.isNormal()
881  ? last_move.capturePtype() : PTYPE_EMPTY;
882  const Ptype last_ptype = last_move.isNormal()
883  ? last_move.ptype() : PTYPE_EMPTY;
884  const bool king_escape = (last_ptype == KING) && last_capture == PTYPE_EMPTY;
885 
886  if ((depth() + std::min(additional_depth,2) <= -2)
887  || (depth() <= 0 && additional_depth == 0)
888  || (! king_escape
889  && ((depth() + additional_depth <= 0)
890  || (depth() <= 0 && last_capture != PTYPE_EMPTY
891  && last_ptype != KING))))
892  {
893  if (ev.progress16().value() == 15
894  && state.tryThreatmate()
895  && ImmediateCheckmate::hasCheckmateMove<PlayerTraits<P>::opponent>(state.state()))
896  return ev.value() + base_t::threatmatePenalty(P);
897  const int base = takeBackValue<P>(alpha, beta, ev, last_move);
898 #ifdef QSEARCH_LAST_CHECK_PENALTY
899  if ((last_move.ptype() == KING)
900  && (last_capture == PTYPE_EMPTY))
901  {
902  // 最後の手が王手回避 => ペナルティ
903  // 銀くらい取れそう
904  return base+eval_t::captureValue(newPtypeO(alt(P), KNIGHT));
905  }
906 #endif
907  return base;
908  }
909  // 王手でなければパスを認めるので最初に静的評価値を求める
910  const int static_value
911  = ((depth() <= 0)
912  ? takeBackValue<P>(alpha, beta, ev, last_move)
913 #ifdef QSEARCH_REAL_PASS
914  : ((depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot)
915  && (! last_move.isPass()))
916  ? passValue<P>(alpha, beta, ev)
917 #endif
918  : staticValue<P,has_record>(ev, alpha, beta, record))
919 #ifndef MINIMAL
920  + (OslConfig::evalRandom() ? HashRandom::value(state.currentHash()): 0)
921 #endif
922  ;
923  assert(static_value % 2 == 0);
924  assert(! isWinValue(alt(P), static_value));
925 #ifdef QSEARCH_DEBUG
926  QuiescenceLog::staticValue(depth(), static_value);
927 #endif
928  if (EvalTraits<P>::notLessThan(static_value, cur_val))
929  {
930  cur_val = static_value;
931  if (EvalTraits<P>::betterThan(cur_val, alpha))
932  {
933  alpha = cur_val + EvalTraits<P>::delta;
934  if (has_record)
935  {
936 #ifndef OSL_SMP
937  assert((record->lowerDepth() < depth())
938  || EvalTraits<P>::notLessThan(cur_val, record->lowerBound())
939  || in_pv);
940 #endif
941  record->setLowerBound(depth(), cur_val, record->bestMove());
942  }
943  if (EvalTraits<P>::betterThan(cur_val, beta))
944  return cur_val;
945  }
946  }
947 
948  // 反映済のはず
949  assert(alpha == EvalTraits<P>::max(alpha, cur_val + EvalTraits<P>::delta));
950  assert(EvalTraits<P>::notLessThan(beta, alpha));
951 
952  Piece last_capture_piece = Piece::EMPTY();
953  if (! has_record)
954  {
955  state.getBigramKillerMoves(moves);
956  if (examineMoves<P,has_record,false,UNKNOWN>
957  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
958  additional_depth))
959  return cur_val;
960  moves.clear();
961  }
962  else
963  {
964  // has_record
965  // best move
966  const Move bestmove_in_record=record->bestMove();
967  if (bestmove_in_record.isNormal())
968  {
969  assert(state.state().template isAlmostValidMove<true>(bestmove_in_record));
970  assert(moves.empty());
971  moves.push_back(bestmove_in_record);
972  if (examineMoves<P,has_record,false,UNKNOWN>
973  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
974  additional_depth))
975  return cur_val;
976  moves.clear();
977  last_capture_piece = state.state().pieceOnBoard(bestmove_in_record.to());
978  }
979  // killer moves
980  MoveVector killer_moves;
981  state.getBigramKillerMoves(killer_moves);
982  assert(moves.empty());
983  MoveVector record_moves;
984  record->loadMoves(record_moves);
985  BOOST_FOREACH(Move move, killer_moves)
986  {
987  if (std::find(record_moves.begin(), record_moves.end(), move)
988  == record_moves.end())
989  moves.push_back(move);
990  }
991  record->addKillerMoves(moves);
992 
993  if (examineMoves<P,has_record,false,UNKNOWN>
994  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
995  additional_depth))
996  return cur_val;
997  // already generated moves
998  if (examineMoves<P,has_record,false,UNKNOWN>
999  (record, cur_val, &*record_moves.begin(), &*record_moves.end(), alpha, beta, ev, additional_depth))
1000  return cur_val;
1001  moves.clear();
1002  }
1003 
1004  // TakeBack 優先
1005  assert(moves.empty());
1006  if (((! has_record) || record->movesEmpty())
1007  && (! last_to.isPieceStand()))
1008  {
1009  last_capture_piece = state.state().pieceOnBoard(last_to);
1010  QuiescenceGenerator<P>::capture(state.state(),
1011  last_capture_piece.square(), moves);
1012  if (examineMoves<P,has_record,false,CAPTURE>
1013  (record, cur_val, &*moves.begin(), &*moves.end(),alpha, beta, ev,
1014  additional_depth))
1015  {
1016  if (has_record)
1017  {
1018  // 後で重複してしまうが記録してくれないと困るので
1019  record->addKillerMoves(moves);
1020  }
1021  return cur_val;
1022  }
1023  }
1024 
1025  // 詰めろ防止
1026  const bool has_threatmate
1027  = has_record
1028  && record->threatmate.isThreatmate(P)
1029 #ifdef OSL_SMP
1030  && record->threatmate.threatmateMove(P).isNormal()
1031 #endif
1032  ;
1033  if (has_threatmate)
1034  {
1035  moves.clear();
1037  (state.state(), record->threatmate.threatmateMove(P), pins, moves);
1038  if (examineMoves<P,has_record,false,KING_ESCAPE>
1039  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
1040  additional_depth))
1041  return cur_val;
1042  }
1043 
1044  // 取る手
1045  if (examineCapture<P,ROOK,has_record>
1046  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1047  return cur_val;
1048  if (examineCapture<P,BISHOP,has_record>
1049  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1050  return cur_val;
1051  if (examineCapture<P,GOLD,has_record>
1052  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1053  return cur_val;
1054  if (examineCapture<P,SILVER,has_record>
1055  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1056  return cur_val;
1057  if ((depth() >= QSearch2PrivateTraits::KnightCaptureDepth)
1058  || max_depth <= 2
1060  {
1061  if (examineCapture<P,KNIGHT,has_record>
1062  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1063  return cur_val;
1064  if (examineCapture<P,LANCE,has_record>
1065  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1066  return cur_val;
1067  }
1068  // suggested move by evaluation function
1069  {
1070  const Move suggested = ev.suggestMove(state.state());
1071  if (suggested.isNormal()) {
1072  assert(state.state().isAlmostValidMove(suggested));
1073  moves.clear();
1074  moves.push_back(suggested);
1075  if (examineMoves<P,has_record,false,UNKNOWN>
1076  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
1077  additional_depth)) {
1078  return cur_val;
1079  }
1080  }
1081  }
1082  // 王手
1083  const Move last2_move = state.lastMove(2);
1084  if ((depth() > 2
1085  || (depth() > 0 && !(has_record && record->threatmate.maybeThreatmate(P)))
1086  || (last2_move.isNormal() && last2_move.capturePtype() == ROOK))
1087  && ! (! in_pv && has_record && record->threatmate.maybeThreatmate(P)))
1088  {
1089  moves.clear();
1090 
1091  if (has_record)
1092  QuiescenceGenerator<P>::check(state.state(), pins,
1093  (king_info.liberty() == 0),
1094  record->sendOffSquare<P>(state.state()),
1095  moves);
1096  else
1097  QuiescenceGenerator<P>::check(state.state(), pins, moves,
1098  (king_info.liberty() == 0));
1099  if (examineMoves<P,has_record,false,CHECK>
1100  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
1101  additional_depth))
1102  return cur_val;
1103  }
1104 
1105  const Square my_king = state.state().template kingSquare<P>();
1106 
1107  if (depth() <= 0)
1108  goto finish;
1109  // futility pruning
1110  if (! in_pv
1111  && EvalTraits<P>::betterThan(alpha, ev.value() + (200+350+50*depth())*ev.captureValue(newPtypeO(alt(P),PAWN))/200))
1112  goto king_walk;
1113  if ((depth() >= QSearch2PrivateTraits::AttackPinnedDepth)
1115  {
1116  {
1117  moves.clear();
1118  QuiescenceGenerator<P>::attackToPinned(state.state(), pins, moves);
1119  if (examineMoves<P,has_record,false,ATTACK>
1120  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
1121  additional_depth))
1122  return cur_val;
1123  }
1124  }
1125 
1126  if ((depthFromRoot() < QSearch2PrivateTraits::DropDepthFromRoot)
1127  || (isMajorBasic(last2_move.capturePtype())
1128  && ((depthFromRoot() < QSearch2PrivateTraits::DropDepthFromRoot+2)
1129  || (has_record && record->movesSizeLessThan(4))
1130  ))
1132  {
1133  {
1134  moves.clear();
1135  QuiescenceGenerator<P>::dropMajorPiece3(state.state(), moves, state.historyTable());
1136  if (last_move.isNormal() && isPiece(last_move.capturePtype())
1137  && unpromote(last_move.capturePtype())== BISHOP
1138  && last2_move.isNormal() && last2_move.capturePtype() == BISHOP
1139  && unpromote(last2_move.ptype()) == BISHOP) // 合わせた角を取った
1140  {
1141  const Square drop_again = last2_move.from();
1142  if (! state.state().template hasEffectAt<PlayerTraits<P>::opponent>(drop_again)
1143  // これ以降は多分常にtrue
1144  && state.state().pieceOnBoard(drop_again) == Piece::EMPTY()
1145  && state.state().template hasPieceOnStand<BISHOP>(P))
1146  moves.push_back(Move(drop_again, BISHOP, P));
1147  }
1148 
1149  if (examineMoves<P,has_record,true,OTHER>
1150  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev,
1151  additional_depth))
1152  return cur_val;
1153  }
1154  }
1155  if ((depth() >= QSearch2PrivateTraits::PawnCaptureDepth)
1156  || max_depth <= 2
1158  {
1159  if (examineCapture<P,PAWN,has_record>
1160  (record, cur_val, moves, alpha, beta, ev, last_capture_piece, additional_depth))
1161  return cur_val;
1162  }
1163  if ((depth() >= QSearch2PrivateTraits::FullPromoteDepth)
1164  || max_depth <= 2)
1165  {
1166  moves.clear();
1167  QuiescenceGenerator<P>::promote(state.state(), pins, moves);
1168  if (examineMoves<P,has_record,false,PROMOTE>
1169  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1170  return cur_val;
1171  }
1172  else
1173  {
1174  moves.clear();
1175  QuiescenceGenerator<P>::template promoteN<ROOK,2>(state.state(), moves, state.historyTable());
1176  QuiescenceGenerator<P>::template promoteN<BISHOP,2>(state.state(), moves, state.historyTable());
1177  if (examineMoves<P,has_record,false,PROMOTE>
1178  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1179  return cur_val;
1180  moves.clear();
1181  QuiescenceGenerator<P>::template promoteN<PAWN,2>(state.state(), moves, state.historyTable());
1182  QuiescenceGenerator<P>::template promoteN<LANCE,1>(state.state(), moves, state.historyTable());
1183  QuiescenceGenerator<P>::template promoteN<KNIGHT,1>(state.state(), moves, state.historyTable());
1184  if (examineMoves<P,has_record,false,PROMOTE>
1185  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1186  return cur_val;
1187  }
1188  if (depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot)
1189  {
1190  {
1191  moves.clear();
1192  QuiescenceGenerator<P>::escapeAll(state.state(), moves);
1193  if (examineMoves<P,has_record,false,ESCAPE>
1194  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1195  return cur_val;
1196  }
1197  }
1198  else if ((depthFromRoot() < QSearch2PrivateTraits::EscapeFromLastMoveDepthFromRoot)
1199  || (last_move.isDrop() && isMajorBasic(last_move.ptype()))
1200  || (last_move.isNormal() && last2_move.isNormal()
1201  && isMajor(last2_move.ptype())
1202  && state.state().hasEffectByPiece
1203  (state.state().pieceOnBoard(last_to), last2_move.to()))
1205  {
1206  {
1207  moves.clear();
1208  QuiescenceGenerator<P>::template escapeFromLastMove<EvalT>(state.state(), last_move, moves);
1209  if (examineMoves<P,has_record,false,ESCAPE>
1210  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1211  return cur_val;
1212  }
1213  }
1214  if ((depthFromRoot() < QSearch2PrivateTraits::AttackMajorPieceDepthFromRoot)
1215  || (isMajor(last_move.ptype())
1216  && last_move.isCapture()
1217  && last_to.template canPromote<P>())
1218  || (state.state().hasEffectAt(P, last_to)
1219  && (state.state().
1220  template hasEffectByPtype<ROOK>(alt(P), last_to)))
1221  || ((depthFromRoot() < QSearch2PrivateTraits::AttackMajorPieceDepthFromRoot+2)
1222  && ((last2_move.capturePtype()==KNIGHT)
1223  || (last2_move.capturePtype()==LANCE)
1224  || (last2_move.capturePtype()==BISHOP)))
1226  {
1227  {
1228  moves.clear();
1229  QuiescenceGenerator<P>::attackMajorPiece(state.state(), pins, moves);
1230  if (examineMoves<P,has_record,true,ATTACK>
1231  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1232  return cur_val;
1233  }
1234  }
1235  {
1236  const QuiescenceRecord *parent
1237  = (state.hasLastRecord(1) && state.lastRecord(1))
1238  ? &(state.lastRecord(1)->qrecord) : 0;
1239  if ((depthFromRoot() < QSearch2PrivateTraits::AttackKing8DepthFromRoot)
1240  || (last_move.isNormal() && last_move.ptype() == KING
1241  && last_move.isCapture())
1242  || (((parent && parent->threatmate.isThreatmate(alt(P)))
1243  || (king_info.liberty() == 0))
1244  && depthFromRoot() < 2+QSearch2PrivateTraits::AttackKing8DepthFromRoot)
1246  {
1247  {
1248  moves.clear();
1249  QuiescenceGenerator<P>::attackKing8(state.state(), pins, moves);
1250  if (examineMoves<P,has_record,false,ATTACK>
1251  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1252  return cur_val;
1253  }
1254  }
1255  }
1256  if ((depthFromRoot() < QSearch2PrivateTraits::AttackGoldSilverDepthFromRoot)
1258  {
1259  {
1260  moves.clear();
1261  QuiescenceGenerator<P>::attackGoldWithPawn(state.state(), pins, moves);
1263  if (examineMoves<P,has_record,false,ATTACK>
1264  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1265  return cur_val;
1266  }
1267  }
1268  if ((depthFromRoot() < QSearch2PrivateTraits::AttackKnightDepthFromRoot)
1270  {
1271  {
1272  moves.clear();
1274  if (examineMoves<P,has_record,false,ATTACK>
1275  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1276  return cur_val;
1277  }
1278  }
1279  if ((depth() >= QSearch2PrivateTraits::UtilizePromotedDepth)
1281  {
1282  if (last2_move.isNormal())
1283  {
1284  const Piece last_piece = state.state().pieceOnBoard(last2_move.to());
1285  assert(last_piece.isPiece());
1286  if (last_piece.owner() == P)
1287  {
1288  moves.clear();
1289  QuiescenceGenerator<P>::utilizePromoted(state.state(), last_piece, moves);
1290  if (examineMoves<P,has_record,true,OTHER>
1291  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1292  return cur_val;
1293  }
1294  }
1295  }
1296 
1297  if ((depthFromRoot() < QSearch2PrivateTraits::AdvanceBishopDepthFromRoot)
1299  {
1300  {
1301  moves.clear();
1303  if (examineMoves<P,has_record,true,OTHER>
1304  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1305  return cur_val;
1306  }
1307  }
1308 king_walk:
1309  if (has_threatmate
1310  || (! my_king.template canPromote<PlayerTraits<P>::opponent>() //自陣以外
1311  && last2_move.isNormal() && last2_move.ptype() == KING))
1312  {
1313  {
1314  moves.clear();
1315  QuiescenceGenerator<P>::kingWalk(state.state(), moves);
1316  if (examineMoves<P,has_record,true,OTHER>
1317  (record, cur_val, &*moves.begin(), &*moves.end(), alpha, beta, ev, additional_depth))
1318  return cur_val;
1319  }
1320  }
1321 finish:
1322  // cut しなかった
1323  assert(EvalTraits<P>::betterThan(beta, cur_val));
1324  assert(! isWinValue(alt(P), cur_val));
1325 #ifndef DONT_USE_CHECKMATE
1326  const bool threatmate
1327  = EvalTraits<P>::betterThan(ev.captureValue(newPtypeO(P,KING)), cur_val);
1328  int check_after_threatmate = 0;
1329  if (in_pv
1330  && (threatmate
1331  || (check_after_threatmate = state.countCheckAfterThreatmate(alt(P),2))))
1332  {
1333  // test sudden checkmate
1334  int checkmate_nodes = (node_count - node_count_before)/2;
1335  if (check_after_threatmate)
1336  {
1337  if (depthFromRoot() == 1)
1338  {
1339  const int sacrifice = state.countCheckAfterThreatmateSacrifice(alt(P),2);
1340  checkmate_nodes = std::max(checkmate_nodes,
1341  sacrifice*125+check_after_threatmate*50);
1342  }
1343  else
1344  {
1345  checkmate_nodes = std::max(50, checkmate_nodes);
1346  }
1347  }
1348  if (threatmate)
1349  {
1350  if (! has_record)
1351  record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
1352  checkmate_nodes = std::max(checkmate_nodes, 200);
1353  }
1354  Move check_move;
1355  const bool win = (record && checkmate_nodes >= 50)
1356  ? state.isWinningState<P>(record->checkmateNodesLeft(checkmate_nodes),
1357  checkmate_move)
1358  : (((record && record->checkmateNodesLeft(2))
1359  || (! has_record && threatmate))
1360  ? state.isWinningStateShort<P>(2, checkmate_move)
1361  : false);
1362  if (win)
1363  {
1364  const int result = base_t::winByCheckmate(P);
1365  assert(checkmate_move.isValid());
1366  if (! has_record && ! record)
1367  record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
1368  if (has_record || record) {
1369  assert(state.state().isValidMove(checkmate_move));
1370  record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
1371  result, checkmate_move);
1372  }
1373  return result;
1374  }
1375  }
1376 #if 0
1377  // cache がないと重いのでとりあえずoff
1378  // しょうがないので詰将棋 (シミュレーションのみ) を呼ぶ
1379  if (! has_record)
1380  {
1381  assert(! record);
1382  Move checkmate_move=Move::INVALID();
1383  AttackOracleAges oracle_age_dummy;
1384  const bool win_found // TODO: last move のみとどちらが良い?
1385  = state.isWinningState<P>
1386  (0, checkmate_move, oracle_age_dummy);
1387  if (win_found)
1388  {
1389  const int result = base_t::winByCheckmate(P);
1390  assert(checkmate_move.isValid());
1391  record = qallocate(table, state.currentHash(), allocate_depth_in_threatmate, state);
1392  if (record)
1393  {
1394  record->setLowerBound(QSearchTraits::CheckmateSpecialDepth,
1395  result, checkmate_move);
1396  }
1397  return result;
1398  }
1399  }
1400 #endif
1401 #endif
1402 
1403  if (has_record)
1404  {
1405  if (EvalTraits<P>::betterThan(beta, cur_val))
1406  record->setUpperBound(depth(), cur_val);
1407  }
1408  return cur_val;
1409 }
1410 
1411 namespace osl
1412 {
1413  inline bool importantMove(const NumEffectState& state, Move move,
1414  Square my_king, Square op_king)
1415  {
1416  if (move.ptype() == KING)
1417  return true;
1418  my_king = Centering3x3::adjustCenter(my_king);
1419  op_king = Centering3x3::adjustCenter(op_king);
1420  if (Neighboring8Direct::hasEffect(state, move.ptypeO(), move.to(), op_king)
1421  || Neighboring8Direct::hasEffect(state, move.ptypeO(), move.to(), my_king))
1422  return true;
1423  return move.isCapture()
1424  && ((! move.isDrop() && state.longEffectAt(move.from()).any())
1425  || Neighboring8Direct::hasEffect(state, move.capturePtypeO(), move.to(), my_king)
1426  || Neighboring8Direct::hasEffect(state, move.capturePtypeO(), move.to(), op_king));
1427  }
1428 }
1429 
1430 template <class EvalT>
1431 template <osl::Player P>
1434  int& cur_val, int& alpha, int beta, eval_t const& ev)
1435 {
1436  assert(alpha % 2);
1437  assert(beta % 2);
1438  assert(EvalTraits<P>::betterThan(alpha, cur_val));
1439  assert(EvalTraits<P>::notLessThan(beta, alpha));
1440 
1441  const Square my_king = state.state().template kingSquare<P>();
1442  const Square op_king = state.state().template kingSquare<PlayerTraits<P>::opponent>();
1443 
1444  BOOST_FOREACH(Move move, moves)
1445  {
1446 #ifdef QSEARCH_DEBUG
1447  QuiescenceLog::pushMove(depth(), move, 0);
1448 #endif
1449  const int see = See::see(state.state(), move, state.state().pin(P), state.state().pin(alt(P)), &eval_t::Piece_Value);
1450  int result;
1451  if (see > 0 && importantMove(state.state(), move, my_king, op_king))
1452  {
1453  eval_t new_ev = ev;
1454  // TODO: futility pruning here
1456  helper_t helper(result, this, alpha, beta, new_ev, move);
1457  // 表を使わないのでcast
1458  state.doUndoMoveLight<P,helper_t>(move, helper);
1459  }
1460  else
1461  {
1462  result = ev.value() + see*eval_t::seeScale()*EvalTraits<P>::delta;
1463  }
1464  // 安い順にsortしたので一直線に読む 王手回避はする
1465  if (! base_t::isWinValue(alt(P), result))
1466  {
1467  cur_val = EvalTraits<P>::max(cur_val, result);
1468  return EvalTraits<P>::notLessThan(result, beta);
1469  }
1470  }
1471  assert(EvalTraits<P>::betterThan(beta, cur_val));
1472  return false;
1473 }
1474 
1475 template <class EvalT>
1476 template <osl::Player P, bool calm_move_only, bool first_normal_move_only>
1479  QuiescenceThreat& threat2, QuiescenceThreat& threat1,
1480  int beta1, int beta2, eval_t const& ev)
1481 {
1482  if (moves.empty())
1483  return false;
1484  // P は取る側
1485  using move_classifier::Check;
1487  assert(beta1 % 2);
1488  assert(beta2 % 2);
1489  assert(EvalTraits<P>::notLessThan(threat1.value, threat2.value)); // threat1 >= threat2
1490  assert(EvalTraits<P>::betterThan(beta1, threat1.value)); // beta1 > threat1
1491  assert(EvalTraits<P>::betterThan(beta2, threat2.value)); // beta2 > threat2
1492  assert(EvalTraits<P>::notLessThan(beta1, beta2)); // beta1 >= beta2
1493  assert(state.state().turn() == P);
1494 
1495  const Square my_king = state.state().template kingSquare<P>();
1496  const Square op_king = state.state().template kingSquare<PlayerTraits<P>::opponent>();
1497 
1498  int best_value = threat2.value;
1499  BOOST_FOREACH(Move move, moves)
1500  {
1501  const Square to = move.to();
1502  assert(! ShouldPromoteCut::canIgnoreAndNotDrop<P>(move));
1503  if (calm_move_only
1504  && (state.state().countEffect(alt(P),to) > state.state().countEffect(P,to)))
1505  continue;
1506 #ifdef QSEARCH_DEBUG
1507  QuiescenceLog::pushMove(depth(), move, 0);
1508 #endif
1509  int result;
1510  const int see = See::see(state.state(), move, state.state().pin(P), state.state().pin(alt(P)), &eval_t::Piece_Value);
1511  if (see > 0 && importantMove(state.state(), move, my_king, op_king))
1512  {
1513  eval_t new_ev = ev;
1514  // TODO: futility pruning here
1515  const int beta = EvalTraits<P>::notLessThan(threat1.value, beta2) ? beta2 : beta1;
1517  helper_t helper(result, this,
1518  threat2.value+EvalTraits<P>::delta, beta, new_ev, move);
1519  state.doUndoMoveLight<P,helper_t>(move, helper);
1520  }
1521  else
1522  {
1523  result = ev.value() + see*eval_t::seeScale()*EvalTraits<P>::delta;
1524  }
1525  // first_normal_move_only:安い順にsortしたので一直線に読む (王手回避はする)
1526  if (base_t::isWinValue(alt(P), result))
1527  continue;
1528 
1529  // 終了処理
1530  if (EvalTraits<P>::betterThan(result, best_value))
1531  {
1532  best_value = result;
1533  if (EvalTraits<P>::notLessThan(best_value, threat1.value))
1534  {
1535  threat2 = threat1;
1536  threat1 = QuiescenceThreat(best_value, move);
1537  if (EvalTraits<P>::betterThan(threat1.value, beta1)
1538  || EvalTraits<P>::betterThan(threat2.value, beta2))
1539  return true;
1540  }
1541  else
1542  {
1543  assert(EvalTraits<P>::notLessThan(best_value, threat2.value));
1544  threat2 = QuiescenceThreat(best_value, move);
1545  if (EvalTraits<P>::betterThan(threat2.value, beta2))
1546  return true;
1547  }
1548  }
1549  if (first_normal_move_only)
1550  break;
1551  }
1552  return false;
1553 
1554  // 取り返す手でcutしなかった場合:
1555  // 逃げられない脅威の評価 (Opponent が逃げる)
1556  // 逃げられない場合はthreat1 だけでなくthreat2にもsetする
1557  assert(! moves.empty());
1558  if (! EvalTraits<P>::betterThan(best_value, threat2.value))
1559  return false;
1560  const Move threat_move = *moves.begin();
1561  if (! first_normal_move_only)
1562  {
1563  assert(state.lastMove().isPass());
1564  state.popPass();
1565  bool cut_by_threat2 = false;
1566  // 成る手が防げるか? TODO: 長い利きを近くで止める
1567  const Player Opponent = PlayerTraits<P>::opponent;
1568  MoveVector moves;
1569  move_generator::GenerateAddEffectWithEffect::generate<false>
1570  (Opponent, state.state(), threat_move.to(), moves);
1571  if (moves.empty())
1572  {
1573  threat2 = QuiescenceThreat(best_value, threat_move);
1574  if (EvalTraits<P>::betterThan(threat2.value, beta2))
1575  cut_by_threat2 = true;
1576  }
1577  state.pushPass();
1578  return cut_by_threat2;
1579  }
1580  else if ((depthFromRoot() < QSearch2PrivateTraits::EscapeFromLastMoveDepthFromRoot)
1581  || (unpromote(moves[0].capturePtype()) == ROOK)
1582  || (unpromote(moves[0].capturePtype()) == BISHOP))
1583  {
1584  assert(state.lastMove().isPass());
1585  state.popPass();
1586  bool cut_by_threat2 = false;
1587  const Square to = threat_move.to();
1588  const Piece target = state.state().pieceOnBoard(to);
1589  bool tried_escape
1590  = (depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot);
1591 #ifdef QSEARCH_PESSIMISTIC_ESCAPE_THREAT
1592  if (state.lastMove().isNormal())
1593  {
1594  // 直前の利きは逃げているはずなので,パスは pessimistic に
1595  // TODO: escapeFromOtherThanPawnに合わせて hasEffectIf に変更
1596  const Offset32 offset32(to, state.lastMove().to());
1597  const EffectContent effect
1598  = Ptype_Table.getEffect(state.lastMove().ptypeO(),offset32);
1599  tried_escape = effect.hasEffect();
1600  }
1601 #endif
1602  if (! tried_escape)
1603  {
1604  const Player Opponent = PlayerTraits<P>::opponent;
1606  const bool safe_escape
1608  target, escape);
1609  if (safe_escape)
1610  goto finish;
1611  BOOST_FOREACH(Move move, escape)
1612  {
1613  eval_t new_ev = ev;
1614  new_ev.update(state.state(), Move::PASS(P));
1615  int result;
1616  if (isMajor(move.ptype()))
1617  {
1619  helper_t helper(result, this, best_value+EvalTraits<Opponent>::delta,
1620  threat2.value+EvalTraits<P>::delta, new_ev, move);
1621  state.doUndoMoveLight<Opponent,helper_t>(move, helper);
1622  }
1623  else
1624  {
1626  helper_t helper(result, this, best_value+EvalTraits<Opponent>::delta,
1627  threat2.value+EvalTraits<P>::delta, new_ev, move);
1628  state.doUndoMoveLight<Opponent,helper_t>(move, helper);
1629  }
1630  if (EvalTraits<Opponent>::betterThan(result, best_value))
1631  {
1632  best_value = result;
1633  if (EvalTraits<Opponent>::notLessThan(result, threat2.value))
1634  break;
1635  }
1636  }
1637  }
1638  if (EvalTraits<P>::betterThan(best_value, threat2.value))
1639  {
1640  threat2 = QuiescenceThreat(best_value, threat_move);
1641  if (EvalTraits<P>::betterThan(threat2.value, beta2))
1642  {
1643  cut_by_threat2 = true;
1644  goto finish;
1645  }
1646  }
1647  finish:
1648  state.pushPass();
1649  return cut_by_threat2;
1650  }
1651  return false;
1652 }
1653 
1654 template <class EvalT>
1655 template <osl::Player P>
1657 takeBackOrChase(int alpha, int beta, eval_t const& ev, Move last_move)
1658 {
1659  assert(last_move.isNormal());
1660  int best_value = takeBackValue<P>(alpha, beta, ev, last_move);
1661  if (EvalTraits<P>::betterThan(best_value, beta))
1662  return best_value;
1663 
1664  MoveVector moves;
1665  QuiescenceGenerator<P>::capture1(state.state(), last_move.from(), moves);
1666  if (moves.empty())
1667  return best_value;
1668  BOOST_FOREACH(Move move, moves)
1669  {
1670  eval_t new_ev = ev;
1671 
1672  typedef QSearch2SafeEscape<eval_t, P> helper_t;
1673  helper_t helper(&state.state(),
1674  state.state().pieceOnBoard(last_move.to()),
1675  new_ev, move);
1676  state.doUndoMoveLight<P,helper_t>(move, helper);
1677  if (helper.is_invalid)
1678  continue;
1679 
1680  int result = new_ev.value();
1681  if (! helper.has_safe_escape)
1682  result += new_ev.captureValue(last_move.ptypeO());
1683  if (state.state().template hasEffectByPtype<ROOK>(P, move.from()))
1684  result += (new_ev.captureValue(newPtypeO(alt(P),PROOK))
1685  - new_ev.captureValue(newPtypeO(alt(P),ROOK)));
1686  best_value = EvalTraits<P>::max(result, best_value);
1687  break; // 追撃は一手だけ試す
1688  }
1689  return best_value;
1690 }
1691 
1692 template <class EvalT>
1693 template <osl::Player P>
1695 takeBackValue(int alpha, int beta, eval_t const& ev, Move last_move)
1696 {
1697  assert(alpha % 2);
1698  assert(beta % 2);
1699 
1700  ++node_count;
1701  assert(EvalTraits<P>::notLessThan(beta, alpha));
1702  if (state.state().inCheck(alt(P)))
1703  return base_t::winByFoul(P);
1704  if (last_move.isPass())
1705  return ev.value();
1706 
1707  const Square last_to = last_move.to();
1708  MoveVector moves;
1709  const Piece last_move_piece = state.state().pieceOnBoard(last_to);
1710  int cur_val;
1711  if (state.state().inCheck())
1712  {
1713  const bool check_by_lance = state.state().hasEffectByPtypeStrict<LANCE>
1714  (alt(P), state.state().template kingSquare<P>());
1715  const bool has_safe_move
1716  = QuiescenceGenerator<P>::escapeKingInTakeBack(state.state(), moves, check_by_lance);
1717  cur_val = (has_safe_move
1718  ? currentValueWithLastThreat(ev, last_move_piece)
1719  : base_t::winByCheckmate(alt(P)));
1720  assert(cur_val % 2 == 0);
1721  }
1722  else
1723  {
1724  cur_val = currentValueWithLastThreat(ev, last_move_piece);
1725  assert(cur_val % 2 == 0);
1726  if (EvalTraits<P>::betterThan(cur_val, beta)) // generate の省略
1727  return cur_val;
1728  QuiescenceGenerator<P>::capture1(state.state(),
1729  last_move_piece.square(), moves);
1730  }
1731  if (EvalTraits<P>::betterThan(cur_val, alpha))
1732  {
1733  alpha = cur_val + EvalTraits<P>::delta;
1734  if (EvalTraits<P>::betterThan(cur_val, beta)) {
1735  return cur_val;
1736  }
1737  }
1738 
1739  assert(EvalTraits<P>::betterThan(alpha, cur_val));
1740  if (examineTakeBack<P>(moves, cur_val, alpha, beta, ev)) {
1741  assert(cur_val % 2 == 0);
1742  return cur_val;
1743  }
1744 
1745  // cut しなかった
1746  assert(cur_val % 2 == 0);
1747  return cur_val;
1748 }
1749 
1750 template <class EvalT>
1751 template <osl::Player P>
1753 staticValueWithThreat(eval_t const& ev, int alpha,
1754  QuiescenceThreat& threat1, QuiescenceThreat& threat2)
1755 {
1756  assert(alpha % 2);
1757  assert(! state.state().inCheck());
1758  const int static_value = ev.value();
1759  if (EvalTraits<P>::notLessThan(alpha, static_value))
1760  return static_value;
1762  const int FirstThreat = QSearchTraits::FirstThreat;
1763  const int SecondThreat
1764  = (depthFromRoot() < QSearch2PrivateTraits::EscapeDepthFromRoot)
1765  ? 1
1766  : QSearchTraits::SecondThreat;
1767 
1768  const int o_beta1
1769  = (EvalTraits<O>::min(base_t::winByCheckmate(O),
1770  static_value - FirstThreat*(static_value - alpha))
1771  - ((FirstThreat % 2) ? 0 : EvalTraits<O>::delta));
1772  const int o_beta2
1773  = (EvalTraits<O>::min(base_t::winByCheckmate(O),
1774  static_value - SecondThreat*(static_value - alpha))
1775  - ((SecondThreat % 2) ? 0 : EvalTraits<O>::delta));
1776 
1777  threat1.value = static_value;
1778  threat2.value = static_value;
1779 
1780  assert(state.state().turn() == P);
1781  state.pushPass();
1782 
1783  assert(! state.state().inCheck());
1784 
1785  assert(EvalTraits<O>::betterThan(o_beta1, threat1.value));
1786  assert(EvalTraits<O>::betterThan(o_beta2, threat1.value));
1787  assert(EvalTraits<O>::notLessThan(o_beta1, o_beta2));
1788  EvalT ev2(ev);
1789  ev2.update(state.state(), Move::PASS(P));
1790 
1791  MoveVector moves;
1792  if (generateAndExamineTakeBack2<O,ROOK>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1793  goto finish;
1794  if (generateAndExamineTakeBack2<O,BISHOP>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1795  goto finish;
1796  if (generateAndExamineTakeBack2<O,GOLD>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1797  goto finish;
1798  if (generateAndExamineTakeBack2<O,SILVER>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1799  goto finish;
1800  if (generateAndExamineTakeBack2<O,KNIGHT>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1801  goto finish;
1802  if (generateAndExamineTakeBack2<O,LANCE>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1803  goto finish;
1804  // 成る手は飛車と角と歩 (TODO: 玉の近傍)
1805  QuiescenceGenerator<O>::template promoteN<ROOK,1>(state.state(), moves, state.historyTable());
1806  if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1807  goto finish;
1808  moves.clear();
1809  QuiescenceGenerator<O>::template promoteN<BISHOP,1>(state.state(), moves, state.historyTable());
1810  if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1811  goto finish;
1812  moves.clear();
1813  QuiescenceGenerator<O>::template promoteN<PAWN,1>(state.state(), moves, state.historyTable());
1814  if (examineTakeBack2<O,true,false>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1815  goto finish;
1816  moves.clear();
1817  if (depth() >= QSearch2PrivateTraits::PawnCaptureDepth
1818  || max_depth <= 2)
1819  {
1820  if (generateAndExamineTakeBack2<O,PAWN>(moves, threat2, threat1, o_beta1, o_beta2, ev2))
1821  goto finish;
1822  }
1823 finish:
1824  state.popPass();
1825  // handle the first threat more seriously in some condition
1826  if (threat1.move == threat2.move && threat1.move.isNormal()) {
1827  const Piece target = state.state().pieceOnBoard(threat1.move.to());
1828  if (isMajorBasic(target.ptype())
1829  && target.square().template canPromote<O>()) {
1830  assert(alt(target.owner()) == O);
1831  assert(threat1.value % 2 == 0);
1832  return threat1.value;
1833  }
1834  }
1835  // usual KFEND-like threat handling
1836  const int result1 = (static_value - (static_value - threat1.value)/FirstThreat);
1837  const int result2 = (static_value - (static_value - threat2.value)/SecondThreat);
1838 
1839  const int result = EvalTraits<O>::max(result1, result2) & (~0x1);
1840  assert(result % 2 == 0);
1841  return result;
1842 }
1843 
1844 #endif /* OSL_QUIESCENCESEARCH2_TCC */
1845 // ;;; Local Variables:
1846 // ;;; mode:c++
1847 // ;;; c-basic-offset:2
1848 // ;;; End: