All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
ntesukiSimulationSearcherDisproof.tcc
Go to the documentation of this file.
1 /* ntesukiSimulationDisproof.tcc
2  */
4 #include "osl/state/hashEffectState.h"
5 
10 #include "osl/apply_move/applyMoveWithPath.h"
11 
12 #ifndef NDEBUG
13 #define RETURN \
14  TRY_DFPN;\
15  ntesuki_assert(result.isFinal());\
16  CATCH_DFPN; \
17  return
18 #else
19 #define RETURN return
20 #endif
21 
22 using namespace osl;
23 using namespace osl::ntesuki;
24 
25 template <class Searcher, Player P>
26 class
29 {
33  unsigned int pass_left;
34  const Move last_move;
35 
36 public:
38  NtesukiRecord* record,
39  const NtesukiRecord* record_orig,
40  unsigned int pass_left,
41  const Move last_move)
42  : searcher(searcher),
43  record(record), record_orig(record_orig),
44  pass_left(pass_left),
45  last_move(last_move)
46  {}
47 
49  {
50  (*searcher).template defenseForDisproof<PlayerTraits<P>::opponent>
51  (record, record_orig, pass_left, last_move);
52  }
53 };
54 
55 template <class Searcher, Player P>
58 {
62  unsigned int pass_left;
63  const Move last_move;
64 public:
66  NtesukiRecord* record,
67  const NtesukiRecord* record_orig,
68  unsigned int pass_left,
69  const Move last_move)
70  : searcher(searcher),
71  record(record), record_orig(record_orig),
72  pass_left(pass_left),
73  last_move(last_move)
74  {}
75 
76 
78  {
79  (*searcher).template attackForDisproof<PlayerTraits<P>::opponent>
80  (record, record_orig, pass_left, last_move);
81  }
82 };
83 
84 /*======================================================================
85  * Disproof
86  *======================================================================
87  */
88 
89 template <Player P>
90 void
91 NtesukiSimulationSearcher::
92 attackForDisproof(NtesukiRecord* record,
93  const NtesukiRecord* record_orig,
94  const unsigned int pass_left,
95  const Move last_move)
96 {
97  const Player attacker = P;
98  ++node_count;
99  ntesuki_assert(P == state.turn());
100 
101  ntesuki_assert(record);
102  ntesuki_assert(record->getBestMove<attacker>(pass_left).isInvalid());
103  ntesuki_assert(record_orig);
104 
105  const bool invalid_defense = state.inCheck(PlayerTraits<P>::opponent);
106  if (invalid_defense)
107  {
109  RETURN;
110  }
111 
112  ntesuki_assert (!record->isVisited());
113  NtesukiRecord::VisitLock visitLock(record);
114 
115  if (record->setUpNode<P>())
116  {
117  result = record->getValueWithPath<attacker>(pass_left, path);
118  if (result.isFinal())
119  {
120  /* result by fixed depth searcher */
121  RETURN;
122  }
123  }
124 
125  /* n が少ないときの結果を確定 */
126  if (pass_left > 0)
127  {
128  result = record->getValueWithPath<attacker>(pass_left - 1, path);
129  if (!result.isFinal())
130  {
131  NtesukiRecord::UnVisitLock unVisitLock(record);
132  attackForDisproof<P>(record, record_orig, pass_left - 1, last_move);
133  }
134 
135  if (!result.isCheckmateFail())
136  {
137  RETURN;
138  }
139  ntesuki_assert(result.isCheckmateFail());
140  }
141 
142  /* 攻め手の生成
143  */
145  record->generateMoves<P>(moves, pass_left, false);
146 
147  /* 攻める手の実行
148  */
149  bool has_loop = false;
150  bool disproof_failed = false;
151  for (NtesukiMoveList::iterator move_it = moves.begin();
152  move_it != moves.end(); move_it++)
153  {
154  NtesukiMove& move = *move_it;
155 
156  if (move.isPass()) continue;
157  if (move.isCheckmateFail<attacker>(pass_left)) continue;
158  if (!move.isCheck() && 0 == pass_left) continue;
159 
160  /* DANGEROUS this time pawn checkmate might be avoidable */
161  if (move.isNoPromote()) continue;
162 
163  NtesukiRecord *record_child = table.allocateWithMove(record, move);
164  if (record_child == 0)
165  {
167  RETURN;
168  }
169  ntesuki_assert(record_child);
170  if(record_child->isVisited())
171  {
172  //move.setCheckmateFail<attacker>(pass_left);
173  has_loop = true;
174  continue;
175  }
176 
177  PathEncoding path_child(path, move.getMove());
178  result = record_child->getValueWithPath<attacker>(pass_left, path_child);
179 
180  if(result.isUnknown())
181  {
182  const NtesukiRecord* record_child_orig = table.findWithMoveConst(record_orig, move);
183  if (!record_child_orig ||
184  !record_child_orig->getValue<attacker>(pass_left).isCheckmateFail())
185  {
186  /* a move that used not to be a check became a check, or
187  * might have been a loop
188  */
189  result = ProofDisproof::Checkmate();
190  RETURN;
191  }
192 
194  record_child,
195  record_child_orig,
196  pass_left,
197  move.getMove());
198  TRY_DFPN;
199  ApplyMoveWithPath<P>::doUndoMove(state, path, move.getMove(), helper);
200  CATCH_DFPN;
201  if (record->getValueWithPath<attacker>(pass_left, path).isFinal())
202  {
203  result = record->getValueWithPath<attacker>(pass_left, path);
204  RETURN;
205  }
206  }
207 
208  if (result.isCheckmateSuccess())
209  {
210  disproof_failed = true;
211  continue;
212  }
213  else if (result == ProofDisproof::LoopDetection())
214  {
215  has_loop = true;
216  }
217 
218  ntesuki_assert(result.isCheckmateFail());
219  move.setCheckmateFail<attacker>(pass_left);
220  }
221 
222  if (disproof_failed)
223  {
225  RETURN;
226  }
227 
228 
229  if (has_loop)
230  {
231  record->setLoopWithPath<attacker>(pass_left, path);
233  TRY_DFPN;
234  record->setResult<attacker>(pass_left, NtesukiResult(1, 1),
235  NtesukiMove::INVALID(), false);
236  CATCH_DFPN;
237  }
238  else
239  {
241  TRY_DFPN;
242  record->setResult<attacker>(pass_left, result,
243  NtesukiMove::INVALID(), true);
244  CATCH_DFPN;
245  }
246  RETURN;
247 }
248 
249 template <Player P>
250 void
251 NtesukiSimulationSearcher::
252 defenseForDisproof(NtesukiRecord* record,
253  const NtesukiRecord* record_orig,
254  const unsigned int pass_left,
255  const Move last_move)
256 {
257  const Player attacker = PlayerTraits<P>::opponent;
258  ++node_count;
259  ntesuki_assert(P == state.turn());
260 
261  ntesuki_assert(state.inCheck(P) || (pass_left > 0));
262 
263  ntesuki_assert(record);
264  ntesuki_assert(record->getBestMove<attacker>(pass_left).isInvalid());
265  ntesuki_assert(record_orig);
266  ntesuki_assert(!record->isVisited());
267  ntesuki_assert(record_orig->getValue<attacker>(pass_left).
268  isCheckmateFail());
269  NtesukiRecord::VisitLock visitLock(record);
270 
271  if (record->setUpNode<P>())
272  {
273  result = record->getValueWithPath<attacker>(pass_left, path);
274  if (result.isFinal())
275  {
276  /* result by fixed depth searcher */
277  RETURN;
278  }
279  }
280 
281 #ifndef NDEBUG
282  /* 攻撃側に王手がかかっていないか調べる */
283  ntesuki_assert(!state.inCheck(attacker));
284 #endif
285 
286  /* 以前の bestMove を実行
287  */
288  const NtesukiMove best_move =
289  record_orig->getBestMove<attacker>(pass_left);
290  if (best_move.isInvalid())
291  {
292  /* is by fixed depth searcher */
294  RETURN;
295  }
296  const NtesukiRecord *record_child_orig = table.findWithMoveConst(record_orig, best_move);
297  if (!record_child_orig ||
298  !record_child_orig->getValue<attacker>(pass_left).isCheckmateFail())
299  {
300  /* fixed depth searcher 等での disproof */
302  RETURN;
303  }
304  ntesuki_assert(record_child_orig);
305 
306  if (!best_move.isPass() &&
307  !state.template isAlmostValidMove<false>(best_move.getMove()))
308  {
310  RETURN;
311  }
312 
313  NtesukiRecord *record_child = table.allocateWithMove(record, best_move);
314  if (record_child == 0)
315  {
317  RETURN;
318  }
319  ntesuki_assert(record_child);
320 
321  int pass_left_child = pass_left;
322  if (best_move.isPass()) --pass_left_child;
323 
324  if (record_child->isVisited())
325  {
326  TRY_DFPN;
328  record->setLoopWithPath<attacker>(pass_left, path);
329  record->setResult<attacker>(pass_left, NtesukiResult(1, 1),
330  NtesukiMove::INVALID(), false);
331  CATCH_DFPN;
332  RETURN;
333  }
334  else if (!record_child_orig->getValue<attacker>(pass_left_child).isCheckmateFail())
335  {
337  RETURN;
338  }
339 
340  const PathEncoding path_child(path, best_move.getMove());
341  result = record_child->getValueWithPath<attacker>(pass_left_child, path_child);
342 
343  if (result.isUnknown())
344  {
346  record_child,
347  record_child_orig,
348  pass_left_child,
349  best_move.getMove());
350  TRY_DFPN;
351  ApplyMoveWithPath<P>::doUndoMoveOrPass(state, path, best_move.getMove(), helper);
352  CATCH_DFPN;
353  if (record->getValueWithPath<attacker>(pass_left, path).isFinal())
354  {
355  result = record->getValueWithPath<attacker>(pass_left, path);
356  RETURN;
357  }
358  }
359 
360  if (result == ProofDisproof::LoopDetection())
361  {
362  TRY_DFPN;
363  record->setLoopWithPath<attacker>(pass_left, path);
364  record->setResult<attacker>(pass_left, NtesukiResult(1, 1),
365  NtesukiMove::INVALID(), false);
366  CATCH_DFPN;
367  RETURN;
368  }
369  else if (result.isCheckmateFail())
370  {
371  NtesukiMove move(best_move.getMove());
372  TRY_DFPN;
373  move.setCheckmateFail<attacker>(pass_left);
374  record->setResult<attacker>(pass_left, result, move, true);
375  CATCH_DFPN;
376  RETURN;
377  }
378  else
379  {
380  /* best_move is invalid : some rare casese, including
381  * - the original state was invalid(attacker was under check)
382  */
383  // ntesuki_assert(record_orig->getValue<attacker>(pass_left)
384  // == ProofDisproof::AttackBack());
385  result = ProofDisproof::Checkmate();
386  RETURN;
387  }
388 }
389 
390 /* Start simulation to disproof, P as Attacker.
391  * @return true, if nocheckmate is proven
392  */
393 template <Player P>
394 bool
395 NtesukiSimulationSearcher::
396 startFromAttackDisproof(NtesukiRecord *record,
397  const NtesukiRecord *record_orig,
398  const unsigned int pass_left,
399  const Move last_move)
400 {
401  ++disproof_count;
402  const Player attacker = P;
403  ntesuki_assert(record_orig);
404  if (!record_orig->getValue<attacker>(pass_left).isCheckmateFail())
405  return false;
406 
407  TRY_DFPN;
408  attackForDisproof<P>(record, record_orig, pass_left, last_move);
409  CATCH_DFPN;
410  if (result.isCheckmateFail())
411  {
412  ++disproof_success_count;
413  return true;
414  }
415  return false;
416 }
417 
418 /* Start simulation to disproof, P as Defender.
419  * @return true, if nocheckmate is proven
420  */
421 template <Player P>
422 bool
423 NtesukiSimulationSearcher::
424 startFromDefenseDisproof(NtesukiRecord *record,
425  const NtesukiRecord *record_orig,
426  const unsigned int pass_left,
427  const Move last_move)
428 {
429  ntesuki_assert (P == state.turn());
430  ++disproof_count;
431  const Player attacker = PlayerTraits<P>::opponent;
432  ntesuki_assert(record_orig);
433  if (!record_orig->getValue<attacker>(pass_left).isCheckmateFail())
434  return false;
435 
436  TRY_DFPN;
437  defenseForDisproof<P>(record, record_orig, pass_left, last_move);
438  CATCH_DFPN;
439  if (result.isCheckmateFail())
440  {
441  ++disproof_success_count;
442  return true;
443  }
444  return false;
445 }
446 
447 #undef RETURN
448 
449 // ;;; Local Variables:
450 // ;;; mode:c++
451 // ;;; c-basic-offset:2
452 // ;;; End: