fixedDepthSearcher.tcc

Go to the documentation of this file.

/* fixedDepthSearcher.tcc
 */
#ifndef OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC
#define OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC
#include "osl/checkmate/fixedDepthSearcher.h"
#include "osl/checkmate/immediateCheckmate.h"
#include "osl/checkmate/proofPieces.h"
#include "osl/checkmate/proofNumberTable.h"
#include "osl/checkmate/checkMoveVector.h"
#include "osl/state/numEffectState.h"
#include "osl/container/moveVector.h"
#include "osl/move_action/store.h"
#include "osl/move_action/count.h"
#include "osl/move_generator/addEffectWithEffect.h"
#include "osl/move_generator/escape_.h"
#include "osl/move_classifier/check_.h"
#include "osl/effect_util/effectUtil.h"
#include "osl/neighboring8.h"
#include "osl/stat/ratio.h"
#include <boost/foreach.hpp>

namespace osl
{
  namespace checkmate
  {
    template<Player P, bool SetPieces>
    struct FixedAttackHelper{
      FixedDepthSearcher &searcher;
      Move move;
      int depth;
      ProofDisproof& pdp;
      PieceStand& pieces;
      FixedAttackHelper(FixedDepthSearcher &s,int d,ProofDisproof& p,
                        PieceStand& pi)
        : searcher(s), depth(d), pdp(p), pieces(pi)
      {
      }
      void operator()(Square)
      {
        assert(move.isNormal());
        pdp=searcher.defense<P,SetPieces>(move,depth-1,pieces);
      }
    };
    template<Player P, bool SetPieces, bool MayUnsafe=false>
    struct FixedDefenseHelper{
      FixedDepthSearcher &searcher;
      int depth;
      ProofDisproof& pdp;
      PieceStand& pieces;
      Move best_move;
      FixedDefenseHelper(FixedDepthSearcher &s,int d,ProofDisproof& p,
                         PieceStand& pi) 
        : searcher(s), depth(d), pdp(p), pieces(pi)
      {
      }
      void operator()(Square)
      {
        if (MayUnsafe)
          pdp=searcher.attackMayUnsafe<P,SetPieces,false>(depth-1, best_move, pieces);
        else
          pdp=searcher.attack<P,SetPieces,false>(depth-1, best_move, pieces);
      }
    };
  }
}

template <osl::Player P, bool SetPieces, bool HasGuide>
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
attackMayUnsafe(int depth, Move& best_move, PieceStand& proof_pieces)
{
  assert(state->turn() == P);
  const Square target_king
    = state->template kingSquare<PlayerTraits<P>::opponent>();
  if (state->hasEffectAt<P>(target_king))
    return ProofDisproof::NoEscape();
  return attack<P,SetPieces,HasGuide>(depth, best_move, proof_pieces);
}

template <osl::Player P, bool SetPieces, bool HasGuide>
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
attack(int depth, Move& best_move, PieceStand& proof_pieces)
{
  assert(state->turn() == P);
  assert ((! HasGuide)
          || (state->isAlmostValidMove(best_move)
              && move_classifier::
	      Check<P>::isMember(*state, best_move.ptype(), best_move.from(), 
                                 best_move.to())));
  addCount();
  const Square target_king
    = state->template kingSquare<PlayerTraits<P>::opponent>();
  assert(! state->hasEffectAt<P>(target_king));
  const King8Info info(state->Iking8Info(alt(P)));
  if ((! state->inCheck())
      && ImmediateCheckmate::hasCheckmateMove<P>(*state, info, target_king,
                                                 best_move))
  {
    if (SetPieces)
    {
      proof_pieces = PieceStand();
      if (best_move.isDrop())
        proof_pieces.add(best_move.ptype());
    }
    return ProofDisproof::Checkmate();
  }
  if (depth <= 0) 
  {
    const King8Info info_modified 
      = Edge_Table.resetEdgeFromLiberty(alt(P), target_king, info);
    return Proof_Number_Table.attackEstimation(*state, P, info_modified, target_king);
  }

  ProofDisproof pdp;
  typedef FixedAttackHelper<P,SetPieces> helper_t;
  helper_t helper(*this,depth,pdp,proof_pieces);
  int minProof = ProofDisproof::PROOF_MAX;
  int sumDisproof=0;
  if (HasGuide)
  {
    helper.move=best_move;
    state->makeUnmakeMove(Player2Type<P>(),best_move,helper);
    if (pdp.isCheckmateSuccess())
    {
      if (SetPieces)
        proof_pieces = ProofPieces::attack(proof_pieces, best_move, stand(P));
      return ProofDisproof::Checkmate();
    }
    minProof = pdp.proof();
    sumDisproof += pdp.disproof();
  }
  
  const Square targetKing
    = state->template kingSquare<PlayerTraits<P>::opponent>();
  CheckMoveVector moves;
  bool has_pawn_checkmate=false;
  {
    move_action::Store store(moves);    
    move_generator::AddEffectWithEffect<move_action::Store>::template generate<P,true>
      (*state,targetKing,store,has_pawn_checkmate);
  }
  if (moves.size()==0){
    if(has_pawn_checkmate)
      return ProofDisproof::PawnCheckmate();
    else
      return ProofDisproof::NoCheckmate();
  }
  if(has_pawn_checkmate)
    minProof=std::min(minProof,(int)ProofDisproof::PAWN_CHECK_MATE_PROOF);
  BOOST_FOREACH(Move move, moves) {
    if (HasGuide && move == best_move)
      continue;
    helper.move=move;
    state->makeUnmakeMove(Player2Type<P>(), move,helper);
    int proof=pdp.proof();
    if (proof<minProof){
      if (proof==0){
        best_move=move;
        if (SetPieces)
        {
          proof_pieces = ProofPieces::attack(proof_pieces, best_move, stand(P));
        }
        return ProofDisproof::Checkmate();
      }
      minProof=proof;
    }
    sumDisproof+=pdp.disproof();
  }
  // depth >= 3 では PawnCheckmateの際にunpromoteを試す必要あり
  return ProofDisproof(minProof,sumDisproof);
}

template <osl::Player P, bool SetPieces>
inline
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
defenseEstimation(Move last_move, PieceStand& proof_pieces,
                  Piece attacker_piece, Square target_position) const
{
  assert(state->turn() == alt(P));
  const Player Opponent = PlayerTraits<P>::opponent;
  int count=King8Info(state->Iking8Info(Opponent)).libertyCount();
  // multiple checkなので，pawn dropではない
  if (attacker_piece.isEmpty())
  {
    if (count>0){
      return ProofDisproof(count,1);
    }
    return ProofDisproof::NoEscape();
  }
  const Square attack_from=attacker_piece.square();
  count += state->countEffect(alt(P), attack_from);
  if (Neighboring8::isNeighboring8(attack_from, target_position))
    --count;
  const EffectContent effect
    = Ptype_Table.getEffect(attacker_piece.ptypeO(), 
                            attack_from, target_position);
  if (! effect.hasUnblockableEffect())
  {
    // this is better approximation than naive enumeration of blocking moves,
    // for counting of disproof number in df-pn,
    ++count;
  }

  if (count==0){
    if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
      return ProofDisproof::PawnCheckmate();
    if (SetPieces)
    {
      proof_pieces = ProofPieces::leaf(*state, P, stand(P));
    }
    return ProofDisproof::NoEscape();
  }
  return ProofDisproof(count, 1);
}

template <osl::Player Defense>
void osl::checkmate::FixedDepthSearcher::
generateBlockingWhenLiberty0(Piece defense_king, Square attack_from,
                             CheckMoveVector& moves) const
{
  assert(state->kingPiece(Defense) == defense_king);
  using namespace move_generator;
  using namespace move_action;
  CheckMoveVector all_moves;
  {
    Store store(all_moves);
    Escape<Store>::
      generateBlockingKing<Defense,false>(*state, defense_king, attack_from,store);
  }

  BOOST_FOREACH(Move move, all_moves)
  {
    if (move.isDrop())
    {
      if (! state->hasEffectAt<Defense>(move.to()))
        continue;
    }
    else
    {
      // move
      if (! Neighboring8::isNeighboring8(move.from(), defense_king.square()))
      {
        if (! state->hasMultipleEffectAt(Defense, move.to()))
          continue;
      }
    }
    moves.push_back(move);
  }
}

template <osl::Player Defense> inline
int osl::checkmate::FixedDepthSearcher::
blockEstimation(Square /*attack_from*/, Square /*defense_king*/) const
{
  // 利きのあるマスを数えようと思ったら効果がなかった
  return 1;
}

template <osl::Player P, bool SetPieces>
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
defense(Move last_move, int depth, PieceStand& proof_pieces)
{
  assert(state->turn() == alt(P));
  addCount();
  const Player Defense = PlayerTraits<P>::opponent;
  const Square attackerKing
    = state->template kingSquare<P>();
  if (attackerKing.isOnBoard() && state->hasEffectAt<Defense>(attackerKing))
    return ProofDisproof::NoCheckmate();
  const Piece target_king
    = state->template kingPiece<Defense>();
  const Square target_position = target_king.square();
  assert(state->hasEffectAt<P>(target_position));
  Piece attacker_piece;
  state->template findCheckPiece<Defense>(attacker_piece);
  if (depth <= 0)
  {
    return defenseEstimation<P, SetPieces>
      (last_move, proof_pieces, attacker_piece, target_position);
  }

  assert(depth > 0);
  CheckMoveVector moves;
  bool blockable_check = false;
  int nonblock_moves;
  {
    using namespace move_generator;
    using namespace move_action;
    if (attacker_piece.isEmpty()) {
      move_action::Store store(moves);
      Escape<Store>::template
        generateEscape<Defense,KING>(*state,target_king,store);
      nonblock_moves = moves.size();
    }
    else {
      const Square attack_from=attacker_piece.square();
      {
        move_action::Store store(moves);
        Escape<Store>::
          generateCaptureKing<Defense>(*state, target_king, attack_from, store);
      }
      const int num_captures = moves.size();
      {
        move_action::Store store(moves);
        Escape<Store>::template
          generateEscape<Defense,KING>(*state, target_king, store);
      }
      nonblock_moves = moves.size();
      blockable_check =
        ! effect_util::UnblockableCheck::isMember(alt(P), *state);
      if ((depth <= 1) && num_captures && (nonblock_moves > 2))
      {
        if (nonblock_moves > 3)
        {
          const int block_estimate = blockable_check 
            ? blockEstimation<Defense>(attack_from, target_position) 
            : 0;
          return ProofDisproof(nonblock_moves + block_estimate, 1);
        }
      } 
      if (moves.empty())
        generateBlockingWhenLiberty0<Defense>(target_king, attack_from, moves);
    }
  }
  const size_t initial_moves = moves.size();
  if (moves.empty() && !blockable_check) {
    if (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN)
      return ProofDisproof::PawnCheckmate();
    if (SetPieces)
    {
      proof_pieces = ProofPieces::leaf(*state, P, stand(P));
    }
    return ProofDisproof::NoEscape();
  }
  const bool cut_candidate = (depth <= 1)
    && (nonblock_moves - (state->hasPieceOnStand<GOLD>(P)
                          || state->hasPieceOnStand<SILVER>(P)) > 4);
  if (cut_candidate)
    return ProofDisproof(nonblock_moves, 1);

  typedef FixedDefenseHelper<P,SetPieces> helper_t;
  if (SetPieces)
    proof_pieces = PieceStand();
  PieceStand child_proof;
  ProofDisproof pdp;
  helper_t helper(*this, depth, pdp, child_proof);
  int minDisproof = ProofDisproof::DISPROOF_MAX;
  int sumProof = 0;
  size_t i=0, no_promote_moves=0;
start_examine:
  for (;i<moves.size();i++){
    state->makeUnmakeMove(Player2Type<PlayerTraits<P>::opponent>(),moves[i],helper);
    const int disproof=pdp.disproof();
    if (disproof<minDisproof){
      if (disproof==0)
      {
        return pdp;             // maybe PawnCheckmate
      }
      minDisproof=disproof;
    }
    sumProof+=pdp.proof();
    if (sumProof == 0)
    {
      if (SetPieces)
        proof_pieces = proof_pieces.max(child_proof);
    }
    else
    {
      if (i+1 < moves.size())
      {
        minDisproof = 1;
        if ((int)i < nonblock_moves)
          sumProof += nonblock_moves - (i+1);
        if (blockable_check)
          ++sumProof;
      }
      return ProofDisproof(sumProof,minDisproof);
    }
  }
  if (sumProof == 0)
  {
    if (blockable_check && moves.size() == initial_moves)
    {
      using namespace move_generator;
      using namespace move_action;
      const Square attack_from=attacker_piece.square();
      {
        move_action::Store store(moves);
        Escape<Store>::
          generateBlockingKing<Defense,false>(*state, target_king, attack_from,store);
      }
      if ((int)moves.size() > nonblock_moves)
        goto start_examine;
      if (moves.empty()) {
        assert(! (last_move.isValid() && last_move.isDrop() && last_move.ptype()==PAWN));
        if (SetPieces)
          proof_pieces = ProofPieces::leaf(*state, P, stand(P));
        return ProofDisproof::NoEscape();
      }
    }
    if (no_promote_moves == 0) 
    {
      no_promote_moves = moves.size();
      for (size_t i=0; i<no_promote_moves; ++i) 
        if (moves[i].hasIgnoredUnpromote<Defense>())
          moves.push_back(moves[i].unpromote());
      if (moves.size() > no_promote_moves)
        goto start_examine;
    }
    if (SetPieces && blockable_check)
      ProofPiecesUtil::addMonopolizedPieces(*state, P, stand(P), proof_pieces);
  }
  // depth >= 2 では unprmote も試す必要あり
  return ProofDisproof(sumProof,minDisproof);
}

template <osl::Player P>
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
hasEscapeByMove(Move next_move, int depth, Move& check_move,
                PieceStand& proof_pieces)
{
  typedef FixedDefenseHelper<P,true,true> helper_t;
  proof_pieces = PieceStand();
  ProofDisproof pdp;
  helper_t helper(*this, depth+1, pdp, proof_pieces);
  state->makeUnmakeMove(Player2Type<PlayerTraits<P>::opponent>(),next_move,helper);
  check_move = helper.best_move;
  return pdp;
}

template <osl::Player P>
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
hasEscapeByMove(Move next_move, int depth)
{
  typedef FixedDefenseHelper<P,false,true> helper_t;
  PieceStand proof_pieces;
  ProofDisproof pdp;
  helper_t helper(*this, depth+1, pdp, proof_pieces);
  state->makeUnmakeMove(Player2Type<PlayerTraits<P>::opponent>(),next_move,helper);
  return pdp;
}

template <osl::Player P>
const osl::checkmate::ProofDisproof 
osl::checkmate::FixedDepthSearcher::
hasCheckmateWithGuide(int depth, Move& guide, PieceStand& proof_pieces)
{
  assert(guide.isNormal());
  if (! guide.isDrop())
  {
    const Piece p=state->pieceOnBoard(guide.to());
    if (!p.isPtype<KING>())
      guide=guide.newCapture(p);
  }
  if (state->template isAlmostValidMove<false>(guide)
      && move_classifier::Check<P>
      ::isMember(*state, guide.ptype(), guide.from(), guide.to()))
    return attack<P,true,true>(depth, guide, proof_pieces);
  return attack<P,true,false>(depth, guide, proof_pieces);
}

#endif /* OSL_CHECKMATE_FIXED_DEPTH_SERCHER_TCC */
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End: