Debian Codegraph @

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

raw
1 /* checkHashRecord.h
2 */
3 #ifndef _CHECKHASHRECORD_H
4 #define _CHECKHASHRECORD_H
5
6 #include "osl/checkmate/proofDisproof.h"
7 #include "checkMoveList.h"
8 #include "checkAssert.h"
9 #include "twinList.h"
10 #include "twinTable.h"
11 #include "osl/checkmate/proofPieces.h"
12 #include "osl/checkmate/disproofPieces.h"
13 #include "osl/pieceStand.h"
14 #include "osl/move.h"
15
16 /**
17 * @def CHECK_PROPAGATE_BY_DOMINANCE
18 * 定義すると局面の優越関係を記憶し,詰/不詰を伝播させる
19 */
20 #define CHECK_PROPAGATE_BY_DOMINANCE
21
22 /**
23 * @def CHECK_EXTRA_LIMIT_PROOF
24 * 内部ノードの再展開抑制のための大きめの閾値 (Kishimoto2003?)
25 */
26 #define CHECK_EXTRA_LIMIT_PROOF
27 /**
28 * @def CHECK_EXTRA_LIMIT_DISPROOF
29 * 内部ノードの再展開抑制のための大きめの閾値 (Kishimoto2003?)
30 */
31 #define CHECK_EXTRA_LIMIT_DISPROOF
32
33 /**
34 * @def CHECK_DELAY_UPWARDS
35 * サイクル対策 (Kishimoto2003)
36 */
37 #define CHECK_DELAY_UPWARDS
38
39 /**
40 * @def CHECK_ABSORB_LOOP
41 * LoopDetection の伝播制限 (bug 45)
42 */
43 // #define CHECK_ABSORB_LOOP
44
45 namespace osl
46 {
47 namespace checkmate
48 {
49 struct SameBoardList;
50 /**
51 * 詰将棋でノードごとにテーブルに保持するデータ
52 */
53 struct CheckHashRecord
54 {
55 private:
56 ProofDisproof proof_disproof;
57 public:
58 /** 手番に*否定的*な結果が判明した指手の中で最も都合が良い結果.
59 * 但し, LoopDetection は除く
60 * TODO: メモリ節約: proof/disproof のどちらかは省略可
61 */
62 ProofDisproof bestResultInSolved;
63 /** 現在探索中のリスト */
64 CheckMoveList moves;
65 /** 詰の場合の詰ます手 finalByDominance の場合、別のノードの (solved)moves を指す場合がある*/
66 CheckMove *bestMove;
67 /** 親の一つ,合流の検出に使う */
68 CheckHashRecord *parent; // root はまとめられているので注意
69 /** 優越関係で詰/不詰が分かった場合に記録 */
70 private:
71 const CheckHashRecord *final_by_dominance;
72 public:
73 /** 同じ盤面(持駒が違う)のリスト */
74 SameBoardList *sameBoards;
75 /** LoopDetection 関係(シミュレーション候補) */
76 TwinList twins;
77 private:
78 /** 現在の局面の持駒 */
79 PieceStand black_stand, white_stand;
80 /** 証明駒または反証駒: 詰(不詰)の場合のみセットされる */
81 PieceStand proof_disproof_pieces;
82 public:
83 /** root からの最短パスの距離 */
84 signed short distance;
85 /** 現在対象とする指手の種類 */
86 MoveFilter filter;
87 // この辺のbool は後でbit field にすることを試す
88 /** 自身で合流の場合真 */
89 bool isConfluence;
90 /** 真なら sum の代わりにmax を取る (loop/dag 対策) */
91 bool useMaxInsteadOfSum;
92 /** 探索中に書き換えられる */
93 bool isVisited;
94 /** 柿木2005 */
95 bool false_branch_candidate;
96 bool false_branch;
97 private:
98 enum ProofPiecesType {
99 UNSET = 0, PROOF, DISPROOF,
100 };
101 /** proof (disproof) pieces をセットしたかどうか. */
102 char proof_pieces_type;
103 public:
104 /** proofDisproof の初期値. 優越関係が見つかったら上書きされる */
105 static const ProofDisproof initialProofDisproof()
106 {
107 return ProofDisproof(1,1);
108 }
109 CheckHashRecord()
110 : proof_disproof(initialProofDisproof()),
111 bestResultInSolved(ProofDisproof::Bottom()),
112 bestMove(0), parent(0), final_by_dominance(0), sameBoards(0),
113 distance(0), isConfluence(false),
114 useMaxInsteadOfSum(false), isVisited(false),
115 false_branch_candidate(false), false_branch(false),
116 proof_pieces_type(UNSET)
117 {
118 }
119 CheckHashRecord(PieceStand black, PieceStand white)
120 : proof_disproof(initialProofDisproof()),
121 bestResultInSolved(ProofDisproof::Bottom()),
122 bestMove(0), parent(0), final_by_dominance(0), sameBoards(0),
123 black_stand(black), white_stand(white),
124 distance(0), isConfluence(false),
125 useMaxInsteadOfSum(false), isVisited(false),
126 false_branch_candidate(false), false_branch(false),
127 proof_pieces_type(UNSET)
128 {
129 }
130 ~CheckHashRecord();
131
132 void setProofDisproof(const ProofDisproof& pdp)
133 {
134 check_assert(! pdp.isFinal());
135 check_assert(! proof_disproof.isFinal());
136 proof_disproof = pdp;
137 }
138 void setProofDisproof(unsigned int proof, unsigned int disproof)
139 {
140 check_assert(proof && disproof);
141 check_assert(! proof_disproof.isFinal());
142 assert(proof < ProofDisproof::PROOF_LIMIT);
143 assert(disproof < ProofDisproof::DISPROOF_LIMIT);
144 setProofDisproof(ProofDisproof(proof, disproof));
145 }
146 const ProofDisproof& proofDisproof() const { return proof_disproof; }
147 unsigned int proof() const { return proof_disproof.proof(); }
148 unsigned int disproof() const { return proof_disproof.disproof(); }
149
150 void setProofByDominance(unsigned int disproof,
151 const CheckHashRecord *final_by_dominance)
152 {
153 assert(disproof > ProofDisproof::DISPROOF_LIMIT);
154 assert(final_by_dominance);
155 proof_disproof = ProofDisproof(0, disproof);
156 check_assert(final_by_dominance->hasProofPieces());
157 setProofPieces(final_by_dominance->proofPieces());
158 setFinalByDominance(final_by_dominance->finalByDominance()
159 ? final_by_dominance->finalByDominance() : final_by_dominance);
160 check_assert(! finalByDominance()->finalByDominance());
161 bestMove = final_by_dominance->bestMove;
162 assert(isConsistent());
163 }
164 void setDisproofByDominance(unsigned int proof,
165 const CheckHashRecord *final_by_dominance)
166 {
167 assert(proof > ProofDisproof::PROOF_LIMIT);
168 proof_disproof = ProofDisproof(proof, 0);
169 assert(final_by_dominance->proofDisproof().isCheckmateFail());
170 check_assert(final_by_dominance->hasDisproofPieces()
171 || (final_by_dominance->dump(), 0));
172 setDisproofPieces(final_by_dominance->disproofPieces());
173 setFinalByDominance
174 (final_by_dominance->finalByDominance()
175 ? final_by_dominance->finalByDominance() : final_by_dominance);
176 check_assert((! finalByDominance()->finalByDominance())
177 || (final_by_dominance->dump(),0));
178 bestMove = final_by_dominance->bestMove;
179 }
180 void setFinalByDominance(const CheckHashRecord *dominance)
181 {
182 check_assert((dominance == 0) || dominance->final_by_dominance == 0);
183 // 証明駒/反証駒をセットしてから
184 check_assert((dominance == 0) || proof_pieces_type);
185 final_by_dominance = dominance;
186 }
187
188 const PieceStand stand(Player player) const
189 {
190 return (player == BLACK) ? black_stand : white_stand;
191 }
192 const CheckHashRecord *finalByDominance() const
193 {
194 return final_by_dominance;
195 }
196 void setProofPieces(PieceStand new_stand)
197 {
198 check_assert(proof_pieces_type == UNSET);
199 proof_pieces_type = PROOF;
200 proof_disproof_pieces = new_stand;
201 }
202 /** bestMove をもとに証明駒を設定 */
203 void setProofPiecesAttack(Player attacker)
204 {
205 check_assert(bestMove && bestMove->record);
206 check_assert(bestMove->record->hasProofPieces());
207 const PieceStand proof_pieces
208 = ProofPieces::attack(bestMove->record->proofPieces(), bestMove->move,
209 stand(attacker));
210 setProofPieces(proof_pieces);
211 }
212 void setDisproofPieces(PieceStand new_stand)
213 {
214 check_assert(proof_pieces_type == UNSET);
215 proof_pieces_type = DISPROOF;
216 proof_disproof_pieces = new_stand;
217 }
218 /** bestMove をもとに反証駒を設定 */
219 void setDisproofPiecesDefense(Player defense)
220 {
221 check_assert(bestMove && bestMove->record);
222 check_assert(bestMove->record->hasDisproofPieces());
223 const PieceStand disproof_pieces
224 = DisproofPieces::defense(bestMove->record->disproofPieces(), bestMove->move,
225 stand(defense));
226 setDisproofPieces(disproof_pieces);
227 }
228 bool hasProofPieces() const { return proof_pieces_type == PROOF; }
229 bool hasDisproofPieces() const { return proof_pieces_type == DISPROOF; }
230 const PieceStand proofPieces() const
231 {
232 check_assert(proof_pieces_type == PROOF);
233 return proof_disproof_pieces;
234 }
235 const PieceStand disproofPieces() const
236 {
237 check_assert(proof_pieces_type == DISPROOF);
238 return proof_disproof_pieces;
239 }
240 bool isConsistent() const;
241
242 bool hasBestMove() const { return bestMove; }
243 CheckMove* getBestMove()
244 {
245 check_assert(hasBestMove());
246 return bestMove;
247 }
248 const CheckMove* getBestMove() const
249 {
250 check_assert(hasBestMove());
251 return bestMove;
252 }
253 bool needMoveGeneration() const { return moves.empty(); }
254 unsigned int add(unsigned int a, unsigned int b)
255 {
256 const unsigned int result = (useMaxInsteadOfSum) ? std::max(a,b) : a+b;
257 check_assert(result >= a);
258 check_assert(result >= b);
259 return result;
260 }
261 private:
262 template <Player Attacker>
263 void propagateCheckmateRecursive();
264 template <Player Attacker>
265 void propagateNoCheckmateRecursive();
266 public:
267 /** 詰の時に proofDisproof を設定し,さらに優越関係がある局面に伝播 */
268 template <Player Attacker>
269 void propagateCheckmate(ProofDisproof pdp)
270 {
271 check_assert(pdp.proof()==0);
272 proof_disproof = pdp;
273 #ifdef CHECK_PROPAGATE_BY_DOMINANCE
274 if (sameBoards)
275 propagateCheckmateRecursive<Attacker>();
276 #endif
277 }
278 /** 不詰の時に proofDisproof を設定し,さらに優越関係がある局面に伝播 */
279 template <Player Attacker>
280 void propagateNoCheckmate(ProofDisproof pdp)
281 {
282 check_assert(pdp.disproof()==0);
283 check_assert(! pdp.isLoopDetection());
284 proof_disproof = pdp;
285 #ifdef CHECK_PROPAGATE_BY_DOMINANCE
286 if (sameBoards)
287 propagateNoCheckmateRecursive<Attacker>();
288 #endif
289 }
290 public:
291 /** 親が等しいことを確認 */
292 void confirmParent(CheckHashRecord *parent)
293 {
294 check_assert(this->parent && parent);
295 if (this->parent != parent)
296 {
297 isConfluence = true;
298 this->parent = parent; // 上書き
299 this->distance = std::min(parent->distance+1, (int)this->distance);
300 }
301 }
302 /**
303 * 攻撃側の moves を一通り眺め,各種(dis)proof number を集計し,最善の手を bestChild に保存する.
304 *
305 * - NoEscape より Checkmate を選ぶ
306 * @return 反証されていない子供の proof number のだいたいの平均
307 * @param bestResultInSolved (bestChild==0) の時に,もっともましなpdp.
308 * LoopDetection を含む
309 */
310 unsigned int selectBestAttackMove(const PathEncoding& path,
311 const TwinTable& table,
312 unsigned int& currentBestProofNumber,
313 unsigned int& currentSecondBestProofNumber,
314 unsigned int& currentDisproofNumber,
315 unsigned int& currentBestDisproofNumber,
316 ProofDisproof& bestResultInSolved,
317 CheckMove *&bestChild);
318 // TODO: かっこ悪いので何とかする
319 unsigned int selectBestAttackMoveMain(const PathEncoding& path,
320 const TwinTable& table,
321 unsigned int& currentBestProofNumber,
322 unsigned int& currentSecondBestProofNumber,
323 unsigned int& currentDisproofNumber,
324 unsigned int& currentBestDisproofNumber,
325 ProofDisproof& bestResultInSolved,
326 CheckMove *&bestChild);
327 /**
328 * 防御側の moves を一通り眺め,各種(dis)proof number を集計し,最善の手を bestChild に保存する.
329 *
330 * finalでない時,proof number が同じならdisproof number が小さい方を選ぶ
331 * - Checkmate より NoEscape を選ぶ (打歩詰の可能性があるから)
332 * @param bestResultInSolved (bestChild==0) の時に,もっともましなpdp
333 * @return 証明されていない子供の disproof number のだいたいの平均
334 */
335 unsigned int selectBestDefenseMove(const PathEncoding& path,
336 const TwinTable& table,
337 unsigned int& currentBestDisproofNumber,
338 unsigned int& currentSecondBestDisproofNumber,
339 unsigned int& currentProofNumber,
340 unsigned int& currentBestProofNumber,
341 ProofDisproof& bestResultInSolved,
342 CheckMove *&bestChild);
343 /** @param dumpDepth 1 以上の時に bestMove を再帰的にdumpする. */
344 void dump(std::ostream& os, int dumpDepth) const;
345 void dump(int dumpDepth=1) const;
346
347 void updateBestResultInSolvedAttack(const ProofDisproof& pdp)
348 {
349 check_assert(pdp.isCheckmateFail());
350 check_assert(! pdp.isLoopDetection());
351 bestResultInSolved = bestResultInSolved.betterForAttack(pdp);
352 }
353 void updateBestResultInSolvedDefense(const ProofDisproof& pdp)
354 {
355 check_assert(pdp.isCheckmateSuccess());
356 bestResultInSolved = bestResultInSolved.betterForDefense(pdp);
357 }
358 /**
359 * @param isAttack 攻方のノードかどうか
360 */
361 void addToSolved(CheckMove& move, const ProofDisproof& pdp,
362 bool isAttack)
363 {
364 check_assert(std::find(moves.begin(), moves.end(), move) != moves.end());
365 check_assert(pdp.isFinal());
366 check_assert(move.record == 0
367 || move.record->proofDisproof().isFinal());
368 check_assert(! pdp.isLoopDetection());
369 if (isAttack)
370 updateBestResultInSolvedAttack(pdp);
371 else
372 updateBestResultInSolvedDefense(pdp);
373 move.flags = MoveFlags::Solved;
374 }
375 void addToSolvedInAttack(CheckMove& move, const ProofDisproof& pdp)
376 {
377 check_assert(pdp.disproof() == 0);
378 check_assert(! pdp.isLoopDetection());
379 addToSolved(move, pdp, true);
380 }
381 void addToSolvedInDefense(CheckMove& move, const ProofDisproof& pdp)
382 {
383 check_assert(pdp.proof() == 0);
384 addToSolved(move, pdp, false);
385 }
386 void setLoopDetection(const PathEncoding& path, const CheckMove& move,
387 const CheckHashRecord *loopTo)
388 {
389 check_assert(! proofDisproof().isFinal());
390 proof_disproof = ProofDisproof::Unknown();
391 twins.addLoopDetection(path, move, loopTo);
392 }
393 template <Player Attacker>
394 void setLoopDetectionTryMerge(const PathEncoding& path,
395 CheckMove& move,
396 const CheckHashRecord *loopTo)
397 {
398 check_assert(Attacker == alt(move.move.player()));
399 #ifdef CHECK_ABSORB_LOOP
400 if (loopTo == this)
401 {
402 check_assert(move.record);
403 const ProofDisproof& pdp = move.record->bestResultInSolved;
404 const ProofDisproof nocheck
405 = pdp.betterForAttack(ProofDisproof::NoCheckmate());
406 check_assert(nocheck.disproof() == 0);
407 bestMove = &move;
408 twins.clear();
409 propagateNoCheckmate<Attacker>(nocheck);
410 return;
411 }
412 #endif
413 setLoopDetection(path, move, loopTo);
414 }
415 void setLoopDetection(const PathEncoding& path,
416 const CheckHashRecord *loopTo)
417 {
418 setLoopDetection(path, CheckMove(), loopTo);
419 }
420 template <Player Attacker>
421 void setLoopDetectionInAttack(const PathEncoding& path)
422 {
423 #ifdef CHECK_ABSORB_LOOP
424 const CheckHashRecord *loopTo = 0;
425 for (CheckMoveList::iterator p=moves.begin(); p!=moves.end(); ++p)
426 {
427 if (! filter.isTarget(p->flags))
428 continue;
429 check_assert(p->record);
430 if (p->record->isVisited)
431 {
432 if (loopTo && (loopTo != p->record))
433 goto multiple_loops;
434 loopTo = p->record;
435 continue;
436 }
437 const TwinEntry *curLoop = p->findLoop(path);
438 check_assert(curLoop);
439 if (curLoop->loopTo == this)
440 {
441 p->flags.set(MoveFlags::Solved);
442 continue;
443 }
444 if ((curLoop->loopTo == 0)
445 || (loopTo && (loopTo != curLoop->loopTo)))
446 goto multiple_loops;
447 loopTo = curLoop->loopTo;
448 }
449 if (loopTo == 0)
450 {
451 twins.clear();
452 const ProofDisproof nocheck
453 = bestResultInSolved.betterForAttack(ProofDisproof::NoCheckmate());
454 check_assert(nocheck.disproof() == 0);
455 propagateNoCheckmate<Attacker>(nocheck);
456 return;
457 }
458 setLoopDetection(path, CheckMove(), loopTo);
459 return;
460 multiple_loops:
461 #endif
462 setLoopDetection(path, CheckMove(), 0);
463 return;
464 }
465 /**
466 * 全てのtwin entry を調べて,loopがあるかどうかを判定する.
467 * path で this に到達した時に LoopDetection ならば TwinEntryを返す
468 * TODO: 一手先の検索がほとんどなので,一手前のものを保存するのが良い?
469 */
470 const TwinEntry* findLoop(const PathEncoding& path,
471 const TwinTable& table) const
472 {
473 if (twins.empty())
474 return 0;
475
476 TwinList::const_iterator pos = twins.find(path);
477 if (pos != twins.end())
478 return &*pos;
479 return table.findTwin(path);
480 }
481 /**
482 * twin list を調べて,loopがあるかどうかを判定する.
483 * simulation の場合は,twin list にあるループだけを対象とすれば良い
484 */
485 const TwinEntry* findLoopInList(const PathEncoding& path) const
486 {
487 TwinList::const_iterator pos = twins.find(path);
488 if (pos != twins.end())
489 return &*pos;
490 return 0;
491 }
492 };
493
494
495 inline const TwinEntry*
496 CheckMove::findLoop(const PathEncoding& path, const TwinTable& table) const
497 {
498 check_assert(record);
499 PathEncoding new_path = path;
500 new_path.pushMove(move);
501 return record->findLoop(new_path, table);
502 }
503 inline const TwinEntry*
504 CheckMove::findLoopInList(const PathEncoding& path) const
505 {
506 check_assert(record);
507 PathEncoding new_path = path;
508 new_path.pushMove(move);
509 return record->findLoopInList(new_path);
510 }
511 } // namespace checkmate
512
513 using checkmate::CheckHashRecord;
514 } // namespace osl
515
516 #endif /* _CHECKHASHRECORD_H */
517 // ;;; Local Variables:
518 // ;;; mode:c++
519 // ;;; c-basic-offset:2
520 // ;;; End: