All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
ntesukiSimulationSearcherProof.tcc
Go to the documentation of this file.
1 /* ntesukiSimulationProof.tcc
2  */
9 #include "osl/apply_move/applyMoveWithPath.h"
12 #ifdef NDEBUG
15 //# include "osl/move_generator/escape.tcc"
16 #endif
17 
18 using namespace osl;
19 using namespace osl::ntesuki;
20 
21 #ifndef RETURN
22 #ifndef NDEBUG
23 #define RETURN \
24  ntesuki_assert(result.isCheckmateSuccess() ==\
25  record->getValueWithPath<A>(pass_left, path).isCheckmateSuccess());\
26  if (record->getValueWithPath<A>(pass_left, path).proof() == 0)\
27  ntesuki_assert(record->getValueWithPath<A>(pass_left, path).disproof() > ProofDisproof::DISPROOF_LIMIT);\
28  if (record->getValueWithPath<A>(pass_left, path).disproof() == 0)\
29  ntesuki_assert(record->getValueWithPath<A>(pass_left, path).proof() > ProofDisproof::PROOF_LIMIT);\
30  return
31 #else
32 #define RETURN return
33 #endif
34 #endif
35 
36 
37 /* Helper classes
38  */
39 template <class Searcher, Player P>
40 class
43 {
47  unsigned int pass_left;
48  const Move last_move;
49 public:
51  NtesukiRecord* record,
52  const NtesukiRecord* record_orig,
53  unsigned int pass_left,
54  const Move last_move)
55  : searcher(searcher),
56  record(record), record_orig(record_orig),
57  pass_left(pass_left),
58  last_move(last_move)
59  {}
60 
62  {
63  (*searcher).template defenseForProof<PlayerTraits<P>::opponent>
64  (record, record_orig, pass_left, last_move);
65  }
66 };
67 
68 template <class Searcher, Player P>
71 {
75  unsigned int pass_left;
76  const Move last_move;
77 public:
79  NtesukiRecord* record,
80  const NtesukiRecord* record_orig,
81  unsigned int pass_left,
82  const Move last_move)
83  : searcher(searcher),
84  record(record), record_orig(record_orig),
85  pass_left(pass_left),
86  last_move(last_move)
87  {}
88 
90  {
91  (*searcher).template attackForProof<PlayerTraits<P>::opponent>
92  (record, record_orig, pass_left, last_move);
93  }
94 };
95 
96 /* ===================
97  * Count the increase of child nodes
98  */
99 class CountChildLock
100 {
101 public:
103  const NtesukiTable& t)
104  : record(r), table(t)
105  {
106  size_start = table.size();
107  }
108 
110  {
111  record->addChildCount(table.size() - size_start);
112  }
113 private:
115  const osl::ntesuki::NtesukiTable& table;
116  unsigned int size_start;
117 };
118 
119 /*======================================================================
120  * Proof
121  *======================================================================
122  */
123 
127 template <Player P>
128 bool
129 NtesukiSimulationSearcher::
130 isSafeMove(const Move move,
131  int pass_left)
132 {
133  if (!state.isValidMove(move, false)) return false;
134 
135  if (move.isDrop()) return true;
136 
137  return move_classifier::SafeMove<P>::isMember(state, move.ptype(), move.from(), move.to());
138 }
139 
140 template <Player P>
141 void
142 NtesukiSimulationSearcher::
143 attackForProof(NtesukiRecord* record,
144  const NtesukiRecord* record_orig,
145  const unsigned int pass_left,
146  const Move last_move)
147 {
148  CountChildLock cclock(record, table);
149  const Player A = P;
150 #ifndef NDEBUG
152 #endif
153  ++node_count;
154  ntesuki_assert(P == state.turn());
155 
156  ntesuki_assert(record);
157  ntesuki_assert(!record->getValueWithPath<A>(pass_left, path).isFinal());
158  ntesuki_assert(record->getBestMove<A>(pass_left).isInvalid());
159 
160  ntesuki_assert(record_orig);
161  ntesuki_assert(record_orig->getValueWithPath<A>(pass_left, path).isCheckmateSuccess());
162  ntesuki_assert(record_orig->getBestMove<A>(pass_left).isValid());
163 
164  ntesuki_assert(!state.inCheck(O));
165 
166  if (record->isVisited())
167  {
169  RETURN;
170  }
171 
172  /* 深さ固定 checkmate searcher を呼び出す */
173  if (record->setUpNode<P>())
174  {
175  const NtesukiResult result_cur = record->getValueWithPath<A>(pass_left, path);
176  if (result_cur.isCheckmateSuccess())
177  {
178  /* Immediate Checkmate */
180  RETURN;
181  }
182  else if (result_cur.isFinal())
183  {
184  result = result_cur;
185  RETURN;
186  }
187  }
188 
189  /* Simulation 元が immediate checkmate ならこの先は simulate できない */
190  const NtesukiMove best_move_orig = record_orig->getBestMove<A>(pass_left);
191  if (best_move_orig.isImmediateCheckmate())
192  {
194  RETURN;
195  }
196 
197  NtesukiRecord::VisitLock visitLock(record);
198  /* n が少ないときの結果を参照 */
199  if ((pass_left > 0) &&
200  record_orig->getValueWithPath<A>(pass_left - 1, path)
202  {
203  if (record->getValueWithPath<A>(pass_left - 1, path)
204  .isCheckmateFail())
205  {
207  RETURN;
208  }
209 
210  ntesuki_assert(!record->getValueWithPath<A>(pass_left - 1, path)
211  .isFinal());
212  NtesukiRecord::UnVisitLock unVisitLock(record);
213 
214  TRY_DFPN;
215  attackForProof<P>(record, record_orig, pass_left - 1, last_move);
216  CATCH_DFPN;
217  RETURN;
218  }
219 
220  const Move move = adjustMove<P>(best_move_orig.getMove());
221 
222  /* invalid move となってしまった */
223  if (!move.isValid() ||
224  !isSafeMove<P>(move, pass_left))
225  {
227  RETURN;
228  }
229 
231  isMember(state, move));
232  if (0 == pass_left && !move_is_check)
233  {
235  RETURN;
236  }
237  if (move_is_check != best_move_orig.isCheck())
238  {
240  RETURN;
241  }
242 
243  /* 以前の bestMove を実行
244  */
245  NtesukiRecord *record_child = table.allocateWithMove(record, move);
246  if (record_child == 0)
247  {
249  RETURN;
250  }
251  const NtesukiRecord* record_child_orig = table.findWithMoveConst(record_orig,
252  best_move_orig);
253  if (!record_child_orig)
254  {
256  RETURN;
257  }
258 
259  result = record_child->getValueWithPath<A>(pass_left, path);
260  if (result.isUnknown())
261  {
263  record_child,
264  record_child_orig,
265  pass_left,
266  move);
267  TRY_DFPN;
268  ApplyMoveWithPath<P>::doUndoMove(state, path, move, helper);
269  if (record->getValueWithPath<A>(pass_left, path).isFinal())
270  {
271  result = record->getValueWithPath<A>(pass_left, path);
272  RETURN;
273  }
274  CATCH_DFPN;
275  }
276 
277  if (result.isPawnDropFoul(move))
278  {
280  RETURN;
281  }
282  else if (result.isCheckmateSuccess())
283  {
285  NtesukiMove best_move(move);
286 
287  TRY_DFPN;
288  best_move.setCheckmateSuccess<A>(pass_left);
289  record->setResult<A>(pass_left, result, best_move, true);
290  CATCH_DFPN;
291  RETURN;
292  }
293  else if (result == ProofDisproof::LoopDetection())
294  {
296  }
297 
298  ntesuki_assert(result.isCheckmateFail());
299  RETURN;
300 }
301 
302 template <Player P>
303 void NtesukiSimulationSearcher::
304 defenseForProof(NtesukiRecord* record,
305  const NtesukiRecord* record_orig,
306  const unsigned int pass_left,
307  const Move last_move)
308 {
309  CountChildLock cclock(record, table);
312 
313  ++node_count;
314  ntesuki_assert(P == state.turn());
315 
316  ntesuki_assert(record);
317  if (!record_orig)
318  {
320  return;
321  }
322 
323  if (state.inCheck(O))
324  {
325  //the previous move was a drop move that did not resolve a check
327  return;
328  }
329 
330  /* 深さ固定 checkmate searcher を呼び出す */
331  if (record->setUpNode<P>())
332  {
333  result = record->getValueWithPath<A>(pass_left, path);
334  if (result.isFinal())
335  {
336  return;
337  }
338  }
339 
340  /* 元のシナリオが間違っている */
341  if (!record_orig->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
342  {
344  return;
345  }
346 
347  if (record->isVisited())
348  {
350  RETURN;
351  }
352  NtesukiRecord::VisitLock visitLock(record);
353 
354  /* 攻撃側に王手がかかっていないか調べる */
355  const bool invalidAttack = state.inCheck(PlayerTraits<P>::opponent);
356  if (invalidAttack)
357  {
359  RETURN;
360  }
361 
362  /* n が少ないときの結果を参照 */
363  if (pass_left > 0 &&
364  record_orig->getValueWithPath<A>(pass_left - 1, path)
366  {
367  result = (record->getValueWithPath<A>(pass_left - 1, path));
368  if(result.isCheckmateFail())
369  {
370  RETURN;
371  }
372  ntesuki_assert(!record->getValueWithPath<A>(pass_left - 1, path)
373  .isFinal());
374  NtesukiRecord::UnVisitLock unVisitLock(record);
375 
376  TRY_DFPN;
377  defenseForProof<P>(record, record_orig, pass_left - 1, last_move);
378  CATCH_DFPN;
379  RETURN;
380  }
381 
382  /*
383  * 受ける手の実行
384  */
385  /*
386  * 守り側の手を生成する
387  * - 王手がかかっているか調べる(王手がかかっていた場合には逃げる手を生成する)
388  * - そうでないなら,通常の手生成を行う
389  */
391  record->generateMoves<P>(moves, 0, true);
393 
394  if (moves.empty())
395  {
396  result = ProofDisproof::NoEscape();
397  TRY_DFPN;
398  record->setResult<A>(pass_left, result,
399  NtesukiMove::INVALID(), false);
400 
401  CATCH_DFPN;
402  RETURN;
403  }
404 
405  bool some_moves_not_generated = false;
406  for (NtesukiMoveList::iterator move_it = moves.begin();
407  move_it != moves.end(); move_it++)
408  {
409  NtesukiMove& move = *move_it;
410  if (move.isCheckmateSuccess<A>(pass_left)) continue;
411 
412  /* 逆王手は読んでいない可能性がある */
413  if (isscheme != NtesukiRecord::normal_is &&
414  isscheme != NtesukiRecord::delay_is &&
415  move.isCheck() && pass_left > 0) continue;
416 
417  /* シミュレーション元の子を探す */
418  const NtesukiRecord* record_child_orig = table.findWithMoveConst(record_orig, move);
419  if (!record_child_orig ||
420  !record_child_orig->getValue<A>(pass_left).isCheckmateSuccess())
421  {
422  some_moves_not_generated = true;
423  continue;
424  }
425 
426  NtesukiRecord *record_child = table.allocateWithMove(record, move);
427  if (record_child == 0)
428  {
429  result = ProofDisproof::NoCheckmate();
430  RETURN;
431  }
432 
433  if(record_child->isVisited())
434  {
435  result = ProofDisproof::LoopDetection();
436  record->setLoopWithPath<A>(pass_left, path);
437  TRY_DFPN;
438  record->setResult<A>(pass_left, NtesukiResult(1, 1),
439  NtesukiMove::INVALID(), false);
440  CATCH_DFPN;
441  RETURN;
442  }
443 
444  int pass_left_child = pass_left;
445  if (move.isPass()) --pass_left_child;
446  const PathEncoding path_child(path, move.getMove());
447  result = record_child->getValueWithPath<A>(pass_left_child, path_child);
448  if (result.isUnknown())
449  {
451  record_child,
452  record_child_orig,
453  pass_left_child,
454  move.getMove());
455  TRY_DFPN;
456  ApplyMoveWithPath<P>::doUndoMoveOrPass(state, path,
457  move.getMove(),
458  helper);
459  CATCH_DFPN;
460  if (record->getValueWithPath<A>(pass_left, path).isFinal())
461  {
462  result = record->getValueWithPath<A>(pass_left, path);
463  RETURN;
464  }
465  }
466 
467  if (result.isCheckmateFail())
468  {
469  RETURN;
470  }
471  }
472 
473  ntesuki_assert(result.isCheckmateSuccess());
474 
475  if (some_moves_not_generated)
476  {
477  result = ProofDisproof::NoCheckmate();
478  }
479  else
480  {
481  TRY_DFPN;
482  record->setResult<A>(pass_left, result,
483  NtesukiMove::INVALID(), true);
484  CATCH_DFPN;
485  }
486  RETURN;
487 }
488 
489 /* Public interface
490  */
491 template <Player P>
492 bool
493 NtesukiSimulationSearcher::
494 startFromAttackProof(NtesukiRecord* record,
495  const NtesukiRecord* record_orig,
496  const unsigned int pass_left,
497  const Move last_move)
498 {
499  assert(P == state.turn());
500 
501  const Player A = P;
502  ntesuki_assert(record);
503  if (!record_orig)
504  {
505  return false;
506  }
507 
508  if (!record_orig->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
509  {
510  return false;
511  }
512 
513  if (!record->isDominatedByProofPieces<A>(record_orig, pass_left))
514  {
515  return false;
516  }
517 
518  TRY_DFPN;
519  if (record->setUpNode<P>())
520  {
521  if (record->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
522  {
523  /* Immediate Checkmate */
525  return true;
526  }
527  else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
528  {
530  return false;
531  }
532  }
533  CATCH_DFPN;
534 
535  TRY_DFPN;
536  const NtesukiMove m = (record_orig->getBestMove<A>(pass_left));
537  if (m.isImmediateCheckmate()) return false;
538  CATCH_DFPN;
539 
540  ++proof_count;
541 
542  TRY_DFPN;
543  OracleProverLight light(state, mg, path, table,isscheme);
544  if (light.startFromAttack<P>(record, record_orig, pass_left))
545  {
546  ++proof_success_count;
547  ++light_proof_success_count;
548  ntesuki_assert(record->getValueWithPath<A>(pass_left, path)
549  .isCheckmateSuccess());
550  return true;
551  }
552  else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
553  {
555  return false;
556  }
557  CATCH_DFPN;
558 
559  TRY_DFPN;
560  attackForProof<P>(record, record_orig, pass_left, last_move);
561  CATCH_DFPN;
562  if (result.isCheckmateSuccess())
563  {
564  ++proof_success_count;
565  return true;
566  }
567  return false;
568 }
569 
570 template <Player P>
571 bool
572 NtesukiSimulationSearcher::
573 startFromDefenseProof(NtesukiRecord* record,
574  const NtesukiRecord* record_orig,
575  const unsigned int pass_left,
576  const Move last_move)
577 {
578  assert(P == state.turn());
579 
581  ntesuki_assert(record);
582  if (!record_orig ||
583  !record_orig->getValueWithPath<A>(pass_left, path).
584  isCheckmateSuccess())
585  {
586  return false;
587  }
588 
589  if (!record->isDominatedByProofPieces<A>(record_orig, pass_left))
590  {
591  return false;
592  }
593 
594  if (record->setUpNode<P>())
595  {
596  if (record->getValueWithPath<A>(pass_left, path).isCheckmateSuccess())
597  {
598  /* Immediate Checkmate */
600  return true;
601  }
602  else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
603  {
605  return false;
606  }
607  }
608 
609  const NtesukiMove m = (record_orig->getBestMove<A>(pass_left));
610  if (m.isImmediateCheckmate()) return false;
611 
612  ++proof_count;
613 
614  OracleProverLight light(state, mg, path, table, isscheme);
615  TRY_DFPN;
616  if (light.startFromDefense<P>(record, record_orig, pass_left))
617  {
618  ++proof_success_count;
619  ++light_proof_success_count;
620  ntesuki_assert(record->getValueWithPath<A>(pass_left, path).
621  isCheckmateSuccess());
622  return true;
623  }
624  else if (record->getValueWithPath<A>(pass_left, path).isCheckmateFail())
625  {
627  return false;
628  }
629  CATCH_DFPN;
630 
631  TRY_DFPN;
632  defenseForProof<P>(record, record_orig, pass_left, last_move);
633  CATCH_DFPN;
634 
635  if (result.isCheckmateSuccess())
636  {
637  ++proof_success_count;
638  return true;
639  }
640  return false;
641 }
642 
643 #undef RETURN
644 
645 // ;;; Local Variables:
646 // ;;; mode:c++
647 // ;;; c-basic-offset:2
648 // ;;; End: