00001
00002
00003 #include "osl/checkmate/oraclePool.h"
00004 #include "osl/checkmate/checkHashRecord.h"
00005 #include "osl/state/simpleState.h"
00006 #include "osl/hash/hashKey.h"
00007 #include "osl/centering3x3.h"
00008 #include "osl/stl/hash_map.h"
00009 #include "osl/stl/vector.h"
00010 #ifdef OSL_SMP
00011 # include "osl/misc/lightMutex.h"
00012 #endif
00013 #ifdef CHECKMATE_DEBUG
00014 # include <iostream>
00015 #endif
00016 #include <algorithm>
00017
00018
00019 #ifdef CHECKMATE_DEBUG_EXTRA
00020 # include <sstream>
00021 #endif
00022
00023 namespace osl
00024 {
00025 namespace checkmate
00026 {
00027 struct AddOracleError
00028 {
00029 };
00030
00031 struct OracleInfo
00032 {
00033 const CheckHashRecord *record;
00034 short attack_count, defense_count;
00035 int node_count;
00036 #ifdef CHECKMATE_DEBUG_EXTRA
00037 std::string state;
00038 #endif
00039 OracleInfo() : record(0), attack_count(0), defense_count(0),
00040 node_count(0) {}
00041 OracleInfo(const CheckHashRecord *oracle, int node,
00042 const NumEffectState& state, Player defender)
00043 : record(oracle), attack_count(0), defense_count(0), node_count(node)
00044 {
00045 if (record->hasBestMove()) {
00046 const Move move = record->getBestMove()->move;
00047 attack_count = state.countEffect(alt(defender), move.to());
00048 defense_count = state.countEffect(defender, move.to());
00049 }
00050 #ifdef CHECKMATE_DEBUG_EXTRA
00051 std::ostringstream os;
00052 os << state;
00053 this->state = os.str();
00054 #endif
00055 }
00056 bool suitableInProof(const NumEffectState& state,
00057 Player defender) const
00058 {
00059 if (! record->hasBestMove())
00060 return true;
00061 const Move move = record->getBestMove()->move;
00062 if (defense_count < state.countEffect(defender, move.to()))
00063 return false;
00064 if (attack_count > state.countEffect(alt(defender), move.to()))
00065 return false;
00066 return state.isAlmostValidMove<false>(move);
00067 }
00068 };
00069
00070 typedef vector<OracleInfo> vector_t;
00071 typedef hash_map<HashKey,vector_t> hash_map_t;
00072
00073 const unsigned int max_oracles_for_key_soft_limit = 128;
00074 const unsigned int max_oracles_for_key_hard_limit = 65534;
00075 }
00076 }
00077
00082 struct osl::checkmate::OraclePool::Table
00083 {
00084 #ifdef OSL_SMP
00085 typedef osl::misc::LightMutex Mutex;
00086 mutable Mutex mutex;
00087 #endif
00088
00089 hash_map_t table;
00090 const Player defender;
00091 explicit Table(Player attacker) : defender(alt(attacker))
00092 {
00093 }
00094 ~Table()
00095 {
00096 #ifdef CHECKMATE_DEBUG
00097 size_t max_length = 0;
00098 for (hash_map_t::const_iterator p=table.begin(); p!=table.end(); ++p) {
00099 max_length = std::max(p->second.size(), max_length);
00100 }
00101 if (max_length > 10)
00102 std::cerr << "OraclePool " << max_length << "\n";
00103 #endif
00104 }
00105 template <Direction DIR>
00106 static void addKey(HashKey& key, const SimpleState& state, Position target)
00107 {
00108 const Offset offset = Board_Table.getOffsetForBlack(DIR);
00109 target += offset;
00110 const Piece piece = state.getPieceOnBoard(target);
00111 hash::Hash_Gen_Table.addHashKey(key, target, piece.ptypeO());
00112 }
00113 const HashKey makeKey(const SimpleState& state) const
00114 {
00115 const Position target_king=state.getKingPosition(defender);
00116 const Position center = Centering3x3::adjustCenter(target_king);
00117
00118 HashKey key;
00119 hash::Hash_Gen_Table.addHashKey(key, center,
00120 state.getPieceOnBoard(center).ptypeO());
00121 addKey<UL>(key, state, center);
00122 addKey<U> (key, state, center);
00123 addKey<UR>(key, state, center);
00124 addKey<L> (key, state, center);
00125 addKey<R> (key, state, center);
00126 addKey<DL>(key, state, center);
00127 addKey<D> (key, state, center);
00128 addKey<DR>(key, state, center);
00129 return key;
00130 }
00131 void dump(const NumEffectState& state, const CheckHashRecord* oracle,
00132 const vector_t& v) const;
00133 void addOracle(const NumEffectState& state, const CheckHashRecord* oracle,
00134 int node_count)
00135 {
00136 #ifdef OSL_SMP
00137 Mutex::scoped_lock lk(mutex);
00138 #endif
00139 const HashKey key = makeKey(state);
00140 vector_t& v = table[key];
00141 if (! v.empty()) {
00142
00143 const vector_t::value_type& last_one = v.back();
00144 if (last_one.record->hasBestMove()
00145 && last_one.node_count == node_count
00146 && last_one.record->getBestMove()->move == oracle->getBestMove()->move)
00147 return;
00148 }
00149 if (v.size() > 16)
00150 return;
00151 if (v.size() >= max_oracles_for_key_soft_limit)
00152 {
00153 #ifdef CHECKMATE_DEBUG
00154 dump(state, oracle, v);
00155 throw AddOracleError();
00156 #endif
00157 return;
00158 }
00159 v.push_back(OracleInfo(oracle, node_count, state, defender));
00160 }
00161 template <bool is_attack>
00162 const CheckHashRecord * find(const NumEffectState& state, PieceStand stand,
00163 unsigned short& age) const;
00164 size_t keySize() const
00165 {
00166 return table.size();
00167 }
00168 size_t totalSize() const
00169 {
00170 #ifdef OSL_SMP
00171 Mutex::scoped_lock lk(mutex);
00172 #endif
00173 size_t result = 0;
00174 for (hash_map_t::const_iterator p=table.begin(); p!=table.end(); ++p)
00175 {
00176 result += p->second.size();
00177 }
00178 return result;
00179 }
00180 };
00181
00182 #ifdef CHECKMATE_DEBUG
00183 void osl::checkmate::OraclePool::
00184 Table::dump(const NumEffectState& state, const CheckHashRecord* oracle,
00185 const vector_t& v) const
00186 {
00187 std::cerr << state;
00188 for (size_t i=0; i<v.size(); ++i) {
00189 std::cerr << "(" << i << ") " << v[i].record->getBestMove()->move
00190 << " " << v[i].defense_count << " " << v[i].node_count << "\n";
00191
00192 #ifdef CHECKMATE_DEBUG_EXTRA
00193 std::cerr << v[i].state;
00194 #endif
00195 }
00196 oracle->dump();
00197 }
00198 #endif
00199
00200 template <bool is_attack>
00201 const osl::checkmate::CheckHashRecord *
00202 osl::checkmate::OraclePool::
00203 Table::find(const NumEffectState& state, PieceStand stand,
00204 unsigned short& age) const
00205 {
00206 #ifdef OSL_SMP
00207 Mutex::scoped_lock lk(mutex);
00208 #endif
00209 const HashKey key = makeKey(state);
00210 hash_map_t::const_iterator pos = table.find(key);
00211 if (pos == table.end())
00212 return 0;
00213
00214 const vector_t& v = pos->second;
00215 assert(v.size() <= max_oracles_for_key_hard_limit);
00216 while (age<v.size())
00217 {
00218 const vector_t::value_type& record = v[age++];
00219 if (is_attack)
00220 {
00221 if (! record.suitableInProof(state, defender))
00222 continue;
00223 if (stand.hasMoreThan<BLACK>(record.record->proofPieces()))
00224 return record.record;
00225 }
00226 else
00227 {
00228 if (stand.hasMoreThan<BLACK>(record.record->disproofPieces()))
00229 return record.record;
00230 }
00231 }
00232 return 0;
00233 }
00234
00235
00236 osl::checkmate::
00237 OraclePool::OraclePool(Player attacker)
00238 : proof_oracles(new Table(attacker)), disproof_oracles(new Table(attacker))
00239 {
00240 }
00241
00242 osl::checkmate::
00243 OraclePool::~OraclePool()
00244 {
00245 }
00246
00247 void osl::checkmate::
00248 OraclePool::addProofOracle(const NumEffectState& state,
00249 const CheckHashRecord* oracle,
00250 int node_count)
00251 {
00252 assert(oracle->hasProofPieces());
00253 proof_oracles->addOracle(state, oracle, node_count);
00254 }
00255 void osl::checkmate::
00256 OraclePool::addDisproofOracle(const NumEffectState& state,
00257 const CheckHashRecord* oracle, int node_count)
00258 {
00259 assert(oracle->proofDisproof().isCheckmateFail()
00260 || (! oracle->twins.empty()));
00261 if (oracle->hasDisproofPieces())
00262 disproof_oracles->addOracle(state, oracle, node_count);
00263 }
00264
00265 const osl::checkmate::CheckHashRecord *
00266 osl::checkmate::
00267 OraclePool::findProofOracle(const NumEffectState& state, PieceStand black_stand,
00268 unsigned short& age) const
00269 {
00270 const PieceStand attack_stand
00271 = (proof_oracles->defender == WHITE) ? black_stand : PieceStand(WHITE, state);
00272 return proof_oracles->find<true>(state, attack_stand, age);
00273 }
00274
00275 const osl::checkmate::CheckHashRecord *
00276 osl::checkmate::
00277 OraclePool::findDisproofOracle(const NumEffectState& state, PieceStand black_stand,
00278 unsigned short& age) const
00279 {
00280 const PieceStand defense_stand
00281 = (disproof_oracles->defender == BLACK) ? black_stand : PieceStand(WHITE, state);
00282 return disproof_oracles->find<false>(state, defense_stand, age);
00283 }
00284
00285 size_t osl::checkmate::
00286 OraclePool::totalSize() const
00287 {
00288 return proof_oracles->totalSize() + disproof_oracles->totalSize();
00289 }
00290
00291 size_t osl::checkmate::
00292 OraclePool::keySize() const
00293 {
00294 return proof_oracles->keySize() + disproof_oracles->keySize();
00295 }
00296
00297
00298
00299
00300
00301