fixedDepthSearcher.tcc
Go to the documentation of this file.
1 /* fixedDepthSearcher.tcc
2  */
3 #ifndef OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC
4 #define OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC
5 #include "osl/checkmate/fixedDepthSearcher.h"
6 #include "osl/checkmate/immediateCheckmate.h"
7 #include "osl/numEffectState.h"
8 #include "osl/move_generator/move_action.h"
9 #include "osl/move_generator/addEffectWithEffect.h"
10 #include "osl/move_generator/escape_.h"
11 #include "osl/move_classifier/check_.h"
12 
13 namespace osl
14 {
15  namespace checkmate
16  {
17  template<Player P, class SetPieces>
18  struct FixedAttackHelper{
19  FixedDepthSearcher &searcher;
20  Move move;
21  int depth;
22  ProofDisproof& pdp;
23  PieceStand& pieces;
24  FixedAttackHelper(FixedDepthSearcher &s,int d,ProofDisproof& p,
25  PieceStand& pi)
26  : searcher(s), depth(d), pdp(p), pieces(pi)
27  {
28  }
29  void operator()(Square)
30  {
31  assert(move.isNormal());
32  pdp=searcher.defense<P,SetPieces>(move,depth-1,pieces);
33  }
34  };
35  /**
36  * Pは動かす側ではなく攻撃側
37  */
38  template<Player P, class SetPieces, bool MayUnsafe=false>
39  struct FixedDefenseHelper{
40  FixedDepthSearcher &searcher;
41  int depth;
42  ProofDisproof& pdp;
43  PieceStand& pieces;
44  Move best_move;
45  FixedDefenseHelper(FixedDepthSearcher &s,int d,ProofDisproof& p,
46  PieceStand& pi)
47  : searcher(s), depth(d), pdp(p), pieces(pi)
48  {
49  }
50  void operator()(Square)
51  {
52  if (MayUnsafe)
53  pdp=searcher.attackMayUnsafe<P,SetPieces,false>(depth-1, best_move, pieces);
54  else
55  pdp=searcher.attack<P,SetPieces,false>(depth-1, best_move, pieces);
56  }
57  };
58  }
59 }
60 
61 template <osl::Player P, class SetPieces, bool HasGuide>
62 const osl::checkmate::ProofDisproof
63 osl::checkmate::FixedDepthSearcher::
64 attackMayUnsafe(int depth, Move& best_move, PieceStand& proof_pieces)
65 {
66  assert(state->turn() == P);
67  const Square target_king
68  = state->template kingSquare<alt(P)>();
69  if (state->hasEffectAt<P>(target_king))
70  return ProofDisproof::NoEscape();
71  return attack<P,SetPieces,HasGuide>(depth, best_move, proof_pieces);
72 }
73 
74 template <osl::Player P, class SetPieces, bool HasGuide>
75 const osl::checkmate::ProofDisproof
76 osl::checkmate::FixedDepthSearcher::
77 attack(int depth, Move& best_move, PieceStand& proof_pieces)
78 {
79  assert(state->turn() == P);
80  assert ((! HasGuide)
81  || (state->isAlmostValidMove(best_move)
82  && move_classifier::
83  Check<P>::isMember(*state, best_move.ptype(), best_move.from(),
84  best_move.to())));
85  addCount();
86  const Square target_king
87  = state->template kingSquare<alt(P)>();
88  assert(! state->hasEffectAt<P>(target_king));
89  const King8Info info(state->Iking8Info(alt(P)));
90  if ((! state->inCheck())
91  && ImmediateCheckmate::hasCheckmateMove<P>(*state, info, target_king,
92  best_move))
93  {
94  SetPieces::setAttackLeaf(best_move, proof_pieces);
95  return ProofDisproof::Checkmate();
96  }
97  if (depth <= 0)
98  {
99  return SetPieces::attackEstimation(*state, P, info);
100  }
101 
102  ProofDisproof pdp;
103  typedef FixedAttackHelper<P,SetPieces> helper_t;
104  helper_t helper(*this,depth,pdp,proof_pieces);
105  int minProof = ProofDisproof::PROOF_MAX;
106  int sumDisproof=0;
107  if (HasGuide)
108  {
109  helper.move=best_move;
110  state->makeUnmakeMove(Player2Type<P>(),best_move,helper);
111  if (pdp.isCheckmateSuccess())
112  {
113  SetPieces::attack(best_move, PieceStand(P,*state), proof_pieces);
114  return ProofDisproof::Checkmate();
115  }
116  minProof = pdp.proof();
117  sumDisproof += pdp.disproof();
118  }
119 
120  const Square targetKing
121  = state->template kingSquare<alt(P)>();
122  CheckMoveVector moves;
123  bool has_pawn_checkmate=false;
124  {
125  move_action::Store store(moves);
126  move_generator::AddEffectWithEffect<move_action::Store>::template generate<P,true>
127  (*state,targetKing,store,has_pawn_checkmate);
128  }
129  if (moves.size()==0){
130  if(has_pawn_checkmate)
131  return ProofDisproof::PawnCheckmate();
132  else
133  return ProofDisproof::NoCheckmate();
134  }
135  if(has_pawn_checkmate)
136  minProof=std::min(minProof,(int)ProofDisproof::PAWN_CHECK_MATE_PROOF);
137  for (Move move: moves) {
138  if (HasGuide && move == best_move)
139  continue;
140  helper.move=move;
141  state->makeUnmakeMove(Player2Type<P>(), move,helper);
142  int proof=pdp.proof();
143  if (proof<minProof){
144  if (proof==0){
145  best_move=move;
146  SetPieces::attack(best_move, PieceStand(P,*state), proof_pieces);
147  return ProofDisproof::Checkmate();
148  }
149  minProof=proof;
150  }
151  sumDisproof+=pdp.disproof();
152  }
153  // depth >= 3 では PawnCheckmateの際にunpromoteを試す必要あり
154  return ProofDisproof(minProof,sumDisproof);
155 }
156 
157 template <osl::Player P, class SetPieces>
158 inline
159 const osl::checkmate::ProofDisproof
160 osl::checkmate::FixedDepthSearcher::
161 defenseEstimation(Move last_move, PieceStand& proof_pieces,
162  Piece attacker_piece, Square target_position) const
163 {
164  assert(state->turn() == alt(P));
165  const Player Opponent = alt(P);
166  int count=King8Info(state->Iking8Info(Opponent)).libertyCount();
167  // multiple checkなので,pawn dropではない
168  if (attacker_piece.isEmpty())
169  {
170  if (count>0){
171  return ProofDisproof(count,1);
172  }
173  return ProofDisproof::NoEscape();
174  }
175  const Square attack_from=attacker_piece.square();
176  count += state->countEffect(alt(P), attack_from);
177  if (attack_from.isNeighboring8(target_position))
178  --count;
179  const EffectContent effect
180  = Ptype_Table.getEffect(attacker_piece.ptypeO(),
181  attack_from, target_position);
182  if (! effect.hasUnblockableEffect())
183  {
184  // this is better approximation than naive enumeration of blocking moves,
185  // for counting of disproof number in df-pn,
186  ++count;
187  }
188 
189  if (count==0){
190  if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
191  return ProofDisproof::PawnCheckmate();
192  SetPieces::setLeaf(*state, P, stand(P), proof_pieces);
193  return ProofDisproof::NoEscape();
194  }
195  return ProofDisproof(count, 1);
196 }
197 
198 template <osl::Player Defense>
199 void osl::checkmate::FixedDepthSearcher::
200 generateBlockingWhenLiberty0(Piece defense_king, Square attack_from,
201  CheckMoveVector& moves) const
202 {
203  assert(state->kingPiece(Defense) == defense_king);
204  using namespace move_generator;
205  using namespace move_action;
206  CheckMoveVector all_moves;
207  {
208  Store store(all_moves);
209  Escape<Store>::
210  generateBlockingKing<Defense,false>(*state, defense_king, attack_from,store);
211  }
212 
213  for (Move move: all_moves)
214  {
215  if (move.isDrop())
216  {
217  if (! state->hasEffectAt<Defense>(move.to()))
218  continue;
219  }
220  else
221  {
222  // move
223  if (! move.from().isNeighboring8(defense_king.square()))
224  {
225  if (! state->hasMultipleEffectAt(Defense, move.to()))
226  continue;
227  }
228  }
229  moves.push_back(move);
230  }
231 }
232 
233 template <osl::Player Defense> inline
234 int osl::checkmate::FixedDepthSearcher::
235 blockEstimation(Square /*attack_from*/, Square /*defense_king*/) const
236 {
237  // 利きのあるマスを数えようと思ったら効果がなかった
238  return 1;
239 }
240 
241 template <osl::Player P, class SetPieces>
242 const osl::checkmate::ProofDisproof
243 osl::checkmate::FixedDepthSearcher::
244 defense(Move last_move, int depth, PieceStand& proof_pieces)
245 {
246  assert(state->turn() == alt(P));
247  addCount();
248  const Player Defense = alt(P);
249  const Square attackerKing
250  = state->template kingSquare<P>();
251  /**
252  * 直前の攻め方の手が自殺手
253  */
254  if (attackerKing.isOnBoard() && state->hasEffectAt<Defense>(attackerKing))
255  return ProofDisproof::NoCheckmate();
256  const Piece target_king
257  = state->template kingPiece<Defense>();
258  const Square target_position = target_king.square();
259  assert(state->hasEffectAt<P>(target_position));
260  Piece attacker_piece;
261  state->template findCheckPiece<Defense>(attacker_piece);
262  if (depth <= 0)
263  {
264  return defenseEstimation<P, SetPieces>
265  (last_move, proof_pieces, attacker_piece, target_position);
266  }
267 
268  assert(depth > 0);
269  CheckMoveVector moves;
270  bool blockable_check = false;
271  int nonblock_moves;
272  {
273  using namespace move_generator;
274  using namespace move_action;
275  if (attacker_piece.isEmpty()) {
276  move_action::Store store(moves);
277  Escape<Store>::template
278  generateEscape<Defense,KING>(*state,target_king,store);
279  nonblock_moves = moves.size();
280  }
281  else {
282  const Square attack_from=attacker_piece.square();
283  {
284  move_action::Store store(moves);
285  Escape<Store>::
286  generateCaptureKing<Defense>(*state, target_king, attack_from, store);
287  }
288  const int num_captures = moves.size();
289  {
290  move_action::Store store(moves);
291  Escape<Store>::template
292  generateEscape<Defense,KING>(*state, target_king, store);
293  }
294  nonblock_moves = moves.size();
295  blockable_check = ! state->inUnblockableCheck(alt(P));
296  if ((depth <= 1) && num_captures && (nonblock_moves > 2))
297  {
298  if (nonblock_moves > 3)
299  {
300  const int block_estimate = blockable_check
301  ? blockEstimation<Defense>(attack_from, target_position)
302  : 0;
303  return ProofDisproof(nonblock_moves + block_estimate, 1);
304  }
305  }
306  if (moves.empty())
307  generateBlockingWhenLiberty0<Defense>(target_king, attack_from, moves);
308  }
309  }
310  const size_t initial_moves = moves.size();
311  if (moves.empty() && !blockable_check) {
312  if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
313  return ProofDisproof::PawnCheckmate();
314  SetPieces::setLeaf(*state, P, PieceStand(P,*state), proof_pieces);
315  return ProofDisproof::NoEscape();
316  }
317  const bool cut_candidate = (depth <= 1)
318  && (nonblock_moves - (state->hasPieceOnStand<GOLD>(P)
319  || state->hasPieceOnStand<SILVER>(P)) > 4);
320  if (cut_candidate)
321  return ProofDisproof(nonblock_moves, 1);
322 
323  typedef FixedDefenseHelper<P,SetPieces> helper_t;
324  SetPieces::clear(proof_pieces);
325  PieceStand child_proof;
326  ProofDisproof pdp;
327  helper_t helper(*this, depth, pdp, child_proof);
328  int minDisproof = ProofDisproof::DISPROOF_MAX;
329  int sumProof = 0;
330  size_t i=0, no_promote_moves=0;
331 start_examine:
332  for (;i<moves.size();i++){
333  state->makeUnmakeMove(Player2Type<alt(P)>(),moves[i],helper);
334  const int disproof=pdp.disproof();
335  if (disproof<minDisproof){
336  if (disproof==0)
337  {
338  return pdp; // maybe PawnCheckmate
339  }
340  minDisproof=disproof;
341  }
342  sumProof+=pdp.proof();
343  if (sumProof == 0)
344  {
345  SetPieces::updateMax(child_proof, proof_pieces);
346  }
347  else
348  {
349  if (i+1 < moves.size())
350  {
351  minDisproof = 1;
352  if ((int)i < nonblock_moves)
353  sumProof += nonblock_moves - (i+1);
354  if (blockable_check)
355  ++sumProof;
356  }
357  return ProofDisproof(sumProof,minDisproof);
358  }
359  }
360  if (sumProof == 0)
361  {
362  if (blockable_check && moves.size() == initial_moves)
363  {
364  using namespace move_generator;
365  using namespace move_action;
366  const Square attack_from=attacker_piece.square();
367  {
368  move_action::Store store(moves);
369  Escape<Store>::
370  generateBlockingKing<Defense,false>(*state, target_king, attack_from,store);
371  }
372  if ((int)moves.size() > nonblock_moves)
373  goto start_examine;
374  if (moves.empty()) {
375  assert(! (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN));
376  SetPieces::setLeaf(*state, P, PieceStand(P,*state), proof_pieces);
377  return ProofDisproof::NoEscape();
378  }
379  }
380  if (no_promote_moves == 0)
381  {
382  no_promote_moves = moves.size();
383  for (size_t i=0; i<no_promote_moves; ++i)
384  if (moves[i].hasIgnoredUnpromote<Defense>())
385  moves.push_back(moves[i].unpromote());
386  if (moves.size() > no_promote_moves)
387  goto start_examine;
388  }
389  if (blockable_check)
390  SetPieces::addMonopolizedPieces(*state, P, stand(P), proof_pieces);
391  }
392  // depth >= 2 では unprmote も試す必要あり
393  return ProofDisproof(sumProof,minDisproof);
394 }
395 
396 template <osl::Player P>
397 const osl::checkmate::ProofDisproof
398 osl::checkmate::FixedDepthSearcher::
399 hasEscapeByMove(Move next_move, int depth)
400 {
401  typedef FixedDefenseHelper<P,NoProofPieces,true> helper_t;
402  PieceStand proof_pieces;
403  ProofDisproof pdp;
404  helper_t helper(*this, depth+1, pdp, proof_pieces);
405  state->makeUnmakeMove(Player2Type<alt(P)>(),next_move,helper);
406  return pdp;
407 }
408 
409 #endif /* OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC */
410 // ;;; Local Variables:
411 // ;;; mode:c++
412 // ;;; c-basic-offset:2
413 // ;;; End: