Debian Codegraph @

old-sample/legacy-checkmate/lib/dualCheckmateSearcher.tcc

raw
1 /* dualCheckmateSearcher.tcc
2 */
3 #ifndef _DUALCHECKMATESEARCHER_TCC
4 #define _DUALCHECKMATESEARCHER_TCC
5
6 #include "dualCheckmateSearcher.h"
7 #include "checkHistoryToTable.h"
8 #include <iostream>
9 #include <iomanip>
10
11 template <class Table,class HEstimator,class CostEstimator>
12 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
13 CheckmatorWithOracle::
14 CheckmatorWithOracle(Player attacker, size_t total_nodelimit)
15 : table(attacker),
16 searcher(attacker, table, total_nodelimit),
17 #ifdef OSL_SMP
18 table_small(attacker),
19 searcher_small(attacker, table_small, total_nodelimit),
20 #endif
21 prover(table), disprover(table), num_cleared(0),
22 shared(new SharedOracles(attacker))
23 {
24 }
25
26 template <class Table,class HEstimator,class CostEstimator>
27 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
28 CheckmatorWithOracle::
29 CheckmatorWithOracle(const CheckmatorWithOracle& src)
30 : table(src.table.getAttacker()),
31 searcher(src.table.getAttacker(), table, src.searcher.totalNodeLimit()),
32 #ifdef OSL_SMP
33 table_small(src.table.getAttacker()),
34 searcher_small(src.table.getAttacker(), table_small, src.searcher_small.totalNodeLimit()),
35 #endif
36 prover(table), disprover(table), num_cleared(0),
37 shared(src.shared)
38 {
39 }
40
41 template <class Table,class HEstimator,class CostEstimator>
42 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
43 CheckmatorWithOracle::
44 ~CheckmatorWithOracle()
45 {
46 }
47
48 /* ------------------------------------------------------------------------- */
49 template <class Table,class HEstimator,class CostEstimator>
50 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
51 DualCheckmateSearcher(size_t total_nodelimit)
52 : black(BLACK, total_nodelimit), white(WHITE, total_nodelimit),
53 simulation_node_count(0),
54 proof_by_oracle(0), unknown_by_oracle(0), disproof_by_oracle(0),
55 proof_by_search(0), unknown_by_search(0), disproof_by_search(0)
56 {
57 }
58 template <class Table,class HEstimator,class CostEstimator>
59 osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
60 ~DualCheckmateSearcher()
61 {
62 if (get(BLACK).searcher.verbose() && (oracles(BLACK).oracles.keySize() > 1))
63 {
64 std::cerr << "oracle p " << std::setw(5) << proof_by_oracle
65 << " u " << std::setw(5) << unknown_by_oracle
66 << " d " << std::setw(5) << disproof_by_oracle << "\n";
67 std::cerr << "search p " << std::setw(5) << proof_by_search
68 << " u " << std::setw(5) << unknown_by_search
69 << " d " << std::setw(5) << disproof_by_search << "\n";
70 std::cerr << "oracles ";
71 oracles(BLACK).showStatus();
72 std::cerr << " ";
73 oracles(WHITE).showStatus();
74 std::cerr << "\n";
75 }
76 }
77
78 template <class Table,class HEstimator,class CostEstimator>
79 template <osl::Player P>
80 inline
81 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
82 isWinningStateByOracle(int node_limit, NumEffectState& state,
83 const HashKey& key, const PathEncoding& path,
84 Move& best_move, ProofOracleAttack<P> oracle)
85 {
86 if (! oracle.isValid())
87 return false;
88
89 if (node_limit > 120)
90 {
91 if (get(P).prover.proofWin(state, key, path, oracle, best_move))
92 {
93 ++proof_by_oracle;
94 assert(state.isValidMove(best_move));
95 return true;
96 }
97 }
98 else
99 {
100 OracleProverLight<P> prover;
101 const bool result = prover.proofWin(state, oracle, best_move);
102 simulation_node_count += prover.nodeCount();
103 if (result)
104 {
105 ++proof_by_oracle;
106 assert(state.isValidMove(best_move));
107 return true;
108 }
109 }
110 ++unknown_by_oracle;
111 return false;
112 }
113
114 template <class Table,class HEstimator,class CostEstimator>
115 template <osl::Player P>
116 inline
117 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
118 isNotWinningStateByOracle(NumEffectState& state,
119 const HashKey& key, const PathEncoding& path,
120 const DisproofOracleAttack<P>& oracle)
121 {
122 if (oracle.isValid())
123 {
124 if (get(P).disprover.proofNoCheckmate(state, key, path, oracle))
125 {
126 ++disproof_by_oracle;
127 return true;
128 }
129 ++unknown_by_oracle;
130 return false;
131 }
132 return false;
133 }
134
135 template <class Table,class HEstimator,class CostEstimator>
136 template <osl::Player P>
137 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
138 isWinningStateByOracle(NumEffectState& state,
139 const HashKey& key, const PathEncoding& path,
140 Move& best_move, unsigned short& oracle_age,
141 int node_limit)
142 {
143 assert(state.turn() == P);
144 const PieceStand black_stand = key.blackStand();
145 while (true)
146 {
147 #ifndef NDEBUG
148 const unsigned int old_age = oracle_age;
149 #endif
150 const CheckHashRecord *guide
151 = oracles(P).oracles.findProofOracle(state, black_stand, oracle_age);
152 if (! guide)
153 break;
154 assert(old_age < oracle_age);
155 ProofOracleAttack<P> oracle(guide);
156 if (isWinningStateByOracle(node_limit, state, key, path, best_move, oracle))
157 return true;
158 if (node_limit <= 20 && oracle_age == 1)
159 break;
160 }
161 return false;
162 }
163
164 template <class Table,class HEstimator,class CostEstimator>
165 template <osl::Player P>
166 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
167 isWinningStateByOracleLastMove(NumEffectState& state,
168 const HashKey& key, const PathEncoding& path,
169 Move& best_move, Move last_move,
170 unsigned short& oracle_age,
171 int node_limit)
172 {
173 assert(state.turn() == P);
174 if ((! last_move.isNormal()) || last_move.isDrop())
175 return false;
176
177 const PieceStand black_stand = key.blackStand();
178 const CheckHashRecord *guide
179 = oracles(P).oracles_last_move.findOracle(state, last_move, black_stand,
180 oracle_age);
181 ProofOracleAttack<P> oracle(guide);
182 return isWinningStateByOracle(node_limit,
183 state, key, path, best_move, oracle);
184 }
185
186 template <class Table,class HEstimator,class CostEstimator>
187 template <osl::Player P>
188 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
189 isWinningState(int node_limit, NumEffectState& state,
190 const HashKey& key, const PathEncoding& path,
191 Move& best_move, AttackOracleAges& oracle_age, Move last_move)
192 {
193 assert(state.turn() == P);
194 assert(path.turn() == P);
195 #ifdef USE_ORACLE
196 if (isWinningStateByOracleLastMove<P>(state, key, path, best_move, last_move,
197 oracle_age.proof_last_move,
198 node_limit))
199 return true;
200 if (isWinningStateByOracle<P>(state, key, path, best_move,oracle_age.proof,
201 node_limit))
202 return true;
203 if (node_limit == 0)
204 return false;
205 if (node_limit > disproof_oracle_record_limit)
206 {
207 if (isNotWinningStateByOracle<P>(state, key, path, oracle_age.disproof))
208 return false;
209 }
210 #endif
211 #ifdef OSL_SMP
212 if (node_limit < 80+get(P).num_cleared*10)
213 {
214 // check if already recorded as checkmate
215 const CheckHashRecord *record
216 = get(P).searcher.getTable().find(key);
217 if (record && record->proofDisproof().isFinal()) {
218 if (record->proofDisproof().isCheckmateSuccess()) {
219 best_move = record->bestMove->move;
220 return true;
221 }
222 return false;
223 }
224 // clear table?
225 if (get(P).table_small.size() >= 200000) {
226 if (get(P).table.size() > get(P).table_small.size())
227 get(P).num_cleared++;
228 std::cerr << "clear table: main " << get(P).table.size()
229 << " sub " << get(P).table_small.size() << "\n";
230 get(P).table_small.clear();
231 }
232 // search
233 const size_t node_count_before = searcher(P).totalNodeCount();
234 const ProofDisproof proof_disproof
235 = get(P).searcher_small.template hasCheckmateMove<P>
236 (state, key, path, node_limit, best_move);
237 const size_t node_count_after = searcher(P).totalNodeCount();
238
239 if (! proof_disproof.isCheckmateSuccess())
240 return false;
241 ++proof_by_search;
242 // migrate proof tree
243 record = get(P).table_small.find(key);
244 assert(record);
245 #ifndef NDEBUG
246 const bool win =
247 #endif
248 get(P).prover.proofWin(state, key, path, ProofOracleAttack<P>(record), best_move);
249 assert(win);
250 assert(state.isValidMove(best_move));
251 #ifdef USE_ORACLE
252 record = get(P).searcher.getTable().find(key);
253 assert(record);
254 const int node_visited = node_count_after - node_count_before;
255 oracles(P).oracles.addProofOracle(state, record, node_visited);
256 if (last_move.isNormal() && (! last_move.isDrop()))
257 {
258 oracles(P).oracles_last_move.addOracle(state, last_move, record);
259 }
260 #endif
261 return true;
262 }
263 #endif
264 const size_t node_count_before = searcher(P).totalNodeCount();
265 const ProofDisproof proof_disproof
266 = get(P).searcher.template hasCheckmateMove<P>
267 (state, key, path, node_limit, best_move);
268 const size_t node_count_after = searcher(P).totalNodeCount();
269 const int node_visited = node_count_after - node_count_before;
270 if (proof_disproof.isCheckmateSuccess())
271 {
272 assert(state.isValidMove(best_move));
273 ++proof_by_search;
274 #ifdef USE_ORACLE
275 const CheckHashRecord *record
276 = get(P).searcher.getTable().find(key);
277 assert(record);
278 oracles(P).oracles.addProofOracle(state, record, node_visited);
279 if (last_move.isNormal() && (! last_move.isDrop()))
280 {
281 oracles(P).oracles_last_move.addOracle(state, last_move, record);
282 }
283 #endif
284 return true;
285 }
286 if (proof_disproof.isCheckmateFail())
287 {
288 ++disproof_by_search;
289 #ifdef USE_ORACLE
290 if (node_visited > disproof_oracle_record_limit)
291 {
292 const CheckHashRecord *record
293 = get(P).searcher.getTable().find(key);
294 assert(record);
295 oracles(P).oracles.addDisproofOracle(state, record, node_visited);
296 }
297 #endif
298 }
299 else
300 {
301 ++unknown_by_search;
302 }
303 return false;
304 }
305
306 template <class Table,class HEstimator,class CostEstimator>
307 template <osl::Player P>
308 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
309 isLosingState(int node_limit, NumEffectState& state,
310 const HashKey& key, const PathEncoding& path, Move last_move)
311 {
312 assert(state.turn() == P);
313 assert(path.turn() == P);
314 const Player attacker = PlayerTraits<P>::opponent;
315 OraclePool& oracles = this->oracles(attacker).oracles_after_attack;
316 #ifdef USE_ORACLE
317 unsigned short castle_oracle_age=0; // dummy
318 const PieceStand black_stand = key.blackStand();
319 const CheckHashRecord *guide
320 = oracles.findProofOracle(state, black_stand, castle_oracle_age);
321 ProofOracleDefense<attacker> oracle(guide);
322 if (oracle.isValid())
323 {
324 if (get(attacker).prover.proofLose(state, key,
325 path, oracle, last_move))
326 {
327 ++proof_by_oracle;
328 return true;
329 }
330 ++unknown_by_oracle;
331 }
332 #endif
333 const size_t node_count_before = searcher(P).totalNodeCount();
334 const size_t node_count_after = searcher(P).totalNodeCount();
335 const ProofDisproof proof_disproof = get(attacker).searcher.template
336 hasEscapeMove<attacker>(state, key, path,
337 node_limit, last_move);
338 const int node_visited = node_count_after - node_count_before;
339 if (proof_disproof.isCheckmateSuccess())
340 {
341 ++proof_by_search;
342 #ifdef USE_ORACLE
343 const CheckHashRecord *record
344 = get(attacker).searcher.getTable().find(key);
345 assert(record);
346 oracles.addProofOracle(state, record, node_visited);
347 #endif
348 return true;
349 }
350 ++unknown_by_search;
351 return false;
352 }
353
354
355 template <class Table,class HEstimator,class CostEstimator>
356 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
357 isWinningState(int node_limit, NumEffectState& state,
358 const HashKey& key, const PathEncoding& path,
359 Move& best_move, AttackOracleAges& age, Move last_move)
360 {
361 if (state.turn() == BLACK)
362 return isWinningState<BLACK>(node_limit, state, key, path, best_move, age, last_move);
363 else
364 return isWinningState<WHITE>(node_limit, state, key, path, best_move, age, last_move);
365 }
366
367 template <class Table,class HEstimator,class CostEstimator>
368 bool osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
369 isLosingState(int node_limit, NumEffectState& state,
370 const HashKey& key, const PathEncoding& path,
371 Move last_move)
372 {
373 if (state.turn() == BLACK)
374 return isLosingState<BLACK>(node_limit, state, key, path, last_move);
375 else
376 return isLosingState<WHITE>(node_limit, state, key, path, last_move);
377 }
378
379 template <class Table,class HEstimator,class CostEstimator>
380 void osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
381 writeRootHistory(const RepetitionCounter& counter, const MoveStack& moves,
382 const SimpleState& state, Player attack)
383 {
384 CheckHistoryToTable::write(getTable(attack), counter, moves,
385 state, attack);
386 }
387
388 #ifdef CHECKMATE_DEBUG
389 template <class Table,class HEstimator,class CostEstimator>
390 void osl::checkmate::DualCheckmateSearcher<Table,HEstimator,CostEstimator>::
391 undoWriteRootHistory(
392 #ifdef CHECKMATE_DEBUG
393 const RepetitionCounter& counter,
394 const MoveStack&,
395 const SimpleState&, Player attack
396 #else
397 const RepetitionCounter&,
398 const MoveStack&,
399 const SimpleState&, Player
400 #endif
401 )
402 {
403 CheckHistoryToTable::undoWrite(getTable(attack), counter, attack);
404 }
405 #endif
406
407 #endif /* _DUALCHECKMATESEARCHER_TCC */
408 /* ------------------------------------------------------------------------- */
409 // ;;; Local Variables:
410 // ;;; mode:c++
411 // ;;; c-basic-offset:2
412 // ;;; End: