All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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
12 #include "osl/move_action/store.h"
13 #include "osl/move_action/count.h"
18 #include "osl/neighboring8.h"
19 #include "osl/stat/ratio.h"
20 #include <boost/foreach.hpp>
21 
22 namespace osl
23 {
24  namespace checkmate
25  {
26  template<Player P, bool SetPieces>
30  int depth;
34  PieceStand& pi)
35  : searcher(s), depth(d), pdp(p), pieces(pi)
36  {
37  }
39  {
40  assert(move.isNormal());
41  pdp=searcher.defense<P,SetPieces>(move,depth-1,pieces);
42  }
43  };
47  template<Player P, bool SetPieces, bool MayUnsafe=false>
50  int depth;
55  PieceStand& pi)
56  : searcher(s), depth(d), pdp(p), pieces(pi)
57  {
58  }
60  {
61  if (MayUnsafe)
62  pdp=searcher.attackMayUnsafe<P,SetPieces,false>(depth-1, best_move, pieces);
63  else
64  pdp=searcher.attack<P,SetPieces,false>(depth-1, best_move, pieces);
65  }
66  };
67  }
68 }
69 
70 template <osl::Player P, bool SetPieces, bool HasGuide>
73 attackMayUnsafe(int depth, Move& best_move, PieceStand& proof_pieces)
74 {
75  assert(state->turn() == P);
76  const Square target_king
77  = state->template kingSquare<PlayerTraits<P>::opponent>();
78  if (state->hasEffectAt<P>(target_king))
79  return ProofDisproof::NoEscape();
80  return attack<P,SetPieces,HasGuide>(depth, best_move, proof_pieces);
81 }
82 
83 template <osl::Player P, bool SetPieces, bool HasGuide>
86 attack(int depth, Move& best_move, PieceStand& proof_pieces)
87 {
88  assert(state->turn() == P);
89  assert ((! HasGuide)
90  || (state->isAlmostValidMove(best_move)
92  Check<P>::isMember(*state, best_move.ptype(), best_move.from(),
93  best_move.to())));
94  addCount();
95  const Square target_king
96  = state->template kingSquare<PlayerTraits<P>::opponent>();
97  assert(! state->hasEffectAt<P>(target_king));
98  const King8Info info(state->Iking8Info(alt(P)));
99  if ((! state->inCheck())
100  && ImmediateCheckmate::hasCheckmateMove<P>(*state, info, target_king,
101  best_move))
102  {
103  if (SetPieces)
104  {
105  proof_pieces = PieceStand();
106  if (best_move.isDrop())
107  proof_pieces.add(best_move.ptype());
108  }
109  return ProofDisproof::Checkmate();
110  }
111  if (depth <= 0)
112  {
113  const King8Info info_modified
114  = Edge_Table.resetEdgeFromLiberty(alt(P), target_king, info);
115  return Proof_Number_Table.attackEstimation(*state, P, info_modified, target_king);
116  }
117 
118  ProofDisproof pdp;
119  typedef FixedAttackHelper<P,SetPieces> helper_t;
120  helper_t helper(*this,depth,pdp,proof_pieces);
121  int minProof = ProofDisproof::PROOF_MAX;
122  int sumDisproof=0;
123  if (HasGuide)
124  {
125  helper.move=best_move;
126  state->makeUnmakeMove(Player2Type<P>(),best_move,helper);
127  if (pdp.isCheckmateSuccess())
128  {
129  if (SetPieces)
130  proof_pieces = ProofPieces::attack(proof_pieces, best_move, stand(P));
131  return ProofDisproof::Checkmate();
132  }
133  minProof = pdp.proof();
134  sumDisproof += pdp.disproof();
135  }
136 
137  const Square targetKing
138  = state->template kingSquare<PlayerTraits<P>::opponent>();
140  bool has_pawn_checkmate=false;
141  {
142  move_action::Store store(moves);
144  (*state,targetKing,store,has_pawn_checkmate);
145  }
146  if (moves.size()==0){
147  if(has_pawn_checkmate)
149  else
151  }
152  if(has_pawn_checkmate)
153  minProof=std::min(minProof,(int)ProofDisproof::PAWN_CHECK_MATE_PROOF);
154  BOOST_FOREACH(Move move, moves) {
155  if (HasGuide && move == best_move)
156  continue;
157  helper.move=move;
158  state->makeUnmakeMove(Player2Type<P>(), move,helper);
159  int proof=pdp.proof();
160  if (proof<minProof){
161  if (proof==0){
162  best_move=move;
163  if (SetPieces)
164  {
165  proof_pieces = ProofPieces::attack(proof_pieces, best_move, stand(P));
166  }
167  return ProofDisproof::Checkmate();
168  }
169  minProof=proof;
170  }
171  sumDisproof+=pdp.disproof();
172  }
173  // depth >= 3 では PawnCheckmateの際にunpromoteを試す必要あり
174  return ProofDisproof(minProof,sumDisproof);
175 }
176 
177 template <osl::Player P, bool SetPieces>
178 inline
181 defenseEstimation(Move last_move, PieceStand& proof_pieces,
182  Piece attacker_piece, Square target_position) const
183 {
184  assert(state->turn() == alt(P));
185  const Player Opponent = PlayerTraits<P>::opponent;
186  int count=King8Info(state->Iking8Info(Opponent)).libertyCount();
187  // multiple checkなので,pawn dropではない
188  if (attacker_piece.isEmpty())
189  {
190  if (count>0){
191  return ProofDisproof(count,1);
192  }
193  return ProofDisproof::NoEscape();
194  }
195  const Square attack_from=attacker_piece.square();
196  count += state->countEffect(alt(P), attack_from);
197  if (Neighboring8::isNeighboring8(attack_from, target_position))
198  --count;
199  const EffectContent effect
200  = Ptype_Table.getEffect(attacker_piece.ptypeO(),
201  attack_from, target_position);
202  if (! effect.hasUnblockableEffect())
203  {
204  // this is better approximation than naive enumeration of blocking moves,
205  // for counting of disproof number in df-pn,
206  ++count;
207  }
208 
209  if (count==0){
210  if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
212  if (SetPieces)
213  {
214  proof_pieces = ProofPieces::leaf(*state, P, stand(P));
215  }
216  return ProofDisproof::NoEscape();
217  }
218  return ProofDisproof(count, 1);
219 }
220 
221 template <osl::Player Defense>
223 generateBlockingWhenLiberty0(Piece defense_king, Square attack_from,
224  CheckMoveVector& moves) const
225 {
226  assert(state->kingPiece(Defense) == defense_king);
227  using namespace move_generator;
228  using namespace move_action;
229  CheckMoveVector all_moves;
230  {
231  Store store(all_moves);
232  Escape<Store>::
233  generateBlockingKing<Defense,false>(*state, defense_king, attack_from,store);
234  }
235 
236  BOOST_FOREACH(Move move, all_moves)
237  {
238  if (move.isDrop())
239  {
240  if (! state->hasEffectAt<Defense>(move.to()))
241  continue;
242  }
243  else
244  {
245  // move
246  if (! Neighboring8::isNeighboring8(move.from(), defense_king.square()))
247  {
248  if (! state->hasMultipleEffectAt(Defense, move.to()))
249  continue;
250  }
251  }
252  moves.push_back(move);
253  }
254 }
255 
256 template <osl::Player Defense> inline
258 blockEstimation(Square /*attack_from*/, Square /*defense_king*/) const
259 {
260  // 利きのあるマスを数えようと思ったら効果がなかった
261  return 1;
262 }
263 
264 template <osl::Player P, bool SetPieces>
267 defense(Move last_move, int depth, PieceStand& proof_pieces)
268 {
269  assert(state->turn() == alt(P));
270  addCount();
271  const Player Defense = PlayerTraits<P>::opponent;
272  const Square attackerKing
273  = state->template kingSquare<P>();
277  if (attackerKing.isOnBoard() && state->hasEffectAt<Defense>(attackerKing))
279  const Piece target_king
280  = state->template kingPiece<Defense>();
281  const Square target_position = target_king.square();
282  assert(state->hasEffectAt<P>(target_position));
283  Piece attacker_piece;
284  state->template findCheckPiece<Defense>(attacker_piece);
285  if (depth <= 0)
286  {
287  return defenseEstimation<P, SetPieces>
288  (last_move, proof_pieces, attacker_piece, target_position);
289  }
290 
291  assert(depth > 0);
293  bool blockable_check = false;
294  int nonblock_moves;
295  {
296  using namespace move_generator;
297  using namespace move_action;
298  if (attacker_piece.isEmpty()) {
299  move_action::Store store(moves);
300  Escape<Store>::template
301  generateEscape<Defense,KING>(*state,target_king,store);
302  nonblock_moves = moves.size();
303  }
304  else {
305  const Square attack_from=attacker_piece.square();
306  {
307  move_action::Store store(moves);
308  Escape<Store>::
309  generateCaptureKing<Defense>(*state, target_king, attack_from, store);
310  }
311  const int num_captures = moves.size();
312  {
313  move_action::Store store(moves);
314  Escape<Store>::template
315  generateEscape<Defense,KING>(*state, target_king, store);
316  }
317  nonblock_moves = moves.size();
318  blockable_check =
320  if ((depth <= 1) && num_captures && (nonblock_moves > 2))
321  {
322  if (nonblock_moves > 3)
323  {
324  const int block_estimate = blockable_check
325  ? blockEstimation<Defense>(attack_from, target_position)
326  : 0;
327  return ProofDisproof(nonblock_moves + block_estimate, 1);
328  }
329  }
330  if (moves.empty())
331  generateBlockingWhenLiberty0<Defense>(target_king, attack_from, moves);
332  }
333  }
334  const size_t initial_moves = moves.size();
335  if (moves.empty() && !blockable_check) {
336  if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
338  if (SetPieces)
339  {
340  proof_pieces = ProofPieces::leaf(*state, P, stand(P));
341  }
342  return ProofDisproof::NoEscape();
343  }
344  const bool cut_candidate = (depth <= 1)
345  && (nonblock_moves - (state->hasPieceOnStand<GOLD>(P)
346  || state->hasPieceOnStand<SILVER>(P)) > 4);
347  if (cut_candidate)
348  return ProofDisproof(nonblock_moves, 1);
349 
350  typedef FixedDefenseHelper<P,SetPieces> helper_t;
351  if (SetPieces)
352  proof_pieces = PieceStand();
353  PieceStand child_proof;
354  ProofDisproof pdp;
355  helper_t helper(*this, depth, pdp, child_proof);
356  int minDisproof = ProofDisproof::DISPROOF_MAX;
357  int sumProof = 0;
358  size_t i=0, no_promote_moves=0;
359 start_examine:
360  for (;i<moves.size();i++){
361  state->makeUnmakeMove(Player2Type<PlayerTraits<P>::opponent>(),moves[i],helper);
362  const int disproof=pdp.disproof();
363  if (disproof<minDisproof){
364  if (disproof==0)
365  {
366  return pdp; // maybe PawnCheckmate
367  }
368  minDisproof=disproof;
369  }
370  sumProof+=pdp.proof();
371  if (sumProof == 0)
372  {
373  if (SetPieces)
374  proof_pieces = proof_pieces.max(child_proof);
375  }
376  else
377  {
378  if (i+1 < moves.size())
379  {
380  minDisproof = 1;
381  if ((int)i < nonblock_moves)
382  sumProof += nonblock_moves - (i+1);
383  if (blockable_check)
384  ++sumProof;
385  }
386  return ProofDisproof(sumProof,minDisproof);
387  }
388  }
389  if (sumProof == 0)
390  {
391  if (blockable_check && moves.size() == initial_moves)
392  {
393  using namespace move_generator;
394  using namespace move_action;
395  const Square attack_from=attacker_piece.square();
396  {
397  move_action::Store store(moves);
398  Escape<Store>::
399  generateBlockingKing<Defense,false>(*state, target_king, attack_from,store);
400  }
401  if ((int)moves.size() > nonblock_moves)
402  goto start_examine;
403  if (moves.empty()) {
404  assert(! (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN));
405  if (SetPieces)
406  proof_pieces = ProofPieces::leaf(*state, P, stand(P));
407  return ProofDisproof::NoEscape();
408  }
409  }
410  if (no_promote_moves == 0)
411  {
412  no_promote_moves = moves.size();
413  for (size_t i=0; i<no_promote_moves; ++i)
414  if (moves[i].hasIgnoredUnpromote<Defense>())
415  moves.push_back(moves[i].unpromote());
416  if (moves.size() > no_promote_moves)
417  goto start_examine;
418  }
419  if (SetPieces && blockable_check)
420  ProofPiecesUtil::addMonopolizedPieces(*state, P, stand(P), proof_pieces);
421  }
422  // depth >= 2 では unprmote も試す必要あり
423  return ProofDisproof(sumProof,minDisproof);
424 }
425 
426 template <osl::Player P>
429 hasEscapeByMove(Move next_move, int depth, Move& check_move,
430  PieceStand& proof_pieces)
431 {
432  typedef FixedDefenseHelper<P,true,true> helper_t;
433  proof_pieces = PieceStand();
434  ProofDisproof pdp;
435  helper_t helper(*this, depth+1, pdp, proof_pieces);
436  state->makeUnmakeMove(Player2Type<PlayerTraits<P>::opponent>(),next_move,helper);
437  check_move = helper.best_move;
438  return pdp;
439 }
440 
441 template <osl::Player P>
444 hasEscapeByMove(Move next_move, int depth)
445 {
446  typedef FixedDefenseHelper<P,false,true> helper_t;
447  PieceStand proof_pieces;
448  ProofDisproof pdp;
449  helper_t helper(*this, depth+1, pdp, proof_pieces);
450  state->makeUnmakeMove(Player2Type<PlayerTraits<P>::opponent>(),next_move,helper);
451  return pdp;
452 }
453 
454 template <osl::Player P>
457 hasCheckmateWithGuide(int depth, Move& guide, PieceStand& proof_pieces)
458 {
459  assert(guide.isNormal());
460  if (! guide.isDrop())
461  {
462  const Piece p=state->pieceOnBoard(guide.to());
463  if (!p.isPtype<KING>())
464  guide=guide.newCapture(p);
465  }
466  if (state->template isAlmostValidMove<false>(guide)
468  ::isMember(*state, guide.ptype(), guide.from(), guide.to()))
469  return attack<P,true,true>(depth, guide, proof_pieces);
470  return attack<P,true,false>(depth, guide, proof_pieces);
471 }
472 
473 #endif /* OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC */
474 // ;;; Local Variables:
475 // ;;; mode:c++
476 // ;;; c-basic-offset:2
477 // ;;; End: