My Project
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
13namespace 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
61template <osl::Player P, class SetPieces, bool HasGuide>
62const osl::checkmate::ProofDisproof
63osl::checkmate::FixedDepthSearcher::
64attackMayUnsafe(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
74template <osl::Player P, class SetPieces, bool HasGuide>
75const osl::checkmate::ProofDisproof
76osl::checkmate::FixedDepthSearcher::
77attack(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
157template <osl::Player P, class SetPieces>
158inline
159const osl::checkmate::ProofDisproof
160osl::checkmate::FixedDepthSearcher::
161defenseEstimation(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
198template <osl::Player Defense>
199void osl::checkmate::FixedDepthSearcher::
200generateBlockingWhenLiberty0(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
233template <osl::Player Defense> inline
234int osl::checkmate::FixedDepthSearcher::
235blockEstimation(Square /*attack_from*/, Square /*defense_king*/) const
236{
237 // 利きのあるマスを数えようと思ったら効果がなかった
238 return 1;
239}
240
241template <osl::Player P, class SetPieces>
242const osl::checkmate::ProofDisproof
243osl::checkmate::FixedDepthSearcher::
244defense(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;
331start_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
396template <osl::Player P>
397const osl::checkmate::ProofDisproof
398osl::checkmate::FixedDepthSearcher::
399hasEscapeByMove(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: