Debian Codegraph @

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

raw
1 /* checkHashRecord.cc
2 */
3 #include "checkHashRecord.h"
4 #include "sameBoardList.h"
5 // TODO: PAWN_CHECKMATE_SENSITIVE, DELAY_SACRIFICE のためだけなので分離
6 #include "checkMoveGenerator.h"
7 #ifdef CHECKMATE_DEBUG
8 # include "osl/stat/ratio.h"
9 #endif
10
11 // #define TWINLIST_STAT
12
13 #ifdef TWINLIST_STAT
14 # include "osl/stat/histogram.h"
15 #endif
16 #include <iostream>
17
18 // /** 定義すると局面の優越関係を記憶し,詰/不詰だけでなく証明数を伝播させる */
19 // #define PROOF_NUMBER_PROPAGATE_BY_DOMINANCE
20
21 namespace osl
22 {
23 namespace checkmate
24 {
25 // explicit instantiation
26 template void CheckHashRecord::propagateCheckmateRecursive<BLACK>();
27 template void CheckHashRecord::propagateCheckmateRecursive<WHITE>();
28 template void CheckHashRecord::propagateNoCheckmateRecursive<BLACK>();
29 template void CheckHashRecord::propagateNoCheckmateRecursive<WHITE>();
30
31 // これを越えるようだとallocator の調整が必要
32 BOOST_STATIC_ASSERT(sizeof(CheckHashRecord) + sizeof(int)*6
33 + sizeof(void*) <= 192);
34 }
35 }
36
37 bool osl::checkmate::CheckHashRecord::
38 isConsistent() const
39 {
40 assert(! proofDisproof().isLoopDetection());
41 static int last_type = UNSET;
42 if (proof_pieces_type != UNSET)
43 {
44 if (! proof_disproof.isFinal())
45 {
46 std::cerr << "record->proof_pieces_type " << last_type
47 << " => " << (int)proof_pieces_type << "\n";
48 }
49 check_assert(proof_disproof.isFinal());
50 }
51 last_type = proof_pieces_type;
52 return true;
53 }
54
55 osl::checkmate::CheckHashRecord::
56 ~CheckHashRecord()
57 {
58 #if 0
59 // final_by_dominance が dangling pointer になっている可能性があるため
60 // さわってはいけない
61 if (final_by_dominance)
62 assert(final_by_dominance->final_by_dominance == 0);
63 #endif
64 assert(isConsistent());
65
66 #ifdef TWINLIST_STAT
67 static stat::Histogram t_hist(1,300,0,true);
68 t_hist.add(twins.size());
69 #endif
70 }
71
72 unsigned int osl::checkmate::CheckHashRecord::
73 selectBestAttackMove(const PathEncoding& path,
74 const TwinTable& table,
75 unsigned int& min_proof,
76 unsigned int& min_proof2,
77 unsigned int& sum_disproof,
78 unsigned int& disproof_of_bestchild,
79 ProofDisproof& bestResultInSolved,
80 CheckMove *& best_child)
81 {
82 #ifdef DELAY_SACRIFICE
83 if ((! filter.isTarget(MoveFlags::Sacrifice))
84 && (getProof(proofDisproof()) > 8)) // ここの数字次第で208辺りがこける
85 filter.addTarget(MoveFlags::Sacrifice);
86 #endif
87 while (true)
88 {
89 const unsigned int result =
90 selectBestAttackMoveMain(path, table, min_proof,
91 min_proof2,
92 sum_disproof,
93 disproof_of_bestchild,
94 bestResultInSolved, best_child);
95 if (! best_child)
96 {
97 #ifdef DELAY_SACRIFICE
98 if (! filter.isTarget(MoveFlags::Sacrifice))
99 {
100 filter.addTarget(MoveFlags::Sacrifice);
101 continue;
102 }
103 #endif
104 if ((this->bestResultInSolved == ProofDisproof::PawnCheckmate())
105 && (! filter.isTarget(MoveFlags::NoPromote)))
106 {
107 filter.addTarget(MoveFlags::NoPromote);
108 continue;
109 }
110 #ifdef CHECK_DELAY_UPWARDS
111 if (! filter.isTarget(MoveFlags::Upward))
112 {
113 filter.addTarget(MoveFlags::Upward);
114 useMaxInsteadOfSum = true;
115 continue;
116 }
117 #endif
118 }
119 else
120 {
121 if (best_child->record)
122 check_assert(! best_child->findLoop(path, table));
123 }
124 return result;
125 }
126 }
127
128 unsigned int osl::checkmate::CheckHashRecord::
129 selectBestAttackMoveMain(const PathEncoding& path,
130 const TwinTable& table,
131 unsigned int& min_proof,
132 unsigned int& min_proof2,
133 unsigned int& sum_disproof,
134 unsigned int& disproof_of_bestchild,
135 ProofDisproof& bestResultInSolved,
136 CheckMove*& best_child)
137 {
138 min_proof=ProofDisproof::BigProofNumber;
139 min_proof2=ProofDisproof::BigProofNumber;
140 sum_disproof=0;
141 disproof_of_bestchild=ProofDisproof::BigProofNumber;
142 bestResultInSolved = this->bestResultInSolved;
143 best_child = 0;
144 unsigned int sum_frontier_proofs = 0;
145 unsigned int num_frontiers = 0;
146
147 // TODO: targetUpwards でtemplate にして分けた方が良いか
148 const bool targetUpwards = filter.isTarget(MoveFlags::Upward);
149 for (CheckMoveList::iterator p=moves.begin(); p!=moves.end(); ++p)
150 {
151 #ifdef CHECK_DELAY_UPWARDS
152 if ((! targetUpwards) && (p->flags.isSet(MoveFlags::Upward)))
153 {
154 check_assert(p->record);
155 const ProofDisproof& pdp = p->record->proofDisproof();
156 if (pdp.proof()==0)
157 {
158 if (! pdp.isPawnDropFoul(p->move))
159 {
160 best_child = &*p;
161 return 0;
162 }
163 else
164 {
165 addToSolvedInAttack(*p, ProofDisproof::PawnCheckmate());
166 }
167 }
168 continue;
169 }
170 #endif
171 if (! filter.isTarget(p->flags))
172 continue;
173
174 unsigned int child_proof, child_disproof;
175 if (p->record)
176 {
177 #ifdef PROOF_NUMBER_PROPAGATE_BY_DOMINANCE
178 if (p->record->sameBoards && (! p->record->proofDisproof().isFinal())
179 && (! p->record->isVisited) && (! p->findLoop(path, table)))
180 p->record->sameBoards->updateSlow<false>(p->move.player(), *p->record,
181 PathEncoding(path, p->move));
182 #endif
183 const TwinEntry *loopDetected = p->findLoop(path, table);
184 if (loopDetected)
185 {
186 #ifdef PAWN_CHECKMATE_SENSITIVE
187 if ((this->bestResultInSolved != ProofDisproof::PawnCheckmate())
188 && loopDetected->move.record
189 && (loopDetected->move.record->bestResultInSolved
190 == ProofDisproof::PawnCheckmate()))
191 {
192 this->bestResultInSolved
193 = this->bestResultInSolved.betterForAttack(ProofDisproof::PawnCheckmate());
194 }
195 #endif
196 #ifdef CHECK_ABSORB_LOOP
197 if (loopDetected->loopTo == this)
198 {
199 p->flags.set(MoveFlags::Solved);
200 this->bestResultInSolved = betterForAttack(this->bestResultInSolved, NoCheckmate);
201 continue;
202 }
203 #endif
204 bestResultInSolved
205 = bestResultInSolved.betterForAttack(ProofDisproof::LoopDetection());
206 continue;
207 }
208 if (p->record->isVisited)
209 {
210 if (p->record->proofDisproof() == ProofDisproof::PawnCheckmate())
211 this->bestResultInSolved
212 = this->bestResultInSolved.betterForAttack(ProofDisproof::PawnCheckmate());
213 bestResultInSolved = bestResultInSolved.betterForAttack(ProofDisproof::LoopDetection());
214 continue;
215 }
216 if (targetUpwards && (distance > p->record->distance))
217 distance = p->record->distance;
218
219 const ProofDisproof& child_pdp = p->record->proofDisproof();
220 child_proof=child_pdp.proof();
221 child_disproof=child_pdp.disproof();
222 if (child_proof == 0)
223 {
224 if (! child_pdp.isPawnDropFoul(p->move))
225 {
226 best_child = &*p;
227 return 0;
228 }
229 else
230 {
231 addToSolvedInAttack(*p, ProofDisproof::PawnCheckmate());
232 continue;
233 }
234 }
235 else if (child_disproof == 0)
236 {
237 check_assert(! child_pdp.isLoopDetection());
238 addToSolvedInAttack(*p, child_pdp);
239 continue;
240 }
241 else {
242 #ifdef CHECK_DELAY_UPWARDS
243 if ((!targetUpwards) && (p->record->distance <= distance)) {
244 p->flags.set(MoveFlags::Upward);
245 continue;
246 }
247 child_proof += p->cost_proof;
248 child_disproof += p->cost_disproof;
249 }
250 #endif
251 }
252 else
253 {
254 child_proof = p->h_proof + p->cost_proof;
255 child_disproof = p->h_disproof + p->cost_proof;
256 sum_frontier_proofs += p->h_proof;
257 ++num_frontiers;
258 }
259
260 check_assert(child_proof != 0);
261 check_assert(child_disproof != 0);
262
263 p->addCost(child_proof,child_disproof);
264
265 if (child_proof <= min_proof2)
266 {
267 if ((child_proof < min_proof)
268 || ((child_proof == min_proof)
269 && (child_disproof < disproof_of_bestchild)))
270 {
271 best_child=&*p;
272 min_proof2=min_proof;
273 min_proof=child_proof;
274 disproof_of_bestchild=child_disproof;
275 }
276 else
277 {
278 min_proof2=child_proof;
279 }
280 sum_disproof
281 = add(child_disproof, sum_disproof);
282 continue;
283 }
284 sum_disproof
285 = add(child_disproof, sum_disproof);
286 }
287
288 bestResultInSolved
289 = bestResultInSolved.betterForAttack(this->bestResultInSolved);
290 #ifdef CHECK_EXTRA_LIMIT_PROOF
291 // (分母が)いい加減な平均
292 const unsigned int proof_average
293 = num_frontiers ? (sum_frontier_proofs / num_frontiers) : 1;
294 assert(proof_average >= 1);
295 return proof_average;
296 #else
297 return 0;
298 #endif
299 }
300
301
302 unsigned int osl::checkmate::CheckHashRecord::
303 selectBestDefenseMove(const PathEncoding& path,
304 const TwinTable& table,
305 unsigned int& min_disproof,
306 unsigned int& min_disproof2,
307 unsigned int& sum_proof,
308 unsigned int& proof_of_bestchild,
309 ProofDisproof& bestResultInSolved,
310 CheckMove *&best_child)
311 {
312 // TODO: targetUpwards でtemplate にして分けた方が良いか
313 const bool targetUpwards = filter.isTarget(MoveFlags::Upward);
314 min_disproof=ProofDisproof::BigProofNumber;
315 min_disproof2=ProofDisproof::BigProofNumber;
316 sum_proof=0;
317 proof_of_bestchild=ProofDisproof::BigProofNumber;
318 best_child = 0;
319 bestResultInSolved = this->bestResultInSolved;
320 unsigned int sum_frontier_disproofs = 0;
321 unsigned int num_frontiers=0;
322 // 柿木2005
323 unsigned int simple_king_move_proofmax = 0;
324 const CheckHashRecord *converge_candidate = 0;
325
326 for (CheckMoveList::iterator p=moves.begin(); p!=moves.end(); ++p)
327 {
328 #ifdef CHECK_DELAY_UPWARDS
329 if ((! targetUpwards) && (p->flags.isSet(MoveFlags::Upward)))
330 {
331 check_assert(p->record);
332 const ProofDisproof& pdp = p->record->proofDisproof();
333 if ((pdp.disproof()==0) || p->record->isVisited // 不詰
334 || p->findLoop(path, table))
335 {
336 best_child = &*p;
337 return 0;
338 }
339 continue;
340 }
341 #endif
342 if (! filter.isTarget(p->flags))
343 continue;
344
345 unsigned int child_proof, child_disproof;
346 if (p->record)
347 {
348 #ifdef PROOF_NUMBER_PROPAGATE_BY_DOMINANCE
349 if (p->record->sameBoards && (! p->record->proofDisproof().isFinal())
350 && (! p->record->isVisited) && (! p->findLoop(path, table)))
351 {
352 p->record->sameBoards->updateSlow<true>(alt(p->move.player()), *p->record,
353 PathEncoding(path, p->move));
354 }
355 #endif
356 if (targetUpwards && (distance > p->record->distance))
357 distance = p->record->distance;
358
359 const ProofDisproof& child_pdp = p->record->proofDisproof();
360 child_proof=child_pdp.proof();
361 child_disproof=child_pdp.disproof();
362
363 if ((child_disproof==0) || p->record->isVisited // 不詰
364 || p->findLoop(path, table))
365 {
366 best_child = &*p;
367 return 0;
368 }
369 else if (child_proof == 0) // 詰
370 {
371 addToSolvedInDefense(*p, child_pdp);
372 continue;
373 }
374 else {
375 #ifdef CHECK_DELAY_UPWARDS
376 if ((! targetUpwards) && (p->record->distance <= distance)) {
377 p->flags.set(MoveFlags::Upward);
378 continue;
379 }
380 #endif
381 child_proof += p->cost_proof;
382 child_disproof += p->cost_disproof;
383 }
384 }
385 else
386 {
387 child_proof = p->h_proof + p->cost_proof;
388 child_disproof = p->h_disproof + p->cost_disproof;
389 sum_frontier_disproofs += p->h_disproof;
390 ++num_frontiers;
391 }
392 assert(child_proof);
393 assert(child_disproof);
394
395 p->addCost(child_proof, child_disproof);
396
397 if ((child_disproof < min_disproof)
398 || ((child_disproof == min_disproof)
399 && (child_proof < proof_of_bestchild)))
400 {
401 best_child = &*p;
402
403 min_disproof2=min_disproof;
404 min_disproof=child_disproof;
405 proof_of_bestchild=child_proof;
406 }
407 else if (child_disproof < min_disproof2)
408 {
409 min_disproof2=child_disproof;
410 }
411 if (false_branch_candidate && p->record && p->move.ptype() == KING
412 && p->move.capturePtype() == PTYPE_EMPTY) {
413 if (! false_branch
414 && p->record->hasBestMove() && p->record->getBestMove()->record) {
415 if (converge_candidate) {
416 if (converge_candidate == p->record->getBestMove()->record)
417 false_branch = true;
418 }
419 else {
420 converge_candidate = p->record->getBestMove()->record;
421 }
422 }
423 if (false_branch) {
424 if (simple_king_move_proofmax < child_proof)
425 simple_king_move_proofmax = child_proof;
426 }
427 else {
428 simple_king_move_proofmax = add(simple_king_move_proofmax, child_proof);
429 }
430 }
431 else {
432 sum_proof = add(sum_proof, child_proof);
433 }
434 }
435 sum_proof += simple_king_move_proofmax;
436 bestResultInSolved
437 = bestResultInSolved.betterForDefense(this->bestResultInSolved);
438 #ifdef CHECK_EXTRA_LIMIT_DISPROOF
439 const unsigned int disproof_average
440 = num_frontiers ? (sum_frontier_disproofs / num_frontiers) : 1;
441 assert(disproof_average >= 1);
442 return disproof_average;
443 #else
444 return 0;
445 #endif
446 }
447
448 template <osl::Player Attacker>
449 void osl::checkmate::CheckHashRecord::propagateCheckmateRecursive()
450 {
451 assert(proof_pieces_type == PROOF);
452 #ifdef CHECKMATE_DEBUG
453 static stat::Ratio ratio("propagateCheckmate");
454 if ((! moves.empty()) && (moves.begin()->move.player() == Attacker))
455 {
456 // or-node
457 check_assert(hasBestMove());
458 }
459 #endif
460 check_assert(final_by_dominance == 0);
461 for (SameBoardList::iterator p=sameBoards->begin(); p!=sameBoards->end(); ++p)
462 {
463 if (p->stand(BLACK) == black_stand)
464 continue;
465 const PieceStand& attack_stand
466 = (Attacker == BLACK) ? p->black_stand : p->white_stand;
467 if (attack_stand.template hasMoreThan<BLACK>(proofPieces()))
468 {
469 #ifdef CHECKMATE_DEBUG
470 ratio.add(p->proof());
471 #endif
472 check_assert(p->disproof());
473 if (p->proof())
474 {
475 check_assert(p->final_by_dominance == 0);
476 p->setProofPieces(proofPieces());
477 p->setFinalByDominance(this);
478 p->bestMove = bestMove;
479 p->proof_disproof = proofDisproof();
480 check_assert(p->isConsistent());
481 }
482 }
483 }
484 }
485
486 template <osl::Player Attacker>
487 void osl::checkmate::CheckHashRecord::propagateNoCheckmateRecursive()
488 {
489 #ifdef CHECKMATE_DEBUG
490 static stat::Ratio ratio("propagateNoCheckmate");
491 #endif
492 check_assert(final_by_dominance == 0);
493 check_assert(hasDisproofPieces());
494 check_assert(! proofDisproof().isLoopDetection());
495 for (SameBoardList::iterator p=sameBoards->begin(); p!=sameBoards->end(); ++p)
496 {
497 if (p->stand(BLACK) == black_stand)
498 continue;
499 const PieceStand& defense_stand
500 = (Attacker == BLACK) ? p->white_stand : p->black_stand;
501 if (defense_stand.template hasMoreThan<BLACK>(disproofPieces()))
502 {
503 #ifdef CHECKMATE_DEBUG
504 ratio.add(p->disproof());
505 #endif
506 check_assert(p->proof()
507 || (p->dump(), dump(), std::cerr << Attacker << "\n", 0));
508 if (p->disproof())
509 {
510 check_assert((p->final_by_dominance == 0) || (p->dump(), 0));
511 p->setDisproofPieces(disproofPieces());
512 p->setFinalByDominance(this);
513 p->bestMove = bestMove;
514 p->proof_disproof = proofDisproof();
515 p->twins.clear();
516 }
517 }
518 }
519 }
520
521 #ifndef MINIMAL
522 void osl::checkmate::CheckHashRecord::dump(int dump_depth) const
523 {
524 dump(std::cerr, dump_depth);
525 }
526
527 void osl::checkmate::CheckHashRecord::dump(std::ostream& os, int dump_depth) const
528 {
529 if (dump_depth <= 0)
530 return;
531 os << "+ CheckHashRecord::dump(" << dump_depth << ") "
532 << this << " distance " << distance << " ";
533 os << proofDisproof() << " " << filter;
534 if (proofDisproof().isFinal())
535 os << " " << bestResultInSolved;
536 os << "\n"
537 << " black " << stand(BLACK) << " white " << stand(WHITE) << "\n"
538 << " bestMove " << &*(bestMove);
539 if (bestMove)
540 os << " " << bestMove->move << " " << bestMove->record;
541 if (hasProofPieces())
542 os << " pp " << proofPieces();
543 else if (hasDisproofPieces())
544 os << " dp " << disproofPieces();
545 os << "\n";
546 if (final_by_dominance)
547 {
548 os << "--- final_by_dominance " << final_by_dominance << "\n";
549 final_by_dominance->dump(os, 1);
550 os << "+++ final_by_dominance\n";
551 }
552 if (parent)
553 {
554 os << "parent " << parent << " " << parent->proofDisproof();
555 os << " " << parent->filter;
556 if (parent->bestMove)
557 os << " " << parent->bestMove->move << " " << parent->bestMove->record
558 << parent->bestMove->flags;
559 if (parent->final_by_dominance)
560 os << " f " << final_by_dominance;
561 os << "\n";
562 }
563 moves.dump(os);
564 twins.dump(os);
565 if (bestMove)
566 {
567 os << "depth " << dump_depth << " " << bestMove->record << "\n";
568 if ((dump_depth > 0) && (bestMove->record))
569 bestMove->record->dump(os, dump_depth-1);
570 }
571 }
572 #endif
573
574 #ifdef USE_CHECKMATE_FIND_DAG_ORIGIN
575 osl::CheckHashRecord*
576 osl::CheckHashRecord::getGrandParentForDag(bool isAttackNode,
577 osl::CheckHashRecord* child)
578 {
579 if ((! parent) || (! parent->parent))
580 return NULL;
581 // loop の疑い
582 if (parent->useMaxInsteadOfSum || parent->parent->useMaxInsteadOfSum)
583 return NULL;
584 if ((!isAttackNode)
585 ? (parent->proof() != proof())
586 : (parent->disproof() != disproof()))
587 return NULL;
588
589 child = parent;
590 return parent->parent;
591 }
592
593
594 osl::CheckHashRecord *
595 osl::CheckHashRecord::findDagOrigin(CheckHashRecord *other, bool isAttackNode)
596 {
597 if (! other)
598 return 0;
599 assert(this != other);
600
601 CheckHashRecord *cur_child = NULL;
602 CheckHashRecord *cur = getGrandParentForDag(isAttackNode, cur_child);
603 while (cur)
604 {
605 CheckHashRecord *work_child = NULL;
606 CheckHashRecord *work = other->getGrandParentForDag(isAttackNode,
607 work_child);
608 while (work)
609 {
610 if (cur == work)
611 {
612
613 }
614 work = work->getGrandParentForDag(isAttackNode, work_child);
615 }
616 cur = cur->getGrandParentForDag(isAttackNode, cur_child);
617 }
618 return 0;
619 }
620 #endif
621 /* ------------------------------------------------------------------------- */
622 // ;;; Local Variables:
623 // ;;; mode:c++
624 // ;;; c-basic-offset:2
625 // ;;; End: