Debian Codegraph @

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

raw
1 /* sameBoardList.cc
2 */
3 #include "sameBoardList.h"
4 #include <iostream>
5 osl::checkmate::
6 SameBoardList::~SameBoardList()
7 {
8 }
9
10 void osl::checkmate::
11 SameBoardList::clear()
12 {
13 colleagues.clear();
14 }
15
16 size_t osl::checkmate::
17 SameBoardList::confirmNoVisitedRecords() const
18 {
19 size_t visited = 0;
20 for (list_t::const_iterator q=colleagues.begin(); q!=colleagues.end(); ++q)
21 {
22 if (q->isVisited)
23 {
24 ++visited;
25 #ifdef CHECKMATE_EXTRA_DEBUG
26 std::cerr << q->stand(BLACK) << " " << &*q << "\n";
27 #endif
28 }
29 }
30 return visited;
31 }
32
33 void osl::checkmate::
34 SameBoardList::setMoreProvable(unsigned int& proofLL, unsigned int& disproofUL,
35 const CheckHashRecord *& final_by_dominance,
36 CheckHashRecord& record)
37 {
38 // key の方が record より詰みにくい
39 #ifdef SAMEBOARDLIST_STAT
40 static stat::Ratio ratioDom("SameBoardList: disproof by dominance");
41 #endif
42 const unsigned int p = record.proof();
43 const unsigned int d = record.disproof();
44 #ifdef SAMEBOARDLIST_STAT
45 ratioDom.add(d == 0);
46 #endif
47 if (d == 0)
48 {
49 disproofUL = d; // 不詰
50 if (proofLL <= p)
51 {
52 proofLL = p;
53 final_by_dominance = &record;
54 }
55 check_assert(final_by_dominance);
56 }
57 else
58 {
59 proofLL = std::max(p, proofLL);
60 disproofUL = std::min(d, disproofUL);
61 }
62 }
63
64 void osl::checkmate::
65 SameBoardList::setLessProvable(unsigned int& proofUL, unsigned int& disproofLL,
66 const CheckHashRecord *& final_by_dominance,
67 CheckHashRecord& record)
68 {
69 #ifdef SAMEBOARDLIST_STAT
70 static stat::Ratio ratioDom("SameBoardList: proof by dominance");
71 #endif
72 // key の方が record より詰みやすい
73 const unsigned int p = record.proof();
74 const unsigned int d = record.disproof();
75 #ifdef SAMEBOARDLIST_STAT
76 ratioDom.add(p == 0);
77 #endif
78 if (p == 0)
79 {
80 proofUL = p; // 詰
81 if (disproofLL <= d)
82 {
83 disproofLL = d;
84 final_by_dominance = &record;
85 }
86 check_assert(final_by_dominance);
87 }
88 else
89 {
90 proofUL = std::min(p, proofUL);
91 disproofLL = std::max(d, disproofLL);
92 }
93 }
94
95 osl::checkmate::CheckHashRecord * osl::checkmate::
96 SameBoardList::allocateSlow(Player attacker,
97 const PieceStand& black_stand,
98 const PieceStand& white_stand,
99 const PathEncoding& path,
100 size_t& counter)
101 {
102 if (attacker == BLACK)
103 return allocate<BLACK>(black_stand, white_stand, path, counter);
104 else
105 return allocate<WHITE>(black_stand, white_stand, path, counter);
106 }
107
108
109 template <osl::Player Attacker>
110 osl::checkmate::CheckHashRecord * osl::checkmate::
111 SameBoardList::allocate(const PieceStand& black_stand,
112 const PieceStand& white_stand,
113 const PathEncoding& path,
114 size_t& counter)
115 {
116 CheckHashRecord *result=0;
117 unsigned int proofUL=ProofDisproof::PROOF_MAX; // upper limit
118 unsigned int proofLL=1; // lower limit
119 unsigned int disproofUL=ProofDisproof::DISPROOF_MAX;
120 unsigned int disproofLL=1;
121 const CheckHashRecord *final_by_dominance = 0;
122 const CheckHashRecord *ineffectiveDropLoop = 0;
123
124 const PieceStand& attack_stand
125 = (Attacker == BLACK) ? black_stand : white_stand;
126
127 for (list_t::iterator p=begin(); p!=end(); ++p)
128 {
129 if (p->stand(BLACK) == black_stand)
130 {
131 result = &*p;
132 if (result->proofDisproof().isFinal())
133 return result;
134 if (result->findLoopInList(path))
135 return result;
136 if ((proofUL == 0) || (disproofUL == 0))
137 break;
138
139 continue;
140 }
141 // 証明駒
142 if (p->hasProofPieces()
143 && attack_stand.hasMoreThan<BLACK>(p->proofPieces()))
144 {
145 assert(p->proofDisproof().isCheckmateSuccess());
146 proofUL = 0; // 詰
147 disproofLL = p->disproof();
148 final_by_dominance = &*p;
149 if (result)
150 break;
151 }
152 // 反証駒
153 // 普通の持駒
154 if (p->stand(BLACK).template hasMoreThan<Attacker>(black_stand))
155 {
156 if (p->isVisited) // わざわざ持駒を少なくした
157 {
158 ineffectiveDropLoop = &*p;
159 continue;
160 }
161 setMoreProvable(proofLL, disproofUL, final_by_dominance, *p);
162 }
163 else if ((! p->isVisited)
164 && (black_stand.template hasMoreThan<Attacker>(p->stand(BLACK))))
165 {
166 setLessProvable(proofUL, disproofLL, final_by_dominance, *p);
167 }
168 }
169 if (result)
170 {
171 if (ineffectiveDropLoop)
172 result->setLoopDetection(path, ineffectiveDropLoop);
173 if (! ((proofUL == 0) || (disproofUL == 0)))
174 return result;
175 }
176 if (! result)
177 {
178 ++counter;
179 colleagues.push_front(CheckHashRecord(black_stand, white_stand));
180 result = &colleagues.front();
181 result->sameBoards = this;
182 }
183 if (proofUL == 0)
184 {
185 assert(disproofUL);
186 result->setProofByDominance(disproofLL, final_by_dominance);
187 return result;
188 }
189 if (disproofUL == 0)
190 {
191 assert(proofUL);
192 result->setDisproofByDominance(proofLL, final_by_dominance);
193 return result;
194 }
195 assert(proofLL);
196 assert(disproofLL);
197 // TODO: loop がらみのlower limit は不当に高い場合がある?
198 result->setProofDisproof(ProofDisproof(proofLL, disproofLL));
199 if (ineffectiveDropLoop)
200 result->setLoopDetection(path, ineffectiveDropLoop);
201 return result;
202 }
203
204 void osl::checkmate::
205 SameBoardList::updateSlow(bool is_attack, Player attacker,
206 CheckHashRecord& record, const PathEncoding& path)
207 {
208 if (is_attack)
209 updateSlow<true>(attacker, record, path);
210 else
211 updateSlow<false>(attacker, record, path);
212 }
213
214 template <bool isAttack, osl::Player Attacker>
215 void osl::checkmate::
216 SameBoardList::update(CheckHashRecord& record, const PathEncoding& path)
217 {
218 #ifdef CHECKMATE_DEBUG
219 static stat::Ratio ratio("SameBoardList: skip update by ancestor");
220 #endif
221 unsigned int proofUL=ProofDisproof::PROOF_MAX; // upper limit
222 unsigned int proofLL=record.proof(); // lower limit
223 unsigned int disproofUL=ProofDisproof::DISPROOF_MAX;
224 unsigned int disproofLL=record.disproof();
225 check_assert(proofLL);
226 check_assert(disproofLL);
227 const PieceStand black_stand = record.stand(BLACK);
228 #ifdef CHECKMATE_DEBUG
229 bool found_myself = false;
230 #endif
231 const PieceStand attack_stand = record.stand(Attacker);
232 const CheckHashRecord *final_by_dominance = record.finalByDominance();
233
234 for (list_t::iterator p=begin(); p!=end(); ++p)
235 {
236 if (p->stand(BLACK) == black_stand)
237 {
238 check_assert(&*p == &record);
239 #ifdef CHECKMATE_DEBUG
240 found_myself = true;
241 #endif
242 continue;
243 }
244 // 証明駒
245 if (p->hasProofPieces()
246 && attack_stand.hasMoreThan<BLACK>(p->proofPieces()))
247 {
248 assert(p->proofDisproof().isCheckmateSuccess());
249 proofUL = 0; // 詰
250 disproofLL = p->disproof();
251 final_by_dominance = &*p;
252 break;
253 }
254 // 反証駒
255 // 普通の持駒
256 const bool skip_ancestor = (p->distance < record.distance)
257 || ((p->distance == record.distance) && p->useMaxInsteadOfSum);
258 #ifdef CHECKMATE_DEBUG
259 ratio.add(skip_ancestor);
260 #endif
261 if (skip_ancestor)
262 continue; // loopと合流で無限ポンプができるため,TODO: 条件を絞れるかも
263 if (p->stand(BLACK).template hasMoreThan<Attacker>(black_stand))
264 {
265 if (p->isVisited) // わざわざ持駒を少なくした
266 {
267 record.setLoopDetection(path, &*p);
268 return;
269 }
270 setMoreProvable(proofLL, disproofUL, final_by_dominance, *p);
271 }
272 else if ((! p->isVisited)
273 && (black_stand
274 .template hasMoreThan<Attacker>(p->stand(BLACK))))
275 {
276 setLessProvable(proofUL, disproofLL, final_by_dominance, *p);
277 }
278 }
279 #ifdef CHECKMATE_DEBUG
280 assert(final_by_dominance || found_myself);
281 #endif
282 if (proofUL == 0)
283 {
284 check_assert(disproofUL);
285 record.setProofByDominance(disproofLL, final_by_dominance);
286 return;
287 }
288 if (disproofUL == 0)
289 {
290 check_assert(proofUL);
291 record.setDisproofByDominance(proofLL, final_by_dominance);
292 return;
293 }
294 check_assert(proofUL);
295 check_assert(disproofUL);
296 // TODO: loop がらみのlower limit は不当に高い場合がある?
297 record.setProofDisproof(proofLL, disproofLL);
298 }
299
300 /* ------------------------------------------------------------------------- */
301 // ;;; Local Variables:
302 // ;;; mode:c++
303 // ;;; c-basic-offset:2
304 // ;;; End: