00001
00002
00003 #ifndef OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC
00004 #define OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC
00005 #include "osl/checkmate/fixedDepthSearcher.h"
00006 #include "osl/checkmate/immediateCheckmate.h"
00007 #include "osl/numEffectState.h"
00008 #include "osl/move_generator/move_action.h"
00009 #include "osl/move_generator/addEffectWithEffect.h"
00010 #include "osl/move_generator/escape_.h"
00011 #include "osl/move_classifier/check_.h"
00012
00013 namespace osl
00014 {
00015 namespace checkmate
00016 {
00017 template<Player P, class SetPieces>
00018 struct FixedAttackHelper{
00019 FixedDepthSearcher &searcher;
00020 Move move;
00021 int depth;
00022 ProofDisproof& pdp;
00023 PieceStand& pieces;
00024 FixedAttackHelper(FixedDepthSearcher &s,int d,ProofDisproof& p,
00025 PieceStand& pi)
00026 : searcher(s), depth(d), pdp(p), pieces(pi)
00027 {
00028 }
00029 void operator()(Square)
00030 {
00031 assert(move.isNormal());
00032 pdp=searcher.defense<P,SetPieces>(move,depth-1,pieces);
00033 }
00034 };
00038 template<Player P, class SetPieces, bool MayUnsafe=false>
00039 struct FixedDefenseHelper{
00040 FixedDepthSearcher &searcher;
00041 int depth;
00042 ProofDisproof& pdp;
00043 PieceStand& pieces;
00044 Move best_move;
00045 FixedDefenseHelper(FixedDepthSearcher &s,int d,ProofDisproof& p,
00046 PieceStand& pi)
00047 : searcher(s), depth(d), pdp(p), pieces(pi)
00048 {
00049 }
00050 void operator()(Square)
00051 {
00052 if (MayUnsafe)
00053 pdp=searcher.attackMayUnsafe<P,SetPieces,false>(depth-1, best_move, pieces);
00054 else
00055 pdp=searcher.attack<P,SetPieces,false>(depth-1, best_move, pieces);
00056 }
00057 };
00058 }
00059 }
00060
00061 template <osl::Player P, class SetPieces, bool HasGuide>
00062 const osl::checkmate::ProofDisproof
00063 osl::checkmate::FixedDepthSearcher::
00064 attackMayUnsafe(int depth, Move& best_move, PieceStand& proof_pieces)
00065 {
00066 assert(state->turn() == P);
00067 const Square target_king
00068 = state->template kingSquare<alt(P)>();
00069 if (state->hasEffectAt<P>(target_king))
00070 return ProofDisproof::NoEscape();
00071 return attack<P,SetPieces,HasGuide>(depth, best_move, proof_pieces);
00072 }
00073
00074 template <osl::Player P, class SetPieces, bool HasGuide>
00075 const osl::checkmate::ProofDisproof
00076 osl::checkmate::FixedDepthSearcher::
00077 attack(int depth, Move& best_move, PieceStand& proof_pieces)
00078 {
00079 assert(state->turn() == P);
00080 assert ((! HasGuide)
00081 || (state->isAlmostValidMove(best_move)
00082 && move_classifier::
00083 Check<P>::isMember(*state, best_move.ptype(), best_move.from(),
00084 best_move.to())));
00085 addCount();
00086 const Square target_king
00087 = state->template kingSquare<alt(P)>();
00088 assert(! state->hasEffectAt<P>(target_king));
00089 const King8Info info(state->Iking8Info(alt(P)));
00090 if ((! state->inCheck())
00091 && ImmediateCheckmate::hasCheckmateMove<P>(*state, info, target_king,
00092 best_move))
00093 {
00094 SetPieces::setAttackLeaf(best_move, proof_pieces);
00095 return ProofDisproof::Checkmate();
00096 }
00097 if (depth <= 0)
00098 {
00099 return SetPieces::attackEstimation(*state, P, info);
00100 }
00101
00102 ProofDisproof pdp;
00103 typedef FixedAttackHelper<P,SetPieces> helper_t;
00104 helper_t helper(*this,depth,pdp,proof_pieces);
00105 int minProof = ProofDisproof::PROOF_MAX;
00106 int sumDisproof=0;
00107 if (HasGuide)
00108 {
00109 helper.move=best_move;
00110 state->makeUnmakeMove(Player2Type<P>(),best_move,helper);
00111 if (pdp.isCheckmateSuccess())
00112 {
00113 SetPieces::attack(best_move, PieceStand(P,*state), proof_pieces);
00114 return ProofDisproof::Checkmate();
00115 }
00116 minProof = pdp.proof();
00117 sumDisproof += pdp.disproof();
00118 }
00119
00120 const Square targetKing
00121 = state->template kingSquare<alt(P)>();
00122 CheckMoveVector moves;
00123 bool has_pawn_checkmate=false;
00124 {
00125 move_action::Store store(moves);
00126 move_generator::AddEffectWithEffect<move_action::Store>::template generate<P,true>
00127 (*state,targetKing,store,has_pawn_checkmate);
00128 }
00129 if (moves.size()==0){
00130 if(has_pawn_checkmate)
00131 return ProofDisproof::PawnCheckmate();
00132 else
00133 return ProofDisproof::NoCheckmate();
00134 }
00135 if(has_pawn_checkmate)
00136 minProof=std::min(minProof,(int)ProofDisproof::PAWN_CHECK_MATE_PROOF);
00137 for (Move move: moves) {
00138 if (HasGuide && move == best_move)
00139 continue;
00140 helper.move=move;
00141 state->makeUnmakeMove(Player2Type<P>(), move,helper);
00142 int proof=pdp.proof();
00143 if (proof<minProof){
00144 if (proof==0){
00145 best_move=move;
00146 SetPieces::attack(best_move, PieceStand(P,*state), proof_pieces);
00147 return ProofDisproof::Checkmate();
00148 }
00149 minProof=proof;
00150 }
00151 sumDisproof+=pdp.disproof();
00152 }
00153
00154 return ProofDisproof(minProof,sumDisproof);
00155 }
00156
00157 template <osl::Player P, class SetPieces>
00158 inline
00159 const osl::checkmate::ProofDisproof
00160 osl::checkmate::FixedDepthSearcher::
00161 defenseEstimation(Move last_move, PieceStand& proof_pieces,
00162 Piece attacker_piece, Square target_position) const
00163 {
00164 assert(state->turn() == alt(P));
00165 const Player Opponent = alt(P);
00166 int count=King8Info(state->Iking8Info(Opponent)).libertyCount();
00167
00168 if (attacker_piece.isEmpty())
00169 {
00170 if (count>0){
00171 return ProofDisproof(count,1);
00172 }
00173 return ProofDisproof::NoEscape();
00174 }
00175 const Square attack_from=attacker_piece.square();
00176 count += state->countEffect(alt(P), attack_from);
00177 if (attack_from.isNeighboring8(target_position))
00178 --count;
00179 const EffectContent effect
00180 = Ptype_Table.getEffect(attacker_piece.ptypeO(),
00181 attack_from, target_position);
00182 if (! effect.hasUnblockableEffect())
00183 {
00184
00185
00186 ++count;
00187 }
00188
00189 if (count==0){
00190 if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
00191 return ProofDisproof::PawnCheckmate();
00192 SetPieces::setLeaf(*state, P, stand(P), proof_pieces);
00193 return ProofDisproof::NoEscape();
00194 }
00195 return ProofDisproof(count, 1);
00196 }
00197
00198 template <osl::Player Defense>
00199 void osl::checkmate::FixedDepthSearcher::
00200 generateBlockingWhenLiberty0(Piece defense_king, Square attack_from,
00201 CheckMoveVector& moves) const
00202 {
00203 assert(state->kingPiece(Defense) == defense_king);
00204 using namespace move_generator;
00205 using namespace move_action;
00206 CheckMoveVector all_moves;
00207 {
00208 Store store(all_moves);
00209 Escape<Store>::
00210 generateBlockingKing<Defense,false>(*state, defense_king, attack_from,store);
00211 }
00212
00213 for (Move move: all_moves)
00214 {
00215 if (move.isDrop())
00216 {
00217 if (! state->hasEffectAt<Defense>(move.to()))
00218 continue;
00219 }
00220 else
00221 {
00222
00223 if (! move.from().isNeighboring8(defense_king.square()))
00224 {
00225 if (! state->hasMultipleEffectAt(Defense, move.to()))
00226 continue;
00227 }
00228 }
00229 moves.push_back(move);
00230 }
00231 }
00232
00233 template <osl::Player Defense> inline
00234 int osl::checkmate::FixedDepthSearcher::
00235 blockEstimation(Square , Square ) const
00236 {
00237
00238 return 1;
00239 }
00240
00241 template <osl::Player P, class SetPieces>
00242 const osl::checkmate::ProofDisproof
00243 osl::checkmate::FixedDepthSearcher::
00244 defense(Move last_move, int depth, PieceStand& proof_pieces)
00245 {
00246 assert(state->turn() == alt(P));
00247 addCount();
00248 const Player Defense = alt(P);
00249 const Square attackerKing
00250 = state->template kingSquare<P>();
00254 if (attackerKing.isOnBoard() && state->hasEffectAt<Defense>(attackerKing))
00255 return ProofDisproof::NoCheckmate();
00256 const Piece target_king
00257 = state->template kingPiece<Defense>();
00258 const Square target_position = target_king.square();
00259 assert(state->hasEffectAt<P>(target_position));
00260 Piece attacker_piece;
00261 state->template findCheckPiece<Defense>(attacker_piece);
00262 if (depth <= 0)
00263 {
00264 return defenseEstimation<P, SetPieces>
00265 (last_move, proof_pieces, attacker_piece, target_position);
00266 }
00267
00268 assert(depth > 0);
00269 CheckMoveVector moves;
00270 bool blockable_check = false;
00271 int nonblock_moves;
00272 {
00273 using namespace move_generator;
00274 using namespace move_action;
00275 if (attacker_piece.isEmpty()) {
00276 move_action::Store store(moves);
00277 Escape<Store>::template
00278 generateEscape<Defense,KING>(*state,target_king,store);
00279 nonblock_moves = moves.size();
00280 }
00281 else {
00282 const Square attack_from=attacker_piece.square();
00283 {
00284 move_action::Store store(moves);
00285 Escape<Store>::
00286 generateCaptureKing<Defense>(*state, target_king, attack_from, store);
00287 }
00288 const int num_captures = moves.size();
00289 {
00290 move_action::Store store(moves);
00291 Escape<Store>::template
00292 generateEscape<Defense,KING>(*state, target_king, store);
00293 }
00294 nonblock_moves = moves.size();
00295 blockable_check = ! state->inUnblockableCheck(alt(P));
00296 if ((depth <= 1) && num_captures && (nonblock_moves > 2))
00297 {
00298 if (nonblock_moves > 3)
00299 {
00300 const int block_estimate = blockable_check
00301 ? blockEstimation<Defense>(attack_from, target_position)
00302 : 0;
00303 return ProofDisproof(nonblock_moves + block_estimate, 1);
00304 }
00305 }
00306 if (moves.empty())
00307 generateBlockingWhenLiberty0<Defense>(target_king, attack_from, moves);
00308 }
00309 }
00310 const size_t initial_moves = moves.size();
00311 if (moves.empty() && !blockable_check) {
00312 if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
00313 return ProofDisproof::PawnCheckmate();
00314 SetPieces::setLeaf(*state, P, PieceStand(P,*state), proof_pieces);
00315 return ProofDisproof::NoEscape();
00316 }
00317 const bool cut_candidate = (depth <= 1)
00318 && (nonblock_moves - (state->hasPieceOnStand<GOLD>(P)
00319 || state->hasPieceOnStand<SILVER>(P)) > 4);
00320 if (cut_candidate)
00321 return ProofDisproof(nonblock_moves, 1);
00322
00323 typedef FixedDefenseHelper<P,SetPieces> helper_t;
00324 SetPieces::clear(proof_pieces);
00325 PieceStand child_proof;
00326 ProofDisproof pdp;
00327 helper_t helper(*this, depth, pdp, child_proof);
00328 int minDisproof = ProofDisproof::DISPROOF_MAX;
00329 int sumProof = 0;
00330 size_t i=0, no_promote_moves=0;
00331 start_examine:
00332 for (;i<moves.size();i++){
00333 state->makeUnmakeMove(Player2Type<alt(P)>(),moves[i],helper);
00334 const int disproof=pdp.disproof();
00335 if (disproof<minDisproof){
00336 if (disproof==0)
00337 {
00338 return pdp;
00339 }
00340 minDisproof=disproof;
00341 }
00342 sumProof+=pdp.proof();
00343 if (sumProof == 0)
00344 {
00345 SetPieces::updateMax(child_proof, proof_pieces);
00346 }
00347 else
00348 {
00349 if (i+1 < moves.size())
00350 {
00351 minDisproof = 1;
00352 if ((int)i < nonblock_moves)
00353 sumProof += nonblock_moves - (i+1);
00354 if (blockable_check)
00355 ++sumProof;
00356 }
00357 return ProofDisproof(sumProof,minDisproof);
00358 }
00359 }
00360 if (sumProof == 0)
00361 {
00362 if (blockable_check && moves.size() == initial_moves)
00363 {
00364 using namespace move_generator;
00365 using namespace move_action;
00366 const Square attack_from=attacker_piece.square();
00367 {
00368 move_action::Store store(moves);
00369 Escape<Store>::
00370 generateBlockingKing<Defense,false>(*state, target_king, attack_from,store);
00371 }
00372 if ((int)moves.size() > nonblock_moves)
00373 goto start_examine;
00374 if (moves.empty()) {
00375 assert(! (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN));
00376 SetPieces::setLeaf(*state, P, PieceStand(P,*state), proof_pieces);
00377 return ProofDisproof::NoEscape();
00378 }
00379 }
00380 if (no_promote_moves == 0)
00381 {
00382 no_promote_moves = moves.size();
00383 for (size_t i=0; i<no_promote_moves; ++i)
00384 if (moves[i].hasIgnoredUnpromote<Defense>())
00385 moves.push_back(moves[i].unpromote());
00386 if (moves.size() > no_promote_moves)
00387 goto start_examine;
00388 }
00389 if (blockable_check)
00390 SetPieces::addMonopolizedPieces(*state, P, stand(P), proof_pieces);
00391 }
00392
00393 return ProofDisproof(sumProof,minDisproof);
00394 }
00395
00396 template <osl::Player P>
00397 const osl::checkmate::ProofDisproof
00398 osl::checkmate::FixedDepthSearcher::
00399 hasEscapeByMove(Move next_move, int depth)
00400 {
00401 typedef FixedDefenseHelper<P,NoProofPieces,true> helper_t;
00402 PieceStand proof_pieces;
00403 ProofDisproof pdp;
00404 helper_t helper(*this, depth+1, pdp, proof_pieces);
00405 state->makeUnmakeMove(Player2Type<alt(P)>(),next_move,helper);
00406 return pdp;
00407 }
00408
00409 #endif
00410
00411
00412
00413