00001
00002
00003 #ifndef _DUALCHECKMATESEARCHER_H
00004 #define _DUALCHECKMATESEARCHER_H
00005
00006 #include "osl/checkmate/checkmateSearcher.h"
00007 #include "osl/checkmate/checkHashTable.h"
00008 #include "osl/checkmate/oraclePool.h"
00009 #include "osl/checkmate/oraclePoolLastMove.h"
00010 #include "osl/checkmate/oracleProver.h"
00011 #include "osl/checkmate/oracleProverLight.h"
00012 #include "osl/checkmate/oracleDisprover.h"
00013 #include "osl/checkmate/oracleAges.h"
00014
00015 #ifdef CHECKMATE_DEBUG
00016 # include "osl/checkmate/analyzer/checkTableAnalyzer.h"
00017 #endif
00018
00019 #include "osl/misc/carray.h"
00020
00021 #include <boost/shared_ptr.hpp>
00022 #include <cassert>
00023
00025 #define USE_ORACLE
00026
00027 namespace osl
00028 {
00029 class RepetitionCounter;
00030 namespace container
00031 {
00032 class MoveStack;
00033 }
00034 using container::MoveStack;
00035 namespace checkmate
00036 {
00037 inline size_t limitToCheckCount(int limit){
00038 assert(limit >= 0);
00039 extern CArray<size_t,32> limitToCheckCountTable;
00040 return limitToCheckCountTable[limit>>7];
00041 }
00042
00043 struct SharedOracles
00044 {
00045 OraclePool oracles;
00046 OraclePoolLastMove oracles_last_move;
00047 OraclePool oracles_after_attack;
00048 void showStatus() const;
00049
00050 SharedOracles(Player attack);
00051 };
00052
00058 template <class Table=CheckHashTable, class HEstimator=LibertyEstimator, class CostEstimator=PieceCost>
00059 class DualCheckmateSearcher
00060 {
00061 public:
00062 typedef Table table_t;
00063 typedef CheckmateSearcher<table_t, HEstimator, CostEstimator> checkmate_t;
00064 typedef OracleProver<table_t> prover_t;
00065 typedef OracleDisprover<table_t> disprover_t;
00066 struct CheckmatorWithOracle
00067 {
00068 table_t table;
00069 checkmate_t searcher;
00070 #ifdef OSL_SMP
00071 table_t table_small;
00072 checkmate_t searcher_small;
00073 #endif
00074 prover_t prover;
00075 disprover_t disprover;
00076 int num_cleared;
00077 boost::shared_ptr<SharedOracles> shared;
00078
00079 CheckmatorWithOracle(Player attacker, size_t total_nodelimit);
00081 CheckmatorWithOracle(const CheckmatorWithOracle& src);
00082 ~CheckmatorWithOracle();
00083 };
00084 private:
00085 CheckmatorWithOracle black, white;
00086 CheckmatorWithOracle& get(Player attacker)
00087 {
00088 return (attacker == BLACK) ? black : white;
00089 }
00090 const CheckmatorWithOracle& get(Player attacker) const
00091 {
00092 return (attacker == BLACK) ? black : white;
00093 }
00094 SharedOracles& oracles(Player attacker)
00095 {
00096 return *(get(attacker).shared);
00097 }
00098 static const int disproof_oracle_record_limit = 500;
00099
00100 size_t simulation_node_count;
00101 unsigned int proof_by_oracle, unknown_by_oracle, disproof_by_oracle;
00102 unsigned int proof_by_search, unknown_by_search, disproof_by_search;
00103 public:
00109 explicit DualCheckmateSearcher(size_t total_node_limit=CHECKMATE_DEFAULT_TOTAL_NODE_LIMIT);
00110
00111 virtual ~DualCheckmateSearcher();
00112 void setVerbose(bool verbose=true) {
00113 get(BLACK).searcher.setVerbose(verbose);
00114 get(WHITE).searcher.setVerbose(verbose);
00115 }
00116 private:
00117 template <Player P>
00118 bool isWinningStateByOracle(int node_limit, NumEffectState& state,
00119 const HashKey& key, const PathEncoding& path,
00120 Move& best_move, ProofOracleAttack<P> oracle);
00121 template <Player P>
00122 bool isNotWinningStateByOracle(NumEffectState& state,
00123 const HashKey& key, const PathEncoding& path,
00124 const DisproofOracleAttack<P>& oracle);
00125 public:
00129 template <Player P>
00130 bool isWinningStateByOracle(NumEffectState& state,
00131 const HashKey& key, const PathEncoding& path,
00132 Move& best_move, unsigned short& oracle_age,
00133 int node_limit=0);
00138 template <Player P>
00139 bool isNotWinningStateByOracle(NumEffectState& state,
00140 const HashKey& key, const PathEncoding& path,
00141 unsigned short& oracle_age)
00142 {
00143 assert(state.getTurn() == P);
00144 const PieceStand black_stand = key.blackStand();
00145 const CheckHashRecord *guide
00146 = oracles(P).oracles.findDisproofOracle(state, black_stand, oracle_age);
00147 DisproofOracleAttack<P> oracle(guide);
00148 return isNotWinningStateByOracle(state, key, path, oracle);
00149 }
00154 template <Player P>
00155 bool isWinningStateByOracleLastMove(NumEffectState& state,
00156 const HashKey& key, const PathEncoding& path,
00157 Move& best_move, Move last_move,
00158 unsigned short& oracle_age,
00159 int node_limit=0);
00160 bool isWinningStateByOracleLastMove(NumEffectState& state,
00161 const HashKey& key, const PathEncoding& path,
00162 Move& best_move, Move last_move,
00163 unsigned short& age)
00164 {
00165 if (state.getTurn() == BLACK)
00166 return isWinningStateByOracleLastMove<BLACK>
00167 (state, key, path, best_move, last_move, age);
00168 else
00169 return isWinningStateByOracleLastMove<WHITE>
00170 (state, key, path, best_move, last_move, age);
00171 }
00176 template <Player P>
00177 bool isWinningState(int node_limit, NumEffectState& state,
00178 const HashKey& key, const PathEncoding& path,
00179 Move& best_move, AttackOracleAges& oracle_age,
00180 Move last_move=Move::INVALID());
00181 bool isWinningState(int node_limit, NumEffectState& state,
00182 const HashKey& key, const PathEncoding& path,
00183 Move& best_move, AttackOracleAges& oracle_age,
00184 Move last_move=Move::INVALID());
00185 bool isWinningState(int node_limit, NumEffectState& state,
00186 const HashKey& key, const PathEncoding& path,
00187 Move& best_move, Move last_move=Move::INVALID())
00188 {
00189 AttackOracleAges dummy_age;
00190 return isWinningState(node_limit, state, key, path, best_move,
00191 dummy_age, last_move);
00192 }
00199 template <Player P>
00200 bool isLosingState(int node_limit, NumEffectState& state,
00201 const HashKey& key, const PathEncoding& path,
00202 Move last_move=Move::INVALID());
00203 bool isLosingState(int node_limit, NumEffectState& state,
00204 const HashKey&, const PathEncoding& path,
00205 Move last_move=Move::INVALID());
00206
00207 const checkmate_t& searcher(Player P) const { return get(P).searcher; }
00208 const table_t& getTable(Player P) const { return get(P).table; }
00209 table_t& getTable(Player P) { return get(P).table; }
00210 size_t mainNodeCount() const
00211 {
00212 return searcher(BLACK).totalNodeCount()
00213 + searcher(WHITE).totalNodeCount();
00214 }
00215 size_t totalNodeCount() const
00216 {
00217 return (simulation_node_count
00218 + searcher(BLACK).totalNodeCount()
00219 + searcher(WHITE).totalNodeCount()
00220 #ifdef OSL_SMP
00221 + get(BLACK).searcher_small.totalNodeCount()
00222 + get(WHITE).searcher_small.totalNodeCount()
00223 #endif
00224 + get(BLACK).prover.nodeCount()
00225 + get(WHITE).prover.nodeCount()
00226 + get(BLACK).disprover.nodeCount()
00227 + get(WHITE).disprover.nodeCount());
00228 }
00229
00230 void writeRootHistory(const RepetitionCounter& counter,
00231 const MoveStack& moves,
00232 const SimpleState& state, Player attack);
00233 void undoWriteRootHistory(const RepetitionCounter& counter,
00234 const MoveStack& moves,
00235 const SimpleState& state, Player attack);
00236 };
00237
00238 }
00239 using checkmate::DualCheckmateSearcher;
00240 }
00241
00242 #endif
00243
00244
00245
00246