Debian Codegraph @

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

raw
1 #ifndef _CHECKMATE_SEARHCER_TCC
2 #define _CHECKMATE_SEARHCER_TCC
3
4 #include "checkmateSearcher.h"
5 #include "checkMoveList.h"
6 #include "checkHashRecord.h"
7 #include "checkmateRecorder.h"
8 #include "checkHashTable.h"
9 #include "checkMoveGenerator.h"
10 #include "checkTableUtil.h"
11 #include "osl/checkmate/libertyEstimator.h"
12 #include "osl/checkmate/pieceCost.h"
13 #include "oracleProver.h"
14 #include "oracleDisprover.h"
15 #include "sameBoardList.h"
16 #include "blockingSimulation.h"
17 #include "blockingSimulation.tcc"
18 #include "defenseSimulation.h"
19 #include "defenseSimulation.tcc"
20 #include "osl/checkmate/pawnCheckmateMoves.h"
21 #include "osl/checkmate/immediateCheckmate.h"
22 #include "osl/checkmate/fixedDepthSearcher.tcc"
23 #include "osl/apply_move/applyMoveWithPath.h"
24 #include "osl/effect_util/effectUtil.h"
25 #ifdef CHECKMATE_DEBUG
26 # include "osl/stat/ratio.h"
27 #endif
28 #include <algorithm>
29
30 // CHECKMATE_A3 or CHECKMATE_D2
31 // see kaneko's paper@gpw2005
32 #define CHECKMATE_D2
33 // #define CHECKMATE_A3
34
35 /** 証明のシミュレーションを有効に */
36 #define PROOF_SIMULATION
37 /** 反証のシミュレーションを有効に */
38 #define DISPROOF_SIMULATION
39 /** twin ノードを利用した反証のシミュレーションを有効に */
40 #define DISPROOF_TWIN_SIMULATION
41
42 /** root で未展開のままだったら打切る閾値 */
43 #define ROOT_NOEXPAND_TOL 100u
44 /** root で打切る証明数の閾値 */
45 #define ROOT_PROOF_TOL 65536ul*1024
46 /** root で打切る反証数の閾値 */
47 #define ROOT_DISPROOF_TOL 65536ul*1024
48
49 #define max_twin_simulation 16
50
51 namespace osl
52 {
53 namespace checkmate
54 {
55 template<Player P, class CheckmateSearcher>
56 struct ChildDefenseHelper
57 {
58 typedef CheckmateSearcher searcher_t;
59 searcher_t& searcher;
60 int proof_number, disproof_number;
61 CheckHashRecord *parent;
62 CheckHashRecord *record;
63 ChildDefenseHelper(searcher_t& s,int pn, int dn,
64 CheckHashRecord *p, CheckHashRecord *r)
65 : searcher(s),proof_number(pn),disproof_number(dn),
66 parent(p), record(r)
67 {
68 check_assert(record && (! record->proofDisproof().isFinal()));
69 }
70 void operator()(Square)
71 {
72 searcher.template defense<P>
73 (proof_number, disproof_number, parent, record);
74 record->isVisited = false;
75 }
76 };
77
78 template <Player P, class CheckmateSearcher>
79 struct ChildAttackHelper
80 {
81 typedef CheckmateSearcher searcher_t;
82 searcher_t& searcher;
83 int proof_number, disproof_number;
84 CheckHashRecord *parent;
85 CheckHashRecord *record;
86 ChildAttackHelper(searcher_t& s,int pn, int dn,
87 CheckHashRecord *p, CheckHashRecord *r)
88 : searcher(s),proof_number(pn),disproof_number(dn),
89 parent(p), record(r)
90 {
91 check_assert(record && (! record->proofDisproof().isFinal()));
92 }
93 void operator()(Square)
94 {
95 searcher.template attack<P>(proof_number,disproof_number,parent,record);
96 record->isVisited = false;
97 }
98 };
99
100 inline
101 unsigned int addWithSaturation(unsigned int limit,
102 unsigned int l, unsigned int r)
103 {
104 if (limit < l)
105 return limit;
106 const unsigned int sum = l+r;
107 if (limit < sum)
108 return limit;
109 // guard against overflow
110 if (sum < l)
111 return limit;
112 check_assert(r < sum);
113 return sum;
114 }
115
116 } // namespace checkmate
117 } // namespace osl
118
119 template <class Table,class HEstimator,class CostEstimator>
120 osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
121 CheckmateSearcher(Player a, Table& t, size_t limit)
122 : state(0), table(t), node_count(0), search_node_limit(0),
123 total_node_count(0), total_node_limit(limit), verbose_destructor(false),
124 attacker(a)
125 {
126 check_assert(t.getAttacker() == attacker);
127 }
128
129 template <class Table,class HEstimator,class CostEstimator>
130 osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
131 ~CheckmateSearcher()
132 {
133 clearNodeCount();
134 #ifndef MINIMAL
135 if (verbose_destructor && total_node_count)
136 CheckmateRecorder::stat("~CheckmateSearcher", attacker, table.size(),
137 total_node_count, total_node_limit);
138 #endif
139 }
140
141 template <class Table,class HEstimator,class CostEstimator>
142 inline
143 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
144 exceedNodeCount(unsigned int future_cost) const
145 {
146 return (node_count + future_cost > search_node_limit)
147 || (node_count > search_node_limit);
148 }
149
150 template <class Table,class HEstimator,class CostEstimator>
151 template<osl::Player P>
152 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
153 setUpAttackNode(CheckHashRecord *record)
154 {
155 check_assert(record->needMoveGeneration()); // 初めて訪れる局面
156 const Square op_king_position
157 =(*state).template kingSquare<PlayerTraits<P>::opponent>();
158 #ifndef NDEBUG
159 check_assert(! state->hasEffectAt(P,op_king_position)); // 逃げる手になっていなかった
160 #endif
161 const bool in_check = state->inCheck();
162 King8Info info = state->king8Info(alt(P));
163 #if ((! defined CHECKMATE_A3) || (! defined CHECKMATE_D2))
164 // fixed_searcher を使う場合は不要
165 Move check_move;
166 if (in_check)
167 record->updateBestResultInSolvedAttack(ProofDisproof::PawnCheckmate());
168 if ((! in_check)
169 && ImmediateCheckmate::hasCheckmateMove<P>(*state, info,
170 op_king_position, check_move))
171 {
172 CheckMove best_move(check_move);
173 best_move.flags.set(MoveFlags::ImmediateCheckmate);
174 record->moves.setOne(best_move, table.listProvider());
175 record->bestMove = &*(record->moves.begin());
176 PieceStand proof_pieces; // Note: ImmediateCheckmate が合駒が必要な王手を使わないことに依存
177 if (check_move.isDrop())
178 proof_pieces.add(check_move.ptype());
179 record->setProofPieces(proof_pieces);
180 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
181 return true;
182 }
183 #endif
184 bool has_pawn_checkmate=false;
185 CheckMoveGenerator<P>::generateAttack(*state, table.listProvider(),
186 record->moves, has_pawn_checkmate);
187 for (CheckMoveList::iterator p=record->moves.begin(); p!=record->moves.end(); ++p)
188 {
189 CostEstimator::setAttackCost(P, *state, *p);
190 {
191 unsigned int proof, disproof;
192 HEstimator::attackH(attacker, *state, info, p->move,
193 proof, disproof);
194 p->h_proof = proof;
195 p->h_disproof = disproof;
196 check_assert(p->h_proof && p->h_disproof);
197 }
198 }
199 if (has_pawn_checkmate)
200 record->updateBestResultInSolvedAttack(ProofDisproof::PawnCheckmate());
201 if (record->moves.empty()) // 王手をかける手がない
202 {
203 record->setDisproofPieces(DisproofPieces::leaf(*state, alt(P),
204 record->stand(alt(P))));
205 record->propagateNoCheckmate<P>((in_check || has_pawn_checkmate)
206 ? ProofDisproof::PawnCheckmate()
207 : ProofDisproof::NoCheckmate());
208 return true; // 不詰み
209 }
210 return false;
211 }
212
213 template <class Table,class HEstimator,class CostEstimator>
214 template<osl::Player P>
215 void osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
216 attack(unsigned int proof_limit, unsigned int disproof_limit,
217 CheckHashRecord *parent, CheckHashRecord *record)
218 {
219 #ifndef NDEBUG
220 CheckmateRecorder::Tracer tracer("attack ", record, key, path,
221 proof_limit, disproof_limit);
222 #endif
223 node_count++;
224
225 check_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
226 check_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
227 check_assert(record && parent && record->parent);
228 check_assert(! record->isVisited);
229 check_assert(! record->findLoop(path, table.getTwinTable()));
230 check_assert(! record->proofDisproof().isFinal());
231 check_assert((record->proof() < proof_limit));
232 check_assert((record->disproof() < disproof_limit));
233 check_assert(record->isConsistent());
234
235 record->confirmParent(parent);
236 if (record->sameBoards)
237 {
238 const CheckHashRecord *loop =
239 (*record->sameBoards).template
240 findIneffectiveDropLoop<P>(key.blackStand());
241 if (loop)
242 {
243 record->setLoopDetection(path, loop);
244 CheckmateRecorder::setLeaveReason("loop confirmation (drop)");
245 return;
246 }
247 }
248 if (record->needMoveGeneration()) // 初めて訪れる局面
249 {
250 {
251 Move check_move;
252 #ifdef CHECKMATE_A3
253 if (record->distance >= 0)
254 {
255 PieceStand proof_pieces;
256 const ProofDisproof pdp
257 = fixed_searcher.hasCheckmateMove<P>(2, check_move, proof_pieces);
258 if (pdp.isCheckmateSuccess())
259 {
260 CheckMove best_move(check_move);
261 best_move.flags.set(MoveFlags::ImmediateCheckmate);
262 record->moves.push_back(best_move);
263 record->bestMove = &*(record->moves.begin());
264 record->setProofPieces(proof_pieces);
265 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
266 return;
267 }
268 else if (pdp.isCheckmateFail())
269 {
270 // 本当はここで return したいが反証駒がない
271 }
272 else
273 {
274 assert(pdp.isUnknown());
275 record->setProofDisproof(std::max(pdp.proof(), record->proof()),
276 std::max(pdp.disproof(), record->disproof()));
277 if ((pdp.proof() >= proof_limit)
278 || (pdp.disproof() >= disproof_limit))
279 return;
280 }
281 }
282 #endif
283 }
284 if (record->needMoveGeneration() && setUpAttackNode<P>(record))
285 return;
286 }
287 #ifdef DISPROOF_SIMULATION
288 # ifdef DISPROOF_TWIN_SIMULATION
289 if (! record->twins.empty())
290 {
291 # ifdef CHECKMATE_DEBUG
292 static stat::Ratio ratio("disproof by twins (attack)");
293 # endif
294 TwinAgeEntry& age = table.allocateTwin(path);
295 check_assert(! age.hasTwinEntry());
296 for (TwinList::const_iterator p=record->twins.begin();
297 (p!=record->twins.end()) && ((size_t)age.age < std::min((unsigned int)max_twin_simulation, record->twins.size()));
298 ++p, ++age.age)
299 {
300 # ifdef CHECKMATE_DEBUG
301 ratio.add(record->proofDisproof().isFinal()|| record->findLoop(path, table.getTwinTable()));
302 # endif
303 DisproofOracleAttack<P> oracle(record, p->path);
304 assert(oracle.isValid());
305 typedef OracleDisprover<Table> disprover_t;
306 disprover_t disprover(table);
307 const bool disproved = disprover.proofNoCheckmate(*state, key,
308 path, oracle);
309 # ifdef CHECKMATE_DEBUG
310 ratio.add(disproved);
311 # endif
312 if (disproved)
313 return;
314 node_count += disprover.nodeCount()/4;
315 }
316 }
317 # endif
318 #endif
319 if (record->proofDisproof().isFinal())
320 return;
321
322 check_assert(! record->needMoveGeneration());
323 check_assert(! record->isVisited);
324 check_assert(proof_limit && disproof_limit);
325 record->isVisited = true;
326 check_assert(record->isConsistent());
327 for (;;)
328 {
329 check_assert(! record->findLoop(path, table.getTwinTable()));
330 unsigned int child_best_proof_number, child_second_best_proof_number;
331 unsigned int current_disproof_number, child_best_disproof_number;
332 CheckMove *best_move;
333 ProofDisproof bestResultInSolved;
334 #ifdef CHECK_EXTRA_LIMIT_PROOF
335 const unsigned int proof_average =
336 #endif
337 record->selectBestAttackMove(path, table.getTwinTable(),
338 child_best_proof_number,
339 child_second_best_proof_number,
340 current_disproof_number, child_best_disproof_number,
341 bestResultInSolved, best_move);
342 if (! best_move)
343 {
344 if (! bestResultInSolved.isLoopDetection())
345 {
346 record->setDisproofPieces(DisproofPieces::attack(record->moves, *state,
347 record->stand(alt(P))));
348 record->twins.clear();
349 record->propagateNoCheckmate<P>(bestResultInSolved);
350 return;
351 }
352 else
353 {
354 record->setLoopDetectionInAttack<P>(path);
355 return;
356 }
357 }
358 check_assert(best_move);
359 record->bestMove = best_move;
360
361 HashKey new_key = key.newHashWithMove(best_move->move);
362 PathEncoding new_path = PathEncoding(path, best_move->move);
363 if (! best_move->record)
364 {
365 CheckTableUtil::allocate(best_move->move, best_move->record, table,
366 new_key, new_path, record);
367 if (best_move->record->isVisited
368 || best_move->findLoop(path, table.getTwinTable())
369 || best_move->record->proofDisproof().isPawnDropFoul(best_move->move)
370 || (best_move->record->proof()
371 && ((best_move->record->proofDisproof()
372 != CheckHashRecord::initialProofDisproof())
373 || (best_move->record->distance <= record->distance))))
374 continue; // confluence or something found by using dominance, so perform selection again
375 }
376
377 check_assert(best_move->record);
378 check_assert(! best_move->record->isVisited);
379 check_assert(! best_move->findLoop(path, table.getTwinTable()));
380 check_assert(best_move->record->isConsistent());
381 if (best_move->record->proof()==0)
382 {
383 check_assert(! (best_move->record->proofDisproof()
384 .isPawnDropFoul(best_move->move)));
385 if (record->bestMove == 0)
386 record->bestMove = best_move;
387 check_assert(best_move == record->bestMove);
388 check_assert(best_move->record->hasProofPieces());
389 record->setProofPiecesAttack(P);
390 record->propagateCheckmate<P>(ProofDisproof::Checkmate());
391 CheckmateRecorder::setLeaveReason("checkmate found");
392 check_assert(record->isConsistent());
393 return; // 詰み
394 }
395
396 if (child_best_proof_number>=proof_limit
397 || current_disproof_number>=disproof_limit
398 || current_disproof_number==0
399 || exceedNodeCount(child_best_proof_number))
400 {
401 CheckmateRecorder::setLeaveReason("limit over");
402 check_assert(current_disproof_number <= ProofDisproof::DISPROOF_LIMIT);
403 check_assert(child_best_proof_number && current_disproof_number);
404 record->setProofDisproof(child_best_proof_number, current_disproof_number);
405 return;
406 }
407
408 const ProofDisproof& pdp = best_move->record->proofDisproof();
409 check_assert(! pdp.isFinal());
410 check_assert(record->useMaxInsteadOfSum
411 || (best_move->record->distance > record->distance));
412 #ifdef CHECK_EXTRA_LIMIT_PROOF
413 const unsigned int next_proof_limit
414 = addWithSaturation(proof_limit, child_second_best_proof_number, proof_average)
415 - best_move->cost_proof;
416 #else
417 const unsigned int next_proof_limit
418 = ((proof_limit <= child_second_best_proof_number)
419 ? proof_limit
420 : child_second_best_proof_number +1)
421 - best_move->cost_proof;
422 #endif
423 const unsigned int next_disproof_limit
424 = disproof_limit-current_disproof_number+child_best_disproof_number;
425 ChildDefenseHelper<P,CheckmateSearcher>
426 helper(*this, next_proof_limit, next_disproof_limit,
427 record, best_move->record);
428 CheckmateRecorder::setNextMove(&*best_move);
429
430 std::swap(key, new_key);
431 std::swap(path, new_path);
432
433 ApplyMove<P>::doUndoMove(*state, best_move->move, helper);
434
435 key = new_key;
436 path = new_path;
437
438 check_assert(best_move->record->isConfluence
439 || (best_move->record->parent == record));
440 if (record->proofDisproof().isFinal())
441 return;
442 if (pdp.proof() == 0)
443 {
444 if (! pdp.isPawnDropFoul(best_move->move))
445 {
446 if (record->bestMove == 0) // TODO: 2057:72
447 record->bestMove = best_move;
448 check_assert(best_move == record->bestMove);
449 check_assert(best_move->record->hasProofPieces());
450 record->setProofPiecesAttack(P);
451 record->propagateCheckmate<P>(ProofDisproof::Checkmate()); // Checkmate instead of NoEscape
452 CheckmateRecorder::setLeaveReason("checkmate found after move");
453 return; // 詰み
454 }
455 // 打歩詰め
456 record->addToSolvedInAttack(*best_move, ProofDisproof::PawnCheckmate());
457 record->filter.addTarget(MoveFlags::NoPromote);
458 }
459 else if (pdp.disproof() == 0) // 不詰
460 {
461 check_assert(! pdp.isLoopDetection());
462 record->addToSolvedInAttack(*best_move, pdp);
463 #ifdef DISPROOF_SIMULATION
464 assert(best_move->move.isValid());
465 if (best_move->move.isDrop())
466 {
467 const Ptype ptype = best_move->move.ptype();
468 if ((ptype == ROOK) || (ptype == BISHOP))
469 {
470 DefenseSimulation<P>::disproofDropSibling
471 (*state, key, path, record, table, *best_move, node_count);
472 }
473 }
474 #endif
475 }
476 #ifdef PAWN_CHECKMATE_SENSITIVE
477 const TwinEntry *loopDetected = best_move->findLoop(path, table.getTwinTable());
478 if (((pdp == ProofDisproof::PawnCheckmate())
479 || (loopDetected && loopDetected->move.record
480 && (loopDetected->move.record->bestResultInSolved
481 == ProofDisproof::PawnCheckmate())))
482 && PawnCheckmateMoves::hasParingNoPromote(best_move->move))
483 {
484 const Move try_nopromote = best_move->move.unpromote();
485 for (CheckMoveList::iterator p=record->moves.begin();
486 p!=record->moves.end(); ++p)
487 {
488 if (p->move == try_nopromote)
489 {
490 if (! p->record)
491 {
492 p->flags.unset(MoveFlags::NoPromote); // 一つだけ候補に加える
493 const HashKey new_key = key.newHashWithMove(try_nopromote);
494 const PathEncoding new_path(path, try_nopromote);
495 CheckTableUtil::allocate
496 (p->move, p->record, table, new_key, new_path, record);
497 #ifdef DISPROOF_SIMULATION
498 DefenseSimulation<P>::disproofNoPromote
499 (*state, new_key, new_path, record, table, *p, *best_move, node_count);
500 #endif
501 }
502 break;
503 }
504 }
505 }
506 #endif
507 }
508 }
509
510 template <class Table,class HEstimator,class CostEstimator>
511 template<osl::Player P>
512 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
513 setUpDefenseNode(CheckHashRecord *record)
514 {
515 check_assert(record->needMoveGeneration()); // 初めて訪れる局面
516 #ifdef CHECKMATE_DEBUG
517 const Square op_king_position=(*state).template kingSquare<P>();
518 // 王手をかけたら自玉が取られる状態
519 check_assert(op_king_position.isPieceStand()
520 || ! state->hasEffectAt(alt(P),op_king_position));
521 #endif
522 const unsigned int simple_king_moves =
523 CheckMoveGenerator<P>::generateEscape(*state, table.listProvider(),
524 record->moves);
525 if (record->moves.empty()) { // 逃げる手がない
526 assert(! record->proofDisproof().isFinal());
527 record->setProofPieces(ProofPieces::leaf(*state, P, record->stand(P)));
528 record->propagateCheckmate<P>(ProofDisproof::NoEscape());
529 check_assert(record->isConsistent());
530 return true; // 一手ばったり
531 }
532 if (simple_king_moves == 2)
533 record->false_branch_candidate = true;
534
535 for (CheckMoveList::iterator p=record->moves.begin();
536 p!=record->moves.end(); ++p)
537 {
538 check_assert(p->move.isNormal());
539 #ifdef CHECKMATE_D2
540 PieceStand proof_pieces;
541 Move check_move;
542 const ProofDisproof pdp
543 = fixed_searcher.hasEscapeByMove<P>(p->move, 0, check_move, proof_pieces);
544
545 if (pdp.isCheckmateSuccess())
546 {
547 CheckTableUtil::registerImmediateCheckmateInDefense<P,Table>
548 (key, path, record, *p, pdp, check_move, proof_pieces, table);
549 }
550 else if (pdp.isCheckmateFail())
551 {
552 CheckMove best_move = *p; // copy
553 record->moves.setOne(best_move, table.listProvider());
554 break;
555 }
556 else
557 {
558 p->h_proof = pdp.proof();
559 p->h_disproof = pdp.disproof();
560 }
561 #endif
562 #if (! defined CHECKMATE_D2)
563 unsigned int proof, disproof;
564 HEstimator::defenseH(attacker, *state, p->move,
565 proof, disproof);
566 p->h_proof = proof;
567 p->h_disproof = disproof;
568 #endif
569 check_assert(p->h_proof && p->h_disproof);
570 }
571
572 for (CheckMoveList::iterator p=record->moves.begin();
573 p!=record->moves.end(); ++p)
574 {
575 CostEstimator::setDefenseCost(P, *state, *p);
576 }
577 return false;
578 }
579
580 template <class Table,class HEstimator,class CostEstimator>
581 template<osl::Player P>
582 void osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
583 defense(unsigned int proof_limit, unsigned int disproof_limit,
584 CheckHashRecord *parent, CheckHashRecord *record)
585 {
586 #ifndef NDEBUG
587 CheckmateRecorder::Tracer tracer("defense", record, key, path,
588 proof_limit, disproof_limit);
589 #endif
590 node_count++;
591
592 check_assert(proof_limit < ProofDisproof::PROOF_LIMIT);
593 check_assert(disproof_limit < ProofDisproof::DISPROOF_LIMIT);
594 check_assert(record && parent && record->parent);
595 check_assert(! record->findLoop(path, table.getTwinTable()));
596 check_assert(! record->isVisited);
597 check_assert(! record->proofDisproof().isFinal());
598 check_assert(! (record->proof()>proof_limit));
599 check_assert(! (record->disproof()>disproof_limit));
600 check_assert(record->isConsistent());
601
602 record->confirmParent(parent);
603 if (record->sameBoards)
604 {
605 const CheckHashRecord *loop =
606 (*record->sameBoards).template
607 findIneffectiveDropLoop<P>(key.blackStand());
608 if (loop)
609 {
610 record->setLoopDetection(path, loop);
611 CheckmateRecorder::setLeaveReason("loop confirmation (drop)");
612 return;
613 }
614 }
615 if (record->needMoveGeneration())
616 {
617 if (setUpDefenseNode<P>(record))
618 return;
619 }
620 #ifdef DISPROOF_SIMULATION
621 # ifdef DISPROOF_TWIN_SIMULATION
622 if (! record->twins.empty())
623 {
624 # ifdef CHECKMATE_DEBUG
625 static stat::Ratio ratio("disproof by twins (defense)");
626 # endif
627 TwinAgeEntry& age = table.allocateTwin(path);
628 check_assert(! age.hasTwinEntry());
629 for (TwinList::const_iterator p=record->twins.begin();
630 (p!=record->twins.end()) && ((size_t)age.age < std::min((unsigned int)max_twin_simulation, record->twins.size()));
631 ++p, ++age.age)
632 {
633 DisproofOracleDefense<P> oracle(record, p->path);
634 assert(oracle.isValid());
635 typedef OracleDisprover<Table> disprover_t;
636 disprover_t prover(table);
637 Move escape_move;
638 const bool disproved
639 = prover.proofEscape(*state, key, path, oracle, escape_move,
640 record->parent->bestMove->move);
641 # ifdef CHECKMATE_DEBUG
642 ratio.add(disproved);
643 # endif
644 if (disproved)
645 return;
646 node_count += prover.nodeCount()/4;
647 }
648 }
649 # endif
650 #endif
651 if (record->proofDisproof().isFinal())
652 return;
653
654 check_assert(! record->needMoveGeneration());
655 check_assert(proof_limit && disproof_limit);
656 record->isVisited = true;
657 check_assert(record->isConsistent());
658 for (;;)
659 {
660 if (record->findLoop(path, table.getTwinTable()))
661 return;
662 unsigned int child_best_disproof_number, child_second_best_disproof_number;
663 unsigned int current_proof_number, child_best_proof_number;
664 ProofDisproof bestResultInSolved;
665 CheckMove *best_move;
666 #ifdef CHECK_EXTRA_LIMIT_DISPROOF
667 const unsigned int disproof_average =
668 #endif
669 record->selectBestDefenseMove(path, table.getTwinTable(),
670 child_best_disproof_number,
671 child_second_best_disproof_number,
672 current_proof_number, child_best_proof_number,
673 bestResultInSolved, best_move);
674 if (! best_move)
675 {
676 if (! record->filter.isTarget(MoveFlags::BlockingBySacrifice))
677 {
678 record->filter.addTarget(MoveFlags::BlockingBySacrifice);
679 for (CheckMoveList::iterator p=record->moves.begin();
680 p!=record->moves.end(); ++p)
681 {
682 if (p->flags.isSet(MoveFlags::BlockingBySacrifice))
683 {
684 const HashKey new_key = key.newHashWithMove(p->move);
685 const PathEncoding new_path(path, p->move);
686 if (! p->record)
687 {
688 CheckTableUtil::allocate
689 (p->move, p->record, table, new_key, new_path, record);
690 }
691 #ifdef PROOF_SIMULATION
692 if (BlockingSimulation<P>::proof(*state, new_key, new_path,
693 record, table, *p, node_count))
694 p->flags = MoveFlags::Solved;
695 else
696 #endif
697 best_move = &*p;
698 }
699 }
700 }
701 if ((! best_move) && (! record->filter.isTarget(MoveFlags::Upward)))
702 {
703 record->filter.addTarget(MoveFlags::Upward);
704 record->useMaxInsteadOfSum = true;
705 continue;
706 }
707 if (! best_move)
708 {
709 CheckmateRecorder::setLeaveReason("no unsolved moves");
710 check_assert(record->bestResultInSolved.proof() == 0);
711 if (! record->proofDisproof().isCheckmateSuccess())
712 {
713 assert(! record->proofDisproof().isFinal());
714 record->setProofPieces(ProofPieces::defense(record->moves, *state,
715 record->stand(P)));
716 record->propagateCheckmate<P>(record->bestResultInSolved);
717 }
718 return;
719 }
720 continue;
721 }
722 check_assert(best_move);
723 record->bestMove = &*best_move;
724
725 HashKey new_key = key.newHashWithMove(best_move->move);
726 PathEncoding new_path(path, best_move->move);
727 if (! best_move->record)
728 {
729 CheckTableUtil::allocate(best_move->move, best_move->record, table,
730 new_key, new_path, record);
731 if ((! best_move->record->isVisited)
732 && (! best_move->findLoop(path, table.getTwinTable()))
733 && best_move->record->disproof()
734 && ((best_move->record->proofDisproof()
735 != CheckHashRecord::initialProofDisproof())
736 || (best_move->record->distance <= record->distance)))
737 continue; // confluence or something found by using dominance, so perform selection again
738 }
739
740 check_assert(best_move->record);
741 if (best_move->record->disproof()==0)
742 {
743 record->setDisproofPiecesDefense(alt(P));
744 record->twins.clear();
745 record->propagateNoCheckmate<P>(best_move->record->proofDisproof());
746 CheckmateRecorder::setLeaveReason("no checkmate found");
747 return;
748 }
749 if (best_move->record->isVisited)
750 {
751 record->setLoopDetection(path, *best_move, best_move->record);
752 CheckmateRecorder::setLeaveReason("loop to visited");
753 return;
754 }
755 if (const TwinEntry *loop = best_move->findLoop(path, table.getTwinTable()))
756 {
757 record->setLoopDetectionTryMerge<P>
758 (path, *best_move, loop->loopTo);
759 CheckmateRecorder::setLeaveReason("loop found");
760 return;
761 }
762
763 if (child_best_disproof_number>=disproof_limit
764 || current_proof_number>=proof_limit
765 || exceedNodeCount(current_proof_number))
766 {
767 check_assert(current_proof_number);
768 check_assert(current_proof_number<=ProofDisproof::PROOF_LIMIT);
769 check_assert(child_best_disproof_number);
770 record->setProofDisproof(current_proof_number, child_best_disproof_number);
771 CheckmateRecorder::setLeaveReason("limit over");
772 return;
773 }
774 check_assert(best_move->record && (! best_move->record->isVisited)
775 && (! best_move->findLoop(path, table.getTwinTable())));
776 check_assert(! best_move->record->proofDisproof().isFinal());
777 const unsigned int next_proof_limit
778 = proof_limit-current_proof_number+child_best_proof_number;
779 #ifdef CHECK_EXTRA_LIMIT_DISPROOF
780 const unsigned int next_disproof_limit
781 = addWithSaturation(disproof_limit,
782 child_second_best_disproof_number, disproof_average)
783 - best_move->cost_disproof;
784 #else
785 const unsigned int next_disproof_limit
786 = ((disproof_limit <= child_second_best_disproof_number)
787 ? disproof_limit
788 : child_second_best_disproof_number +1)
789 - best_move->cost_disproof;
790 #endif
791 ChildAttackHelper<P,CheckmateSearcher>
792 helper(*this, next_proof_limit, next_disproof_limit,
793 record, best_move->record);
794 CheckmateRecorder::setNextMove(&*best_move);
795
796 std::swap(key, new_key);
797 std::swap(path, new_path);
798 ApplyMove<PlayerTraits<P>::opponent>
799 ::doUndoMove(*state,best_move->move,helper);
800 key = new_key;
801 path = new_path;
802
803 check_assert(best_move->record->isConfluence
804 || (best_move->record->parent == record)
805 || record->finalByDominance());
806 if (record->proofDisproof().isFinal())
807 return;
808 if (best_move->record->disproof()==0)
809 {
810 record->setDisproofPiecesDefense(alt(P));
811 record->twins.clear();
812 record->propagateNoCheckmate<P>(best_move->record->proofDisproof());
813 CheckmateRecorder::setLeaveReason("no checkmate after move");
814 return; // 不詰
815 }
816 #ifdef PROOF_SIMULATION
817 if ((best_move->record->proof()==0)
818 && best_move->move.isDrop())
819 {
820 BlockingSimulation<P>::proofSibling(*state, key, path, record, table,
821 *best_move, node_count);
822 }
823 #endif
824 }
825 }
826
827 template <class Table,class HEstimator,class CostEstimator>
828 inline
829 bool osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
830 exceedRootTolerance(unsigned int proof_number, unsigned int disproof_number,
831 unsigned int continuousNoExpandLoop)
832 {
833 return (proof_number >= ROOT_PROOF_TOL)
834 || (disproof_number >= ROOT_DISPROOF_TOL)
835 || (continuousNoExpandLoop >= ROOT_NOEXPAND_TOL);
836 }
837
838 template <class Table,class HEstimator,class CostEstimator>
839 template<osl::Player P>
840 const osl::checkmate::ProofDisproof osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
841 hasCheckmateMove(state_t& s, const HashKey& root_key,
842 const PathEncoding& root_path,
843 size_t search_node_limit, Move& best_move)
844 {
845 assert(P == attacker);
846 check_assert(s.turn()==P);
847 assert(node_count == 0);
848 state = &s;
849 path = root_path;
850 key = root_key;
851 CheckmateRecorder::setState(state);
852 fixed_searcher.setState(*state);
853
854 CheckHashRecord *record = table.find(key);
855 if (! record)
856 {
857 const PieceStand white_stand(WHITE, *state);
858
859 CheckHashRecord *root = table.root();
860 root->distance = path.getDepth()-1;
861 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
862 }
863 if (record->proofDisproof().isFinal())
864 {
865 if (record->hasBestMove())
866 best_move = record->bestMove->move;
867 check_assert((record->proof() != 0) ||
868 (record->hasBestMove() && best_move.isValid()));
869 return record->proofDisproof();
870 }
871 assert(record->parent);
872 if (record->findLoop(path, table.getTwinTable()))
873 return ProofDisproof::LoopDetection();
874 if (total_node_count>total_node_limit)
875 return ProofDisproof::Unknown();
876 search_node_limit=std::min(search_node_limit,total_node_limit-total_node_count);
877 this->search_node_limit = search_node_limit;
878 unsigned int proof_number = record->proof();
879 unsigned int disproof_number = record->disproof();
880 if ((ROOT_PROOF_TOL <= proof_number)
881 || (ROOT_DISPROOF_TOL <= disproof_number))
882 return record->proofDisproof();
883 size_t continuousNoExpandLoop = 0;
884 CheckmateRecorder::rootLog("hasCheckmateMove start", table.size(),
885 continuousNoExpandLoop);
886 // bug 96 でpathencodingを使った対策にすれば,assertに戻せる
887 if (record->isVisited)
888 return ProofDisproof::LoopDetection();
889 for (;;)
890 {
891 assert(path == root_path);
892 const size_t nodeSizeAtRoot = table.size();
893 CheckmateRecorder::setNextMove(0);
894 attack<P>(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL, record->parent, record);
895 record->isVisited = false;
896 if (record->findLoop(path, table.getTwinTable()))
897 {
898 clearNodeCount();
899 return ProofDisproof::LoopDetection();
900 }
901 proof_number=record->proof();
902 disproof_number=record->disproof();
903 check_assert(!(proof_number==0 && disproof_number==0));
904 if (proof_number == 0 || disproof_number==0
905 || exceedNodeCount(proof_number)
906 || exceedRootTolerance(proof_number, disproof_number, continuousNoExpandLoop))
907 {
908 if (record->hasBestMove())
909 {
910 best_move = record->bestMove->move;
911 check_assert((disproof_number == 0) || best_move.isValid());
912 }
913 check_assert((proof_number != 0) || (record->hasBestMove() && best_move.isValid()));
914 clearNodeCount();
915 return record->proofDisproof();
916 }
917 if (nodeSizeAtRoot == table.size())
918 ++continuousNoExpandLoop;
919 else
920 continuousNoExpandLoop = 0;
921 CheckmateRecorder::rootLog("hasCheckmateMove", table.size(), continuousNoExpandLoop);
922 }
923 }
924
925 template <class Table,class HEstimator,class CostEstimator>
926 template<osl::Player P>
927 const osl::checkmate::ProofDisproof osl::checkmate::CheckmateSearcher<Table,HEstimator,CostEstimator>::
928 hasEscapeMove(state_t& s, const HashKey& root_key, const PathEncoding& root_path,
929 size_t search_node_limit, Move last_move)
930 {
931 assert(P == attacker);
932 assert(s.turn()==alt(P));
933 assert(node_count == 0);
934 state = &s;
935 path = root_path;
936 key = root_key;
937 CheckmateRecorder::setState(state);
938 fixed_searcher.setState(*state);
939 check_assert(state->hasEffectAt(P,(*state).template kingSquare<PlayerTraits<P>::opponent>()));
940
941 CheckHashRecord *record = table.find(key);
942 if (! record)
943 {
944 const PieceStand white_stand(WHITE, *state);
945 CheckHashRecord *root = table.root();
946 root->distance = path.getDepth()-1;
947 root->moves.setOne(CheckMove(last_move), table.listProvider());
948 root->bestMove = &*root->moves.begin();
949 CheckTableUtil::allocate(record, table, key, white_stand, path, root);
950 }
951 if (record->proofDisproof().isFinal())
952 {
953 if (record->proofDisproof().isPawnDropFoul(last_move))
954 return ProofDisproof::PawnCheckmate();
955 return record->proofDisproof();
956 }
957 if (record->findLoop(path, table.getTwinTable()))
958 return ProofDisproof::LoopDetection();
959 if (total_node_count>total_node_limit)
960 return ProofDisproof::Unknown();
961 search_node_limit=std::min(search_node_limit,total_node_limit-total_node_count);
962 this->search_node_limit = search_node_limit;
963
964 unsigned int proof_number = record->proof();
965 unsigned int disproof_number = record->disproof();
966 if ((ROOT_PROOF_TOL <= proof_number)
967 || (ROOT_DISPROOF_TOL <= disproof_number))
968 return record->proofDisproof();
969 size_t continuousNoExpandLoop = 0;
970 CheckmateRecorder::rootLog("hasEscapeMove start", table.size(),
971 continuousNoExpandLoop);
972 // bug 96 でpathencodingを使った対策にすれば,assertに戻せる
973 if (record->isVisited)
974 return ProofDisproof::LoopDetection();
975 for (;;)
976 {
977 const size_t nodeSizeAtRoot = table.size();
978 check_assert(path == root_path);
979 CheckmateRecorder::setNextMove(0);
980 defense<P>(ROOT_PROOF_TOL, ROOT_DISPROOF_TOL, record->parent, record);
981 record->isVisited = false;
982 proof_number=record->proof();
983 disproof_number=record->disproof();
984 check_assert(!(proof_number==0 && disproof_number==0));
985 if (record->findLoop(path, table.getTwinTable()))
986 {
987 clearNodeCount();
988 return ProofDisproof::LoopDetection();
989 }
990 if (record->proofDisproof().isFinal()
991 || exceedNodeCount(proof_number)
992 || exceedRootTolerance(proof_number, disproof_number, continuousNoExpandLoop))
993 {
994 clearNodeCount();
995 if (record->proofDisproof().isPawnDropFoul(last_move))
996 return ProofDisproof::PawnCheckmate();
997 return record->proofDisproof();
998 }
999 if (nodeSizeAtRoot == table.size())
1000 ++continuousNoExpandLoop;
1001 else
1002 continuousNoExpandLoop = 0;
1003 CheckmateRecorder::rootLog("hasEscapeMove", table.size(), continuousNoExpandLoop);
1004 }
1005 }
1006
1007 #endif /* _CHECKMATE_SEARHCER_TCC */
1008 // ;;; Local Variables:
1009 // ;;; mode:c++
1010 // ;;; c-basic-offset:2
1011 // ;;; End: