00001
00002
00003 #include "osl/checkmate/sameBoardList.h"
00004 #include <iostream>
00005 osl::checkmate::
00006 SameBoardList::~SameBoardList()
00007 {
00008 }
00009
00010 void osl::checkmate::
00011 SameBoardList::clear()
00012 {
00013 colleagues.clear();
00014 }
00015
00016 size_t osl::checkmate::
00017 SameBoardList::confirmNoVisitedRecords() const
00018 {
00019 size_t visited = 0;
00020 for (list_t::const_iterator q=colleagues.begin(); q!=colleagues.end(); ++q)
00021 {
00022 if (q->isVisited)
00023 {
00024 ++visited;
00025 #ifdef CHECKMATE_EXTRA_DEBUG
00026 std::cerr << q->stand(BLACK) << " " << &*q << "\n";
00027 #endif
00028 }
00029 }
00030 return visited;
00031 }
00032
00033 void osl::checkmate::
00034 SameBoardList::setMoreProvable(unsigned int& proofLL, unsigned int& disproofUL,
00035 const CheckHashRecord *& final_by_dominance,
00036 CheckHashRecord& record)
00037 {
00038
00039 #ifdef SAMEBOARDLIST_STAT
00040 static stat::Ratio ratioDom("SameBoardList: disproof by dominance");
00041 #endif
00042 const unsigned int p = record.proof();
00043 const unsigned int d = record.disproof();
00044 #ifdef SAMEBOARDLIST_STAT
00045 ratioDom.add(d == 0);
00046 #endif
00047 if (d == 0)
00048 {
00049 disproofUL = d;
00050 if (proofLL <= p)
00051 {
00052 proofLL = p;
00053 final_by_dominance = &record;
00054 }
00055 check_assert(final_by_dominance);
00056 }
00057 else
00058 {
00059 proofLL = std::max(p, proofLL);
00060 disproofUL = std::min(d, disproofUL);
00061 }
00062 }
00063
00064 void osl::checkmate::
00065 SameBoardList::setLessProvable(unsigned int& proofUL, unsigned int& disproofLL,
00066 const CheckHashRecord *& final_by_dominance,
00067 CheckHashRecord& record)
00068 {
00069 #ifdef SAMEBOARDLIST_STAT
00070 static stat::Ratio ratioDom("SameBoardList: proof by dominance");
00071 #endif
00072
00073 const unsigned int p = record.proof();
00074 const unsigned int d = record.disproof();
00075 #ifdef SAMEBOARDLIST_STAT
00076 ratioDom.add(p == 0);
00077 #endif
00078 if (p == 0)
00079 {
00080 proofUL = p;
00081 if (disproofLL <= d)
00082 {
00083 disproofLL = d;
00084 final_by_dominance = &record;
00085 }
00086 check_assert(final_by_dominance);
00087 }
00088 else
00089 {
00090 proofUL = std::min(p, proofUL);
00091 disproofLL = std::max(d, disproofLL);
00092 }
00093 }
00094
00095 osl::checkmate::CheckHashRecord * osl::checkmate::
00096 SameBoardList::allocateSlow(Player attacker,
00097 const PieceStand& black_stand,
00098 const PieceStand& white_stand,
00099 const PathEncoding& path,
00100 size_t& counter)
00101 {
00102 if (attacker == BLACK)
00103 return allocate<BLACK>(black_stand, white_stand, path, counter);
00104 else
00105 return allocate<WHITE>(black_stand, white_stand, path, counter);
00106 }
00107
00108
00109 template <osl::Player Attacker>
00110 osl::checkmate::CheckHashRecord * osl::checkmate::
00111 SameBoardList::allocate(const PieceStand& black_stand,
00112 const PieceStand& white_stand,
00113 const PathEncoding& path,
00114 size_t& counter)
00115 {
00116 CheckHashRecord *result=0;
00117 unsigned int proofUL=ProofDisproof::PROOF_MAX;
00118 unsigned int proofLL=1;
00119 unsigned int disproofUL=ProofDisproof::DISPROOF_MAX;
00120 unsigned int disproofLL=1;
00121 const CheckHashRecord *final_by_dominance = 0;
00122 const CheckHashRecord *ineffectiveDropLoop = 0;
00123
00124 const PieceStand& attack_stand
00125 = (Attacker == BLACK) ? black_stand : white_stand;
00126
00127 for (list_t::iterator p=begin(); p!=end(); ++p)
00128 {
00129 if (p->stand(BLACK) == black_stand)
00130 {
00131 result = &*p;
00132 if (result->proofDisproof().isFinal())
00133 return result;
00134 if (result->findLoopInList(path))
00135 return result;
00136 if ((proofUL == 0) || (disproofUL == 0))
00137 break;
00138
00139 continue;
00140 }
00141
00142 if (p->hasProofPieces()
00143 && attack_stand.hasMoreThan<BLACK>(p->proofPieces()))
00144 {
00145 assert(p->proofDisproof().isCheckmateSuccess());
00146 proofUL = 0;
00147 disproofLL = p->disproof();
00148 final_by_dominance = &*p;
00149 if (result)
00150 break;
00151 }
00152
00153
00154 if (p->stand(BLACK).template hasMoreThan<Attacker>(black_stand))
00155 {
00156 if (p->isVisited)
00157 {
00158 ineffectiveDropLoop = &*p;
00159 continue;
00160 }
00161 setMoreProvable(proofLL, disproofUL, final_by_dominance, *p);
00162 }
00163 else if ((! p->isVisited)
00164 && (black_stand.template hasMoreThan<Attacker>(p->stand(BLACK))))
00165 {
00166 setLessProvable(proofUL, disproofLL, final_by_dominance, *p);
00167 }
00168 }
00169 if (result)
00170 {
00171 if (ineffectiveDropLoop)
00172 result->setLoopDetection(path, ineffectiveDropLoop);
00173 if (! ((proofUL == 0) || (disproofUL == 0)))
00174 return result;
00175 }
00176 if (! result)
00177 {
00178 ++counter;
00179 colleagues.push_front(CheckHashRecord(black_stand, white_stand));
00180 result = &colleagues.front();
00181 result->sameBoards = this;
00182 }
00183 if (proofUL == 0)
00184 {
00185 assert(disproofUL);
00186 result->setProofByDominance(disproofLL, final_by_dominance);
00187 return result;
00188 }
00189 if (disproofUL == 0)
00190 {
00191 assert(proofUL);
00192 result->setDisproofByDominance(proofLL, final_by_dominance);
00193 return result;
00194 }
00195 assert(proofLL);
00196 assert(disproofLL);
00197
00198 result->setProofDisproof(ProofDisproof(proofLL, disproofLL));
00199 if (ineffectiveDropLoop)
00200 result->setLoopDetection(path, ineffectiveDropLoop);
00201 return result;
00202 }
00203
00204 void osl::checkmate::
00205 SameBoardList::updateSlow(bool is_attack, Player attacker,
00206 CheckHashRecord& record, const PathEncoding& path)
00207 {
00208 if (is_attack)
00209 updateSlow<true>(attacker, record, path);
00210 else
00211 updateSlow<false>(attacker, record, path);
00212 }
00213
00214 template <bool isAttack, osl::Player Attacker>
00215 void osl::checkmate::
00216 SameBoardList::update(CheckHashRecord& record, const PathEncoding& path)
00217 {
00218 #ifdef CHECKMATE_DEBUG
00219 static stat::Ratio ratio("SameBoardList: skip update by ancestor");
00220 #endif
00221 unsigned int proofUL=ProofDisproof::PROOF_MAX;
00222 unsigned int proofLL=record.proof();
00223 unsigned int disproofUL=ProofDisproof::DISPROOF_MAX;
00224 unsigned int disproofLL=record.disproof();
00225 check_assert(proofLL);
00226 check_assert(disproofLL);
00227 const PieceStand black_stand = record.stand(BLACK);
00228 #ifdef CHECKMATE_DEBUG
00229 bool found_myself = false;
00230 #endif
00231 const PieceStand attack_stand = record.stand(Attacker);
00232 const CheckHashRecord *final_by_dominance = record.finalByDominance();
00233
00234 for (list_t::iterator p=begin(); p!=end(); ++p)
00235 {
00236 if (p->stand(BLACK) == black_stand)
00237 {
00238 check_assert(&*p == &record);
00239 #ifdef CHECKMATE_DEBUG
00240 found_myself = true;
00241 #endif
00242 continue;
00243 }
00244
00245 if (p->hasProofPieces()
00246 && attack_stand.hasMoreThan<BLACK>(p->proofPieces()))
00247 {
00248 assert(p->proofDisproof().isCheckmateSuccess());
00249 proofUL = 0;
00250 disproofLL = p->disproof();
00251 final_by_dominance = &*p;
00252 break;
00253 }
00254
00255
00256 const bool skip_ancestor = (p->distance < record.distance)
00257 || ((p->distance == record.distance) && p->useMaxInsteadOfSum);
00258 #ifdef CHECKMATE_DEBUG
00259 ratio.add(skip_ancestor);
00260 #endif
00261 if (skip_ancestor)
00262 continue;
00263 if (p->stand(BLACK).template hasMoreThan<Attacker>(black_stand))
00264 {
00265 if (p->isVisited)
00266 {
00267 record.setLoopDetection(path, &*p);
00268 return;
00269 }
00270 setMoreProvable(proofLL, disproofUL, final_by_dominance, *p);
00271 }
00272 else if ((! p->isVisited)
00273 && (black_stand
00274 .template hasMoreThan<Attacker>(p->stand(BLACK))))
00275 {
00276 setLessProvable(proofUL, disproofLL, final_by_dominance, *p);
00277 }
00278 }
00279 #ifdef CHECKMATE_DEBUG
00280 assert(final_by_dominance || found_myself);
00281 #endif
00282 if (proofUL == 0)
00283 {
00284 check_assert(disproofUL);
00285 record.setProofByDominance(disproofLL, final_by_dominance);
00286 return;
00287 }
00288 if (disproofUL == 0)
00289 {
00290 check_assert(proofUL);
00291 record.setDisproofByDominance(proofLL, final_by_dominance);
00292 return;
00293 }
00294 check_assert(proofUL);
00295 check_assert(disproofUL);
00296
00297 record.setProofDisproof(proofLL, disproofLL);
00298 }
00299
00300
00301
00302
00303
00304