immediateCheckmate.tcc
Go to the documentation of this file.
1 /* immediateCheckmate.tcc
2  */
3 #ifndef OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC
4 #define OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC
5 #include "osl/checkmate/immediateCheckmate.h"
6 #include "osl/checkmate/immediateCheckmateTable.h"
7 #include "osl/move_classifier/kingOpenMove.h"
8 #include "osl/bits/directionTraits.h"
9 #include "osl/bits/pieceTable.h"
10 #include "osl/bits/mask.h"
11 
12 namespace osl
13 {
14  namespace checkmate
15  {
16  namespace detail {
17  using osl::misc::BitOp;
18  template<Player P>
19  bool blockingVerticalAttack(NumEffectState const& state,Square pos)
20  {
21  PieceMask effect=state.effectSetAt(pos)&
22  state.effectSetAt(pos+DirectionPlayerTraits<U,P>::offset());
23  mask_t mask=effect.getMask(1); // longは常に1
24  mask&=(state.piecesOnBoard(P).getMask(1)<<8);
25  if((mask&mask_t::makeDirect(PtypeFuns<LANCE>::indexMask<<8)).none()){
26  mask&=mask_t::makeDirect(PtypeFuns<ROOK>::indexMask<<8);
27  while(mask.any()){
28  int num=mask.takeOneBit()+NumBitmapEffect::longToNumOffset;
29  Square from=state.pieceOf(num).square();
30  assert(from.isOnBoard());
31  if(from.isU<P>(pos)) goto found;
32  }
33  return false;
34  found:;
35  }
36  const Offset offset=DirectionPlayerTraits<U,P>::offset();
37  pos+=offset;
38  const Player altP=alt(P);
39  for(int i=0;i<3;i++,pos+=offset){
40  Piece p=state.pieceAt(pos);
41  if(p.canMoveOn<altP>()){ // 自分の駒か空白
42  if(state.countEffect(P,pos)==1) return true;
43  if(!p.isEmpty()) return false;
44  }
45  else return false;
46  }
47  return false;
48  }
49  template<Player P>
50  bool
51 #ifdef __GNUC__
52  __attribute__ ((pure))
53 #endif
54  blockingDiagonalAttack(NumEffectState const& state,Square pos,Square target,
55  King8Info canMoveMask)
56  {
57  const Player altP=alt(P);
58  Square to=target-DirectionPlayerTraits<U,P>::offset();
59  // Uに相手の駒がある
60  if((canMoveMask.uint64Value()&(0x10000<<U))==0) return false;
61  PieceMask effect=state.effectSetAt(to)&state.effectSetAt(pos);
62  mask_t mask=effect.getMask(1); // longは常に1
63  mask&=(state.piecesOnBoard(P).getMask(1)<<8);
64  mask&=mask_t::makeDirect(PtypeFuns<BISHOP>::indexMask<<8);
65  while(mask.any()){
66  int num=mask.takeOneBit()+NumBitmapEffect::longToNumOffset;
67  Square from=state.pieceOf(num).square();
68  assert(from.isOnBoard());
69  Offset offset=Board_Table.getShort8OffsetUnsafe(to,from);
70  if(to+offset != pos) continue;
71  if(state.countEffect(P,to)==1) return true;
72  // Uがspaceだと絡んでくる
73  if(!state.pieceAt(to).isEmpty()) return false;
74  Square pos1=to-offset;
75  // BISHOPの利き一つで止めていた
76  Piece p=state.pieceAt(pos1);
77  if(p.canMoveOn<altP>() &&
78  state.countEffect(P,pos1)==1){
79  return true;
80  }
81  }
82  return false;
83  }
84  template<Player P,bool canDrop,bool setBestMove>
85  bool hasKnightCheckmate(NumEffectState const& state,
86  Square target,
87  Square pos,
88  King8Info canMoveMask,
89  Move& bestMove, mask_t mask1)
90  {
91  if(!pos.isOnBoard()) return false;
92  const Player altP=alt(P);
93  Piece p=state.pieceAt(pos);
94  if(p.canMoveOn<P>() &&
95  !state.hasEffectByNotPinned(altP,pos)
96  ){
97  mask_t mask=state.effectSetAt(pos).getMask<KNIGHT>()&mask1;
98  if(mask.any()){
99  if(blockingVerticalAttack<P>(state,pos) ||
100  blockingDiagonalAttack<P>(state,pos,target,canMoveMask)) return false;
101  if(setBestMove){
102  int num=mask.takeOneBit()+(PtypeFuns<KNIGHT>::indexNum<<5);
103  Piece p1=state.pieceOf(num);
104  Square from=p1.square();
105  bestMove=Move(from,pos,KNIGHT,p.ptype(),false,P);
106  }
107  return true;
108  }
109  else if(canDrop && p.isEmpty()){
110  if(blockingVerticalAttack<P>(state,pos) ||
111  blockingDiagonalAttack<P>(state,pos,target,canMoveMask)) return false;
112  if(setBestMove)
113  bestMove=Move(pos,KNIGHT,P);
114  return true;
115  }
116  }
117  return false;
118  }
119  // KNIGHT
120  // KNIGHTのdropは利きを遮ることはない
121  template<Player P,bool setBestMove>
122  bool hasCheckmateMoveKnight(NumEffectState const& state, Square target,
123  King8Info canMoveMask,Move& bestMove)
124  {
125  // 8近傍に移動できる時は桂馬の一手詰めはない
126  if((canMoveMask.uint64Value()&0xff00)!=0) return false;
127  mask_t mask=mask_t::makeDirect(PtypeFuns<KNIGHT>::indexMask);
128  mask&=state.piecesOnBoard(P).getMask<KNIGHT>();
129  mask&= ~state.promotedPieces().getMask<KNIGHT>();
130  mask&= ~state.pinOrOpen(P).getMask<KNIGHT>();
131  if(state.hasPieceOnStand<KNIGHT>(P)){
132  Square pos=target-DirectionPlayerTraits<UUR,P>::offset();
133  if(hasKnightCheckmate<P,true,setBestMove>(state,target,pos,canMoveMask,bestMove,mask))
134  return true;
135  pos=target-DirectionPlayerTraits<UUL,P>::offset();
136  return hasKnightCheckmate<P,true,setBestMove>(state,target,pos,canMoveMask,bestMove,mask);
137  }
138  else{
139  Square pos=target-DirectionPlayerTraits<UUR,P>::offset();
140  if(hasKnightCheckmate<P,false,setBestMove>(state,target,pos,canMoveMask,bestMove,mask))
141  return true;
142  pos=target-DirectionPlayerTraits<UUL,P>::offset();
143  return hasKnightCheckmate<P,false,setBestMove>(state,target,pos,canMoveMask,bestMove,mask);
144  }
145  return false;
146  }
147  template<Player P,bool setBestMove>
148  bool slowCheckDrop(NumEffectState const& state,Square target,
149  Ptype ptype,King8Info canMoveMask,Move& bestMove)
150  {
151  unsigned int dropMask=(canMoveMask.uint64Value()&0xff)
152  &Immediate_Checkmate_Table.ptypeDropMask(ptype,canMoveMask);
153  // dropMaskが0ならここに来ない
154  assert(dropMask!=0);
155  while(dropMask!=0){
156  int i=BitOp::takeOneBit(dropMask);
157  Direction d=static_cast<Direction>(i);
158  unsigned int blockingMask=Immediate_Checkmate_Table.blockingMask(ptype,d) &
159  (canMoveMask.uint64Value()>>16);
160  Square drop=target-Board_Table.getOffset<P>(d);
161  if(blockingMask!=0){
162  NumBitmapEffect effect=state.effectSetAt(drop);
163  mask_t longEffect=effect.getMask(1)&NumBitmapEffect::longEffectMask();
164  longEffect&=(state.piecesOnBoard(P).getMask(1)<<8);
165  if(longEffect.any()){
166  do{
167  int j=BitOp::takeOneBit(blockingMask);
168  Direction d1=static_cast<Direction>(j);
169  Square pos=target-Board_Table.getOffset<P>(d1);
170  NumBitmapEffect effect1=state.effectSetAt(pos);
171  if(effect1.countEffect(P)>1) continue;
172  mask_t longEffect1=effect1.getMask(1)&longEffect;
173  if(!longEffect1.any()) continue;
174  //
175  int num=longEffect1.takeOneBit()+NumBitmapEffect::longToNumOffset;
176  if(Board_Table.isBetween(drop,state.pieceOf(num).square(),pos))
177  goto tryNext;
178  }while(blockingMask!=0);
179  }
180  }
181  // blockingMaskの点がすべてOKならOK
182  if(setBestMove)
183  bestMove=Move(drop,ptype,P);
184  return true;
185  tryNext:;
186  }
187  return false;
188  }
189  } // detail
190  } // checkmate
191 } // osl
192 
193 // not KNIGHT
194 template<osl::Player P,bool setBestMove>
195 bool osl::checkmate::ImmediateCheckmate::
196 hasCheckmateDrop(NumEffectState const& state, Square target,
197  King8Info canMoveMask,Move& bestMove)
198 {
199  typedef misc::GeneralMask<unsigned short> mask_t;
200  mask_t dropPtypeMask=mask_t::makeDirect(Immediate_Checkmate_Table.dropPtypeMask(canMoveMask));
201  while(dropPtypeMask.any()){
202  Ptype ptype=static_cast<Ptype>(dropPtypeMask.takeOneBit()+PTYPE_BASIC_MIN);
203  if(state.hasPieceOnStand(P,ptype) &&
204  detail::slowCheckDrop<P,setBestMove>(state,target,ptype,canMoveMask,
205  bestMove))
206  return true;
207  }
208  return false;
209 }
210 
211 template<osl::Player P,bool setBestMove>
212 bool osl::checkmate::ImmediateCheckmate::
213 slowHasCheckmateMoveDirPiece(NumEffectState const& state, Square target,
214  King8Info canMoveMask,Direction d,Square pos,Piece p,Ptype ptype,Move& bestMove){
215  const Player altP=alt(P);
216  // ptypeがPROOKの時は,更なるチェックが必要
217  if(ptype==PROOK){
218  int dx=target.x()-pos.x();
219  int dy=target.y()-pos.y();
220  if(abs(dx)==1 && abs(dy)==1){
221  {
222  Square pos1=pos+Offset(dx,0);
223  Piece p1=state.pieceAt(pos1);
224  if(!p1.isEmpty()){
225  {
226  // * -OU *
227  // (A)(B)(D)
228  // * (C) *
229  // (E) * *
230  // +RY (C) -> (A), (E) -> (A)
231  // -?? - (B)
232  // (D) - 竜以外の利きなし
233  Square pos2=pos+Offset(2*dx,0);
234  if(state.pieceAt(pos2).template canMoveOn<altP>()){
235  NumBitmapEffect effect2=state.effectSetAt(pos2);
236  if(effect2.countEffect(P)==0 ||
237  (effect2.countEffect(P)==1 &&
238  effect2.test(p.number())))
239  return false;
240  }
241  }
242  {
243  // * -OU *
244  // (A)(B) *
245  // * (C) *
246  // +RY (C) -> (A)
247  // -?? - (B)竜でpinされているが実はAへの利き持つ
248  if(p.square()==target-Offset(0,2*dy) &&
249  state.hasEffectByPiece(p1,pos))
250  return false;
251  }
252  }
253  }
254  {
255  Square pos1=pos+Offset(0,dy);
256  Piece p1=state.pieceAt(pos1);
257  if(!p1.isEmpty()){
258  Square pos2=pos+Offset(0,2*dy);
259  {
260  if(state.pieceAt(pos2).template canMoveOn<altP>()){
261  NumBitmapEffect effect2=state.effectSetAt(pos2);
262  if(effect2.countEffect(P)==0 ||
263  (effect2.countEffect(P)==1 &&
264  effect2.test(p.number())))
265  return false;
266 
267  }
268  {
269  // (C)(B)-OU
270  // * (A) *
271  // +RY (C) -> (A)
272  // -?? - (B)竜でpinされているが実はAへの利き持つ
273  if(p.square()==target-Offset(2*dx,0) &&
274  state.hasEffectByPiece(p1,pos))
275  return false;
276  }
277  }
278  }
279  }
280  }
281  }
282  // 元々2つの利きがあったマスが,
283  // block & 自分の利きの除去で利きがなくなることはあるか?
284  // -> ある.
285  // +KA * *
286  // * (A) +KI
287  // * -OU (B)
288  // * * *
289  // で金がAに移動して王手をかけると,Bの利きが2から0になる.
290  mask_t mask=mask_t::makeDirect((canMoveMask.uint64Value()>>16)&Immediate_Checkmate_Table.noEffectMask(ptype,d));
291  if(mask.any()){
292  int num=p.number();
293  NumBitmapEffect effect2=state.effectSetAt(pos);
294  effect2.reset(num+8);
295  mask_t longEffect2=effect2.getMask(1)&NumBitmapEffect::longEffectMask();
296  longEffect2&=(state.piecesOnBoard(P).getMask(1)<<8);
297  do {
298  Direction d1=static_cast<Direction>(mask.takeOneBit());
299  Square pos1=target-Board_Table.getOffset<P>(d1);
300  NumBitmapEffect effect1=state.effectSetAt(pos1);
301  int count=effect1.countEffect(P);
302  // 自分の利きの除去
303  if(effect1.test(num)) count--;
304  if(count==0) return false;
305  // blockしている利きの除去
306  mask_t longEffect1=effect1.getMask(1)&longEffect2;
307  while(longEffect1.any()){
308  int num1=longEffect1.takeOneBit()+NumBitmapEffect::longToNumOffset;
309  if(Board_Table.isBetween(pos,state.pieceOf(num1).square(),pos1))
310  count--;
311  if(count==0) return false;
312  }
313  } while (mask.any());
314  }
315  // 自殺手でないことのチェックを入れる
316  if(move_classifier::KingOpenMove<P>::isMember(state,ptype,p.square(),pos)) return false;
317  if(setBestMove){
318  bestMove=Move(p.square(),pos,ptype,
319  state.pieceAt(pos).ptype(),
320  ptype!=p.ptype(),P);
321  }
322  return true;
323 }
324 
325 template<osl::Player P,bool setBestMove>
326 bool osl::checkmate::ImmediateCheckmate::
327 hasCheckmateMoveDirPiece(NumEffectState const& state, Square target,
328  King8Info canMoveMask,Direction d,Square pos,Piece p,Move& bestMove){
329  Square from=p.square();
330  Ptype ptype=p.ptype();
331  // 相手の利きが伸びてしまって移動後も利きがついてくる可能性
332  {
333  const Player altP=alt(P);
334  Direction d1=Board_Table.getShort8Unsafe<P>(from,pos);
335  if(d1!=DIRECTION_INVALID_VALUE){ // not knight move
336  int num=state.longEffectNumTable()[p.number()][P==BLACK ? d1 : inverse(d1)];
337  if(num != EMPTY_NUM && state.pieceOf(num).isOnBoardByOwner<altP>())
338  return false;
339  }
340  }
341  if(canPromote(ptype) &&
342  (from.canPromote<P>() || pos.canPromote<P>())){
343  Ptype pptype=promote(ptype);
344  if((((canMoveMask.uint64Value()>>8)|0x100)&
345  Immediate_Checkmate_Table.noEffectMask(pptype,d))==0){
346  if(slowHasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,p,pptype,bestMove)) return true;
347  }
348  if (ptype==PAWN || /*basic because canpromote*/isMajorBasic(ptype))
349  return false;
350  }
351  if((((canMoveMask.uint64Value()>>8)|0x100)&
352  Immediate_Checkmate_Table.noEffectMask(ptype,d))==0){
353  if(slowHasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,p,ptype,bestMove)) return true;
354  }
355  return false;
356 }
357 
358 template<osl::Player P,bool setBestMove>
359 bool osl::checkmate::ImmediateCheckmate::
360 hasCheckmateMoveDir(NumEffectState const& state, Square target,
361  King8Info canMoveMask,Direction d,Move& bestMove){
362  Square pos=target-Board_Table.getOffset<P>(d);
363  if(state.countEffect(P,pos)<2 &&
364  !effect_util::AdditionalEffect::hasEffect(state,pos,P)) return false;
365  PieceMask pieceMask=state.piecesOnBoard(P)&state.effectSetAt(pos);
366  assert(pos.isOnBoard());
367  // 玉で王手をかけない
368  pieceMask.reset(KingTraits<P>::index);
369  for(int i=0;i<=PieceMask::numToIndex(40);i++){
370  mask_t mask=pieceMask.getMask(i);
371  while (mask.any()){
372  const int num=mask.takeOneBit()+i*32;
373  if(hasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,state.pieceOf(num),bestMove)) return true;
374  }
375  }
376  return false;
377 }
378 
379 // not KNIGHT
380 template<osl::Player P,bool setBestMove>
381 bool osl::checkmate::ImmediateCheckmate::
382 hasCheckmateMove(NumEffectState const& state, Square target,
383  King8Info canMoveMask,Move& bestMove)
384 {
385  assert(! state.inCheck());
386  typedef misc::GeneralMask<unsigned int> mask_t;
387  mask_t mask2=mask_t::makeDirect((canMoveMask.uint64Value()>>24)&0xff);
388  while(mask2.any()){
389  Direction d=static_cast<Direction>(mask2.takeOneBit());
390  if(hasCheckmateMoveDir<P,setBestMove>(state,target,canMoveMask,d,bestMove)) return true;
391  }
392  return false;
393 }
394 
395 template<osl::Player P>
396 bool osl::checkmate::ImmediateCheckmate::
397 hasCheckmateMove(NumEffectState const& state, King8Info canMoveMask)
398 {
399  const Player altP=alt(P);
400  const Square target=state.kingSquare(altP);
401  assert(target.isOnBoard());
402  // 相手からの王手がかかっていない
403  Move dummy;
404  if(hasCheckmateMove<P,false>(state,target,canMoveMask,dummy)) return true;
405  if(detail::hasCheckmateMoveKnight<P,false>(state,target,canMoveMask,dummy)) return true;
406  return hasCheckmateDrop<P,false>(state,target,canMoveMask,dummy);
407 }
408 
409 template<osl::Player P>
410 bool osl::checkmate::ImmediateCheckmate::
411 hasCheckmateMove(NumEffectState const& state)
412 {
413  const Player altP=alt(P);
414 #ifndef NDEBUG
415  const Square target=state.kingSquare(altP);
416 #endif
417  assert(target.isOnBoard());
418  King8Info canMoveMask(state.Iking8Info(altP));
419  return hasCheckmateMove<P>(state, canMoveMask);
420 }
421 
422 template<osl::Player P>
423 bool osl::checkmate::ImmediateCheckmate::
424 hasCheckmateMove(NumEffectState const& state, King8Info canMoveMask,
425  Square target, Move& bestMove)
426 {
427  assert(! state.inCheck());
428  assert(target.isOnBoard());
429 
430  if(hasCheckmateMove<P,true>(state,target,canMoveMask,bestMove)) return true;
431  if(detail::hasCheckmateMoveKnight<P,true>(state,target,canMoveMask,bestMove)) return true;
432  return hasCheckmateDrop<P,true>(state,target,canMoveMask,bestMove);
433 }
434 
435 template<osl::Player P>
436 bool osl::checkmate::ImmediateCheckmate::
437 hasCheckmateMove(NumEffectState const& state,Move& bestMove)
438 {
439  const Player altP=alt(P);
440  const Square target=state.kingSquare(altP);
441  King8Info canMoveMask(state.Iking8Info(altP));
442  return hasCheckmateMove<P>(state, canMoveMask, target, bestMove);
443 }
444 
445 #endif /* OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC */
446 // ;;; Local Variables:
447 // ;;; mode:c++
448 // ;;; c-basic-offset:2
449 // ;;; End:
450