Debian Codegraph @

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

raw
1 /* oracleProver.tcc
2 */
3 #ifndef _ORACLEPROVER_TCC
4 #define _ORACLEPROVER_TCC
5
6 #include "oracleProver.h"
7 #include "checkHashTable.h"
8 #include "checkMoveGenerator.h"
9 #include "checkTableUtil.h"
10 #include "checkmateRecorder.h"
11 #include "osl/checkmate/proofPieces.h"
12 #include "osl/checkmate/immediateCheckmate.h"
13 #include "osl/checkmate/fixedDepthSearcher.tcc"
14 #include "osl/checkmate/oracleAdjust.h"
15 #include "osl/apply_move/applyMoveWithPath.h"
16 #include "osl/effect_util/effectUtil.h"
17
18
19 // 不変条件: (! record->needMoveGeneration()) の時は手生成が終了していること
20 namespace osl
21 {
22 namespace checkmate
23 {
24 /**
25 * OracleProver::defense を呼ぶhelper
26 */
27 template <Player P, class Prover>
28 struct OracleProverDefense
29 {
30 Prover *prover;
31 CheckHashRecord *record;
32 ProofOracleDefense<P> oracle;
33 OracleProverDefense(Prover *p,
34 CheckHashRecord *r, ProofOracleDefense<P> o)
35 : prover(p), record(r), oracle(o)
36 {
37 }
38 void operator()(Square)
39 {
40 (*prover).template defense<P>(record, oracle);
41 record->isVisited = false;
42 }
43 };
44
45 /**
46 * OracleProver::attack を呼ぶhelper
47 */
48 template <Player P, class Prover>
49 struct OracleProverAttack
50 {
51 Prover *prover;
52 CheckHashRecord *record;
53 ProofOracleAttack<P> oracle;
54 OracleProverAttack(Prover *p,
55 CheckHashRecord *r, ProofOracleAttack<P> o)
56 : prover(p), record(r), oracle(o)
57 {
58 }
59 void operator()(Square)
60 {
61 (*prover).template attack<P>(record, oracle);
62 record->isVisited = false;
63 }
64 };
65
66 } // namespace checkmate
67 } // namespace osl
68
69 template <class Table>
70 template <osl::Player P>
71 bool osl::checkmate::OracleProver<Table>::
72 proofWin(state_t& state, const HashKey& key, const PathEncoding& root_path,
73 ProofOracleAttack<P> oracle, Move& best_move)
74 {
75 check_assert(oracle.isValid());
76 check_assert(state.turn() == P);
77 path = root_path;
78 this->state = &state;
79 fixed_searcher.setState(state);
80 CheckmateRecorder::setState(&state);
81 this->key = key;
82
83 CheckHashRecord *record = table.find(key);
84 if (! record)
85 {
86 const PieceStand white_stand(WHITE, state);
87 CheckHashRecord *root = table.root();
88 root->distance = path.getDepth()-1;
89 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
90 }
91 if (! record->proofDisproof().isFinal()
92 && (! record->findLoop(path, table.getTwinTable())))
93 {
94 const bool visitedBeforeAttack = record->isVisited;
95 CheckmateRecorder::setNextMove(0);
96 record->isVisited = false;
97 attack<P>(record, oracle);
98 record->isVisited = visitedBeforeAttack;
99 }
100 if (record->proofDisproof().isCheckmateSuccess())
101 {
102 check_assert(record->hasBestMove());
103 best_move = record->getBestMove()->move;
104 check_assert(best_move.isValid());
105 check_assert(best_move.player() == P);
106 assert(state.isValidMove(best_move));
107 return true;
108 }
109 return false;
110 }
111
112 template <class Table>
113 template <osl::Player P>
114 bool osl::checkmate::OracleProver<Table>::
115 proofLose(state_t& state, const HashKey& key, const PathEncoding& root_path,
116 ProofOracleDefense<P> oracle, Move last_move)
117 {
118 check_assert(oracle.isValid());
119 check_assert(state.turn() == alt(P));
120 path = root_path;
121 this->state = &state;
122 fixed_searcher.setState(state);
123 CheckmateRecorder::setState(&state);
124 this->key = key;
125
126 CheckHashRecord *record = table.find(key);
127 if (! record)
128 {
129 const PieceStand white_stand(WHITE, state);
130 CheckHashRecord *root = table.root();
131 root->distance = path.getDepth()-1;
132 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
133 }
134 if (record->findLoop(path, table.getTwinTable()))
135 return false;
136 if (! record->proofDisproof().isFinal())
137 {
138 const bool visitedBeforeDefense = record->isVisited;
139 CheckmateRecorder::setNextMove(0);
140 record->isVisited = false;
141 defense<P>(record, oracle);
142 record->isVisited = visitedBeforeDefense;
143 }
144 if (record->proofDisproof().isPawnDropFoul(last_move))
145 return false;
146 return record->proofDisproof().isCheckmateSuccess();
147 }
148
149 template <class Table>
150 template <osl::Player P>
151 void osl::checkmate::OracleProver<Table>::
152 testFixedDepthAttack(CheckHashRecord *record, Move guide)
153 {
154 PieceStand proof_pieces;
155 ProofDisproof pdp;
156 if (guide.isNormal())
157 pdp = fixed_searcher.hasCheckmateWithGuide<P>(2, guide, proof_pieces);
158 else
159 pdp = fixed_searcher.hasCheckmateMove<P>(2, guide, proof_pieces);
160 if (pdp.isCheckmateSuccess())
161 {
162 CheckMove *attack = record->moves.find(guide);
163 if (attack == 0) {
164 CheckMove best_move(guide);
165 record->moves.setOne(best_move, table.listProvider());
166 attack = &*(record->moves.begin());
167 }
168 attack->flags.set(MoveFlags::ImmediateCheckmate);
169 record->bestMove = attack;
170 record->setProofPieces(proof_pieces);
171 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
172 }
173 else if (pdp.isCheckmateFail())
174 {
175 // 反証駒があれば登録できる
176 }
177 else
178 {
179 assert(pdp.isUnknown());
180 record->setProofDisproof(std::max(pdp.proof(), record->proof()),
181 std::max(pdp.disproof(), record->disproof()));
182 }
183 }
184
185 template <class Table>
186 template <osl::Player P>
187 void osl::checkmate::OracleProver<Table>::
188 testFixedDepthDefense(CheckHashRecord *record, CheckMove& next_move)
189 {
190 PieceStand proof_pieces;
191 Move check_move;
192 const ProofDisproof pdp
193 = fixed_searcher.hasEscapeByMove<P>(next_move.move, 2, check_move,
194 proof_pieces);
195 if (pdp.isCheckmateSuccess())
196 {
197 CheckTableUtil::registerImmediateCheckmateInDefense<P,Table>
198 (key, path, record, next_move, pdp, check_move, proof_pieces, table);
199 }
200 else if (pdp.isCheckmateFail())
201 {
202 // 反証駒があれば登録できる
203 }
204 else
205 {
206 assert(pdp.isUnknown());
207 record->setProofDisproof(std::max(pdp.proof(), record->proof()),
208 std::max(pdp.disproof(), record->disproof()));
209 }
210 }
211
212 template <class Table>
213 template <osl::Player P>
214 void osl::checkmate::OracleProver<Table>::
215 attack(CheckHashRecord *record, ProofOracleAttack<P> oracle)
216 {
217 ++node_count;
218 #ifndef NDEBUG
219 CheckmateRecorder::Tracer tracer("oracle attack ", record,
220 key, path, 0, 0);
221 #endif
222 check_assert(state->turn() == P);
223 check_assert(record);
224 check_assert(! record->proofDisproof().isFinal());
225 check_assert(! record->findLoop(path, table.getTwinTable()));
226 check_assert(! record->isVisited);
227 check_assert(oracle.isValid());
228 record->isVisited = true;
229 #ifdef CHECKMATE_DEBUG
230 const Square target_king_square
231 =(*state).template kingSquare<PlayerTraits<P>::opponent>();
232 check_assert(! state->hasEffectAt(P,target_king_square)); // 逃げる手になっていなかった
233 #endif
234 if (record->needMoveGeneration())
235 {
236 Move check_move;
237 if ((! state->inCheck())
238 && ImmediateCheckmate::hasCheckmateMove<P>(*state, check_move))
239 {
240 CheckMove best_move(check_move);
241 best_move.flags.set(MoveFlags::ImmediateCheckmate);
242 record->moves.setOne(best_move, table.listProvider());
243 record->bestMove = &*(record->moves.begin());
244 PieceStand proof_pieces;
245 if (check_move.isDrop())
246 proof_pieces.add(check_move.ptype());
247 record->setProofPieces(proof_pieces);
248 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
249 return;
250 }
251 if (oracle.guide && oracle.guide->hasBestMove()
252 && oracle.guide->getBestMove()->flags.isSet(MoveFlags::ImmediateCheckmate))
253 {
254 testFixedDepthAttack<P>(record, oracle.guide->getBestMove()->move);
255 return;
256 }
257 }
258 ProofOracleDefense<P> new_oracle = oracle.expandOracle();
259 if (! new_oracle.isValid()) {
260 testFixedDepthAttack<P>(record, Move::INVALID());
261 return;
262 }
263 check_assert(oracle.oracle().player() == P);
264 Move check_move = OracleAdjust::attack(*state, oracle.oracle());
265 if (! check_move.isNormal())
266 return;
267 bool has_pawn_checkmate=false;
268 if (record->moves.empty()) {
269 CheckMoveGenerator<P>::generateAttack(*state, table.listProvider(),
270 record->moves, has_pawn_checkmate);
271 if (has_pawn_checkmate)
272 record->updateBestResultInSolvedAttack(ProofDisproof::PawnCheckmate());
273 }
274
275 record->bestMove = 0;
276 for (CheckMoveList::iterator p=record->moves.begin();
277 p!=record->moves.end(); ++p)
278 {
279 if (p->move == check_move)
280 {
281 if (! p->flags.isSet(MoveFlags::Solved))
282 record->bestMove = &*p;
283 break;
284 }
285 }
286 unsigned int best_move_proof = 1;
287 unsigned int best_move_disproof = 1;
288 HashKey new_key;
289 PathEncoding new_path;
290
291 if (! record->hasBestMove()) // 合法な王手でなかった場合など
292 goto failure_end;
293
294 check_assert(record->hasBestMove()
295 && (record->getBestMove()->move == check_move));
296 new_key = key.newHashWithMove(check_move);
297 new_path = PathEncoding(path, check_move);
298
299 if (! record->getBestMove()->record)
300 {
301 CheckTableUtil::allocate(check_move, record->getBestMove()->record, table,
302 new_key, new_path, record);
303 if (record->proofDisproof().isFinal())
304 {
305 if (record->proofDisproof().isCheckmateSuccess())
306 check_assert(record->hasBestMove());
307 return;
308 }
309 }
310
311 if ((! record->getBestMove()->record->isVisited)
312 && (! record->getBestMove()->findLoop(path, table.getTwinTable())))
313 {
314 const ProofDisproof& pdp = record->getBestMove()->record->proofDisproof();
315 if (! pdp.isFinal())
316 {
317 OracleProverDefense<P,OracleProver>
318 oracle_prover(this, record->getBestMove()->record, new_oracle);
319 CheckmateRecorder::setNextMove(&*record->getBestMove());
320
321 std::swap(key, new_key);
322 std::swap(path, new_path);
323
324 ApplyMove<P>::doUndoMove(*state, check_move, oracle_prover);
325
326 key = new_key;
327 path = new_path;
328
329 if (record->proofDisproof().isFinal())
330 {
331 if (record->proofDisproof().isCheckmateSuccess())
332 check_assert(record->hasBestMove());
333 return;
334 }
335 }
336 if (pdp.isCheckmateSuccess() && (! pdp.isPawnDropFoul(check_move)))
337 {
338 if (! record->proofDisproof().isCheckmateSuccess())
339 {
340 check_assert(record->bestMove->record->hasProofPieces());
341 record->setProofPiecesAttack(P);
342 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
343 check_assert(record->isConsistent());
344 }
345 return;
346 }
347 if (! pdp.isFinal())
348 {
349 // 打歩詰か不詰は除く
350 best_move_proof = pdp.proof();
351 best_move_disproof = pdp.disproof();
352 }
353 }
354 record->bestMove = 0;
355 failure_end:
356 if (record->moves.empty())
357 {
358 record->setDisproofPieces(DisproofPieces::leaf(*state, alt(P),
359 record->stand(alt(P))));
360 record->propagateNoCheckmate<P>(has_pawn_checkmate
361 ? ProofDisproof::PawnCheckmate()
362 : ProofDisproof::NoCheckmate());
363 }
364 else
365 {
366 check_assert(best_move_proof < ProofDisproof::PROOF_LIMIT);
367 check_assert(best_move_disproof < ProofDisproof::DISPROOF_LIMIT);
368 check_assert(! record->proofDisproof().isFinal());
369 record->setProofDisproof(std::max(record->proof(),
370 best_move_proof/4),
371 std::max((size_t)record->disproof(),
372 best_move_disproof + record->moves.size()));
373 }
374 return;
375 }
376
377 template <class Table>
378 template <osl::Player P>
379 void osl::checkmate::OracleProver<Table>::
380 defense(CheckHashRecord *record, ProofOracleDefense<P> oracle)
381 {
382 ++node_count;
383 #ifndef NDEBUG
384 CheckmateRecorder::Tracer tracer("oracle defense", record,
385 key, path, 0, 0);
386 #endif
387 check_assert(oracle.isValid());
388 check_assert(record);
389 check_assert(! record->findLoop(path, table.getTwinTable()));
390 check_assert(! record->proofDisproof().isFinal());
391 check_assert(! record->isVisited);
392 record->isVisited = true;
393 #ifndef NDEBUG
394 const Square attack_king_position=(*state).template kingSquare<P>();
395 const Square defense_king_position=(*state).template kingSquare<PlayerTraits<P>::opponent>();
396 // 王手をかけたら自玉が取られる状態 or 王手になっていなかった場合
397 // 今はないはず
398 check_assert((attack_king_position.isPieceStand()
399 || ! state->hasEffectAt(alt(P),attack_king_position))
400 && state->hasEffectAt(P,defense_king_position));
401 #endif
402 if (record->needMoveGeneration())
403 {
404 CheckMoveGenerator<P>::generateEscape(*state, table.listProvider(),
405 record->moves);
406 if (record->moves.empty())
407 {
408 record->setProofPieces(ProofPieces::leaf(*state, P, record->stand(P)));
409 record->propagateCheckmate<P>(ProofDisproof::NoEscape());
410 check_assert(record->isConsistent());
411 return;
412 }
413 check_assert(record->moves.size());
414 record->setProofDisproof(std::max((size_t)record->proofDisproof().proof(),
415 record->moves.size()),
416 record->proofDisproof().disproof());
417 }
418 examine_moves:
419 int proved = 0; // このループで証明が判明した数
420 unsigned int sum_proof = 0; // 証明失敗があったかどうかにも使う
421 unsigned int min_disproof = ProofDisproof::DISPROOF_LIMIT;
422 for (CheckMoveList::iterator p=record->moves.begin();
423 p!=record->moves.end(); ++p)
424 {
425 check_assert(p->move.player() == alt(P));
426 if (! record->filter.isTarget(p->flags)) // 中合など
427 continue;
428
429 HashKey new_key = key.newHashWithMove(p->move);
430 PathEncoding new_path(path, p->move);
431 if (! p->record)
432 {
433 CheckTableUtil::allocate(p->move, p->record, table,
434 new_key, new_path, record);
435 }
436 if (p->record->isVisited)
437 {
438 record->bestMove = &*p;
439 record->setLoopDetection(path, *p, p->record);
440 return;
441 }
442 if (const TwinEntry *loop = p->findLoop(path, table.getTwinTable()))
443 {
444 record->bestMove = &*p;
445 record->setLoopDetectionTryMerge<P>(path, *p, loop->loopTo);
446 return;
447 }
448 const ProofDisproof& pdp = p->record->proofDisproof();
449 if (! pdp.isFinal())
450 {
451 ProofOracleAttack<P> new_oracle = oracle.expandOracle(p->move);
452 if (! new_oracle.isValid()) {
453 testFixedDepthDefense<P>(record, *p);
454 if (record->proofDisproof().isCheckmateSuccess())
455 continue;
456 return;
457 }
458 OracleProverAttack<P,OracleProver>
459 oracle_prover(this, p->record, new_oracle);
460 CheckmateRecorder::setNextMove(&*p);
461
462 std::swap(key, new_key);
463 std::swap(path, new_path);
464
465 ApplyMove<PlayerTraits<P>::opponent>::
466 doUndoMove(*state, p->move, oracle_prover);
467
468 key = new_key;
469 path = new_path;
470 }
471 if (! pdp.isCheckmateSuccess())
472 {
473 record->bestMove = &*p;
474 if (pdp.isCheckmateFail())
475 {
476 if (! record->proofDisproof().isCheckmateFail())
477 {
478 assert(! pdp.isLoopDetection());
479 record->setDisproofPiecesDefense(alt(P));
480 record->propagateNoCheckmate<P>(pdp);
481 }
482 return;
483 }
484 if (const TwinEntry *loop = p->findLoop(path, table.getTwinTable()))
485 {
486 record->bestMove = &*p;
487 record->setLoopDetectionTryMerge<P>(path, *p, loop->loopTo);
488 return;
489 }
490 sum_proof += pdp.proof();
491 min_disproof = std::min(min_disproof, pdp.disproof());
492 continue;
493 }
494 ++proved;
495 record->addToSolvedInDefense(*p, p->record->proofDisproof());
496 }
497 if (sum_proof && (proved == 0))
498 {
499 CheckmateRecorder::setLeaveReason("no checkmate found");
500 assert(min_disproof < ProofDisproof::DISPROOF_LIMIT);
501 assert(sum_proof < ProofDisproof::PROOF_LIMIT);
502 check_assert(! record->proofDisproof().isFinal());
503 record->setProofDisproof(std::max(record->proof(), sum_proof),
504 std::max(record->disproof(), min_disproof));
505 return;
506 }
507 if (sum_proof)
508 goto examine_moves;
509 if (! record->filter.isTarget(MoveFlags::BlockingBySacrifice))
510 {
511 record->filter.addTarget(MoveFlags::BlockingBySacrifice);
512 goto examine_moves;
513 }
514 if (! record->filter.isTarget(MoveFlags::Upward))
515 {
516 record->filter.addTarget(MoveFlags::Upward);
517 record->useMaxInsteadOfSum = true;
518 goto examine_moves;
519 }
520
521 if (! record->proofDisproof().isCheckmateSuccess())
522 {
523 record->setProofPieces(ProofPieces::defense(record->moves, *state,
524 record->stand(P)));
525 record->propagateCheckmate<P>(record->bestResultInSolved);
526 }
527 check_assert(record->proofDisproof().isCheckmateSuccess());
528 check_assert(record->isConsistent());
529 return;
530 }
531
532 template <class Table>
533 bool osl::checkmate::OracleProver<Table>::
534 proofWin(state_t& state, const PathEncoding& path,
535 const CheckHashRecord *record, Move& best_move)
536 {
537 const HashKey key(state);
538 if (state.turn() == BLACK)
539 {
540 ProofOracleAttack<BLACK> oracle(record);
541 return proofWin(state, key, path, oracle, best_move);
542 }
543 else
544 {
545 ProofOracleAttack<WHITE> oracle(record);
546 return proofWin(state, key, path, oracle, best_move);
547 }
548 }
549
550 template <class Table>
551 bool osl::checkmate::OracleProver<Table>::
552 proofLose(state_t& state, const PathEncoding& path,
553 const CheckHashRecord *record, Move last_move)
554 {
555 const HashKey key(state);
556 if (state.turn() == BLACK)
557 {
558 ProofOracleDefense<WHITE> oracle(record);
559 return proofLose(state, key, path, oracle, last_move);
560 }
561 else
562 {
563 ProofOracleDefense<BLACK> oracle(record);
564 return proofLose(state, key, path, oracle, last_move);
565 }
566 }
567
568
569 #endif /* _ORACLEPROVER_TCC */
570 // ;;; Local Variables:
571 // ;;; mode:c++
572 // ;;; c-basic-offset:2
573 // ;;; End: