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