00001
00002
00003 #ifndef _CHECKHASHRECORD_H
00004 #define _CHECKHASHRECORD_H
00005
00006 #include "osl/checkmate/proofDisproof.h"
00007 #include "osl/checkmate/checkMoveList.h"
00008 #include "osl/checkmate/checkAssert.h"
00009 #include "osl/checkmate/twinList.h"
00010 #include "osl/checkmate/twinTable.h"
00011 #include "osl/checkmate/proofPieces.h"
00012 #include "osl/checkmate/disproofPieces.h"
00013 #include "osl/pieceStand.h"
00014 #include "osl/move.h"
00015
00020 #define CHECK_PROPAGATE_BY_DOMINANCE
00021
00026 #define CHECK_EXTRA_LIMIT_PROOF
00027
00031 #define CHECK_EXTRA_LIMIT_DISPROOF
00032
00037 #define CHECK_DELAY_UPWARDS
00038
00043
00044
00045 namespace osl
00046 {
00047 namespace checkmate
00048 {
00049 struct SameBoardList;
00053 struct CheckHashRecord
00054 {
00055 private:
00056 ProofDisproof proof_disproof;
00057 public:
00062 ProofDisproof bestResultInSolved;
00064 CheckMoveList moves;
00066 CheckMove *bestMove;
00068 CheckHashRecord *parent;
00070 private:
00071 const CheckHashRecord *final_by_dominance;
00072 public:
00074 SameBoardList *sameBoards;
00076 TwinList twins;
00077 private:
00079 PieceStand black_stand, white_stand;
00081 PieceStand proof_disproof_pieces;
00082 public:
00084 signed short distance;
00086 MoveFilter filter;
00087
00089 bool isConfluence;
00091 bool useMaxInsteadOfSum;
00093 bool isVisited;
00095 bool false_branch_candidate;
00096 bool false_branch;
00097 private:
00098 enum ProofPiecesType {
00099 UNSET = 0, PROOF, DISPROOF,
00100 };
00102 char proof_pieces_type;
00103 public:
00105 static const ProofDisproof initialProofDisproof()
00106 {
00107 return ProofDisproof(1,1);
00108 }
00109 CheckHashRecord()
00110 : proof_disproof(initialProofDisproof()),
00111 bestResultInSolved(ProofDisproof::Bottom()),
00112 bestMove(0), parent(0), final_by_dominance(0), sameBoards(0),
00113 distance(0), isConfluence(false),
00114 useMaxInsteadOfSum(false), isVisited(false),
00115 false_branch_candidate(false), false_branch(false),
00116 proof_pieces_type(UNSET)
00117 {
00118 }
00119 CheckHashRecord(PieceStand black, PieceStand white)
00120 : proof_disproof(initialProofDisproof()),
00121 bestResultInSolved(ProofDisproof::Bottom()),
00122 bestMove(0), parent(0), final_by_dominance(0), sameBoards(0),
00123 black_stand(black), white_stand(white),
00124 distance(0), isConfluence(false),
00125 useMaxInsteadOfSum(false), isVisited(false),
00126 false_branch_candidate(false), false_branch(false),
00127 proof_pieces_type(UNSET)
00128 {
00129 }
00130 ~CheckHashRecord();
00131
00132 void setProofDisproof(const ProofDisproof& pdp)
00133 {
00134 check_assert(! pdp.isFinal());
00135 check_assert(! proof_disproof.isFinal());
00136 proof_disproof = pdp;
00137 }
00138 void setProofDisproof(unsigned int proof, unsigned int disproof)
00139 {
00140 check_assert(proof && disproof);
00141 check_assert(! proof_disproof.isFinal());
00142 assert(proof < ProofDisproof::PROOF_LIMIT);
00143 assert(disproof < ProofDisproof::DISPROOF_LIMIT);
00144 setProofDisproof(ProofDisproof(proof, disproof));
00145 }
00146 const ProofDisproof& proofDisproof() const { return proof_disproof; }
00147 unsigned int proof() const { return proof_disproof.proof(); }
00148 unsigned int disproof() const { return proof_disproof.disproof(); }
00149
00150 void setProofByDominance(unsigned int disproof,
00151 const CheckHashRecord *final_by_dominance)
00152 {
00153 assert(disproof > ProofDisproof::DISPROOF_LIMIT);
00154 assert(final_by_dominance);
00155 proof_disproof = ProofDisproof(0, disproof);
00156 check_assert(final_by_dominance->hasProofPieces());
00157 setProofPieces(final_by_dominance->proofPieces());
00158 setFinalByDominance(final_by_dominance->finalByDominance()
00159 ? final_by_dominance->finalByDominance() : final_by_dominance);
00160 check_assert(! finalByDominance()->finalByDominance());
00161 bestMove = final_by_dominance->bestMove;
00162 assert(isConsistent());
00163 }
00164 void setDisproofByDominance(unsigned int proof,
00165 const CheckHashRecord *final_by_dominance)
00166 {
00167 assert(proof > ProofDisproof::PROOF_LIMIT);
00168 proof_disproof = ProofDisproof(proof, 0);
00169 assert(final_by_dominance->proofDisproof().isCheckmateFail());
00170 check_assert(final_by_dominance->hasDisproofPieces()
00171 || (final_by_dominance->dump(), 0));
00172 setDisproofPieces(final_by_dominance->disproofPieces());
00173 setFinalByDominance
00174 (final_by_dominance->finalByDominance()
00175 ? final_by_dominance->finalByDominance() : final_by_dominance);
00176 check_assert((! finalByDominance()->finalByDominance())
00177 || (final_by_dominance->dump(),0));
00178 bestMove = final_by_dominance->bestMove;
00179 }
00180 void setFinalByDominance(const CheckHashRecord *dominance)
00181 {
00182 check_assert((dominance == 0) || dominance->final_by_dominance == 0);
00183
00184 check_assert((dominance == 0) || proof_pieces_type);
00185 final_by_dominance = dominance;
00186 }
00187
00188 const PieceStand stand(Player player) const
00189 {
00190 return (player == BLACK) ? black_stand : white_stand;
00191 }
00192 const CheckHashRecord *finalByDominance() const
00193 {
00194 return final_by_dominance;
00195 }
00196 void setProofPieces(PieceStand new_stand)
00197 {
00198 check_assert(proof_pieces_type == UNSET);
00199 proof_pieces_type = PROOF;
00200 proof_disproof_pieces = new_stand;
00201 }
00203 void setProofPiecesAttack(Player attacker)
00204 {
00205 check_assert(bestMove && bestMove->record);
00206 check_assert(bestMove->record->hasProofPieces());
00207 const PieceStand proof_pieces
00208 = ProofPieces::attack(bestMove->record->proofPieces(), bestMove->move,
00209 stand(attacker));
00210 setProofPieces(proof_pieces);
00211 }
00212 void setDisproofPieces(PieceStand new_stand)
00213 {
00214 check_assert(proof_pieces_type == UNSET);
00215 proof_pieces_type = DISPROOF;
00216 proof_disproof_pieces = new_stand;
00217 }
00219 void setDisproofPiecesDefense(Player defense)
00220 {
00221 check_assert(bestMove && bestMove->record);
00222 check_assert(bestMove->record->hasDisproofPieces());
00223 const PieceStand disproof_pieces
00224 = DisproofPieces::defense(bestMove->record->disproofPieces(), bestMove->move,
00225 stand(defense));
00226 setDisproofPieces(disproof_pieces);
00227 }
00228 bool hasProofPieces() const { return proof_pieces_type == PROOF; }
00229 bool hasDisproofPieces() const { return proof_pieces_type == DISPROOF; }
00230 const PieceStand proofPieces() const
00231 {
00232 check_assert(proof_pieces_type == PROOF);
00233 return proof_disproof_pieces;
00234 }
00235 const PieceStand disproofPieces() const
00236 {
00237 check_assert(proof_pieces_type == DISPROOF);
00238 return proof_disproof_pieces;
00239 }
00240 bool isConsistent() const;
00241
00242 bool hasBestMove() const { return bestMove; }
00243 CheckMove* getBestMove()
00244 {
00245 check_assert(hasBestMove());
00246 return bestMove;
00247 }
00248 const CheckMove* getBestMove() const
00249 {
00250 check_assert(hasBestMove());
00251 return bestMove;
00252 }
00253 bool needMoveGeneration() const { return moves.empty(); }
00254 unsigned int add(unsigned int a, unsigned int b)
00255 {
00256 const unsigned int result = (useMaxInsteadOfSum) ? std::max(a,b) : a+b;
00257 check_assert(result >= a);
00258 check_assert(result >= b);
00259 return result;
00260 }
00261 private:
00262 template <Player Attacker>
00263 void propagateCheckmateRecursive();
00264 template <Player Attacker>
00265 void propagateNoCheckmateRecursive();
00266 public:
00268 template <Player Attacker>
00269 void propagateCheckmate(ProofDisproof pdp)
00270 {
00271 check_assert(pdp.proof()==0);
00272 proof_disproof = pdp;
00273 #ifdef CHECK_PROPAGATE_BY_DOMINANCE
00274 if (sameBoards)
00275 propagateCheckmateRecursive<Attacker>();
00276 #endif
00277 }
00279 template <Player Attacker>
00280 void propagateNoCheckmate(ProofDisproof pdp)
00281 {
00282 check_assert(pdp.disproof()==0);
00283 check_assert(! pdp.isLoopDetection());
00284 proof_disproof = pdp;
00285 #ifdef CHECK_PROPAGATE_BY_DOMINANCE
00286 if (sameBoards)
00287 propagateNoCheckmateRecursive<Attacker>();
00288 #endif
00289 }
00290 public:
00292 void confirmParent(CheckHashRecord *parent)
00293 {
00294 check_assert(this->parent && parent);
00295 if (this->parent != parent)
00296 {
00297 isConfluence = true;
00298 this->parent = parent;
00299 this->distance = std::min(parent->distance+1, (int)this->distance);
00300 }
00301 }
00310 unsigned int selectBestAttackMove(const PathEncoding& path,
00311 const TwinTable& table,
00312 unsigned int& currentBestProofNumber,
00313 unsigned int& currentSecondBestProofNumber,
00314 unsigned int& currentDisproofNumber,
00315 unsigned int& currentBestDisproofNumber,
00316 ProofDisproof& bestResultInSolved,
00317 CheckMove *&bestChild);
00318
00319 unsigned int selectBestAttackMoveMain(const PathEncoding& path,
00320 const TwinTable& table,
00321 unsigned int& currentBestProofNumber,
00322 unsigned int& currentSecondBestProofNumber,
00323 unsigned int& currentDisproofNumber,
00324 unsigned int& currentBestDisproofNumber,
00325 ProofDisproof& bestResultInSolved,
00326 CheckMove *&bestChild);
00335 unsigned int selectBestDefenseMove(const PathEncoding& path,
00336 const TwinTable& table,
00337 unsigned int& currentBestDisproofNumber,
00338 unsigned int& currentSecondBestDisproofNumber,
00339 unsigned int& currentProofNumber,
00340 unsigned int& currentBestProofNumber,
00341 ProofDisproof& bestResultInSolved,
00342 CheckMove *&bestChild);
00344 void dump(std::ostream& os, int dumpDepth) const;
00345 void dump(int dumpDepth=1) const;
00346
00347 void updateBestResultInSolvedAttack(const ProofDisproof& pdp)
00348 {
00349 check_assert(pdp.isCheckmateFail());
00350 check_assert(! pdp.isLoopDetection());
00351 bestResultInSolved = bestResultInSolved.betterForAttack(pdp);
00352 }
00353 void updateBestResultInSolvedDefense(const ProofDisproof& pdp)
00354 {
00355 check_assert(pdp.isCheckmateSuccess());
00356 bestResultInSolved = bestResultInSolved.betterForDefense(pdp);
00357 }
00361 void addToSolved(CheckMove& move, const ProofDisproof& pdp,
00362 bool isAttack)
00363 {
00364 check_assert(std::find(moves.begin(), moves.end(), move) != moves.end());
00365 check_assert(pdp.isFinal());
00366 check_assert(move.record == 0
00367 || move.record->proofDisproof().isFinal());
00368 check_assert(! pdp.isLoopDetection());
00369 if (isAttack)
00370 updateBestResultInSolvedAttack(pdp);
00371 else
00372 updateBestResultInSolvedDefense(pdp);
00373 move.flags = MoveFlags::Solved;
00374 }
00375 void addToSolvedInAttack(CheckMove& move, const ProofDisproof& pdp)
00376 {
00377 check_assert(pdp.disproof() == 0);
00378 check_assert(! pdp.isLoopDetection());
00379 addToSolved(move, pdp, true);
00380 }
00381 void addToSolvedInDefense(CheckMove& move, const ProofDisproof& pdp)
00382 {
00383 check_assert(pdp.proof() == 0);
00384 addToSolved(move, pdp, false);
00385 }
00386 void setLoopDetection(const PathEncoding& path, const CheckMove& move,
00387 const CheckHashRecord *loopTo)
00388 {
00389 check_assert(! proofDisproof().isFinal());
00390 proof_disproof = ProofDisproof::Unknown();
00391 twins.addLoopDetection(path, move, loopTo);
00392 }
00393 template <Player Attacker>
00394 void setLoopDetectionTryMerge(const PathEncoding& path,
00395 CheckMove& move,
00396 const CheckHashRecord *loopTo)
00397 {
00398 check_assert(Attacker == alt(move.move.player()));
00399 #ifdef CHECK_ABSORB_LOOP
00400 if (loopTo == this)
00401 {
00402 check_assert(move.record);
00403 const ProofDisproof& pdp = move.record->bestResultInSolved;
00404 const ProofDisproof nocheck
00405 = pdp.betterForAttack(ProofDisproof::NoCheckmate());
00406 check_assert(nocheck.disproof() == 0);
00407 bestMove = &move;
00408 twins.clear();
00409 propagateNoCheckmate<Attacker>(nocheck);
00410 return;
00411 }
00412 #endif
00413 setLoopDetection(path, move, loopTo);
00414 }
00415 void setLoopDetection(const PathEncoding& path,
00416 const CheckHashRecord *loopTo)
00417 {
00418 setLoopDetection(path, CheckMove(), loopTo);
00419 }
00420 template <Player Attacker>
00421 void setLoopDetectionInAttack(const PathEncoding& path)
00422 {
00423 #ifdef CHECK_ABSORB_LOOP
00424 const CheckHashRecord *loopTo = 0;
00425 for (CheckMoveList::iterator p=moves.begin(); p!=moves.end(); ++p)
00426 {
00427 if (! filter.isTarget(p->flags))
00428 continue;
00429 check_assert(p->record);
00430 if (p->record->isVisited)
00431 {
00432 if (loopTo && (loopTo != p->record))
00433 goto multiple_loops;
00434 loopTo = p->record;
00435 continue;
00436 }
00437 const TwinEntry *curLoop = p->findLoop(path);
00438 check_assert(curLoop);
00439 if (curLoop->loopTo == this)
00440 {
00441 p->flags.set(MoveFlags::Solved);
00442 continue;
00443 }
00444 if ((curLoop->loopTo == 0)
00445 || (loopTo && (loopTo != curLoop->loopTo)))
00446 goto multiple_loops;
00447 loopTo = curLoop->loopTo;
00448 }
00449 if (loopTo == 0)
00450 {
00451 twins.clear();
00452 const ProofDisproof nocheck
00453 = bestResultInSolved.betterForAttack(ProofDisproof::NoCheckmate());
00454 check_assert(nocheck.disproof() == 0);
00455 propagateNoCheckmate<Attacker>(nocheck);
00456 return;
00457 }
00458 setLoopDetection(path, CheckMove(), loopTo);
00459 return;
00460 multiple_loops:
00461 #endif
00462 setLoopDetection(path, CheckMove(), 0);
00463 return;
00464 }
00470 const TwinEntry* findLoop(const PathEncoding& path,
00471 const TwinTable& table) const
00472 {
00473 if (twins.empty())
00474 return 0;
00475
00476 TwinList::const_iterator pos = twins.find(path);
00477 if (pos != twins.end())
00478 return &*pos;
00479 return table.findTwin(path);
00480 }
00485 const TwinEntry* findLoopInList(const PathEncoding& path) const
00486 {
00487 TwinList::const_iterator pos = twins.find(path);
00488 if (pos != twins.end())
00489 return &*pos;
00490 return 0;
00491 }
00492 };
00493
00494
00495 inline const TwinEntry*
00496 CheckMove::findLoop(const PathEncoding& path, const TwinTable& table) const
00497 {
00498 check_assert(record);
00499 PathEncoding new_path = path;
00500 new_path.pushMove(move);
00501 return record->findLoop(new_path, table);
00502 }
00503 inline const TwinEntry*
00504 CheckMove::findLoopInList(const PathEncoding& path) const
00505 {
00506 check_assert(record);
00507 PathEncoding new_path = path;
00508 new_path.pushMove(move);
00509 return record->findLoopInList(new_path);
00510 }
00511 }
00512
00513 using checkmate::CheckHashRecord;
00514 }
00515
00516 #endif
00517
00518
00519
00520