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