00001
00002
00003 #ifndef _DUALCHECKMATESEARCHER_TCC
00004 #define _DUALCHECKMATESEARCHER_TCC
00005
00006 #include "osl/checkmate/dualCheckmateSearcher.h"
00007 #include "osl/checkmate/checkHistoryToTable.h"
00008 #include <iostream>
00009 #include <iomanip>
00010
00011 template <class Table,class HEstimator,class CostEstimator>
00012 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00013 CheckmatorWithOracle::
00014 CheckmatorWithOracle(Player attacker, size_t total_nodelimit)
00015 : table(attacker),
00016 searcher(attacker, table, total_nodelimit),
00017 #ifdef OSL_SMP
00018 table_small(attacker),
00019 searcher_small(attacker, table_small, total_nodelimit),
00020 #endif
00021 prover(table), disprover(table), num_cleared(0),
00022 shared(new SharedOracles(attacker))
00023 {
00024 }
00025
00026 template <class Table,class HEstimator,class CostEstimator>
00027 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00028 CheckmatorWithOracle::
00029 CheckmatorWithOracle(const CheckmatorWithOracle& src)
00030 : table(src.table.getAttacker()),
00031 searcher(src.table.getAttacker(), table, src.searcher.totalNodeLimit()),
00032 #ifdef OSL_SMP
00033 table_small(src.table.getAttacker()),
00034 searcher_small(src.table.getAttacker(), table_small, src.searcher_small.totalNodeLimit()),
00035 #endif
00036 prover(table), disprover(table), num_cleared(0),
00037 shared(src.shared)
00038 {
00039 }
00040
00041 template <class Table,class HEstimator,class CostEstimator>
00042 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00043 CheckmatorWithOracle::
00044 ~CheckmatorWithOracle()
00045 {
00046 }
00047
00048
00049 template <class Table,class HEstimator,class CostEstimator>
00050 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00051 DualCheckmateSearcher(size_t total_nodelimit)
00052 : black(BLACK, total_nodelimit), white(WHITE, total_nodelimit),
00053 simulation_node_count(0),
00054 proof_by_oracle(0), unknown_by_oracle(0), disproof_by_oracle(0),
00055 proof_by_search(0), unknown_by_search(0), disproof_by_search(0)
00056 {
00057 }
00058 template <class Table,class HEstimator,class CostEstimator>
00059 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00060 ~DualCheckmateSearcher()
00061 {
00062 if (get(BLACK).searcher.verbose() && (oracles(BLACK).oracles.keySize() > 1))
00063 {
00064 std::cerr << "oracle p " << std::setw(5) << proof_by_oracle
00065 << " u " << std::setw(5) << unknown_by_oracle
00066 << " d " << std::setw(5) << disproof_by_oracle << "\n";
00067 std::cerr << "search p " << std::setw(5) << proof_by_search
00068 << " u " << std::setw(5) << unknown_by_search
00069 << " d " << std::setw(5) << disproof_by_search << "\n";
00070 std::cerr << "oracles ";
00071 oracles(BLACK).showStatus();
00072 std::cerr << " ";
00073 oracles(WHITE).showStatus();
00074 std::cerr << "\n";
00075 }
00076 }
00077
00078 template <class Table,class HEstimator,class CostEstimator>
00079 template <osl::Player P>
00080 inline
00081 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00082 isWinningStateByOracle(int node_limit, NumEffectState& state,
00083 const HashKey& key, const PathEncoding& path,
00084 Move& best_move, ProofOracleAttack<P> oracle)
00085 {
00086 if (! oracle.isValid())
00087 return false;
00088
00089 if (node_limit > 120)
00090 {
00091 if (get(P).prover.proofWin(state, key, path, oracle, best_move))
00092 {
00093 ++proof_by_oracle;
00094 assert(state.isValidMove(best_move));
00095 return true;
00096 }
00097 }
00098 else
00099 {
00100 OracleProverLight<P> prover;
00101 const bool result = prover.proofWin(state, oracle, best_move);
00102 simulation_node_count += prover.nodeCount();
00103 if (result)
00104 {
00105 ++proof_by_oracle;
00106 assert(state.isValidMove(best_move));
00107 return true;
00108 }
00109 }
00110 ++unknown_by_oracle;
00111 return false;
00112 }
00113
00114 template <class Table,class HEstimator,class CostEstimator>
00115 template <osl::Player P>
00116 inline
00117 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00118 isNotWinningStateByOracle(NumEffectState& state,
00119 const HashKey& key, const PathEncoding& path,
00120 const DisproofOracleAttack<P>& oracle)
00121 {
00122 if (oracle.isValid())
00123 {
00124 if (get(P).disprover.proofNoCheckmate(state, key, path, oracle))
00125 {
00126 ++disproof_by_oracle;
00127 return true;
00128 }
00129 ++unknown_by_oracle;
00130 return false;
00131 }
00132 return false;
00133 }
00134
00135 template <class Table,class HEstimator,class CostEstimator>
00136 template <osl::Player P>
00137 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00138 isWinningStateByOracle(NumEffectState& state,
00139 const HashKey& key, const PathEncoding& path,
00140 Move& best_move, unsigned short& oracle_age,
00141 int node_limit)
00142 {
00143 assert(state.getTurn() == P);
00144 const PieceStand black_stand = key.blackStand();
00145 while (true)
00146 {
00147 #ifndef NDEBUG
00148 const unsigned int old_age = oracle_age;
00149 #endif
00150 const CheckHashRecord *guide
00151 = oracles(P).oracles.findProofOracle(state, black_stand, oracle_age);
00152 if (! guide)
00153 break;
00154 assert(old_age < oracle_age);
00155 ProofOracleAttack<P> oracle(guide);
00156 if (isWinningStateByOracle(node_limit, state, key, path, best_move, oracle))
00157 return true;
00158 if (node_limit <= 20 && oracle_age == 1)
00159 break;
00160 }
00161 return false;
00162 }
00163
00164 template <class Table,class HEstimator,class CostEstimator>
00165 template <osl::Player P>
00166 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00167 isWinningStateByOracleLastMove(NumEffectState& state,
00168 const HashKey& key, const PathEncoding& path,
00169 Move& best_move, Move last_move,
00170 unsigned short& oracle_age,
00171 int node_limit)
00172 {
00173 assert(state.getTurn() == P);
00174 if ((! last_move.isNormal()) || last_move.isDrop())
00175 return false;
00176
00177 const PieceStand black_stand = key.blackStand();
00178 const CheckHashRecord *guide
00179 = oracles(P).oracles_last_move.findOracle(state, last_move, black_stand,
00180 oracle_age);
00181 ProofOracleAttack<P> oracle(guide);
00182 return isWinningStateByOracle(node_limit,
00183 state, key, path, best_move, oracle);
00184 }
00185
00186 template <class Table,class HEstimator,class CostEstimator>
00187 template <osl::Player P>
00188 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00189 isWinningState(int node_limit, NumEffectState& state,
00190 const HashKey& key, const PathEncoding& path,
00191 Move& best_move, AttackOracleAges& oracle_age, Move last_move)
00192 {
00193 assert(state.getTurn() == P);
00194 assert(path.turn() == P);
00195 #ifdef USE_ORACLE
00196 if (isWinningStateByOracleLastMove<P>(state, key, path, best_move, last_move,
00197 oracle_age.proof_last_move,
00198 node_limit))
00199 return true;
00200 if (isWinningStateByOracle<P>(state, key, path, best_move,oracle_age.proof,
00201 node_limit))
00202 return true;
00203 if (node_limit == 0)
00204 return false;
00205 if (node_limit > disproof_oracle_record_limit)
00206 {
00207 if (isNotWinningStateByOracle<P>(state, key, path, oracle_age.disproof))
00208 return false;
00209 }
00210 #endif
00211 #ifdef OSL_SMP
00212 if (node_limit < 80+get(P).num_cleared*10)
00213 {
00214
00215 const CheckHashRecord *record
00216 = get(P).searcher.getTable().find(key);
00217 if (record && record->proofDisproof().isFinal()) {
00218 if (record->proofDisproof().isCheckmateSuccess()) {
00219 best_move = record->bestMove->move;
00220 return true;
00221 }
00222 return false;
00223 }
00224
00225 if (get(P).table_small.size() >= 200000) {
00226 if (get(P).table.size() > get(P).table_small.size())
00227 get(P).num_cleared++;
00228 std::cerr << "clear table: main " << get(P).table.size()
00229 << " sub " << get(P).table_small.size() << "\n";
00230 get(P).table_small.clear();
00231 }
00232
00233 const size_t node_count_before = searcher(P).totalNodeCount();
00234 const ProofDisproof proof_disproof
00235 = get(P).searcher_small.template hasCheckmateMove<P>
00236 (state, key, path, node_limit, best_move);
00237 const size_t node_count_after = searcher(P).totalNodeCount();
00238
00239 if (! proof_disproof.isCheckmateSuccess())
00240 return false;
00241 ++proof_by_search;
00242
00243 record = get(P).table_small.find(key);
00244 assert(record);
00245 #ifndef NDEBUG
00246 const bool win =
00247 #endif
00248 get(P).prover.proofWin(state, key, path, ProofOracleAttack<P>(record), best_move);
00249 assert(win);
00250 assert(state.isValidMove(best_move));
00251 #ifdef USE_ORACLE
00252 record = get(P).searcher.getTable().find(key);
00253 assert(record);
00254 const int node_visited = node_count_after - node_count_before;
00255 oracles(P).oracles.addProofOracle(state, record, node_visited);
00256 if (last_move.isNormal() && (! last_move.isDrop()))
00257 {
00258 oracles(P).oracles_last_move.addOracle(state, last_move, record);
00259 }
00260 #endif
00261 return true;
00262 }
00263 #endif
00264 const size_t node_count_before = searcher(P).totalNodeCount();
00265 const ProofDisproof proof_disproof
00266 = get(P).searcher.template hasCheckmateMove<P>
00267 (state, key, path, node_limit, best_move);
00268 const size_t node_count_after = searcher(P).totalNodeCount();
00269 const int node_visited = node_count_after - node_count_before;
00270 if (proof_disproof.isCheckmateSuccess())
00271 {
00272 assert(state.isValidMove(best_move));
00273 ++proof_by_search;
00274 #ifdef USE_ORACLE
00275 const CheckHashRecord *record
00276 = get(P).searcher.getTable().find(key);
00277 assert(record);
00278 oracles(P).oracles.addProofOracle(state, record, node_visited);
00279 if (last_move.isNormal() && (! last_move.isDrop()))
00280 {
00281 oracles(P).oracles_last_move.addOracle(state, last_move, record);
00282 }
00283 #endif
00284 return true;
00285 }
00286 if (proof_disproof.isCheckmateFail())
00287 {
00288 ++disproof_by_search;
00289 #ifdef USE_ORACLE
00290 if (node_visited > disproof_oracle_record_limit)
00291 {
00292 const CheckHashRecord *record
00293 = get(P).searcher.getTable().find(key);
00294 assert(record);
00295 oracles(P).oracles.addDisproofOracle(state, record, node_visited);
00296 }
00297 #endif
00298 }
00299 else
00300 {
00301 ++unknown_by_search;
00302 }
00303 return false;
00304 }
00305
00306 template <class Table,class HEstimator,class CostEstimator>
00307 template <osl::Player P>
00308 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00309 isLosingState(int node_limit, NumEffectState& state,
00310 const HashKey& key, const PathEncoding& path, Move last_move)
00311 {
00312 assert(state.getTurn() == P);
00313 assert(path.turn() == P);
00314 const Player attacker = PlayerTraits<P>::opponent;
00315 OraclePool& oracles = this->oracles(attacker).oracles_after_attack;
00316 #ifdef USE_ORACLE
00317 unsigned short castle_oracle_age=0;
00318 const PieceStand black_stand = key.blackStand();
00319 const CheckHashRecord *guide
00320 = oracles.findProofOracle(state, black_stand, castle_oracle_age);
00321 ProofOracleDefense<attacker> oracle(guide);
00322 if (oracle.isValid())
00323 {
00324 if (get(attacker).prover.proofLose(state, key,
00325 path, oracle, last_move))
00326 {
00327 ++proof_by_oracle;
00328 return true;
00329 }
00330 ++unknown_by_oracle;
00331 }
00332 #endif
00333 const size_t node_count_before = searcher(P).totalNodeCount();
00334 const size_t node_count_after = searcher(P).totalNodeCount();
00335 const ProofDisproof proof_disproof = get(attacker).searcher.template
00336 hasEscapeMove<attacker>(state, key, path,
00337 node_limit, last_move);
00338 const int node_visited = node_count_after - node_count_before;
00339 if (proof_disproof.isCheckmateSuccess())
00340 {
00341 ++proof_by_search;
00342 #ifdef USE_ORACLE
00343 const CheckHashRecord *record
00344 = get(attacker).searcher.getTable().find(key);
00345 assert(record);
00346 oracles.addProofOracle(state, record, node_visited);
00347 #endif
00348 return true;
00349 }
00350 ++unknown_by_search;
00351 return false;
00352 }
00353
00354
00355 template <class Table,class HEstimator,class CostEstimator>
00356 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00357 isWinningState(int node_limit, NumEffectState& state,
00358 const HashKey& key, const PathEncoding& path,
00359 Move& best_move, AttackOracleAges& age, Move last_move)
00360 {
00361 if (state.getTurn() == BLACK)
00362 return isWinningState<BLACK>(node_limit, state, key, path, best_move, age, last_move);
00363 else
00364 return isWinningState<WHITE>(node_limit, state, key, path, best_move, age, last_move);
00365 }
00366
00367 template <class Table,class HEstimator,class CostEstimator>
00368 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00369 isLosingState(int node_limit, NumEffectState& state,
00370 const HashKey& key, const PathEncoding& path,
00371 Move last_move)
00372 {
00373 if (state.getTurn() == BLACK)
00374 return isLosingState<BLACK>(node_limit, state, key, path, last_move);
00375 else
00376 return isLosingState<WHITE>(node_limit, state, key, path, last_move);
00377 }
00378
00379 template <class Table,class HEstimator,class CostEstimator>
00380 void osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00381 writeRootHistory(const RepetitionCounter& counter, const MoveStack& moves,
00382 const SimpleState& state, Player attack)
00383 {
00384 CheckHistoryToTable::write(getTable(attack), counter, moves,
00385 state, attack);
00386 }
00387
00388 #ifdef CHECKMATE_DEBUG
00389 template <class Table,class HEstimator,class CostEstimator>
00390 void osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
00391 undoWriteRootHistory(
00392 #ifdef CHECKMATE_DEBUG
00393 const RepetitionCounter& counter,
00394 const MoveStack&,
00395 const SimpleState&, Player attack
00396 #else
00397 const RepetitionCounter&,
00398 const MoveStack&,
00399 const SimpleState&, Player
00400 #endif
00401 )
00402 {
00403 CheckHistoryToTable::undoWrite(getTable(attack), counter, attack);
00404 }
00405 #endif
00406
00407 #endif
00408
00409
00410
00411
00412