Debian Codegraph @

old-sample/legacy-checkmate/lib/oraclePool.cc

raw
1 /* oraclePool.cc
2 */
3 #include "oraclePool.h"
4 #include "checkHashRecord.h"
5 #include "osl/state/simpleState.h"
6 #include "osl/hash/hashKey.h"
7 #include "osl/centering3x3.h"
8 #include "osl/stl/hash_map.h"
9 #include "osl/stl/vector.h"
10 #ifdef OSL_SMP
11 # include "osl/misc/lightMutex.h"
12 #endif
13 #ifdef CHECKMATE_DEBUG
14 # include <iostream>
15 #endif
16 #include <algorithm>
17
18 // #define CHECKMATE_DEBUG_EXTRA
19 #ifdef CHECKMATE_DEBUG_EXTRA
20 # include <sstream>
21 #endif
22
23 namespace osl
24 {
25 namespace checkmate
26 {
27 struct AddOracleError
28 {
29 };
30
31 struct OracleInfo
32 {
33 const CheckHashRecord *record;
34 short attack_count, defense_count;
35 int node_count;
36 #ifdef CHECKMATE_DEBUG_EXTRA
37 std::string state;
38 #endif
39 OracleInfo() : record(0), attack_count(0), defense_count(0),
40 node_count(0) {}
41 OracleInfo(const CheckHashRecord *oracle, int node,
42 const NumEffectState& state, Player defender)
43 : record(oracle), attack_count(0), defense_count(0), node_count(node)
44 {
45 if (record->hasBestMove()) {
46 const Move move = record->getBestMove()->move;
47 attack_count = state.countEffect(alt(defender), move.to());
48 defense_count = state.countEffect(defender, move.to());
49 }
50 #ifdef CHECKMATE_DEBUG_EXTRA
51 std::ostringstream os;
52 os << state;
53 this->state = os.str();
54 #endif
55 }
56 bool suitableInProof(const NumEffectState& state,
57 Player defender) const
58 {
59 if (! record->hasBestMove())
60 return true;
61 const Move move = record->getBestMove()->move;
62 if (defense_count < state.countEffect(defender, move.to()))
63 return false;
64 if (attack_count > state.countEffect(alt(defender), move.to()))
65 return false;
66 return state.isAlmostValidMove<false>(move);
67 }
68 };
69 // TODO: list の方がメモリは使うが速いはず
70 typedef vector<OracleInfo> vector_t;
71 typedef hash_map<HashKey,vector_t> hash_map_t;
72
73 const unsigned int max_oracles_for_key_soft_limit = 128;
74 const unsigned int max_oracles_for_key_hard_limit = 65534;
75 }
76 } // namespace osl
77
78 /**
79 * とりあえず8近傍で判定してみる.
80 * 持駒や25近傍などが他の候補
81 */
82 struct osl::checkmate::OraclePool::Table
83 {
84 #ifdef OSL_SMP
85 typedef osl::misc::LightMutex Mutex;
86 mutable Mutex mutex;
87 #endif
88
89 hash_map_t table;
90 const Player defender;
91 explicit Table(Player attacker) : defender(alt(attacker))
92 {
93 }
94 ~Table()
95 {
96 #ifdef CHECKMATE_DEBUG
97 size_t max_length = 0;
98 for (hash_map_t::const_iterator p=table.begin(); p!=table.end(); ++p) {
99 max_length = std::max(p->second.size(), max_length);
100 }
101 if (max_length > 10)
102 std::cerr << "OraclePool " << max_length << "\n";
103 #endif
104 }
105 template <Direction DIR>
106 static void addKey(HashKey& key, const SimpleState& state, Square target)
107 {
108 const Offset offset = Board_Table.getOffsetForBlack(DIR);
109 target += offset; // 8 近傍全て試すなら手番による符合変換は不要
110 const Piece piece = state.pieceOnBoard(target);
111 hash::Hash_Gen_Table.addHashKey(key, target, piece.ptypeO());
112 }
113 const HashKey makeKey(const SimpleState& state) const
114 {
115 const Square target_king=state.kingSquare(defender);
116 const Square center = Centering3x3::adjustCenter(target_king);
117
118 HashKey key;
119 hash::Hash_Gen_Table.addHashKey(key, center,
120 state.pieceOnBoard(center).ptypeO());
121 addKey<UL>(key, state, center);
122 addKey<U> (key, state, center);
123 addKey<UR>(key, state, center);
124 addKey<L> (key, state, center);
125 addKey<R> (key, state, center);
126 addKey<DL>(key, state, center);
127 addKey<D> (key, state, center);
128 addKey<DR>(key, state, center);
129 return key;
130 }
131 void dump(const NumEffectState& state, const CheckHashRecord* oracle,
132 const vector_t& v) const;
133 void addOracle(const NumEffectState& state, const CheckHashRecord* oracle,
134 int node_count)
135 {
136 #ifdef OSL_SMP
137 SCOPED_LOCK(lk,mutex);
138 #endif
139 const HashKey key = makeKey(state);
140 vector_t& v = table[key];
141 if (! v.empty()) {
142 // perhaps, we should reduce entries more
143 const vector_t::value_type& last_one = v.back();
144 if (last_one.record->hasBestMove()
145 && last_one.node_count == node_count
146 && last_one.record->getBestMove()->move == oracle->getBestMove()->move)
147 return;
148 }
149 if (v.size() > 16)
150 return;
151 if (v.size() >= max_oracles_for_key_soft_limit)
152 {
153 #ifdef CHECKMATE_DEBUG
154 dump(state, oracle, v);
155 throw AddOracleError();
156 #endif
157 return;
158 }
159 v.push_back(OracleInfo(oracle, node_count, state, defender));
160 }
161 template <bool is_attack>
162 const CheckHashRecord * find(const NumEffectState& state, PieceStand stand,
163 unsigned short& age) const;
164 size_t keySize() const
165 {
166 return table.size();
167 }
168 size_t totalSize() const
169 {
170 #ifdef OSL_SMP
171 SCOPED_LOCK(lk,mutex);
172 #endif
173 size_t result = 0;
174 for (hash_map_t::const_iterator p=table.begin(); p!=table.end(); ++p)
175 {
176 result += p->second.size();
177 }
178 return result;
179 }
180 };
181
182 #ifdef CHECKMATE_DEBUG
183 void osl::checkmate::OraclePool::
184 Table::dump(const NumEffectState& state, const CheckHashRecord* oracle,
185 const vector_t& v) const
186 {
187 std::cerr << state;
188 for (size_t i=0; i<v.size(); ++i) {
189 std::cerr << "(" << i << ") " << v[i].record->getBestMove()->move
190 << " " << v[i].defense_count << " " << v[i].node_count << "\n";
191 // v[i].record->dump();
192 #ifdef CHECKMATE_DEBUG_EXTRA
193 std::cerr << v[i].state;
194 #endif
195 }
196 oracle->dump();
197 }
198 #endif
199
200 template <bool is_attack>
201 const osl::checkmate::CheckHashRecord *
202 osl::checkmate::OraclePool::
203 Table::find(const NumEffectState& state, PieceStand stand,
204 unsigned short& age) const
205 {
206 #ifdef OSL_SMP
207 SCOPED_LOCK(lk,mutex);
208 #endif
209 const HashKey key = makeKey(state);
210 hash_map_t::const_iterator pos = table.find(key);
211 if (pos == table.end())
212 return 0;
213
214 const vector_t& v = pos->second;
215 assert(v.size() <= max_oracles_for_key_hard_limit);
216 while (age<v.size())
217 {
218 const vector_t::value_type& record = v[age++];
219 if (is_attack)
220 {
221 if (! record.suitableInProof(state, defender))
222 continue;
223 if (stand.hasMoreThan<BLACK>(record.record->proofPieces()))
224 return record.record;
225 }
226 else
227 {
228 if (stand.hasMoreThan<BLACK>(record.record->disproofPieces()))
229 return record.record;
230 }
231 }
232 return 0;
233 }
234 /* ------------------------------------------------------------------------- */
235
236 osl::checkmate::
237 OraclePool::OraclePool(Player attacker)
238 : proof_oracles(new Table(attacker)), disproof_oracles(new Table(attacker))
239 {
240 }
241
242 osl::checkmate::
243 OraclePool::~OraclePool()
244 {
245 }
246
247 void osl::checkmate::
248 OraclePool::addProofOracle(const NumEffectState& state,
249 const CheckHashRecord* oracle,
250 int node_count)
251 {
252 assert(oracle->hasProofPieces());
253 proof_oracles->addOracle(state, oracle, node_count);
254 }
255 void osl::checkmate::
256 OraclePool::addDisproofOracle(const NumEffectState& state,
257 const CheckHashRecord* oracle, int node_count)
258 {
259 assert(oracle->proofDisproof().isCheckmateFail()
260 || (! oracle->twins.empty()));
261 if (oracle->hasDisproofPieces()) // TODO: loop でも持たせると効率向上
262 disproof_oracles->addOracle(state, oracle, node_count);
263 }
264
265 const osl::checkmate::CheckHashRecord *
266 osl::checkmate::
267 OraclePool::findProofOracle(const NumEffectState& state, PieceStand black_stand,
268 unsigned short& age) const
269 {
270 const PieceStand attack_stand
271 = (proof_oracles->defender == WHITE) ? black_stand : PieceStand(WHITE, state);
272 return proof_oracles->find<true>(state, attack_stand, age);
273 }
274
275 const osl::checkmate::CheckHashRecord *
276 osl::checkmate::
277 OraclePool::findDisproofOracle(const NumEffectState& state, PieceStand black_stand,
278 unsigned short& age) const
279 {
280 const PieceStand defense_stand
281 = (disproof_oracles->defender == BLACK) ? black_stand : PieceStand(WHITE, state);
282 return disproof_oracles->find<false>(state, defense_stand, age);
283 }
284
285 size_t osl::checkmate::
286 OraclePool::totalSize() const
287 {
288 return proof_oracles->totalSize() + disproof_oracles->totalSize();
289 }
290
291 size_t osl::checkmate::
292 OraclePool::keySize() const
293 {
294 return proof_oracles->keySize() + disproof_oracles->keySize();
295 }
296
297 /* ------------------------------------------------------------------------- */
298 // ;;; Local Variables:
299 // ;;; mode:c++
300 // ;;; c-basic-offset:2
301 // ;;; End: