00001
00002
00003 #include "osl/checkmate/checkHashRecord.h"
00004 #include "osl/checkmate/sameBoardList.h"
00005
00006 #include "osl/checkmate/checkMoveGenerator.h"
00007 #ifdef CHECKMATE_DEBUG
00008 # include "osl/stat/ratio.h"
00009 #endif
00010
00011
00012
00013 #ifdef TWINLIST_STAT
00014 # include "osl/stat/histogram.h"
00015 #endif
00016 #include <iostream>
00017
00018
00019
00020
00021 namespace osl
00022 {
00023 namespace checkmate
00024 {
00025
00026 template void CheckHashRecord::propagateCheckmateRecursive<BLACK>();
00027 template void CheckHashRecord::propagateCheckmateRecursive<WHITE>();
00028 template void CheckHashRecord::propagateNoCheckmateRecursive<BLACK>();
00029 template void CheckHashRecord::propagateNoCheckmateRecursive<WHITE>();
00030
00031
00032 BOOST_STATIC_ASSERT(sizeof(CheckHashRecord) + sizeof(int)*6
00033 + sizeof(void*) <= 192);
00034 }
00035 }
00036
00037 bool osl::checkmate::CheckHashRecord::
00038 isConsistent() const
00039 {
00040 assert(! proofDisproof().isLoopDetection());
00041 static int last_type = UNSET;
00042 if (proof_pieces_type != UNSET)
00043 {
00044 if (! proof_disproof.isFinal())
00045 {
00046 std::cerr << "record->proof_pieces_type " << last_type
00047 << " => " << (int)proof_pieces_type << "\n";
00048 }
00049 check_assert(proof_disproof.isFinal());
00050 }
00051 last_type = proof_pieces_type;
00052 return true;
00053 }
00054
00055 osl::checkmate::CheckHashRecord::
00056 ~CheckHashRecord()
00057 {
00058 #if 0
00059
00060
00061 if (final_by_dominance)
00062 assert(final_by_dominance->final_by_dominance == 0);
00063 #endif
00064 assert(isConsistent());
00065
00066 #ifdef TWINLIST_STAT
00067 static stat::Histogram t_hist(1,300,0,true);
00068 t_hist.add(twins.size());
00069 #endif
00070 }
00071
00072 unsigned int osl::checkmate::CheckHashRecord::
00073 selectBestAttackMove(const PathEncoding& path,
00074 const TwinTable& table,
00075 unsigned int& min_proof,
00076 unsigned int& min_proof2,
00077 unsigned int& sum_disproof,
00078 unsigned int& disproof_of_bestchild,
00079 ProofDisproof& bestResultInSolved,
00080 CheckMove *& best_child)
00081 {
00082 #ifdef DELAY_SACRIFICE
00083 if ((! filter.isTarget(MoveFlags::Sacrifice))
00084 && (getProof(proofDisproof()) > 8))
00085 filter.addTarget(MoveFlags::Sacrifice);
00086 #endif
00087 while (true)
00088 {
00089 const unsigned int result =
00090 selectBestAttackMoveMain(path, table, min_proof,
00091 min_proof2,
00092 sum_disproof,
00093 disproof_of_bestchild,
00094 bestResultInSolved, best_child);
00095 if (! best_child)
00096 {
00097 #ifdef DELAY_SACRIFICE
00098 if (! filter.isTarget(MoveFlags::Sacrifice))
00099 {
00100 filter.addTarget(MoveFlags::Sacrifice);
00101 continue;
00102 }
00103 #endif
00104 if ((this->bestResultInSolved == ProofDisproof::PawnCheckmate())
00105 && (! filter.isTarget(MoveFlags::NoPromote)))
00106 {
00107 filter.addTarget(MoveFlags::NoPromote);
00108 continue;
00109 }
00110 #ifdef CHECK_DELAY_UPWARDS
00111 if (! filter.isTarget(MoveFlags::Upward))
00112 {
00113 filter.addTarget(MoveFlags::Upward);
00114 useMaxInsteadOfSum = true;
00115 continue;
00116 }
00117 #endif
00118 }
00119 else
00120 {
00121 if (best_child->record)
00122 check_assert(! best_child->findLoop(path, table));
00123 }
00124 return result;
00125 }
00126 }
00127
00128 unsigned int osl::checkmate::CheckHashRecord::
00129 selectBestAttackMoveMain(const PathEncoding& path,
00130 const TwinTable& table,
00131 unsigned int& min_proof,
00132 unsigned int& min_proof2,
00133 unsigned int& sum_disproof,
00134 unsigned int& disproof_of_bestchild,
00135 ProofDisproof& bestResultInSolved,
00136 CheckMove*& best_child)
00137 {
00138 min_proof=ProofDisproof::BigProofNumber;
00139 min_proof2=ProofDisproof::BigProofNumber;
00140 sum_disproof=0;
00141 disproof_of_bestchild=ProofDisproof::BigProofNumber;
00142 bestResultInSolved = this->bestResultInSolved;
00143 best_child = 0;
00144 unsigned int sum_frontier_proofs = 0;
00145 unsigned int num_frontiers = 0;
00146
00147
00148 const bool targetUpwards = filter.isTarget(MoveFlags::Upward);
00149 for (CheckMoveList::iterator p=moves.begin(); p!=moves.end(); ++p)
00150 {
00151 #ifdef CHECK_DELAY_UPWARDS
00152 if ((! targetUpwards) && (p->flags.isSet(MoveFlags::Upward)))
00153 {
00154 check_assert(p->record);
00155 const ProofDisproof& pdp = p->record->proofDisproof();
00156 if (pdp.proof()==0)
00157 {
00158 if (! pdp.isPawnDropFoul(p->move))
00159 {
00160 best_child = &*p;
00161 return 0;
00162 }
00163 else
00164 {
00165 addToSolvedInAttack(*p, ProofDisproof::PawnCheckmate());
00166 }
00167 }
00168 continue;
00169 }
00170 #endif
00171 if (! filter.isTarget(p->flags))
00172 continue;
00173
00174 unsigned int child_proof, child_disproof;
00175 if (p->record)
00176 {
00177 #ifdef PROOF_NUMBER_PROPAGATE_BY_DOMINANCE
00178 if (p->record->sameBoards && (! p->record->proofDisproof().isFinal())
00179 && (! p->record->isVisited) && (! p->findLoop(path, table)))
00180 p->record->sameBoards->updateSlow<false>(p->move.player(), *p->record,
00181 PathEncoding(path, p->move));
00182 #endif
00183 const TwinEntry *loopDetected = p->findLoop(path, table);
00184 if (loopDetected)
00185 {
00186 #ifdef PAWN_CHECKMATE_SENSITIVE
00187 if ((this->bestResultInSolved != ProofDisproof::PawnCheckmate())
00188 && loopDetected->move.record
00189 && (loopDetected->move.record->bestResultInSolved
00190 == ProofDisproof::PawnCheckmate()))
00191 {
00192 this->bestResultInSolved
00193 = this->bestResultInSolved.betterForAttack(ProofDisproof::PawnCheckmate());
00194 }
00195 #endif
00196 #ifdef CHECK_ABSORB_LOOP
00197 if (loopDetected->loopTo == this)
00198 {
00199 p->flags.set(MoveFlags::Solved);
00200 this->bestResultInSolved = betterForAttack(this->bestResultInSolved, NoCheckmate);
00201 continue;
00202 }
00203 #endif
00204 bestResultInSolved
00205 = bestResultInSolved.betterForAttack(ProofDisproof::LoopDetection());
00206 continue;
00207 }
00208 if (p->record->isVisited)
00209 {
00210 if (p->record->proofDisproof() == ProofDisproof::PawnCheckmate())
00211 this->bestResultInSolved
00212 = this->bestResultInSolved.betterForAttack(ProofDisproof::PawnCheckmate());
00213 bestResultInSolved = bestResultInSolved.betterForAttack(ProofDisproof::LoopDetection());
00214 continue;
00215 }
00216 if (targetUpwards && (distance > p->record->distance))
00217 distance = p->record->distance;
00218
00219 const ProofDisproof& child_pdp = p->record->proofDisproof();
00220 child_proof=child_pdp.proof();
00221 child_disproof=child_pdp.disproof();
00222 if (child_proof == 0)
00223 {
00224 if (! child_pdp.isPawnDropFoul(p->move))
00225 {
00226 best_child = &*p;
00227 return 0;
00228 }
00229 else
00230 {
00231 addToSolvedInAttack(*p, ProofDisproof::PawnCheckmate());
00232 continue;
00233 }
00234 }
00235 else if (child_disproof == 0)
00236 {
00237 check_assert(! child_pdp.isLoopDetection());
00238 addToSolvedInAttack(*p, child_pdp);
00239 continue;
00240 }
00241 else {
00242 #ifdef CHECK_DELAY_UPWARDS
00243 if ((!targetUpwards) && (p->record->distance <= distance)) {
00244 p->flags.set(MoveFlags::Upward);
00245 continue;
00246 }
00247 child_proof += p->cost_proof;
00248 child_disproof += p->cost_disproof;
00249 }
00250 #endif
00251 }
00252 else
00253 {
00254 child_proof = p->h_proof + p->cost_proof;
00255 child_disproof = p->h_disproof + p->cost_proof;
00256 sum_frontier_proofs += p->h_proof;
00257 ++num_frontiers;
00258 }
00259
00260 check_assert(child_proof != 0);
00261 check_assert(child_disproof != 0);
00262
00263 p->addCost(child_proof,child_disproof);
00264
00265 if (child_proof <= min_proof2)
00266 {
00267 if ((child_proof < min_proof)
00268 || ((child_proof == min_proof)
00269 && (child_disproof < disproof_of_bestchild)))
00270 {
00271 best_child=&*p;
00272 min_proof2=min_proof;
00273 min_proof=child_proof;
00274 disproof_of_bestchild=child_disproof;
00275 }
00276 else
00277 {
00278 min_proof2=child_proof;
00279 }
00280 sum_disproof
00281 = add(child_disproof, sum_disproof);
00282 continue;
00283 }
00284 sum_disproof
00285 = add(child_disproof, sum_disproof);
00286 }
00287
00288 bestResultInSolved
00289 = bestResultInSolved.betterForAttack(this->bestResultInSolved);
00290 #ifdef CHECK_EXTRA_LIMIT_PROOF
00291
00292 const unsigned int proof_average
00293 = num_frontiers ? (sum_frontier_proofs / num_frontiers) : 1;
00294 assert(proof_average >= 1);
00295 return proof_average;
00296 #else
00297 return 0;
00298 #endif
00299 }
00300
00301
00302 unsigned int osl::checkmate::CheckHashRecord::
00303 selectBestDefenseMove(const PathEncoding& path,
00304 const TwinTable& table,
00305 unsigned int& min_disproof,
00306 unsigned int& min_disproof2,
00307 unsigned int& sum_proof,
00308 unsigned int& proof_of_bestchild,
00309 ProofDisproof& bestResultInSolved,
00310 CheckMove *&best_child)
00311 {
00312
00313 const bool targetUpwards = filter.isTarget(MoveFlags::Upward);
00314 min_disproof=ProofDisproof::BigProofNumber;
00315 min_disproof2=ProofDisproof::BigProofNumber;
00316 sum_proof=0;
00317 proof_of_bestchild=ProofDisproof::BigProofNumber;
00318 best_child = 0;
00319 bestResultInSolved = this->bestResultInSolved;
00320 unsigned int sum_frontier_disproofs = 0;
00321 unsigned int num_frontiers=0;
00322
00323 unsigned int simple_king_move_proofmax = 0;
00324 const CheckHashRecord *converge_candidate = 0;
00325
00326 for (CheckMoveList::iterator p=moves.begin(); p!=moves.end(); ++p)
00327 {
00328 #ifdef CHECK_DELAY_UPWARDS
00329 if ((! targetUpwards) && (p->flags.isSet(MoveFlags::Upward)))
00330 {
00331 check_assert(p->record);
00332 const ProofDisproof& pdp = p->record->proofDisproof();
00333 if ((pdp.disproof()==0) || p->record->isVisited
00334 || p->findLoop(path, table))
00335 {
00336 best_child = &*p;
00337 return 0;
00338 }
00339 continue;
00340 }
00341 #endif
00342 if (! filter.isTarget(p->flags))
00343 continue;
00344
00345 unsigned int child_proof, child_disproof;
00346 if (p->record)
00347 {
00348 #ifdef PROOF_NUMBER_PROPAGATE_BY_DOMINANCE
00349 if (p->record->sameBoards && (! p->record->proofDisproof().isFinal())
00350 && (! p->record->isVisited) && (! p->findLoop(path, table)))
00351 {
00352 p->record->sameBoards->updateSlow<true>(alt(p->move.player()), *p->record,
00353 PathEncoding(path, p->move));
00354 }
00355 #endif
00356 if (targetUpwards && (distance > p->record->distance))
00357 distance = p->record->distance;
00358
00359 const ProofDisproof& child_pdp = p->record->proofDisproof();
00360 child_proof=child_pdp.proof();
00361 child_disproof=child_pdp.disproof();
00362
00363 if ((child_disproof==0) || p->record->isVisited
00364 || p->findLoop(path, table))
00365 {
00366 best_child = &*p;
00367 return 0;
00368 }
00369 else if (child_proof == 0)
00370 {
00371 addToSolvedInDefense(*p, child_pdp);
00372 continue;
00373 }
00374 else {
00375 #ifdef CHECK_DELAY_UPWARDS
00376 if ((! targetUpwards) && (p->record->distance <= distance)) {
00377 p->flags.set(MoveFlags::Upward);
00378 continue;
00379 }
00380 #endif
00381 child_proof += p->cost_proof;
00382 child_disproof += p->cost_disproof;
00383 }
00384 }
00385 else
00386 {
00387 child_proof = p->h_proof + p->cost_proof;
00388 child_disproof = p->h_disproof + p->cost_disproof;
00389 sum_frontier_disproofs += p->h_disproof;
00390 ++num_frontiers;
00391 }
00392 assert(child_proof);
00393 assert(child_disproof);
00394
00395 p->addCost(child_proof, child_disproof);
00396
00397 if ((child_disproof < min_disproof)
00398 || ((child_disproof == min_disproof)
00399 && (child_proof < proof_of_bestchild)))
00400 {
00401 best_child = &*p;
00402
00403 min_disproof2=min_disproof;
00404 min_disproof=child_disproof;
00405 proof_of_bestchild=child_proof;
00406 }
00407 else if (child_disproof < min_disproof2)
00408 {
00409 min_disproof2=child_disproof;
00410 }
00411 if (false_branch_candidate && p->record && p->move.ptype() == KING
00412 && p->move.capturePtype() == PTYPE_EMPTY) {
00413 if (! false_branch
00414 && p->record->hasBestMove() && p->record->getBestMove()->record) {
00415 if (converge_candidate) {
00416 if (converge_candidate == p->record->getBestMove()->record)
00417 false_branch = true;
00418 }
00419 else {
00420 converge_candidate = p->record->getBestMove()->record;
00421 }
00422 }
00423 if (false_branch) {
00424 if (simple_king_move_proofmax < child_proof)
00425 simple_king_move_proofmax = child_proof;
00426 }
00427 else {
00428 simple_king_move_proofmax = add(simple_king_move_proofmax, child_proof);
00429 }
00430 }
00431 else {
00432 sum_proof = add(sum_proof, child_proof);
00433 }
00434 }
00435 sum_proof += simple_king_move_proofmax;
00436 bestResultInSolved
00437 = bestResultInSolved.betterForDefense(this->bestResultInSolved);
00438 #ifdef CHECK_EXTRA_LIMIT_DISPROOF
00439 const unsigned int disproof_average
00440 = num_frontiers ? (sum_frontier_disproofs / num_frontiers) : 1;
00441 assert(disproof_average >= 1);
00442 return disproof_average;
00443 #else
00444 return 0;
00445 #endif
00446 }
00447
00448 template <osl::Player Attacker>
00449 void osl::checkmate::CheckHashRecord::propagateCheckmateRecursive()
00450 {
00451 assert(proof_pieces_type == PROOF);
00452 #ifdef CHECKMATE_DEBUG
00453 static stat::Ratio ratio("propagateCheckmate");
00454 if ((! moves.empty()) && (moves.begin()->move.player() == Attacker))
00455 {
00456
00457 check_assert(hasBestMove());
00458 }
00459 #endif
00460 check_assert(final_by_dominance == 0);
00461 for (SameBoardList::iterator p=sameBoards->begin(); p!=sameBoards->end(); ++p)
00462 {
00463 if (p->stand(BLACK) == black_stand)
00464 continue;
00465 const PieceStand& attack_stand
00466 = (Attacker == BLACK) ? p->black_stand : p->white_stand;
00467 if (attack_stand.template hasMoreThan<BLACK>(proofPieces()))
00468 {
00469 #ifdef CHECKMATE_DEBUG
00470 ratio.add(p->proof());
00471 #endif
00472 check_assert(p->disproof());
00473 if (p->proof())
00474 {
00475 check_assert(p->final_by_dominance == 0);
00476 p->setProofPieces(proofPieces());
00477 p->setFinalByDominance(this);
00478 p->bestMove = bestMove;
00479 p->proof_disproof = proofDisproof();
00480 check_assert(p->isConsistent());
00481 }
00482 }
00483 }
00484 }
00485
00486 template <osl::Player Attacker>
00487 void osl::checkmate::CheckHashRecord::propagateNoCheckmateRecursive()
00488 {
00489 #ifdef CHECKMATE_DEBUG
00490 static stat::Ratio ratio("propagateNoCheckmate");
00491 #endif
00492 check_assert(final_by_dominance == 0);
00493 check_assert(hasDisproofPieces());
00494 check_assert(! proofDisproof().isLoopDetection());
00495 for (SameBoardList::iterator p=sameBoards->begin(); p!=sameBoards->end(); ++p)
00496 {
00497 if (p->stand(BLACK) == black_stand)
00498 continue;
00499 const PieceStand& defense_stand
00500 = (Attacker == BLACK) ? p->white_stand : p->black_stand;
00501 if (defense_stand.template hasMoreThan<BLACK>(disproofPieces()))
00502 {
00503 #ifdef CHECKMATE_DEBUG
00504 ratio.add(p->disproof());
00505 #endif
00506 check_assert(p->proof()
00507 || (p->dump(), dump(), std::cerr << Attacker << "\n", 0));
00508 if (p->disproof())
00509 {
00510 check_assert((p->final_by_dominance == 0) || (p->dump(), 0));
00511 p->setDisproofPieces(disproofPieces());
00512 p->setFinalByDominance(this);
00513 p->bestMove = bestMove;
00514 p->proof_disproof = proofDisproof();
00515 p->twins.clear();
00516 }
00517 }
00518 }
00519 }
00520
00521 void osl::checkmate::CheckHashRecord::dump(int dump_depth) const
00522 {
00523 dump(std::cerr, dump_depth);
00524 }
00525
00526 void osl::checkmate::CheckHashRecord::dump(std::ostream& os, int dump_depth) const
00527 {
00528 if (dump_depth <= 0)
00529 return;
00530 os << "+ CheckHashRecord::dump(" << dump_depth << ") "
00531 << this << " distance " << distance << " ";
00532 os << proofDisproof() << " " << filter;
00533 if (proofDisproof().isFinal())
00534 os << " " << bestResultInSolved;
00535 os << "\n"
00536 << " black " << stand(BLACK) << " white " << stand(WHITE) << "\n"
00537 << " bestMove " << &*(bestMove);
00538 if (bestMove)
00539 os << " " << bestMove->move << " " << bestMove->record;
00540 if (hasProofPieces())
00541 os << " pp " << proofPieces();
00542 else if (hasDisproofPieces())
00543 os << " dp " << disproofPieces();
00544 os << "\n";
00545 if (final_by_dominance)
00546 {
00547 os << "--- final_by_dominance " << final_by_dominance << "\n";
00548 final_by_dominance->dump(os, 1);
00549 os << "+++ final_by_dominance\n";
00550 }
00551 if (parent)
00552 {
00553 os << "parent " << parent << " " << parent->proofDisproof();
00554 os << " " << parent->filter;
00555 if (parent->bestMove)
00556 os << " " << parent->bestMove->move << " " << parent->bestMove->record
00557 << parent->bestMove->flags;
00558 if (parent->final_by_dominance)
00559 os << " f " << final_by_dominance;
00560 os << "\n";
00561 }
00562 moves.dump(os);
00563 twins.dump(os);
00564 if (bestMove)
00565 {
00566 os << "depth " << dump_depth << " " << bestMove->record << "\n";
00567 if ((dump_depth > 0) && (bestMove->record))
00568 bestMove->record->dump(os, dump_depth-1);
00569 }
00570 }
00571
00572 #ifdef USE_CHECKMATE_FIND_DAG_ORIGIN
00573 osl::CheckHashRecord*
00574 osl::CheckHashRecord::getGrandParentForDag(bool isAttackNode,
00575 osl::CheckHashRecord* child)
00576 {
00577 if ((! parent) || (! parent->parent))
00578 return NULL;
00579
00580 if (parent->useMaxInsteadOfSum || parent->parent->useMaxInsteadOfSum)
00581 return NULL;
00582 if ((!isAttackNode)
00583 ? (parent->proof() != proof())
00584 : (parent->disproof() != disproof()))
00585 return NULL;
00586
00587 child = parent;
00588 return parent->parent;
00589 }
00590
00591
00592 osl::CheckHashRecord *
00593 osl::CheckHashRecord::findDagOrigin(CheckHashRecord *other, bool isAttackNode)
00594 {
00595 if (! other)
00596 return 0;
00597 assert(this != other);
00598
00599 CheckHashRecord *cur_child = NULL;
00600 CheckHashRecord *cur = getGrandParentForDag(isAttackNode, cur_child);
00601 while (cur)
00602 {
00603 CheckHashRecord *work_child = NULL;
00604 CheckHashRecord *work = other->getGrandParentForDag(isAttackNode,
00605 work_child);
00606 while (work)
00607 {
00608 if (cur == work)
00609 {
00610
00611 }
00612 work = work->getGrandParentForDag(isAttackNode, work_child);
00613 }
00614 cur = cur->getGrandParentForDag(isAttackNode, cur_child);
00615 }
00616 return 0;
00617 }
00618 #endif
00619
00620
00621
00622
00623